Naši uporabniki si pišejo sporočila, ne da bi se zavedali utrujenosti.
To je kar veliko. Če bi se lotili branja vseh sporočil vseh uporabnikov, bi trajalo več kot 150 tisoč let. Pod pogojem, da ste dokaj napreden bralec in za vsako sporočilo ne porabite več kot sekundo.
Pri takšnem obsegu podatkov je ključnega pomena, da je logika shranjevanja in dostopa do njih zgrajena optimalno. V nasprotnem primeru lahko v enem ne tako čudovitem trenutku postane jasno, da bo kmalu šlo vse narobe.
Za nas je ta trenutek prišel pred letom in pol. Kako smo prišli do tega in kaj se je zgodilo na koncu - vam povemo po vrsti.
zgodovina primer
V prvi izvedbi so sporočila VKontakte delovala na kombinaciji zaledja PHP in MySQL. To je povsem običajna rešitev za majhno študentsko spletno stran. Vendar je to spletno mesto nenadzorovano raslo in začelo zahtevati optimizacijo podatkovnih struktur zase.
Konec leta 2009 je bil napisan prvi tekstovni repozitorij, leta 2010 pa so bila vanj prenesena sporočila.
V besedilnem stroju so bila sporočila shranjena na seznamih - nekakšnih "nabiralnikih". Vsak tak seznam določa uid - uporabnik, ki je lastnik vseh teh sporočil. Sporočilo ima niz atributov: identifikator sogovornika, besedilo, priloge itd. Identifikator sporočila znotraj »polja« je local_id, nikoli se ne spremeni in se za nova sporočila dodeli zaporedno. "Škatle" so neodvisne in niso sinhronizirane med seboj znotraj motorja; komunikacija med njimi poteka na ravni PHP. Podatkovno strukturo in zmožnosti besedilnega mehanizma si lahko ogledate od znotraj .
To je bilo povsem dovolj za dopisovanje med dvema uporabnikoma. Uganete, kaj se je zgodilo potem?
Maja 2011 je VKontakte uvedel pogovore z več udeleženci - multi-chat. Da bi sodelovali z njimi, smo ustvarili dva nova grozda - članske klepete in klepetalnice. Prvi hrani podatke o klepetih po uporabnikih, drugi pa podatke o uporabnikih po klepetih. Poleg samih seznamov to vključuje na primer uporabnika, ki vabi, in čas, ko je bil dodan v klepet.
"PHP, pošljimo sporočilo v klepet," pravi uporabnik.
»Daj no, {uporabniško ime},« pravi PHP.
Ta shema ima slabosti. Za sinhronizacijo je še vedno odgovoren PHP. Veliki klepeti in uporabniki, ki jim hkrati pošiljajo sporočila, so nevarna zgodba. Ker je primerek besedilnega mehanizma odvisen od uid-ja, lahko udeleženci klepeta prejmejo isto sporočilo ob različnih časih. S tem bi lahko živeli, če bi se napredek ustavil. Ampak to se ne bo zgodilo.
Konec leta 2015 smo lansirali sporočila skupnosti, v začetku leta 2016 pa API zanje. S pojavom velikih chatbotov v skupnostih je bilo mogoče pozabiti na enakomerno porazdelitev obremenitve.
Dober bot ustvari več milijonov sporočil na dan - s tem se ne morejo pohvaliti niti najbolj zgovorni uporabniki. To pomeni, da so nekateri primerki besedilnega motorja, na katerem so takšni boti živeli, začeli v največji meri trpeti.
Motorji za sporočila v letu 2016 so 100 primerkov klepetalnikov in članskih klepetov ter 8000 besedilnih mehanizmov. Gostovali so na tisoč strežnikih, vsak s 64 GB pomnilnika. Kot prvi nujni ukrep smo povečali pomnilnik še za 32 GB. Ocenili smo napovedi. Brez drastičnih sprememb bi to zadostovalo še za kakšno leto. Pridobiti morate strojno opremo ali optimizirati same baze podatkov.
Zaradi narave arhitekture je strojno opremo smiselno povečati le v večkratnikih. To je vsaj podvojitev števila avtomobilov - očitno je to precej draga pot. Optimizirali bomo.
Nov koncept
Osrednje bistvo novega pristopa je klepet. Klepet ima seznam sporočil, ki se nanašajo nanj. Uporabnik ima seznam klepetov.
Zahtevani minimum sta dve novi bazi podatkov:
- klepetalnica. To je skladišče vektorjev za klepet. Vsak klepet ima vektor sporočil, ki se nanašajo nanj. Vsako sporočilo ima besedilo in edinstven identifikator sporočila znotraj klepeta - chat_local_id.
- uporabniški motor. To je shramba uporabniških vektorjev – povezav do uporabnikov. Vsak uporabnik ima vektor peer_id (sogovorniki - drugi uporabniki, multi-chat ali skupnosti) in vektor sporočil. Vsak peer_id ima vektor sporočil, ki se nanašajo nanj. Vsako sporočilo ima chat_local_id in edinstven ID sporočila za tega uporabnika - user_local_id.
Nove gruče med seboj komunicirajo s pomočjo TCP - to zagotavlja, da se vrstni red zahtev ne spremeni. Same zahteve in potrditve zanje so zabeležene na trdem disku - tako lahko kadarkoli po okvari ali ponovnem zagonu motorja obnovimo stanje čakalne vrste. Ker sta uporabniški in klepetalni motor po 4 tisoč drobcev, bo čakalna vrsta zahtev enakomerno porazdeljena med grozdi (v resnici pa je sploh ni - in deluje zelo hitro).
Delo z diskom v naših bazah podatkov v večini primerov temelji na kombinaciji binarnega dnevnika sprememb (binlog), statičnih posnetkov in delne slike v pomnilniku. Spremembe čez dan se zapišejo v binlog, občasno pa se ustvari posnetek trenutnega stanja. Posnetek je zbirka podatkovnih struktur, optimiziranih za naše namene. Sestavljen je iz glave (metaindeksa slike) in niza metadatotek. Glava je trajno shranjena v RAM-u in označuje, kje iskati podatke iz posnetka. Vsaka metadatoteka vključuje podatke, ki bodo verjetno potrebni v bližnjih časovnih točkah – na primer v zvezi z enim uporabnikom. Ko poizvedujete po zbirki podatkov z glavo posnetka, se zahtevana metadatoteka prebere, nato pa se upoštevajo spremembe v binlogu, do katerih je prišlo po ustvarjanju posnetka. Več o prednostih tega pristopa lahko preberete .
Hkrati se podatki na samem trdem disku spremenijo le enkrat na dan - pozno zvečer v Moskvi, ko je obremenitev minimalna. Zahvaljujoč temu (ob zavedanju, da je struktura na disku ves dan konstantna) si lahko privoščimo zamenjavo vektorjev z nizi fiksne velikosti - in s tem pridobimo na pomnilniku.
Pošiljanje sporočila v novi shemi izgleda takole:
- Zaledje PHP stopi v stik z uporabniškim motorjem z zahtevo za pošiljanje sporočila.
- uporabniški motor posreduje zahtevo želenemu primerku klepetalnega mehanizma, ki se vrne v uporabniški motor chat_local_id – edinstven identifikator novega sporočila v tem klepetu. Chat_engine nato odda sporočilo vsem prejemnikom v klepetu.
- uporabniški motor prejme chat_local_id od chat-engine in PHP vrne user_local_id – edinstven identifikator sporočila za tega uporabnika. Ta identifikator se nato uporabi na primer za delo s sporočili prek API-ja.
Toda poleg dejanskega pošiljanja sporočil morate implementirati še nekaj pomembnih stvari:
- Podseznami so na primer najnovejša sporočila, ki jih vidite, ko odprete seznam pogovorov. Neprebrana sporočila, sporočila z oznakami (»pomembno«, »neželena pošta« itd.).
- Stiskanje sporočil v klepetalnici
- Predpomnjenje sporočil v uporabniškem motorju
- Iskanje (skozi vsa pogovorna okna in znotraj določenega).
- Posodobitev v realnem času (Longpolling).
- Shranjevanje zgodovine za izvajanje predpomnjenja na mobilnih odjemalcih.
Vsi podseznami imajo hitro spreminjajočo se strukturo. Za delo z njimi uporabljamo . Ta izbira je razložena z dejstvom, da na vrhu drevesa včasih shranimo cel segment sporočil iz posnetka - na primer, po nočnem ponovnem indeksiranju je drevo sestavljeno iz enega vrha, ki vsebuje vsa sporočila podseznama. Drevo Splay omogoča preprosto vstavljanje v sredino takega vrha, ne da bi morali razmišljati o uravnoteženju. Poleg tega Splay ne shranjuje nepotrebnih podatkov, kar nam prihrani spomin.
Sporočila vključujejo veliko količino informacij, večinoma besedila, ki jih je koristno stisniti. Pomembno je, da lahko natančno dearhiviramo celo posamezno sporočilo. Uporablja se za stiskanje sporočil z lastno hevristiko - na primer vemo, da se v sporočilih besede izmenjujejo z "ne-besedami" - presledki, ločila - in spomnimo se tudi nekaterih značilnosti uporabe simbolov za ruski jezik.
Ker je uporabnikov veliko manj kot klepetalnikov, za shranjevanje diskovnih zahtev z naključnim dostopom v klepetalni mehanizem sporočila predpomnimo v uporabniškem motorju.
Iskanje sporočil je implementirano kot diagonalna poizvedba od uporabniškega mehanizma do vseh primerkov klepetalnega mehanizma, ki vsebujejo klepete tega uporabnika. Rezultati so združeni v samem uporabniškem motorju.
No, vse podrobnosti so bile upoštevane, preostane le prehod na novo shemo - in po možnosti ne da bi uporabniki to opazili.
Selitev podatkov
Imamo torej besedilni mehanizem, ki shranjuje sporočila po uporabnikih, in dve gruči chat-members in member-chats, ki shranjujeta podatke o večklepetalnicah in uporabnikih v njih. Kako preiti s tega na nov uporabniški in klepetalni motor?
članski klepet v stari shemi je bil uporabljen predvsem za optimizacijo. Hitro smo iz njega prenesli potrebne podatke članom klepetalnic, nato pa ni več sodeloval v procesu migracije.
Čakalna vrsta za člane klepeta. Vključuje 100 primerkov, medtem ko jih ima chat-engine 4 tisoč. Če želite prenesti podatke, jih morate uskladiti - za to so bili člani klepeta razdeljeni v enakih 4 tisoč kopij, nato pa je bilo v klepetalnici omogočeno branje binloga članov klepeta.
Zdaj klepetalnica ve za več klepetov članov klepeta, vendar še ne ve ničesar o dialogih z dvema sogovornikoma. Takšni dialogi se nahajajo v besedilnem mehanizmu glede na uporabnike. Tu smo podatke vzeli neposredno: vsak primerek mehanizma za klepet je vprašal vse primerke mehanizma za besedilo, ali imajo dialog, ki ga potrebuje.
Odlično – klepetalnica ve, kateri klepeti z več klepeti obstajajo, in ve, kateri dialogi obstajajo.
Sporočila v klepetih z več klepeti morate združiti tako, da boste na koncu imeli seznam sporočil v vsakem klepetu. Najprej klepetalni mehanizem iz besedilnega mehanizma pridobi vsa uporabniška sporočila iz tega klepeta. V nekaterih primerih jih je precej (do sto milijonov), toda z zelo redkimi izjemami se klepet v celoti prilega RAM-u. Imamo neurejena sporočila, vsako v več izvodih - navsezadnje so vsa potegnjena iz različnih primerkov besedilnih mehanizmov, ki ustrezajo uporabnikom. Cilj je razvrstiti sporočila in se znebiti kopij, ki zasedajo nepotreben prostor.
Vsako sporočilo ima časovni žig, ki vsebuje čas pošiljanja in besedilo. Čas uporabljamo za razvrščanje - postavljamo kazalce na najstarejša sporočila udeležencev multichata in primerjamo zgoščene vrednosti iz besedila predvidenih kopij, pri čemer se premikamo proti naraščajočemu časovnemu žigu. Logično je, da bodo imele kopije enak hash in časovni žig, vendar v praksi ni vedno tako. Kot se spomnite, je sinhronizacijo v stari shemi izvajal PHP - in v redkih primerih se je čas pošiljanja istega sporočila med različnimi uporabniki razlikoval. V teh primerih smo si dovolili urediti časovni žig – običajno v eni sekundi. Druga težava je različen vrstni red sporočil za različne prejemnike. V takih primerih smo omogočili ustvarjanje dodatne kopije z različnimi možnostmi naročanja za različne uporabnike.
Po tem se podatki o sporočilih v multichatu pošljejo uporabniškemu motorju. In tu se pojavi neprijetna lastnost uvoženih sporočil. Pri normalnem delovanju so sporočila, ki pridejo v motor, razvrščena strogo v naraščajočem vrstnem redu glede na user_local_id. Sporočila, uvožena iz starega motorja v uporabniški motor, so izgubila to koristno lastnost. Hkrati morate za udobje testiranja imeti možnost hitrega dostopa do njih, iskati nekaj v njih in dodati nove.
Za shranjevanje uvoženih sporočil uporabljamo posebno podatkovno strukturo.
Predstavlja vektor velikosti kje so vsi - so različni in razvrščeni v padajočem vrstnem redu, s posebnim vrstnim redom elementov. V vsakem segmentu z indeksi elementi so razvrščeni. Iskanje elementa v takšni strukturi zahteva čas prek binarna iskanja. Dodatek elementa se amortizira .
Tako smo ugotovili, kako prenesti podatke iz starih motorjev v nove. Toda ta proces traja več dni - in malo verjetno je, da bodo v teh dneh naši uporabniki opustili navado pisanja drug drugemu. Da v tem času ne izgubimo sporočil, preklopimo na delovno shemo, ki uporablja stare in nove gruče.
Podatki se pišejo članom klepeta in uporabniškemu mehanizmu (in ne besedilnemu mehanizmu, kot pri normalnem delovanju po stari shemi). uporabniški motor posreduje zahtevo klepetalnemu motorju - in tukaj je vedenje odvisno od tega, ali je bil ta klepet že združen ali ne. Če klepet še ni bil združen, klepetalni mehanizem ne napiše sporočila sam sebi in njegova obdelava poteka samo v besedilnem mehanizmu. Če je bil klepet že združen v klepetalni mehanizem, vrne chat_local_id uporabniškemu motorju in pošlje sporočilo vsem prejemnikom. uporabniški motor posreduje vse podatke tekstovnemu motorju - tako da se lahko, če se kaj zgodi, vedno vrnemo nazaj in imamo vse trenutne podatke v starem motorju. text-engine vrne user_local_id, ki ga user-engine shrani in vrne v zaledje.
Posledično je postopek prehoda videti takole: povežemo prazne gruče user-engine in chat-engine. klepetalnica prebere celoten binlog članov klepeta, nato se proxy začne v skladu z zgoraj opisano shemo. Prenesemo stare podatke in dobimo dva sinhronizirana grozda (starega in novega). Vse, kar ostane, je, da preklopite branje z besedilnega mehanizma na uporabniški motor in onemogočite proxy.
Ugotovitve
Zahvaljujoč novemu pristopu so bile izboljšane vse metrike delovanja motorjev in odpravljene težave z doslednostjo podatkov. Zdaj lahko hitro implementiramo nove funkcije v sporočila (in to smo že začeli početi - povečali smo največje število udeležencev klepeta, uvedli iskanje po posredovanih sporočilih, zagnali pripeta sporočila in dvignili omejitev skupnega števila sporočil na uporabnika) .
Spremembe v logiki so res ogromne. In rad bi opozoril, da to ne pomeni vedno celih let razvoja ogromne ekipe in nešteto vrstic kode. chat-engine in user-engine skupaj z vsemi dodatnimi zgodbami, kot je Huffman za stiskanje sporočil, drevesa Splay in struktura za uvožena sporočila, je manj kot 20 tisoč vrstic kode. In napisali so jih 3 razvijalci v samo 10 mesecih (vendar je vredno upoštevati, da - svetovni prvaki ).
Poleg tega smo namesto podvojitve števila strežnikov zmanjšali njihovo število za polovico - zdaj uporabniški in klepetalni motor živita na 500 fizičnih strojih, medtem ko ima nova shema velik prostor za obremenitev. Pri opremi smo prihranili veliko denarja - približno 5 milijonov $ + 750 tisoč $ na leto v operativnih stroških.
Prizadevamo si najti najboljše rešitve za najbolj kompleksne in obsežne probleme. Imamo jih veliko - in zato iščemo nadarjene razvijalce v oddelku za baze podatkov. Če radi in znate reševati tovrstne probleme, odlično poznate algoritme in podatkovne strukture, vas vabimo v ekipo. Obrnite se na naše za podrobnosti.
Tudi če ta zgodba ne govori o vas, upoštevajte, da cenimo priporočila. Povej prijatelju o , in če uspešno opravi poskusno dobo, boste prejeli bonus v višini 100 tisoč rubljev.
Vir: www.habr.com