Переписати базу повідомлень ВКонтакте з нуля та вижити

Наші користувачі пишуть одне одному повідомлення, не знаючи втоми.

Це дуже багато. Якби Ви мали на меті прочитати всі повідомлення всіх користувачів, це зайняло б понад 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 тисячі шардів кожен, черга запитів між кластерами буде розподілятися рівномірно (а насправді її немає взагалі — і це працює дуже швидко).

Робота з диском у наших базах у більшості випадків заснована на поєднанні бінарного лога змін (бінлогу), статичних знімків та часткового образу пам'яті. Зміни протягом дня пишуться до бінлогу, періодично створюється знімок поточного стану. Знімок є набором структур даних, оптимізованих для наших цілей. Він складається з заголовка (метаіндекс знімка) і набору метафайлів. Заголовок постійно зберігається в оперативній пам'яті та вказує, де шукати дані зі знімка. Кожен метафайл включає дані, які з великою ймовірністю будуть потрібні в найближчі моменти часу - наприклад, відносяться до одного користувача. При запиті до бази за допомогою заголовка знімка читається потрібний метафайл, а потім враховуються зміни в бінлозі, що відбулися після створення знімка. Докладніше про переваги такого підходу можна прочитати тут.

При цьому дані на жорсткому диску змінюються тільки раз на добу — глибокої ночі по Москві, коли навантаження мінімальне. Завдяки цьому (знаючи, що структура на диску протягом доби стала) ми можемо дозволити собі замінити вектори на масиви фіксованого розміру — і за рахунок цього виграти в пам'яті.

Надсилання повідомлення у новій схемі виглядає так:

1. PHP backend звертається до user-engine із запитом на відправлення повідомлення.
2. user-engine проксує запит до потрібного примірника chat-engine, який повертає до user-engine chat_local_id — унікальний ідентифікатор нового повідомлення всередині цього чату. Потім chat_engine надсилає повідомлення всім одержувачам у чаті.
3. 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 повідомлення втрачали цю корисну властивість. При цьому для зручності тестування потрібно вміти швидко до них звертатися, щось шукати в них і додавати нові.

Для зберігання імпортованих повідомлень ми використовуємо особливу структуру даних.

Вона являє собою вектор розміру , де всі - Різні і впорядковані за спаданням, з особливим порядком елементів. У кожному відрізку з індексами елементи відсортовані. Пошук елемента у такій структурі виконується за час через бінарних пошуків. Додавання елемента виконується амортизовано за .

Отже, ми розібралися з тим, як переливати дані зі старих двигунів в нові. Але цей процес займає кілька днів — і навряд чи цими днями наші користувачі кинуть звичку писати один одному. Щоб не втратити повідомлення за цей час, ми перемикаємось на схему роботи, яка задіяна і старими, і новими кластерами.

Запис даних йде у 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 тисяч рублів.

Джерело: habr.com