Course All lectures for NL purposes - Lecture: Scherven: achterkant

2.1 Hoe shard en vertraag je N keer?

Je kunt exact N keer zo sharden en vertragen:

Verzend docs00...docs15-verzoeken opeenvolgend , niet parallel.
Maak bij eenvoudige zoekopdrachten een selectie niet op sleutel , WHERE something=234.

In dit geval neemt het geserialiseerde deel (serieel) niet 1% en niet 5%, maar ongeveer 20% in moderne databases. U kunt ook 50% van het geserialiseerde deel krijgen als u de database benadert met behulp van een enorm efficiënt binair protocol of als u deze als een dynamische bibliotheek koppelt aan een Python-script.

De rest van de verwerkingstijd van een eenvoudig verzoek zal worden ingenomen door niet-paralleleerbare bewerkingen zoals het ontleden van het verzoek, het opstellen van het plan, enz. Dat wil zeggen, het niet lezen van de plaat vertraagt.

Als we de gegevens in 16 tabellen verdelen en sequentieel uitvoeren, zoals gebruikelijk is in bijvoorbeeld de programmeertaal PHP (die is niet erg goed in het starten van asynchrone processen), dan krijgen we een 16-voudige vertraging. En misschien zelfs wel meer, want er komen ook netwerkrondreizen bij.

Plots is de keuze van de programmeertaal belangrijk bij sharding.

Denk aan de keuze van de programmeertaal, want als u achtereenvolgens query's naar de database (of zoekserver) stuurt, waar komt de versnelling dan vandaan? Er zal eerder sprake zijn van een vertraging.

2.2 Over semi-automatisch

Op sommige plaatsen inspireert de verfijning van informatietechnologie chtonische horror. MySQL had bijvoorbeeld out of the box niet de implementatie van sharding naar bepaalde versies, maar de omvang van de databases die in de strijd worden gebruikt, groeit uit tot onfatsoenlijke waarden.

De mensheid lijden in het aangezicht van individuele DBA's wordt al jaren gekweld en schrijft verschillende slechte sharding-oplossingen op basis van niets. Daarna wordt een min of meer degelijke sharding-oplossing geschreven genaamd ProxySQL (MariaDB/Spider, PG/pg_shard/Citus, ...). Dit is een bekend voorbeeld van deze vlek.

ProxySQL als geheel is natuurlijk een volwaardige enterprise-class oplossing voor open source, voor routering en meer. Maar een van de taken die moet worden opgelost, is sharding voor een database, die op zichzelf niet op een menselijke manier kan sharden. Zie je, er is geen schakelaar "shards = 16", je moet ofwel elk verzoek in de applicatie herschrijven, en er zijn er veel op plaatsen, of een tussenlaag plaatsen tussen de applicatie en de database die eruitziet: "Hmm ... SELECT * UIT documenten? Ja, het moet worden opgesplitst in 16 kleine SELECT * FROM server1.document1, SELECT * FROM server2.document2 - naar deze server met zo'n login / wachtwoord, naar deze met een andere. Als men niet antwoordde, dan ... ", enz. Precies dit kan worden gedaan door tussenliggende vlekken. Ze zijn iets minder dan voor alle databases. Voor PostgreSQL, voor zover ik begrijp,

Het configureren van elke specifieke patch is een apart gigantisch onderwerp dat niet in één rapport past, dus we zullen alleen de basisconcepten bespreken. Laten we het beter eens hebben over de theorie van buzz.

2.3 Absoluut perfecte automatisering?

De hele theorie van high worden in het geval van sharding in deze letter F() , het basisprincipe is altijd ongeveer hetzelfde: shard_id = F(object).

Scherven - waar gaat het allemaal over? We hebben 2 miljard records (of 64). We willen ze in verschillende stukken breken. Een onverwachte vraag rijst - hoe? Volgens welk principe moet ik mijn 2 miljard records (of 64) verspreiden over 16 servers die voor mij beschikbaar zijn?

De latente wiskundige in ons zou moeten suggereren dat er uiteindelijk altijd een magische functie is die voor elk document (object, lijn, enz.) zal bepalen in welk stuk het moet worden geplaatst.

Als we dieper ingaan op de wiskunde, hangt deze functie altijd niet alleen af van het object zelf (de rij zelf), maar ook van externe instellingen zoals het totale aantal scherven. Een functie die voor elk object moet aangeven waar het geplaatst moet worden, kan niet meer waarde teruggeven dan er servers in het systeem zijn. En de functies zijn iets anders:

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

Maar verder gaan we niet dieper in op deze wilds van individuele functies, we zullen het alleen hebben over wat magische functies F () zijn.

2.4 Wat is F()?

Ze kunnen veel verschillende en veel verschillende implementatiemechanismen bedenken. Voorbeeld samenvatting:

F = rand() % nums_shards
F = somehash(object.id) % num_shards
F = object.date % num_shards
F = object.user_id % num_shards
...
F = shard_table [somehash() |... object.date |...]

Een interessant feit - je kunt natuurlijk alle gegevens willekeurig verspreiden - we gooien het volgende record op een willekeurige server, op een willekeurige kern, in een willekeurige tabel. Hier zal niet veel geluk in zitten, maar het zal werken.

Er zijn iets intelligentere methoden om te sharden door een reproduceerbare of zelfs consistente hash-functie, of om te sharden door een attribuut. Laten we elke methode doornemen.

F = rand()

Rondstrooien is geen erg correcte methode. Eén probleem: we hebben onze 2 miljard records willekeurig verspreid over duizend servers en we weten niet waar het record is. We moeten gebruiker_1 eruit halen, maar we weten niet waar hij is. We gaan naar duizend servers en doorzoeken alles - op de een of andere manier is dit inefficiënt.

F = een beetje()

Laten we gebruikers op een volwassen manier verspreiden: bereken de reproduceerbare hashfunctie van user_id, neem de rest van de deling door het aantal servers en neem onmiddellijk contact op met de gewenste server.

Waarom doen we dit? En dan, dat we een hoge belasting hebben en niets anders op één server past. Als het zou passen, zou het leven zo eenvoudig zijn.

Geweldig, de situatie is al verbeterd, om één record te krijgen, gaan we van tevoren naar één bekende server. Maar als we een reeks sleutels hebben, dan moeten we in dit hele bereik alle waarden van de sleutels doorlopen en, binnen de limiet, naar zoveel scherven gaan als we sleutels in het bereik hebben, of zelfs naar elke server. De situatie is natuurlijk verbeterd, maar niet voor alle verzoeken. Sommige zoekopdrachten zijn beïnvloed.

Natuurlijke sharding (F = object.date % num_shards)

Soms, dat wil zeggen vaak, zijn 95% van het verkeer en 95% van de belasting verzoeken die een soort van natuurlijke sharding hebben. Zo heeft 95% van de voorwaardelijk sociaal-analytische zoekopdrachten alleen betrekking op gegevens van de laatste 1 dag, 3 dagen, 7 dagen, en de overige 5% heeft betrekking op de afgelopen jaren. Maar 95% van de verzoeken zijn dus natuurlijk geshard op datum, de interesse van systeemgebruikers is gericht op de afgelopen dagen.

In dit geval kunt u de gegevens op datum delen, bijvoorbeeld door één dag, en de reactie op het verzoek om een rapport voor een bepaalde dag of een object van deze dag naar deze scherf volgen en gaan.

Het leven wordt beter - we weten nu niet alleen de locatie van een bepaald object, maar we weten ook wat het bereik is. Als ons niet om een reeks datums wordt gevraagd, maar om een reeks andere kolommen, dan zullen we natuurlijk alle scherven moeten doornemen. Maar volgens de spelregels hebben we slechts 5% van dergelijke verzoeken.

Het lijkt erop dat we voor alles een ideale oplossing hebben bedacht, maar er zijn twee problemen:

Deze oplossing is op maat gemaakt voor een specifiek geval, wanneer 95% van de verzoeken alleen betrekking heeft op de laatste week.
Aangezien 95% van de verzoeken de afgelopen week betreft, vallen ze allemaal op één scherf die deze laatste week dient. Deze scherf zal smelten, terwijl alle anderen gedurende deze tijd inactief zullen zijn. Tegelijkertijd mag je ze niet weggooien, ook archiefgegevens moeten bewaard worden.

Om niet te zeggen dat dit een slecht sharding-schema is - we hebben hot data afgesneden, maar toch moet er iets worden gedaan met de heetste scherf.

Het probleem wordt opgelost door capriolen, sprongen en kompressen, dat wil zeggen een toename van het aantal replica's voor de brandende huidige dag, en vervolgens een geleidelijke afname van het aantal replica's wanneer deze dag voorbij is en naar het archief gaat. Er is geen ideale oplossing genaamd "je hoeft alleen maar de data op een verkeerde manier over het cluster te verspreiden met een magische hashfunctie".

2.5 Prijs te betalen

Formeel weten we nu dat we "alles" weten. Toegegeven, we kennen niet één gigantische hoofdpijn en twee kleinere hoofdpijn.

1. Simpele pijn: erg besmeurd

Dit is een voorbeeld uit een leerboek, dat bijna nooit voorkomt in een gevecht, maar plotseling.

Als voorbeeld met een datum, alleen zonder datum!
Onbedoelde ongelijke (waarneembare) verdeling.

Ze kozen voor het sharding-mechanisme en/of de gegevens veranderden, en natuurlijk bracht de PM de vereisten niet over (we hebben geen fouten in de code, de PM rapporteert altijd niet de vereisten), en de distributie werd monsterlijk ongelijk. Dat wil zeggen, ze misten het criterium.

Om te vangen, moet je kijken naar de grootte van de scherven. We zullen het probleem zeker zien op het moment dat een van onze scherven oververhit raakt of 100 keer groter wordt dan de andere. U kunt dit eenvoudig oplossen door de sleutel of de sharding-functie te vervangen.

Dit is een eenvoudig probleem, om eerlijk te zijn, ik denk niet dat minstens één op de honderd mensen dit in het leven tegenkomt, maar ineens zal het in ieder geval iemand helpen.

2. "Onoverwinnelijke" pijn: aggregatie, meedoen

Hoe maak je selecties die een miljard records uit de ene tabel samenvoegen voor een miljard records uit een andere tabel?

Hoe "snel" berekenen... WAAR randcol TUSSEN aaa EN bbb?
Hoe "slim" te doen... users_32shards DOE MEE MET posts_1024 shards?

Kort antwoord: echt niet, lijd!

Als je in de eerste tabel een miljard records hebt gedistribueerd naar duizend servers zodat ze sneller werken, en hetzelfde deed in de tweede tabel, dan zouden natuurlijk duizend tot duizend servers in paren met elkaar moeten praten. Een miljoen verbindingen zullen niet goed werken. Als we verzoeken doen aan de database (zoeken, opslaan, documentopslag of gedistribueerd bestandssysteem) die niet goed passen bij sharding, zullen deze verzoeken enorm vertragen.

Een belangrijk punt is dat sommige verzoeken altijd zonder succes worden uitgesmeerd en vertragen . Het is belangrijk om te proberen hun percentage te minimaliseren. Hierdoor is het niet nodig om gigantische joins te maken met een miljard bij een miljard records. Als het mogelijk is om een kleine tabel, ten opzichte waarvan u deelneemt in een gigantische gedeelde tabel, te repliceren naar alle knooppunten, dan moet u dat doen. Als de joins bijvoorbeeld op de een of andere manier lokaal zijn, is het mogelijk om de gebruiker en zijn berichten naast elkaar te plaatsen, ze op dezelfde manier te sharden en alle joins binnen dezelfde machine te doen - je moet precies dat doen .

Dit is een aparte cursus van drie dagen, dus laten we verder gaan met de laatste helse pijn en verschillende algoritmen om ermee om te gaan.

2.6. Complexe/Lange Pijn: Resharding

Maak je klaar: als je je gegevens voor het eerst in je leven versnippert, dan doe je dat gemiddeld nog vijf keer.

Het maakt niet uit hoeveel clusters u configureert, u moet nog steeds opnieuw harden.

Als je heel slim en gelukkig bent, overshard dan minstens één keer. Maar als je het eenmaal zeker weet, want op het moment dat je denkt dat 10 eenheden genoeg zijn voor de gebruiker, schrijft iemand op dat moment een verzoek voor 30 en is van plan een verzoek te hebben voor 100 eenheden onbekende bronnen. Scherven zijn nooit genoeg. Met het eerste sharding-schema mis je in ieder geval - je zult altijd ofwel het aantal toe te voegen servers moeten verhogen, ofwel iets anders moeten doen - in het algemeen de gegevens op de een of andere manier opnieuw verpakken.

Het is goed als we mooie machten van twee hebben: er waren 16 serverscherven, nu zijn het er 32. Het is leuker als het 17 was, het is 23 - twee vasimaal priemgetallen. Hoe doen databases het, misschien hebben ze een soort magie in zich?

Het juiste antwoord is: nee, er zit geen magie in, ze hebben de hel van binnen.

Vervolgens zullen we bekijken wat er "met de hand" kan worden gedaan, misschien begrijpen we "als een automatische machine".

Op het voorhoofd #1. Alles verhuizen

Voor alle objecten beschouwen we NewF(object), shift naar een nieuwe scherf.

De kans op NewF()=OldF()-matching is klein.

Laten we bijna alles behandelen.

Oh.

Ik hoop dat er geen hel bestaat om alle 2 miljard records over te zetten van oude scherven naar nieuwe. De naïeve aanpak is begrijpelijk: er waren 17 machines, er werden 6 machines aan het cluster toegevoegd, 2 miljard records werden uitgezocht, ze werden verplaatst van 17 machines naar 23 machines. Eens in de 10 jaar kun je het waarschijnlijk zelfs doen. Maar over het algemeen is het een slechte zet.

Op het voorhoofd #2. Verplaats de helft

De volgende naïeve verbetering - laten we van zo'n stom plan afstappen - verbiedt 17 auto's om opnieuw in te delen in 23, en we zullen altijd 16 auto's opnieuw indelen in 32 auto's! Dan zullen we volgens de theorie precies de helft van de data moeten verschuiven, en in de praktijk kunnen we dit ook.

Voor alle objecten beschouwen we NewF(object), shift naar een nieuwe scherf.

Het was strikt 2^N, nu is het strikt 2^(N+1) scherven.

De kans op het matchen van NewF()=OldF() is 0,5.

Laten we ongeveer 50% van de gegevens overdragen.

Optimaal, maar werkt alleen voor machten van twee.

In principe is alles in orde, behalve het binden aan de macht van twee qua aantal auto's. Deze naïeve benadering kan, vreemd genoeg, werken.

Houd er rekening mee dat de extra splitsing van de cluster door machten van twee in dit geval ook optimaal is. In ieder geval, als we 16 machines toevoegen aan een cluster van 16, zijn we verplicht om de helft van de gegevens te verschuiven - precies de helft en verschuiven.

Oké, maar heeft de mensheid echt niets anders uitgevonden - de vraag komt voort uit een nieuwsgierige geest.

Meer plezier #3. Consistent hashen

Natuurlijk is hier een afbeelding met een cirkel over consistente hashing vereist.

Als je "consistente hashing" googelt, dan komt er zeker een cirkel uit, alle resultaten zijn gevuld met cirkels.

Idee: laten we shard-ID's (hashes) op een cirkel tekenen en de gehashte server-ID's bovenaan markeren. Als je een server moet toevoegen, plaatsen we een nieuw punt op de cirkel, en wat er dichtbij bleek te zijn (en alleen wat er dichtbij bleek te zijn), verplaatsen we.

Bij het toevoegen van een scherf: we kijken niet door alles, maar slechts 2 "buren", we verschuiven gemiddeld 1/n.

Bij het verwijderen van een scherf: we kijken alleen naar de scherf die wordt verwijderd, we verplaatsen alleen deze. Een beetje optimaal.

Zeer effectief in termen van het minimaliseren van verkeer bij het toevoegen van een scherf, en absoluut walgelijk in termen van normale gegevensbalans. Want als we al deze objecten die we over een groot aantal machines verdelen, hashen, doen we dat relatief ongelijk: de punten rond de cirkel zijn ongelijk verdeeld en de belasting van elk afzonderlijk knooppunt kan heel anders zijn dan de rest.

Dit probleem wordt opgelost door de laatste regel van het virtuele knooppunt. Elk knooppunt, elke server op de cirkel wordt aangegeven met meer dan één punt. Door een server, een shard, etc. toe te voegen, voegen we een paar punten toe. Elke keer dat we iets verwijderen, verwijderen we dienovereenkomstig een paar punten en verschuiven we een klein deel van de gegevens.

Ik heb het over deze ruimte met cirkels, omdat zo'n schema bijvoorbeeld in Cassandra zit. Dat wil zeggen, wanneer ze records tussen knooppunten begon na te jagen, weet dan dat de cirkel naar je kijkt en het waarschijnlijk niet goedkeurt.

In vergelijking met de eerste methoden is het leven echter verbeterd - bij het toevoegen / verwijderen van een scherf kijken we al door niet alle records, maar slechts een deel, en verschuiven we slechts een deel.

Let op, de vraag is: kan het nog beter? En ook de uniformiteit van het laden van scherven verbeteren? Ze zeggen dat het mogelijk is!

Meer plezier #4. Rendez-vous/HRW

Het volgende eenvoudige idee (het materiaal is educatief, dus niets ingewikkelds): shard_id = arg max hash(object_id, shard_id).

Waarom het Rendezvous-hashing wordt genoemd, weet ik niet, maar ik weet wel waarom het Highest Random Weight wordt genoemd. Het is heel gemakkelijk om het als volgt te visualiseren:

We hebben bijvoorbeeld 16 scherven. Voor elk object (string) dat ergens geplaatst moet worden, berekenen we 16 hashes afhankelijk van het object uit het shardnummer. Degene met de hoogste hash-waarde wint.

Dit is de zogenaamde HRW-hashing, oftewel Rendezvous-hashing. Stom als een stok, het schema voor het berekenen van het aantal van een scherf is in de eerste plaats prettiger voor het oog dan cirkels en geeft aan de andere kant een uniforme belasting.

Het enige negatieve is dat het toevoegen van een nieuwe scherf voor ons is verslechterd. Het risico bestaat dat we bij het toevoegen van een nieuwe shard nog enkele hashes hebben die zullen veranderen en dat het nodig kan zijn om alles opnieuw te bekijken. De technologie voor het verwijderen van scherfjes is niet veel veranderd.

Een ander probleem is dat het rekenkundig zwaar is met een groot aantal scherven.

Meer plezier #5. Meer technieken

Interessant genoeg staat onderzoek niet stil en publiceert Google elk jaar nieuwe ruimtetechnologie:

Jump-hasj - Google '2014.
Multi-sonde—Google '2015.
Maglev-Google '2016.

Als je geïnteresseerd bent in het onderwerp, kun je veel dissertaties lezen. Ik presenteer deze gegevens om duidelijk te maken dat het probleem niet is opgelost, er is geen superoplossing die in alle databases kan worden geïmplementeerd. Tot nu toe verdedigt men proefschriften.

conclusies

Er is een belangrijke basistechniek genaamd sharding genoemd naar Gallius Julius Caesar: “Verdeel en heers, heers en verdeel!”. Als de gegevens niet op één server passen, is het noodzakelijk om deze op te splitsen in 20 servers.

Als je dit alles hebt geleerd, zou je de indruk moeten krijgen dat het beter is om niet te scherven. Als je besluit dat het beter is om niet te sharden, dan is dit het juiste gevoel. Als je geheugen aan de server kunt toevoegen voor $ 100 en niets kunt sharden, dan zou je het moeten doen. Bij sharding zal een complex gedistribueerd systeem verschijnen met het heen en weer overbrengen van gegevens, waarbij gegevens worden gestapeld op niemand weet waar. Als het vermeden kan worden, moet het vermeden worden.

Het is beter om het niet met de hand te doen, het is beter dat de "basis" (zoeken, DFS, ...) zichzelf kan sharden. Hoe dan ook, vroeg of laat zal er een hoge belasting komen en zullen de gegevens op de een of andere manier moeten worden gesplitst. Het is geen feit dat zelfs als de basis het zelf kan, je geen problemen zult tegenkomen. Denk aan algoritmisch fundamentalisme - je moet begrijpen hoe alles van binnen werkt.

Kies F() zorgvuldig wanneer u sharding voor het eerst instelt, denk na over verzoeken, netwerk, enz. Maar maak je klaar, je zult waarschijnlijk 2 keer moeten kiezen en minstens één keer moet je alles opnieuw doen.