TAO - Распределенная база данных Facebook для Social Graph

Вступление

Я расскажу об архитектуре и ключевых принципах дизайна, изложенных в статье, опубликованной в Facebook о графовых базах данных. Это попытка обобщить архитектуру хорошо масштабируемой графовой базы данных, которая может поддерживать объекты и их ассоциации, для тяжелой рабочей нагрузки чтения, состоящей из миллиардов транзакций в секунду. В случае Facebook чтение составляет более 99% запросов, а запись - менее процента.

Фон

У Facebook миллиарды пользователей, и большинство из них потребляют контент чаще, чем создают контент. Так что очевидно, что их рабочая нагрузка очень высока. Поэтому они изначально реализовали распределенный внешний кэш с использованием memcach ed, на который в этой статье много ссылается. В этой рабочей нагрузке для поддержки всех операций чтения и записи в базу данных используется резервный кеш. Хорошая частота попаданий в кеш обеспечивает хорошую производительность и не приводит к перегрузке базы данных. На следующем рисунке показано, как внешний кэш на основе memcache используется в facebook для оптимизации чтения.

Хотя это чрезвычайно полезно, большая часть информации в Facebook лучше всего представлена с помощью социального графа, а контент, который отображается на странице, легко настраивается в зависимости от настроек конфиденциальности пользователей и персонализирован для каждого пользователя. Это означает, что данные необходимо хранить как есть, а затем фильтровать при просмотре / рендеринге.

Посмотрите на социальную диаграмму, которая создается на основе типичного простого действия, такого как: «Кто-то посетил мост Золотые Ворота с кем-то еще, а затем несколько человек прокомментировали это»

Представление этой информации в хранилище «ключ-значение», таком как резервный кеш, становится очень сложным и громоздким. Вот некоторые из основных мотивов создания собственного хранилища на основе графов:

Одна из возможных реализаций - использовать отформатированный список ребер как одно значение. Но это означает, что каждый доступ потребует загрузки всего списка ребер и такой же дополнительной модификации списка ребер. Можно было бы ввести собственные типы списков, которые можно связать с ключом. Но это решает только проблему эффективного поиска доступа к списку ребер. В социальном графе многие объекты связаны между собой, и координация таких обновлений с помощью списков ребер является сложной задачей.
В реализации кэша памяти в Facebook выдача кэша памяти указывает на то, что клиенты должны подождать некоторое время, и это предотвращает грохочение стада (чтение и запись одних и тех же популярных объектов, вызывающих промахи в кеше, а затем переход к базе данных). Это перемещает логику управления к клиентам, и, поскольку клиенты не общаются друг с другом, это усложняет ситуацию. В модели объектов и ассоциаций все управляется системой TAO, которая может их эффективно реализовать, и, следовательно, клиенты могут быстро выполнять итерацию.
Использование семантики графа позволяет более эффективно реализовать модель согласованности чтения после записи.

Таким образом, TAO вместо этого предоставляет объекты и ассоциации в качестве основных единиц доступа в системе. Он также оптимизируется для тяжелых чтений и в большинстве случаев является последовательным, но в случае сбоев обеспечивает согласованность в конечном итоге.

Модель данных

Модель данных состоит из двух основных сущностей:

Объект: он сопоставляет «id» с «Key, ObjectType, Value».

В приведенном выше примере Алиса является объектом типа User. Также комментарий, добавленный Кэти, представляет собой объект типа comment с текстом «желаю, чтобы мы были там». Объекты лучше представляют повторяющиеся вещи, например комментарии.

Ассоциация: отображает «Объект1, Тип ассоциации, Объект2» на «время, ключ, значение». Ассоциации представляют собой отношения, которые происходят не более одного раза. Два друга подключаются не более одного раза с помощью ассоциации. Полезность поля времени станет яснее в следующих разделах о том, как работают запросы.

В приведенном выше примере Алиса и Кэти связаны друг с другом с помощью типа ассоциации friend. Также два объекта checkin и золотые ворота location связаны друг с другом. Тип объединения в каждом направлении разный. Golden Gate объект местоположения связан с объектом регистрации с помощью типа ассоциации регистрации. В то время как объект отметки подключается к объекту местоположения "золотые ворота" с помощью типа привязки местоположения.

API для объектов и ассоциаций

API-интерфейсы объектов просты и позволяют создавать, изменять, удалять и извлекать объекты, используя их идентификаторы.

API создания, изменения и удаления ассоциаций в основном изменяют связь между двумя идентификаторами объектов с ассоциацией.

Более интересны API ассоциативных запросов. Здесь в игру вступает сила семантики графов. Рассмотрите такие запросы, как:

«Дайте мне последние 10 комментариев о проверке Алисы»

Это можно смоделировать как assoc_range (CHECKIN_ID, COMMENT, 0, 10). Здесь также пригодится поле времени, прикрепленное к ассоциациям. Поле времени можно использовать для простой сортировки подобных запросов.

«Сколько лайков получил комментарий Кэти?»

assoc_count (COMMENT_ID, LIKED_BY) Этот запрос вернет количество «лайков», связанных с отметкой.

Архитектура ТАО

Постоянного хранения

На высоком уровне TAO использует базу данных mysql в качестве постоянного хранилища объектов и ассоциаций. Таким образом, они получают все функции репликации базы данных, резервного копирования, миграции и т. Д., В то время как другие системы, такие как LevelDB, не соответствовали их потребностям в этом отношении.

Все содержимое системы разделено на шарды. Каждый object_id содержит в себе shard_id, отражающий логическое расположение этого объекта. Это означает поиск хоста для этого объекта. Также ассоциации хранятся в том же сегменте, что и исходный объект (помните, что ассоциация определяется как Object1, AssociationType, Object2). Это обеспечивает лучшую локальность и помогает получать объекты и ассоциации с одного и того же хоста. В системе гораздо больше шардов, чем количество хостов, на которых размещены серверы mysql. Так много шардов сопоставлено с одним хостом.

Все данные, принадлежащие объектам, сериализуются и сохраняются по идентификатору. Это делает дизайн таблицы объектов в базе данных mysql довольно простым. Ассоциация хранится с идентификатором аналогично ключу, и данные сериализуются и хранятся в одном столбце. С учетом упомянутых выше запросов на основе ассоциативных таблиц строятся дополнительные индексы для: исходного идентификатора (Object1), сортировки по времени, типа ассоциации.

Кэширующий слой

Как и в статье о memcache, по-прежнему очень важно разгрузить рабочую нагрузку базы данных с помощью уровня кэширования. Клиент, запрашивающий информацию, сначала подключается к кешу. Этот кеш принадлежит к уровню, состоящему из нескольких таких кешей и базы данных. Они несут коллективную ответственность за обслуживание объектов и ассоциаций.

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

Масштабирование кэширующих серверов: регионы, уровни, лидеры и последователи

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

Следовательно, идея состоит в том, чтобы иметь двухуровневую иерархию. Регион будет состоять из нескольких уровней, но только один уровень будет уровнем лидера, а остальные - уровнями последователей. Промахи при чтении (неудовлетворенные размещенными в одном месте узлами могут переходить на уровни последователей), а записи всегда переходят на уровень лидера в регионе. Обращения при чтении будут обрабатываться уровнем подписчиков, на котором был получен запрос от клиента, или другим уровнем подписчиков. Таким образом, горячие точки могут быть уменьшены за счет согласованного хеширования, что упрощает добавление уровней без существенной перебалансировки кешей. Кроме того, подписчики могут полностью передать нагрузку чтения популярных объектов клиенту, а клиенты могут кэшировать их на более длительный срок.

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

В этой архитектуре есть несколько уровней подчиненных, работающих независимо друг от друга. Уровень 1 может обновлять значение, а уровень 2 не может узнать о новом значении. Следовательно, уровни подписчиков должны быть осведомлены об изменениях, произошедших через другие уровни подписчиков. Это достигается с помощью сообщения обслуживания кеша, которое лидер асинхронно отправляет последователям. Это означает, что последователи будут согласованы только по чтению после записи.

Масштабирование и география

В то время как в последнем разделе рассматривается масштабирование данного центра обработки данных, у facebook есть миллиарды пользователей, разбросанных по разным континентам и географическим регионам. Если есть запрос, который может поступить для популярного осколка из Азии, но осколок обслуживается подписчиком, размещенным в центре обработки данных в США, то задержка чтения для таких объектов будет значительной. Чтобы решить эту проблему, шард может быть размещен в подчиненном регионе в Азии, у которого есть реплика БД, последователей и лидеров.

На высоком уровне подчиненный регион выполняет следующие задачи:

Подчиненные последователи могут продолжать обслуживать обращения к чтению из своих собственных кешей.
Ведомые ведомые должны перейти к ведомому лидеру в случае промахов чтения, которые будут отправлены в базу данных реплик для получения значения.
Записи идут к подчиненному лидеру, затем к главному лидеру, а затем к главной БД синхронно. Главная БД реплицируется на подчиненную БД.
Ссылка репликации запускает обновления ведомого лидера, который, в свою очередь, запускает сообщения об аннулировании этого ведомого ведомого ведомого.

Обработка отказов

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

Сбои сети:

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

Сбои базы данных:

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

Неудачи лидера:

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

Ошибки подписчика:

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

Заключение

Я наткнулся на много литературы о хранилищах ключей и значений различных типов, таких как Cassandra, BigTable, C-store и т. Д., Но я не особо подробно разбирался в проблемах и необходимости графических баз данных. Эта статья очень хорошо резюмирует это. Кроме того, масштабирование на основе географии кажется хорошим подходом для действительно распределенной базы данных. В целом, я слышал гораздо больше шума в индустрии о Kafka для pub-sub, Cassandra, чем о графических базах данных, таких как Neo4j или TAO. Учитывая, насколько персонализированным становится Интернет, мне это кажется нелогичным.

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

TAO - Распределенная база данных Facebook для Social Graph