Ons gebruikers skryf boodskappe aan mekaar sonder om moegheid te ken.
Dis nogal baie. As jy van plan is om al die boodskappe van alle gebruikers te lees, sal dit meer as 150 duisend jaar neem. Met dien verstande dat jy 'n redelik gevorderde leser is en nie meer as 'n sekonde aan elke boodskap bestee nie.
Met so 'n volume data is dit van kritieke belang dat die logika vir die stoor en toegang daartoe optimaal gebou word. Anders kan dit in een nie-so-wonderlike oomblik duidelik word dat alles binnekort skeefloop.
Vir ons het hierdie oomblik 'n jaar en 'n half gelede aangebreek. Hoe ons hiertoe gekom het en wat op die ou end gebeur het - ons vertel jou in volgorde.
Geskiedenis van die uitgawe
In die heel eerste implementering het VKontakte-boodskappe op 'n kombinasie van PHP-agtergrond en MySQL gewerk. Dit is 'n heeltemal normale oplossing vir 'n klein studentewebwerf. Hierdie webwerf het egter onbeheersd gegroei en begin om optimalisering van datastrukture vir homself te eis.
Aan die einde van 2009 is die eerste teksenjin-bewaarplek geskryf, en in 2010 is boodskappe daarna oorgedra.
In die teksenjin is boodskappe in lyste gestoor - 'n soort "posbusse". Elke so 'n lys word bepaal deur 'n uid - die gebruiker wat al hierdie boodskappe besit. 'n Boodskap het 'n stel eienskappe: gespreksgenoot-identifiseerder, teks, aanhangsels, ensovoorts. Die boodskap identifiseerder binne die "boks" is local_id, dit verander nooit en word opeenvolgend vir nuwe boodskappe toegeken. Die "bokse" is onafhanklik en word nie binne die enjin met mekaar gesinchroniseer nie; kommunikasie tussen hulle vind plaas op PHP-vlak. U kan van binne na die datastruktuur en vermoëns van teksenjin kyk .
Dit was genoeg vir korrespondensie tussen twee gebruikers. Raai wat volgende gebeur het?
In Mei 2011 het VKontakte gesprekke met verskeie deelnemers bekendgestel—multi-klets. Om saam met hulle te werk, het ons twee nuwe groepe geskep – lidkletse en geselslede. Die eerste een stoor data oor kletse deur gebruikers, die tweede stoor data oor gebruikers deur kletse. Benewens die lyste self, sluit dit byvoorbeeld die nooiende gebruiker in en die tyd wat hulle by die klets gevoeg is.
"PHP, kom ons stuur 'n boodskap na die klets," sê die gebruiker.
"Komaan, {gebruikersnaam}," sê PHP.
Daar is nadele aan hierdie skema. Sinchronisasie is steeds die verantwoordelikheid van PHP. Groot geselsies en gebruikers wat gelyktydig boodskappe aan hulle stuur, is 'n gevaarlike storie. Aangesien die teks-enjin-instansie van die uid afhang, kan kletsdeelnemers dieselfde boodskap op verskillende tye ontvang. ’n Mens sou hiermee kon saamleef as vooruitgang stilstaan. Maar dit sal nie gebeur nie.
Aan die einde van 2015 het ons gemeenskapsboodskappe bekendgestel, en aan die begin van 2016 het ons 'n API vir hulle bekendgestel. Met die koms van groot kletsbotte in gemeenskappe was dit moontlik om van eweredige vragverspreiding te vergeet.
’n Goeie bot genereer etlike miljoene boodskappe per dag – selfs die mees spraaksame gebruikers kan nie hiermee spog nie. Dit beteken dat sommige gevalle van teks-enjin, waarop sulke bots geleef het, ten volle begin ly het.
Boodskapenjins in 2016 is 100 gevalle van kletslede en ledekletse, en 8000 teksenjins. Hulle is op 'n duisend bedieners aangebied, elk met 64 GB geheue. As 'n eerste noodmaatreël het ons die geheue met nog 32 GB vergroot. Ons het die voorspellings beraam. Sonder drastiese veranderinge sou dit genoeg wees vir nog sowat 'n jaar. Jy moet óf hardeware in die hande kry óf die databasisse self optimaliseer.
As gevolg van die aard van die argitektuur, maak dit net sin om hardeware in veelvoude te verhoog. Dit wil sê, ten minste verdubbeling van die aantal motors - natuurlik is dit 'n taamlik duur pad. Ons sal optimaliseer.
Nuwe konsep
Die sentrale essensie van die nuwe benadering is klets. 'n Klets het 'n lys boodskappe wat daarmee verband hou. Die gebruiker het 'n lys van kletse.
Die vereiste minimum is twee nuwe databasisse:
- klets-enjin. Dit is 'n bewaarplek van kletsvektore. Elke klets het 'n vektor van boodskappe wat daarmee verband hou. Elke boodskap het 'n teks en 'n unieke boodskap-identifiseerder binne die klets - chat_local_id.
- gebruikers-enjin. Dit is 'n berging van gebruikersvektore - skakels na gebruikers. Elke gebruiker het 'n vektor van peer_id (gesprekkers - ander gebruikers, multi-klets of gemeenskappe) en 'n vektor van boodskappe. Elke peer_id het 'n vektor van boodskappe wat daarmee verband hou. Elke boodskap het 'n chat_local_id en 'n unieke boodskap-ID vir daardie gebruiker - user_local_id.
Nuwe groepe kommunikeer met mekaar met behulp van TCP - dit verseker dat die volgorde van versoeke nie verander nie. Die versoeke self en bevestigings daarvoor word op die hardeskyf aangeteken - dus kan ons die toestand van die tou enige tyd herstel na 'n mislukking of herbegin van die enjin. Aangesien die gebruikersenjin en kletsenjin elk 4 duisend stukke is, sal die versoektou tussen die clusters eweredig versprei word (maar in werklikheid is daar glad nie een nie - en dit werk baie vinnig).
Werk met skyf in ons databasisse is in die meeste gevalle gebaseer op 'n kombinasie van 'n binêre log van veranderinge (binlog), statiese foto's en 'n gedeeltelike beeld in die geheue. Veranderinge gedurende die dag word na 'n binlog geskryf, en 'n momentopname van die huidige toestand word periodiek geskep. 'n Momentopname is 'n versameling datastrukture wat vir ons doeleindes geoptimaliseer is. Dit bestaan uit 'n kopskrif (meta-indeks van die prent) en 'n stel metafile. Die kopskrif word permanent in RAM gestoor en dui aan waar om te soek vir data van die momentopname. Elke metalêer bevat data wat waarskynlik op die nabye tydstip benodig sal word—byvoorbeeld wat verband hou met 'n enkele gebruiker. Wanneer jy navraag doen oor die databasis deur die snapshot-opskrif te gebruik, word die vereiste metalêer gelees, en dan word veranderinge in die binlog wat plaasgevind het nadat die momentopname geskep is, in ag geneem. U kan meer lees oor die voordele van hierdie benadering .
Terselfdertyd verander die data op die hardeskyf self net een keer per dag - laat in die nag in Moskou, wanneer die vrag minimaal is. Danksy dit (met die wete dat die struktuur op die skyf deur die loop van die dag konstant is), kan ons dit bekostig om vektore te vervang met skikkings van 'n vaste grootte - en as gevolg hiervan, wins in geheue.
Die stuur van 'n boodskap in die nuwe skema lyk soos volg:
- Die PHP backend kontak die gebruiker-enjin met 'n versoek om 'n boodskap te stuur.
- gebruiker-enjin volmag die versoek na die verlangde klets-enjin instansie, wat terugkeer na gebruiker-enjin chat_local_id - 'n unieke identifiseerder van 'n nuwe boodskap binne hierdie klets. Die chat_engine saai dan die boodskap aan alle ontvangers in die klets uit.
- gebruiker-enjin ontvang chat_local_id van chat-enjin en stuur user_local_id terug na PHP - 'n unieke boodskap identifiseerder vir hierdie gebruiker. Hierdie identifiseerder word dan byvoorbeeld gebruik om met boodskappe via die API te werk.
Maar benewens om werklik boodskappe te stuur, moet jy nog 'n paar belangrike dinge implementeer:
- Sublyste is byvoorbeeld die mees onlangse boodskappe wat jy sien wanneer jy die gespreklys oopmaak. Ongeleesde boodskappe, boodskappe met etikette ("Belangrik", "Strooipos", ens.).
- Komprimeer boodskappe in klets-enjin
- Kas boodskappe in gebruikersenjin
- Soek (deur alle dialoë en binne 'n spesifieke een).
- Intydse opdatering (Longpolling).
- Stoor geskiedenis om caching op mobiele kliënte te implementeer.
Alle sublyste is vinnig veranderende strukture. Om met hulle te werk gebruik ons . Hierdie keuse word verklaar deur die feit dat ons soms 'n hele segment van boodskappe vanaf 'n momentopname bo-aan die boom stoor - byvoorbeeld, na nagtelike herindeksering, bestaan die boom uit een bokant, wat al die boodskappe van die sublys bevat. Die Splay-boom maak dit maklik om in die middel van so 'n hoekpunt in te steek sonder om aan balansering te dink. Boonop stoor Splay nie onnodige data nie, wat ons geheue bespaar.
Boodskappe behels 'n groot hoeveelheid inligting, meestal teks, wat nuttig is om te kan saamdruk. Dit is belangrik dat ons selfs een individuele boodskap akkuraat kan deargiveer. Word gebruik om boodskappe saam te pers met ons eie heuristiek - byvoorbeeld, ons weet dat in boodskappe woorde afgewissel word met "nie-woorde" - spasies, leestekens - en ons onthou ook van die kenmerke van die gebruik van simbole vir die Russiese taal.
Aangesien daar baie minder gebruikers as kletse is, kas ons boodskappe in gebruikersenjin om ewekansige toegang-skyfversoeke in kletsenjin te stoor.
Boodskapsoektog word geïmplementeer as 'n diagonale navraag vanaf gebruikersenjin na alle kletsenjingevalle wat kletse van hierdie gebruiker bevat. Die resultate word in die gebruikersenjin self gekombineer.
Wel, al die besonderhede is in ag geneem, al wat oorbly is om na 'n nuwe skema oor te skakel – en verkieslik sonder dat gebruikers dit agterkom.
Datamigrasie
So, ons het 'n teksenjin wat boodskappe per gebruiker stoor, en twee groepe kletslede en lidkletse wat data oor multi-kletskamers en die gebruikers daarin stoor. Hoe om van hierdie na die nuwe gebruikersenjin en kletsenjin te beweeg?
lidkletse in die ou skema is hoofsaaklik vir optimalisering gebruik. Ons het vinnig die nodige data daaruit na kletslede oorgedra, en toe het dit nie meer aan die migrasieproses deelgeneem nie.
Tou vir kletslede. Dit sluit 100 gevalle in, terwyl chat-enjin 4 duisend het. Om die data oor te dra, moet jy dit in ooreenstemming bring - hiervoor is kletslede in dieselfde 4 duisend kopieë verdeel, en dan is die lees van die kletslede-binlog in die kletsenjin geaktiveer.
Nou weet klets-enjin van multi-klets van kletslede, maar dit weet nog niks van dialoë met twee gespreksgenote nie. Sulke dialoë is geleë in die teks-enjin met verwysing na gebruikers. Hier het ons die data "kop-aan" geneem: elke klets-enjin-instansie het alle teks-enjin-instansies gevra of hulle die nodige dialoog gehad het.
Groot - klets-enjin weet watter multi-klets geselsies daar is en weet watter dialoë daar is.
Jy moet boodskappe kombineer in multi-klets kletse sodat jy eindig met 'n lys van boodskappe in elke klets. Eerstens haal kletsenjin alle gebruikerboodskappe van hierdie klets af uit teksenjin. In sommige gevalle is daar nogal baie van hulle (tot honderde miljoene), maar met baie seldsame uitsonderings pas die klets heeltemal in RAM. Ons het ongeordende boodskappe, elk in verskeie kopieë - hulle word immers almal getrek uit verskillende teks-enjin-instansies wat ooreenstem met gebruikers. Die doel is om boodskappe te sorteer en ontslae te raak van kopieë wat onnodige spasie opneem.
Elke boodskap het 'n tydstempel wat die tyd wat dit gestuur is en teks bevat. Ons gebruik tyd vir sortering - ons plaas wysers na die oudste boodskappe van multichat-deelnemers en vergelyk hashes uit die teks van die beoogde kopieë, en beweeg na die verhoging van die tydstempel. Dit is logies dat die kopieë dieselfde hash en tydstempel sal hê, maar in die praktyk is dit nie altyd die geval nie. Soos u onthou, is sinchronisasie in die ou skema deur PHP uitgevoer - en in seldsame gevalle het die tyd van die stuur van dieselfde boodskap tussen verskillende gebruikers verskil. In hierdie gevalle het ons onsself toegelaat om die tydstempel te wysig - gewoonlik binne 'n sekonde. Die tweede probleem is die verskillende volgorde van boodskappe vir verskillende ontvangers. In sulke gevalle het ons toegelaat dat 'n ekstra kopie geskep word, met verskillende bestelopsies vir verskillende gebruikers.
Hierna word data oor boodskappe in multichat na die gebruikersenjin gestuur. En hier kom 'n onaangename kenmerk van ingevoerde boodskappe. In normale werking word boodskappe wat na die enjin kom, streng in stygende volgorde volgens user_local_id gerangskik. Boodskappe wat vanaf die ou enjin in die gebruikersenjin ingevoer is, het hierdie nuttige eienskap verloor. Terselfdertyd, vir die gerief van toetsing, moet jy vinnig toegang daartoe kan kry, iets daarin kan soek en nuwes kan byvoeg.
Ons gebruik 'n spesiale datastruktuur om ingevoerde boodskappe te stoor.
Dit verteenwoordig 'n vektor van grootte waar is almal - is anders en georden in dalende volgorde, met 'n spesiale volgorde van elemente. In elke segment met indekse elemente gesorteer word. Om na 'n element in so 'n struktuur te soek, neem tyd deur binêre soektogte. Die byvoeging van 'n element word oor geamortiseer .
So, ons het uitgevind hoe om data van ou enjins na nuwes oor te dra. Maar hierdie proses neem 'n paar dae - en dit is onwaarskynlik dat ons gebruikers gedurende hierdie dae die gewoonte sal prysgee om aan mekaar te skryf. Om nie boodskappe gedurende hierdie tyd te verloor nie, skakel ons oor na 'n werkskema wat beide ou en nuwe groepe gebruik.
Data word geskryf aan kletslede en gebruikersenjin (en nie na teksenjin nie, soos in normale werking volgens die ou skema). gebruiker-enjin volmag die versoek na klets-enjin - en hier hang die gedrag daarvan af of hierdie klets reeds saamgevoeg is of nie. As die klets nog nie saamgevoeg is nie, skryf die klets-enjin nie die boodskap aan homself nie, en die verwerking daarvan vind slegs in die teks-enjin plaas. As die klets reeds in klets-enjin saamgevoeg is, stuur dit chat_local_id terug na gebruiker-enjin en stuur die boodskap aan alle ontvangers. gebruiker-enjin volmag alle data na teks-enjin - sodat as iets gebeur, ons altyd kan terugrol, met al die huidige data in die ou enjin. teks-enjin gee user_local_id terug, wat gebruiker-enjin stoor en terugkeer na die agterkant.
Gevolglik lyk die oorgangsproses so: ons koppel leë gebruikersenjin- en kletsenjinklusters. klets-enjin lees die hele klets-lede binlog, dan begin volmag volgens die skema hierbo beskryf. Ons dra die ou data oor en kry twee gesinchroniseerde groepe (oud en nuut). Al wat oorbly, is om lees van teksenjin na gebruikersenjin oor te skakel en instaanbediener te deaktiveer.
Bevindinge
Danksy die nuwe benadering is alle werkverrigtingmaatstawwe van die enjins verbeter en probleme met datakonsekwentheid opgelos. Nou kan ons vinnig nuwe kenmerke in boodskappe implementeer (en het reeds begin om dit te doen - ons het die maksimum aantal kletsdeelnemers verhoog, 'n soektog vir aangestuurde boodskappe geïmplementeer, vasgespelde boodskappe van stapel gestuur en die limiet op die totale aantal boodskappe per gebruiker verhoog) .
Die veranderinge in logika is werklik enorm. En ek wil daarop let dat dit nie altyd 'n hele jare se ontwikkeling deur 'n groot span en magdom reëls kode beteken nie. klets-enjin en gebruikers-enjin saam met al die bykomende stories soos Huffman vir boodskapkompressie, Splay trees en struktuur vir ingevoerde boodskappe is minder as 20 duisend reëls kode. En dit is binne 3 maande deur 10 ontwikkelaars geskryf (dit is egter die moeite werd om in gedagte te hou dat - wêreldkampioene ).
Boonop, in plaas daarvan om die aantal bedieners te verdubbel, het ons hul getal met die helfte verminder - nou leef die gebruikersenjin en kletsenjin op 500 fisiese masjiene, terwyl die nuwe skema 'n groot laairuimte het. Ons het baie geld op toerusting gespaar – sowat $5 miljoen + $750 duisend per jaar aan bedryfsuitgawes.
Ons streef daarna om die beste oplossings vir die mees komplekse en grootskaalse probleme te vind. Ons het baie van hulle - en dit is hoekom ons op soek is na talentvolle ontwikkelaars in die databasisafdeling. As jy lief is en weet hoe om sulke probleme op te los, 'n uitstekende kennis van algoritmes en datastrukture het, nooi ons jou uit om by die span aan te sluit. Kontak ons vir besonderhede.
Selfs al gaan hierdie storie nie oor jou nie, let asseblief daarop dat ons aanbevelings waardeer. Vertel 'n vriend van , en as hy die proeftydperk suksesvol voltooi, sal jy 'n bonus van 100 duisend roebels ontvang.
Bron: will.com