Onze gebruikers schrijven berichten naar elkaar zonder vermoeidheid te kennen.
Dat is best veel. Als je alle berichten van alle gebruikers zou willen lezen, zou dat ruim 150 jaar duren. Op voorwaarde dat je een redelijk gevorderde lezer bent en niet meer dan een seconde aan elk bericht besteedt.
Met een dergelijke hoeveelheid gegevens is het van cruciaal belang dat de logica voor het opslaan en openen ervan optimaal is opgebouwd. Anders kan het op een niet zo geweldig moment duidelijk worden dat alles snel mis zal gaan.
Voor ons kwam dit moment anderhalf jaar geleden. Hoe we hiertoe zijn gekomen en wat er uiteindelijk is gebeurd, vertellen we u in volgorde.
anamnese
In de allereerste implementatie werkten VKontakte-berichten op een combinatie van PHP-backend en MySQL. Dit is een volkomen normale oplossing voor een kleine studentenwebsite. Deze site groeide echter ongecontroleerd en begon voor zichzelf optimalisatie van datastructuren te eisen.
Eind 2009 werd de eerste repository voor tekstengines geschreven en in 2010 werden er berichten naartoe overgebracht.
In de tekstengine werden berichten opgeslagen in lijsten - een soort "mailboxen". Elke dergelijke lijst wordt bepaald door een uid: de gebruiker die eigenaar is van al deze berichten. Een bericht heeft een reeks kenmerken: identificatie van de gesprekspartner, tekst, bijlagen, enzovoort. De bericht-ID in de “box” is local_id, deze verandert nooit en wordt opeenvolgend toegewezen aan nieuwe berichten. De “boxen” zijn onafhankelijk en zijn niet met elkaar gesynchroniseerd in de engine; de communicatie daartussen vindt plaats op PHP-niveau. U kunt de datastructuur en mogelijkheden van de tekst-engine van binnenuit bekijken .
Dit was voldoende voor correspondentie tussen twee gebruikers. Raad eens wat er daarna gebeurde?
In mei 2011 introduceerde VKontakte gesprekken met verschillende deelnemers: multi-chat. Om met hen samen te werken hebben we twee nieuwe clusters opgericht: ledenchats en chatleden. De eerste slaat gegevens op over chats van gebruikers, de tweede slaat gegevens op over gebruikers door chats. Naast de lijsten zelf bevat dit bijvoorbeeld de uitnodigende gebruiker en het tijdstip waarop deze aan de chat is toegevoegd.
“PHP, laten we een bericht naar de chat sturen”, zegt de gebruiker.
“Kom op, {gebruikersnaam}”, zegt PHP.
Er zijn nadelen aan deze regeling. Synchronisatie is nog steeds de verantwoordelijkheid van PHP. Grote chats en gebruikers die er tegelijkertijd berichten naar sturen, zijn een gevaarlijk verhaal. Omdat de instantie van de tekstengine afhankelijk is van de uid, kunnen chatdeelnemers hetzelfde bericht op verschillende tijdstippen ontvangen. Je zou hiermee kunnen leven als de vooruitgang stilstond. Maar dat zal niet gebeuren.
Eind 2015 lanceerden we communityberichten en begin 2016 lanceerden we er een API voor. Met de komst van grote chatbots in communities was het mogelijk om de gelijkmatige verdeling van de lasten te vergeten.
Een goede bot genereert enkele miljoenen berichten per dag - zelfs de meest spraakzame gebruikers kunnen daar niet over opscheppen. Dit betekent dat sommige gevallen van tekst-engine, waarop dergelijke bots leefden, ten volle begonnen te lijden.
Berichtenengines in 2016 zijn 100 exemplaren van chatleden en ledenchats, en 8000 tekstengines. Ze werden gehost op duizend servers, elk met 64 GB geheugen. Als eerste noodmaatregel hebben we het geheugen met nog eens 32 GB vergroot. Wij hebben de voorspellingen geschat. Zonder drastische veranderingen zou dit genoeg zijn voor nog een jaar. U moet hardware aanschaffen of de databases zelf optimaliseren.
Vanwege de aard van de architectuur is het alleen zinvol om de hardware in veelvouden uit te breiden. Dat wil zeggen, op zijn minst een verdubbeling van het aantal auto's - dit is uiteraard een vrij dure weg. Wij zullen optimaliseren.
Nieuw concept
De centrale essentie van de nieuwe aanpak is chat. Een chat bevat een lijst met berichten die hierop betrekking hebben. De gebruiker heeft een lijst met chats.
Het vereiste minimum is twee nieuwe databases:
- chat-engine. Dit is een opslagplaats van chatvectoren. Elke chat heeft een vector van berichten die daarop betrekking hebben. Elk bericht heeft een tekst en een unieke bericht-ID in de chat: chat_local_id.
- gebruikers-engine. Dit is een opslag van gebruikersvectoren - links naar gebruikers. Elke gebruiker heeft een vector van peer_id (gesprekspartners - andere gebruikers, multi-chat of communities) en een vector van berichten. Elke peer_id heeft een vector van berichten die daarop betrekking hebben. Elk bericht heeft een chat_local_id en een unieke bericht-ID voor die gebruiker: user_local_id.
Nieuwe clusters communiceren met elkaar via TCP - dit zorgt ervoor dat de volgorde van de verzoeken niet verandert. De verzoeken zelf en de bevestigingen ervan worden op de harde schijf vastgelegd, zodat we de status van de wachtrij op elk moment kunnen herstellen na een storing of herstart van de motor. Omdat de gebruikers-engine en chat-engine elk vierduizend shards bevatten, zal de wachtrij voor verzoeken gelijkmatig over de clusters worden verdeeld (maar in werkelijkheid is er helemaal geen - en het werkt erg snel).
Het werken met schijf in onze databases is in de meeste gevallen gebaseerd op een combinatie van een binair logboek van wijzigingen (binlog), statische snapshots en een gedeeltelijke afbeelding in het geheugen. Wijzigingen gedurende de dag worden naar een binlog geschreven en er wordt periodiek een momentopname van de huidige status gemaakt. Een momentopname is een verzameling gegevensstructuren die voor onze doeleinden zijn geoptimaliseerd. Het bestaat uit een header (metaindex van de afbeelding) en een reeks metabestanden. De header wordt permanent opgeslagen in het RAM en geeft aan waar naar gegevens uit de momentopname moet worden gezocht. Elk metabestand bevat gegevens die waarschijnlijk op korte tijdstippen nodig zijn, bijvoorbeeld gerelateerd aan een enkele gebruiker. Wanneer u de database doorzoekt met behulp van de snapshot-header, wordt het vereiste metabestand gelezen en wordt er rekening gehouden met de wijzigingen in de binlog die plaatsvonden nadat de snapshot was gemaakt. U kunt meer lezen over de voordelen van deze aanpak .
Tegelijkertijd veranderen de gegevens op de harde schijf zelf slechts één keer per dag - laat in de nacht in Moskou, wanneer de belasting minimaal is. Dankzij dit (wetende dat de structuur op de schijf de hele dag constant is), kunnen we het ons veroorloven om vectoren te vervangen door arrays van een vaste grootte - en daardoor geheugenwinst.
Het verzenden van een bericht in het nieuwe schema ziet er als volgt uit:
- De PHP-backend neemt contact op met de user-engine met het verzoek een bericht te sturen.
- user-engine stuurt het verzoek door naar de gewenste instantie van de chat-engine, die terugkeert naar user-engine chat_local_id - een unieke identificatie van een nieuw bericht binnen deze chat. De chat_engine zendt het bericht vervolgens uit naar alle ontvangers in de chat.
- user-engine ontvangt chat_local_id van chat-engine en retourneert user_local_id naar PHP - een unieke bericht-ID voor deze gebruiker. Deze identifier wordt vervolgens gebruikt om bijvoorbeeld met berichten via de API te werken.
Maar naast het daadwerkelijk verzenden van berichten, moet je nog een paar belangrijke dingen implementeren:
- Sublijsten zijn bijvoorbeeld de meest recente berichten die je ziet als je de conversatielijst opent. Ongelezen berichten, berichten met tags (“Belangrijk”, “Spam”, enz.).
- Berichten comprimeren in de chat-engine
- Berichten cachen in de gebruikersengine
- Zoeken (door alle dialoogvensters en binnen een specifiek dialoogvenster).
- Realtime update (Longpolling).
- Geschiedenis opslaan om caching op mobiele clients te implementeren.
Alle sublijsten zijn snel veranderende structuren. Om ermee te werken, gebruiken we . Deze keuze wordt verklaard door het feit dat we bovenaan de boom soms een heel segment berichten uit een momentopname opslaan - na een nachtelijke herindexering bestaat de boom bijvoorbeeld uit één top, die alle berichten van de sublijst bevat. De Splay-boom maakt het gemakkelijk om in het midden van zo'n hoekpunt te plaatsen zonder dat je hoeft na te denken over balanceren. Bovendien slaat Splay geen onnodige gegevens op, wat ons geheugen bespaart.
Berichten bevatten een grote hoeveelheid informatie, meestal tekst, wat handig is om te kunnen comprimeren. Het is belangrijk dat we zelfs één individueel bericht nauwkeurig kunnen uit het archief halen. Wordt gebruikt om berichten te comprimeren met onze eigen heuristieken - we weten bijvoorbeeld dat woorden in berichten worden afgewisseld met 'niet-woorden' - spaties, leestekens - en we herinneren ons ook enkele eigenaardigheden van het gebruik van symbolen voor de Russische taal.
Omdat er veel minder gebruikers zijn dan chats, slaan we berichten in de gebruikersengine op in de cache om schijfverzoeken met willekeurige toegang in de chat-engine op te slaan.
Het zoeken naar berichten wordt geïmplementeerd als een diagonale zoekopdracht van de gebruikersengine naar alle instanties van de chatengine die chats van deze gebruiker bevatten. De resultaten worden gecombineerd in de gebruikersengine zelf.
Welnu, met alle details is rekening gehouden, het enige dat overblijft is overstappen naar een nieuw schema - en het liefst zonder dat gebruikers het merken.
Data migratie
We hebben dus een tekstengine die berichten per gebruiker opslaat, en twee clusters chatleden en ledenchats die gegevens opslaan over multi-chatrooms en de gebruikers daarin. Hoe kun je hiervan overstappen naar de nieuwe gebruikers-engine en chat-engine?
Member-chats in het oude schema werden voornamelijk gebruikt voor optimalisatie. We hebben de benodigde gegevens snel van hem overgezet naar chatleden, waarna hij niet langer deelnam aan het migratieproces.
Wachtrij voor chatleden. Het bevat 100 exemplaren, terwijl de chat-engine er 4 heeft. Om de gegevens over te dragen, moet u deze in overeenstemming brengen - hiervoor werden chatleden verdeeld in dezelfde 4 exemplaren, en vervolgens werd het lezen van de binlog van chatleden ingeschakeld in de chat-engine.
Nu weet de chat-engine van multi-chat van chatleden, maar nog niets van dialogen met twee gesprekspartners. Dergelijke dialogen bevinden zich in de tekstengine met verwijzing naar gebruikers. Hier hebben we de gegevens “frontaal” genomen: elke chat-engine-instantie vroeg alle tekst-engine-instanties of ze de dialoog hadden die nodig was.
Geweldig - de chat-engine weet welke multi-chat-chats er zijn en welke dialogen er zijn.
U moet berichten in multi-chatchats combineren, zodat u in elke chat een lijst met berichten krijgt. Eerst haalt de chat-engine alle gebruikersberichten uit deze chat op uit de tekst-engine. In sommige gevallen zijn het er behoorlijk veel (tot honderden miljoenen), maar op zeer zeldzame uitzonderingen na past de chat volledig in het RAM-geheugen. We hebben ongeordende berichten, elk in verschillende kopieën - ze worden tenslotte allemaal opgehaald uit verschillende tekstengine-instanties die overeenkomen met gebruikers. Het doel is om berichten te sorteren en kopieën te verwijderen die onnodige ruimte in beslag nemen.
Elk bericht heeft een tijdstempel met het tijdstip waarop het is verzonden en de tekst. We gebruiken tijd om te sorteren - we plaatsen verwijzingen naar de oudste berichten van multichat-deelnemers en vergelijken hashes van de tekst van de beoogde kopieën, waarbij we de tijdstempel vergroten. Het is logisch dat de kopieën dezelfde hash en tijdstempel hebben, maar in de praktijk is dit niet altijd het geval. Zoals u zich herinnert, werd de synchronisatie in het oude schema uitgevoerd door PHP - en in zeldzame gevallen verschilde het tijdstip waarop hetzelfde bericht werd verzonden tussen verschillende gebruikers. In deze gevallen hebben we onszelf toegestaan de tijdstempel te bewerken, meestal binnen een seconde. Het tweede probleem is de verschillende volgorde van berichten voor verschillende ontvangers. In dergelijke gevallen hebben we toegestaan dat er een extra exemplaar werd gemaakt, met verschillende bestelopties voor verschillende gebruikers.
Hierna worden gegevens over berichten in multichat naar de gebruikersengine gestuurd. En hier komt een onaangenaam kenmerk van geïmporteerde berichten. Bij normaal gebruik worden berichten die naar de engine komen strikt in oplopende volgorde gerangschikt op user_local_id. Berichten die vanuit de oude engine in de gebruikersengine werden geïmporteerd, verloren deze nuttige eigenschap. Tegelijkertijd moet u, voor het gemak van het testen, er snel toegang toe hebben, er iets in kunnen zoeken en nieuwe kunnen toevoegen.
We gebruiken een speciale datastructuur om geïmporteerde berichten op te slaan.
Het vertegenwoordigt een vector van grootte waar is iedereen - zijn verschillend en geordend in aflopende volgorde, met een speciale volgorde van elementen. In elk segment met indexen elementen zijn gesorteerd. Het zoeken naar een element in zo’n structuur kost tijd door binaire zoekopdrachten. Over de toevoeging van een element wordt afgeschreven .
Dus we hebben ontdekt hoe we gegevens van oude naar nieuwe motoren kunnen overbrengen. Maar dit proces duurt enkele dagen - en het is onwaarschijnlijk dat onze gebruikers gedurende deze dagen de gewoonte zullen opgeven om naar elkaar te schrijven. Om in deze tijd geen berichten kwijt te raken, stappen we over op een werkschema dat gebruik maakt van zowel oude als nieuwe clusters.
Gegevens worden naar chatleden en gebruikersengine geschreven (en niet naar tekstengine, zoals bij normaal gebruik volgens het oude schema). user-engine proxy's het verzoek aan chat-engine - en hier hangt het gedrag af van of deze chat al is samengevoegd of niet. Als de chat nog niet is samengevoegd, schrijft de chat-engine het bericht niet naar zichzelf en vindt de verwerking ervan alleen plaats in de tekst-engine. Als de chat al is samengevoegd in de chat-engine, retourneert deze chat_local_id naar de gebruikers-engine en wordt het bericht naar alle ontvangers verzonden. user-engine stuurt alle gegevens naar de tekst-engine - zodat we, als er iets gebeurt, altijd terug kunnen gaan, waarbij we alle huidige gegevens in de oude engine hebben. text-engine retourneert user_local_id, welke user-engine opslaat en terugkeert naar de backend.
Als gevolg hiervan ziet het transitieproces er als volgt uit: we verbinden lege user-engine- en chat-engine-clusters. chat-engine leest de volledige binlog van chatleden, waarna proxying begint volgens het hierboven beschreven schema. We dragen de oude gegevens over en krijgen twee gesynchroniseerde clusters (oud en nieuw). Het enige dat overblijft is het lezen van de tekst-engine naar de gebruikers-engine over te schakelen en proxying uit te schakelen.
Bevindingen
Dankzij de nieuwe aanpak zijn alle prestatiegegevens van de motoren verbeterd en zijn problemen met de gegevensconsistentie opgelost. Nu kunnen we snel nieuwe functies in berichten implementeren (en we zijn hier al mee begonnen - we hebben het maximale aantal chatdeelnemers verhoogd, een zoekopdracht naar doorgestuurde berichten geïmplementeerd, vastgezette berichten gelanceerd en de limiet voor het totale aantal berichten per gebruiker verhoogd) .
De veranderingen in de logica zijn werkelijk enorm. En ik zou willen opmerken dat dit niet altijd hele jaren van ontwikkeling betekent door een enorm team en talloze regels code. chat-engine en gebruikers-engine samen met alle aanvullende verhalen zoals Huffman voor berichtcompressie, Splay-bomen en structuur voor geïmporteerde berichten is minder dan 20 regels code. En ze zijn in slechts 3 maanden door drie ontwikkelaars geschreven (het is echter de moeite waard om dat in gedachten te houden). - wereld Kampioenen ).
Bovendien hebben we, in plaats van het aantal servers te verdubbelen, het aantal met de helft teruggebracht - nu leven de gebruikers-engine en chat-engine op 500 fysieke machines, terwijl het nieuwe schema veel ruimte biedt voor belasting. We hebben veel geld bespaard op apparatuur: ongeveer $ 5 miljoen + $ 750 per jaar aan bedrijfskosten.
Wij streven ernaar om de beste oplossingen te vinden voor de meest complexe en grootschalige problemen. We hebben er genoeg - en daarom zijn we op zoek naar getalenteerde ontwikkelaars op de databaseafdeling. Als je van dergelijke problemen houdt en weet hoe je deze moet oplossen, en als je een uitstekende kennis hebt van algoritmen en datastructuren, nodigen we je uit om je bij het team aan te sluiten. Neem contact op met onze voor details.
Zelfs als dit verhaal niet over jou gaat, houd er dan rekening mee dat we aanbevelingen op prijs stellen. Vertel een vriend erover , en als hij de proeftijd met succes voltooit, ontvangt u een bonus van 100 duizend roebel.
Bron: www.habr.com