Pārrakstiet VKontakte ziņojumu datu bāzi no nulles un izdzīvojiet

Mūsu lietotāji raksta viens otram ziņas, nezinot nogurumu.

Tas ir diezgan daudz. Ja jūs nolemjat izlasīt visus visu lietotāju ziņojumus, tas aizņemtu vairāk nekā 150 tūkstošus gadu. Ar nosacījumu, ka esat diezgan pieredzējis lasītājs un katrai ziņai veltāt ne vairāk kā sekundi.

Ar šādu datu apjomu ir ļoti svarīgi, lai to glabāšanas un piekļuves loģika tiktu veidota optimāli. Pretējā gadījumā vienā ne pārāk brīnišķīgā mirklī var kļūt skaidrs, ka drīz viss noies greizi.

Mums šis brīdis pienāca pirms pusotra gada. Kā mēs līdz tam nonācām un kas notika beigās - mēs jums pastāstīsim secībā.

slimības vēsture

Pirmajā ieviešanā VKontakte ziņojumi darbojās ar PHP aizmugursistēmas un MySQL kombināciju. Tas ir pilnīgi normāls risinājums nelielai studentu vietnei. Tomēr šī vietne nekontrolējami pieauga un sāka pieprasīt datu struktūru optimizāciju.

2009. gada beigās tika uzrakstīta pirmā teksta dzinēja repozitorija, un 2010. gadā uz to tika pārsūtīti ziņojumi.

Teksta programmā ziņojumi tika saglabāti sarakstos - sava veida “pastkastītēs”. Katru šādu sarakstu nosaka uid — lietotājs, kuram pieder visi šie ziņojumi. Ziņojumam ir atribūtu kopa: sarunu partnera identifikators, teksts, pielikumi un tā tālāk. Ziņojuma identifikators lodziņā ir local_id, tas nekad nemainās un tiek piešķirts secīgi jauniem ziņojumiem. “Kastes” ir neatkarīgas un nav sinhronizētas viena ar otru dzinēja iekšpusē; saziņa starp tām notiek PHP līmenī. Jūs varat apskatīt teksta dzinēja datu struktūru un iespējas no iekšpuses šeit.

Ar to pilnīgi pietika sarakstei starp diviem lietotājiem. Uzminiet, kas notika tālāk?

2011. gada maijā VKontakte ieviesa sarunas ar vairākiem dalībniekiem — vairāku tērzēšanu. Lai strādātu ar viņiem, mēs izveidojām divus jaunus klasterus — dalībnieku tērzēšanu un tērzēšanas dalībniekus. Pirmajā tiek glabāti dati par lietotāju tērzēšanu, otrajā tiek saglabāti dati par lietotājiem pēc tērzēšanas. Papildus pašiem sarakstiem tas ietver, piemēram, uzaicināto lietotāju un laiku, kad viņš tika pievienots tērzēšanai.

"PHP, nosūtīsim ziņojumu uz tērzēšanu," saka lietotājs.
“Nāc, {lietotājvārds},” saka PHP.

Šai shēmai ir trūkumi. Sinhronizācija joprojām ir PHP atbildība. Lielas tērzēšanas sarunas un lietotāji, kas vienlaikus sūta viņiem ziņojumus, ir bīstams stāsts. Tā kā teksta programmas gadījums ir atkarīgs no uid, tērzēšanas dalībnieki var saņemt vienu un to pašu ziņojumu dažādos laikos. Ar to varētu dzīvot, ja progress apstātos. Bet tas nenotiks.

2015. gada beigās mēs izlaidām kopienas ziņojumus, bet 2016. gada sākumā – API. Līdz ar lielu tērzēšanas robotu parādīšanos kopienās bija iespējams aizmirst par vienmērīgu slodzes sadalījumu.

Labs robots dienā ģenerē vairākus miljonus ziņojumu - ar to nevar lepoties pat vispļāpīgākie lietotāji. Tas nozīmē, ka daži teksta dzinēju gadījumi, kuros šādi roboti dzīvoja, sāka ciest pilnībā.

Ziņojumu programmas 2016. gadā ir 100 tērzēšanas dalībnieku un dalībnieku tērzēšanas gadījumi un 8000 tekstu programmas. Tie tika mitināti tūkstoš serveros, katrs ar 64 GB atmiņu. Kā pirmo ārkārtas pasākumu mēs palielinājām atmiņu vēl par 32 GB. Mēs aprēķinājām prognozes. Bez krasām izmaiņām ar to pietiktu vēl apmēram gadam. Jums ir jāiegūst aparatūra vai jāoptimizē pašas datu bāzes.

Arhitektūras rakstura dēļ ir jēga palielināt aparatūru tikai vairākkārt. Tas ir, automašīnu skaita vismaz dubultošana - acīmredzot, tas ir diezgan dārgs ceļš. Mēs optimizēsim.

Jauna koncepcija

Jaunās pieejas galvenā būtība ir tērzēšana. Tērzēšanā ir ar to saistīto ziņojumu saraksts. Lietotājam ir tērzēšanas sarunu saraksts.

Nepieciešamais minimums ir divas jaunas datu bāzes:

• tērzēšanas dzinējs. Šī ir tērzēšanas vektoru krātuve. Katrai tērzēšanai ir ar to saistīto ziņojumu vektors. Katram ziņojumam ir teksts un unikāls ziņojuma identifikators tērzēšanas iekšpusē - chat_local_id.
• lietotāja dzinējs. Šī ir lietotāju vektoru krātuve - saites uz lietotājiem. Katram lietotājam ir vienādranga_id vektors (sarunu biedri - citi lietotāji, multi-tērzēšana vai kopienas) un ziņojumu vektors. Katram peer_id ir ar to saistīto ziņojumu vektors. Katram ziņojumam ir chat_local_id un unikāls ziņojuma ID šim lietotājam — user_local_id.

Jauni klasteri sazinās savā starpā, izmantojot TCP – tas nodrošina, ka pieprasījumu secība nemainās. Paši pieprasījumi un apstiprinājumi tiem tiek ierakstīti cietajā diskā – tātad mēs varam jebkurā brīdī atjaunot rindas stāvokli pēc kļūmes vai dzinēja restartēšanas. Tā kā lietotāja dzinējs un tērzēšanas dzinējs ir katrs pa 4 tūkstošiem shardu, pieprasījumu rinda starp klasteriem tiks sadalīta vienmērīgi (bet patiesībā tādas nav vispār - un tas darbojas ļoti ātri).

Darbs ar disku mūsu datubāzēs vairumā gadījumu ir balstīts uz binārā izmaiņu žurnāla (binlog), statisko momentuzņēmumu un daļēja attēla kombināciju atmiņā. Dienas laikā veiktās izmaiņas tiek ierakstītas binlogā, un periodiski tiek izveidots pašreizējā stāvokļa momentuzņēmums. Momentuzņēmums ir datu struktūru kolekcija, kas optimizēta mūsu mērķiem. Tas sastāv no galvenes (attēla metaindekss) un metafailu kopas. Galvene tiek pastāvīgi saglabāta RAM un norāda, kur meklēt datus no momentuzņēmuma. Katrā metafailā ir iekļauti dati, kas, visticamāk, būs nepieciešami tuvākajā laikā, piemēram, saistīti ar vienu lietotāju. Kad vaicājat datu bāzē, izmantojot momentuzņēmuma galveni, tiek nolasīts nepieciešamais metafails, un pēc tam tiek ņemtas vērā izmaiņas binlog, kas notika pēc momentuzņēmuma izveides. Jūs varat lasīt vairāk par šīs pieejas priekšrocībām šeit.

Tajā pašā laikā dati uz paša cietā diska mainās tikai vienu reizi dienā - vēlu vakarā Maskavā, kad slodze ir minimāla. Pateicoties tam (zinot, ka diska struktūra ir nemainīga visas dienas garumā), mēs varam atļauties vektorus aizstāt ar fiksēta izmēra masīviem - un tāpēc palielināsies atmiņa.

Ziņojuma nosūtīšana jaunajā shēmā izskatās šādi:

1. PHP aizmugursistēma sazinās ar lietotāja dzinēju ar pieprasījumu nosūtīt ziņojumu.
2. user-engine starpniekserveri pieprasījumu vēlamajai tērzēšanas programmas instancei, kas atgriežas lietotāja dzinēja tērzēšanas_local_id — jauna ziņojuma unikālajā identifikatorā šajā tērzēšanas ietvaros. Pēc tam tērzēšanas_programma pārraida ziņojumu visiem tērzēšanas adresātiem.
3. user-engine saņem chat_local_id no tērzēšanas dzinēja un atgriež user_local_id PHP — unikālu ziņojuma identifikatoru šim lietotājam. Pēc tam šis identifikators tiek izmantots, piemēram, darbam ar ziņojumiem, izmantojot API.

Taču papildus faktiskajai ziņojumu sūtīšanai jums ir jāievieš vēl dažas svarīgas lietas:

• Apakšsaraksti ir, piemēram, jaunākie ziņojumi, ko redzat, atverot sarunu sarakstu. Nelasīti ziņojumi, ziņojumi ar atzīmēm (“Svarīgi”, “Mēstules” utt.).
• Ziņojumu saspiešana tērzēšanas programmā
• Ziņojumu saglabāšana kešatmiņā lietotāja dzinējā
• Meklēt (visos dialogos un konkrētā).
• Reāllaika atjauninājums (Longpolling).
• Vēstures saglabāšana, lai mobilajos klientiem ieviestu kešatmiņu.

Visi apakšsaraksti ir strauji mainīgas struktūras. Lai strādātu ar viņiem, mēs izmantojam Spēļu koki. Šāda izvēle ir izskaidrojama ar to, ka koka augšdaļā mēs dažkārt glabājam veselu segmentu ziņojumu no momentuzņēmuma - piemēram, pēc ikvakara pārindeksēšanas koks sastāv no vienas augšas, kurā ir visi apakšsaraksta ziņojumi. Splay koks ļauj viegli ievietot šādas virsotnes vidū, nedomājot par balansēšanu. Turklāt Splay neuzglabā nevajadzīgus datus, kas ietaupa mūsu atmiņu.

Ziņojumi ietver lielu informācijas daudzumu, galvenokārt tekstu, kas ir noderīgi, lai varētu saspiest. Ir svarīgi, lai mēs varētu precīzi dearhivēt pat vienu atsevišķu ziņojumu. Izmanto, lai saspiestu ziņojumus Hafmena algoritms ar savu heiristiku - piemēram, mēs zinām, ka ziņojumos vārdi mijas ar "nevārdiem" - atstarpes, pieturzīmes - un atceramies arī dažas krievu valodas simbolu lietošanas īpatnības.

Tā kā lietotāju ir daudz mazāk nekā tērzēšanas lietotāju, lai saglabātu brīvpiekļuves diska pieprasījumus tērzēšanas programmā, mēs kešatmiņā saglabājam ziņojumus lietotāja programmā.

Ziņojumu meklēšana tiek ieviesta kā diagonāls vaicājums no lietotāja dzinēja uz visiem tērzēšanas programmas gadījumiem, kuros ir šī lietotāja tērzēšanas sarunas. Rezultāti tiek apvienoti pašā lietotāja dzinējā.

Nu, visas detaļas ir ņemtas vērā, atliek tikai pāriet uz jaunu shēmu - un vēlams, lietotājiem to nemanot.

Datu migrācija

Tātad, mums ir teksta programma, kas glabā ziņojumus pēc lietotāja, un divas tērzēšanas dalībnieku un dalībnieku tērzēšanas kopas, kas glabā datus par vairāku tērzēšanas istabām un lietotājiem tajās. Kā no šīs pāriet uz jauno lietotāja dzinēju un tērzēšanas programmu?

biedru tērzēšana vecajā shēmā galvenokārt tika izmantota optimizācijai. Mēs ātri pārsūtījām no tā nepieciešamos datus tērzēšanas dalībniekiem, un tad tas vairs nepiedalījās migrācijas procesā.

Rinda tērzēšanas dalībniekiem. Tas ietver 100 gadījumus, savukārt tērzēšanas dzinējam ir 4 tūkstoši. Lai pārsūtītu datus, tie ir jāsaskaņo - šim nolūkam tērzēšanas dalībnieki tika sadalīti tajos pašos 4 tūkstošos kopiju, un pēc tam tērzēšanas programmā tika iespējota tērzēšanas dalībnieku binlog lasīšana.

Tagad tērzēšanas dzinējs zina par multi-čatu no tērzēšanas dalībniekiem, bet vēl neko nezina par dialogiem ar diviem sarunu biedriem. Šādi dialogi atrodas teksta dzinējā, atsaucoties uz lietotājiem. Šeit mēs ņēmām datus uz priekšu: katrs tērzēšanas programmas gadījums jautāja visiem teksta programmas gadījumiem, vai viņiem ir nepieciešamais dialogs.

Lieliski — tērzēšanas dzinējs zina, kādi ir vairāku tērzēšanas sarunu veidi, un zina, kādi dialogi pastāv.
Ziņojumi ir jāapvieno vairāku tērzēšanas sarunās, lai katrā tērzēšanā tiktu parādīts ziņojumu saraksts. Pirmkārt, tērzēšanas programma no teksta programmas izgūst visus lietotāja ziņojumus no šīs tērzēšanas. Dažos gadījumos to ir diezgan daudz (līdz pat simtiem miljonu), taču ar ļoti retiem izņēmumiem tērzēšana pilnībā iekļaujas RAM. Mums ir nesakārtoti ziņojumi, katrs vairākos eksemplāros - galu galā tie visi ir izvilkti no dažādiem lietotājiem atbilstošiem teksta dzinēja gadījumiem. Mērķis ir kārtot ziņas un atbrīvoties no kopijām, kas aizņem nevajadzīgu vietu.

Katram ziņojumam ir laikspiedols, kurā norādīts tās nosūtīšanas laiks un teksts. Mēs izmantojam laiku šķirošanai - ievietojam norādes uz multičata dalībnieku vecākajiem ziņojumiem un salīdzinām jaucējvārdus no paredzēto kopiju teksta, virzoties uz laika zīmoga palielināšanu. Loģiski, ka kopijām būs vienāds jaukums un laikspiedols, taču praksē tas ne vienmēr notiek. Kā jūs atceraties, sinhronizāciju vecajā shēmā veica PHP - un retos gadījumos viena un tā paša ziņojuma nosūtīšanas laiks dažādiem lietotājiem bija atšķirīgs. Šādos gadījumos mēs atļāvām rediģēt laikspiedolu — parasti sekundes laikā. Otra problēma ir atšķirīgā ziņojumu secība dažādiem adresātiem. Šādos gadījumos mēs atļāvām izveidot papildu kopiju ar dažādām pasūtīšanas iespējām dažādiem lietotājiem.

Pēc tam dati par ziņojumiem multičatā tiek nosūtīti uz lietotāja dzinēju. Un šeit parādās nepatīkama importēto ziņojumu iezīme. Parastā darbībā ziņojumi, kas nonāk dzinējā, tiek sakārtoti augošā secībā pēc user_local_id. Ziņojumi, kas importēti no vecā dzinēja lietotāja dzinējā, zaudēja šo noderīgo īpašību. Tajā pašā laikā testēšanas ērtībai ir jāspēj tiem ātri piekļūt, kaut ko meklēt un pievienot jaunus.

Importēto ziņojumu glabāšanai mēs izmantojam īpašu datu struktūru.

Tas apzīmē lieluma vektoru kur is Visi - ir dažādi un sakārtoti dilstošā secībā, ar īpašu elementu secību. Katrā segmentā ar indeksiem elementi ir sakārtoti. Elementa meklēšana šādā struktūrā prasa laiku caur binārie meklējumi. Elementa pievienošana tiek amortizēta .

Tātad, mēs izdomājām, kā pārsūtīt datus no vecajiem dzinējiem uz jauniem. Taču šis process aizņem vairākas dienas – un maz ticams, ka šo dienu laikā mūsu lietotāji atteiksies no ieraduma rakstīt viens otram. Lai šajā laikā nepazaudētu ziņojumus, mēs pārslēdzamies uz darba shēmu, kurā tiek izmantoti gan vecie, gan jaunie klasteri.

Dati tiek rakstīti tērzēšanas dalībniekiem un lietotāja dzinējam (nevis teksta dzinējam, kā parastajā darbībā saskaņā ar veco shēmu). user-engine starpniekserveri pieprasījumu tērzēšanas dzinējam — un šeit darbība ir atkarīga no tā, vai šī tērzēšana jau ir apvienota vai nav. Ja tērzēšana vēl nav apvienota, tērzēšanas programma neraksta ziņojumu sev, un tā apstrāde notiek tikai teksta programmā. Ja tērzēšana jau ir apvienota ar tērzēšanas programmu, tā atgriež lietotāja dzinējam chat_local_id un nosūta ziņojumu visiem adresātiem. user-engine starpniekserveri visus datus teksta dzinējam — lai, ja kaut kas notiek, mēs vienmēr varētu atsaukt atpakaļ, izmantojot visus pašreizējos datus vecajā dzinējā. text-engine atgriež user_local_id, kuru lietotāja programma saglabā un atgriež aizmugursistēmā.

Rezultātā pārejas process izskatās šādi: mēs savienojam tukšas lietotāja dzinēja un tērzēšanas programmas kopas. tērzēšanas dzinējs nolasa visu tērzēšanas dalībnieku binlog, pēc tam sākas starpniekserverēšana saskaņā ar iepriekš aprakstīto shēmu. Mēs pārsūtām vecos datus un iegūstam divus sinhronizētus klasteri (veco un jauno). Atliek tikai pārslēgt lasīšanu no teksta dzinēja uz lietotāja dzinēju un atspējot starpniekserveri.

rezultātus

Pateicoties jaunajai pieejai, ir uzlaboti visi dzinēju veiktspējas rādītāji un atrisinātas problēmas ar datu konsekvenci. Tagad mēs varam ātri ieviest jaunas funkcijas ziņojumos (un esam jau sākuši to darīt — palielinājām maksimālo tērzēšanas dalībnieku skaitu, ieviesām pārsūtīto ziņojumu meklēšanu, palaižam piespraustos ziņojumus un palielinājām kopējo ziņojumu skaita ierobežojumu vienam lietotājam) .

Izmaiņas loģikā ir patiešām milzīgas. Un es vēlos atzīmēt, ka tas ne vienmēr nozīmē veselus gadus ilgas izstrādes, ko veic milzīga komanda un neskaitāmas koda rindiņas. tērzēšanas dzinējs un lietotāja dzinējs kopā ar visiem papildu stāstiem, piemēram, Huffman ziņojumu saspiešanai, Splay koki un importēto ziņojumu struktūra ir mazāks par 20 tūkstošiem koda rindiņu. Un tos tikai 3 mēnešu laikā uzrakstīja 10 izstrādātāji (tomēr ir vērts paturēt prātā, ka viss trīs izstrādātājs - pasaules čempioni sporta programmās).

Turklāt tā vietā, lai dubultotu serveru skaitu, mēs to skaitu samazinājām uz pusi - tagad lietotāja dzinējs un tērzēšanas dzinējs darbojas uz 500 fiziskām iekārtām, savukārt jaunajā shēmā ir liela slodze. Mēs ietaupījām daudz naudas par iekārtām – apmēram $ 5 miljoni + $ 750 tūkstoši gadā darbības izdevumos.

Mēs cenšamies atrast labākos risinājumus vissarežģītākajām un apjomīgākajām problēmām. Mums to ir daudz, un tāpēc mēs datu bāzes nodaļā meklējam talantīgus izstrādātājus. Ja mīli un proti risināt šādas problēmas, lieliski pārzini algoritmus un datu struktūras, aicinām pievienoties komandai. Sazinieties ar mūsu HRsīkākai informācijai.

Pat ja šis stāsts nav par jums, lūdzu, ņemiet vērā, ka mēs augstu vērtējam ieteikumus. Pastāstiet draugam par izstrādātāju vakances, un, ja viņš veiksmīgi pabeigs pārbaudes laiku, jūs saņemsiet prēmiju 100 tūkstošu rubļu apmērā.

Avots: www.habr.com