Course All lectures for NO purposes - Lecture: Sharding: bakside

2.1 Hvordan skjære og bremse ned N ganger?

Du kan skjære og bremse nøyaktig N ganger slik:

Send docs00...docs15-forespørsler sekvensielt , ikke parallelt.
I enkle spørringer, gjør et valg ikke med tasten , WHERE something=234.

I dette tilfellet tar den serialiserte delen (seriell) ikke 1% og ikke 5%, men omtrent 20% i moderne databaser. Du kan også få 50 % av den serialiserte delen hvis du får tilgang til databasen ved hjelp av en veldig effektiv binær protokoll eller kobler den som et dynamisk bibliotek inn i et Python-skript.

Resten av behandlingstiden for en enkel forespørsel vil bli okkupert av ikke-paralliserbare operasjoner med å analysere forespørselen, utarbeide planen osv. Det vil si at det går langsommere å ikke lese posten.

Hvis vi deler dataene inn i 16 tabeller og kjører sekvensielt, slik det for eksempel er vanlig i PHP-programmeringsspråket (det er ikke så bra til å starte asynkrone prosesser), så vil vi få en 16 gangers nedgang. Og kanskje enda mer, fordi nettverksreiser også vil bli lagt til.

Plutselig er valget av programmeringsspråk viktig ved sharding.

Husk valget av programmeringsspråk, for hvis du sender spørringer til databasen (eller søkeserveren) sekvensielt, hvor kommer da akselerasjonen fra? Snarere blir det en nedgang.

2.2 Om halvautomatisk

Noen steder inspirerer sofistikeringen av informasjonsteknologi til chtonisk skrekk. For eksempel, MySQL ut av boksen hadde ikke implementeringen av sharding til visse versjoner, men størrelsen på databasene som brukes i kamp vokser til uanstendige verdier.

Å lide medmenneskelighet i møte med individuelle DBA-er har vært plaget i årevis og skriver flere dårlige sønderdelingsløsninger basert på ingenting. Etter det skrives en mer eller mindre grei sharding-løsning som heter ProxySQL (MariaDB/Spider, PG/pg_shard/Citus, ...). Dette er et velkjent eksempel på nettopp denne flekken.

ProxySQL som helhet er selvfølgelig en fullverdig løsning i bedriftsklassen for åpen kildekode, for ruting og mer. Men en av oppgavene som skal løses er sharding for en database, som i seg selv ikke kan skjære på en menneskelig måte. Du skjønner, det er ingen "shards = 16"-bryter, du må enten skrive om hver forespørsel i applikasjonen, og det er mange av dem på steder, eller legge et mellomlag mellom applikasjonen og databasen som ser ut: "Hmm ... VELG * FRA dokumenter? Ja, det må deles inn i 16 små SELECT * FRA server1.dokument1, VELG * FRA server2.dokument2 - til denne serveren med en slik innlogging / passord, til denne med en annen. Hvis man ikke svarte, så ... ", osv. Akkurat dette kan gjøres med mellomflekker. De er litt mindre enn for alle databaser. For PostgreSQL, så vidt jeg forstår,

Konfigurering av hver spesifikk oppdatering er et eget gigantisk emne som ikke passer i én rapport, så vi vil bare diskutere de grunnleggende konseptene. La oss heller snakke litt om teorien om buzz.

2.3 Absolutt perfekt automatisering?

Hele teorien om å bli høy i tilfelle av sharding i denne bokstaven F() , er det grunnleggende prinsippet alltid det samme omtrent: shard_id = F(objekt).

Sharding - hva handler det om? Vi har 2 milliarder poster (eller 64). Vi ønsker å dele dem i flere deler. Et uventet spørsmål dukker opp – hvordan? Etter hvilket prinsipp bør jeg spre mine 2 milliarder poster (eller 64) på 16 servere som er tilgjengelige for meg?

Den latente matematikeren i oss burde foreslå at det til slutt alltid er en magisk funksjon som, for hvert dokument (objekt, linje, osv.), vil avgjøre hvilken brikke det skal settes i.

Når vi går dypere inn i matematikken, avhenger denne funksjonen alltid ikke bare av selve objektet (selve raden), men også av eksterne innstillinger som det totale antallet shards. En funksjon som for hvert objekt må fortelle hvor den skal plasseres, kan ikke returnere en verdi mer enn det er servere i systemet. Og funksjonene er litt forskjellige:

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

Men videre skal vi ikke grave inn i disse villmarkene av individuelle funksjoner, vi vil bare snakke om hva magiske funksjoner F () er.

2.4 Hva er F()?

De kan komme opp med mange forskjellige og mange forskjellige implementeringsmekanismer. Eksempelsammendrag:

F = rand() % nums_shards
F = somehash(objekt.id) % num_shards
F = objekt.dato % antall_shards
F = objekt.bruker-id % antall_shards
...
F = shard_table [ somehash() |… objekt.dato |… ]

Et interessant faktum - du kan naturligvis spre alle dataene tilfeldig - vi kaster neste post på en vilkårlig server, på en vilkårlig kjerne, i en vilkårlig tabell. Det vil ikke være mye lykke i dette, men det vil fungere.

Det er litt mer intelligente metoder for å skjære med en reproduserbar eller til og med konsistent hash-funksjon, eller shard av en eller annen egenskap. La oss gå gjennom hver metode.

F = rand()

Å spre rundt er ikke en veldig riktig metode. Ett problem: vi spredte våre 2 milliarder poster på tusen servere tilfeldig, og vi vet ikke hvor posten er. Vi må trekke ut user_1, men vi vet ikke hvor han er. Vi går til tusen servere og sorterer gjennom alt - på en eller annen måte er dette ineffektivt.

F = noe hash()

La oss spre brukere på en voksen måte: beregn den reproduserbare hash-funksjonen fra user_id, ta resten av divisjonen etter antall servere, og kontakt den ønskede serveren umiddelbart.

Hvorfor gjør vi dette? Og så, at vi har en høybelastning og ingenting annet passer inn i en server. Hvis det passet, ville livet vært så enkelt.

Flott, situasjonen har allerede forbedret seg, for å få én post går vi til én kjent server på forhånd. Men hvis vi har en rekke nøkler, må vi i hele denne serien gå gjennom alle verdiene til nøklene og, i grensen, enten gå til så mange skår som vi har nøkler i området, eller til og med til hver server. Situasjonen har selvfølgelig forbedret seg, men ikke for alle forespørsler. Noen forespørsler har blitt berørt.

Naturlig skjæring (F = objekt.dato % num_shards)

Noen ganger, det vil si ofte, er 95 % av trafikken og 95 % av belastningen forespørsler som har en slags naturlig skjæring. For eksempel påvirker 95 % av betinget sosialanalytiske søk data bare for den siste dagen, 3 dagene, 7 dagene, og de resterende 5 % refererer til de siste årene. Men 95 % av forespørslene er dermed naturlig sønderdelt etter dato, interessen til systembrukere er fokusert på de siste dagene.

I dette tilfellet kan du dele dataene etter dato, for eksempel med én dag, og følge svaret på forespørselen om en rapport for en dag eller et objekt fra denne dagen til dette skjæret og gå.

Livet blir bedre - vi vet nå ikke bare plasseringen til et bestemt objekt, men vi vet også om rekkevidden. Hvis vi ikke blir spurt om en rekke datoer, men om en rekke andre kolonner, så må vi selvfølgelig gå gjennom alle skårene. Men i henhold til spillereglene har vi bare 5 % av slike forespørsler.

Det ser ut til at vi har kommet opp med en ideell løsning på alt, men det er to problemer:

Denne løsningen er skreddersydd for en spesifikk sak, når 95 % av forespørslene kun gjelder den siste uken.
Siden 95 % av forespørslene berører den siste uken, vil de alle falle på ett skjær som leveres denne siste uken. Denne skåren vil smelte, mens alle de andre vil være inaktive i løpet av denne tiden. Samtidig kan du ikke kaste dem, arkivdata må også lagres.

For ikke å si at dette er en dårlig skjæringsordning - vi kutter av varme data, likevel må noe gjøres med det hotteste skjæret.

Problemet løses med krumspring, hopp og omslag, det vil si en økning i antall kopier for den brennende gjeldende dagen, deretter en gradvis nedgang i antall kopier når denne dagen blir fortid og går inn i arkivet. Det er ingen ideell løsning kalt "du trenger bare å spre dataene over klyngen med en magisk hash-funksjon på feil måte".

2.5 Pris som skal betales

Formelt sett vet vi nå at vi vet "alt". Riktignok kjenner vi ikke til en gigantisk hodepine og to mindre hodepine.

1. Enkel smerte: dårlig utsmurt

Dette er et eksempel fra en lærebok, som nesten aldri forekommer i kamp, men plutselig.

Som et eksempel med en date, bare uten en date!
Utilsiktet ujevn (oppfattelig) fordeling.

De valgte sønderdelingsmekanismen, og/eller dataene ble endret, og selvfølgelig formidlet ikke statsministeren kravene (vi har ingen feil i koden, statsministeren rapporterer alltid ikke kravene), og distribusjonen ble uhyrlig ujevn. Det vil si at de bommet på kriteriet.

For å fange må du se på størrelsen på skårene. Vi vil definitivt se problemet i øyeblikket når en av våre skår enten overopphetes eller blir 100 ganger større enn de andre. Du kan fikse det ganske enkelt ved å bytte ut nøkkelen eller skjærefunksjonen.

Dette er et enkelt problem, for å være ærlig, jeg tror ikke at minst én person av hundre vil støte på dette i livet, men plutselig vil det hjelpe minst noen.

2. "Uovervinnelig" smerte: aggregering, bli med

Hvordan gjøre valg som slår sammen en milliard poster fra ett bord for en milliard poster fra et annet bord?

Hvordan "raskt" beregne... HVOR randcol MELLOM aaa OG bbb?
Hvordan "smart" gjøre... users_32shards BLI MEDLEM PÅ innlegg_1024 shards?

Kort svar: ingen måte, lide!

Hvis du distribuerte en milliard poster til tusen servere i den første tabellen slik at de fungerer raskere, og gjorde det samme i den andre tabellen, så burde naturlig nok tusen til tusen servere snakke med hverandre i par. En million tilkoblinger vil ikke fungere bra. Hvis vi kommer med forespørsler til databasen (søk, lagring, dokumentlager eller distribuert filsystem) som ikke passer godt med sharding, vil disse forespørslene bremse voldsomt.

Et viktig poeng er at noen forespørsler alltid vil bli mislykket og vil bremse ned . Det er viktig å prøve å minimere prosentandelen deres. Som en konsekvens er det ikke nødvendig å lage gigantiske sammenføyninger med en milliard ganger en milliard poster. Hvis det er mulig å replikere en liten tabell, i forhold til hvilken du blir med i en gigantisk delt tabell, til alle noder, bør du gjøre det. Hvis sammenføyningene faktisk er lokale på en eller annen måte, for eksempel, er det mulig å plassere brukeren og hans innlegg side om side, skjære dem på samme måte og gjøre alle sammenføyningene i samme maskin - du må gjøre nettopp det .

Dette er et eget forelesningskurs i tre dager, så la oss gå videre til den siste helvetes smerten og forskjellige algoritmer for å håndtere den.

2.6. Kompleks/lang smerte: Gjendannende

Gjør deg klar: Hvis du sønderdelte dataene dine for første gang i livet ditt, vil du i gjennomsnitt skjære dem fem ganger til.

Uansett hvor mange klynger du konfigurerer, må du fortsatt reharde.

Hvis du er veldig smart og heldig, så overskjær minst én gang. Men når du er sikker, for i øyeblikket når du tror at 10 enheter er nok for brukeren, skriver noen akkurat i det øyeblikket en forespørsel om 30, og planlegger å ha en forespørsel om 100 enheter med ukjente ressurser. Skår er aldri nok. Med den første sharding-ordningen vil du uansett gå glipp av - du må alltid enten øke antall servere for å legge til, eller gjøre noe annet - generelt sett, på en eller annen måte pakke om dataene.

Det er bra hvis vi har fine krefter på to: det var 16 serverskår, nå er det 32. Det er morsommere hvis det var 17, det er 23 - to vasimalt primtall. Hvordan gjør databaser det, kanskje de har en slags magi inni seg?

Det riktige svaret er: nei, det er ingen magi inni, de har helvete inni seg.

Deretter vil vi vurdere hva som kan gjøres "for hånd", kanskje vil vi forstå "som en automatisk maskin".

På pannen #1. Flytt alt

For alle objekter vurderer vi NewF(objekt), skift til en ny shard.

Sjansen for samsvar mellom NewF()=OldF() er lav.

La oss dekke nesten alt.

Åh.

Jeg håper det ikke finnes et helvete som å overføre alle 2 milliarder poster fra gamle skår til nye. Den naive tilnærmingen er forståelig: det var 17 maskiner, 6 maskiner ble lagt til klyngen, 2 milliarder poster ble sortert ut, de ble flyttet fra 17 maskiner til 23 maskiner. En gang hvert 10. år kan du sannsynligvis til og med gjøre det. Men totalt sett er det et dårlig trekk.

På pannen #2. Flytt halvparten

Den neste naive forbedringen - la oss forlate et så dumt opplegg - vil forby 17 biler å omskjære til 23, og vi vil alltid omharde 16 biler til 32 biler! Da vil vi ifølge teorien måtte flytte nøyaktig halvparten av dataene, og i praksis kan vi også gjøre dette.

For alle objekter vurderer vi NewF(objekt), skift til en ny shard.

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

Sannsynligheten for å matche NewF()=OldF() er 0,5.

La oss overføre omtrent 50 % av dataene.

Optimal, men fungerer bare for to potenser.

I prinsippet er alt bra, bortsett fra bindingen til to-styrken når det gjelder antall biler. Denne naive tilnærmingen kan merkelig nok fungere.

Vær oppmerksom på at tilleggsdelingen av klyngen med to potenser i dette tilfellet også er optimal. I alle fall, legger vi 16 maskiner til en klynge på 16, er vi forpliktet til å flytte halvparten av dataene - nøyaktig halvparten og skifte.

Ok, men har menneskeheten virkelig ikke funnet opp noe annet - spørsmålet kommer fra et nysgjerrig sinn.

Mer moro #3. Konsekvent hashing

Her kreves selvfølgelig et bilde med en sirkel om konsekvent hashing.

Hvis du googler «konsistent hashing», vil det definitivt komme ut en sirkel, alle resultatene er fylt med sirkler.

Idé: la oss tegne shard-identifikatorer (hasher) på en sirkel, og merke de hash-kodede serveridentifikatorene på toppen. Når du trenger å legge til en server, legger vi et nytt punkt på sirkelen, og det som viste seg å være nær den (og bare det som viste seg å være nær den), flytter vi.

Når du legger til en shard: vi ser gjennom ikke alt, men bare 2 "naboer", vi skifter i gjennomsnitt 1/n.

Når du sletter et shard: vi ser bare på shard som slettes, vi flytter bare det. Litt optimalt.

Veldig effektivt med tanke på å minimere trafikken når man legger til et shard, og helt ekkelt med tanke på normal databalansering. For når vi hash alle disse objektene som vi distribuerer til et stort antall maskiner, gjør vi det relativt ujevnt: punktene rundt sirkelen er ujevnt fordelt, og belastningen til hver enkelt node kan være veldig forskjellig fra resten.

Dette problemet løses av den siste linjen i den virtuelle noden. Hver node, hver server på sirkelen er indikert med mer enn én prikk. Ved å legge til en server, en shard, etc., legger vi til noen få punkter. Hver gang vi fjerner noe, fjerner vi følgelig noen få punkter og flytter en liten del av dataene.

Jeg snakker om dette rommet med sirkler, fordi for eksempel et slikt opplegg er inne i Cassandra. Det vil si, når hun begynte å jage poster mellom noder, vet at sirkelen ser på deg og sannsynligvis ikke godkjenner.

Imidlertid, sammenlignet med de første metodene, har livet blitt bedre - når vi legger til / fjerner et shard, ser vi allerede gjennom ikke alle poster, men bare en del, og skifter bare en del.

Oppmerksomhet, spørsmålet er: kan det forbedres ytterligere? Og også forbedre jevnheten til lasting av skår? De sier det er mulig!

Mer moro #4. Rendezvous/HRW

Den neste enkle ideen (materialet er lærerikt, så ikke noe komplisert): shard_id = arg max hash(object_id, shard_id).

Hvorfor det heter Rendezvous-hashing vet jeg ikke, men jeg vet hvorfor det heter Høyeste tilfeldige vekt. Det er veldig enkelt å visualisere det slik:

Vi har for eksempel 16 skår. For hvert objekt (streng) som må settes et sted, beregner vi 16 hashes avhengig av objektet fra shardnummeret. Den som har høyest hashverdi vinner.

Dette er såkalt HRW-hashing, også kjent som Rendezvous-hashing. Dum som en pinne, skjemaet for å beregne antallet av et skår, for det første, er lettere for øyet enn sirkler og gir en jevn belastning, på den annen side.

Det eneste negative er at det har blitt verre for oss å legge til et nytt skår. Det er en risiko for at når vi legger til et nytt shard, har vi fortsatt noen hashes som vil endre seg og det kan være nødvendig å gjennomgå alt. Teknologien for fjerning av skår har ikke endret seg mye.

Et annet problem er at den er regnemessig tung med et stort antall skår.

Mer moro #5. Flere teknikker

Interessant nok står ikke forskningen stille og Google publiserer noe ny romteknologi hvert år:

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

Hvis du er interessert i emnet, kan du lese mange avhandlinger. Jeg presenterer disse dataene for å gjøre det klart at problemet ikke er løst, det er ingen superløsning som kan implementeres i alle databaser. Frem til nå forsvarer folk avhandlinger.

konklusjoner

Det er en viktig grunnleggende teknikk kalt sharding oppkalt etter Gallius Julius Caesar: "Del og hersk, hersk og del!". Hvis dataene ikke passer inn i én server, er det nødvendig å dele dem opp i 20 servere.

Etter å ha lært alt dette, bør man få inntrykk av at det ville være bedre å ikke skjære. Hvis du bestemmer deg for at det ville være bedre å ikke skjære, er dette den rette følelsen. Hvis du kan legge til minne til serveren for $100 og ikke sønderdele noe, bør du gjøre det. Ved sharding vil et komplekst distribuert system dukke opp med overføring av data frem og tilbake, stabling av data i ingen vet hvor. Hvis det kan unngås, må det unngås.

Det er bedre å ikke gjøre det for hånd, det er bedre at "basen" (søk, DFS, ...) kan sønderdele seg selv. I alle fall, før eller senere, vil høybelastning komme og på en eller annen måte må dataene deles. Det er ikke et faktum at selv om basen kan gjøre det selv, vil du ikke få problemer. Husk algoritmisk fundamentalisme - du må forstå hvordan alt fungerer på innsiden.

Når du setter opp sharding for første gang, velg F() nøye, tenk på forespørsler, nettverk osv. Men gjør deg klar, du må nok velge 2 ganger og minst en gang må du gjøre om alt.