- Огромный массив данных сообщений ВКонтакте
- История вопроса
- Новая концепция сообщений ВКонтакте
- Миграция данных сообщений ВКонтакте
- Результаты нового алгоритма работы сообщений ВКонтакте
Огромный массив данных сообщений ВКонтакте
Пользователи ВКонтакте пишут друг другу сообщения, не зная усталости. Это довольно много. Если бы Вы задались целью прочитать все сообщения всех пользователей, это бы заняло больше 150 тысяч лет. При условии, что Вы довольно прокачанный чтец и тратите на каждое сообщение не больше секунды. При таком объёме данных критически важно, чтобы логика хранения и доступа к ним была построена оптимально. Иначе в один не такой уж и прекрасный момент может выясниться, что скоро всё пойдёт не так.
История вопроса
В самой первой реализации сообщения ВКонтакте работали на связке PHP-бэкенда и MySQL. Это вполне нормальное решение для небольшого студенческого сайта. Однако этот сайт безудержно рос и начал требовать оптимизировать структуры данных под себя. В конце 2009 года было написано первое хранилище text-engine, а в 2010 на него перевели сообщения.
В text-engine сообщения хранились списками — своего рода «почтовыми ящиками». Каждый такой список определяется uid’ом — пользователем-владельцем всех этих сообщений. У сообщения есть набор атрибутов: идентификатор собеседника, текст, вложения и так далее. Идентификатор сообщения внутри «ящика» — local_id, он никогда не изменяется и назначается последовательно для новых сообщений. «Ящики» независимы и друг с другом внутри движка никак не синхронизируются, связь между ними происходит уже на уровне PHP.
Этого было вполне достаточно для переписки двух пользователей. Угадайте, что случилось потом?
В мае 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 рассылает сообщение всем получателям в чате.
Но помимо собственно рассылки сообщений нужно реализовать ещё несколько важных вещей:
- Подсписки — это например, самые свежие сообщения, которые Вы видите, открывая список диалогов. Непрочитанные сообщения, сообщения с метками («Важные», «Спам» и т.д.).
- Сжатие сообщений в 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, где n — сумма степеней двойки. Степени различны и упорядочены по убыванию. В каждом отрезке с индексами от одной степени двойки до следующей элементы отсортированы. Поиск элемента в такой структуре выполняется за время O(log²n) через log n бинарных поисков. Добавление элемента выполняется амортизированно за O(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 тысяч рублей.
По материалам:
https://vk.com/blog/messages-database
Автор: Дмитрий Егоров — директор по высоконагруженным системам и оптимизации
Заберите ссылку на статью к себе, чтобы потом легко её найти!
Раз уж досюда дочитали, то может может есть желание рассказать об этом месте своим друзьям, знакомым и просто мимо проходящим?
Не надо себя сдерживать! ;)
