Kirjutage VKontakte sõnumite andmebaas nullist ümber ja jääge ellu

Meie kasutajad kirjutavad üksteisele sõnumeid tundmata väsimust.

Seda on päris palju. Kui kavatsete lugeda kõigi kasutajate kõiki sõnumeid, kuluks selleks rohkem kui 150 tuhat aastat. Eeldusel, et olete üsna kogenud lugeja ja ei kuluta igale sõnumile rohkem kui sekundi.

Sellise andmemahu puhul on ülioluline, et nende salvestamise ja juurdepääsu loogika oleks üles ehitatud optimaalselt. Muidu võib ühel mitte just imelisel hetkel selguda, et peagi läheb kõik viltu.

Meie jaoks saabus see hetk poolteist aastat tagasi. Kuidas me selleni jõudsime ja mis lõpuks juhtus - räägime teile järjekorras.

haiguslugu

Esimeses rakenduses töötasid VKontakte sõnumid PHP taustaprogrammi ja MySQL kombinatsioonil. See on väikese tudengiveebi jaoks täiesti tavaline lahendus. See sait aga kasvas kontrollimatult ja hakkas nõudma enda jaoks andmestruktuuride optimeerimist.

2009. aasta lõpus kirjutati esimene tekstimootori repositoorium, kuhu 2010. aastal kanti üle sõnumid.

Tekstimootoris salvestati sõnumid loenditesse - omamoodi postkastidesse. Iga sellise loendi määrab uid - kasutaja, kellele kõik need sõnumid kuuluvad. Sõnumil on atribuutide komplekt: vestluspartneri identifikaator, tekst, manused ja nii edasi. Sõnumi identifikaator “kasti” sees on local_id, see ei muutu kunagi ja määratakse uute sõnumite jaoks järjestikku. "Kastid" on sõltumatud ja neid ei sünkroonita üksteisega mootori sees, nendevaheline suhtlus toimub PHP tasemel. Saate vaadata tekstimootori andmestruktuuri ja võimalusi seestpoolt siin.

Sellest piisas kahe kasutaja kirjavahetuseks täiesti. Arvake ära, mis edasi juhtus?

2011. aasta mais tutvustas VKontakte vestlusi mitme osalejaga – multivestlust. Nendega töötamiseks lõime kaks uut klastrit – liikmevestlused ja vestlusliikmed. Esimene salvestab andmeid kasutajate vestluste kohta, teine ​​salvestab andmed kasutajate kohta vestluste kaupa. Lisaks loenditele endile hõlmab see näiteks kutsuvat kasutajat ja tema vestlusesse lisamise aega.

"PHP, saadame vestlusele sõnumi," ütleb kasutaja.
"Tule nüüd, {username}," ütleb PHP.

Sellel skeemil on puudusi. Sünkroonimise eest vastutab endiselt PHP. Suured vestlused ja kasutajad, kes saadavad neile samaaegselt sõnumeid, on ohtlik lugu. Kuna tekstimootori eksemplar sõltub kasutajatunnusest, võivad vestluses osalejad saada sama sõnumi erinevatel aegadel. Sellega võiks elada, kui areng seisaks. Aga seda ei juhtu.

2015. aasta lõpus lansseerisime kogukonnasõnumid ja 2016. aasta alguses nende jaoks API. Suurte vestlusrobotite tulekuga kogukondadesse oli võimalik unustada koormuse ühtlane jaotus.

Hea bot genereerib mitu miljonit sõnumit päevas – isegi kõige jutukamad kasutajad ei saa sellega kiidelda. See tähendab, et mõned tekstimootori juhtumid, millel sellised robotid elasid, hakkasid täiel määral kannatama.

2016. aasta sõnumimootorid on 100 vestlusliikme ja liikme vestluse eksemplari ning 8000 tekstimootorit. Neid majutati tuhandel serveril, millest igaühel oli 64 GB mälu. Esimese hädaabinõuna suurendasime mälu veel 32 GB võrra. Hindasime prognoose. Ilma drastiliste muudatusteta piisaks sellest veel umbes aastaks. Peate hankima riistvara või optimeerima andmebaase ise.

Arhitektuuri olemusest tulenevalt on riistvara mõtet suurendada vaid kordades. Ehk siis autode arvu vähemalt kahekordistamine – ilmselgelt on see üsna kallis tee. Me optimeerime.

Uus kontseptsioon

Uue lähenemisviisi keskne olemus on vestlus. Vestlusel on sellega seotud sõnumite loend. Kasutajal on vestluste loend.

Nõutav miinimum on kaks uut andmebaasi:

• vestlusmootor. See on vestlusvektorite hoidla. Igal vestlusel on sellega seotud sõnumite vektor. Igal sõnumil on vestluses tekst ja kordumatu sõnumi identifikaator - chat_local_id.
• kasutaja mootor. See on kasutajate vektorite salvestus – kasutajate lingid. Igal kasutajal on peer_id vektor (vestluspartnerid - teised kasutajad, multivestlus või kogukonnad) ja sõnumite vektor. Igal peer_id-l on sellega seotud sõnumite vektor. Igal kirjal on chat_local_id ja selle kasutaja kordumatu sõnumi ID – user_local_id.

Uued klastrid suhtlevad omavahel TCP abil – see tagab, et päringute järjekord ei muutu. Päringud ise ja nende kinnitused salvestatakse kõvakettale – nii saame pärast mootori riket või taaskäivitamist igal ajal järjekorra oleku taastada. Kuna kasutajamootor ja vestlusmootor on kumbki 4 tuhat killust, jaotatakse päringujärjekord klastrite vahel ühtlaselt (kuid tegelikult pole seda üldse - ja see töötab väga kiiresti).

Meie andmebaasides kettaga töötamine põhineb enamikul juhtudel muudatuste binaarlogi (binlog), staatiliste hetktõmmiste ja mälus oleva osalise kujutise kombinatsioonil. Päeva jooksul tehtud muudatused kirjutatakse binlogi ja perioodiliselt luuakse hetkeseisu hetketõmmis. Hetktõmmis on meie eesmärkide jaoks optimeeritud andmestruktuuride kogum. See koosneb päisest (pildi metaindeks) ja metafailide komplektist. Päis salvestatakse püsivalt RAM-i ja see näitab, kust hetktõmmise andmeid otsida. Iga metafail sisaldab andmeid, mida tõenäoliselt läheb vaja lähiajal – näiteks seoses ühe kasutajaga. Kui teete andmebaasist päringu hetktõmmise päise abil, loetakse vajalik metafail ja seejärel võetakse arvesse pärast hetktõmmise loomist toimunud binlogis toimunud muudatusi. Lisateavet selle lähenemisviisi eeliste kohta saate lugeda siin.

Samal ajal muutuvad kõvaketta enda andmed ainult üks kord päevas - Moskvas hilisõhtul, kui koormus on minimaalne. Tänu sellele (teades, et ketta struktuur on päeva jooksul konstantne) saame lubada vektorite asendamist fikseeritud suurusega massiividega - ja tänu sellele mälu suurenemist.

Sõnumi saatmine uues skeemis näeb välja selline:

1. PHP taustaprogramm võtab kasutajamootoriga ühendust sõnumi saatmise taotlusega.
2. user-engine puhverserverib päringu soovitud vestlusmootori eksemplarile, mis naaseb kasutajamootori chat_local_id-sse – selles vestluses uue sõnumi kordumatuks identifikaatoriks. Chat_engine edastab seejärel sõnumi kõigile vestluses osalevatele adressaatidele.
3. user-engine saab vestlusmootorilt chat_local_id ja tagastab PHP-le user_local_id – selle kasutaja kordumatu sõnumiidentifikaatori. Seda identifikaatorit kasutatakse siis näiteks API kaudu sõnumitega töötamiseks.

Kuid lisaks sõnumite saatmisele peate rakendama veel mitmeid olulisi asju:

• Alamloendid on näiteks kõige värskemad sõnumid, mida näete vestlusloendi avamisel. Lugemata kirjad, siltidega kirjad ("Tähtis", "Rämpspost" jne).
• Sõnumite tihendamine vestlusmootoris
• Sõnumite vahemällu salvestamine kasutajamootoris
• Otsi (kõigis dialoogides ja konkreetses dialoogis).
• Reaalajas värskendus (Longpolling).
• Ajaloo salvestamine mobiiliklientide vahemällu salvestamiseks.

Kõik alamloendid on kiiresti muutuvate struktuuridega. Nendega töötamiseks kasutame Splay puud. See valik on seletatav asjaoluga, et puu ülaossa salvestame mõnikord terve segmendi hetktõmmise sõnumeid – näiteks pärast igaõhtust uuesti indekseerimist koosneb puu ühest tipust, mis sisaldab kõiki alamloendi teateid. Splay puu abil on lihtne sisestada sellise tipu keskele, ilma tasakaalustamisele mõtlemata. Lisaks ei salvesta Splay tarbetuid andmeid, mis säästab meie mälu.

Sõnumid sisaldavad suurt hulka teavet, enamasti teksti, mis on kasulik tihendamiseks. On oluline, et saaksime täpselt dearhiveerida isegi ühe üksiku sõnumi. Kasutatakse sõnumite tihendamiseks Huffmani algoritm oma heuristikaga - näiteks teame, et sõnumites vahelduvad sõnad "mittesõnadega" - tühikud, kirjavahemärgid - ja meenuvad ka mõned vene keele sümbolite kasutamise iseärasused.

Kuna kasutajaid on palju vähem kui vestlusi, salvestame juhusliku juurdepääsuga kettapäringute salvestamiseks vestlusmootorisse sõnumid vahemällu.

Sõnumiotsing rakendatakse diagonaalse päringuna kasutajamootorist kõikidesse vestlusmootori eksemplaridesse, mis sisaldavad selle kasutaja vestlusi. Tulemused kombineeritakse kasutajamootoris endas.

Noh, kõik üksikasjad on arvesse võetud, jääb üle minna üle uuele skeemile - ja eelistatavalt ilma, et kasutajad seda märkaksid.

Andmete migratsioon

Seega on meil tekstimootor, mis salvestab sõnumeid kasutajate kaupa, ja kaks klastrit vestlusliikmed ja liikmevestlused, mis salvestavad andmeid mitme jututubade ja neis olevate kasutajate kohta. Kuidas liikuda sellelt uuele kasutaja- ja vestlusmootorile?

Vana skeemi liikmevestlusi kasutati peamiselt optimeerimiseks. Edastasime sealt kiiresti vajalikud andmed chat-liikmetele ja seejärel ta enam migratsiooniprotsessis ei osalenud.

Järjekord vestlusliikmetele. See sisaldab 100 eksemplari, vestlusmootoril aga 4 tuhat. Andmete edastamiseks peate need vastavusse viima - selleks jagati vestlusliikmed samasse 4 tuhandesse eksemplari ja seejärel lubati vestlusmootoris vestlusliikmete binlogi lugemine.

Nüüd teab chat-mootor vestlusliikmete multivestlust, kuid ei tea veel midagi kahe vestluskaaslasega peetavast dialoogist. Sellised dialoogid asuvad tekstimootoris, viidates kasutajatele. Siin võtsime andmed otse ette: iga vestlusmootori eksemplar küsis kõigilt tekstimootori eksemplaridelt, kas neil on vajalik dialoog.

Suurepärane – vestlusmootor teab, millised multi-chat-vestlused on olemas, ja teab, millised dialoogid seal on.
Peate kombineerima sõnumid mitme vestlusega vestlustes, nii et saate igas vestluses kirjade loendi. Esiteks hangib vestlusmootor tekstimootorist kõik kasutajate sõnumid sellest vestlusest. Mõnel juhul on neid üsna palju (kuni sadu miljoneid), kuid väga harvade eranditega mahub vestlus täielikult RAM-i. Meil on järjestamata sõnumeid, millest igaüks on mitmes eksemplaris – lõppude lõpuks on need kõik võetud erinevatest kasutajatele vastavatest tekstimootori eksemplaridest. Eesmärk on sorteerida sõnumeid ja vabaneda koopiatest, mis võtavad tarbetult ruumi.

Igal sõnumil on ajatempel, mis sisaldab saatmisaega ja teksti. Kasutame aega sorteerimiseks – asetame viidad multivestluses osalejate vanimatele sõnumitele ja võrdleme kavandatavate koopiate tekstide räsi, liikudes ajatempli suurendamise suunas. On loogiline, et koopiatel on sama räsi ja ajatempel, kuid praktikas pole see alati nii. Nagu mäletate, viis vanas skeemis sünkroonimise läbi PHP - ja harvadel juhtudel oli sama sõnumi saatmise aeg erinevatel kasutajatel erinev. Sellistel juhtudel lubasime ajatemplit muuta – tavaliselt sekundi jooksul. Teine probleem on sõnumite erinev järjestus erinevatele adressaatidele. Sellistel juhtudel lubasime luua lisakoopia, millel on erinevatele kasutajatele erinevad tellimisvõimalused.

Pärast seda saadetakse andmed multivestluse sõnumite kohta kasutajamootorisse. Ja siit tuleb imporditud sõnumite ebameeldiv omadus. Tavatöös järjestatakse mootorisse saabuvad sõnumid kasutaja_kohalik_id järgi rangelt kasvavas järjekorras. Vanast mootorist kasutajamootorisse imporditud sõnumid kaotasid selle kasuliku omaduse. Samas peab testimise mugavuse huvides saama neile kiiresti ligi pääseda, sealt midagi otsida ja uusi lisada.

Imporditud sõnumite salvestamiseks kasutame spetsiaalset andmestruktuuri.

See tähistab suuruse vektorit kus kõik on - on erinevad ja järjestatud kahanevas järjekorras, elementide erijärjekorraga. Igas segmendis koos indeksitega elemendid on sorteeritud. Sellises struktuuris elemendi otsimine võtab aega läbi binaarsed otsingud. Elemendi lisandumine amortiseeritakse üle .

Niisiis, mõtlesime välja, kuidas andmeid vanadelt mootoritelt uutele üle kanda. Kuid see protsess võtab mitu päeva – ja on ebatõenäoline, et nende päevade jooksul meie kasutajad üksteisele kirjutamise harjumusest loobuksid. Et selle aja jooksul sõnumeid mitte kaotada, läheme üle tööskeemile, mis kasutab nii vanu kui ka uusi klastreid.

Andmed kirjutatakse vestlusliikmetele ja kasutajamootorisse (ja mitte tekstimootorisse, nagu vana skeemi järgi tavatöös). user-engine puhverdab taotluse chat-mootorile – ja siin sõltub käitumine sellest, kas see vestlus on juba liidetud või mitte. Kui vestlust pole veel liidetud, ei kirjuta vestlusmootor sõnumit endale ja selle töötlemine toimub ainult tekstimootoris. Kui vestlus on juba vestlusmootoriga liidetud, tagastab see kasutajamootorile chat_local_id ja saadab sõnumi kõigile adressaatidele. user-engine puhverdab kõik andmed tekstimootorisse – nii et kui midagi juhtub, saame alati tagasi kerida, kuna kõik praegused andmed on vanas mootoris. text-engine tagastab user_local_id, mille kasutajamootor salvestab ja naaseb taustaprogrammi.

Selle tulemusena näeb üleminekuprotsess välja järgmine: ühendame tühjad kasutaja-mootori ja vestlusmootori klastrid. chat-mootor loeb kogu vestlusliikmete binlogi, seejärel algab puhverserver vastavalt ülalkirjeldatud skeemile. Edastame vanad andmed ja saame kaks sünkroniseeritud klastrit (vana ja uus). Jääb vaid lülitada lugemine tekstimootorilt kasutajamootorile ja keelata puhverserver.

Järeldused

Tänu uuele lähenemisele on täiustatud mootorite kõiki jõudlusnäitajaid ja lahendatud probleemid andmete järjepidevusega. Nüüd saame sõnumitesse kiiresti uusi funktsioone juurutada (ja oleme seda juba tegema hakanud – suurendasime vestluses osalejate maksimaalset arvu, rakendasime edasisaadetud sõnumite otsingu, käivitasime kinnitatud sõnumid ja tõstsime kasutaja kohta sõnumite koguarvu limiiti) .

Muutused loogikas on tõesti tohutud. Ja ma tahaksin märkida, et see ei tähenda alati terveid aastaid tohutu meeskonna arendustööd ja lugematuid koodiridu. vestlusmootor ja kasutajamootor koos kõigi lisalugudega, nagu Huffman sõnumite tihendamiseks, esituspuud ja imporditud sõnumite struktuur, on alla 20 tuhande koodirea. Ja need kirjutasid 3 arendajat vaid 10 kuuga (tasub aga meeles pidada, et kõik kolm arendaja - maailmameistrid spordiprogrammides).

Veelgi enam, serverite arvu kahekordistamise asemel vähendasime nende arvu poole võrra – nüüd töötavad kasutaja- ja vestlusmootor 500 füüsilisel masinal, samas kui uuel skeemil on palju koormust. Säästsime palju raha seadmete pealt – umbes 5 miljonit dollarit + 750 tuhat dollarit aastas tegevuskuludelt.

Püüame leida parimaid lahendusi kõige keerukamatele ja suuremahulistele probleemidele. Meil on neid palju – seepärast otsime andmebaasiosakonda andekaid arendajaid. Kui Sulle meeldib ja oskad selliseid probleeme lahendada, tunned suurepäraselt algoritme ja andmestruktuurisid, kutsume Sind meeskonnaga liituma. Võtke meiega ühendust HRüksikasjade saamiseks.

Isegi kui see lugu ei puuduta teid, pange tähele, et hindame soovitusi. Räägi sellest sõbrale arendaja vabad töökohad, ja kui ta katseaja edukalt läbib, saate boonust 100 tuhat rubla.

Allikas: www.habr.com