Reverku la mesaĝan datumbazon de VKontakte de nulo kaj pluvivu

Niaj uzantoj skribas mesaĝojn unu al la alia sen scii lacecon.

Tio estas sufiĉe multe. Se vi komencus legi ĉiujn mesaĝojn de ĉiuj uzantoj, ĝi bezonus pli ol 150 mil jarojn. Kondiĉe ke vi estas sufiĉe progresinta leganto kaj elspezu ne pli ol sekundon por ĉiu mesaĝo.

Kun tia volumo de datumoj, estas kritike, ke la logiko por konservi kaj aliri ĝin estas konstruita optimume. Alie, en unu ne tiom mirinda momento, eble evidentiĝos, ke ĉio baldaŭ misfunkcios.

Por ni, ĉi tiu momento venis antaŭ jaro kaj duono. Kiel ni venis al ĉi tio kaj kio okazis finfine - ni rakontas al vi en ordo.

Fono

En la unua efektivigo, VKontakte-mesaĝoj funkciis sur kombinaĵo de PHP-backend kaj MySQL. Ĉi tio estas tute normala solvo por malgranda studenta retejo. Tamen, ĉi tiu retejo kreskis neregeble kaj komencis postuli optimumigo de datumstrukturoj por si mem.

Fine de 2009, la unua tekst-motora deponejo estis verkita, kaj en 2010 mesaĝoj estis transdonitaj al ĝi.

En la tekstmaŝino, mesaĝoj estis konservitaj en listoj - speco de "leterkestoj". Ĉiu tia listo estas determinita de uid - la uzanto kiu posedas ĉiujn ĉi mesaĝojn. Mesaĝo havas aron da atributoj: identigilo de interparolanto, teksto, aldonaĵoj ktp. La mesaĝo-identigilo ene de la "kesto" estas local_id, ĝi neniam ŝanĝiĝas kaj estas asignita sinsekve por novaj mesaĝoj. La "kestoj" estas sendependaj kaj ne estas sinkronigitaj unu kun la alia ene de la motoro; komunikado inter ili okazas ĉe la PHP-nivelo. Vi povas rigardi la datumstrukturon kaj kapablojn de teksta motoro de interne tie.

Tio sufiĉis por korespondado inter du uzantoj. Divenu, kio okazis poste?

En majo 2011, VKontakte enkondukis konversaciojn kun pluraj partoprenantoj — plurbabilado. Por labori kun ili, ni kreis du novajn aretojn - membro-babilejojn kaj babil-membrojn. La unua konservas datumojn pri babilejoj de uzantoj, la dua konservas datumojn pri uzantoj per babilejoj. Krom la listoj mem, ĉi tio inkluzivas, ekzemple, la invitan uzanton kaj la tempon kiam ili estis aldonitaj al la babilejo.

"PHP, ni sendu mesaĝon al la babilejo," diras la uzanto.
"Venu, {uzantnomo}," diras PHP.

Estas malavantaĝoj al ĉi tiu skemo. Sinkronigo daŭre estas la respondeco de PHP. Grandaj babilejoj kaj uzantoj, kiuj samtempe sendas mesaĝojn al ili, estas danĝera rakonto. Ĉar la tekstmotora petskribo dependas de la uid, babilejpartoprenantoj povus ricevi la saman mesaĝon en malsamaj tempoj. Oni povus vivi kun tio, se la progreso haltus. Sed tio ne okazos.

Fine de 2015, ni lanĉis komunumajn mesaĝojn, kaj komence de 2016, ni lanĉis API por ili. Kun la apero de grandaj babilrotoj en komunumoj, eblis forgesi eĉ pri distribuo de ŝarĝo.

Bona bot generas plurajn milionojn da mesaĝoj ĉiutage - eĉ la plej parolemaj uzantoj ne povas fanfaroni pri tio. Ĉi tio signifas, ke iuj okazoj de tekstmaŝino, sur kiuj vivis tiaj robotoj, komencis plene suferi.

Mesaĝmotoroj en 2016 estas 100 okazoj de babilej-membroj kaj membro-babiloj, kaj 8000 tekst-motoroj. Ili estis gastigitaj sur mil serviloj, ĉiu kun 64 GB da memoro. Kiel unua kriz-rimedo, ni pliigis la memoron je pliaj 32 GB. Ni taksis la antaŭvidojn. Sen drastaj ŝanĝoj, ĉi tio sufiĉus por proksimume alia jaro. Vi devas aŭ akiri aparataron aŭ optimumigi la datumbazojn mem.

Pro la naturo de la arkitekturo, ĝi nur havas sencon pliigi aparataron en multobloj. Tio estas, almenaŭ duobligi la nombron da aŭtoj - evidente, ĉi tio estas sufiĉe multekosta vojo. Ni optimumigos.

Nova koncepto

La centra esenco de la nova aliro estas babilejo. Babilejo havas liston de mesaĝoj kiuj rilatas al ĝi. La uzanto havas liston de babilejoj.

La bezonata minimumo estas du novaj datumbazoj:

• babil-motoro. Ĉi tio estas deponejo de babilvektoroj. Ĉiu babilejo havas vektoron de mesaĝoj kiuj rilatas al ĝi. Ĉiu mesaĝo havas tekston kaj unikan mesaĝon ene de la babilejo - chat_local_id.
• uzant-motoro. Ĉi tio estas stokado de uzantvektoroj - ligiloj al uzantoj. Ĉiu uzanto havas vektoron de peer_id (interparolantoj - aliaj uzantoj, plurbabilejo aŭ komunumoj) kaj vektoro de mesaĝoj. Ĉiu peer_id havas vektoron de mesaĝoj kiuj rilatas al ĝi. Ĉiu mesaĝo havas chat_local_id kaj unikan mesaĝan ID por tiu uzanto - user_local_id.

Novaj aretoj komunikas inter si per TCP - tio certigas, ke la ordo de petoj ne ŝanĝiĝas. La petoj mem kaj konfirmoj por ili estas registritaj sur la malmola disko - do ni povas restarigi la staton de la vosto en ajna momento post malsukceso aŭ rekomenco de la motoro. Ĉar la uzant-motoro kaj babilejo-motoro estas po 4 mil fragmentoj, la petovico inter la aretoj estos distribuita egale (sed fakte tute ne ekzistas - kaj ĝi funkcias tre rapide).

Labori kun disko en niaj datumbazoj en la plej multaj kazoj baziĝas sur kombinaĵo de binara protokolo de ŝanĝoj (binlog), statikaj momentfotoj kaj parta bildo en memoro. Ŝanĝoj dumtage estas skribitaj al binlog, kaj momentfoto de la nuna stato estas periode kreita. Momentfoto estas kolekto de datumstrukturoj optimumigitaj por niaj celoj. Ĝi konsistas el kaplinio (metaindekso de la bildo) kaj aro de metadosieroj. La kaplinio estas konstante konservita en RAM kaj indikas kie serĉi datumojn de la momentfoto. Ĉiu metadosiero inkluzivas datumojn, kiuj verŝajne estos bezonataj en proksimaj tempoj—ekzemple, rilataj al ununura uzanto. Kiam vi pridemandas la datumbazon per la kaplinio de momentfoto, la bezonata metadosiero estas legita, kaj tiam ŝanĝoj en la binlog kiu okazis post kiam la momentfoto estis kreita estas enkalkulitaj. Vi povas legi pli pri la avantaĝoj de ĉi tiu aliro tie.

Samtempe, la datumoj sur la malmola disko mem ŝanĝiĝas nur unufoje tage - malfrue en la nokto en Moskvo, kiam la ŝarĝo estas minimuma. Dank'al ĉi tio (sciante, ke la strukturo sur la disko estas konstanta dum la tuta tago), ni povas pagi anstataŭigi vektorojn per tabeloj de fiksa grandeco - kaj pro tio gajni memoron.

Sendi mesaĝon en la nova skemo aspektas jene:

1. La PHP-backend kontaktas la uzanto-motoron kun peto sendi mesaĝon.
2. user-engine prokuras la peton al la dezirata babilejo-motoro, kiu revenas al user-engine chat_local_id - unika identigilo de nova mesaĝo ene de ĉi tiu babilejo. La chat_engine tiam dissendas la mesaĝon al ĉiuj ricevantoj en la babilejo.
3. user-engine ricevas chat_local_id de chat-engine kaj resendas user_local_id al PHP - unika mesaĝo-identigilo por ĉi tiu uzanto. Ĉi tiu identigilo tiam estas uzata, ekzemple, por labori kun mesaĝoj per la API.

Sed krom vere sendi mesaĝojn, vi devas efektivigi kelkajn pli gravajn aferojn:

• Sublistoj estas, ekzemple, la plej lastatempaj mesaĝoj, kiujn vi vidas kiam vi malfermas la konversacian liston. Nelegitaj mesaĝoj, mesaĝoj kun etikedoj ("Grava", "Spamo", ktp.).
• Kunpremante mesaĝojn en babilejo-motoro
• Kaŝmemoro de mesaĝoj en uzantmotoro
• Serĉu (tra ĉiuj dialogoj kaj ene de unu specifa).
• Realtempa ĝisdatigo (Longvolling).
• Konservado de historio por efektivigi kaŝmemoron ĉe poŝtelefonaj klientoj.

Ĉiuj sublistoj rapide ŝanĝas strukturojn. Por labori kun ili ni uzas Splay arboj. Ĉi tiu elekto estas klarigita per tio, ke ĉe la supro de la arbo ni foje stokas tutan segmenton de mesaĝoj de momentfoto - ekzemple, post nokta reindeksado, la arbo konsistas el unu supro, kiu enhavas ĉiujn mesaĝojn de la sublisto. La Splay-arbo faciligas enmeti en la mezon de tia vertico sen devi pensi pri ekvilibro. Krome, Splay ne stokas nenecesajn datumojn, kio ŝparas al ni memoron.

Mesaĝoj implikas grandan kvanton da informoj, plejparte teksto, kiu estas utila por povi kunpremi. Gravas, ke ni povas precize malarkivi eĉ unu individuan mesaĝon. Uzita por kunpremi mesaĝojn Huffman-algoritmo kun nia propra heŭristiko - ekzemple, ni scias, ke en mesaĝoj vortoj alternas kun "ne-vortoj" - spacoj, interpunkciaj signoj - kaj ni memoras ankaŭ kelkajn el la trajtoj de uzado de simboloj por la rusa lingvo.

Ĉar estas multe malpli da uzantoj ol babilejoj, por konservi hazard-alirajn diskpetojn en babil-motoro, ni konservas mesaĝojn en uzantmotoro.

Mesaĝserĉo estas efektivigita kiel diagonala demando de uzantmotoro al ĉiuj babilmotorokazoj kiuj enhavas babilojn de ĉi tiu uzanto. La rezultoj estas kombinitaj en la uzanto-motoro mem.

Nu, ĉiuj detaloj estas enkalkulitaj, restas nur ŝanĝi al nova skemo - kaj prefere sen ke uzantoj rimarku ĝin.

Migrado de datumoj

Do, ni havas tekst-motoron, kiu stokas mesaĝojn de uzanto, kaj du aretojn de babilanoj kaj membro-babilejoj, kiuj konservas datumojn pri multbabilejoj kaj la uzantoj en ili. Kiel movi de ĉi tio al la nova uzant-motoro kaj babilejo-motoro?

membro-babiloj en la malnova skemo estis uzata ĉefe por optimumigo. Ni rapide transdonis la necesajn datumojn de ĝi al babilanoj, kaj tiam ĝi ne plu partoprenis en la migrada procezo.

Vico por babilanoj. Ĝi inkluzivas 100 petskribojn, dum babil-motoro havas 4 mil. Por transdoni la datumojn, vi devas plenumi ĝin - por tio, babilanoj estis dividitaj en la samajn 4 mil ekzemplerojn, kaj tiam la legado de la retbabilejo-membroj estis ebligita en la babilejo-motoro.

Nun babil-motoro scias pri plurbabilado de babilanoj, sed ĝi ankoraŭ nenion scias pri dialogoj kun du interparolantoj. Tiaj dialogoj troviĝas en la tekstmaŝino rilate al uzantoj. Ĉi tie ni prenis la datumojn "fronte": ĉiu babil-motora petskribo demandis ĉiujn tekst-motorajn petskribojn ĉu ili havas la dialogon, kiun ĝi bezonas.

Bonege - babilejo-motoro scias kiaj plurbabilaj babilejoj ekzistas kaj scias kiaj dialogoj ekzistas.
Vi devas kombini mesaĝojn en multbabilaj babilejoj por ke vi alvenu kun listo de mesaĝoj en ĉiu babilejo. Unue, babilejo-motoro prenas de tekst-motoro ĉiujn uzantmesaĝojn de ĉi tiu babilejo. En iuj kazoj estas sufiĉe multaj (ĝis centoj da milionoj), sed kun tre maloftaj esceptoj la babilejo tute taŭgas en RAM. Ni havas neordigitajn mesaĝojn, ĉiu en pluraj kopioj - post ĉio, ili ĉiuj estas eltiritaj de malsamaj tekst-motoraj okazoj respondaj al uzantoj. La celo estas ordigi mesaĝojn kaj forigi kopiojn, kiuj okupas nenecesan spacon.

Ĉiu mesaĝo havas tempomarkon enhavantan la tempon kiam ĝi estis sendita kaj tekston. Ni uzas tempon por ordigo - ni metas montrilojn al la plej malnovaj mesaĝoj de plurbabilaj partoprenantoj kaj komparas haŝojn de la teksto de la celitaj kopioj, moviĝante al pliiĝanta tempostampo. Estas logike, ke la kopioj havos la saman hash kaj tempostampon, sed praktike tio ne ĉiam okazas. Kiel vi memoras, sinkronigado en la malnova skemo estis farita de PHP - kaj en maloftaj kazoj, la tempo por sendi la saman mesaĝon malsamis inter malsamaj uzantoj. En ĉi tiuj kazoj, ni permesis al ni redakti la tempomarkon - kutime ene de sekundo. La dua problemo estas la malsama ordo de mesaĝoj por malsamaj ricevantoj. En tiaj kazoj, ni permesis krei kroman kopion, kun malsamaj mendaj opcioj por malsamaj uzantoj.

Post tio, datumoj pri mesaĝoj en multibabilejo estas senditaj al la uzantmotoro. Kaj jen venas malagrabla trajto de importitaj mesaĝoj. En normala funkciado, mesaĝoj, kiuj venas al la motoro, estas ordonitaj strikte en kreskanta ordo per user_local_id. Mesaĝoj importitaj de la malnova motoro en la uzantmotoron perdis ĉi tiun utilan posedaĵon. Samtempe, por la komforto de testado, vi devas rapide aliri ilin, serĉi ion en ili kaj aldoni novajn.

Ni uzas specialan datumstrukturon por stoki importitajn mesaĝojn.

Ĝi reprezentas vektoron de grandeco kie estas ĉiuj - estas malsamaj kaj ordigitaj en malkreskanta ordo, kun speciala ordo de elementoj. En ĉiu segmento kun indeksoj elementoj estas ordigitaj. Serĉi elementon en tia strukturo prenas tempon tra binaraj serĉoj. La aldono de elemento estas amortizita super .

Do, ni eksciis kiel transdoni datumojn de malnovaj motoroj al novaj. Sed ĉi tiu procezo daŭras plurajn tagojn - kaj estas neverŝajne ke dum ĉi tiuj tagoj niaj uzantoj rezignu la kutimon skribi unu al la alia. Por ne perdi mesaĝojn dum ĉi tiu tempo, ni ŝanĝas al laborskemo kiu uzas kaj malnovajn kaj novajn aretojn.

Datumoj estas skribitaj al babilanoj kaj uzantmotoro (kaj ne al tekstmotoro, kiel en normala funkciado laŭ la malnova skemo). user-engine transdonas la peton al chat-engine - kaj ĉi tie la konduto dependas de ĉu ĉi tiu babilejo jam estas kunfandita aŭ ne. Se la babilejo ankoraŭ ne estas kunfandita, la babilejo ne skribas la mesaĝon al si mem, kaj ĝia prilaborado okazas nur en la teksta motoro. Se la babilejo jam estis kunfandita en babilejon, ĝi resendas chat_local_id al user-engine kaj sendas la mesaĝon al ĉiuj ricevantoj. uzant-motoro transdonas ĉiujn datumojn al tekst-motoro - tiel ke se io okazas, ni ĉiam povas reveni, havante ĉiujn aktualajn datumojn en la malnova motoro. text-engine resendas user_local_id, kiun uzantmotoro konservas kaj revenas al la backend.

Kiel rezulto, la transira procezo aspektas jene: ni konektas malplenajn uzant-motorojn kaj babil-motorajn aretojn. babilejo-motoro legas la tutan retbabilejo-membrojn binlog, tiam prokurado komenciĝas laŭ la skemo priskribita supre. Ni translokigas la malnovajn datumojn kaj ricevas du sinkronigitajn aretojn (malnovaj kaj novaj). Restas nur ŝanĝi legadon de teksto-motoro al uzantmotoro kaj malŝalti prokuradon.

Результаты

Dank'al la nova aliro, ĉiuj agado-metrikoj de la motoroj estis plibonigitaj kaj problemoj kun datuma konsistenco estis solvitaj. Nun ni povas rapide efektivigi novajn funkciojn en mesaĝoj (kaj jam komencis fari tion - ni pliigis la maksimuman nombron da babilaj partoprenantoj, efektivigis serĉon por plusenditaj mesaĝoj, lanĉis alpinglitajn mesaĝojn kaj altigis la limon de la totala nombro da mesaĝoj por uzanto) .

La ŝanĝoj en logiko estas vere enormaj. Kaj mi ŝatus rimarki, ke ĉi tio ne ĉiam signifas tutajn jarojn da evoluo de grandega teamo kaj miriadoj da linioj de kodo. babilejo-motoro kaj uzantmotoro kune kun ĉiuj pliaj rakontoj kiel Huffman por mesaĝkunpremo, Splay-arboj kaj strukturo por importitaj mesaĝoj estas malpli ol 20 mil linioj de kodo. Kaj ili estis verkitaj de 3 programistoj en nur 10 monatoj (tamen indas konsideri, ke ĉiuj tri ellaboranto - mondĉampionoj en sporta programado).

Krome, anstataŭ duobligi la nombron da serviloj, ni reduktis ilian nombron je duono - nun la uzant-motoro kaj babilejo-motoro vivas sur 500 fizikaj maŝinoj, dum la nova skemo havas grandan kapspacon por ŝarĝo. Ni ŝparis multe da mono sur ekipaĵo - ĉirkaŭ $ 5 milionoj + $ 750 mil jare en operaciaj elspezoj.

Ni strebas trovi la plej bonajn solvojn por la plej kompleksaj kaj grandskalaj problemoj. Ni havas multe da ili - kaj tial ni serĉas talentajn programistojn en la datumbaza fako. Se vi amas kaj scias kiel solvi tiajn problemojn, havas bonegan scion pri algoritmoj kaj datumstrukturoj, ni invitas vin aliĝi al la teamo. Kontaktu nian HRpor detaloj.

Eĉ se ĉi tiu rakonto ne temas pri vi, bonvolu noti, ke ni taksas rekomendojn. Rakontu al amiko pri vakantaĵoj por programistoj, kaj se li sukcese finos la provperiodon, vi ricevos gratifikon de 100 mil rubloj.

fonto: www.habr.com