Sharding

1.1 Vad är skärning?

Om man ihärdigt googlar visar det sig att det är en ganska suddig gräns mellan den så kallade partitioneringen och den så kallade shardingen. Alla ringer vad de vill, vad de vill. Vissa människor skiljer mellan horisontell partitionering och skärning. Andra säger att skärning är en viss typ av horisontell uppdelning.

Jag hittade inte en enda terminologisk standard som skulle godkännas av grundarna och certifieras av ISO. Personlig inre övertygelse är ungefär så här: Att partitionera i genomsnitt är att "klippa basen i bitar" på ett godtyckligt sätt.

• Vertikal partitionering - efter kolumn. Det finns till exempel ett gigantiskt bord med ett par miljarder poster i 60 kolumner. Istället för att behålla en sådan gigantisk tabell, behåller vi minst 60 gigantiska tabeller med 2 miljarder poster vardera - och detta är inte en kolumnbas, utan vertikal partitionering (som ett exempel på terminologi).
• Horisontell partitionering - vi skär rad för rad, kanske inne i servern.

Det besvärliga ögonblicket här är den subtila skillnaden mellan horisontell uppdelning och skärning. Jag kan skäras i bitar, men jag kan inte säga dig säkert vad det är. Det finns en känsla av att skärning och horisontell uppdelning är ungefär samma sak.

Sharding är i allmänhet när en stor tabell i termer av databaser eller en pro-samling av dokument, objekt, om du inte har en databas, utan ett dokumentlager, skärs exakt av objekt. Det vill säga från 2 miljarder objekt väljs bitar ut oavsett storlek. Själva föremålen inuti varje föremål skärs inte i bitar, vi lägger inte ut dem i separata kolumner, nämligen vi lägger ut dem i omgångar på olika ställen.

Det finns subtila terminologiska skillnader. Till exempel, relativt sett, kan Postgres-utvecklare säga att horisontell partitionering är när alla tabeller som huvudtabellen är uppdelad i ligger i samma schema, och när det är på olika maskiner, sker detta redan.

I en allmän mening, utan att vara bunden till terminologin för en specifik databas och ett specifikt datahanteringssystem, finns det en känsla av att skärning bara är att skära rad för rad / dokument för dokument, och så vidare - det är allt.

Jag betonar typiska. I den meningen att vi gör allt detta inte bara för att skära 2 miljarder dokument i 20 tabeller, som var och en skulle vara mer hanterbar, utan för att distribuera den över många kärnor, många diskar eller många olika fysiska eller virtuella servrar.

1.2 Dela det odelbara

Det är underförstått att vi gör detta så att varje skärva - varje databit - replikeras många gånger. Men egentligen nej.

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

Faktum är att om du gör en sådan uppdelning av data, och från en gigantisk SQL-tabell på MySQL på din tappra bärbara dator, kommer du att generera 16 små tabeller, utan att gå längre än en enda bärbar dator, inte ett enda schema, inte en enda databas, etc. . och så vidare. - det är det, du har redan skärvning.

Detta resulterar i följande:

• Bandbredden ökar.
• Latensen förändras inte, det vill säga var och en, så att säga, arbetare eller konsument i detta fall, får sin egen. Olika förfrågningar betjänas ungefär samtidigt.
• Eller båda, och en annan, och även hög tillgänglighet (replikering).

Varför bandbredd? Vi kan ibland ha sådana datamängder som inte får plats - det är inte klart var, men de passar inte - på 1 {kärna | disk | server | ...}. Det finns helt enkelt inte tillräckligt med resurser, det är allt. För att kunna arbeta med denna stora datamängd måste du klippa den.

Varför latens? På en kärna är det 20 gånger långsammare att skanna en tabell med 2 miljarder rader än att skanna 20 tabeller på 20 kärnor och göra det parallellt. Data bearbetas för långsamt på en enskild resurs.

Varför hög tillgänglighet? Eller så klipper vi data för att göra båda samtidigt, och samtidigt flera kopior av varje skärva - replikering säkerställer hög tillgänglighet.

1.3 Ett enkelt exempel "hur man gör det för hand"

Villkorlig skärning kan skäras ut med testtabellen test.documents för 32 dokument, och generera 16 testtabeller från denna tabell, cirka 2 dokument vardera 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 

Varför ungefär? Eftersom vi a priori inte vet hur id fördelas, om från 1 till 32 kommer det att finnas exakt 2 dokument var, annars inte.

Vi gör det här varför. Efter att vi har gjort 16 bord kan vi "ta" 16 av det vi behöver. Oavsett vad vi träffar kan vi parallellisera dessa resurser. Till exempel, om det inte finns tillräckligt med diskutrymme, skulle det vara vettigt att dekomponera dessa tabeller på separata diskar.

Allt detta är tyvärr inte gratis. Jag misstänker att när det gäller den kanoniska SQL-standarden (jag har inte läst om SQL-standarden på länge, den kanske inte har uppdaterats på länge) så finns det ingen officiell standardiserad syntax för att säga till någon SQL-server : "Kära SQL-server, gör mig 32 shards och dela upp dem i 4 diskar. Men i enskilda implementeringar finns det ofta en specifik syntax för att göra i princip samma sak. PostgreSQL har mekanismer för partitionering, MySQL har MariaDB, Oracle gjorde förmodligen allt detta för länge sedan.

Men om vi gör det för hand, utan databasstöd och inom ramen för standarden, betalar vi villkorligt med dataåtkomstens komplexitet . Där det fanns ett enkelt SELECT * FROM dokument WHERE id=123, nu 16 x SELECT * FROM docsXX. Och det är bra om vi försökte få skivan med nyckel. Mycket mer intressant om vi försökte få ett tidigt utbud av skivor. Nu (om vi, jag betonar, är, så att säga, idioter och förblir inom ramen för standarden), kommer resultaten av dessa 16 SELECT * FROM att behöva kombineras i applikationen.

Vilken prestandaförändring kan du förvänta dig?

• Intuitivt - linjärt.
• Teoretiskt - sublinjär, eftersom Amdahl lag.
• Praktiskt taget, kanske nästan linjärt, kanske inte.

I själva verket är det rätta svaret okänt. Med en smart tillämpning av skärningstekniken kan du uppnå en betydande superlinjär försämring av din applikations prestanda, och till och med DBA kommer igång med en glödhet poker.

Låt oss se hur detta kan uppnås. Det är klart att det inte är intressant att bara sätta inställningen till PostgreSQL shards=16, och sedan tar det fart av sig själv. Låt oss fundera på hur vi kan se till att vi saktar ner från skärning med 16 gånger med 32 - det här är intressant ur synvinkeln av hur man inte gör detta.

Våra försök att snabba upp eller bromsa kommer alltid att stöta på klassikerna - den gamla goda Amdahl-lagen, som säger att det inte finns någon perfekt parallellisering av någon begäran, det finns alltid någon konsekvent del.

1.4 Amdahls lag

Det finns alltid en serialiserad del.

Det finns alltid en del av frågekörningen som är parallelliserad, och det finns alltid en del som inte är parallelliserad. Även om det verkar för dig som en perfekt parallell fråga, finns åtminstone insamlingen av resultatraden som du ska skicka till klienten från raderna som tas emot från varje skärva alltid där, och den är alltid sekventiell.

Det finns alltid någon konsekvent del. Den kan vara liten, helt osynlig mot den allmänna bakgrunden, den kan vara gigantisk och följaktligen starkt påverka parallelliseringen, men den finns alltid.

Dessutom förändras dess inflytande och kan växa avsevärt, om vi till exempel skär vårt bord – låt oss höja insatserna – från 64 poster till 16 bord med 4 poster, kommer denna del att förändras. Naturligtvis, att döma av sådana gigantiska mängder data, arbetar vi på en mobiltelefon och en 2 MHz 86-processor, och vi har inte tillräckligt med filer som kan hållas öppna samtidigt. Tydligen öppnar vi med sådana ingångar en fil i taget.

• Det var Totalt = Seriell + Parallell . Där till exempel parallell är allt arbete inuti DB, och seriell skickar resultatet till klienten.
• Blev Total2 = Seriell + Parallell/N + Xseriell . Till exempel när den totala ORDER BY, Xserial>0.

Med detta enkla exempel försöker jag visa att något Xserial dyker upp. Förutom att det alltid finns en serialiserad del, och det faktum att vi försöker arbeta med data parallellt, finns det ytterligare en del för att tillhandahålla denna dataslicing. Grovt sett kan vi behöva:

• hitta dessa 16 tabeller i databasens interna ordbok;
• öppna filer;
• allokera minne;
• avallokera minne;
• slå samman resultat;
• synkronisera mellan kärnor.

Vissa effekter som inte är synkroniserade visas fortfarande. De kan vara obetydliga och uppta en miljarddel av den totala tiden, men de är alltid från noll och alltid där. Med deras hjälp kan vi dramatiskt förlora prestanda efter skärning.

Detta är en standardbild om Amdahls lag. Det viktiga här är att linjerna, som helst ska vara raka och växa linjärt, löper in i en asymptot. Men eftersom grafen från Internet är oläslig gjorde jag, enligt mig, mer visuella tabeller med siffror.

Låt oss säga att vi har någon serialiserad del av förfrågningsbehandlingen som bara tar 5 %: seriell = 0,05 = 1/20 .

Intuitivt verkar det som att med en serialiserad del som bara tar 1/20 av begärandebehandlingen, om vi parallelliserar begäranbearbetningen för 20 kärnor, kommer den att bli cirka 20, i värsta fall 18 gånger snabbare.

Faktum är att matematik är en hjärtlös sak :

vägg = 0,05 + 0,95/antal_kärnor, speedup = 1 / (0,05 + 0,95/antal_kärnor)

Det visar sig att om man noggrant räknar, med en serialiserad del på 5 %, så blir hastigheten 10 gånger (10,3), vilket är 51 % jämfört med det teoretiska idealet.

Efter att ha använt 20 kärnor (20 diskar, om du vill) för uppgiften som man brukade arbeta med, kommer vi aldrig ens teoretiskt få en acceleration på mer än 20 gånger, men i praktiken - mycket mindre. Med ett ökat antal paralleller ökar dessutom ineffektiviteten kraftigt.

När endast 1 % av det serialiserade arbetet återstår, och 99 % är parallelliserat, förbättras hastighetshöjningsvärdena något:

För en perfekt termonukleär fråga, som naturligtvis tar timmar att slutföra, och det förberedande arbetet och monteringen av resultatet tar väldigt lite tid (seriell = 0,001), kommer vi redan att se god effektivitet:

Observera att vi aldrig kommer att se 100 % . I särskilt bra fall kan man se till exempel 99,999 %, men inte exakt 100 %.