Felosztás: hátoldal

2.1 Hogyan szilánkolás és lassítás N-szer?

Pontosan N-szer feldarabolhat és lassíthat így:

• A docs00...docs15 kéréseket egymás után küldje el , nem párhuzamosan.
• Az egyszerű lekérdezéseknél ne kulcs alapján válasszon , WHERE valami=234.

Ebben az esetben a soros rész (serial) nem 1% és nem 5%, hanem körülbelül 20% a modern adatbázisokban. A szerializált rész 50%-át is megkaphatja, ha egy rendkívül hatékony bináris protokoll használatával éri el az adatbázist, vagy dinamikus könyvtárként kapcsolja össze egy Python-szkripttel.

Egy egyszerű kérés feldolgozási idejének fennmaradó részét a kérés elemzésének, a terv elkészítésének stb. nem párhuzamosítható műveletei foglalják el. Vagyis a lemez el nem olvasása lelassul.

Ha 16 táblára osztjuk az adatokat, és szekvenciálisan lefuttatjuk, ahogy az például a PHP programozási nyelvben szokás (az aszinkron folyamatok elindításához nem túl jó), akkor 16-szoros lassulást kapunk. És talán még többet is, mert a hálózati oda-vissza utak is hozzáadásra kerülnek.

Hirtelen fontos a programozási nyelv kiválasztása a sharding során.

Emlékezz a programozási nyelv kiválasztására, mert ha szekvenciálisan küldöd a lekérdezéseket az adatbázisnak (vagy keresőszervernek), akkor honnan jön a gyorsítás? Inkább lassulás lesz.

2.2 A félautomata

Helyenként az információs technológia kifinomultsága chtonikus horrort inspirál. Például a MySQL out of the box nem biztos, hogy bizonyos verziókra implementálta a shardingot, azonban a csatában használt adatbázisok mérete méltatlan értékekre nő.

Az egyes DBA-kkal szemben szenvedő emberiség évek óta gyötrődik, és több rossz szilánkos megoldást ír a semmi alapján. Ezt követően egy többé-kevésbé tisztességes sharding megoldást írnak ProxySQL néven (MariaDB/Spider, PG/pg_shard/Citus, ...). Ez egy jól ismert példa ennek a foltnak.

A ProxySQL összességében természetesen teljes értékű vállalati szintű megoldás nyílt forráskódhoz, útválasztáshoz és még sok máshoz. De az egyik megoldandó feladat az adatbázis szilánkolása, amely önmagában emberi módon nem tud szilánkokra törni. Látod, nincs "shards = 16" kapcsoló, vagy minden kérést át kell írni az alkalmazásban, és helyenként nagyon sok van, vagy valami köztes réteget kell tenni az alkalmazás és az adatbázis közé, amely így néz ki: "Hmm ... KIVÁLASZT * A dokumentumokból? Igen, 16 kis részre kell bontani: SELECT * FROM server1.document1, SELECT * FROM server2.document2 - erre a szerverre ilyen bejelentkezési/jelszóval, erre egy másikkal. Ha valaki nem válaszolt, akkor..." stb. Pontosan ezt köztes foltokkal lehet megtenni. Valamivel kisebbek, mint az összes adatbázis esetében. A PostgreSQL esetében, ha jól értem,

Az egyes javítások konfigurálása külön óriási téma, amely nem fér bele egy jelentésbe, ezért csak az alapfogalmakat tárgyaljuk. Inkább beszéljünk egy kicsit a zümmögés elméletéről.

2.3 Abszolút tökéletes automatizálás?

Az egész elmélet a magasra jutásról ebben az F() betűben , az alapelv nagyjából mindig ugyanaz: shard_id = F(object).

Sharding – miről is van szó? 2 milliárd rekordunk van (vagy 64). Ezeket szeretnénk több részre bontani. Felmerül egy váratlan kérdés – hogyan? Milyen elv alapján szórjam szét a 2 milliárd rekordomat (vagy 64-et) a rendelkezésemre álló 16 szerveren?

A bennünk rejtőzködő matematikusnak azt kell javasolnia, hogy a végén mindig legyen valami mágikus függvény, amely minden egyes dokumentum (objektum, vonal stb.) esetében meghatározza, hogy melyik darabba kerüljön.

Ha mélyebbre megyünk a matematikában, ez a függvény nem csak magától az objektumtól (magától a sortól) függ, hanem a külső beállításoktól is, például a szilánkok teljes számától. Egy olyan függvény, amelynek minden objektumhoz meg kell adnia, hogy hova helyezze, nem adhat vissza többet, mint amennyi szerver van a rendszerben. És a funkciók kissé eltérnek:

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

De a továbbiakban nem ásunk bele az egyéni függvények vadjaiba, csak arról fogunk beszélni, hogy mik azok az F () mágikus függvények.

2.4 Mi az F()?

Sokféle és sokféle megvalósítási mechanizmust találhatnak ki. Minta összefoglaló:

• F = rand() % nums_shards
• F = somehash(object.id) % szilánkok_száma
• F = objektum.dátum % szilánkok száma
• F = objektum.felhasználói_azonosító % szilánkok_száma
• ...
• F = shard_table [ somehash() |… object.date |… ]

Érdekes tény - természetesen az összes adatot véletlenszerűen szétszórhatjuk -, a következő rekordot egy tetszőleges szerverre dobjuk, egy tetszőleges magra, egy tetszőleges táblába. Nem sok boldogság lesz ebben, de menni fog.

Léteznek valamivel intelligensebb módszerek reprodukálható vagy akár konzisztens hash-függvénnyel, vagy valamilyen attribútummal való shardra. Nézzük végig az egyes módszereket.

F = rand()

A szétszórt módszer nem túl helyes módszer. Egy probléma: véletlenszerűen szórtuk szét a 2 milliárd rekordunkat ezer szerveren, és nem tudjuk, hol van a rekord. Ki kell húznunk user_1-et, de nem tudjuk, hol van. Ezer szerverhez megyünk és mindent átválogatunk – ez valahogy nem hatékony.

F = somehash()

Felnőtt módon szórjuk szét a felhasználókat: számítsuk ki a reprodukálható hash függvényt a user_id-ből, vegyük ki az osztás maradékát a szerverek számával, és azonnal lépjen kapcsolatba a kívánt szerverrel.

Miért csináljuk ezt? Aztán, hogy nagy terhelésünk van, és semmi más nem fér bele egy szerverbe. Ha megfelelne, az élet olyan egyszerű lenne.

Remek, már javult a helyzet, egy rekord megszerzése érdekében előre megyünk egy ismert szerverre. De ha van egy kulcstartományunk, akkor ebben a teljes tartományban át kell mennünk a kulcsok összes értékén, és a limiten belül vagy annyi szilánkra kell mennünk, ahány kulcsunk van a tartományban, vagy akár minden szerver. A helyzet természetesen javult, de nem minden kérés esetében. Néhány lekérdezés érintett.

Természetes felosztás (F = objektum.dátum % szilánkok száma)

Néha, azaz gyakran a forgalom 95%-a és a terhelés 95%-a olyan kérés, amely valamilyen természetes szilánkosodást tartalmaz. Például a feltételesen társadalmi-analitikus lekérdezések 95%-a csak az elmúlt 1 nap, 3 nap, 7 nap adatait érinti, a fennmaradó 5% pedig az elmúlt néhány évre vonatkozik. De a kérések 95%-a így természetesen dátum szerint töredezett, a rendszerhasználók érdeklődése az utolsó napokra irányul.

Ebben az esetben az adatokat feloszthatja dátum szerint, például egy nappal, és követheti a jelentéskérésre adott választ egy napra vagy egy tárgyra ettől a naptól kezdve egészen a szilánkig, és már mehet is.

Az élet javulóban van – most már nemcsak egy adott objektum helyét ismerjük, hanem a hatótávolságáról is. Ha nem egy dátumtartományt, hanem egy sor egyéb rovatot kérnek tőlünk, akkor természetesen az összes szilánkot át kell mennünk. De a játékszabályok szerint az ilyen kéréseknek csak 5%-a van.

Úgy tűnik, mindenre kitaláltunk egy ideális megoldást, de két probléma van:

• Ez a megoldás egy konkrét esetre szabott, amikor a kérelmek 95%-a csak az utolsó hétre vonatkozik.
• Mivel a kérelmek 95%-a az elmúlt hetet érinti, mindegyik egy szilánkra esik, amely ezt szolgálja a múlt héten. Ez a szilánk megolvad, míg az összes többi tétlen lesz ezalatt. Ugyanakkor nem dobhatja ki őket, az archív adatokat is tárolni kell.

Nem azt mondom, hogy ez egy rossz felosztási séma - levágjuk a forró adatokat, ennek ellenére valamit tenni kell a legforróbb szilánkkal.

A problémát bohóckodások, ugrások és borogatások oldják meg, vagyis a replikák számának növelése az égető aktuális napra, majd a replikák számának fokozatos csökkenése, amikor ez a nap a múlté és az archívumba kerül. Nincs ideális megoldás az úgynevezett „csak el kell terjeszteni az adatokat a klaszteren egy varázslatos hash függvény segítségével rossz módon”.

2.5 Fizetendő ár

Formálisan már tudjuk, hogy "mindent" tudunk. Igaz, egy óriási fejfájást és két kisebb fejfájást nem ismerünk.

1. Egyszerű fájdalom: csúnyán elkenődött

Ez egy példa egy tankönyvből, ami szinte soha nem fordul elő csatában, hanem hirtelen.

• Példaként dátummal, csak randevú nélkül!
• Nem szándékos egyenetlen (érzékelhető) eloszlás.

Kiválasztották a sharling mechanizmust, és/vagy változtak az adatok, és természetesen a PM nem közvetítette a követelményeket (nincs hiba a kódban, a PM nem mindig jelenti a követelményeket), és a terjesztést szörnyen egyenetlenné vált. Vagyis elmulasztották a kritériumot.

A fogáshoz meg kell nézni a szilánkok méretét. Biztosan látni fogjuk a problémát abban a pillanatban, amikor az egyik szilánkunk vagy túlmelegszik, vagy 100-szor nagyobb lesz, mint a többi. Egyszerűen megjavíthatja a kulcs cseréjével vagy a sharding funkcióval.

Ez egy egyszerű probléma, hogy őszinte legyek, nem hiszem, hogy százból legalább egy ember belefutna ebbe az életben, de hirtelen ez legalább valakinek segít.

2. "Legyőzhetetlen" fájdalom: aggregáció, csatlakozás

Hogyan készítsünk olyan kijelöléseket, amelyek egymilliárd rekordot egyesítenek egy táblából, egy másik tábla milliárd rekordjához?

• Hogyan kell "gyorsan" kiszámolni... HOL randcol aaa ÉS bbb KÖZÖTT?
• Hogyan lehet "okosan" csinálni... users_32shards CSATLAKOZNI posts_1024 shardshoz?

Rövid válasz: dehogy, szenvedj!

Ha az első táblában ezer kiszolgálóhoz osztottunk szét egymilliárd rekordot, hogy gyorsabban működjenek, és ugyanezt tette a második táblában, akkor természetesen ezer-ezer szervernek párban kell beszélnie egymással. Egymillió kapcsolat nem fog jól működni. Ha olyan kéréseket küldünk az adatbázisba (keresés, tárolás, dokumentumtár vagy elosztott fájlrendszer), amelyek nem illeszkednek jól a shardinghoz, ezek a kérések vadul lelassulnak.

Fontos szempont, hogy egyes kérések mindig sikertelenül elkenődnek, és lelassulnak . Fontos, hogy megpróbáljuk minimálisra csökkenteni százalékos arányukat. Következésképpen nincs szükség gigantikus összeillesztésekre egymilliárdszor milliárd rekorddal. Ha lehetséges replikálni egy kis táblát, amelyhez képest egy óriási megosztott táblába csatlakozik, minden csomópontra, akkor ezt meg kell tennie. Ha például az összekapcsolások valamilyen módon lokálisak, akkor a felhasználót és a bejegyzéseit egymás mellé lehet helyezni, ugyanúgy feldarabolni, és az összes összeillesztést ugyanazon a gépen belül kell elvégezni - ezt meg kell tenni .

Ez egy különálló, háromnapos előadási kurzus, úgyhogy térjünk át az utolsó pokoli fájdalomra és a különböző kezelési algoritmusokra.

2.6. Komplex/hosszú fájdalom: Újradarabolás

Készülj fel: ha életedben először tördelted fel az adataidat, akkor átlagosan még ötször fogod feldarabolni.

Nem számít, hány fürtöt konfigurál, továbbra is újra kell tördelnie.

Ha nagyon okos és szerencsés vagy, akkor legalább egyszer éld túl. De ha már biztos vagy benne, mert abban a pillanatban, amikor úgy gondolod, hogy 10 egység elég a felhasználónak, valaki éppen abban a pillanatban ír egy kérést 30-ra, és azt tervezi, hogy 100 egységnyi ismeretlen erőforrást kér. A szilánkokból sosem elég. Az első felosztási sémával mindenesetre hiányozni fog - mindig vagy növelnie kell a hozzáadandó szerverek számát, vagy valami mást kell tennie - általában valahogy újra kell csomagolnia az adatokat.

Jó, ha kettőnek szép hatványai vannak: 16 szerverszilánk volt, most 32. Szórakoztatóbb, ha 17 volt, 23 - két vasimális prímszám. Hogy csinálják az adatbázisok, esetleg van bennük valami varázslat?

A helyes válasz: nem, nincs benne varázslat, bennük van a pokol.

Ezután megfontoljuk, hogy mit lehet „kézzel” megtenni, talán „automata gépként” fogjuk megérteni.

A homlokon #1. Mindent áthelyezni

Minden objektumnál figyelembe vesszük a NewF(object)-t, az eltolást egy új szilánkra.

A NewF()=OldF() egyezés esélye kicsi.

Szinte mindenre térjünk ki.

Ó.

Remélem, nincs olyan pokol, hogy mind a 2 milliárd rekordot a régi szilánkokról átrakják az újakra. A naiv megközelítés érthető: 17 gép volt, 6 gép került a klaszterbe, 2 milliárd rekordot rendeztek ki, 17 gépről 23 gépre kerültek. 10 évente egyszer valószínűleg megteheti. De összességében ez egy rossz lépés.

A homlokon #2. Helyezze át a felét

A következő naiv fejlesztés – hagyjuk fel az ilyen hülye sémát – megtiltja 17 autó 23-ra való átforgácsolását, és 16 autót mindig 32 autóvá fogunk újradarabolni! Ekkor az elmélet szerint pontosan az adatok felét kell eltolni, és a gyakorlatban ezt is megtehetjük.

Minden objektumnál figyelembe vesszük a NewF(object)-t, az eltolást egy új szilánkra.

Szigorúan 2^N volt, most szigorúan 2^(N+1) szilánk.

A NewF()=OldF() egyezés valószínűsége 0,5.

Vigyük át az adatok körülbelül 50%-át.

Optimális, de csak kettős hatvány esetén működik.

Elvileg minden rendben van, kivéve az autók számát tekintve kettős hatványra kötést. Ez a naiv megközelítés, furcsa módon, működhet.

Kérjük, vegye figyelembe, hogy ebben az esetben a fürt további kettõs hatványokkal történõ felosztása is optimális. Mindenesetre, ha 16 gépet adunk egy 16-os klaszterhez, kötelesek vagyunk az adatok felét eltolni - pontosan a felét és eltolni.

Oké, de tényleg nem talált ki mást az emberiség – vetődik fel a kérdés egy érdeklődő elméből.

További móka #3. Következetes kivonatolás

Természetesen itt egy kör alakú kép szükséges a következetes hashelésről.

Ha rákeresel a google-ba, hogy „konzisztens hash”, akkor biztosan kijön egy kör, az összes eredmény körökkel lesz feltöltve.

Ötlet: rajzoljunk egy körre szilánkazonosítókat (kivonatokat), és a tetejére jelöljük meg a kivonatolt szerverazonosítókat. Amikor fel kell venni egy szervert, új pontot teszünk a körre, és ami közel van hozzá (és csak ami közel volt hozzá), azt áthelyezzük.

Szilánk hozzáadásakor: nem mindent nézünk át, hanem csak 2 "szomszéd", átlagosan 1/n-t tolunk.

Szilánk törlésekor: csak a törlendő szilánkot nézzük, csak azt toljuk el. Valahogy optimális.

Nagyon hatékony a forgalom minimalizálása szempontjából szilánk hozzáadásakor, és teljesen undorító a normál adatkiegyenlítés szempontjából. Ugyanis amikor ezeket az objektumokat kivonatoljuk, amelyeket nagyszámú gépre osztunk ki, akkor azt viszonylag egyenetlenül tesszük: a kör körüli pontok egyenlőtlenül helyezkednek el, és az egyes csomópontok terhelése nagyon eltérhet a többitől.

Ezt a problémát a virtuális csomópont utolsó sora oldja meg. A kör minden csomópontját és szerverét egynél több pont jelzi. Szerver, szilánk stb. hozzáadásával néhány pontot adunk hozzá. Minden alkalommal, amikor eltávolítunk valamit, ennek megfelelően eltávolítunk néhány pontot, és eltoljuk az adatok egy kis részét.

Erről a körökkel ellátott térről beszélek, mert például Cassandra belsejében van egy ilyen séma. Vagyis amikor elkezdte üldözni a rekordokat a csomópontok között, tudd, hogy a kör rád néz, és valószínűleg nem helyesli.

Az első módszerekhez képest azonban az élet javult - egy szilánk hozzáadásakor / eltávolításakor már nem minden rekordot nézünk át, hanem csak egy részt, és csak egy részét toljuk el.

Figyelem, a kérdés az: lehet-e még javítani? És javítja a szilánkok betöltésének egyenletességét? Azt mondják, lehetséges!

További móka #4. Rendezvous/HRW

A következő egyszerű ötlet (az anyag oktató jellegű, tehát semmi bonyolult): shard_id = arg max hash(object_id, shard_id).

Hogy miért hívják Rendezvous hash-nek, azt nem tudom, de azt igen, hogy miért hívják Legmagasabb véletlenszerű súlynak. Nagyon könnyű így elképzelni:

Van például 16 szilánkunk. Minden objektumhoz (karakterlánchoz), amelyet el kell helyezni valahova, 16 hash-t számítunk ki az objektumtól függően a szilánkszámból. Akinek a legmagasabb a hash értéke, az nyer.

Ez az úgynevezett HRW-kivonat, más néven Rendezvous hash. Buta, mint a bot, a szilánkok számának kiszámításának séma először is könnyebb a szemnek, mint a köröknek, másrészt egyenletes terhelést ad.

Az egyetlen negatívum az, hogy egy új szilánk hozzáadása tovább rontott számunkra. Fennáll annak a veszélye, hogy új szilánk hozzáadásakor még mindig vannak kivonataink, amelyek változni fognak, és szükség lehet mindent felülvizsgálni. A szilánkeltávolítási technológia nem sokat változott.

Egy másik probléma, hogy számításilag nehéz, sok szilánkkal.

További móka #5. Több technika

Érdekes módon a kutatás nem áll meg, és a Google minden évben közzétesz néhány új űrtechnológiát:

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

Ha érdekli a téma, sok szakdolgozatot olvashat. Ezeket az adatokat azért mutatom be, hogy egyértelmű legyen, hogy a probléma nem oldódott meg, nincs minden adatbázisban megvalósítható szupermegoldás. Eddig az emberek dolgozatokat védenek.

következtetéseket

Létezik egy fontos alaptechnika, az úgynevezett sharding, amelyet Gallius Julius Caesarról neveztek el: „Oszd meg és uralkodj, uralkodj és oszd meg!”. Ha az adatok nem férnek el egy szerverre, akkor 20 szerverre kell felosztani.

Mindezek megtanulása után az embernek az a benyomása kell legyen, hogy jobb lenne nem szilánkolni. Ha úgy döntesz, hogy jobb, ha nem szilánkodik, ez a megfelelő érzés. Ha 100 dollárért memóriát tud hozzáadni a szerverhez, és semmit sem tör el, akkor meg kell tennie. Felosztáskor egy összetett elosztott rendszer jelenik meg, amely oda-vissza továbbítja az adatokat, és az adatokat senki sem tudja hova halmozva. Ha el lehet kerülni, akkor el kell kerülni.

Jobb, ha nem kézzel csinálod, jobb, ha az „alap” (keresés, DFS, ...) feldarabolhatja magát. Mindenesetre előbb-utóbb jön a highload és valahogy szét kell osztani az adatokat. Nem tény, hogy még ha az alap is meg tudja csinálni, akkor sem fog semmilyen problémába ütközni. Ne feledje az algoritmikus fundamentalizmust - meg kell értenie, hogyan működik minden belül.

Amikor először állítja be a felosztást, gondosan válassza az F()-t, gondolja át a kéréseket, a hálózatot stb. De készülj fel, valószínűleg kétszer kell választanod, és legalább egyszer mindent újra kell csinálnod.