Переписать базу сообщений ВКонтакте с нуля и выжить17.11.2017 15:03

Наши пользователи пишут друг другу сообщения, не зная усталости.

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

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

Для нас этот момент наступил полтора года назад. Как мы к этому пришли и что получилось в итоге — рассказываем по порядку.

История вопроса

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

В конце 2009 года было написано первое хранилище text-engine, а в 2010 на него перевели сообщения.

В text-engine сообщения хранились списками — своего рода «почтовыми ящиками». Каждый такой список определяется uid«ом — пользователем-владельцем всех этих сообщений. У сообщения есть набор атрибутов: идентификатор собеседника, текст, вложения и так далее. Идентификатор сообщения внутри «ящика» — local_id, он никогда не изменяется и назначается последовательно для новых сообщений. «Ящики» независимы и друг с другом внутри движка никак не синхронизируются, связь между ними происходит уже на уровне PHP. Посмотреть на структуру данных и возможности text-engine изнутри можно здесь.

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

В мае 2011 года ВКонтакте появились беседы с несколькими участниками — мультичаты. Для работы с ними мы подняли два новых кластера — member-chats и chat-members. Первый хранит данные о чатах по пользователям, второй — данные о пользователях по чатам. Кроме самих списков это, например, пригласивший пользователь и время добавления в чат.

— PHP, давай отправим сообщение в чат, — говорит пользователь.
— Ну давай, {username}, — говорит PHP.

В этой схеме есть минусы. Синхронизация по-прежнему возложена на PHP. Большие чаты и пользователи, которые одновременно отправляют сообщения в них — опасная история. Поскольку экземпляр text-engine зависит от uid, участники чата могли получать одно и то же сообщение с разницей во времени. С этим можно было жить, если бы прогресс стоял на месте. Но не бывать такому.

В конце 2015 года мы запустили сообщения сообществ, а в начале 2016 — API для них. С появлением крупных чат-ботов в сообществах о равномерности распределения нагрузки можно было забыть.

Годный бот генерирует несколько миллионов сообщений в сутки — даже самые словоохотливые пользователи таким похвастаться не могут. А это значит, что некоторым экземплярам text-engine, на которых жили такие вот боты, стало доставаться по полной.

Движки сообщений в 2016 году — это по 100 экземпляров chat-members и member-chats, и 8000 text-engine. Они размещались на тысяче серверов, каждый с 64 Гб памяти. В качестве первой экстренной меры мы увеличили память ещё на 32 Гб. Прикинули прогнозы. Без кардинальных изменений этого хватило бы ещё примерно на год. Нужно либо разживаться железом, либо оптимизировать сами БД.

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

Новая концепция

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

Необходимый минимум — это две новые базы данных:

chat-engine. Это хранилище векторов чатов. У каждого чата есть вектор сообщений, которые к нему относятся. У каждого сообщения есть текст и уникальный идентификатор сообщения внутри чата — chat_local_id.
user-engine. Это хранилище векторов users — ссылок на пользователей. У каждого пользователя есть вектор peer_id (собеседников — других пользователей, мультичатов или сообществ) и вектор сообщений. У каждого peer_id есть вектор сообщений, которые к нему относятся. У каждого сообщения есть chat_local_id и уникальный идентификатор сообщения для этого пользователя — user_local_id.

Новые кластеры общаются между собой с помощью TCP — это гарантирует, что порядок запросов не изменится. Сами запросы и подтверждения для них записываются на жёсткий диск — поэтому мы можем восстановить состояние очереди в любой момент времени после сбоя или перезапуска движка. Поскольку user-engine и chat-engine это 4 тысячи шардов каждый, очередь запросов между кластерами будет распределяться равномерно (а в реальности её нет вообще — и это работает очень быстро).

Работа с диском в наших базах в большинстве случаев основана на сочетании бинарного лога изменений (бинлога), статических снимков и частичного образа в памяти. Изменения в течение дня пишутся в бинлог, периодически создаётся снимок текущего состояния. Снимок представляет собой набор структур данных, оптимизированных для наших целей. Он состоит из заголовка (метаиндекса снимка) и набора метафайлов. Заголовок постоянно хранится в оперативной памяти и указывает, где искать данные из снимка. Каждый метафайл включает данные, которые с большой вероятностью потребуются в близкие моменты времени — например, относятся к одному пользователю. При запросе к базе с помощью заголовка снимка читается нужный метафайл, а затем учитываются изменения в бинлоге, произошедшие уже после создания снимка. Прочитать подробнее о преимуществах такого подхода можно здесь.

При этом данные на самом жёстком диске изменяются только раз в сутки — глубокой ночью по Москве, когда нагрузка минимальна. Благодаря этому (зная, что структура на диске в течение суток постоянная) мы можем позволить себе заменить векторы на массивы фиксированного размера — и за счёт этого выиграть в памяти.

Отправка сообщения в новой схеме выглядит так:

PHP backend обращается к user-engine с запросом на отправку сообщения.
user-engine проксирует запрос в нужный экземпляр chat-engine, который возвращает в user-engine chat_local_id — уникальный идентификатор нового сообщения внутри этого чата. Затем chat_engine рассылает сообщение всем получателям в чате.
user-engine принимает от chat-engine chat_local_id и возвращает в PHP user_local_id — уникальный идентификатор сообщения для этого пользователя. Этот идентификатор затем используется, например, для работы с сообщениями через API.

Но помимо собственно рассылки сообщений нужно реализовать ещё несколько важных вещей:

Подсписки — это например, самые свежие сообщения, которые Вы видите, открывая список диалогов. Непрочитанные сообщения, сообщения с метками («Важные», «Спам» и т.д.).
Сжатие сообщений в chat-engine
Кэширование сообщений в user-engine
Поиск (по всем диалогам и внутри конкретного).
Обновление в реальном времени (Longpolling).
Сохранение истории для реализации кэширования на мобильных клиентах.

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

Сообщения подразумевают большой объём информации, в основном текстовой, которую полезно уметь сжимать. При этом важно, чтобы мы могли точно разархивировать даже одно отдельное сообщение. Для сжатия сообщений используется алгоритм Хаффмана с собственными эвристиками — например, мы знаем, что в сообщениях слова чередуются с «не словами» — пробелами, знаками пунктуации, —, а также помним о некоторых особенностях использования символов для русского языка.

Поскольку пользователей гораздо меньше, чем чатов, для экономии random-access запросов к диску в chat-engine мы кэшируем сообщения в user-engine.

Поиск по сообщениям реализован как диагональный запрос из user-engine ко всем экземплярам chat-engine, которые содержат чаты этого пользователя. Результаты объединяются уже в самом user-engine.

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

Миграция данных

Итак, у нас есть text-engine, который хранит сообщения по пользователям, и два кластера chat-members и member-chats, которые хранят данные о мультичатах и пользователях в них. Как от этого перейти к новым user-engine и chat-engine?

member-chats в старой схеме использовался преимущественно для оптимизации. Мы довольно быстро перенесли нужные данные из него в chat-members, и далее в процесе миграции он уже не участвовал.

Очередь за chat-members. Он включает 100 экземпляров, в то время как chat-engine — 4 тысячи. Для переливки данных нужно привести их в соответствие — для этого chat-members разбили на те же 4 тысячи экземпляров, а после включили чтение бинлога chat-members в chat-engine.

Теперь chat-engine знает о мультичатах из chat-members, но ему пока ничего не известно о диалогах с двумя собеседниками. Такие диалоги лежат в text-engine с привязкой к пользователям. Здесь мы забирали данные «в лоб»: каждый экземпляр chat-engine запрашивал у всех экземпляров text-engine, есть ли у них нужный ему диалог.

Отлично — chat-engine знает, какие есть мультичаты, и знает, какие есть диалоги.
Нужно объединить сообщения в мультичатах — так, чтобы в итоге для каждого чата получить список сообщений в нём. Сначала chat-engine забирает из text-engine все сообщения пользователей из этого чата. В некоторых случаях их довольно много (до сотни миллионов), но за очень редким исключением чат полностью помещается в оперативную память. Мы имеем неупорядоченные сообщения, каждое в нескольких копиях — ведь вытаскиваются они все из разных экземпляров text-engine, соответствующих пользователям. Задача в том, чтобы отсортировать сообщения и избавиться от копий, которые занимают лишнее место.

У каждого сообщения есть timestamp, содержащий время отправки, и текст. Используем время для сортировки — помещаем указатели на самые старые сообщения участников мультичата и сравниваем хэши от текста предполагаемых копий, двигаясь в сторону увеличения timestamp. Логично, что у копий будут совпадать и хэш, и timestamp, но на практике это не всегда так. Как Вы помните, синхронизация в старой схеме осуществлялась силами PHP — и в редких случаях время отправки одного и того же сообщения отличалось у разных пользователей. В этих случаях мы позволяли себе редактировать timestamp — обычно, в пределах секунды. Вторая проблема — разный порядок сообщений для разных получателей. В таких случаях мы допускали создание лишней копии, с разными вариантами порядка для разных пользователей.

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

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

Она представляет собой вектор размера $n=2^{a_0} + 2^{a_1} + ... + 2^{a_k}n=2^{a_0} + 2^{a_1} + ... + 2^{a_k}$ , где все $a_i$ — различны и упорядочены по убыванию, с особым порядком элементов. В каждом отрезке с индексами $[0,2^{a_0}), [2^{a_0}, 2^{a_0} + 2^{a_1}),[2^{a_0} + 2^{a_1}, 2^{a_0} + 2^{a_1}+2^{a_2}),...$ элементы отсортированы. Поиск элемента в такой структуре выполняется за время $O(log^2n)$ через $log\:{n}$ бинарных поисков. Добавление элемента выполняется амортизированно за .

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

Запись данных идёт в chat-members и user-engine (а не в text-engine, как при нормальной работе по старой схеме). user-engine проксирует запрос к chat-engine — и здесь поведение зависит от того, смержен уже этот чат или еще нет. Если чат еще не смержен, chat-engine не записывает сообщение к себе, и его обработка происходит только в text-engine. Если чат уже смержен в chat-engine, он возвращает в user-engine chat_local_id и рассылает сообщение всем получателям. user-engine проксирует все данные в text-engine — чтобы в случае чего мы всегда могли откатиться назад, имея все актуальные данные в старом движке. text-engine возвращает user_local_id, который user-engine сохраняет у себя и возвращает в бэкенд.

В итоге процесс перехода выглядит так: подключаем пустые кластеры user-engine и chat-engine. chat-engine читает весь бинлог chat-members, затем запускается проксирование по схеме, описанной выше. Переливаем старые данные, получаем два синхронизированных кластера (старый и новый). Остается только переключить чтение с text-engine на user-engine и отключить проксирование.

Результаты

Благодаря новому подходу улучшились все метрики качества работы движков, решены проблемы с консистентностью данных. Теперь мы можем быстрее внедрять новые фичи в сообщениях (и уже начали это делать — увеличили максимальное число участников чата, реализовали поиск по пересланным сообщениям, запустили закреплённые сообщения и подняли лимит на общее число сообщений у одного пользователя).

Изменения в логике действительно грандиозные. И хочется отметить, что это не всегда означает целые годы разработки огромной командой и мириады строк кода. chat-engine и user-engine вместе со всеми дополнительными историями вроде Хаффмана для сжатия сообщений, Splay-деревьев и структуры для импортированных сообщений — это менее 20 тысяч строк кода. И написали их 3 разработчика всего за 10 месяцев (впрочем, стоит иметь в виду, что все три разработчика — чемпионы мира по спортивному программированию).

Более того, вместо удвоения числа серверов мы пришли к уменьшению их числа наполовину — сейчас user-engine и chat-engine живут на 500 физических машинах, при этом у новой схемы есть большой запас по нагрузке. Мы сэкономили кучу денег на оборудовании — это около $5 млн + $750 тысяч в год за счёт операционных расходов.

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

Даже если эта история не про Вас, обратите внимание, что мы ценим рекомендации. Расскажите другу о любой нашей вакансии, и, если он успешно пройдёт испытательный срок, Вы получите бонус в размере 100 тысяч рублей.