Přepište databázi zpráv VKontakte od nuly a přežijte

Naši uživatelé si píší zprávy, aniž by si byli vědomi únavy.

To je docela hodně. Pokud byste se vydali číst všechny zprávy všech uživatelů, trvalo by to více než 150 tisíc let. Za předpokladu, že jste poměrně pokročilý čtenář a strávíte na každé zprávě maximálně sekundu.

Při takovém objemu dat je důležité, aby logika pro jejich ukládání a přístup k nim byla postavena optimálně. V opačném případě může být v jeden nepříliš úžasný okamžik jasné, že se vše brzy pokazí.

Pro nás tento okamžik nastal před rokem a půl. Jak jsme k tomu přišli a co se nakonec stalo - vám řekneme v pořádku.

Pozadí

V úplně první implementaci fungovaly zprávy VKontakte na kombinaci PHP backendu a MySQL. Pro malý studentský web je to zcela běžné řešení. Tento web však nekontrolovatelně rostl a začal pro sebe vyžadovat optimalizaci datových struktur.

Na konci roku 2009 bylo napsáno první textové úložiště a v roce 2010 do něj byly přeneseny zprávy.

V textovém motoru byly zprávy ukládány do seznamů - jakési „poštovní schránky“. Každý takový seznam je určen uid - uživatelem, který vlastní všechny tyto zprávy. Zpráva má sadu atributů: identifikátor partnera, text, přílohy a tak dále. Identifikátor zprávy uvnitř „boxu“ je local_id, nikdy se nemění a je přidělován postupně pro nové zprávy. „Schránky“ jsou nezávislé a nejsou vzájemně synchronizovány uvnitř enginu, komunikace mezi nimi probíhá na úrovni PHP. Na datovou strukturu a možnosti textového stroje se můžete podívat zevnitř zde.

To bylo docela dost pro korespondenci mezi dvěma uživateli. Hádejte, co se dělo dál?

V květnu 2011 VKontakte představil konverzace s několika účastníky — multichat. Abychom s nimi mohli pracovat, vytvořili jsme dva nové skupiny – členské chaty a chatové členy. První ukládá data o chatech podle uživatelů, druhá ukládá data o uživatelích podle chatů. Kromě samotných seznamů sem patří například zvoucí uživatel a čas, kdy byl do chatu přidán.

„PHP, pošleme zprávu do chatu,“ říká uživatel.
"No tak, {username}," říká PHP.

Toto schéma má nevýhody. Synchronizace je stále v kompetenci PHP. Velké chaty a uživatelé, kteří jim současně posílají zprávy, jsou nebezpečný příběh. Vzhledem k tomu, že instance textového stroje závisí na uid, mohli účastníci chatu obdržet stejnou zprávu v různých časech. S tím by se dalo žít, kdyby se pokrok zastavil. Ale to se nestane.

Na konci roku 2015 jsme spustili komunitní zprávy a začátkem roku 2016 jsme pro ně spustili API. S příchodem velkých chatbotů v komunitách bylo možné zapomenout na rovnoměrné rozložení zátěže.

Dobrý bot generuje několik milionů zpráv denně - ani ti nejupovídanější uživatelé se tím nemohou pochlubit. To znamená, že některé případy textového stroje, na kterém takoví boti žili, začaly trpět naplno.

Moduly zpráv v roce 2016 jsou 100 instancí členů chatu a členských chatů a 8000 textových modulů. Byly hostovány na tisícovce serverů, každý s 64 GB paměti. Jako první nouzové opatření jsme navýšili paměť o dalších 32 GB. Odhadovali jsme předpovědi. Bez razantních změn by to vystačilo zhruba na další rok. Musíte buď sehnat hardware, nebo optimalizovat databáze samotné.

Vzhledem k povaze architektury má smysl navyšovat hardware pouze v násobcích. Tedy minimálně zdvojnásobení počtu aut – zjevně jde o poměrně drahou cestu. Budeme optimalizovat.

Nový koncept

Ústřední podstatou nového přístupu je chat. Chat obsahuje seznam zpráv, které se k němu vztahují. Uživatel má seznam chatů.

Požadované minimum jsou dvě nové databáze:

• chat-engine. Toto je úložiště chatových vektorů. Každý chat má vektor zpráv, které se ho týkají. Každá zpráva má v chatu text a jedinečný identifikátor zprávy – chat_local_id.
• uživatelský motor. Jedná se o úložiště uživatelských vektorů - odkazů na uživatele. Každý uživatel má vektor peer_id (partneri – ostatní uživatelé, multichat nebo komunity) a vektor zpráv. Každé peer_id má vektor zpráv, které se k němu vztahují. Každá zpráva má chat_local_id a jedinečné ID zprávy pro daného uživatele – user_local_id.

Nové clustery spolu komunikují pomocí TCP – tím je zajištěno, že se pořadí požadavků nemění. Samotné požadavky a potvrzení k nim se zaznamenávají na pevný disk – stav fronty tak můžeme kdykoli po poruše nebo restartu motoru obnovit. Vzhledem k tomu, že uživatel-engine a chat-engine jsou po 4 tisících útržků, bude fronta požadavků mezi clustery rozdělena rovnoměrně (ale ve skutečnosti neexistuje vůbec žádná - a funguje to velmi rychle).

Práce s diskem v našich databázích je ve většině případů založena na kombinaci binárního protokolu změn (binlog), statických snímků a částečného obrazu v paměti. Změny během dne se zapisují do binlogu a pravidelně se vytváří snímek aktuálního stavu. Snímek je kolekce datových struktur optimalizovaných pro naše účely. Skládá se z hlavičky (metaindexu obrázku) a sady metasouborů. Hlavička je trvale uložena v paměti RAM a označuje, kde hledat data ze snímku. Každý metasoubor obsahuje data, která budou pravděpodobně potřeba v nejbližších okamžicích – například související s jedním uživatelem. Při dotazu na databázi pomocí záhlaví snímku se přečte požadovaný metasoubor a poté se zohlední změny v binlogu, ke kterým došlo po vytvoření snímku. O výhodách tohoto přístupu si můžete přečíst více zde.

Data na samotném pevném disku se přitom mění jen jednou denně – pozdě v noci v Moskvě, kdy je zátěž minimální. Díky tomu (s vědomím, že struktura na disku je konstantní po celý den) si můžeme dovolit nahradit vektory poli pevné velikosti – a díky tomu získat paměť.

Odeslání zprávy v novém schématu vypadá takto:

1. PHP backend kontaktuje uživatelský engine s požadavkem na odeslání zprávy.
2. user-engine předá požadavek požadované instanci nástroje chatu, která se vrátí na chat_local_id uživatelského nástroje - jedinečný identifikátor nové zprávy v rámci tohoto chatu. Chat_engine poté odešle zprávu všem příjemcům v chatu.
3. user-engine obdrží chat_local_id z chat-engine a vrátí user_local_id do PHP - jedinečný identifikátor zprávy pro tohoto uživatele. Tento identifikátor pak slouží například pro práci se zprávami přes API.

Ale kromě skutečného odesílání zpráv musíte implementovat několik důležitých věcí:

• Dílčí seznamy jsou například nejnovější zprávy, které vidíte při otevření seznamu konverzací. Nepřečtené zprávy, zprávy se štítky („Důležité“, „Spam“ atd.).
• Komprese zpráv v chatovacím modulu
• Ukládání zpráv do mezipaměti v uživatelském enginu
• Hledat (ve všech dialogových oknech a v rámci jednoho konkrétního).
• Aktualizace v reálném čase (Longpolling).
• Ukládání historie za účelem implementace ukládání do mezipaměti na mobilních klientech.

Všechny podseznamy rychle mění strukturu. K práci s nimi používáme Rozvětvené stromy. Tato volba se vysvětluje tím, že v horní části stromu někdy ukládáme celý segment zpráv ze snímku – například po noční reindexaci se strom skládá z jednoho vrcholu, který obsahuje všechny zprávy podseznamu. Strom Splay umožňuje snadné vložení do středu takového vrcholu, aniž byste museli přemýšlet o vyvážení. Splay navíc neukládá zbytečná data, což nám šetří paměť.

Zprávy obsahují velké množství informací, většinou textu, které je užitečné zkomprimovat. Je důležité, abychom mohli přesně zrušit archivaci i jedné jednotlivé zprávy. Používá se ke kompresi zpráv Huffmanův algoritmus s vlastní heuristikou - například víme, že ve zprávách se slova střídají s „neslovy“ - mezerami, interpunkčními znaménky - a také si pamatujeme některé rysy používání symbolů pro ruský jazyk.

Vzhledem k tomu, že existuje mnohem méně uživatelů než chatů, ukládáme zprávy do mezipaměti v uživatelském modulu, abychom ušetřili požadavky na disk s náhodným přístupem v modulu chatu.

Vyhledávání zpráv je implementováno jako diagonální dotaz z uživatelského modulu do všech instancí nástroje chatu, které obsahují chaty tohoto uživatele. Výsledky jsou kombinovány v samotném uživatelském motoru.

No, všechny detaily byly zohledněny, zbývá jen přejít na nové schéma – a nejlépe, aniž by si toho uživatelé všimli.

Migrace dat

Máme tedy textový stroj, který ukládá zprávy podle uživatelů, a dva clustery členů chatu a členské chaty, které ukládají data o multichatovacích místnostech a uživatelích v nich. Jak přejít z tohoto na nový uživatelský a chatovací modul?

členské chaty ve starém schématu sloužily především k optimalizaci. Rychle jsme z něj přenesli potřebná data členům chatu a pak se již neúčastnil procesu migrace.

Fronta pro členy chatu. Zahrnuje 100 instancí, zatímco chat-engine má 4 tisíce. Chcete-li data přenést, musíte je uvést do souladu - za tímto účelem byli členové chatu rozděleni do stejných 4 tisíc kopií a poté bylo v modulu chatu povoleno čtení binlogu členů chatu.

Nyní chat-engine ví o multichatu od členů chatu, ale zatím neví nic o dialozích se dvěma účastníky rozhovoru. Tyto dialogy jsou umístěny v textovém modulu s odkazem na uživatele. Zde jsme vzali data „přímo“: každá instance nástroje pro chat se zeptala všech instancí textového nástroje, zda mají dialog, který potřebují.

Skvělé - chat-engine ví, jaké multichatové chaty existují, a ví, jaké dialogy existují.
V chatech s více chaty je třeba zprávy zkombinovat, abyste nakonec dostali seznam zpráv v každém chatu. Nejprve chat-engine načte z textového modulu všechny uživatelské zprávy z tohoto chatu. V některých případech je jich poměrně hodně (až stovky milionů), ale až na velmi vzácné výjimky se chat vejde celý do RAM. Máme neuspořádané zprávy, každou v několika kopiích – všechny jsou koneckonců staženy z různých instancí textového stroje odpovídajících uživatelům. Cílem je seřadit zprávy a zbavit se kopií, které zabírají zbytečné místo.

Každá zpráva má časové razítko obsahující čas odeslání a text. K třídění využíváme čas – umisťujeme ukazatele na nejstarší zprávy účastníků multichatu a porovnáváme hashe z textu zamýšlených kopií směřující ke zvýšení časového razítka. Je logické, že kopie budou mít stejný hash a časové razítko, ale v praxi tomu tak vždy není. Jak si pamatujete, synchronizaci ve starém schématu provádělo PHP - a ve vzácných případech se čas odeslání stejné zprávy u různých uživatelů lišil. V těchto případech jsme si dovolili upravit časové razítko – většinou během vteřiny. Druhým problémem je různé pořadí zpráv pro různé příjemce. V takových případech jsme umožnili vytvoření další kopie s různými možnostmi objednání pro různé uživatele.

Poté jsou data o zprávách v multichatu odeslána do uživatelského enginu. A zde přichází nepříjemná vlastnost importovaných zpráv. V normálním provozu jsou zprávy, které přicházejí do motoru, seřazeny přesně ve vzestupném pořadí podle user_local_id. Zprávy importované ze starého enginu do uživatelského enginu ztratily tuto užitečnou vlastnost. Zároveň je pro pohodlí testování k nim potřeba mít rychlý přístup, něco v nich hledat a přidávat nové.

K ukládání importovaných zpráv používáme speciální datovou strukturu.

Představuje vektor velikosti kde jsou všichni - jsou různé a seřazené v sestupném pořadí, se zvláštním pořadím prvků. V každém segmentu s indexy prvky jsou seřazeny. Hledání prvku v takové struktuře zabere čas přes binární vyhledávání. Přidání prvku se amortizuje .

Takže jsme přišli na to, jak přenést data ze starých motorů do nových. Tento proces však trvá několik dní – a je nepravděpodobné, že během těchto dnů naši uživatelé opustí zvyk psát si. Abychom během této doby neztratili zprávy, přecházíme na pracovní schéma, které využívá staré i nové clustery.

Data se zapisují do chat-členů a uživatelského modulu (a nikoli do textového modulu, jako v běžném provozu podle starého schématu). user-engine zastupuje požadavek na chat-engine - a zde chování závisí na tom, zda byl tento chat již sloučen nebo ne. Pokud chat ještě nebyl sloučen, chatovací modul si zprávu nezapíše a její zpracování probíhá pouze v textovém modulu. Pokud byl chat již sloučen do modulu chatu, vrátí chat_local_id do uživatelského modulu a odešle zprávu všem příjemcům. user-engine zastupuje všechna data do textového motoru - takže pokud se něco stane, můžeme se vždy vrátit zpět a mít všechna aktuální data ve starém enginu. text-engine vrací user_local_id, které uživatelský engine ukládá a vrací se do backendu.

Výsledkem je, že proces přechodu vypadá takto: propojíme prázdné clustery user-engine a chat-engine. chat-engine přečte celý binlog členů chatu a poté se spustí proxy podle schématu popsaného výše. Přeneseme stará data a získáme dva synchronizované clustery (starý a nový). Zbývá pouze přepnout čtení z textového stroje na uživatelský a zakázat proxy.

výsledky

Díky novému přístupu byly vylepšeny všechny metriky výkonu motorů a vyřešeny problémy s konzistencí dat. Nyní můžeme rychle implementovat nové funkce do zpráv (a již jsme s tím začali – zvýšili jsme maximální počet účastníků chatu, implementovali vyhledávání přeposílaných zpráv, spustili připnuté zprávy a zvýšili limit celkového počtu zpráv na uživatele) .

Změny v logice jsou skutečně obrovské. A rád bych poznamenal, že to nemusí vždy znamenat celé roky vývoje obrovským týmem a myriádami řádků kódu. chat-engine a user-engine spolu se všemi dalšími příběhy, jako je Huffman pro kompresi zpráv, Splay stromy a struktura pro importované zprávy, je méně než 20 tisíc řádků kódu. A napsali je 3 vývojáři za pouhých 10 měsíců (je však třeba mít na paměti, že vše tři vývojář - mistři světa ve sportovním programování).

Kromě toho jsme místo zdvojnásobení počtu serverů snížili jejich počet na polovinu – uživatelský engine a chatovací engine nyní žijí na 500 fyzických strojích, přičemž nové schéma má velkou rezervu pro zatížení. Ušetřili jsme spoustu peněz na vybavení – asi 5 milionů dolarů + 750 tisíc dolarů ročně na provozních nákladech.

Snažíme se najít nejlepší řešení pro nejsložitější a rozsáhlé problémy. Máme jich spoustu – a proto hledáme talentované vývojáře do databázového oddělení. Pokud milujete a umíte řešit takové problémy, máte vynikající znalosti algoritmů a datových struktur, zveme vás do týmu. Kontaktujte naše HRpro detaily.

I když tento příběh není o vás, mějte na paměti, že si ceníme doporučení. Řekněte o tom příteli volná místa pro vývojáře, a pokud úspěšně dokončí zkušební dobu, získáte bonus 100 tisíc rublů.

Zdroj: www.habr.com