Våre brukere skriver meldinger til hverandre uten å føle seg slitne.
Det er ganske mye. Hvis du ville lese alle meldingene til alle brukere, ville det ta mer enn 150 tusen år. Forutsatt at du er en ganske avansert leser og ikke bruker mer enn ett sekund på hver melding.
Med et slikt datavolum er det avgjørende at logikken for lagring og tilgang til dem bygges optimalt. Ellers, i et ikke så fantastisk øyeblikk, kan det bli klart at alt snart vil gå galt.
For oss kom dette øyeblikket for halvannet år siden. Hvordan vi kom til dette og hva som skjedde til slutt - vi forteller deg i rekkefølge.
case historie
I den aller første implementeringen fungerte VKontakte-meldinger på en kombinasjon av PHP-backend og MySQL. Dette er en helt vanlig løsning for et lite studentnettsted. Imidlertid vokste dette nettstedet ukontrollert og begynte å kreve optimalisering av datastrukturer for seg selv.
På slutten av 2009 ble det første tekstmotorlageret skrevet, og i 2010 ble meldinger overført til det.
I tekstmotoren ble meldinger lagret i lister - en slags "postbokser". Hver slik liste bestemmes av en uid - brukeren som eier alle disse meldingene. En melding har et sett med attributter: samtalepartneridentifikator, tekst, vedlegg og så videre. Meldingsidentifikatoren inne i "boksen" er local_id, den endres aldri og tildeles sekvensielt for nye meldinger. "Kassene" er uavhengige og er ikke synkronisert med hverandre inne i motoren; kommunikasjon mellom dem skjer på PHP-nivå. Du kan se på datastrukturen og egenskapene til tekstmotoren fra innsiden .
Dette var nok for korrespondanse mellom to brukere. Gjett hva som skjedde videre?
I mai 2011 introduserte VKontakte samtaler med flere deltakere - multichat. For å jobbe med dem, reiste vi to nye klynger – medlemschatter og chat-medlemmer. Den første lagrer data om chatter av brukere, den andre lagrer data om brukere via chatter. I tillegg til selve listene inkluderer dette for eksempel den inviterende brukeren og tidspunktet de ble lagt til i chatten.
"PHP, la oss sende en melding til chatten," sier brukeren.
«Kom igjen, {brukernavn}», sier PHP.
Det er ulemper med denne ordningen. Synkronisering er fortsatt PHPs ansvar. Store chatter og brukere som samtidig sender meldinger til dem er en farlig historie. Siden tekstmotorforekomsten avhenger av uid, kan chatdeltakere motta den samme meldingen til forskjellige tider. Man kunne levd med dette hvis fremgangen sto stille. Men det vil ikke skje.
På slutten av 2015 lanserte vi fellesskapsmeldinger, og i begynnelsen av 2016 lanserte vi en API for dem. Med bruken av store chatbots i fellesskap, var det mulig å glemme jevn lastfordeling.
En god bot genererer flere millioner meldinger per dag – selv de mest pratsomme brukerne kan ikke skryte av dette. Dette betyr at noen forekomster av tekstmotorer, som slike roboter levde på, begynte å lide til det fulle.
Meldingsmotorer i 2016 er 100 forekomster av chat-medlemmer og medlemschatter, og 8000 tekstmotorer. De var vert på tusen servere, hver med 64 GB minne. Som et første nødtiltak økte vi minnet med ytterligere 32 GB. Vi estimerte prognosene. Uten drastiske endringer ville dette vært nok i omtrent ett år til. Du må enten få tak i maskinvare eller optimalisere selve databasene.
På grunn av arkitekturens natur er det bare fornuftig å øke maskinvaren i multipler. Det vil si minst en dobling av antall biler – åpenbart er dette en ganske dyr vei. Vi skal optimalisere.
Nytt konsept
Den sentrale essensen av den nye tilnærmingen er chat. En chat har en liste over meldinger som er relatert til den. Brukeren har en liste over chatter.
Minimumskravet er to nye databaser:
- chat-motor. Dette er et oppbevaringssted for chat-vektorer. Hver chat har en vektor av meldinger som er relatert til den. Hver melding har en tekst og en unik meldingsidentifikator inne i chatten - chat_local_id.
- brukermotor. Dette er en lagring av brukervektorer - lenker til brukere. Hver bruker har en vektor av peer_id (samtaler - andre brukere, multi-chat eller fellesskap) og en vektor av meldinger. Hver peer_id har en vektor av meldinger som er relatert til den. Hver melding har en chat_local_id og en unik meldings-ID for den brukeren - user_local_id.
Nye klynger kommuniserer med hverandre ved hjelp av TCP - dette sikrer at rekkefølgen på forespørsler ikke endres. Selve forespørslene og bekreftelser for dem registreres på harddisken - slik at vi kan gjenopprette tilstanden til køen når som helst etter en feil eller omstart av motoren. Siden bruker-motoren og chat-motoren er på 4 tusen shards hver, vil forespørselskøen mellom klyngene fordeles jevnt (men i virkeligheten er det ingen i det hele tatt - og det fungerer veldig raskt).
Arbeid med disk i våre databaser er i de fleste tilfeller basert på en kombinasjon av en binær logg over endringer (binlog), statiske øyeblikksbilder og et delvis bilde i minnet. Endringer i løpet av dagen skrives til en binlog, og et øyeblikksbilde av gjeldende tilstand opprettes med jevne mellomrom. Et øyeblikksbilde er en samling av datastrukturer optimalisert for våre formål. Den består av en overskrift (metaindeks av bildet) og et sett med metafiler. Overskriften er permanent lagret i RAM og indikerer hvor du skal lete etter data fra øyeblikksbildet. Hver metafil inneholder data som sannsynligvis vil være nødvendig på nært hold – for eksempel relatert til en enkelt bruker. Når du forespør databasen ved hjelp av øyeblikksbildehodet, leses den nødvendige metafilen, og endringer i binloggen som skjedde etter at øyeblikksbildet ble opprettet, tas med i betraktning. Du kan lese mer om fordelene med denne tilnærmingen .
Samtidig endres dataene på selve harddisken bare en gang om dagen - sent på kvelden i Moskva, når belastningen er minimal. Takket være dette (ved å vite at strukturen på disken er konstant gjennom dagen), har vi råd til å erstatte vektorer med arrays av en fast størrelse - og på grunn av dette øke minnet.
Å sende en melding i den nye ordningen ser slik ut:
- PHP-backend kontakter brukermotoren med en forespørsel om å sende en melding.
- user-engine prokserer forespørselen til ønsket chat-engine-forekomst, som returnerer til user-engine chat_local_id - en unik identifikator for en ny melding i denne chatten. Chat_motoren sender deretter meldingen til alle mottakere i chatten.
- user-engine mottar chat_local_id fra chat-engine og returnerer user_local_id til PHP - en unik meldingsidentifikator for denne brukeren. Denne identifikatoren brukes deretter for eksempel til å jobbe med meldinger via API.
Men i tillegg til å faktisk sende meldinger, må du implementere noen flere viktige ting:
- Underlister er for eksempel de siste meldingene du ser når du åpner samtalelisten. Uleste meldinger, meldinger med tagger ("Viktig", "Spam", etc.).
- Komprimering av meldinger i chat-motor
- Bufre meldinger i brukermotoren
- Søk (gjennom alle dialoger og innenfor en bestemt).
- Sanntidsoppdatering (Longpolling).
- Lagre historikk for å implementere caching på mobile klienter.
Alle underlister endrer strukturer raskt. For å jobbe med dem bruker vi . Dette valget forklares av det faktum at vi på toppen av treet noen ganger lagrer et helt segment av meldinger fra et øyeblikksbilde - for eksempel, etter nattlig reindeksering, består treet av en topp, som inneholder alle meldingene i underlisten. Splay-treet gjør det enkelt å sette inn i midten av et slikt toppunkt uten å måtte tenke på balansering. I tillegg lagrer ikke Splay unødvendige data, noe som sparer oss for minne.
Meldinger involverer en stor mengde informasjon, mest tekst, som er nyttig å kunne komprimere. Det er viktig at vi nøyaktig kan dearkivere selv én enkelt melding. Brukes til å komprimere meldinger med vår egen heuristikk - for eksempel vet vi at i meldinger veksler ord med "ikke-ord" - mellomrom, skilletegn - og vi husker også noen av særegenhetene ved å bruke symboler for det russiske språket.
Siden det er mye færre brukere enn chatter, lagrer vi meldinger i brukermotoren for å lagre diskforespørsler med tilfeldig tilgang i chat-motoren.
Meldingssøk implementeres som en diagonal spørring fra brukermotor til alle chat-motorforekomster som inneholder chatter fra denne brukeren. Resultatene kombineres i selve brukermotoren.
Vel, alle detaljer er tatt i betraktning, det gjenstår bare å bytte til en ny ordning – og helst uten at brukerne legger merke til det.
Datamigrering
Så vi har en tekstmotor som lagrer meldinger etter bruker, og to klynger chat-medlemmer og medlemschatter som lagrer data om multi-chatterom og brukerne i dem. Hvordan gå fra denne til den nye bruker- og chat-motoren?
medlemschatter i det gamle opplegget ble først og fremst brukt til optimalisering. Vi overførte raskt de nødvendige dataene fra den til chat-medlemmer, og deretter deltok den ikke lenger i migreringsprosessen.
Kø for chat-medlemmer. Den inkluderer 100 forekomster, mens chat-motoren har 4 tusen. For å overføre dataene, må du bringe dem i samsvar - for dette ble chat-medlemmer delt inn i de samme 4 tusen eksemplarene, og deretter ble lesing av chat-medlemmers binlog aktivert i chat-motoren.
Nå kjenner chat-motoren til multichat fra chat-medlemmer, men den vet ennå ikke noe om dialoger med to samtalepartnere. Slike dialoger er plassert i tekstmotoren med referanse til brukere. Her tok vi dataene "head-on": hver chat-motor-forekomst spurte alle tekst-motor-forekomster om de hadde dialogen den trengte.
Flott - chat-motoren vet hvilke multichat-chatter det er og vet hvilke dialoger det er.
Du må kombinere meldinger i multichat-chatter slik at du ender opp med en liste over meldinger i hver chat. Først henter chat-motoren alle brukermeldinger fra denne chatten fra tekstmotoren. I noen tilfeller er det ganske mange av dem (opptil hundrevis av millioner), men med svært sjeldne unntak passer chatten helt inn i RAM. Vi har uordnede meldinger, hver i flere eksemplarer - tross alt er de alle hentet fra forskjellige tekstmotorforekomster som tilsvarer brukere. Målet er å sortere meldinger og kvitte seg med kopier som tar opp unødvendig plass.
Hver melding har et tidsstempel som inneholder klokkeslettet den ble sendt og tekst. Vi bruker tid til sortering - vi plasserer pekere til de eldste meldingene til multichatdeltakere og sammenligner hashes fra teksten til de tiltenkte kopiene, og beveger oss mot å øke tidsstemplet. Det er logisk at kopiene vil ha samme hasj og tidsstempel, men i praksis er det ikke alltid slik. Som du husker, ble synkronisering i det gamle opplegget utført av PHP - og i sjeldne tilfeller var tidspunktet for sending av samme melding forskjellig mellom forskjellige brukere. I disse tilfellene tillot vi oss selv å redigere tidsstemplet – vanligvis i løpet av et sekund. Det andre problemet er den forskjellige rekkefølgen av meldinger for forskjellige mottakere. I slike tilfeller tillot vi å lage en ekstra kopi, med ulike bestillingsmuligheter for ulike brukere.
Etter dette sendes data om meldinger i multichat til brukermotoren. Og her kommer et ubehagelig trekk ved importerte meldinger. Ved normal drift blir meldinger som kommer til motoren sortert strengt i stigende rekkefølge etter user_local_id. Meldinger importert fra den gamle motoren til brukermotoren mistet denne nyttige egenskapen. Samtidig, for å gjøre det enklere å teste, må du raskt kunne få tilgang til dem, se etter noe i dem og legge til nye.
Vi bruker en spesiell datastruktur for å lagre importerte meldinger.
Den representerer en vektor av størrelse Hvor er alle sammen - er forskjellige og ordnet i synkende rekkefølge, med en spesiell rekkefølge av elementer. I hvert segment med indekser elementene er sortert. Å lete etter et element i en slik struktur tar tid gjennom binære søk. Tillegg av et element amortiseres over .
Så vi fant ut hvordan vi overfører data fra gamle motorer til nye. Men denne prosessen tar flere dager - og det er usannsynlig at brukerne våre i løpet av disse dagene vil gi opp vanen med å skrive til hverandre. For ikke å miste meldinger i denne tiden går vi over til et arbeidsopplegg som bruker både gamle og nye klynger.
Data skrives til chat-medlemmer og brukermotor (og ikke til tekstmotor, som ved normal drift i henhold til den gamle ordningen). user-engine fullfører forespørselen til chat-motor - og her avhenger oppførselen av om denne chatten allerede er slått sammen eller ikke. Hvis chatten ennå ikke er slått sammen, skriver ikke chat-motoren meldingen til seg selv, og behandlingen skjer kun i tekstmotoren. Hvis chatten allerede er slått sammen til chat-motor, returnerer den chat_local_id til brukermotor og sender meldingen til alle mottakere. user-engine prokserer alle data til tekstmotor - slik at hvis noe skjer, kan vi alltid rulle tilbake, med alle gjeldende data i den gamle motoren. text-engine returnerer user_local_id, som brukermotor lagrer og returnerer til backend.
Som et resultat ser overgangsprosessen slik ut: vi kobler sammen tomme brukermotor- og chat-motorklynger. chat-motoren leser hele chat-medlemmers binlog, deretter starter proxying i henhold til skjemaet beskrevet ovenfor. Vi overfører de gamle dataene og får to synkroniserte klynger (gamle og nye). Alt som gjenstår er å bytte lesing fra tekstmotor til brukermotor og deaktivere proxying.
Funn
Takket være den nye tilnærmingen har alle ytelsesmålinger for motorene blitt forbedret og problemer med datakonsistens er løst. Nå kan vi raskt implementere nye funksjoner i meldinger (og har allerede begynt å gjøre dette - vi økte det maksimale antallet chattedeltakere, implementerte et søk etter videresendte meldinger, lanserte festede meldinger og hevet grensen for totalt antall meldinger per bruker) .
Endringene i logikken er virkelig enorme. Og jeg vil merke meg at dette ikke alltid betyr hele år med utvikling av et stort team og myriader av kodelinjer. chat-motor og brukermotor sammen med alle tilleggshistoriene som Huffman for meldingskomprimering, Splay-trær og struktur for importerte meldinger er mindre enn 20 tusen linjer med kode. Og de ble skrevet av 3 utviklere på bare 10 måneder (det er imidlertid verdt å huske på at - verdensmestere ).
Dessuten, i stedet for å doble antallet servere, reduserte vi antallet med det halve - nå lever brukermotoren og chat-motoren på 500 fysiske maskiner, mens den nye ordningen har stor takhøyde for belastning. Vi sparte mye penger på utstyr - ca $5 millioner + $750 tusen per år i driftsutgifter.
Vi streber etter å finne de beste løsningene for de mest komplekse og storskala problemene. Vi har nok av dem - og derfor ser vi etter dyktige utviklere i databaseavdelingen. Hvis du elsker og vet hvordan du løser slike problemer, har utmerket kunnskap om algoritmer og datastrukturer, inviterer vi deg til å bli med på laget. Kontakt vår for detaljer.
Selv om denne historien ikke handler om deg, vær oppmerksom på at vi verdsetter anbefalinger. Fortell en venn om , og hvis han fullfører prøvetiden, vil du motta en bonus på 100 tusen rubler.
Kilde: www.habr.com