Препишете ја базата на податоци за пораки VKontakte од нула и преживејте

Нашите корисници си пишуваат пораки едни на други без да знаат замор.

Тоа е доста. Ако тргнете да ги читате сите пораки на сите корисници, ќе бидат потребни повеќе од 150 илјади години. Под услов да сте прилично напреден читател и да потрошите не повеќе од една секунда на секоја порака.

Со таков обем на податоци, од клучно значење е логиката за складирање и пристап до нив да биде оптимално изградена. Во спротивно, во еден не толку прекрасен момент, може да стане јасно дека наскоро сè ќе тргне наопаку.

За нас овој момент дојде пред година и пол. Како дојдовме до ова и што се случи на крајот - ви кажуваме по ред.

Позадина

Во првата имплементација, пораките на VKontakte работеа на комбинација од PHP backend и 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 и единствен ID на порака за тој корисник - user_local_id.

Новите кластери комуницираат едни со други користејќи TCP - ова осигурува дека редоследот на барањата не се менува. Самите барања и потврдите за нив се запишуваат на хард дискот - за да можеме да ја вратиме состојбата на редот во секое време по дефект или рестартирање на моторот. Бидејќи корисничкиот мотор и моторот за разговор се по 4 илјади фрагменти, редот за барање меѓу кластерите ќе се распредели рамномерно (но во реалноста нема воопшто - и работи многу брзо).

Работата со диск во нашите бази на податоци во повеќето случаи се заснова на комбинација од бинарен дневник на промени (binlog), статични снимки и делумна слика во меморијата. Промените во текот на денот се запишуваат во бинлог и периодично се креира снимка од моменталната состојба. Снимката е збирка структури на податоци оптимизирани за наши цели. Се состои од заглавие (метаиндекс на сликата) и збир на метадатотеки. Заглавието е трајно зачувано во RAM меморијата и покажува каде да барате податоци од снимката. Секоја мета-датотека вклучува податоци кои веројатно ќе бидат потребни во блиски моменти во времето - на пример, поврзани со еден корисник. Кога ја барате базата на податоци користејќи го заглавието на снимката, потребната мета-датотека се чита, а потоа се земаат предвид промените во бинлогот што настанале по креирањето на сликата. Можете да прочитате повеќе за придобивките од овој пристап тука.

Во исто време, податоците на самиот хард диск се менуваат само еднаш дневно - доцна навечер во Москва, кога оптоварувањето е минимално. Благодарение на ова (знаејќи дека структурата на дискот е константна во текот на денот), можеме да си дозволиме да ги замениме векторите со низи со фиксна големина - и поради тоа, зголемување на меморијата.

Испраќањето порака во новата шема изгледа вака:

1. Заднината на PHP контактира со корисничкиот мотор со барање да испрати порака.
2. user-engine го посредува барањето до саканиот примерок на chat-engine, кој се враќа на user-engine chat_local_id - единствен идентификатор на нова порака во овој разговор. chat_engine потоа ја емитува пораката до сите примачи во разговорот.
3. user-engine добива chat_local_id од chat-engine и го враќа user_local_id во PHP - единствен идентификатор на порака за овој корисник. Овој идентификатор потоа се користи, на пример, за работа со пораки преку API.

Но, покрај тоа што всушност испраќате пораки, треба да имплементирате уште неколку важни работи:

• Подлистите се, на пример, најновите пораки што ги гледате при отворање на списокот со разговори. Непрочитани пораки, пораки со ознаки („Важно“, „Спам“ итн.).
• Компресирање пораки во chat-мотор
• Кеширање пораки во корисничкиот мотор
• Пребарување (низ сите дијалози и во рамките на одреден).
• Ажурирање во реално време (Longpolling).
• Зачувување на историјата за спроведување на кеширање на мобилни клиенти.

Сите подлисти се структури кои брзо се менуваат. За работа со нив користиме Прскајте дрвја. Овој избор се објаснува со фактот дека на врвот на дрвото понекогаш складираме цел сегмент од пораки од снимка - на пример, по ноќното реиндексирање, дрвото се состои од еден врв, кој ги содржи сите пораки од подлистата. Дрвото Splay го олеснува вметнувањето во средината на такво теме без да размислувате за балансирање. Покрај тоа, Splay не складира непотребни податоци, што ни заштедува меморија.

Пораките вклучуваат голема количина на информации, главно текст, што е корисно за да може да се компресира. Важно е да можеме точно да деархивираме дури и една индивидуална порака. Се користи за компресија на пораки Хафман алгоритам со нашата сопствена хеуристика - на пример, знаеме дека во пораките зборовите се менуваат со „не-зборови“ - празни места, интерпункциски знаци - и, исто така, се сеќаваме на некои од особеностите на користење симболи за рускиот јазик.

Бидејќи има многу помалку корисници од разговорите, за да ги зачуваме барањата за диск со случаен пристап во chat-моторот, ги кешираме пораките во корисничкиот мотор.

Пребарувањето пораки се имплементира како дијагонално барање од кориснички мотор до сите примероци на мотор за разговор што содржат разговори на овој корисник. Резултатите се комбинирани во самиот кориснички мотор.

Па, сите детали се земени предвид, останува само да се префрлиме на нова шема - и по можност без корисниците да го забележат тоа.

Миграција на податоци

Значи, имаме текстуален мотор кој складира пораки по корисник, и два кластери членови за разговор и членови-четови кои складираат податоци за собите за повеќе разговори и корисниците во нив. Како да се преселите од ова на новиот кориснички мотор и мотор за разговор?

членови-четовите во старата шема се користеа првенствено за оптимизација. Брзо ги префрливме потребните податоци од него на чет-членови, а потоа тој повеќе не учествуваше во процесот на миграција.

Ред за чет-членови. Вклучува 100 примероци, додека chat-engine има 4 илјади. За да ги пренесете податоците, треба да ги усогласите - за ова, членовите на разговор беа поделени на истите 4 илјади примероци, а потоа беше овозможено читање на бинлогот за членови на разговор во моторот за разговор.

Сега chat-engine знае за мулти-чет од членови на чет, но сè уште не знае ништо за дијалози со двајца соговорници. Таквите дијалози се наоѓаат во текстуалниот мотор со повикување на корисниците. Овде ги зедовме податоците „главно“: секој примерок на мотор за разговор ги прашуваше сите примероци на текстуален мотор дали го имаат потребниот дијалог.

Одлично - чет-моторот знае какви муабети со повеќе разговори има и знае какви дијалози има.
Треба да ги комбинирате пораките во разговорите со повеќе разговори, така што ќе завршите со листа на пораки во секој разговор. Прво, chat-engine ги вади од текстуалниот мотор сите кориснички пораки од овој разговор. Во некои случаи има доста од нив (до стотици милиони), но со многу ретки исклучоци разговорот целосно се вклопува во RAM меморијата. Имаме неподредени пораки, секоја во неколку копии - на крајот на краиштата, сите тие се извлечени од различни примероци на текстуален мотор што одговараат на корисниците. Целта е да се подредат пораките и да се ослободат од копии кои зафаќаат непотребен простор.

Секоја порака има временски печат кој го содржи времето кога е испратена и текстот. Ние користиме време за сортирање - поставуваме покажувачи до најстарите пораки на учесниците во мултичат и споредуваме хашови од текстот на наменетите копии, придвижувајќи се кон зголемување на временскиот печат. Логично е дека копиите ќе имаат ист хаш и временски печат, но во пракса тоа не е секогаш случај. Како што се сеќавате, синхронизацијата во старата шема беше извршена од PHP - и во ретки случаи, времето на испраќање на истата порака се разликуваше кај различни корисници. Во овие случаи, си дозволивме да го уредиме временскиот печат - обично во рок од една секунда. Вториот проблем е различниот редослед на пораки за различни примачи. Во такви случаи, дозволивме да се создаде дополнителна копија, со различни опции за нарачка за различни корисници.

По ова, податоците за пораките во мултичат се испраќаат до корисничкиот мотор. И тука доаѓа една непријатна карактеристика на увезените пораки. Во нормална работа, пораките што доаѓаат до моторот се нарачуваат строго во растечки редослед од user_local_id. Пораките увезени од стариот мотор во корисничкиот мотор го изгубија ова корисно својство. Во исто време, за практичноста на тестирањето, треба да можете брзо да пристапите до нив, да барате нешто во нив и да додавате нови.

Ние користиме специјална структура на податоци за складирање на увезени пораки.

Претставува вектор на големина каде се сите - се различни и подредени по опаѓачки редослед, со посебен ред на елементи. Во секој сегмент со индекси елементите се подредени. Барањето елемент во таква структура бара време преку бинарни пребарувања. Додавањето на елемент се амортизира .

Значи, сфативме како да пренесуваме податоци од старите мотори на нови. Но, овој процес трае неколку дена - и малку е веројатно дека во текот на овие денови нашите корисници ќе се откажат од навиката да пишуваат едни на други. За да не губиме пораки во ова време, се префрламе на работна шема која користи и стари и нови кластери.

Податоците се запишуваат на членовите на разговор и на корисничкиот мотор (а не на текстуалниот мотор, како во нормална работа според старата шема). user-engine го прокси барањето за chat-engine - и овде однесувањето зависи од тоа дали овој разговор е веќе споен или не. Ако разговорот сè уште не е споен, моторот за разговор не ја пишува пораката сам за себе, а нејзината обработка се случува само во моторот за текст. Ако разговорот е веќе споен во chat-engine, тој го враќа chat_local_id на корисничкиот мотор и ја испраќа пораката до сите примачи. кориснички мотор ги префрла сите податоци во текстуален мотор - така што ако се случи нешто, секогаш можеме да се вратиме назад, имајќи ги сите тековни податоци во стариот мотор. text-engine враќа user_local_id, кој корисничкиот мотор го складира и го враќа во задниот дел.

Како резултат на тоа, процесот на транзиција изгледа вака: поврзуваме празни кластери кориснички-мотор и чет-мотор. chat-engine го чита целиот бинлог на членовите на разговорот, а потоа започнува проксирањето според шемата опишана погоре. Ги пренесуваме старите податоци и добиваме два синхронизирани кластери (стари и нови). Останува само да се префрли читањето од текстуален на кориснички мотор и да се оневозможи прокси.

Наоди

Благодарение на новиот пристап, сите показатели за перформансите на моторите се подобрени и проблемите со конзистентноста на податоците се решени. Сега можеме брзо да имплементираме нови функции во пораките (и веќе почнавме да го правиме тоа - го зголемивме максималниот број на учесници во разговорот, имплементиравме пребарување за препратени пораки, стартувавме закачени пораки и го подигнавме ограничувањето на вкупниот број пораки по корисник) .

Промените во логиката се навистина огромни. И би сакал да забележам дека ова не секогаш значи цели години развој од огромен тим и безброј линии код. чет-мотор и кориснички мотор заедно со сите дополнителни приказни како Хафман за компресија на пораки, Splay дрвја и структура за увезени пораки е помалку од 20 илјади линии код. И тие беа напишани од 3 програмери за само 10 месеци (сепак, вреди да се има предвид тоа сите три програмер - светски шампиони во спортско програмирање).

Покрај тоа, наместо да го удвоиме бројот на сервери, го намаливме нивниот број за половина - сега корисничкиот мотор и моторот за разговор живеат на 500 физички машини, додека новата шема има голем простор за оптоварување. Заштедивме многу пари на опрема - околу 5 милиони долари + 750 илјади долари годишно оперативни трошоци.

Ние се стремиме да ги најдеме најдобрите решенија за најсложените и најголеми проблеми. Имаме многу од нив - и затоа бараме талентирани програмери во одделот за бази на податоци. Доколку сакате и знаете како да решавате вакви проблеми, имате одлично познавање на алгоритми и структури на податоци, ве покануваме да се придружите на тимот. Контактирајте го нашиот HRза детали.

Дури и ако оваа приказна не е за вас, ве молиме имајте предвид дека ги цениме препораките. Кажете му на пријател за слободни работни места за програмери, и ако успешно го заврши пробниот период, ќе добиете бонус од 100 илјади рубли.

Извор: www.habr.com