Как FriendFeed использует MySQL для хранения данных без схемы

Original author: Bret Taylor
  • Translation

Условия


Мы используем MySQL для хранения любых данных FriendFeed. Наша база данных растёт вместе с числом пользователей. Сейчас у нас более 250 миллионов записей, это записи пользователей (post'ы), комментарии, оценки («likes»)

По мере того как росла база данных, мы время от времени имели дело с проблемами масштабируемости. Мы решали проблемы стандартными путями: slave-сервера, используемые только для чтения, memcache для увеличения пропускной способности чтения и секционирование для увеличения пропускной способности записи. Однако, по мере роста, использованные методы масштабируемости привели к затруднению добавлению новой функциональности.

В частности, изменение схемы базы данных или добавление индексов к существующим 10-20 миллионов записей приводили к полной блокировке сервера на несколько часов. Удаление старых индексов требовало времени, а не удаление ударяло по производительности, так как база данных продолжала использовать их на каждом INSERT. Существуют сложные процедуры с помощью которых можно обойти эти проблемы (например создание нового индекса на slave-сервере, и последующий обмен местами master'a и slave), однако эти процедуры настолько тяжелые и опасные, что они окончательно лишили нас желания добавлять что-то новое, требующее изменение схемы или индекса. А так как наши базы сильно распределены, реляционные вещи MySQL как например JOIN никогда не работали для нас. Тогда мы решили поискать решение проблем, лежащее вне реляционных баз данных.

Существует множество проектов, призванных решить проблему хранения данных с гибкой схемой и построением индексов на лету (например CouchDB). Однако, по-видимому ни один из них не используется крупными сайтами. В тестах о которых мы читали и прогоняли сами, ни один из проектов не показал себя стабильным, достаточно зрелым для наших целей (см. this somewhat outdated article on CouchDB, например). А все это время MySQL работал. Он не портил данные. Репликация работала. Мы уже в достаточной мере понимали все его узкие места. Нам нравился MySQL именно как хранилище, вне реляционных шаблонов.

Все взвесив, мы решили создать систему хранения данных без схемы поверх MySQL, вместо использования полностью нового решения. В этой статье я попытаюсь описать основные детали системы. Так же нам любопытно как другие сайты решили эти проблемы. Ну и мы думаем, что наша работа будет полезна другим разработчикам.

Введение


Наша база данных хранит данные без схемы в виде множества полей (например JSON объекты или словари (dictionary) в Python). Единственное обязательное поле — это id, 16-байтный UUID. Остальное должно быть не важно для нашего хранилища, именно за этим оно создаётся. Мы «изменяем» схему, просто добавив новые поля.

Будем индексировать данные записей и сохранять индекс в отдельной MySQL таблице. Если мы захотим проиндексировать 3 поля каждой записи, мы получим 3 MySQL таблицы — по одной на каждый индекс. Если больше не нуждаемся в индексе, мы перестаём писать в таблицу индекса, и можем удалить таблицу при желании. Если требуется новый индекс, мы создаём новую таблицу MySQL для него и запускаем асинхронный процесс для заполнения индекса, не прерывая остальные задачи.

Как результат, мы получаем большее число таблиц чем было до этого, но добавление и удаление индексов упростилось. Мы серьезно оптимизировали процесс для заполнения индексов (который мы назвали «The Cleaner»), так чтобы он создавал индексы быстро без нарушения работы сайта. Теперь мы можем добавлять новые свойства и индексировать за дни, а не недели. Так же теперь не требуется обмен master на slave или другие опасные операции.

Детали


В MySQL наши записи хранятся следующим образом:
Copy Source | Copy HTML
  1. CREATE TABLE entities (
  2.     added_id INT NOT NULL AUTO_INCREMENT PRIMARY KEY,
  3.     id BINARY(16) NOT NULL,
  4.     updated TIMESTAMP NOT NULL,
  5.     body MEDIUMBLOB,
  6.     UNIQUE KEY (id),
  7.     KEY (updated)
  8. ) ENGINE=InnoDB;

Столбец added_id нужен из-за того, что InnoDB физически сохраняет данные в порядке первичного ключа. AUTO_INCREMENT ключи гарантируют, что новые записи записаны на жесткий диск следом за старыми, что помогает и чтению, и записи (доступ к новым записи как правило происходит чаще, чем к старым записям, поэтому страницы FriendFeed отсортированы в обратном хронологическом порядке). Тело записи хранится как сжатый (zlib) Python-pickled словарь.

Индексы хранятся в отдельных таблицах. Для нового индекса мы создаём таблицу с атрибутами, по которым мы хотим осуществлять поиск. Для примера, запись в FriendFeed выглядит примерно так:
Copy Source | Copy HTML
  1. {
  2.     "id": "71f0c4d2291844cca2df6f486e96e37c",
  3.     "user_id": "f48b0440ca0c4f66991c4d5f6a078eaf",
  4.     "feed_id": "f48b0440ca0c4f66991c4d5f6a078eaf",
  5.     "title": "We just launched a new backend system for FriendFeed!",
  6.     "link": "http://friendfeed.com/e/71f0c4d2-2918-44cc-a2df-6f486e96e37c",
  7.     "published": 1235697046,
  8.     "updated": 1235697046,
  9. }

Мы хотим проиндексировать по полю user_id для отображения всех записей, что сделал пользователь. Наша индекс-таблица выглядит следующим образом:
Copy Source | Copy HTML
  1. CREATE TABLE index_user_id (
  2.     user_id BINARY(16) NOT NULL,
  3.     entity_id BINARY(16) NOT NULL UNIQUE,
  4.     PRIMARY KEY (user_id, entity_id)
  5. ) ENGINE=InnoDB;

Наша библиотека автоматически создаёт индексы. Для старта нашего хранилища, которое сохраняет подобные записи с индексом, описанным выше, мы пишем (на Python):
Copy Source | Copy HTML
  1. user_id_index = friendfeed.datastore.Index(
  2.     table="index_user_id", properties=["user_id"], shard_on="user_id")
  3.  
  4. datastore = friendfeed.datastore.DataStore(
  5.     mysql_shards=["127.0.0.1:3306", "127.0.0.1:3307"],
  6.     indexes=[user_id_index])
  7.  
  8. new_entity = {
  9.     "id": binascii.a2b_hex("71f0c4d2291844cca2df6f486e96e37c"),
  10.     "user_id": binascii.a2b_hex("f48b0440ca0c4f66991c4d5f6a078eaf"),
  11.     "feed_id": binascii.a2b_hex("f48b0440ca0c4f66991c4d5f6a078eaf"),
  12.     "title": u"We just launched a new backend system for FriendFeed!",
  13.     "link": u"http://friendfeed.com/e/71f0c4d2-2918-44cc-a2df-6f486e96e37c",
  14.     "published": 1235697046,
  15.     "updated": 1235697046,
  16. }
  17.  
  18. datastore.put(new_entity)
  19.  
  20. entity = datastore.get(binascii.a2b_hex("71f0c4d2291844cca2df6f486e96e37c"))
  21. entity = user_id_index.get_all(datastore, user_id=binascii.a2b_hex("f48b0440ca0c4f66991c4d5f6a078eaf"))
  22.  

Index класс смотрит на поле user_id во всех записях и автоматически создаёт индекс в таблице index_user_id. Так как наша база данных секционирована (sharding), аргумент shard_on используется для определения в какой сегменте будет храниться индекс (в нашем случае entity[«user_id»] % num_shards)

Для выполнения запроса с использованием созданного индекса используется объект класса Index (см. user_id_index.get_all). Алгоритм «хранилища» делает «join» таблиц index_user_id и таблицы с записями, сначала пробегаясь по всем таблицам index_user_id на всех сегментах базы данных для получения списка ID записей и затем получает эти записи из таблицы entities.

Для создания нового индекса, например по атрибуту link, мы создадим таблицу:
Copy Source | Copy HTML
  1. CREATE TABLE index_link (
  2.     link VARCHAR(735) NOT NULL,
  3.     entity_id BINARY(16) NOT NULL UNIQUE,
  4.     PRIMARY KEY (link, entity_id)
  5. ) ENGINE=InnoDB DEFAULT CHARSET=utf8;

Код включения нового индекса будет:
Copy Source | Copy HTML
  1. user_id_index = friendfeed.datastore.Index(
  2.     table="index_user_id", properties=["user_id"], shard_on="user_id")
  3. link_index = friendfeed.datastore.Index(
  4.     table="index_link", properties=["link"], shard_on="link")
  5. datastore = friendfeed.datastore.DataStore(
  6.     mysql_shards=["127.0.0.1:3306", "127.0.0.1:3307"],
  7.     indexes=[user_id_index, link_index])

Так же мы можем заполнить индекс асинхронно (даже во время реальной работы) с помощью процесса:

./rundatastorecleaner.py --index=index_link

Cогласованность и атомарность


Из-за того что база данных сегментирована, индекс для конкретной записи могут находиться на разных сегментах. Что произойдет, если процесс непредвиденно завершится до того, как запишет все индексы по таблицам?

Самые амбициозные FriendFeed инженеры считали, что транзакции необходимы в данной ситуации. Однако мы хотели сохранить нашу систему как можно более простой. Мы решили ослабить ограничения:
  • Набор атрибутов хранящийся в главной таблице записей — канонический
  • Индекс может возвращать неподходящие записи.

В результате, мы создаём новую запись в следующем порядке:
  1. Сохраняем запись в основную таблицу, пользуясь ACID гарантиями InnoDB (Atomicity, Consistency, Isolation, Durability).
  2. Сохраняем индексы во все индекс-таблицы на всех сегментах

Когда мы читаем из индекс таблиц, мы знаем что результат может быть неточен (то есть результат может содержать лишние объекты, если запись не была закончена на шаге 2). Чтобы убедиться, что мы возвращаем правильные записи, мы повторно фильтруем результат, полученный из индекс таблиц:
  1. Читаем entity_id из всех индекс-таблиц, участвующих в запросе
  2. Читаем все записи по полученным id
  3. Фильтруем (в Python) все записи, что не подходят по критериям запроса.

Для испраления индексов создан процесс «Cleaner» (чистильщик), который упоминался ранее. Он запускается по таблице записей, записывая пропущенные индексы, удаляя старые и исправляя не верные. Он начинает с новых записей, на практике все неточности исправляются очень быстро (в течение нескольких секунд).

Производительность


Мы немного оптимизировали наши первичные ключи в новой системе и довольны результатом. Ниже диаграмма задержек перед отдачей страницы FriendFeed за последний месяц (мы запустили новый backend несколько дней назад):



В частности, задержка нашей системы стабильна, даже во время пиков в середине дня. Ниже диаграмма за последние 24 hours:



Сравните с задержками неделю назад:



С новой системой стало на много легче работать. Мы уже изменили индексы несколько раз на рабочей системе, и сейчас начинаем миграцию наших главных таблиц, дабы двигаться дальше.

How FriendFeed uses MySQL to store schema-less data, by Bret Taylor • February 27, 2009
Так же рекомендую к прочтению обсуждение этой статьи на популярном mysqlperformanceblog.com
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 60

  • UFO just landed and posted this here
    0
    Необычное решение!
      +4
      Автор оригинальной статьи до того, как основал FriendFeed, работал в Google в команде, которая занимается App Engine. Нереляционное хранилище Datastore из App Engine выглядит для программиста почти так же, как и решение из статьи. Только вместо MySQL в основе Datastore лежил распределенный BigTable.
        0
        Я просто не встречался с подобным в MySQL (:
          0
          Кстати, странно что они сами в BigTable не хранят данные)
          +4
          На самом деле ничего необычного. Просто решили построить на основе MySQL key-value базу данных.

          Хорошо это или плохо — на этот счет могут быть разные мнения. Я предпочитаю использовать вещи по назначению. Есть отличные вещи, например, Redis, которые гораздо быстрей мускула (т.к. не реализуют много лишнего функционала, который предлагает мускул, а используют быструю событийную epoll-based архитектуру), и для них архитектура key-value родная, поэтому не прийдется писать своего кода на уровне приложения.

          Ну если уж очень хотелось использовать реляционное хранилище, то тогда уже можно было использовать Drizzle. Drizzle динамически развивающийся проект, который изначально заточен под хранение данных в вебе.
            +1
            Кстати, например, бенчмарк Drizzle vr. MySQL 5.1
            https://lists.launchpad.net/drizzle-discuss/msg03687.html
              +4
              Прелесть MySQL в том, что он стабилен, уже отработаны процедуры работы с ним (масштабирование, бекап и т.д.). Как раз на это часто жалуются разработчики, попробовавшие альтернативы из движения NoSQL.
                +2
                Интересно послушать про масштабирование MySQL.

                Для майтов с малым и средним посещениями и объемом хранимых данных — MySQL, либо другая СУРБД вполне приемлемый вариант.

                Для сайтов, которые имеют проблемы, описанные в статье MySQL вообще не подходит. В частности потому что очень плохо масштабируется горизонтально. (Если это вообще можно назвать возможностью масштабирования)

                Для подобных сайтов нужно использовать нереляционные подходы, key-value в частности.
                  –2
                  Прелесть как раз в том, что слушать не надо. Есть специально обученные люди, которые умеют это делать. Крутится же Facebook и другие сайты на нем.

                  А с любым новым инструментом надо набивать свои шишки, прежде чем появятся люди с опытом. Немного интересуюсь темой NoSQL, пока что отзывы попробовавших не очень. Например, groups.google.ru/group/ror2ru/browse_thread/thread/4d931804805637bd/f4bebb3f225503c9?lnk=gst&q=nosql#msg_61a5a9dbb0f5288e и groups.google.ru/group/ror2ru/browse_thread/thread/11e14f3768e0c2ec/5036099e41591d79?lnk=gst&q=couchdb#msg_15ffdeceb8164a61
                    +1
                    Facebook крутится как раз на NoSQL — Cassandra. На неё же с MySQL перешел и Digg на днях.
                      +1
                      тут вы тоже не совсем правы. Фейсбук не использует какую-то одну технологию, также как и один язык программирования. Масштабы не те.

                      Изначально Cassandra использовалась в фейсбук для рассылки сообщений

                      http://www.facebook.com/note.php?note_id=24413138919
                      0
                      Да, фейсбук использует мускул. О чем, собственно, они говорили http://rutube.ru/tracks/792307.html?v=2562849a5382df69dbd050d4ea9958c4

                      Фигурировало даже число в 2000 серверов сускула.
                      Но не стоит путать. Они используют мускул как персистент сторидж, не более и не менне.
                      Они не выполняют чтений оттуда, т.к. 99,9% чтений выполняются из кешей (мемкеш). Изменения данных, тоже не сразу пишутся. Запись идет булками в какое-то время или по какому-то событию. Это просто сторидж.
                      Притом какой там мускул тоже сложно сказать. Думаю, что-то больше похожее на Drizzle, чем на обычный мускул. Исходя из интервью, ссылку на которое я дал выше, данные о каждом пользователе лежат на разные БД серверах, т.е. это уже шардинг. Шардинг на уровне БД или приложения (если по userid выбирается сервер БД на который коннектиться) тоже сложно сказать.

                      Для построения же дерева связей, естественно, ни о каком MySQL речи быть не может. Думаю, для этого испосльзуют касандру. Хотя пруфлинков не нашел.

                      Ну а про специально оьбученых людей, тут совсем не серьезно… Вы же при выборе технологии не полагаетесь на каких-то абстрактных людей.
                        0
                        Известность технологии, возможность найти опытных разработчиков — один из важных принципов ее выбора. Если нет разработчиков, то явно нужно будет обучать. С новичками в технологии увеличиваются риски срыва сроков. А это (обучение и увеличение вероятности срыва сроков) не для всех типов проектов подходит.
                    0
                    MySQL был изначально проектирован, имея возможность только вертикального масштабирования. Золотой закон — чем больше памяти, тем лучше для MySQL. Сейчас MySQL уже, слава богу, начал лучше насштабироваться на многоядерные системы, т.к. еще до недавнего времени наилучшие результаты были на четырех ядрах.

                    Ну о чем говорить, если в мускуле даже шардинга нет? Есть только унылый партишенинг, который в абсолютном большинстве случаев не поможет.

                    Или вы репликацию называете надежной схемой масштабирования? А как же масштабирование записи? Пока единственно возможно решение это мастер-мастер (активно-пассивный режим, активно-активный). Если вы предлагаете репликацию кольцом, то ИМХО, key-value решения гораздо безопасней и отказоустойчивей.
                +4
                Плохая статья.

                В частности, изменение схемы базы данных или добавление индексов к существующим 10-20 миллионов записей приводили к полной блокировке сервера на несколько часов.
                Да, это исключительно особенность MySQL. Ни одна другая база не работает с индексами настолько медленно. Решать проблему плохого инструмента с помощью смены концепции — это вариант, но мне он не нравится.

                Существует множество проектов, призванных решить проблему хранения данных с гибкой схемой и построением индексов на лету (например CouchDB). Однако, по-видимому ни один из них не используется крупными сайтами.
                Это неправда. Достаточно посмотреть, откуда взялась Cassandra и кто использует Tokyo Cabinet, чтобы убедится в обратном.
                  +5
                  Статье больше года, а NoSQL набирает обороты только сейчас.
                    +6
                    Скажите это Berkeley DB :-)
                      +2
                      Кстати, в статье Bred и его коллеги по сути превратили MySQL в BDB.
                      entites — это объект с primary key added_id, а все остальные таблицы-индексы — это secondary key. На том уровне, на котором он поведал — BDB отлично справляется с задачей.

                      Единственное «но» — если им всё-таки понадобится выполнить один sql запрос — их решение справится, а вот BDB — увы.
                      +1
                      Скорее термин NOSQL набирает обороты, в то время как подобного класса БД сущестовали ещё до своих SQL собратьев
                      0
                      Разве Cassandra schema-less?
                        0
                        Да
                          0
                          Тогда как объясните это: «You define column families in your storage-conf.xml file, and cannot modify them (or add new column families) without restarting your Cassandra process.»
                            +1
                            A column family is a container for columns, analogous to the table in a relational system.
                            То есть вы задаете только коллекции столбцов, а не конкретный их набор.
                              0
                              Не понял. Допустим, я делаю анкету из 10 вопросов — коллекция из 10 столбцов. Чтобы добавить новый, одиннадцатый, мне надо перезапустить систему, или я не прав?
                                0
                                Просто присваиваете значение 11-ому столбцу. типа Ответы['боря'].answer11 = 'a'.
                        0
                        ну так это зависит от того, что за индекс. Хотя некоторые вот умеют строить индекс не блокируя модификации
                        0
                        Отличная статья! Интересная тема!
                          0
                          Сам этот подход не понравился, а вот ссылки на mysqlperformanceblog.com а из него далее на 37 сигналов хороши.
                          • UFO just landed and posted this here
                            • UFO just landed and posted this here
                              • UFO just landed and posted this here
                                  +3
                                  Файловая система
                                    +1
                                    Тупое ACID место.
                                      0
                                      man 2 flock
                                        +1
                                        Ok. Индексы тоже не помешают. Мы в качестве «тупого места» используем BDB.
                                          0
                                          Индексы рядом с файликами с данными. И грепом их, грепом :)
                                0
                                Очень интересное инженерное решение
                                  +2
                                  Как вы затейливо нарекли этот велосипед.
                                  0
                                  Я сейчас как раз озабочен проектированием БД для 30-ти сущностей, раздумываю над тем чтобы остановится на 2-х универсальных таблицах — таблице объектов и таблице их отношений
                                    +1
                                    FriendFeed использовал так называемый Scheme-less подход, полгода назад было упоминание на Хабре, сразу заинтересовало.

                                    Я где-то даже видел статью об инструментах проектирования БД на основе хранения XML в полях, но сейчас не могу ее найти, да и вообще, как-то мало информации по этой тематике, к сожалению.
                                      0
                                      К этому гениальному решению приходят, в какой-то момент, все. Если вам нужен безсхемный подход, возьмите безсхемную базу данных, не пытайтесь натянуть чужую парадигму на SQL-базу.
                                      0
                                      Использовал похожее решение в билинге, когда потребовалось добавить два индекса на одно поле на большой таблице MySQL. Этот костыль дался малой кровью только потому, что позволила специфика (в билинге записи после создания не меняются и их индексирование можно отложить).
                                      Но в общем случае, синхронизацию базовой таблицы и индексов довольно сложно реализовать. Я думаю, это главный из недостатков такой схемы.
                                        +5
                                        интересный подход, конечно, у команды проекта.

                                        практически в каждом случае они просматривали существующие решения только для того, чтобы спроектировать собственный велосипед: сервер Торнадо, фреймворк на нем, теперь по сути NoSQl поверх MySQL.

                                        это мир технологий так беден, или просто у программистов руки чесались до проектирования велосипедов?

                                          +3
                                          На вершине горы всегда одиноко. Большинство решений и технологий — все же для масс-рынка. Вырвавшимся вперед поневоле приходится изобретать что-то свое. Как минимум для сохранения конкурентного преимущества.
                                            +1
                                            да как сказать… вот, к примеру, те же фреймворки или сервера.

                                            на их поддержку и развитие требуется довольно много ресурсов, времени, проектирования. При необходимости поддерживать еще и сам продукт, опирающийся на технологию, усилия команды начинают распыляться.

                                            с другой стороны, появляется возможность принимать архитектурные решения исходя из нужд конкретного проекта.

                                            Но надстройки над БД… Не знаю, мне nosql кажется очень разумным решением, когда вся мощность sql попросту не нужна, а нужна масштабируемость и скорость.
                                          0
                                          читал это давно в оригинале. пожимаю плечами. для меня mongodb работает просто отлично. правда, не уверен что так было на момент написания статьи
                                            +1
                                            Масштабы Вашего проекта?
                                              0
                                              система счетчиков, наподобие google analytics. сотни, тысячи сайтов. при желании мастштабируется неограниченно т.к. данные легко шардятся
                                                +1
                                                baluev'у наверное было интересно ваше личное впечатление, в вашем проекте. Мне бы тоже, если честно, хотелось бы послушать человека используюещего монго в продакшне.
                                                  0
                                                  я не единственный, кто использует его в продакшене. из особенностей — обязательно нужно использовать репликацию, databaserepair, при больших объемах данных может длиться довольно долго. от кривых map-reduce запросов сервер падает(к счастью, падает в 100% случаев)
                                                    0
                                                    Скажите, а аналитику тоже с помощью MongoDB делаете? Просто читал на их сайте, что она в разделе Less Well Suited.
                                                    0
                                                    Ну все равно хотелось бы впечатления от незаинтересованного человека услышать, не все маркетинговые блоги читать.
                                            –6
                                            Да… Вот что бывает, когда иррационалы забивают на изначально качественное проектирование.

                                            Ради того, чтобы постоянно что-то менять менять концепцию и изобретать лисипед?? Ужос тихий.

                                            Хотя цель достигнута — куда деваца.
                                              0
                                              Реализация этого же подхода для ruby/rails:
                                              jamesgolick.com/2009/12/16/introducing-friendly-nosql-with-mysql-in-ruby.html
                                                +3
                                                господи, да это ж баян уже как год.
                                                всё, кто должны были это почитать, давно уже почитали в оригинале и прокнились этой интересной идеей.
                                                  –5
                                                  сразу убило «мы имеем»… всё же наверное «у нас есть» или «в нашей базе содержится».
                                                  или это гуглотранслейт перевод?

                                                  Only users with full accounts can post comments. Log in, please.