Sharding

1.1 Hvad er sharding?

Hvis man vedholdende googler, viser det sig, at der er en ret sløret grænse mellem den såkaldte partitionering og den såkaldte sharding. Alle kalder hvad de vil, hvad de vil. Nogle mennesker skelner mellem vandret opdeling og skæring. Andre siger, at skæring er en vis form for vandret opdeling.

Jeg fandt ikke en eneste terminologisk standard, der ville blive godkendt af grundlæggerne og certificeret af ISO. Personlig indre overbevisning er noget som dette: Opdeling i gennemsnit er at "skære basen i stykker" på en vilkårligt taget måde.

• Lodret opdeling - efter kolonne. For eksempel er der en kæmpe tabel med et par milliarder poster i 60 kolonner. I stedet for at beholde en sådan gigantisk tabel, beholder vi mindst 60 gigantiske tabeller på hver 2 milliarder poster - og dette er ikke en kolonnebase, men lodret opdeling (som et eksempel på terminologi).
• Horisontal partitionering - vi skærer linje for linje, måske inde i serveren.

Det akavede øjeblik her er den subtile forskel mellem vandret opdeling og skæring. Jeg kan skæres i stykker, men jeg kan ikke fortælle dig med sikkerhed, hvad det er. Der er en følelse af, at skæring og vandret opdeling er omtrent det samme.

Sharding er generelt, når en stor tabel i form af databaser eller en pro-samling af dokumenter, objekter, hvis du ikke har en database, men et dokumentlager, skæres nøjagtigt af objekter. Det vil sige, at fra 2 milliarder objekter vælges stykker uanset størrelse. Selve objekterne inde i hver genstand er ikke skåret i stykker, vi lægger dem ikke ud i separate kolonner, nemlig vi lægger dem ud i partier forskellige steder.

Der er subtile terminologiske forskelle. For eksempel, relativt set, kan Postgres-udviklere sige, at horisontal partitionering er, når alle de tabeller, som hovedtabellen er opdelt i, ligger i det samme skema, og når det er på forskellige maskiner, er dette allerede sønderdeling.

I en generel forstand, uden at være bundet til terminologien for en specifik database og et specifikt datastyringssystem, er der en følelse af, at sharding blot er at skære linje for linje / dokument for dokument, og så videre - det er alt.

Jeg understreger typisk. I den forstand, at vi gør alt dette ikke bare for at skære 2 milliarder dokumenter i 20 tabeller, som hver især ville være mere overskuelige, men for at distribuere det over mange kerner, mange diske eller mange forskellige fysiske eller virtuelle servere.

1.2 Del det udelelige

Det er underforstået, at vi gør dette, så hvert shard - hvert stykke data - bliver replikeret mange gange. Men egentlig nej.

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

Faktisk, hvis du laver en sådan udskæring af data, og fra en kæmpe SQL-tabel på MySQL på din tapre bærbare computer, vil du generere 16 små tabeller, uden at gå ud over en enkelt bærbar computer, ikke et enkelt skema, ikke en enkelt database osv. . og så videre. - det er det, du har allerede sønderdeling.

Dette resulterer i følgende:

• Båndbredden øges.
• Latency ændres ikke, det vil sige, at hver, så at sige, arbejder eller forbruger i dette tilfælde får sit eget. Forskellige forespørgsler behandles på nogenlunde samme tid.
• Eller begge dele, og en anden, og også høj tilgængelighed (replikation).

Hvorfor båndbredde? Vi kan nogle gange have sådanne mængder af data, der ikke passer - det er ikke klart hvor, men de passer ikke - på 1 {kerne | disk | server | ...}. Der er bare ikke ressourcer nok, det er alt. For at kunne arbejde med dette store datasæt, skal du klippe det.

Hvorfor latency? På en kerne er scanning af en tabel med 2 milliarder rækker 20 gange langsommere end scanning af 20 tabeller på 20 kerner, hvilket gør det parallelt. Data behandles for langsomt på en enkelt ressource.

Hvorfor høj tilgængelighed? Eller vi klipper dataene for at gøre begge dele på samme tid, og samtidig flere kopier af hvert shard - replikering sikrer høj tilgængelighed.

1.3 Et simpelt eksempel "hvordan man gør det i hånden"

Betinget sønderdeling kan skæres ud ved at bruge testtabellen test.documents for 32 dokumenter og generere 16 testtabeller fra denne tabel, 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 omkring? Fordi vi på forhånd ikke ved, hvordan id er fordelt, hvis fra 1 til 32 inklusive, så vil der være præcis 2 dokumenter hver, ellers ikke.

Vi gør det her hvorfor. Efter vi har lavet 16 borde, kan vi "snakke" 16 af det vi skal bruge. Uanset hvad vi rammer, kan vi parallelisere disse ressourcer. For eksempel, hvis der ikke er nok diskplads, ville det give mening at dekomponere disse tabeller på separate diske.

Alt dette er desværre ikke gratis. Jeg formoder, at i tilfældet med den kanoniske SQL-standard (jeg har ikke genlæst SQL-standarden i lang tid, måske er den ikke blevet opdateret i lang tid), er der ingen officiel standardiseret syntaks til at sige til nogen SQL-server : "Kære SQL-server, lav mig 32 shards og del dem i 4 diske. Men i individuelle implementeringer er der ofte en specifik syntaks for at gøre stort set det samme. PostgreSQL har mekanismer til partitionering, MySQL har MariaDB, Oracle har sandsynligvis gjort alt dette for længe siden.

Ikke desto mindre, hvis vi gør det i hånden, uden databaseunderstøttelse og inden for rammerne af standarden, så betaler vi betinget med kompleksiteten af ​​dataadgang . Hvor der var en simpel SELECT * FROM dokumenter WHERE id=123, nu 16 x SELECT * FROM docsXX. Og det er godt, hvis vi forsøgte at få posten med nøgle. Meget mere interessant, hvis vi forsøgte at få en tidlig række af rekorder. Nu (hvis vi, jeg understreger, så at sige er tåber og forbliver inden for rammerne af standarden), skal resultaterne af disse 16 SELECT * FROM kombineres i applikationen.

Hvilken præstationsændring kan du forvente?

• Intuitivt - lineært.
• Teoretisk - sublineær, fordi Amdahl lov.
• Praktisk, måske næsten lineært, måske ikke.

Faktisk er det rigtige svar ukendt. Med en smart anvendelse af sharding-teknikken kan du opnå en betydelig super-lineær forringelse af din applikations ydeevne, og selv DBA kommer kørende med en rødglødende poker.

Lad os se, hvordan dette kan opnås. Det er klart, at bare at sætte indstillingen til PostgreSQL shards=16, og så tager det af sig selv, er ikke interessant. Lad os tænke på, hvordan vi kan sikre, at vi bremser ned fra sharding med 16 gange med 32 - det er interessant ud fra et synspunkt om, hvordan man ikke gør dette.

Vores forsøg på at fremskynde eller bremse vil altid løbe ind i klassikerne - den gode gamle Amdahl-lov, som siger, at der ikke er nogen perfekt parallelisering af nogen anmodning, der er altid en konsekvent del.

1.4 Amdahl lov

Der er altid en serialiseret del.

Der er altid en del af forespørgselsudførelsen, der er paralleliseret, og der er altid en del, der ikke er paralleliseret. Selvom det forekommer dig, at en perfekt parallel forespørgsel, i det mindste samlingen af ​​resultatrækken, som du vil sende til klienten fra rækkerne modtaget fra hvert shard, er der altid, og den er altid sekventiel.

Der er altid en sammenhængende del. Den kan være lillebitte, fuldstændig usynlig på den generelle baggrund, den kan være gigantisk og følgelig kraftigt påvirke paralleliseringen, men den eksisterer altid.

Derudover ændrer dens indflydelse sig og kan vokse betydeligt, hvis vi for eksempel skærer vores bord - lad os hæve indsatsen - fra 64 poster til 16 borde med 4 poster, vil denne del ændre sig. At dømme efter så gigantiske datamængder arbejder vi selvfølgelig på en mobiltelefon og en 2 MHz 86 processor, og vi har ikke nok filer, der kan holdes åbne på samme tid. Med sådanne input åbner vi åbenbart én fil ad gangen.

• Det var Total = Seriel + Parallel . Hvor for eksempel parallelt er alt arbejdet inde i DB'en, og seriel sender resultatet til klienten.
• Blev Total2 = Seriel + Parallel/N + Xserial . For eksempel, når den samlede ORDER BY, Xserial>0.

Med dette enkle eksempel forsøger jeg at vise, at der dukker noget Xserial op. Udover det faktum, at der altid er en serialiseret del, og det faktum, at vi forsøger at arbejde med data parallelt, er der en ekstra del til at levere denne dataslicing. Groft sagt kan vi have brug for:

• find disse 16 tabeller i databasens interne ordbog;
• åbne filer;
• allokere hukommelse;
• fjerne allokering af hukommelse;
• flette resultater;
• synkronisere mellem kerner.

Nogle usynkroniserede effekter vises stadig. De kan være ubetydelige og optage en milliarddel af den samlede tid, men de er altid ikke-nul og altid der. Med deres hjælp kan vi dramatisk miste ydeevnen efter skæring.

Dette er et standardbillede om Amdahls lov. Det vigtige her er, at linjerne, som ideelt set skal være lige og vokse lineært, løber ind i en asymptote. Men da grafen fra internettet er ulæselig, lavede jeg efter min mening mere visuelle tabeller med tal.

Lad os sige, at vi har en serialiseret del af anmodningsbehandlingen, der kun tager 5 %: seriel = 0,05 = 1/20 .

Intuitivt ser det ud til, at med en serialiseret del, der kun tager 1/20 af anmodningsbehandlingen, hvis vi paralleliserer anmodningsbehandlingen for 20 kerner, vil den blive omkring 20, i værste fald 18, gange hurtigere.

Faktisk er matematik en hjerteløs ting :

væg = 0,05 + 0,95/antal_kerner, speedup = 1 / (0,05 + 0,95/antal_kerner)

Det viser sig, at hvis man omhyggeligt beregner, med en serialiseret del på 5%, vil speedup'en være 10 gange (10,3), hvilket er 51% i forhold til det teoretiske ideal.

Efter at have brugt 20 kerner (20 diske, hvis du vil) til opgaven, som man plejede at arbejde på, vil vi aldrig engang teoretisk få en acceleration på mere end 20 gange, men i praksis - meget mindre. Desuden øges ineffektiviteten meget med en stigning i antallet af paralleller.

Når kun 1% af det serialiserede arbejde er tilbage, og 99% er paralleliseret, forbedres speedup-værdierne noget:

For en perfekt termonuklear forespørgsel, som naturligvis tager timer at fuldføre, og det forberedende arbejde og samlingen af ​​resultatet tager meget lidt tid (seriel = 0,001), vil vi allerede se god effektivitet:

Bemærk venligst, at vi aldrig vil se 100 % . I særligt gode tilfælde kan man for eksempel se 99,999 %, men ikke ligefrem 100 %.