Поново напишите базу података ВКонтакте порука од нуле и преживите

Наши корисници пишу једни другима поруке не знајући да су уморни.

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

Са таквим обимом података, од кључне је важности да се логика за њихово складиштење и приступ њима изгради оптимално. У супротном, у једном не баш чудесном тренутку може постати јасно да ће све ускоро кренути наопако.

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

Позадина

У првој имплементацији, ВКонтакте поруке су радиле на комбинацији ПХП бацкенд-а и МиСКЛ-а. Ово је сасвим нормално решење за мали студентски сајт. Међутим, овај сајт је неконтролисано растао и почео да захтева оптимизацију структуре података за себе.

Крајем 2009. године написано је прво текстуално складиште, ау њега су 2010. пренете поруке.

У текстуалном мотору, поруке су биле ускладиштене у листама - својеврсним „поштанским сандучићима“. Свака таква листа је одређена уид-ом - корисником који поседује све ове поруке. Порука има скуп атрибута: идентификатор саговорника, текст, прилоге и тако даље. Идентификатор поруке унутар „кутије“ је лоцал_ид, никада се не мења и додељује се узастопно за нове поруке. „Кутије“ су независне и нису синхронизоване једна са другом унутар машине; комуникација између њих се одвија на нивоу ПХП-а. Можете погледати структуру података и могућности тект-енгине-а изнутра овде.

Ово је било сасвим довољно за преписку између два корисника. Погоди шта се следеће догодило?

У мају 2011. ВКонтакте је увео разговоре са неколико учесника — мулти-чет. Да бисмо радили са њима, подигли смо два нова кластера - цхат-цхат и цхат-мембер. Први чува податке о четовима по корисницима, други податке о корисницима по четовима. Поред самих листа, ово укључује, на пример, корисника који позива и време када су додани у ћаскање.

„ПХП, пошаљимо поруку у ћаскање“, каже корисник.
„Хајде, {усернаме}“, каже ПХП.

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

Крајем 2015. покренули смо поруке заједнице, а почетком 2016. покренули смо АПИ за њих. Са појавом великих цхатбота у заједницама, било је могуће заборавити на равномерну расподелу оптерећења.

Добар бот генерише неколико милиона порука дневно - чак ни најпричљивији корисници не могу се похвалити овим. То значи да су неке инстанце тект-енгине-а, на којима су живели такви ботови, почели да трпе у потпуности.

Механизми за поруке у 2016. су 100 инстанци чланова и чланова ћаскања и 8000 текстуалних машина. Хостовани су на хиљаду сервера, сваки са 64 ГБ меморије. Као прву хитну меру, повећали смо меморију за још 32 ГБ. Процењивали смо прогнозе. Без драстичних промена, ово би било довољно за још око годину дана. Морате или да набавите хардвер или да оптимизујете саме базе података.

Због природе архитектуре, има смисла само повећати хардвер вишеструко. То јест, барем удвостручити број аутомобила - очигледно, ово је прилично скуп пут. Ми ћемо оптимизовати.

Нови концепт

Централна суштина новог приступа је ћаскање. Ћаскање има листу порука које се односе на њега. Корисник има листу ћаскања.

Неопходан минимум су две нове базе података:

• цхат-енгине. Ово је спремиште вектора за ћаскање. Свако ћаскање има вектор порука које се односе на њега. Свака порука има текст и јединствени идентификатор поруке унутар ћаскања - цхат_лоцал_ид.
• кориснички мотор. Ово је складиште корисничких вектора - веза до корисника. Сваки корисник има вектор пеер_ид (саговорници - други корисници, мулти-чет или заједнице) и вектор порука. Сваки пеер_ид има вектор порука које се односе на њега. Свака порука има цхат_лоцал_ид и јединствени ИД поруке за тог корисника - усер_лоцал_ид.

Нови кластери комуницирају једни са другима користећи ТЦП - ово осигурава да се редослед захтева не мења. Сами захтеви и потврде за њих се снимају на хард диску - тако да можемо да вратимо стање реда у било ком тренутку након квара или поновног покретања мотора. Пошто су кориснички мотор и мотор за ћаскање по 4 хиљаде шарда, ред захтева између кластера ће бити равномерно распоређен (али у стварности га уопште нема - и ради веома брзо).

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

Истовремено, подаци на самом хард диску мењају се само једном дневно - касно увече у Москви, када је оптерећење минимално. Захваљујући томе (знајући да је структура на диску константна током дана), можемо себи приуштити да заменимо векторе низовима фиксне величине - и због тога добијемо меморију.

Слање поруке у новој шеми изгледа овако:

1. ПХП бацкенд контактира кориснички мотор са захтевом да пошаље поруку.
2. усер-енгине проксије захтев жељеној инстанци мотора за ћаскање, који се враћа на усер-енгине цхат_лоцал_ид - јединствени идентификатор нове поруке у оквиру овог ћаскања. Цхат_енгине затим емитује поруку свим примаоцима у ћаскању.
3. усер-енгине прима цхат_лоцал_ид од цхат-енгине и враћа усер_лоцал_ид у ПХП - јединствени идентификатор поруке за овог корисника. Овај идентификатор се затим користи, на пример, за рад са порукама преко АПИ-ја.

Али поред стварног слања порука, потребно је да примените још неколико важних ствари:

• Подлисте су, на пример, најновије поруке које видите када отварате листу конверзација. Непрочитане поруке, поруке са ознакама („Важно“, „Нежељена пошта“ итд.).
• Компресовање порука у систему за ћаскање
• Кеширање порука у корисничком механизму
• Претрага (кроз све дијалоге и унутар одређеног).
• Ажурирање у реалном времену (Лонгполлинг).
• Чување историје за имплементацију кеширања на мобилним клијентима.

Све подлисте су структуре које се брзо мењају. За рад са њима користимо Сплаи треес. Овај избор се објашњава чињеницом да на врху стабла понекад складиштимо читав сегмент порука из снимка – на пример, након ноћног поновног индексирања, стабло се састоји од једног врха, који садржи све поруке подлисте. Сплаи дрво олакшава уметање у средину таквог темена без размишљања о балансирању. Поред тога, Сплаи не складишти непотребне податке, што нам штеди меморију.

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

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

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

Па, сви детаљи су узети у обзир, остаје само да се пређе на нову шему - и по могућности да корисници то не примете.

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

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

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

Ред за чланове ћаскања. Укључује 100 инстанци, док цхат-енгине има 4 хиљаде. Да бисте пренели податке, потребно је да их ускладите - за то су чланови ћаскања подељени у исте 4 хиљаде копија, а затим је омогућено читање бинлог-а чланова ћаскања у мотору за ћаскање.

Сада мотор за ћаскање зна за мулти-чет од чланова четовања, али још не зна ништа о дијалозима са два саговорника. Такви дијалози се налазе у текстуалном мотору у односу на кориснике. Овде смо узели податке директно: свака инстанца мотора за ћаскање је питала све инстанце текстуалног механизма да ли имају дијалог који им је потребан.

Сјајно - машина за ћаскање зна који разговори са више ћаскања постоје и зна који дијалози постоје.
Морате да комбинујете поруке у ћаскањима са више ћаскања тако да на крају добијете листу порука у сваком ћаскању. Прво, машина за ћаскање преузима из текстуалног механизма све корисничке поруке из овог ћаскања. У неким случајевима их има доста (до стотине милиона), али уз веома ретке изузетке, ћаскање се у потпуности уклапа у РАМ. Имамо неуређене поруке, свака у неколико копија – на крају крајева, све су извучене из различитих инстанци текстуалног механизма који одговарају корисницима. Циљ је сортирати поруке и ослободити се копија које заузимају непотребан простор.

Свака порука има временску ознаку која садржи време када је послата и текст. Користимо време за сортирање - постављамо показиваче на најстарије поруке учесника мултицхата и упоређујемо хешове из текста предвиђених копија, крећући се ка повећању временске ознаке. Логично је да ће копије имати исти хеш и временску ознаку, али у пракси то није увек случај. Као што се сећате, синхронизацију у старој шеми вршио је ПХП - а у ретким случајевима време слања исте поруке се разликовало међу различитим корисницима. У овим случајевима, дозволили смо себи да уредимо временску ознаку - обично у року од једне секунде. Други проблем је различит редослед порука за различите примаоце. У таквим случајевима, дозволили смо да се направи додатна копија, са различитим опцијама наручивања за различите кориснике.

Након тога, подаци о порукама у мултицхату се шаљу корисничком мотору. А ту долази и непријатна карактеристика увезених порука. У нормалном раду, поруке које долазе у машину су поређане стриктно у растућем редоследу према усер_лоцал_ид. Поруке увезене са старог мотора у кориснички мотор су изгубиле ово корисно својство. Истовремено, због погодности тестирања, морате бити у могућности да им брзо приступите, потражите нешто у њима и додате нове.

Користимо посебну структуру података за складиштење увезених порука.

Представља вектор величине где су сви - различити су и поређани у опадајућем редоследу, са посебним редоследом елемената. У сваком сегменту са индексима елементи су сортирани. Трагање за елементом у таквој структури захтева време кроз бинарне претраге. Додавање елемента се амортизује .

Дакле, схватили смо како да пренесемо податке са старих мотора на нове. Али овај процес траје неколико дана - и мало је вероватно да ће током ових дана наши корисници одустати од навике писања једни другима. Да не бисмо изгубили поруке током овог времена, прелазимо на радну шему која користи и старе и нове кластере.

Подаци се уписују у цхат-чланове и усер-енгине (а не у тект-енгине, као у нормалном раду по старој шеми). усер-енгине прокси захтев за цхат-енгине - и овде понашање зависи од тога да ли је ово ћаскање већ спојено или не. Ако ћаскање још није спојено, машина за ћаскање не пише поруку себи, а њена обрада се дешава само у текстуалном механизму. Ако је ћаскање већ спојено са машином за ћаскање, враћа цхат_лоцал_ид корисничком мотору и шаље поруку свим примаоцима. усер-енгине прокси све податке у тект-енгине - тако да, ако се нешто деси, увек можемо да се вратимо, имајући све тренутне податке у старом мотору. тект-енгине враћа усер_лоцал_ид, који кориснички мотор чува и враћа у позадину.

Као резултат, процес транзиције изгледа овако: повезујемо празне корисничке машине и кластере за ћаскање. цхат-енгине чита цео бинлог чланова ћаскања, а затим прокси почиње према горе описаној шеми. Преносимо старе податке и добијамо два синхронизована кластера (стари и нови). Све што остаје је да пребаците читање са текстуалног на кориснички механизам и онемогућите прокси.

Налази

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

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

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

Трудимо се да пронађемо најбоља решења за најсложеније и највеће проблеме. Имамо их доста - и зато тражимо талентоване програмере у одељењу за базе података. Ако волите и знате како да решавате овакве проблеме, одлично познајете алгоритме и структуре података, позивамо вас да се придружите тиму. Контактирајте наше HR, чтоби узнать подробности.

Чак и ако ова прича није о вама, имајте на уму да ценимо препоруке. Реци пријатељу о слободна радна места за програмере, а ако успешно заврши пробни период, добићете бонус од 100 хиљада рубаља.

Извор: ввв.хабр.цом