Sharding

1.1 Hva er skjæring?

Hvis du googler vedvarende, viser det seg at det er en ganske uskarp grense mellom såkalt partisjonering og såkalt sharding. Alle ringer hva de vil, hva de vil. Noen mennesker skiller mellom horisontal partisjonering og skjæring. Andre sier at sharding er en viss form for horisontal partisjonering.

Jeg fant ikke en eneste terminologisk standard som ville bli godkjent av grunnleggerne og sertifisert av ISO. Personlig indre overbevisning er noe sånt som dette: Å dele opp i gjennomsnitt er å "skjære basen i stykker" på en vilkårlig måte.

• Vertikal partisjonering - etter kolonne. For eksempel er det et gigantisk bord med et par milliarder poster i 60 kolonner. I stedet for å beholde en slik gigantisk tabell, beholder vi minst 60 gigantiske tabeller på 2 milliarder poster hver – og dette er ikke en kolonnebase, men vertikal partisjonering (som et eksempel på terminologi).
• Horisontal partisjonering - vi kutter linje for linje, kanskje inne i serveren.

Det vanskelige øyeblikket her er den subtile forskjellen mellom horisontal partisjonering og skjæring. Jeg kan kuttes i biter, men jeg kan ikke si deg sikkert hva det er. Det er en følelse av at skjæring og horisontal partisjonering er omtrent det samme.

Sharding er generelt når en stor tabell når det gjelder databaser eller en pro-samling av dokumenter, objekter, hvis du ikke har en database, men et dokumentlager, kuttes nøyaktig av objekter. Det vil si at fra 2 milliarder objekter velges brikker uansett størrelse. Selve gjenstandene inne i hvert objekt er ikke kuttet i stykker, vi legger dem ikke ut i separate kolonner, nemlig vi legger dem ut i grupper på forskjellige steder.

Det er subtile terminologiske forskjeller. For eksempel, relativt sett, kan Postgres-utviklere si at horisontal partisjonering er når alle tabellene som hovedtabellen er delt inn i ligger i samme skjema, og når det er på forskjellige maskiner, er dette allerede sønderdeling.

I en generell forstand, uten å være bundet til terminologien til en bestemt database og et spesifikt databehandlingssystem, er det en følelse av at sharding bare er å kutte linje for linje / dokument for dokument, og så videre - det er alt.

Jeg legger vekt på typisk. I den forstand at vi gjør alt dette ikke bare for å kutte 2 milliarder dokumenter i 20 tabeller, som hver vil være mer håndterbare, men for å distribuere det over mange kjerner, mange disker eller mange forskjellige fysiske eller virtuelle servere.

1.2 Del det udelelige

Det er forstått at vi gjør dette slik at hvert shard - hver del av data - blir replikert mange ganger. Men egentlig, nei.

INSERT INTO docs00 
SELECT * FROM documents WHERE (id%16)=0 
... 
 
INSERT INTO docs15 
SELECT * FROM documents WHERE (id%16)=15 

Faktisk, hvis du gjør en slik oppskjæring av data, og fra en gigantisk SQL-tabell på MySQL på din tapre bærbare datamaskin, vil du generere 16 små tabeller, uten å gå utover en enkelt bærbar datamaskin, ikke et enkelt skjema, ikke en enkelt database osv. . og så videre. - det er det, du har allerede sharding.

Dette resulterer i følgende:

• Båndbredden øker.
• Latency endres ikke, det vil si at hver, så å si, arbeider eller forbruker i dette tilfellet, får sin egen. Ulike forespørsler behandles omtrent samtidig.
• Eller begge deler, og en annen, og også høy tilgjengelighet (replikering).

Hvorfor båndbredde? Vi kan noen ganger ha slike datamengder som ikke passer - det er ikke klart hvor, men de passer ikke - på 1 {kernel | disk | server | ...}. Det er bare ikke nok ressurser, det er alt. For å kunne jobbe med dette store datasettet, må du kutte det.

Hvorfor ventetid? På en kjerne er det å skanne en tabell med 2 milliarder rader 20 ganger langsommere enn å skanne 20 tabeller på 20 kjerner, og gjøre det parallelt. Data behandles for sakte på én enkelt ressurs.

Hvorfor høy tilgjengelighet? Eller vi kutter dataene for å kunne gjøre begge deler samtidig, og samtidig flere kopier av hvert shard - replikering sikrer høy tilgjengelighet.

1.3 Et enkelt eksempel "hvordan gjøre det for hånd"

Betinget skjæring kan kuttes ut ved å bruke testtabellen test.documents for 32 dokumenter, og generere 16 testtabeller fra denne tabellen, ca. 2 dokumenter hver test.docs00, 01, 02, ..., 15.

INSERT INTO docs00 
SELECT * FROM documents WHERE (id%16)=0 
... 
 
INSERT INTO docs15 
SELECT * FROM documents WHERE (id%16)=15 

Hvorfor omtrent? Fordi vi på forhånd ikke vet hvordan id er fordelt, hvis fra 1 til 32 inkludert, vil det være nøyaktig 2 dokumenter hver, ellers ikke.

Vi gjør det her hvorfor. Etter at vi har laget 16 bord kan vi "ta" 16 av det vi trenger. Uansett hva vi treffer, kan vi parallellisere disse ressursene. For eksempel, hvis det ikke er nok diskplass, vil det være fornuftig å dekomponere disse tabellene på separate disker.

Alt dette er dessverre ikke gratis. Jeg mistenker at når det gjelder den kanoniske SQL-standarden (jeg har ikke lest SQL-standarden på nytt på lenge, kanskje den ikke har blitt oppdatert på lenge), er det ingen offisiell standardisert syntaks for å si til en SQL-server : "Kjære SQL-server, lag meg 32 shards og del dem i 4 disker. Men i individuelle implementeringer er det ofte en spesifikk syntaks for å gjøre stort sett det samme. PostgreSQL har mekanismer for partisjonering, MySQL har MariaDB, Oracle har sannsynligvis gjort alt dette for lenge siden.

Likevel, hvis vi gjør det for hånd, uten databasestøtte og innenfor rammen av standarden, betaler vi betinget med kompleksiteten til datatilgang . Der det var en enkel SELECT * FROM dokumenter WHERE id=123, nå 16 x SELECT * FROM docsXX. Og det er bra om vi prøvde å få posten med nøkkel. Mye mer interessant hvis vi prøvde å få et tidlig utvalg av plater. Nå (hvis vi, understreker jeg, så å si er idioter og holder oss innenfor rammen av standarden), må resultatene av disse 16 SELECT * FROM kombineres i applikasjonen.

Hvilken ytelsesendring kan du forvente?

• Intuitivt - lineært.
• Teoretisk - sublineær, fordi Amdahl lov.
• Praktisk talt, kanskje nesten lineært, kanskje ikke.

Faktisk er det riktige svaret ukjent. Med en smart bruk av sønderdelingsteknikken kan du oppnå en betydelig superlineær degradering i ytelsen til applikasjonen din, og til og med DBA vil komme løpende med en rødglødende poker.

La oss se hvordan dette kan oppnås. Det er klart at bare å sette innstillingen til PostgreSQL shards=16, og så tar det av seg selv, ikke er interessant. La oss tenke på hvordan vi kan sørge for at vi bremser ned fra skjæring med 16 ganger med 32 - dette er interessant fra synspunktet om hvordan du ikke gjør dette.

Våre forsøk på å øke hastigheten eller bremse ned vil alltid løpe inn i klassikerne - den gode gamle Amdahl-loven, som sier at det ikke er noen perfekt parallellisering av noen forespørsel, det er alltid en konsistent del.

1.4 Amdahl-loven

Det er alltid en serialisert del.

Det er alltid en del av spørringskjøringen som er parallellisert, og det er alltid en del som ikke er parallellisert. Selv om det virker for deg som en perfekt parallell spørring, er i det minste samlingen av resultatraden som du skal sende til klienten fra radene mottatt fra hvert shard alltid der, og den er alltid sekvensiell.

Det er alltid en konsekvent del. Den kan være liten, helt usynlig mot den generelle bakgrunnen, den kan være gigantisk og følgelig sterkt påvirke parallellisering, men den eksisterer alltid.

I tillegg er dens innflytelse i endring og kan vokse betydelig, for eksempel hvis vi kutter bordet vårt - la oss øke innsatsen - fra 64 poster til 16 tabeller med 4 poster, vil denne delen endres. Selvfølgelig, etter slike gigantiske datamengder, jobber vi med en mobiltelefon og en 2 MHz 86-prosessor, og vi har ikke nok filer som kan holdes åpne samtidig. Tilsynelatende, med slike innganger, åpner vi én fil om gangen.

• Det var Totalt = Seriell + Parallell . Hvor for eksempel parallell er alt arbeidet inne i DB, og seriell sender resultatet til klienten.
• Ble Total2 = Seriell + Parallell/N + Xserial . For eksempel når den samlede ORDER BY, Xserial>0.

Med dette enkle eksempelet prøver jeg å vise at noe Xserial vises. I tillegg til at det alltid er en serialisert del, og det faktum at vi prøver å jobbe med data parallelt, er det en ekstra del for å gi denne dataslicingen. Grovt sett kan vi trenge:

• finn disse 16 tabellene i databasens interne ordbok;
• åpne filer;
• tildele minne;
• fjerne allokering av minne;
• slå sammen resultater;
• synkronisere mellom kjerner.

Noen usynkroniserte effekter vises fortsatt. De kan være ubetydelige og oppta en milliarddel av den totale tiden, men de er alltid ikke-null og alltid der. Med deres hjelp kan vi miste ytelsen dramatisk etter skjæring.

Dette er et standardbilde om Amdahls lov. Det viktige her er at linjene, som ideelt sett skal være rette og vokse lineært, går inn i en asymptote. Men siden grafen fra Internett er uleselig, laget jeg etter min mening mer visuelle tabeller med tall.

La oss si at vi har en serialisert del av forespørselsbehandlingen som bare tar 5 %: serienummer = 0,05 = 1/20 .

Intuitivt ser det ut til at med en serialisert del som tar bare 1/20 av forespørselsbehandlingen, hvis vi parallelliserer forespørselsbehandlingen for 20 kjerner, vil den bli omtrent 20, i verste fall 18 ganger raskere.

Faktisk er matematikk en hjerteløs ting :

vegg = 0,05 + 0,95/antall_cores, speedup = 1 / (0,05 + 0,95/antall_cores)

Det viser seg at hvis du beregner nøye, med en serialisert del på 5 %, vil speedupen være 10 ganger (10,3), som er 51 % sammenlignet med det teoretiske idealet.

Etter å ha brukt 20 kjerner (20 disker, hvis du vil) for oppgaven som en pleide å jobbe med, vil vi teoretisk aldri engang få en akselerasjon på mer enn 20 ganger, men i praksis - mye mindre. Dessuten, med en økning i antall paralleller, øker ineffektiviteten sterkt.

Når bare 1 % av det serialiserte arbeidet gjenstår, og 99 % er parallellisert, forbedres speedup-verdiene noe:

For en perfekt termonukleær spørring, som naturlig nok tar timer å fullføre, og det forberedende arbeidet og monteringen av resultatet tar svært lite tid (seriell = 0,001), vil vi allerede se god effektivitet:

Vær oppmerksom på at vi aldri vil se 100 % . I spesielt gode tilfeller kan du se for eksempel 99,999 %, men ikke akkurat 100 %.