Felhasználóink fáradtság nélkül írnak egymásnak üzeneteket.
Ez elég sok. Ha az összes felhasználó összes üzenetét elolvasná, az több mint 150 ezer évbe telne. Feltéve, ha eléggé haladó olvasó vagy, és legfeljebb egy másodpercet szánsz minden üzenetre.
Ilyen mennyiségű adat esetén kritikus fontosságú, hogy az adatok tárolásának és elérésének logikája optimálisan épüljön fel. Ellenkező esetben egy nem túl csodálatos pillanatban világossá válhat, hogy hamarosan minden balul sül el.
Számunkra ez a pillanat másfél éve jött el. Hogyan jutottunk el idáig, és mi történt a végén - sorban elmondjuk.
kórtörténet
A legelső megvalósításban a VKontakte üzenetek a PHP háttérrendszer és a MySQL kombinációján működtek. Ez egy teljesen normális megoldás egy kis tanulói weboldal számára. Ez az oldal azonban ellenőrizhetetlenül növekedett, és elkezdte követelni magának az adatstruktúrák optimalizálását.
2009 végén megírták az első szövegmotoros repository-t, 2010-ben az üzenetek is átkerültek rá.
A szöveges motorban az üzeneteket listákban tárolták - egyfajta „postafiókként”. Minden ilyen listát egy felhasználói azonosító határoz meg – az a felhasználó, aki az összes üzenetet birtokolja. Az üzenetnek egy sor attribútuma van: beszélgetőpartner azonosítója, szöveg, mellékletek és így tovább. A „dobozban” lévő üzenetazonosító local_id, soha nem változik, és az új üzenetekhez szekvenciálisan hozzárendelődik. A „dobozok” függetlenek és nincsenek egymással szinkronban a motoron belül, a kommunikáció közöttük PHP szinten történik. Belülről tekintheti meg a text-engine adatszerkezetét és képességeit .
Ez elég volt két felhasználó közötti levelezéshez. Képzeld, mi történt ezután?
2011 májusában a VKontakte több résztvevővel folytatott beszélgetéseket – több csevegést. A velük való együttműködés érdekében két új klasztert hoztunk létre: a tag-csevegéseket és a chat-tagokat. Az első a felhasználók csevegéseiről tárol adatokat, a második a csevegésenkénti felhasználókról tárol adatokat. Magukon a listákon kívül ide tartozik például a meghívó felhasználó és az idő, amikor hozzáadták a chathez.
„PHP, küldjünk üzenetet a chatnek” – mondja a felhasználó.
„Gyerünk, {felhasználónév}” – mondja a PHP.
Ennek a rendszernek vannak hátrányai. A szinkronizálás továbbra is a PHP feladata. Veszélyes történet a nagy csevegés és a nekik egyidejűleg üzenetet küldő felhasználók. Mivel a szövegmotor-példány az uid-től függ, a chat résztvevői különböző időpontokban kaphatják meg ugyanazt az üzenetet. Ezzel együtt lehetne élni, ha a fejlődés megállna. De ez nem fog megtörténni.
2015 végén elindítottuk a közösségi üzeneteket, 2016 elején pedig egy API-t. A nagy chatbotok közösségekben való megjelenésével el lehetett felejteni az egyenletes terheléselosztást.
Egy jó bot naponta több millió üzenetet generál – ezzel még a legbeszédesebb felhasználók sem dicsekedhetnek. Ez azt jelenti, hogy a szövegmotor egyes példányai, amelyeken ilyen botok éltek, a legteljesebb mértékben szenvedtek.
Az üzenetmotorok 2016-ban 100 chat-tag és tag-csevegés, valamint 8000 szöveges motor. Ezer szerveren voltak tárolva, mindegyik 64 GB memóriával. Első sürgősségi intézkedésként további 32 GB-tal növeltük a memóriát. Megbecsültük az előrejelzéseket. Drasztikus változtatások nélkül ez még körülbelül egy évre elegendő lenne. Meg kell szereznie a hardvert, vagy optimalizálnia kell magukat az adatbázisokat.
Az architektúra jellegéből adódóan a hardvert csak többszörösére van értelme növelni. Vagyis az autók számának legalább megkétszerezése - nyilvánvalóan ez meglehetősen drága út. Optimalizálni fogjuk.
Új koncepció
Az új megközelítés központi lényege a chat. A csevegésnek van egy listája a hozzá kapcsolódó üzenetekről. A felhasználónak van egy listája a csevegésekről.
A szükséges minimum két új adatbázis:
- chat-motor. Ez a chat vektorok tárháza. Minden csevegésnek van egy vektora a hozzá kapcsolódó üzenetekből. Minden üzenethez tartozik egy szöveg és egy egyedi üzenetazonosító a csevegésen belül – chat_local_id.
- felhasználói motor. Ez a felhasználói vektorok tárolója - a felhasználókhoz mutató hivatkozások. Minden felhasználó rendelkezik egy peer_id vektorral (beszélgetőpartnerek – más felhasználók, több chat vagy közösségek) és egy üzenetvektor. Minden peer_id egy vektorral rendelkezik a hozzá kapcsolódó üzenetekből. Minden üzenetnek van egy chat_local_id és egy egyedi üzenetazonosítója az adott felhasználóhoz – user_local_id.
Az új klaszterek TCP-n keresztül kommunikálnak egymással – ez biztosítja, hogy a kérések sorrendje ne változzon. Maguk a kérések és a hozzájuk tartozó visszaigazolások a merevlemezen rögzítésre kerülnek – így a sor állapotát bármikor visszaállíthatjuk egy meghibásodás vagy a motor újraindítása után. Mivel a felhasználói motor és a chat-motor egyenként 4 ezer szilánkból áll, a kérési sor egyenletesen oszlik el a fürtök között (de a valóságban egyáltalán nincs - és nagyon gyorsan működik).
Az adatbázisunkban lévő lemezekkel végzett munka a legtöbb esetben a változások bináris naplójának (binlog), statikus pillanatképeknek és a memóriában lévő részképnek a kombinációján alapul. A napközbeni változásokat a rendszer egy binlogba írja, és időszakonként pillanatképet készít az aktuális állapotról. A pillanatkép a céljainkra optimalizált adatstruktúrák gyűjteménye. Ez egy fejlécből (a kép metaindexéből) és egy metafájlokból áll. A fejléc állandóan a RAM-ban van tárolva, és jelzi, hogy hol kell adatokat keresni a pillanatképből. Minden metafájl olyan adatokat tartalmaz, amelyekre valószínűleg közeli időpontokban szükség lesz – például egyetlen felhasználóhoz kapcsolódóan. Amikor lekérdezi az adatbázist a pillanatkép fejlécével, a rendszer beolvassa a szükséges metafájlt, majd figyelembe veszi a binlogban a pillanatkép létrehozása után bekövetkezett változásokat. Ennek a megközelítésnek az előnyeiről bővebben olvashat .
Ugyanakkor a merevlemezen lévő adatok csak naponta egyszer változnak - késő este Moszkvában, amikor a terhelés minimális. Ennek köszönhetően (tudván, hogy a lemez szerkezete a nap folyamán állandó), megengedhetjük magunknak, hogy a vektorokat fix méretű tömbökre cseréljük - és ennek köszönhetően a memória növelése.
Az üzenetküldés az új sémában így néz ki:
- A PHP háttérrendszer felveszi a kapcsolatot a felhasználói motorral egy üzenet küldésére vonatkozó kéréssel.
- A user-engine a kérést a kívánt csevegőmotor-példányhoz rendeli, amely visszatér a user-engine chat_local_id azonosítójához – ez a chat-en belüli új üzenet egyedi azonosítója. A chat_engine ezután sugározza az üzenetet a csevegésben résztvevő összes címzettnek.
- A user-engine megkapja a chat_local_id-t a chat-engine-től, és visszaadja a user_local_id-t a PHP-nek – ez a felhasználó egyedi üzenetazonosítója. Ezt az azonosítót azután például az API-n keresztüli üzenetek kezelésére használják.
Az üzenetek küldésén túl azonban még néhány fontos dolgot kell végrehajtania:
- Az allisták például azok a legutóbbi üzenetek, amelyeket a beszélgetéslista megnyitásakor lát. Olvasatlan üzenetek, címkékkel ellátott üzenetek ("Fontos", "Spam" stb.).
- Üzenetek tömörítése chat-motorban
- Üzenetek gyorsítótárazása a felhasználói motorban
- Keresés (az összes párbeszédpanelen és egy adott párbeszédpanelen belül).
- Valós idejű frissítés (Longpolling).
- Előzmények mentése a gyorsítótárazás megvalósításához mobil klienseken.
Minden allista gyorsan változó szerkezet. A velük való együttműködéshez használjuk . Ezt a választást az magyarázza, hogy a fa tetején időnként egy pillanatképből származó üzenetek egész szegmensét tároljuk - például éjszakai újraindexelés után a fa egy felső részből áll, amely az allista összes üzenetét tartalmazza. A Splay fa segítségével könnyen beilleszthető egy ilyen csúcs közepébe anélkül, hogy az egyensúlyozásra kellene gondolnia. Ráadásul a Splay nem tárol felesleges adatokat, amivel memóriát takarítunk meg.
Az üzenetek nagy mennyiségű információt tartalmaznak, többnyire szöveget, ami hasznos a tömörítéshez. Fontos, hogy akár egyetlen üzenetet is pontosan ki tudjunk archiválni. Üzenetek tömörítésére szolgál saját heurisztikáinkkal - például tudjuk, hogy az üzenetekben a szavak váltakoznak a „nem szavakkal” - szóközökkel, írásjelekkel -, és emlékezünk az orosz nyelv szimbólumhasználatának néhány sajátosságára is.
Mivel sokkal kevesebb felhasználó van, mint csevegő, a véletlen hozzáférésű lemezkérelmek chat-motorba való mentéséhez az üzeneteket a felhasználói motorban gyorsítótárazzuk.
Az üzenetkeresés átlós lekérdezésként valósul meg a felhasználói motortól minden olyan csevegőmotor-példány felé, amely a felhasználó csevegéseit tartalmazza. Az eredményeket magában a felhasználói motorban kombinálják.
Nos, minden részletet figyelembe vettek, csak át kell váltani egy új sémára - és lehetőleg anélkül, hogy a felhasználók észrevennék.
Adatmigrálás
Tehát van egy szöveges motorunk, amely felhasználónként tárolja az üzeneteket, és két fürt chat-tagok és tag-chat, amelyek adatokat tárolnak a több chat szobákról és a bennük lévő felhasználókról. Hogyan lehet áttérni erről az új felhasználói motorra és chat-motorra?
A régi sémában a tag-chatet elsősorban az optimalizáláshoz használták. Gyorsan átvittük róla a szükséges adatokat a chat-tagoknak, majd a migrációs folyamatban már nem vett részt.
Várólista a chat-tagoknak. 100 példányt tartalmaz, míg a chat-motorban 4 ezer. Az adatok átviteléhez megfelelővé kell tenni azokat - ehhez a chat-tagokat ugyanabba a 4 ezer példányba osztották fel, majd engedélyezték a chat-tagok binlogjának olvasását a chat-motorban.
A chat-motor most már tud a chat-tagok multi-chatjéről, de még nem tud semmit a két beszélgetőpartnerrel folytatott párbeszédről. Az ilyen párbeszédek a szövegmotorban találhatók a felhasználókra hivatkozva. Itt „fejjel” vettük az adatokat: minden chat-motor-példány megkérdezte az összes szövegmotor-példányt, hogy megvan-e a szükséges párbeszéd.
Nagyszerű – a chat-motor tudja, hogy milyen több chat-csevegés létezik, és tudja, milyen párbeszédek vannak.
Kombinálnia kell az üzeneteket a többcsevegésben, hogy a végén minden csevegésben megjelenjen az üzenetek listája. Először is, a chat-motor lekéri a szöveges motorból az összes felhasználói üzenetet ebből a csevegésből. Egyes esetekben elég sok van belőlük (akár több száz millió), de nagyon ritka kivételektől eltekintve a chat teljes mértékben belefér a RAM-ba. Rendeletlen üzeneteink vannak, mindegyik több példányban – elvégre mindegyik a felhasználóknak megfelelő szövegmotor-példányokból származik. A cél az üzenetek rendezése és a felesleges helyet foglaló másolatok megszabadulása.
Minden üzenethez tartozik egy időbélyeg, amely tartalmazza az elküldés idejét és a szöveget. Időt használunk a válogatásra - mutatunk a multichat résztvevőinek legrégebbi üzeneteire, és összehasonlítjuk a kivonatokat a tervezett másolatok szövegéből, haladva az időbélyeg növelése felé. Logikus, hogy a másolatokon ugyanaz a hash és időbélyeg lesz, de a gyakorlatban ez nem mindig van így. Mint emlékszel, a szinkronizálást a régi sémában a PHP végezte - és ritka esetekben ugyanazon üzenet küldésének időpontja különbözött a különböző felhasználók között. Ezekben az esetekben megengedtük magunknak az időbélyeg szerkesztését – általában egy másodpercen belül. A második probléma az üzenetek eltérő sorrendje a különböző címzetteknél. Ilyen esetekben engedélyeztük egy plusz másolat készítését, a különböző felhasználók számára eltérő rendelési lehetőséggel.
Ezt követően a multichat üzenetekkel kapcsolatos adatok elküldésre kerülnek a felhasználói motornak. És itt jön egy kellemetlen tulajdonsága az importált üzeneteknek. Normál működés közben a motorhoz érkező üzenetek szigorúan növekvő sorrendben vannak rendezve a user_local_id szerint. A régi motorból a felhasználói motorba importált üzenetek elvesztették ezt a hasznos tulajdonságot. Ugyanakkor a tesztelés kényelme érdekében gyorsan hozzá kell férni, keresni kell bennük valamit, és újakat kell hozzáadni.
Az importált üzenetek tárolására speciális adatstruktúrát használunk.
Egy méretvektort jelöl hol van mindenki - különbözőek és csökkenő sorrendben vannak rendezve, az elemek speciális sorrendjével. Minden szegmensben indexekkel az elemek rendezve vannak. Egy ilyen szerkezetben lévő elem keresése időt vesz igénybe keresztül bináris keresések. Egy elem hozzáadását amortizálják .
Tehát kitaláltuk, hogyan vihetünk át adatokat a régi motorokról az újakra. De ez a folyamat több napot vesz igénybe – és nem valószínű, hogy ezalatt a napok alatt a felhasználók felhagynának azzal a szokással, hogy írjanak egymásnak. Annak érdekében, hogy ez idő alatt ne veszítsenek el üzenetek, átváltunk egy olyan munkasémára, amely régi és új fürtöket is használ.
Az adatok a chat-tagokba és a felhasználói motorba íródnak (és nem a szövegmotorba, mint a régi séma szerint). A user-engine a chat-engine-hez közvetíti a kérést – és itt a viselkedés attól függ, hogy a csevegést már összevonták-e vagy sem. Ha a chat még nincs összevonva, akkor a chat-motor nem írja meg magának az üzenetet, feldolgozása csak a szövegmotorban történik. Ha a csevegést már egyesítették a chat-motorral, akkor a chat_local_id értéket adja vissza a user-engine-nek, és elküldi az üzenetet az összes címzettnek. A user-engine az összes adatot a text-engine-hez proxyzza – így ha valami történik, mindig vissza tudjuk görgetni, mivel az összes aktuális adat a régi motorban van. A text-engine visszaadja a user_local_id-t, amelyet a felhasználói motor tárol, és visszatér a háttérrendszerbe.
Ennek eredményeként az átállási folyamat a következőképpen néz ki: üres felhasználói-motor és chat-motor klasztereket kapcsolunk össze. chat-engine beolvassa a teljes chat-members binlogot, majd elindul a proxy a fent leírt séma szerint. Átvisszük a régi adatokat, és két szinkronizált klasztert kapunk (régi és új). Már csak az olvasást át kell váltani szöveg-motorról felhasználói motorra, és letiltani a proxyt.
Álláspontja
Az új megközelítésnek köszönhetően a motorok összes teljesítménymutatója javult, és az adatok konzisztenciájával kapcsolatos problémák megoldódtak. Mostantól gyorsan bevezethetünk új funkciókat az üzenetekbe (és ezt már elkezdtük – megnöveltük a chatben résztvevők maximális számát, bevezettük a továbbított üzenetek keresését, elindítottuk a rögzített üzeneteket és megemeltük a felhasználónkénti üzenetek teljes számának korlátját) .
A logikai változások valóban óriásiak. És szeretném megjegyezni, hogy ez nem mindig jelent egy hatalmas csapat egész éves fejlesztését és számtalan kódsort. chat-motor és user-engine, valamint az összes további történet, mint a Huffman az üzenettömörítéshez, a Splay fák és az importált üzenetek struktúrája kevesebb, mint 20 ezer sornyi kód. És 3 fejlesztő írta őket mindössze 10 hónap alatt (de érdemes észben tartani, hogy - világbajnokok ).
Sőt, a szerverek számának megduplázása helyett felére csökkentettük a számukat – immár 500 fizikai gépen él a felhasználói motor és a chat-motor, miközben az új rendszerben nagy a terhelési tér. Rengeteg pénzt takarítottunk meg a berendezéseken – körülbelül 5 millió dollárt + 750 ezer dollárt évente a működési költségeken.
Arra törekszünk, hogy a legösszetettebb és legnagyszabásúbb problémákra is megtaláljuk a legjobb megoldást. Rengeteg belőlük van – ezért keresünk tehetséges fejlesztőket az adatbázis-osztályra. Ha szereted és tudod, hogyan kell megoldani az ilyen problémákat, kiválóan ismered az algoritmusokat és az adatstruktúrákat, akkor csatlakozz a csapathoz. Lépjen kapcsolatba velünk a részletekért.
Még ha ez a történet nem is rólad szól, kérjük, vegye figyelembe, hogy nagyra értékeljük az ajánlásokat. Mondja el egy barátjának , és ha sikeresen teljesíti a próbaidőt, akkor 100 ezer rubel bónuszt kap.
Forrás: will.com