Skriv om VKontakte-meddelandedatabasen från början och överlev

Våra användare skriver meddelanden till varandra utan att känna till trötthet.

Det är ganska mycket. Om du satte dig för att läsa alla meddelanden från alla användare skulle det ta mer än 150 tusen år. Förutsatt att du är en ganska avancerad läsare och inte lägger mer än en sekund på varje meddelande.

Med en sådan datamängd är det avgörande att logiken för att lagra och komma åt den är uppbyggd optimalt. Annars, i ett inte så underbart ögonblick, kan det stå klart att allt snart kommer att gå fel.

För oss kom detta ögonblick för ett och ett halvt år sedan. Hur vi kom fram till detta och vad som hände till slut – vi berättar i ordning.

sjukdomshistoria

I den allra första implementeringen fungerade VKontakte-meddelanden på en kombination av PHP-backend och MySQL. Detta är en helt normal lösning för en liten studentwebbplats. Den här sidan växte dock okontrollerat och började kräva optimering av datastrukturer för sig själv.

I slutet av 2009 skrevs det första textmotorförrådet och 2010 överfördes meddelanden till det.

I textmotorn lagrades meddelanden i listor - ett slags "brevlådor". Varje sådan lista bestäms av en uid - användaren som äger alla dessa meddelanden. Ett meddelande har en uppsättning attribut: samtalspartners identifierare, text, bilagor och så vidare. Meddelandeidentifieraren inuti "rutan" är local_id, den ändras aldrig och tilldelas sekventiellt för nya meddelanden. "Lådorna" är oberoende och är inte synkroniserade med varandra inuti motorn, kommunikation mellan dem sker på PHP-nivå. Du kan titta på textmotorns datastruktur och funktioner från insidan här.

Detta var tillräckligt för korrespondens mellan två användare. Gissa vad som hände sedan?

I maj 2011 introducerade VKontakte konversationer med flera deltagare - multichatt. För att arbeta med dem skapade vi två nya kluster - medlemschattar och chattmedlemmar. Den första lagrar data om användares chattar, den andra lagrar data om användare via chattar. Utöver själva listorna inkluderar detta till exempel den inbjudande användaren och tiden då de lades till i chatten.

"PHP, låt oss skicka ett meddelande till chatten", säger användaren.
"Kom igen, {användarnamn}", säger PHP.

Det finns nackdelar med detta system. Synkronisering är fortfarande PHPs ansvar. Stora chattar och användare som samtidigt skickar meddelanden till dem är en farlig historia. Eftersom text-motorinstansen beror på uid, kan chattdeltagare få samma meddelande vid olika tidpunkter. Man skulle kunna leva med detta om framstegen stod stilla. Men det kommer inte att hända.

I slutet av 2015 lanserade vi communitymeddelanden och i början av 2016 lanserade vi ett API för dem. Med tillkomsten av stora chatbots i gemenskaper var det möjligt att glömma jämn belastningsfördelning.

En bra bot genererar flera miljoner meddelanden per dag - även de mest pratglada användarna kan inte skryta med detta. Detta betyder att vissa instanser av textmotorer, som sådana bots levde på, började lida för fullt.

Meddelandemotorer under 2016 är 100 instanser av chattmedlemmar och medlemschattar och 8000 textmotorer. De fanns på tusen servrar, var och en med 64 GB minne. Som en första nödåtgärd utökade vi minnet med ytterligare 32 GB. Vi uppskattade prognoserna. Utan drastiska förändringar skulle detta räcka i ungefär ett år till. Du behöver antingen få tag i hårdvara eller optimera själva databaserna.

På grund av arkitekturens natur är det bara meningsfullt att öka hårdvaran i multipler. Det vill säga att åtminstone fördubbla antalet bilar – uppenbarligen är detta en ganska dyr väg. Vi kommer att optimera.

Nytt koncept

Den centrala kärnan i det nya tillvägagångssättet är chatt. En chatt har en lista med meddelanden som relaterar till den. Användaren har en lista med chattar.

Det minsta nödvändiga är två nya databaser:

• chattmotor. Detta är ett förråd av chattvektorer. Varje chatt har en vektor av meddelanden som relaterar till den. Varje meddelande har en text och en unik meddelandeidentifierare i chatten - chat_local_id.
• användarmotor. Detta är en lagring av användarvektorer - länkar till användare. Varje användare har en vektor av peer_id (samtalare - andra användare, multichatt eller gemenskaper) och en vektor av meddelanden. Varje peer_id har en vektor av meddelanden som relaterar till den. Varje meddelande har ett chat_local_id och ett unikt meddelande-ID för den användaren - user_local_id.

Nya kluster kommunicerar med varandra med hjälp av TCP - detta säkerställer att ordningen på förfrågningar inte ändras. Själva förfrågningarna och bekräftelserna för dem registreras på hårddisken - så vi kan återställa tillståndet för kön när som helst efter ett fel eller omstart av motorn. Eftersom användarmotorn och chattmotorn är på 4 tusen shards vardera, kommer förfrågningskön mellan klustren att fördelas jämnt (men i verkligheten finns det ingen alls - och det fungerar väldigt snabbt).

Att arbeta med disk i våra databaser bygger i de flesta fall på en kombination av en binär logg över ändringar (binlog), statiska ögonblicksbilder och en delbild i minnet. Ändringar under dagen skrivs till en binlog, och en ögonblicksbild av det aktuella tillståndet skapas med jämna mellanrum. En ögonblicksbild är en samling datastrukturer optimerade för våra syften. Den består av en rubrik (metaindex för bilden) och en uppsättning metafiler. Rubriken lagras permanent i RAM och indikerar var man ska leta efter data från ögonblicksbilden. Varje metafil innehåller data som sannolikt kommer att behövas vid en nära tidpunkt – till exempel relaterad till en enskild användare. När du frågar databasen med hjälp av ögonblicksbildshuvudet läses den nödvändiga metafilen och sedan beaktas ändringar i binloggen som inträffade efter att ögonblicksbilden skapades. Du kan läsa mer om fördelarna med detta tillvägagångssätt här.

Samtidigt ändras data på själva hårddisken bara en gång om dagen - sent på natten i Moskva, när belastningen är minimal. Tack vare detta (med att veta att strukturen på skivan är konstant under hela dagen) har vi råd att ersätta vektorer med arrayer av en fast storlek - och på grund av detta öka minnet.

Att skicka ett meddelande i det nya schemat ser ut så här:

1. PHP-backend kontaktar användarmotorn med en begäran om att skicka ett meddelande.
2. user-engine proxar begäran till den önskade chattmotorinstansen, som återgår till user-engine chat_local_id - en unik identifierare för ett nytt meddelande i denna chatt. Chattmotorn sänder sedan meddelandet till alla mottagare i chatten.
3. user-engine tar emot chat_local_id från chat-engine och returnerar user_local_id till PHP - en unik meddelandeidentifierare för denna användare. Denna identifierare används sedan till exempel för att arbeta med meddelanden via API:et.

Men förutom att faktiskt skicka meddelanden måste du implementera några fler viktiga saker:

• Underlistor är till exempel de senaste meddelandena som du ser när du öppnar konversationslistan. Olästa meddelanden, meddelanden med taggar ("Viktigt", "Spam", etc.).
• Komprimera meddelanden i chattmotorn
• Cachar meddelanden i användarmotorn
• Sök (genom alla dialogrutor och inom en specifik).
• Realtidsuppdatering (Longpolling).
• Spara historik för att implementera cachelagring på mobila klienter.

Alla underlistor förändras snabbt strukturer. För att arbeta med dem använder vi Splay träd. Detta val förklaras av det faktum att vi i toppen av trädet ibland lagrar ett helt segment av meddelanden från en ögonblicksbild - till exempel, efter nattlig omindexering, består trädet av en topp, som innehåller alla meddelanden i underlistan. Splayträdet gör det enkelt att sätta in i mitten av en sådan vertex utan att behöva tänka på balansering. Dessutom lagrar Splay inte onödig data, vilket sparar oss minne.

Meddelanden innefattar en stor mängd information, mest text, vilket är användbart för att kunna komprimera. Det är viktigt att vi korrekt kan avarkivera även ett enskilt meddelande. Används för att komprimera meddelanden Huffman algoritm med vår egen heuristik - till exempel vet vi att ord i meddelanden alternerar med "icke-ord" - mellanslag, skiljetecken - och vi kommer också ihåg några av särdragen med att använda symboler för det ryska språket.

Eftersom det finns mycket färre användare än chattar, för att spara diskförfrågningar med slumpmässig åtkomst i chattmotorn, cachelagrar vi meddelanden i användarmotorn.

Meddelandesökning implementeras som en diagonal fråga från användarmotor till alla chattmotorinstanser som innehåller chattar för denna användare. Resultaten kombineras i själva användarmotorn.

Jo, alla detaljer har tagits i beaktande, det återstår bara att byta till ett nytt schema – och helst utan att användarna märker det.

Datamigrering

Så vi har en textmotor som lagrar meddelanden efter användare, och två kluster chattmedlemmar och medlemschattar som lagrar data om multichattrum och användarna i dem. Hur går man från detta till den nya användarmotorn och chattmotorn?

medlemschattar i det gamla schemat användes främst för optimering. Vi överförde snabbt nödvändig data från den till chattmedlemmar, och sedan deltog den inte längre i migreringsprocessen.

Kö för chattmedlemmar. Den inkluderar 100 instanser, medan chattmotorn har 4 tusen. För att överföra data måste du anpassa dem - för detta delades chattmedlemmar upp i samma 4 tusen exemplar, och sedan aktiverades läsning av chattmedlemmarnas binlog i chattmotorn.

Nu känner chattmotorn till multichatt från chattmedlemmar, men den vet ännu inget om dialoger med två samtalspartner. Sådana dialoger finns i textmotorn med hänvisning till användare. Här tog vi data "head-on": varje chat-motor-instans frågade alla text-motor-instanser om de hade den dialog som behövs.

Bra - chattmotorn vet vilka multichattchattar det finns och vet vilka dialoger som finns.
Du måste kombinera meddelanden i multichattchattar så att du får en lista med meddelanden i varje chatt. Först hämtar chattmotorn alla användarmeddelanden från denna chatt från textmotorn. I vissa fall finns det ganska många av dem (upp till hundratals miljoner), men med mycket sällsynta undantag passar chatten helt i RAM. Vi har oordnade meddelanden, vart och ett i flera exemplar - trots allt är de alla hämtade från olika textmotorinstanser som motsvarar användare. Målet är att sortera meddelanden och bli av med kopior som tar onödigt utrymme.

Varje meddelande har en tidsstämpel som innehåller tiden det skickades och text. Vi använder tid för sortering - vi placerar pekare till de äldsta meddelandena från multichatdeltagare och jämför hash från texten i de avsedda kopiorna, och går mot att öka tidsstämpeln. Det är logiskt att kopiorna kommer att ha samma hash och tidsstämpel, men i praktiken är det inte alltid så. Som ni minns utfördes synkroniseringen i det gamla schemat av PHP - och i sällsynta fall skilde sig tiden för att skicka samma meddelande mellan olika användare. I dessa fall tillät vi oss själva att redigera tidsstämpeln - vanligtvis inom en sekund. Det andra problemet är olika ordning på meddelanden för olika mottagare. I sådana fall tillät vi att en extra kopia skapades, med olika beställningsalternativ för olika användare.

Efter detta skickas data om meddelanden i multichatt till användarmotorn. Och här kommer ett obehagligt inslag i importerade meddelanden. Vid normal drift ordnas meddelanden som kommer till motorn strikt i stigande ordning efter user_local_id. Meddelanden som importerats från den gamla motorn till användarmotorn förlorade denna användbara egenskap. Samtidigt, för att underlätta testningen, måste du snabbt kunna komma åt dem, leta efter något i dem och lägga till nya.

Vi använder en speciell datastruktur för att lagra importerade meddelanden.

Den representerar en vektor av storlek var är alla - är olika och ordnade i fallande ordning, med en speciell ordning av element. I varje segment med index elementen sorteras. Att söka efter ett element i en sådan struktur tar tid genom binära sökningar. Tillägg av ett element skrivs av .

Så vi kom på hur man överför data från gamla motorer till nya. Men denna process tar flera dagar - och det är osannolikt att våra användare under dessa dagar kommer att ge upp vanan att skriva till varandra. För att inte tappa meddelanden under denna tid byter vi till ett arbetsschema som använder både gamla och nya kluster.

Data skrivs till chattmedlemmar och användarmotor (och inte till textmotor, som vid normal drift enligt det gamla schemat). user-engine proxar förfrågan till chat-motor - och här beror beteendet på om denna chatt redan har slagits samman eller inte. Om chatten ännu inte har slagits samman, skriver inte chattmotorn meddelandet till sig själv, och dess bearbetning sker endast i textmotorn. Om chatten redan har slagits samman till chattmotorn returnerar den chat_local_id till användarmotorn och skickar meddelandet till alla mottagare. user-engine proxar all data till text-engine - så att om något händer kan vi alltid rulla tillbaka, med all aktuell data i den gamla motorn. text-engine returnerar user_local_id, som användarmotor lagrar och återgår till backend.

Som ett resultat ser övergångsprocessen ut så här: vi kopplar ihop tomma användarmotor- och chattmotorkluster. chattmotorn läser hela chattmedlemmarnas binlog, sedan startar proxy enligt schemat som beskrivs ovan. Vi överför den gamla datan och får två synkroniserade kluster (gamla och nya). Allt som återstår är att byta läsning från text-motor till användarmotor och inaktivera proxy.

Resultat

Tack vare det nya tillvägagångssättet har alla prestandamått för motorerna förbättrats och problem med datakonsistens har lösts. Nu kan vi snabbt implementera nya funktioner i meddelanden (och har redan börjat göra detta - vi ökade det maximala antalet chattdeltagare, genomförde en sökning efter vidarebefordrade meddelanden, lanserade fästade meddelanden och höjde gränsen för det totala antalet meddelanden per användare) .

Förändringarna i logik är verkligen enorma. Och jag skulle vilja notera att detta inte alltid betyder hela år av utveckling av ett enormt team och myriader av kodrader. chattmotor och användarmotor tillsammans med alla ytterligare berättelser som Huffman för meddelandekomprimering, Splay-träd och struktur för importerade meddelanden är mindre än 20 tusen rader kod. Och de skrevs av 3 utvecklare på bara 10 månader (det är dock värt att komma ihåg att alla tre utvecklare - världsmästare i sportprogrammering).

Dessutom, istället för att fördubbla antalet servrar, minskade vi antalet med hälften - nu lever användarmotorn och chattmotorn på 500 fysiska maskiner, medan det nya systemet har ett stort utrymme för belastning. Vi sparade mycket pengar på utrustning - cirka 5 miljoner dollar + 750 tusen dollar per år i driftskostnader.

Vi strävar efter att hitta de bästa lösningarna för de mest komplexa och storskaliga problemen. Vi har gott om dem - och det är därför vi letar efter duktiga utvecklare i databasavdelningen. Om du älskar och vet hur man löser sådana problem, har en utmärkt kunskap om algoritmer och datastrukturer, inbjuder vi dig att gå med i teamet. Kontakta vår HRför detaljer.

Även om den här historien inte handlar om dig, observera att vi värdesätter rekommendationer. Berätta för en vän om lediga utvecklare, och om han framgångsrikt slutför provanställningen får du en bonus på 100 tusen rubel.

Källa: will.com