2.1 Hvordan sønderdeles og bremses N gange?

Du kan sønderdele og bremse nøjagtig N gange på denne måde:

  • Send docs00...docs15-anmodninger sekventielt , ikke parallelt.
  • I simple forespørgsler skal du foretage et valg ikke med tasten , WHERE something=234.

I dette tilfælde tager den serialiserede del (serielle) ikke 1% og ikke 5%, men omkring 20% ​​i moderne databaser. Du kan også få 50% af den serialiserede del, hvis du tilgår databasen ved hjælp af en vildt effektiv binær protokol eller forbinder den som et dynamisk bibliotek til et Python-script.

Resten af ​​behandlingstiden for en simpel anmodning vil blive optaget af ikke-parallaliserbare operationer med at parse anmodningen, forberede planen osv. Det vil sige, at ikke læsning af posten går langsommere.

Hvis vi deler dataene op i 16 tabeller og kører sekventielt, som det for eksempel er sædvanligt i PHP programmeringssproget (det er ikke særlig godt til at starte asynkrone processer), så får vi en 16-dobbelt afmatning. Og måske endnu mere, fordi netværksrundrejser også vil blive tilføjet.

Pludselig er valget af programmeringssprog vigtigt ved sharding.

Husk valget af programmeringssprog, for hvis du sender forespørgsler til databasen (eller søgeserveren) sekventielt, hvor kommer accelerationen så fra? Der vil snarere være en opbremsning.

2.2 Om halvautomatisk

Nogle steder inspirerer den sofistikerede informationsteknologi til chtonisk rædsel. For eksempel havde MySQL ud af boksen ikke implementeringen af ​​sharding til visse versioner med sikkerhed, men størrelsen af ​​de databaser, der bruges i kamp, ​​vokser til uanstændige værdier.

Lidende medmenneskelighed over for individuelle DBA'er har været plaget i årevis og skriver flere dårlige sønderdelingsløsninger baseret på ingenting. Derefter skrives en mere eller mindre anstændig sharding-løsning kaldet ProxySQL (MariaDB/Spider, PG/pg_shard/Citus, ...). Dette er et velkendt eksempel på netop denne plet.

ProxySQL som helhed er naturligvis en fuldgyldig løsning i virksomhedsklassen til open source, til routing og mere. Men en af ​​opgaverne, der skal løses, er sharding til en database, som i sig selv ikke kan sønderdele på en menneskelig måde. Du kan se, der er ingen "shards = 16" switch, du skal enten omskrive hver anmodning i applikationen, og der er mange af dem nogle steder, eller lægge et mellemliggende lag mellem applikationen og databasen, der ser ud: "Hmm ... VÆLG * FRA dokumenter? Ja, det skal opdeles i 16 små SELECT * FRA server1.dokument1, VÆLG * FRA server2.dokument2 - til denne server med sådan et login / password, til denne med en anden. Hvis man ikke svarede, så ..." osv. Netop dette kan gøres ved mellemliggende klatter. De er lidt mindre end for alle databaser. For PostgreSQL, så vidt jeg forstår,

Konfiguration af hver specifik patch er et separat gigantisk emne, der ikke passer ind i én rapport, så vi vil kun diskutere de grundlæggende begreber. Lad os hellere tale lidt om teorien om buzz.

2.3 Absolut perfekt automatisering?

Hele teorien om at blive høj i tilfælde af sharding i dette bogstav F() , grundprincippet er altid det samme nogenlunde: shard_id = F(objekt).

Sharding - hvad handler det om? Vi har 2 milliarder poster (eller 64). Vi vil dele dem i flere stykker. Et uventet spørgsmål opstår - hvordan? Efter hvilket princip skal jeg sprede mine 2 milliarder poster (eller 64) på ​​16 servere, der er tilgængelige for mig?

Den latente matematiker i os burde foreslå, at der i sidste ende altid er en eller anden magisk funktion, der for hvert dokument (objekt, linje osv.) vil bestemme, hvilken brik det skal lægges i.

Java webinar

Går man dybere ind i matematikken, afhænger denne funktion altid ikke kun af selve objektet (selve rækken), men også af eksterne indstillinger såsom det samlede antal shards. En funktion, der for hvert objekt skal fortælle, hvor den skal placeres, kan ikke returnere en værdi mere, end der er servere i systemet. Og funktionerne er lidt anderledes:

shard_func = F1(object); 
shard_id = F2(shard_func, ...); 
shard_id = F2(F1(object), current_num_shards, ...).

Men yderligere vil vi ikke grave i disse vildmarker af individuelle funktioner, vi vil blot tale om, hvad magiske funktioner F () er.

2.4 Hvad er F()?

De kan komme med mange forskellige og mange forskellige implementeringsmekanismer. Eksempeloversigt:

  • F = rand() % nums_shards
  • F = somehash(objekt.id) % antal_shards
  • F = objekt.dato % antal_shards
  • F = objekt.bruger_id % antal_shards
  • ...
  • F = shard_table [ somehash() |… objekt.dato |… ]

Et interessant faktum - du kan naturligvis sprede alle data tilfældigt - vi smider den næste post på en vilkårlig server, på en vilkårlig kerne, i en vilkårlig tabel. Der vil ikke være meget lykke i dette, men det vil virke.

Der er lidt mere intelligente metoder til at skære ved hjælp af en reproducerbar eller endda konsistent hash-funktion, eller skære efter en eller anden egenskab. Lad os gennemgå hver metode.

F = rand()

At sprede rundt er ikke en særlig korrekt metode. Et problem: vi spredte vores 2 milliarder poster på tusinde servere tilfældigt, og vi ved ikke, hvor posten er. Vi skal trække user_1 ud, men vi ved ikke, hvor han er. Vi går til tusinde servere og sorterer i alt - på en eller anden måde er det ineffektivt.

F = noget hash()

Lad os sprede brugerne på en voksen måde: beregn den reproducerbare hash-funktion fra user_id, tag resten af ​​divisionen efter antallet af servere, og kontakt straks den ønskede server.

Hvorfor gør vi dette? Og så, at vi har en høj belastning og intet andet passer ind i én server. Hvis det passede, ville livet være så enkelt.

Fantastisk, situationen er allerede forbedret, for at få én post, går vi til én kendt server på forhånd. Men hvis vi har en række nøgler, så skal vi i hele dette område gennemgå alle nøglernes værdier og i grænsen enten gå til lige så mange skår, som vi har nøgler i området, eller endda til hver server. Situationen er naturligvis forbedret, men ikke for alle anmodninger. Nogle forespørgsler er blevet påvirket.

Naturlig sharding (F = objekt.dato % antal_shards)

Nogle gange, det vil sige ofte, er 95 % af trafikken og 95 % af belastningen anmodninger, der har en form for naturlig skæring. For eksempel påvirker 95 % af betinget socialanalytiske forespørgsler kun data for den sidste 1 dag, 3 dage, 7 dage, og de resterende 5 % henviser til de sidste par år. Men 95 % af forespørgslerne er således naturligt sønderdelt efter dato, systembrugernes interesse er fokuseret på de sidste par dage.

I dette tilfælde kan du dividere dataene efter dato, for eksempel med én dag, og følge svaret på anmodningen om en rapport for en dag eller et objekt fra denne dag til dette skår og gå.

Livet bliver bedre - vi kender nu ikke kun placeringen af ​​et bestemt objekt, men vi kender også til rækkevidden. Hvis vi ikke bliver bedt om en række datoer, men om en række andre kolonner, så bliver vi selvfølgelig nødt til at gennemgå alle skårene. Men ifølge spillereglerne har vi kun 5 % af sådanne anmodninger.

Det ser ud til, at vi har fundet en ideel løsning på alt, men der er to problemer:

  • Denne løsning er skræddersyet til en specifik sag, hvor 95 % af anmodningerne kun vedrører den sidste uge.
  • Da 95 % af anmodningerne berører den sidste uge, vil de alle falde på ét stykke, der leveres i sidste uge. Dette skår vil smelte, mens alle de andre vil være inaktive i denne tid. Samtidig kan du ikke smide dem ud, arkivdata skal også opbevares.

For ikke at sige, at dette er en dårlig sharding-ordning - vi afskærer varme data, ikke desto mindre skal der gøres noget med det hotteste shard.

Problemet løses ved løjer, spring og omslag, det vil sige en stigning i antallet af replikaer for den brændende aktuelle dag, derefter et gradvist fald i antallet af replikaer, når denne dag bliver fortid og går i arkivet. Der er ingen ideel løsning kaldet "du skal bare sprede dataene over klyngen med en magisk hash-funktion på en forkert måde".

2.5 Pris, der skal betales

Formelt ved vi nu, at vi ved "alt". Sandt nok kender vi ikke en kæmpe hovedpine og to mindre hovedpine.

1. Simpel smerte: dårligt udtværet

Dette er et eksempel fra en lærebog, som næsten aldrig forekommer i kamp, ​​men pludselig.

  • Som et eksempel med en dato, kun uden en dato!
  • Utilsigtet ujævn (opfattelig) fordeling.

De valgte sønderdelingsmekanismen, og/eller dataene blev ændret, og selvfølgelig formidlede PM ikke kravene (vi har ikke fejl i koden, PM rapporterer altid ikke kravene) og distributionen blev uhyrligt ujævn. Det vil sige, at de missede kriteriet.

For at fange skal du se på størrelsen af ​​skårene. Vi vil helt sikkert se problemet i det øjeblik, hvor et af vores skår enten overophedes eller bliver 100 gange større end de andre. Du kan ordne det blot ved at udskifte nøglen eller sønderdelingsfunktionen.

Dette er et simpelt problem, for at være ærlig, jeg tror ikke, at mindst én person ud af hundrede vil løbe ind i dette i livet, men pludselig vil det hjælpe i det mindste nogen.

2. "Uovervindelig" smerte: sammenlægning, deltage

Hvordan foretager man valg, der forbinder en milliard poster fra en tabel til en milliard poster fra en anden tabel?

  • Hvordan regner man "hurtigt" ud... HVOR randcol MELLEM aaa OG bbb?
  • Hvordan gør man "smart"... users_32shards JOIN posts_1024 shards?

Kort svar: nej, lid!

Hvis du distribuerede en milliard poster til tusinde servere i den første tabel, så de arbejder hurtigere, og gjorde det samme i den anden tabel, så burde tusind til tusinde servere naturligvis tale med hinanden i par. En million forbindelser vil ikke fungere godt. Hvis vi laver anmodninger til databasen (søgning, lagring, dokumentlager eller distribueret filsystem), som ikke passer godt til sharding, vil disse anmodninger bremse helt vildt.

En vigtig pointe er , at nogle anmodninger altid vil blive udtværet uden held og vil bremse . Det er vigtigt at forsøge at minimere deres procentdel. Som en konsekvens er der ingen grund til at lave gigantiske sammenføjninger med en milliard gange en milliard poster. Hvis det er muligt at replikere en lille tabel, i forhold til hvilken du deltager i en kæmpe delt tabel, til alle noder, bør du gøre det. Hvis sammenføjningerne faktisk er lokale på en eller anden måde, er det for eksempel muligt at placere brugeren og hans indlæg side om side, sønderdele dem på samme måde og udføre alle sammenføjningerne inden for samme maskine - det skal du gøre .

Dette er et separat forelæsningsforløb i tre dage, så lad os gå videre til den sidste helvedes smerte og forskellige algoritmer til at håndtere den.

2.6. Komplekse/lange smerter: Genhårdende

Gør dig klar: Hvis du har sønderdelt dine data for første gang i dit liv, vil du i gennemsnit sønderdele dem fem gange mere.

Lige meget hvor mange klynger du konfigurerer, skal du stadig genoprette.

Hvis du er meget klog og heldig, så overskær mindst én gang. Men når du først er sikker, for i det øjeblik, hvor du tror, ​​at 10 enheder er nok for brugeren, skriver nogen lige i det øjeblik en anmodning om 30 og planlægger at have en anmodning om 100 enheder af ukendte ressourcer. Skår er aldrig nok. Med det første sharding-skema vil du under alle omstændigheder gå glip af - du bliver altid nødt til enten at øge antallet af servere, der skal tilføjes, eller gøre noget andet - i almindelighed skal du på en eller anden måde pakke dataene om.

Det er godt, hvis vi har pæne kræfter på to: der var 16 serverskår, nu er det 32. Det er sjovere, hvis det var 17, det er 23 - to vasimalt primtal. Hvordan gør databaser det, måske har de en form for magi indeni?

Det rigtige svar er: nej, der er ingen magi indeni, de har helvede indeni.

Dernæst vil vi overveje, hvad der kan gøres "i hånden", måske vil vi forstå "som en automatisk maskine".

På panden #1. Flyt alt

For alle objekter betragter vi NewF(objekt), skift til et nyt skår.

Chancen for, at NewF()=OldF() matcher er lav.

Lad os dække næsten alt.

Åh.

Jeg håber, at der ikke er et helvede til at overføre alle 2 milliarder poster fra gamle skår til nye. Den naive tilgang er forståelig: der var 17 maskiner, 6 maskiner blev tilføjet til klyngen, 2 milliarder poster blev sorteret fra, de blev flyttet fra 17 maskiner til 23 maskiner. En gang hvert 10. år kan du sikkert endda gøre det. Men generelt er det et dårligt træk.

På panden #2. Flyt halvdelen

Den næste naive forbedring - lad os opgive sådan en dum ordning - vil forbyde 17 biler i at omskære til 23, og vi vil altid omdanne 16 biler til 32 biler! Så skal vi ifølge teorien flytte præcis halvdelen af ​​dataene, og det kan vi i praksis også gøre.

For alle objekter betragter vi NewF(objekt), skift til et nyt skår.

Det var strengt taget 2^N, nu er det strengt taget 2^(N+1) skår.

Sandsynligheden for at matche NewF()=OldF() er 0,5.

Lad os overføre omkring 50 % af dataene.

Optimal, men virker kun for to-potenser.

I princippet er alt fint, bortset fra bindingen til to-styrken i forhold til antallet af biler. Denne naive tilgang kan mærkeligt nok fungere.

Bemærk venligst, at den yderligere opdeling af klyngen med to potenser i dette tilfælde også er optimal. Under alle omstændigheder, hvis vi tilføjer 16 maskiner til en klynge på 16, er vi forpligtet til at flytte halvdelen af ​​dataene - præcis halvdelen og skifte.

Okay, men har menneskeheden virkelig ikke opfundet noget andet - spørgsmålet opstår fra et videbegærligt sind.

Mere sjov #3. Konsekvent hashing

Her kræves selvfølgelig et billede med en cirkel om konsekvent hashing.

Hvis du googler “consistent hashing”, så kommer der helt sikkert en cirkel ud, alle resultaterne er udfyldt med cirkler.

Idé: Lad os tegne shard-id'er (hashes) på en cirkel og markere de hasherede server-id'er øverst. Når du skal tilføje en server, sætter vi et nyt punkt på cirklen, og det, der viste sig at være tæt på den (og kun det, der viste sig at være tæt på det), flytter vi.

Når du tilføjer et skår: vi kigger ikke alt igennem, men kun 2 "naboer", skifter vi i gennemsnit 1/n.

Når du sletter et shard: vi ser kun på det shard, der slettes, vi flytter kun det. Lidt optimalt.

Meget effektiv i forhold til at minimere trafik ved tilføjelse af et shard, og helt ulækkert i forhold til normal databalancering. For når vi hash alle disse objekter, som vi distribuerer til et stort antal maskiner, gør vi det relativt ujævnt: Punkterne omkring cirklen er ujævnt fordelt, og belastningen af ​​hver enkelt knude kan være meget forskellig fra resten.

Dette problem løses af den sidste linje i den virtuelle node. Hver node, hver server på cirklen er angivet med mere end én prik. Ved at tilføje en server, et shard osv. tilføjer vi et par point. Hver gang vi fjerner noget, fjerner vi derfor et par punkter og flytter en lille del af dataene.

Jeg taler om dette rum med cirkler, fordi for eksempel en sådan ordning er inde i Cassandra. Det vil sige, da hun begyndte at jagte poster mellem noder, skal du vide, at cirklen kigger på dig og sandsynligvis ikke godkender.

Men i forhold til de første metoder er livet blevet bedre - når vi tilføjer/fjerner et skår, ser vi allerede ikke alle poster igennem, men kun en del, og flytter kun en del.

Bemærk, spørgsmålet er: kan det forbedres yderligere? Og også forbedre ensartetheden af ​​læsning af skår? De siger, det er muligt!

Mere sjov #4. Rendezvous/HRW

Den næste simple idé (materialet er lærerigt, så intet kompliceret): shard_id = arg max hash(object_id, shard_id).

Hvorfor det hedder Rendezvous hashing ved jeg ikke, men jeg ved hvorfor det hedder Highest Random Weight. Det er meget nemt at visualisere det sådan her:

Vi har for eksempel 16 skår. For hvert objekt (streng), der skal placeres et sted, beregner vi 16 hashes afhængigt af objektet ud fra shardnummeret. Den, der har den højeste hashværdi, vinder.

Dette er den såkaldte HRW-hashing, også kendt som Rendezvous-hashing. Stum som en pind er skemaet til at beregne antallet af et skår for det første lettere for øjet end cirkler og giver på den anden side en ensartet belastning.

Det eneste negative er, at tilføjelsen af ​​et nyt skår er blevet værre for os. Der er en risiko for, at når vi tilføjer et nyt shard, har vi stadig nogle hashes, der vil ændre sig, og det kan være nødvendigt at gennemgå alt. Teknologien til fjernelse af skår har ikke ændret sig meget.

Et andet problem er, at det er regnemæssigt tungt med et stort antal skår.

Mere sjov #5. Flere teknikker

Interessant nok står forskningen ikke stille, og Google udgiver noget ny rumteknologi hvert år:

  • Jump Hash - Google '2014.
  • Multi Probe – Google '2015.
  • Maglev-Google '2016.

Er du interesseret i emnet, kan du læse mange afhandlinger. Jeg præsenterer disse data for at gøre det klart, at problemet ikke er løst, der er ingen superløsning, der kan implementeres i alle databaser. Indtil nu forsvarer folk afhandlinger.

konklusioner

Der er en vigtig grundteknik kaldet sharding opkaldt efter Gallius Julius Cæsar: "Del og hersk, hersk og del!". Hvis dataene ikke passer ind i én server, er det nødvendigt at opdele dem i 20 servere.

Efter at have lært alt dette, burde man få indtryk af, at det ville være bedre ikke at skære. Hvis du beslutter dig for, at det ville være bedre ikke at skære, er dette den rigtige følelse. Hvis du kan tilføje hukommelse til serveren for $100 og ikke sønderdele noget, så bør du gøre det. Ved sharding vil et komplekst distribueret system dukke op med overførsel af data frem og tilbage, stabling data i, ingen ved hvor. Hvis det kan undgås, skal det undgås.

Det er bedre ikke at gøre det i hånden, det er bedre, at "basen" (søgning, DFS, ...) kan sønderdele sig selv. Under alle omstændigheder vil der før eller siden komme høj belastning, og på en eller anden måde skal dataene opdeles. Det er ikke et faktum, at selvom basen kan gøre det selv, vil du ikke løbe ind i problemer. Husk på algoritmisk fundamentalisme - du skal forstå, hvordan alt fungerer indeni.

Når du opsætter sharding for første gang, skal du vælge F() omhyggeligt, tænke på anmodninger, netværk osv. Men gør dig klar, du skal nok vælge 2 gange og mindst én gang skal du lave alt om.