Naši používatelia si píšu správy bez toho, aby poznali únavu.
To je dosť veľa. Ak by ste sa rozhodli čítať všetky správy všetkých používateľov, trvalo by to viac ako 150 tisíc rokov. Za predpokladu, že ste pomerne pokročilý čitateľ a na každú správu nestrávite viac ako sekundu.
Pri takomto objeme údajov je dôležité, aby bola logika na ukladanie a prístup k nim vybudovaná optimálne. V opačnom prípade môže byť v jednom nie nádhernom momente jasné, že sa všetko čoskoro pokazí.
U nás tento moment nastal pred rokom a pol. Ako sme k tomu prišli a čo sa nakoniec stalo - povieme vám v poradí.
anamnéza
V úplne prvej implementácii správy VKontakte fungovali na kombinácii PHP backendu a MySQL. Toto je úplne bežné riešenie pre malý študentský web. Táto stránka však nekontrolovateľne rástla a začala si pre seba vyžadovať optimalizáciu dátových štruktúr.
Koncom roka 2009 bol napísaný prvý textový repozitár, do ktorého boli v roku 2010 prenesené správy.
V textovom stroji boli správy uložené v zoznamoch - akési „poštové schránky“. Každý takýto zoznam je určený uid – používateľom, ktorý vlastní všetky tieto správy. Správa má súbor atribútov: identifikátor partnera, text, prílohy atď. Identifikátor správy vo vnútri „boxu“ je local_id, nikdy sa nemení a novým správam sa priraďuje postupne. „Boxy“ sú nezávislé a nie sú navzájom synchronizované vo vnútri motora, komunikácia medzi nimi prebieha na úrovni PHP. Môžete sa pozrieť na dátovú štruktúru a možnosti textového stroja zvnútra .
To úplne stačilo na korešpondenciu medzi dvoma používateľmi. Hádajte, čo sa stalo potom?
V máji 2011 VKontakte zaviedol rozhovory s niekoľkými účastníkmi — multichat. Aby sme s nimi mohli pracovať, vytvorili sme dva nové klastre – Member-chats a Chat-members. Prvý ukladá údaje o chatoch podľa užívateľov, druhý ukladá dáta o užívateľoch podľa chatov. Okrem samotných zoznamov sem patrí napríklad pozývajúci používateľ a čas, kedy bol do chatu pridaný.
„PHP, pošlime správu do chatu,“ hovorí používateľ.
„No tak, {username},“ hovorí PHP.
Táto schéma má nevýhody. Synchronizácia je stále zodpovednosťou PHP. Veľké chaty a používatelia, ktorí im súčasne posielajú správy, sú nebezpečným príbehom. Keďže inštancia textového nástroja závisí od uid, účastníci chatu môžu dostať rovnakú správu v rôznych časoch. Dalo by sa s tým žiť, keby sa pokrok zastavil. Ale to sa nestane.
Koncom roka 2015 sme spustili komunitné správy a začiatkom roka 2016 sme pre ne spustili API. S príchodom veľkých chatbotov v komunitách bolo možné zabudnúť na rovnomerné rozloženie záťaže.
Dobrý bot generuje niekoľko miliónov správ denne – tým sa nemôžu pochváliť ani tí najzhovorčivejší používatelia. To znamená, že niektoré príklady textového stroja, na ktorom takéto roboty žili, začali naplno trpieť.
Mechanizmy správ v roku 2016 sú 100 inštancií členov chatu a členských chatov a 8000 64 textových modulov. Boli umiestnené na tisíc serveroch, každý so 32 GB pamäte. Ako prvé núdzové opatrenie sme navýšili pamäť o ďalších XNUMX GB. Odhadli sme predpovede. Bez razantných zmien by to vystačilo približne na ďalší rok. Musíte buď zohnať hardvér alebo optimalizovať samotné databázy.
Vzhľadom na povahu architektúry má zmysel zvyšovať hardvér iba v násobkoch. Teda prinajmenšom zdvojnásobenie počtu áut – očividne je to dosť drahá cesta. Budeme optimalizovať.
Nový koncept
Ústrednou podstatou nového prístupu je chat. Rozhovor obsahuje zoznam správ, ktoré sa ho týkajú. Používateľ má zoznam chatov.
Požadované minimum sú dve nové databázy:
- chat-engine. Toto je úložisko chatových vektorov. Každý chat má vektor správ, ktoré sa ho týkajú. Každá správa má v rámci chatu text a jedinečný identifikátor správy – chat_local_id.
- užívateľský motor. Ide o úložisko užívateľských vektorov - odkazov na užívateľov. Každý používateľ má vektor peer_id (partneri - iní používatelia, multichat alebo komunity) a vektor správ. Každé peer_id má vektor správ, ktoré sa ho týkajú. Každá správa má chat_local_id a jedinečné ID správy pre daného používateľa – user_local_id.
Nové klastre medzi sebou komunikujú pomocou TCP – tým je zabezpečené, že sa nezmení poradie požiadaviek. Samotné požiadavky a potvrdenia k nim sa zaznamenávajú na pevný disk – stav fronty tak môžeme kedykoľvek obnoviť po poruche alebo reštarte motora. Keďže užívateľský modul a chatovací modul sú po 4 XNUMX fragmentoch, front požiadaviek medzi klastrami bude rozdelený rovnomerne (ale v skutočnosti neexistuje vôbec žiadny - a funguje veľmi rýchlo).
Práca s diskom v našich databázach je vo väčšine prípadov založená na kombinácii binárneho protokolu zmien (binlog), statických snímok a čiastočného obrazu v pamäti. Zmeny počas dňa sa zapisujú do binlogu a pravidelne sa vytvára snímka aktuálneho stavu. Snímka je zbierka dátových štruktúr optimalizovaných pre naše účely. Pozostáva z hlavičky (metaindexu obrázka) a množiny metasúborov. Hlavička je trvalo uložená v pamäti RAM a označuje, kde hľadať údaje zo snímky. Každý metasúbor obsahuje údaje, ktoré budú pravdepodobne potrebné v časových okamihoch – napríklad súvisiace s jedným používateľom. Pri dotazovaní databázy pomocou hlavičky snímky sa načíta požadovaný metasúbor a potom sa zohľadnia zmeny v binlogu, ktoré nastali po vytvorení snímky. Môžete si prečítať viac o výhodách tohto prístupu .
Zároveň sa údaje na samotnom pevnom disku menia iba raz za deň - neskoro v noci v Moskve, keď je zaťaženie minimálne. Vďaka tomu (s vedomím, že štruktúra na disku je počas dňa konštantná) si môžeme dovoliť nahradiť vektory poliami s pevnou veľkosťou – a vďaka tomu získať pamäť.
Odoslanie správy v novej schéme vyzerá takto:
- Backend PHP kontaktuje užívateľský stroj so žiadosťou o odoslanie správy.
- user-engine odošle požiadavku na požadovanú inštanciu chat-engine, ktorá sa vráti do user-engine chat_local_id - jedinečný identifikátor novej správy v rámci tohto chatu. Chat_engine potom odošle správu všetkým príjemcom v chate.
- user-engine prijme chat_local_id z chat-engine a vráti user_local_id do PHP - jedinečný identifikátor správy pre tohto používateľa. Tento identifikátor sa potom používa napríklad na prácu so správami cez API.
Okrem skutočného odosielania správ však musíte implementovať niekoľko dôležitých vecí:
- Podzoznamy sú napríklad najnovšie správy, ktoré vidíte pri otvorení zoznamu konverzácií. Neprečítané správy, správy so štítkami („Dôležité“, „Spam“ atď.).
- Komprimovanie správ v chat-engine
- Ukladanie správ do vyrovnávacej pamäte v používateľskom mechanizme
- Hľadať (cez všetky dialógové okná a v rámci konkrétneho).
- Aktualizácia v reálnom čase (Longpolling).
- Ukladanie histórie na implementáciu ukladania do vyrovnávacej pamäte na mobilných klientoch.
Všetky podzoznamy rýchlo menia štruktúru. Na prácu s nimi používame . Táto voľba sa vysvetľuje tým, že v hornej časti stromu niekedy ukladáme celý segment správ zo snímky – napríklad po nočnej reindexácii sa strom skladá z jedného vrcholu, ktorý obsahuje všetky správy podzoznamu. Strom Splay umožňuje jednoduché vloženie do stredu takého vrcholu bez toho, aby ste museli premýšľať o vyvážení. Splay navyše neukladá zbytočné dáta, čo nám šetrí pamäť.
Správy obsahujú veľké množstvo informácií, väčšinou textu, ktoré je užitočné komprimovať. Je dôležité, aby sme mohli presne zrušiť archiváciu aj jednej jednotlivej správy. Používa sa na kompresiu správ s našou vlastnou heuristikou - napríklad vieme, že v správach sa slová striedajú s „neslovami“ - medzerami, interpunkčnými znamienkami - a pamätáme si aj niektoré zvláštnosti používania symbolov pre ruský jazyk.
Keďže existuje oveľa menej používateľov ako chatov, na ukladanie požiadaviek na disk s náhodným prístupom v module chatu ukladáme správy do vyrovnávacej pamäte v module user.
Vyhľadávanie správ je implementované ako diagonálny dopyt z používateľského nástroja na všetky inštancie nástroja na rozhovor, ktoré obsahujú rozhovory tohto používateľa. Výsledky sú skombinované v samotnom užívateľskom motore.
Všetky detaily boli zohľadnené, zostáva už len prejsť na novú schému – a pokiaľ možno bez toho, aby si to používatelia všimli.
Migrácia dát
Máme teda textový stroj, ktorý ukladá správy podľa používateľov, a dva klastre členov četu a čety členov, ktoré ukladajú údaje o miestnostiach s viacerými četmi a používateľoch v nich. Ako prejsť z tohto na nový používateľský a chatovací stroj?
členské chaty v starej schéme slúžili predovšetkým na optimalizáciu. Rýchlo sme z neho preniesli potrebné údaje členom chatu a potom sa už nezúčastňoval na procese migrácie.
Poradie pre členov chatu. Zahŕňa 100 inštancií, zatiaľ čo chat-engine má 4 tisíc. Ak chcete preniesť údaje, musíte ich uviesť do súladu - na tento účel boli členovia chatu rozdelení do rovnakých 4 XNUMX kópií a potom bolo v module chatu povolené čítanie binlogu členov chatu.
Teraz chat-engine vie o multi-chat od členov chatu, ale zatiaľ nevie nič o dialógoch s dvoma účastníkmi rozhovoru. Takéto dialógy sa nachádzajú v textovom nástroji s odkazom na používateľov. Tu sme vzali údaje „zoči voči“: každá inštancia nástroja na chat sa spýtala všetkých inštancií textového nástroja, či majú potrebný dialóg.
Skvelé - nástroj na chatovanie vie, aké chaty existujú, a vie, aké dialógy existujú.
V multichatových chatoch musíte skombinovať správy, aby ste nakoniec dostali zoznam správ v každom chate. Po prvé, nástroj chatu načíta z textového nástroja všetky správy používateľov z tohto rozhovoru. V niektorých prípadoch je ich pomerne veľa (až stovky miliónov), ale až na veľmi zriedkavé výnimky sa chat úplne zmestí do pamäte RAM. Máme neusporiadané správy, každú v niekoľkých kópiách – napokon, všetky sú stiahnuté z rôznych inštancií textového nástroja zodpovedajúcich používateľom. Cieľom je triediť správy a zbaviť sa kópií, ktoré zaberajú zbytočné miesto.
Každá správa má časovú pečiatku obsahujúcu čas odoslania a text. Na triedenie využívame čas – umiestňujeme ukazovatele na najstaršie správy účastníkov multichatu a porovnávame hashe z textu zamýšľaných kópií, čím smerujeme k zvyšovaniu časovej pečiatky. Je logické, že kópie budú mať rovnaký hash a časovú pečiatku, ale v praxi to tak nie je vždy. Ako si pamätáte, synchronizáciu v starej schéme vykonal PHP - av zriedkavých prípadoch sa čas odoslania rovnakej správy medzi rôznymi používateľmi líšil. V týchto prípadoch sme si dovolili upraviť časovú pečiatku – zvyčajne do sekundy. Druhým problémom je rozdielne poradie správ pre rôznych príjemcov. V takýchto prípadoch sme umožnili vytvorenie ďalšej kópie s rôznymi možnosťami objednávania pre rôznych používateľov.
Potom sa údaje o správach v multichat odošlú do používateľského nástroja. A tu prichádza nepríjemná vlastnosť importovaných správ. V normálnej prevádzke sú správy, ktoré prichádzajú do motora, zoradené striktne vo vzostupnom poradí podľa user_local_id. Správy importované zo starého nástroja do používateľského nástroja stratili túto užitočnú vlastnosť. Zároveň sa k nim pre pohodlie testovania musíte rýchlo dostať, niečo v nich hľadať a pridávať nové.
Na ukladanie importovaných správ používame špeciálnu dátovú štruktúru.
Predstavuje vektor veľkosti kde sú všetci - sú rôzne a usporiadané v zostupnom poradí, s osobitným poradím prvkov. V každom segmente s indexmi prvky sú triedené. Hľadanie prvku v takejto štruktúre si vyžaduje čas cez binárne vyhľadávanie. Pridanie prvku sa amortizuje .
Takže sme prišli na to, ako preniesť údaje zo starých motorov do nových. Tento proces však trvá niekoľko dní – a je nepravdepodobné, že počas týchto dní sa naši používatelia vzdajú zvyku písať si. Aby sme počas tejto doby nestratili správy, prejdeme na pracovnú schému, ktorá využíva staré aj nové klastre.
Údaje sa zapisujú do chat-členov a užívateľského enginu (a nie do textového enginu, ako pri normálnej prevádzke podľa starej schémy). user-engine zastupuje požiadavku na chat-engine - a tu správanie závisí od toho, či tento chat už bol zlúčený alebo nie. Ak chat ešte nebol zlúčený, chatovací modul si nenapíše správu sám pre seba a jej spracovanie prebieha iba v textovom stroji. Ak už bol chat zlúčený do nástroja na rozhovor, vráti chat_local_id do používateľského nástroja a odošle správu všetkým príjemcom. user-engine proxy všetky dáta do textového motora - takže ak sa niečo stane, vždy sa môžeme vrátiť späť, pričom všetky aktuálne dáta budú v starom engine. textový nástroj vráti user_local_id, ktorý používateľský nástroj uloží a vráti sa späť do backendu.
Výsledkom je, že proces prechodu vyzerá takto: prepojíme prázdne klastre používateľského nástroja a nástroja na rozhovor. chat-engine prečíta celý binlog členov chatu, potom sa spustí proxy podľa schémy opísanej vyššie. Prenesieme staré dáta a získame dva synchronizované klastre (starý a nový). Zostáva len prepnúť čítanie z textového nástroja na používateľský a vypnúť proxy.
výsledky
Vďaka novému prístupu sa zlepšili všetky metriky výkonu motorov a vyriešili sa problémy s konzistenciou dát. Teraz môžeme rýchlo implementovať nové funkcie do správ (a už sme s tým začali – zvýšili sme maximálny počet účastníkov chatu, implementovali vyhľadávanie preposlaných správ, spustili pripnuté správy a zvýšili limit celkového počtu správ na používateľa) .
Zmeny v logike sú skutočne obrovské. A rád by som poznamenal, že to nie vždy znamená celé roky vývoja obrovského tímu a nespočetných riadkov kódu. chat-engine a user-engine spolu so všetkými ďalšími príbehmi, ako je Huffman pre kompresiu správ, Splay stromy a štruktúra pre importované správy, má menej ako 20 tisíc riadkov kódu. A napísali ich 3 vývojári len za 10 mesiacov (je však potrebné mať na pamäti, že - majstri sveta ).
Okrem toho, namiesto zdvojnásobenia počtu serverov, sme ich počet znížili na polovicu – používateľský modul a chatovací modul teraz fungujú na 500 fyzických počítačoch, pričom nová schéma má veľkú rezervu na zaťaženie. Ušetrili sme veľa peňazí na zariadení – približne 5 miliónov dolárov + 750 tisíc dolárov ročne na prevádzkových nákladoch.
Snažíme sa nájsť najlepšie riešenia pre najzložitejšie a rozsiahle problémy. Máme ich veľa – a preto hľadáme šikovných vývojárov do databázového oddelenia. Ak milujete a viete riešiť takéto problémy, máte vynikajúce znalosti o algoritmoch a dátových štruktúrach, pozývame vás do tímu. Kontaktujte našu pre podrobnosti.
Aj keď tento príbeh nie je o vás, uvedomte si, že si ceníme odporúčania. Povedz o tom priateľovi , a ak úspešne dokončí skúšobnú dobu, dostanete bonus 100 tisíc rubľov.
Zdroj: hab.com