Us brûkers skriuwe berjochten nei elkoar sûnder wurgens te witten.
Dat is nochal in soad. As jo útsette om alle berjochten fan alle brûkers te lêzen, soe it mear dan 150 tûzen jier duorje. Op betingst dat jo in frij avansearre lêzer binne en net mear as in sekonde besteegje oan elk berjocht.
Mei sa'n folume fan gegevens is it kritysk dat de logika foar it opslaan en tagong dêrfan optimaal boud is. Oars kin it yn ien net sa prachtich momint dúdlik wurde dat alles gau mis giet.
Foar ús kaam dit momint oardel jier lyn. Hoe't wy hjir komme en wat der op it lêst barde - wy fertelle jo yn oarder.
Eftergrûn
Yn 'e earste ymplemintaasje wurken VKontakte-berjochten oan in kombinaasje fan PHP-backend en MySQL. Dit is in folslein normale oplossing foar in lytse studintewebside. Dizze side groeide lykwols uncontrollably en begon optimisaasje fan gegevensstruktueren foar himsels te freegjen.
Ein 2009 waard de earste repository foar tekstmotoren skreaun, en yn 2010 waarden der berjochten nei oerbrocht.
Yn 'e tekstmotor waarden berjochten opslein yn listen - in soarte fan "brievebussen". Elke sa'n list wurdt bepaald troch in uid - de brûker dy't al dizze berjochten hat. In berjocht hat in set fan attributen: interlocutor identifier, tekst, taheaksels, ensfh. De berjochtidentifikaasje yn 'e "fak" is local_id, it feroaret noait en wurdt sequentieel tawiisd foar nije berjochten. De "doazen" binne ûnôfhinklik en wurde net syngronisearre mei inoar yn 'e motor; kommunikaasje tusken har bart op PHP-nivo. Jo kinne de gegevensstruktuer en mooglikheden fan tekstmotor fan binnen sjen .
Dit wie genôch foar korrespondinsje tusken twa brûkers. Tink wat der dêrnei barde?
Yn maaie 2011, VKontakte yntrodusearre petearen mei ferskate dielnimmers - multi-chat. Om mei har te wurkjen, hawwe wy twa nije klusters oprjochte - lid-chats en chat-leden. De earste bewarret gegevens oer petearen troch brûkers, de twadde bewarret gegevens oer brûkers troch petearen. Neist de listen sels omfettet dit bygelyks de útnoegjende brûker en de tiid dat se taheakke binne oan it petear.
"PHP, lit ús in berjocht stjoere nei it petear," seit de brûker.
"Kom op, {brûkersnamme}," seit PHP.
Der binne neidielen oan dizze regeling. Syngronisaasje is noch altyd de ferantwurdlikens fan PHP. Grutte petearen en brûkers dy't tagelyk berjochten nei har stjoere binne in gefaarlik ferhaal. Sûnt de tekst-engine-eksimplaar hinget ôf fan 'e uid, kinne chat-dielnimmers itselde berjocht op ferskate tiden ûntfange. Dêr soe men mei libje kinne as de foarútgong stilstie. Mar dat sil net barre.
Oan 'e ein fan 2015 lansearren wy mienskipsberjochten, en oan it begjin fan 2016 lansearren wy in API foar har. Mei de komst fan grutte chatbots yn mienskippen wie it mooglik om te ferjitten oer sels loadferdieling.
In goede bot genereart ferskate miljoen berjochten per dei - sels de meast sprekkende brûkers kinne hjir net opskeppe. Dit betsjut dat guon eksimplaren fan tekstmotoren, dêr't sokke bots op wennen, it meast begon te lijen.
Berjochtmotoren yn 2016 binne 100 eksimplaren fan petear-leden en lid-chats, en 8000 tekstmotoren. Se waarden hosted op tûzen servers, elk mei 64 GB ûnthâld. As earste needmaatregel fergrutte wy it ûnthâld mei in oare 32 GB. Wy skatte de prognoazes. Sûnder drastyske feroarings soe dit noch sa'n jier genôch wêze. Jo moatte óf hardware krije óf de databases sels optimalisearje.
Fanwegen de aard fan 'e arsjitektuer makket it allinich sin om hardware yn multiples te fergrutsjen. Dat is, op syn minst ferdûbeling fan it oantal auto's - fansels, dit is in frij djoer paad. Wy sille optimalisearje.
Nij konsept
De sintrale essinsje fan de nije oanpak is petear. In petear hat in list mei berjochten dy't dêrmei relatearje. De brûker hat in list mei petearen.
It fereaske minimum is twa nije databases:
- chat-motor. Dit is in repository fan petearvektoren. Elk petear hat in fektor fan berjochten dy't dêrmei relatearje. Elk berjocht hat in tekst en in unike berjochtidentifikaasje binnen it petear - chat_local_id.
- brûker-motor. Dit is in opslach fan brûkersfektors - keppelings nei brûkers. Elke brûker hat in fektor fan peer_id (sprekkers - oare brûkers, multi-chat of mienskippen) en in fektor fan berjochten. Elke peer_id hat in fektor fan berjochten dy't dêrmei relatearje. Elk berjocht hat in chat_local_id en in unike berjocht-ID foar dy brûker - user_local_id.
Nije klusters kommunisearje mei elkoar mei TCP - dit soarget derfoar dat de folchoarder fan oanfragen net feroaret. De oanfragen sels en befêstigingen foar har wurde opnommen op 'e hurde skiif - sadat wy de steat fan' e wachtrige op elk momint kinne weromsette nei in mislearring of opnij starte fan 'e motor. Om't de brûkersmotor en petearmotor elk 4 tûzen shards binne, sil de oanfraachwachtrige tusken de klusters lykwichtich ferdield wurde (mar yn werklikheid is d'r hielendal gjinien - en it wurket heul fluch).
Wurkje mei skiif yn ús databases is yn 'e measte gefallen basearre op in kombinaasje fan in binêre log fan feroaringen (binlog), statyske snapshots en in dielôfbylding yn it ûnthâld. Feroarings oerdeis wurde skreaun nei in binlog, en in momintopname fan de aktuele steat wurdt periodyk makke. In momintopname is in samling gegevensstruktueren optimalisearre foar ús doelen. It bestiet út in koptekst (metaindex fan 'e ôfbylding) en in set metafiles. De koptekst wurdt permanint opslein yn RAM en jout oan wêr't te sykjen nei gegevens út de momintopname. Elke metafil befettet gegevens dy't wierskynlik nedich binne op tichtby punten yn 'e tiid - bygelyks relatearre oan ien brûker. As jo de databank opfreegje mei de snapshot-header, wurdt it fereaske metafil lêzen, en dan wurde feroaringen yn 'e binlog dy't barde nei't de momintopname makke is rekken holden. Jo kinne mear lêze oer de foardielen fan dizze oanpak .
Tagelyk feroarje de gegevens op 'e hurde skiif sels mar ien kear deis - nachts let yn Moskou, as de lading minimaal is. Mei tank oan dit (wittende dat de struktuer op 'e skiif is konstante hiele dei), kinne wy betelje te ferfangen vectors mei arrays fan in fêste grutte - en dêrtroch winst yn ûnthâld.
It ferstjoeren fan in berjocht yn it nije skema sjocht der sa út:
- De PHP-backend kontaktet de brûkersmotor mei in fersyk om in berjocht te stjoeren.
- user-engine proxearret it fersyk nei de winske chat-engine-eksimplaar, dy't weromkomt nei user-engine chat_local_id - in unike identifier fan in nij berjocht binnen dit petear. De chat_engine stjoert it berjocht dan út nei alle ûntfangers yn it petear.
- user-engine ûntfangt chat_local_id fan chat-engine en jout user_local_id werom nei PHP - in unike berjochtidentifikaasje foar dizze brûker. Dizze identifier wurdt dan brûkt, bygelyks, om te wurkjen mei berjochten fia de API.
Mar neist it feitlik ferstjoeren fan berjochten, moatte jo in pear wichtiger dingen ymplementearje:
- Sublisten binne bygelyks de meast resinte berjochten dy't jo sjogge by it iepenjen fan de konversaasjelist. Net-lêzen berjochten, berjochten mei tags ("Wichtich", "Spam", ensfh.).
- Berjochten komprimearje yn chat-motor
- Caching berjochten yn brûkersmotor
- Sykje (fia alle dialogen en binnen in spesifyk).
- Real-time update (Longpolling).
- Skiednis opslaan om caching op mobile kliïnten te ymplementearjen.
Alle sublisten binne rap feroarjende struktueren. Om mei har te wurkjen brûke wy . Dizze kar wurdt ferklearre troch it feit dat wy oan 'e boppekant fan' e beam soms in hiel segmint fan berjochten fan in momintopname opslaan - bygelyks, nei nachtlike weryndeksearring, bestiet de beam út ien top, dy't alle berjochten fan 'e sublist befettet. De Splay-beam makket it maklik om yn 'e midden fan sa'n toppunt yn te setten sûnder te tinken oer balansearjen. Derneist bewarret Splay gjin ûnnedige gegevens, wat ús ûnthâld besparret.
Berjochten befetsje in grutte hoemannichte ynformaasje, meast tekst, dy't nuttich is om te kinnen komprimearje. It is wichtich dat wy sels ien yndividueel berjocht sekuer kinne unargyfje. Wurdt brûkt om berjochten te komprimearjen mei ús eigen heuristyk - wy witte bygelyks dat yn berjochten wurden ôfwikselje mei "net-wurden" - spaasjes, ynterpunksjes - en wy ûnthâlde ek guon fan 'e funksjes fan it brûken fan symboalen foar de Russyske taal.
Om't d'r folle minder brûkers binne dan petearen, om willekeurich-tagong-skiifoanfragen yn petearmotor op te slaan, cache wy berjochten yn brûkersmotor.
Berjochtsykjen wurdt ymplementearre as in diagonale query fan brûker-motor nei alle chat-motor-eksimplaren dy't petearen fan dizze brûker befetsje. De resultaten wurde kombinearre yn 'e brûkersmotor sels.
No, alle details binne yn rekken brocht, alles wat oerbliuwt is om te wikseljen nei in nij skema - en leafst sûnder dat brûkers it yn 'e gaten hawwe.
Gegevensmigraasje
Dat, wy hawwe in tekstmotor dy't berjochten opslaat per brûker, en twa klusters chat-leden en lid-chats dy't gegevens opslaan oer multi-chat keamers en de brûkers dêryn. Hoe kinne jo fan dit ferpleatse nei de nije brûkersmotor en petearmotor?
lid-chats yn it âlde skema waard primêr brûkt foar optimalisaasje. Wy hawwe fluch de nedige gegevens derfan oerbrocht nei chat-leden, en doe die it net mear mei oan it migraasjeproses.
Wachtrige foar petear-leden. It omfettet 100 eksimplaren, wylst chat-motor 4 tûzen hat. Om de gegevens oer te dragen, moatte jo it yn oerienstimming bringe - hjirfoar waarden petear-leden ferdield yn deselde 4 tûzen eksimplaren, en dan waard it lêzen fan 'e chat-leden binlog ynskeakele yn' e petearmotor.
No wit chat-motor oer multi-chat fan petear-leden, mar it wit noch neat oer dialogen mei twa petearpartners. Sokke dialogen sitte yn 'e tekstmotor mei ferwizing nei brûkers. Hjir namen wy de gegevens "head-on": elke chat-engine-eksimplaar frege alle tekst-motor-eksimplaren as se de dialooch hiene dy't it nedich wie.
Geweldich - chat-motor wit hokker multi-chat chats der binne en wit hokker dialogen der binne.
Jo moatte berjochten kombinearje yn petearen mei meardere petearen sadat jo einigje mei in list mei berjochten yn elk petear. Earst helje chat-engine alle brûkersberjochten fan dit petear fan tekst-motor op. Yn guon gefallen binne d'r nochal in protte (oant hûnderten miljoenen), mar mei heul seldsume útsûnderings past it petear folslein yn RAM. Wy hawwe net-oardere berjochten, elk yn ferskate eksimplaren - se wurde ommers allegear helle út ferskate tekstmotoreksimplaren dy't oerienkomme mei brûkers. It doel is om berjochten te sortearjen en kopyen dy't ûnnedige romte ynnimme kwyt te reitsjen.
Elk berjocht hat in tiidstempel mei de tiid dat it ferstjoerd is en tekst. Wy brûke tiid foar sortearjen - wy pleatse oanwizers nei de âldste berjochten fan multichat-dielnimmers en fergelykje hashes út 'e tekst fan' e bedoelde kopyen, bewegend nei tanimmend tiidstempel. It is logysk dat de kopyen deselde hash en tiidstempel hawwe, mar yn 'e praktyk is dat net altyd it gefal. Sa't jo ûnthâlde, syngronisaasje yn it âlde skema waard útfierd troch PHP - en yn seldsume gefallen, de tiid fan it ferstjoeren fan itselde berjocht ferskille tusken ferskillende brûkers. Yn dizze gefallen hawwe wy ússels tastien om it tiidstempel te bewurkjen - normaal binnen in sekonde. It twadde probleem is de ferskillende folchoarder fan berjochten foar ferskate ûntfangers. Yn sokke gefallen hawwe wy tastien in ekstra kopy te meitsjen, mei ferskate bestellen opsjes foar ferskate brûkers.
Hjirnei wurde gegevens oer berjochten yn multichat stjoerd nei de brûkersmotor. En hjir komt in onaangename eigenskip fan ymporteare berjochten. Yn normale operaasje wurde berjochten dy't nei de motor komme, strikt yn oprinnende folchoarder besteld troch user_local_id. Berjochten ymportearre fan 'e âlde motor yn' e brûkersmotor ferlearen dizze nuttige eigenskip. Tagelyk, foar it gemak fan testen, moatte jo se fluch tagong kinne krije, wat yn har sykje en nije tafoegje.
Wy brûke in spesjale gegevensstruktuer om ymporteare berjochten op te slaan.
It fertsjintwurdiget in vector fan grutte wêr is elkenien - binne oars en oardere yn ôfnimmende folchoarder, mei in spesjale folchoarder fan eleminten. Yn elk segmint mei yndeksen eleminten wurde sortearre. It sykjen nei in elemint yn sa'n struktuer duorret tiid через binêre sykopdrachten. De tafoeging fan in elemint wurdt amortisearre oer .
Dat, wy hawwe útfûn hoe't jo gegevens oerdrage fan âlde motoren nei nije. Mar dit proses duorret ferskate dagen - en it is net wierskynlik dat ús brûkers yn dizze dagen de gewoante opjaan om inoar te skriuwen. Om yn dizze tiid gjin berjochten te ferliezen, skeakelje wy oer nei in wurkskema dat sawol âlde as nije klusters brûkt.
Gegevens wurde skreaun nei petear-leden en brûkersmotor (en net nei tekstmotor, lykas yn normale operaasje neffens it âlde skema). user-engine proxearret it fersyk nei chat-motor - en hjir hinget it gedrach ôf fan oft dit petear al is gearfoege of net. As it petear noch net gearfoege is, skriuwt de petearmotor it berjocht net nei himsels, en de ferwurking dêrfan bart allinich yn 'e tekstmotor. As it petear al is gearfoege yn petearmotor, jout it chat_local_id werom nei brûkersmotor en stjoert it berjocht nei alle ûntfangers. brûker-motor proxearret alle gegevens nei tekstmotor - sadat as der wat bart, wy altyd werom kinne rôlje, mei alle hjoeddeistige gegevens yn 'e âlde motor. text-engine jout user_local_id werom, dy't brûker-motor opslacht en weromkomt nei de efterkant.
As resultaat sjocht it oergongsproses der sa út: wy ferbine lege klusters fan brûkersmotor en petearmotor. chat-engine lêst it hiele binlog fan chat-leden, dan begjint proxying neffens it hjirboppe beskreaune skema. Wy drage de âlde gegevens oer en krije twa syngronisearre klusters (âld en nij). Alles wat oerbliuwt is it lêzen fan tekstmotor nei brûkersmotor te wikseljen en proxying út te skeakeljen.
Resultaten
Mei tank oan de nije oanpak binne alle prestaasjesmetriken fan 'e motoren ferbettere en problemen mei gegevenskonsistinsje binne oplost. No kinne wy fluch nije funksjes yn berjochten ymplementearje (en binne al begon mei dit te dwaan - wy hawwe it maksimale oantal peteardielnimmers ferhege, in sykopdracht útfierd foar trochstjoerde berjochten, lansearre pinne berjochten en ferhege de limyt op it totale oantal berjochten per brûker) .
De feroaringen yn logika binne wirklik enoarm. En ik soe graach opmerke dat dit net altyd betsjuttet hiele jierren fan ûntwikkeling troch in enoarme team en myriaden fan rigels koade. chat-motor en brûker-motor tegearre mei alle ekstra ferhalen lykas Huffman foar berjocht kompresje, Splay beammen en struktuer foar ymportearre berjochten is minder as 20 tûzen rigels fan koade. En se waarden skreaun troch 3 ûntwikkelders yn mar 10 moannen (it is lykwols it wurdich te hâlden dat - wrâldkampioenen ).
Boppedat, ynstee fan it ferdûbeljen fan it oantal servers, hawwe wy har oantal mei de helte fermindere - no libje de brûkersmotor en petearmotor op 500 fysike masines, wylst it nije skema in grutte headroom hat foar lading. Wy hawwe in protte jild besparre op apparatuer - sawat $ 5 miljoen + $ 750 tûzen yn 't jier yn bedriuwskosten.
Wy stribje dernei om de bêste oplossingen te finen foar de meast komplekse en grutskalige problemen. Wy hawwe se genôch - en dêrom sykje wy talintfolle ûntwikkelders yn 'e database-ôfdieling. As jo leafde en witte hoe't jo sokke problemen oplosse, hawwe in poerbêste kennis fan algoritmen en gegevens struktueren, wy noegje jo út om mei te dwaan it team. Nim kontakt op mei ús foar details.
Sels as dit ferhaal net oer jo giet, tink derom dat wy oanbefellings wurdearje. Fertel in freon oer , en as hy de proeftiid mei súkses foltôget, krije jo in bonus fan 100 tûzen roebel.
Boarne: www.habr.com