Нашите потребители пишат съобщения един на друг, без да знаят умората.
Това е доста. Ако решите да прочетете всички съобщения на всички потребители, това ще отнеме повече от 150 хиляди години. При условие, че сте доста напреднал читател и отделяте не повече от секунда за всяко съобщение.
При такъв обем от данни е изключително важно логиката за съхранение и достъп до тях да е изградена оптимално. В противен случай в един не толкова прекрасен момент може да стане ясно, че скоро всичко ще се обърка.
За нас този момент дойде преди година и половина. Как се стигна до това и какво се случи в крайна сметка - разказваме ви по ред.
история на заболяването
В първата реализация съобщенията на VKontakte работеха върху комбинация от PHP бекенд и MySQL. Това е напълно нормално решение за малък студентски сайт. Този сайт обаче се разрасна неконтролируемо и започна да изисква оптимизиране на структурите от данни за себе си.
В края на 2009 г. беше написано първото текстово хранилище, а през 2010 г. съобщенията бяха прехвърлени към него.
В текстовата машина съобщенията се съхраняват в списъци - един вид „пощенски кутии“. Всеки такъв списък се определя от uid - потребителят, който притежава всички тези съобщения. Съобщението има набор от атрибути: идентификатор на събеседника, текст, прикачени файлове и т.н. Идентификаторът на съобщението в кутията е local_id, той никога не се променя и се присвоява последователно за нови съобщения. „Кутиите“ са независими и не са синхронизирани помежду си вътре в двигателя; комуникацията между тях се осъществява на ниво PHP. Можете да разгледате структурата на данните и възможностите на текстовата машина отвътре .
Това беше напълно достатъчно за кореспонденция между двама потребители. Познайте какво се случи след това?
През май 2011 г. VKontakte въведе разговори с няколко участници - мулти-чат. За да работим с тях, създадохме два нови клъстера - членове-чатове и чат-членове. Първият съхранява данни за чатове по потребители, вторият съхранява данни за потребители по чатове. В допълнение към самите списъци, това включва, например, канещия потребител и времето, когато е добавен към чата.
„PHP, нека изпратим съобщение до чата“, казва потребителят.
„Хайде, {username}“, казва PHP.
Тази схема има недостатъци. Синхронизирането все още е отговорност на PHP. Големите чатове и потребителите, които едновременно изпращат съобщения до тях, са опасна история. Тъй като екземплярът на текстовата машина зависи от uid, участниците в чата могат да получат едно и също съобщение по различно време. Човек би могъл да живее с това, ако прогресът беше спрял. Но това няма да стане.
В края на 2015 г. пуснахме общностни съобщения, а в началото на 2016 г. стартирахме API за тях. С появата на големи чатботове в общностите беше възможно да се забрави за равномерното разпределение на натоварването.
Добрият бот генерира няколко милиона съобщения на ден - дори и най-приказливите потребители не могат да се похвалят с това. Това означава, че някои екземпляри на текстова машина, на която живееха такива ботове, започнаха да страдат най-пълно.
Машините за съобщения през 2016 г. са 100 екземпляра на чат-членове и членове-чатове и 8000 текстови машини. Те бяха хоствани на хиляда сървъра, всеки с 64 GB памет. Като първа спешна мярка увеличихме паметта с още 32 GB. Преценихме прогнозите. Без драстични промени това би било достатъчно за още около година. Трябва или да се сдобиете с хардуер, или да оптимизирате самите бази данни.
Поради естеството на архитектурата, има смисъл само хардуерът да се увеличава многократно. Тоест, поне удвояване на броя на колите - очевидно това е доста скъп път. Ще оптимизираме.
Нова концепция
Централната същност на новия подход е чатът. Чатът има списък със съобщения, които се отнасят до него. Потребителят има списък с чатове.
Необходимият минимум са две нови бази данни:
- чат двигател. Това е хранилище на чат вектори. Всеки чат има вектор от съобщения, които се отнасят до него. Всяко съобщение има текст и уникален идентификатор на съобщение в чата - chat_local_id.
- потребителски двигател. Това е хранилище на потребителски вектори - връзки към потребители. Всеки потребител има вектор от peer_id (събеседници - други потребители, мулти-чат или общности) и вектор от съобщения. Всеки peer_id има вектор от съобщения, които се отнасят до него. Всяко съобщение има chat_local_id и уникален идентификатор на съобщението за този потребител - user_local_id.
Новите клъстери комуникират помежду си чрез TCP - това гарантира, че редът на заявките не се променя. Самите заявки и потвържденията за тях се записват на твърдия диск - така че можем да възстановим състоянието на опашката по всяко време след повреда или рестартиране на двигателя. Тъй като потребителската машина и чат машината са по 4 хиляди фрагмента, опашката на заявките между клъстерите ще бъде разпределена равномерно (но в действителност изобщо няма - и работи много бързо).
Работата с диск в нашите бази данни в повечето случаи се основава на комбинация от двоичен регистър на промените (binlog), статични моментни снимки и частично изображение в паметта. Промените през деня се записват в binlog и периодично се създава моментна снимка на текущото състояние. Моментната снимка е съвкупност от структури от данни, оптимизирани за нашите цели. Състои се от заглавка (метаиндекс на изображението) и набор от метафайлове. Заглавката се съхранява постоянно в RAM и показва къде да търсите данни от моментната снимка. Всеки метафайл включва данни, които е вероятно да са необходими в близки моменти във времето - например свързани с един потребител. Когато правите заявка към базата данни, като използвате заглавката на моментната снимка, необходимият метафайл се чете и след това промените в binlog, настъпили след създаването на моментната снимка, се вземат предвид. Можете да прочетете повече за предимствата на този подход .
В същото време данните на самия твърд диск се променят само веднъж на ден - късно през нощта в Москва, когато натоварването е минимално. Благодарение на това (като знаем, че структурата на диска е постоянна през целия ден), можем да си позволим да заменим векторите с масиви с фиксиран размер - и поради това да спечелим памет.
Изпращането на съобщение в новата схема изглежда така:
- Бекендът на PHP се свързва с потребителската машина със заявка за изпращане на съобщение.
- user-engine проксира заявката до желания екземпляр на chat-engine, който се връща към chat_local_id на user-engine - уникален идентификатор на ново съобщение в този чат. След това chat_engine излъчва съобщението до всички получатели в чата.
- user-engine получава chat_local_id от chat-engine и връща user_local_id на PHP - уникален идентификатор на съобщение за този потребител. След това този идентификатор се използва, например, за работа със съобщения чрез API.
Но в допълнение към действителното изпращане на съобщения, трябва да внедрите още няколко важни неща:
- Подсписъците са например най-новите съобщения, които виждате, когато отваряте списъка с разговори. Непрочетени съобщения, съобщения с тагове („Важно“, „Спам“ и др.).
- Компресиране на съобщения в чат машина
- Кеширане на съобщения в потребителската машина
- Търсене (през всички диалогови прозорци и в конкретен).
- Актуализация в реално време (Longpolling).
- Запазване на историята за прилагане на кеширане на мобилни клиенти.
Всички подсписъци са с бързо променящи се структури. За работа с тях използваме . Този избор се обяснява с факта, че в горната част на дървото понякога съхраняваме цял сегмент от съобщения от моментна снимка - например след нощно преиндексиране дървото се състои от един връх, който съдържа всички съобщения от подсписъка. Splay дървото улеснява вмъкването в средата на такъв връх, без да се налага да мислите за балансиране. Освен това Splay не съхранява ненужни данни, което ни спестява памет.
Съобщенията включват голямо количество информация, предимно текст, което е полезно да можете да компресирате. Важно е да можем точно да разархивираме дори едно отделно съобщение. Използва се за компресиране на съобщения с нашите собствени евристики - например знаем, че в съобщенията думите се редуват с „не-думи“ - интервали, препинателни знаци - и също така помним някои от особеностите на използването на символи за руския език.
Тъй като има много по-малко потребители от чатовете, за да запазим дискови заявки с произволен достъп в чат машината, ние кешираме съобщения в потребителската машина.
Търсенето на съобщения е реализирано като диагонална заявка от потребителска машина към всички екземпляри на чат машина, които съдържат чатове на този потребител. Резултатите се комбинират в самата потребителска машина.
Е, всички подробности са взети под внимание, остава само да преминете към нова схема - и за предпочитане без потребителите да го забележат.
Миграция на данни
И така, имаме текстова машина, която съхранява съобщения по потребители, и два клъстера chat-members и members-chats, които съхраняват данни за мулти-чат стаи и потребителите в тях. Как да преминете от този към новия потребителски двигател и чат двигател?
member-chats в старата схема се използваше основно за оптимизация. Бързо прехвърлихме необходимите данни от него към членовете на чат и след това той вече не участва в процеса на миграция.
Опашка за чат-членове. Той включва 100 екземпляра, докато chat-engine има 4 хиляди. За да прехвърлите данните, трябва да ги приведете в съответствие - за това членовете на чат бяха разделени на същите 4 хиляди копия и след това четенето на binlog на членовете на чат беше активирано в чат двигателя.
Сега чат-машината знае за мулти-чат от чат-членове, но все още не знае нищо за диалозите с двама събеседници. Такива диалози се намират в текстовата машина по отношение на потребителите. Тук взехме данните „директно“: всеки екземпляр на чат машина попита всички екземпляри на текстова машина дали имат необходимия диалог.
Страхотно – машината за чат знае какви чатове с множество чатове има и знае какви диалози има.
Трябва да комбинирате съобщения в чатове с множество разговори, така че да получите списък със съобщения във всеки чат. Първо, чат машината извлича от текстовата машина всички потребителски съобщения от този чат. В някои случаи има доста от тях (до стотици милиони), но с много редки изключения чатът се побира изцяло в RAM. Имаме неподредени съобщения, всяко в няколко копия - в края на краищата всички те са изтеглени от различни инстанции на текстова машина, съответстващи на потребителите. Целта е да сортирате съобщенията и да се отървете от копията, които заемат ненужно място.
Всяко съобщение има времево клеймо, съдържащо часа на изпращане и текст. Използваме време за сортиране - поставяме указатели към най-старите съобщения на участниците в мултичат и сравняваме хешовете от текста на предвидените копия, като се движим към увеличаване на времевия печат. Логично е копията да имат еднакъв хеш и времева марка, но на практика това не винаги е така. Както си спомняте, синхронизацията в старата схема се извършваше от PHP - и в редки случаи времето за изпращане на едно и също съобщение се различаваше при различните потребители. В тези случаи си позволихме да редактираме клеймото за време - обикновено в рамките на секунда. Вторият проблем е различният ред на съобщенията за различните получатели. В такива случаи позволявахме да се създаде допълнително копие с различни опции за поръчка за различните потребители.
След това данните за съобщенията в мултичат се изпращат до потребителската машина. И тук идва една неприятна характеристика на импортираните съобщения. При нормална работа съобщенията, които идват до двигателя, се подреждат строго във възходящ ред по user_local_id. Съобщенията, импортирани от старата машина в потребителската машина, загубиха това полезно свойство. В същото време, за удобство на тестването, трябва да имате бърз достъп до тях, да търсите нещо в тях и да добавяте нови.
Използваме специална структура от данни за съхраняване на импортираните съобщения.
Той представлява вектор на размера къде са всички - са различни и подредени в низходящ ред, със специален ред на елементите. Във всеки сегмент с индекси елементите са сортирани. Търсенето на елемент в такава структура отнема време през двоични търсения. Добавянето на елемент се амортизира .
И така, разбрахме как да прехвърляме данни от стари двигатели към нови. Но този процес отнема няколко дни - и е малко вероятно през тези дни нашите потребители да се откажат от навика да си пишат. За да не губим съобщения през това време, преминаваме към работна схема, която използва както стари, така и нови клъстери.
Данните се записват в chat-members и user-engine (а не в text-engine, както при нормална работа по старата схема). user-engine проксира заявката към chat-engine - и тук поведението зависи от това дали този чат вече е обединен или не. Ако чатът все още не е обединен, чат машината не пише съобщението на себе си и обработката му се извършва само в текстовата машина. Ако чатът вече е обединен в чат машината, тя връща chat_local_id на потребителската машина и изпраща съобщението до всички получатели. user-engine проксира всички данни към text-engine - така че ако нещо се случи, винаги можем да се върнем назад, разполагайки с всички текущи данни в старата машина. text-engine връща user_local_id, който user-engine съхранява и връща към бекенда.
В резултат на това процесът на преход изглежда така: свързваме празни потребителски и чат клъстери. chat-engine чете целия binlog на chat-members, след което проксиирането започва съгласно описаната по-горе схема. Прехвърляме старите данни и получаваме два синхронизирани клъстера (стар и нов). Всичко, което остава, е да превключите четенето от текстова машина към потребителска машина и да деактивирате прокси.
резултати
Благодарение на новия подход, всички показатели за ефективност на двигателите са подобрени и проблемите с последователността на данните са решени. Сега можем бързо да внедрим нови функции в съобщенията (и вече започнахме да правим това - увеличихме максималния брой участници в чата, въведохме търсене на препратени съобщения, стартирахме фиксирани съобщения и повишихме ограничението за общия брой съобщения на потребител) .
Промените в логиката са наистина огромни. И бих искал да отбележа, че това не винаги означава цели години разработка от огромен екип и безброй редове код. chat-engine и user-engine заедно с всички допълнителни истории като Huffman за компресиране на съобщения, Splay дървета и структура за импортирани съобщения е по-малко от 20 хиляди реда код. И те са написани от 3 разработчици само за 10 месеца (все пак си струва да се има предвид, че - световни шампиони ).
Освен това, вместо да удвоим броя на сървърите, ние намалихме техния брой наполовина - сега потребителският двигател и чат двигателът живеят на 500 физически машини, докато новата схема има голямо пространство за натоварване. Спестихме много пари от оборудване - около $5 милиона + $750 хиляди годишно оперативни разходи.
Стремим се да намираме най-добрите решения за най-сложните и мащабни проблеми. Имаме много от тях - и затова търсим талантливи разработчици в отдела за бази данни. Ако обичате и знаете как да решавате подобни проблеми, имате отлични познания по алгоритми и структури от данни, ви каним да се присъедините към екипа. Свържете се с нашите за детайли.
Дори тази история да не е за вас, моля, имайте предвид, че ценим препоръките. Кажете на приятел за , и ако той успешно завърши изпитателния период, ще получите бонус от 100 хиляди рубли.
Източник: www.habr.com