Skärning: baksidan

2.1 Hur skära och sakta ner N gånger?

Du kan skära och sakta ner exakt N gånger så här:

• Skicka docs00...docs15-förfrågningar sekventiellt , inte parallellt.
• I enkla frågor, gör ett val inte med tangenten , WHERE something=234.

I det här fallet tar den serialiserade delen (seriell) inte 1% och inte 5%, utan cirka 20% i moderna databaser. Du kan också få 50 % av den serialiserade delen om du kommer åt databasen med ett väldigt effektivt binärt protokoll eller länkar den som ett dynamiskt bibliotek till ett Python-skript.

Resten av bearbetningstiden för en enkel begäran kommer att upptas av icke-parallellerbara operationer för att analysera begäran, förbereda planen, etc. Det vill säga att inte läsa skivan saktar ner.

Om vi ​​delar upp data i 16 tabeller och kör sekventiellt, som det är brukligt i till exempel PHP-programmeringsspråket (det är inte särskilt bra på att starta asynkrona processer), så får vi en 16-faldig avmattning. Och kanske ännu mer, eftersom även nätverksresor kommer att läggas till.

Plötsligt är valet av programmeringsspråk viktigt vid sharding.

Kom ihåg valet av programmeringsspråk, för om du skickar frågor till databasen (eller sökservern) sekventiellt, var kommer då accelerationen ifrån? Snarare blir det en avmattning.

2.2 Om halvautomatisk

På sina ställen inspirerar informationsteknologins sofistikerade chtoniska skräck. Till exempel, MySQL out of the box hade inte implementeringen av sharding till vissa versioner, men storleken på databaserna som används i strid växer till oanständiga värden.

Att lida mänskligheten inför enskilda DBA:er har plågats i åratal och skriver flera dåliga skärningslösningar baserade på ingenting. Efter det skrivs en mer eller mindre hyfsad sharding-lösning som heter ProxySQL (MariaDB/Spider, PG/pg_shard/Citus, ...). Detta är ett välkänt exempel på just denna fläck.

ProxySQL som helhet är naturligtvis en fullfjädrad lösning i företagsklass för öppen källkod, för routing med mera. Men en av uppgifterna som ska lösas är skärning för en databas, som i sig inte kan skärpa på ett mänskligt sätt. Du förstår, det finns ingen "shards = 16"-switch, du måste antingen skriva om varje begäran i applikationen, och det finns många av dem på sina ställen, eller lägga något mellanlager mellan applikationen och databasen som ser ut: "Hmm ... VÄLJA * FRÅN dokument? Ja, det måste delas upp i 16 små SELECT * FRÅN server1.dokument1, SELECT * FRÅN server2.dokument2 - till denna server med ett sådant inloggningsnamn / lösenord, till denna med en annan. Om man inte svarade, då ... ", osv. Exakt detta kan göras med mellanliggande fläckar. De är något mindre än för alla databaser. För PostgreSQL, så vitt jag förstår,

Att konfigurera varje specifik patch är ett separat jätteämne som inte passar i en rapport, så vi kommer bara att diskutera de grundläggande begreppen. Låt oss bättre prata lite om teorin om buzz.

2.3 Absolut perfekt automatisering?

Hela teorin om att bli hög vid sharding i denna bokstav F() , grundprincipen är alltid densamma ungefär: shard_id = F(objekt).

Sharding - vad handlar det om? Vi har 2 miljarder poster (eller 64). Vi vill dela upp dem i flera delar. En oväntad fråga uppstår - hur? Enligt vilken princip ska jag sprida mina 2 miljarder poster (eller 64) på ​​16 tillgängliga servrar?

Den latenta matematikern i oss borde föreslå att det i slutändan alltid finns någon magisk funktion som, för varje dokument (objekt, rad, etc.), kommer att avgöra i vilken bit det ska läggas.

Om man går djupare in i matematiken beror denna funktion alltid inte bara på själva objektet (raden själv), utan också på externa inställningar som det totala antalet skärvor. En funktion som för varje objekt måste berätta var den ska placeras, kan inte returnera ett värde mer än det finns servrar i systemet. Och funktionerna är något annorlunda:

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

Men vidare kommer vi inte att gräva ner oss i dessa vildmarker av individuella funktioner, vi kommer bara att prata om vilka magiska funktioner F () är.

2.4 Vad är F()?

De kan komma med många olika och många olika implementeringsmekanismer. Exempelsammanfattning:

• F = rand() % nums_shards
• F = somehash(objekt.id) % num_shards
• F = objekt.datum % antal_skärvor
• F = object.user_id % antal_shards
• ...
• F = shard_table [ somehash() |… objekt.datum |… ]

Ett intressant faktum - du kan naturligtvis sprida all data slumpmässigt - vi kastar nästa post på en godtycklig server, på en godtycklig kärna, i en godtycklig tabell. Det blir inte mycket glädje i det här, men det kommer att fungera.

Det finns lite mer intelligenta metoder för att skära med en reproducerbar eller till och med konsekvent hashfunktion, eller skärpa av något attribut. Låt oss gå igenom varje metod.

F = rand()

Att sprida runt är inte en särskilt korrekt metod. Ett problem: vi spred våra 2 miljarder poster på tusen servrar slumpmässigt, och vi vet inte var posten är. Vi måste dra ut user_1, men vi vet inte var han är. Vi går till tusen servrar och sorterar igenom allt - på något sätt är detta ineffektivt.

F = något hash()

Låt oss sprida användare på ett vuxet sätt: beräkna den reproducerbara hashfunktionen från user_id, ta resten av divisionen med antalet servrar och kontakta omedelbart den önskade servern.

Varför gör vi det här? Och sedan, att vi har en hög belastning och inget annat passar in i en server. Om det passade skulle livet vara så enkelt.

Bra, situationen har redan förbättrats, för att få en post går vi till en känd server i förväg. Men om vi har ett intervall av nycklar, måste vi i hela detta intervall gå igenom alla värden för nycklar och, i gränsen, gå antingen till så många skärvor som vi har nycklar i intervallet, eller till och med till varje server. Situationen har naturligtvis förbättrats, men inte för alla förfrågningar. Vissa frågor har påverkats.

Naturlig skärning (F = object.date % num_shards)

Ibland, det vill säga ofta, är 95 % av trafiken och 95 % av belastningen förfrågningar som har någon form av naturlig skärning. Till exempel påverkar 95 % av villkorligt socialanalytiska frågor endast data för den senaste 1 dagen, 3 dagarna, 7 dagarna, och de återstående 5 % hänvisar till de senaste åren. Men 95 % av förfrågningarna är alltså naturligt splittrade efter datum, systemanvändarnas intresse fokuseras på de senaste dagarna.

I det här fallet kan du dela upp data efter datum, till exempel med en dag, och följa svaret på begäran om en rapport för en dag eller ett objekt från denna dag till denna skärva och gå.

Livet förbättras - vi vet nu inte bara var ett visst föremål ligger, utan vi vet också om räckvidden. Om vi ​​tillfrågas inte om ett datumintervall, utan om ett antal andra kolumner, så måste vi naturligtvis gå igenom alla skärvor. Men enligt spelets regler har vi bara 5 % av sådana förfrågningar.

Det verkar som att vi har kommit fram till en idealisk lösning på allt, men det finns två problem:

• Denna lösning är skräddarsydd för ett specifikt fall, då 95 % av förfrågningarna endast gäller den senaste veckan.
• Eftersom 95 % av förfrågningarna rör den senaste veckan, kommer de alla att falla på en skärva som tjänar den senaste veckan. Denna skärva kommer att smälta, medan alla andra kommer att vara lediga under denna tid. Samtidigt kan du inte slänga dem, arkivdata måste också lagras.

För att inte säga att detta är ett dåligt skärningsschema - vi skär av heta data, ändå måste något göras med den hetaste skärvan.

Problemet löses med upptåg, hopp och omslag, det vill säga en ökning av antalet repliker för den brinnande aktuella dagen, sedan en gradvis minskning av antalet repliker när denna dag blir förgången och går in i arkivet. Det finns ingen idealisk lösning som heter "du behöver bara sprida data över klustret med en magisk hashfunktion på ett felaktigt sätt".

2.5 Pris som ska betalas

Formellt vet vi nu att vi vet "allt". Det är sant att vi inte känner till en jättehuvudvärk och två mindre huvudvärk.

1. Enkel smärta: dåligt utsmetad

Detta är ett exempel från en lärobok, som nästan aldrig inträffar i strid, utan plötsligt.

• Som ett exempel med en dejt, bara utan en dejt!
• Oavsiktlig ojämn (uppfattbar) fördelning.

De valde skärningsmekanismen, och/eller data ändrades, och naturligtvis förmedlade inte PM:n kraven (vi har inga fel i koden, PM:en rapporterar alltid inte kraven) och distributionen blev monstruöst ojämn. Det vill säga att de missade kriteriet.

För att fånga måste du titta på skärvornas storlek. Vi kommer definitivt att se problemet i det ögonblick då en av våra skärvor antingen överhettas eller blir 100 gånger större än de andra. Du kan fixa det helt enkelt genom att byta ut nyckeln eller skärningsfunktionen.

Detta är ett enkelt problem, för att vara ärlig, jag tror inte att minst en person av hundra kommer att stöta på detta i livet, men plötsligt kommer det att hjälpa åtminstone någon.

2. "Oövervinnerlig" smärta: aggregering, gå med

Hur gör man urval som sammanfogar en miljard poster från ett bord för en miljard poster från ett annat bord?

• Hur räknar man "snabbt"... VAR randcol MELLAN aaa OCH bbb?
• Hur gör man "smart"... users_32shards JOIN posts_1024 shards?

Kort svar: nej, lida!

Om du distribuerade en miljard poster till tusen servrar i den första tabellen så att de fungerar snabbare, och gjorde samma sak i den andra tabellen, så borde naturligtvis tusen till tusen servrar prata med varandra i par. En miljon anslutningar kommer inte att fungera bra. Om vi ​​gör förfrågningar till databasen (sökning, lagring, dokumentarkiv eller distribuerat filsystem) som inte passar bra med sharding, kommer dessa förfrågningar att sakta ner vilt.

En viktig punkt är att vissa förfrågningar alltid kommer att misslyckas och kommer att sakta ner . Det är viktigt att försöka minimera deras andel. Som en konsekvens finns det inget behov av att göra gigantiska sammanfogningar med en miljard gånger en miljard rekord. Om det är möjligt att replikera en liten tabell, i förhållande till vilken du går med i en gigantisk delad tabell, till alla noder, bör du göra det. Om kopplingarna faktiskt är lokala på något sätt, till exempel, är det möjligt att placera användaren och hans inlägg sida vid sida, skära dem på samma sätt och göra alla kopplingar inom samma maskin - du behöver göra just det .

Det här är en separat kurs med föreläsningar i tre dagar, så låt oss gå vidare till den sista helvetes smärtan och olika algoritmer för att hantera den.

2.6. Komplex/lång smärta: Återhärdande

Gör dig redo: om du delade din data för första gången i ditt liv, kommer du i genomsnitt att skära den fem gånger till.

Oavsett hur många kluster du konfigurerar, behöver du fortfarande hårdna om.

Om du är väldigt smart och har tur, överskär minst en gång. Men när du är säker, för i det ögonblick när du tror att 10 enheter räcker för användaren, skriver någon just i det ögonblicket en begäran om 30 och planerar att ha en begäran om 100 enheter av okända resurser. Skärvor räcker aldrig. Med det första skärningsschemat kommer du i alla fall att missa - du måste alltid antingen öka antalet servrar att lägga till eller göra något annat - i allmänhet, på något sätt packa om data.

Det är bra om vi har fina krafter av två: det fanns 16 serverskärvor, nu är det 32. Det är roligare om det var 17, det är 23 - två vasimalt primtal. Hur gör databaser, kanske de har någon form av magi inuti?

Det korrekta svaret är: nej, det finns ingen magi inuti, de har helvetet inuti.

Därefter kommer vi att överväga vad som kan göras "för hand", kanske vi kommer att förstå "som en automatisk maskin".

På pannan #1. Flytta allt

För alla objekt betraktar vi NewF(objekt), skift till en ny skärva.

Chansen att NewF()=OldF() matchar är låg.

Låt oss täcka nästan allt.

Åh.

Jag hoppas att det inte finns något sådant helvete som att överföra alla 2 miljarder poster från gamla skärvor till nya. Det naiva tillvägagångssättet är förståeligt: ​​det fanns 17 maskiner, 6 maskiner lades till i klustret, 2 miljarder poster sorterades bort, de flyttades från 17 maskiner till 23 maskiner. En gång vart tionde år kan du förmodligen till och med göra det. Men överlag är det ett dåligt drag.

På pannan #2. Flytta hälften

Nästa naiva förbättring - låt oss överge ett sådant dumt system - kommer att förbjuda 17 bilar från att skära om till 23, och vi kommer alltid att skära om 16 bilar till 32 bilar! Då måste vi enligt teorin flytta exakt hälften av datan, och i praktiken kan vi också göra detta.

För alla objekt betraktar vi NewF(objekt), skift till en ny skärva.

Det var strikt 2^N, nu är det strikt 2^(N+1) skärvor.

Sannolikheten att matcha NewF()=OldF() är 0,5.

Låt oss överföra cirka 50 % av datan.

Optimalt, men fungerar bara för två potenser.

I princip är allt bra, förutom bindningen till tvåstyrkan vad gäller antalet bilar. Detta naiva tillvägagångssätt kan konstigt nog fungera.

Observera att den ytterligare uppdelningen av klustret med två potenser i detta fall också är optimal. I vilket fall som helst, om vi lägger till 16 maskiner till ett kluster på 16, är vi skyldiga att flytta hälften av datan - exakt hälften och skifta.

Okej, men har mänskligheten verkligen inte uppfunnit något annat - frågan kommer från ett nyfiket sinne.

Roligare #3. Konsekvent hashning

Här krävs naturligtvis en bild med en cirkel om konsekvent hashning.

Om du googlar på "konsekvent hash" kommer definitivt en cirkel att dyka upp, alla resultat är fyllda med cirklar.

Idé: låt oss rita fragmentidentifierare (hash) på en cirkel och markera de hashade serveridentifierarna överst. När du behöver lägga till en server lägger vi en ny punkt på cirkeln, och det som visade sig vara nära den (och bara det som visade sig vara nära den), flyttar vi.

När du lägger till en skärva: vi tittar igenom inte allt, utan bara 2 "grannar", vi skiftar i genomsnitt 1/n.

När du tar bort en skärva: vi tittar bara på skärpan som raderas, vi flyttar bara den. Typ optimalt.

Väldigt effektivt när det gäller att minimera trafiken när man lägger till en shard, och helt äckligt vad gäller normal databalansering. För när vi hash alla dessa objekt som vi distribuerar till ett stort antal maskiner, gör vi det relativt ojämnt: punkterna runt cirkeln är ojämnt fördelade, och belastningen för varje enskild nod kan skilja sig mycket från resten.

Detta problem löses av den sista raden i den virtuella noden. Varje nod, varje server på cirkeln indikeras med mer än en prick. Genom att lägga till en server, en shard, etc., lägger vi till några poäng. Varje gång vi tar bort något tar vi därför bort några punkter och flyttar en liten del av datan.

Jag pratar om det här utrymmet med cirklar, eftersom till exempel ett sådant system finns inuti Cassandra. Det vill säga när hon började jaga poster mellan noder, vet att cirkeln tittar på dig och förmodligen inte godkänner.

Men jämfört med de första metoderna har livet förbättrats - när vi lägger till / tar bort en skärva tittar vi redan igenom inte alla poster, utan bara en del, och flyttar bara en del.

OBS, frågan är: kan det förbättras ytterligare? Och även förbättra enhetligheten för att lasta skärvor? De säger att det är möjligt!

Roligare #4. Rendezvous/HRW

Nästa enkla idé (materialet är pedagogiskt, så inget komplicerat): shard_id = arg max hash(object_id, shard_id).

Varför det heter Rendezvous-hashing vet jag inte, men jag vet varför det heter Högsta slumpmässiga vikt. Det är väldigt lätt att visualisera det så här:

Vi har till exempel 16 skärvor. För varje objekt (sträng) som behöver läggas någonstans, beräknar vi 16 hash beroende på objektet från skärvans nummer. Den som har det högsta hashvärdet vinner.

Detta är den så kallade HRW-hashing, aka Rendezvous-hashing. Dum som en pinne, schemat för att beräkna antalet skärvor, för det första, är lättare för ögat än cirklar och ger en enhetlig belastning, å andra sidan.

Det enda negativa är att det har blivit värre för oss att lägga till en ny skärva. Det finns en risk att när vi lägger till en ny shard har vi fortfarande några hash som kommer att ändras och det kan bli nödvändigt att granska allt. Tekniken för borttagning av skärvor har inte förändrats mycket.

Ett annat problem är att den är beräkningstung med ett stort antal skärvor.

Roligare #5. Fler tekniker

Intressant nog står forskningen inte stilla och Google publicerar en del ny rymdteknik varje år:

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

Om du är intresserad av ämnet kan du läsa många avhandlingar. Jag presenterar dessa data för att tydliggöra att problemet inte är löst, det finns ingen superlösning som kan implementeras i alla databaser. Hittills disputerar folk.

Slutsatser

Det finns en viktig grundteknik som kallas sharding uppkallad efter Gallius Julius Caesar: "Dela och härska, härska och dela!". Om data inte får plats på en server är det nödvändigt att dela upp den i 20 servrar.

Efter att ha lärt sig allt detta bör man få intrycket att det vore bättre att inte skära. Om du bestämmer dig för att det skulle vara bättre att inte skära, är detta den rätta känslan. Om du kan lägga till minne till servern för $100 och inte skära något, då bör du göra det. Vid skärning kommer ett komplext distribuerat system att dyka upp med överföring av data fram och tillbaka, stapling av data i ingen vet var. Kan det undvikas måste det undvikas.

Det är bättre att inte göra det för hand, det är bättre att "basen" (sökning, DFS, ...) kan skära sig själv. Hur som helst, förr eller senare kommer högbelastningen att komma och på något sätt måste data delas upp. Det är inte ett faktum att även om basen klarar det själv så kommer du inte att stöta på några problem. Kom ihåg om algoritmisk fundamentalism - du måste förstå hur allt fungerar inuti.

När du ställer in sharding för första gången, välj F() noggrant, tänk på förfrågningar, nätverk osv. Men gör dig redo, du måste nog välja 2 gånger och minst en gång måste du göra om allt.