Sharding: reversul

2.1 Cum să spargi și să încetinești de N ori?

Puteți fragmenta și încetini exact de N ori astfel:

• Trimiteți cereri docs00...docs15 secvenţial , nu în paralel.
• În interogări simple, faceți o selecție nu prin cheie , WHERE ceva=234.

În acest caz, partea serializată (serial) ia nu 1% și nu 5%, ci aproximativ 20% în bazele de date moderne. De asemenea, puteți obține 50% din partea serializată dacă accesați baza de date folosind un protocol binar extrem de eficient sau o legați ca bibliotecă dinamică într-un script Python.

Restul timpului de procesare a unei cereri simple va fi ocupat de operații neparalelizabile de analizare a cererii, pregătire a planului etc. Adică, a nu citi înregistrarea încetinește.

Dacă împărțim datele în 16 tabele și rulăm secvențial, așa cum este obișnuit în limbajul de programare PHP, de exemplu, (nu este foarte bun la lansarea proceselor asincrone), atunci vom obține o încetinire de 16 ori. Și, poate, chiar mai mult, pentru că se vor adăuga și călătorii dus-întors în rețea.

Dintr-o dată, alegerea limbajului de programare este importantă la sharding.

Amintiți-vă despre alegerea limbajului de programare, pentru că dacă trimiteți interogări la baza de date (sau la serverul de căutare) secvențial, atunci de unde vine accelerația? Mai degrabă, va fi o încetinire.

2.2 Despre semi-automat

Pe alocuri, sofisticarea tehnologiei informației inspiră groază htonică. De exemplu, MySQL out of the box nu a avut implementarea sharding-ului la anumite versiuni cu siguranță, cu toate acestea, dimensiunile bazelor de date folosite în luptă cresc la valori indecente.

Suferința umanității în fața DBA-urilor individuale a fost chinuită de ani de zile și scrie mai multe soluții proaste de spargere bazate pe nimic. După aceea, se scrie o soluție de sharding mai mult sau mai puțin decentă numită ProxySQL (MariaDB/Spider, PG/pg_shard/Citus, ...). Acesta este un exemplu binecunoscut al acestei pete.

ProxySQL în ansamblu este, desigur, o soluție cu drepturi depline de clasă enterprise pentru open source, pentru rutare și multe altele. Dar una dintre sarcinile care trebuie rezolvate este sharding-ul pentru o bază de date, care în sine nu poate shard într-un mod uman. Vedeți, nu există comutator „shards = 16”, fie trebuie să rescrieți fiecare cerere din aplicație și sunt multe pe alocuri, fie să puneți un strat intermediar între aplicație și baza de date care arată: „Hmm ... SELECTAȚI * DIN documente? Da, trebuie împărțit în 16 mici SELECT * FROM server1.document1, SELECT * FROM server2.document2 - la acest server cu o astfel de autentificare / parolă, la acesta cu alta. Dacă cineva nu a răspuns, atunci...”, etc. Exact acest lucru se poate face prin pete intermediare. Sunt puțin mai mici decât pentru toate bazele de date. Pentru PostgreSQL, din câte am înțeles,

Configurarea fiecărui patch specific este un subiect gigant separat, care nu se va încadra într-un singur raport, așa că vom discuta doar conceptele de bază. Să vorbim mai bine despre teoria buzz-ului.

2.3 Automatizare absolut perfectă?

Întreaga teorie a obținerii mari în cazul sharding-ului din această literă F() , principiul de bază este întotdeauna același aproximativ: shard_id = F(obiect).

Sharding - despre ce este vorba? Avem 2 miliarde de înregistrări (sau 64). Vrem să le rupem în mai multe bucăți. Apare o întrebare neașteptată - cum? După ce principiu ar trebui să-mi împrăștii cele 2 miliarde de înregistrări (sau 64) pe 16 servere disponibile pentru mine?

Matematicianul latent din noi ar trebui să sugereze că până la urmă există întotdeauna o anumită funcție magică care, pentru fiecare document (obiect, linie etc.), va determina în ce piesă să-l punem.

Mergând mai adânc în matematică, această funcție depinde întotdeauna nu numai de obiectul în sine (rândul în sine), ci și de setările externe, cum ar fi numărul total de cioburi. O funcție care pentru fiecare obiect trebuie să spună unde să-l pună, nu poate returna o valoare mai mare decât există servere în sistem. Și funcțiile sunt ușor diferite:

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

Dar, mai departe, nu vom explora aceste sălbăticie de funcții individuale, vom vorbi doar despre ce sunt funcțiile magice F ().

2.4 Ce sunt F()?

Ele pot veni cu multe mecanisme de implementare diferite și diferite. Exemplu de rezumat:

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

Un fapt interesant - puteți împrăștia în mod natural toate datele în mod aleatoriu - aruncăm următoarea înregistrare pe un server arbitrar, pe un nucleu arbitrar, într-un tabel arbitrar. Nu va fi prea multă fericire în asta, dar va funcționa.

Există metode puțin mai inteligente de a fragmenta printr-o funcție hash reproductibilă sau chiar consecventă sau a fragmentării după un anumit atribut. Să trecem prin fiecare metodă.

F = rand()

Împrăștierea în jur nu este o metodă foarte corectă. O problemă: ne-am împrăștiat aleatoriu cele 2 miliarde de înregistrări pe o mie de servere și nu știm unde este înregistrarea. Trebuie să scoatem utilizatorul_1, dar nu știm unde se află. Mergem la o mie de servere și sortăm totul - cumva acest lucru este ineficient.

F = somehash()

Să împrăștiem utilizatorii într-un mod adult: calculați funcția hash reproductibilă din user_id, luați restul împărțirii după numărul de servere și contactați imediat serverul dorit.

De ce facem asta? Și apoi, că avem o încărcare mare și nimic altceva nu se potrivește într-un singur server. Dacă s-ar potrivi, viața ar fi atât de simplă.

Grozav, situația s-a îmbunătățit deja, pentru a obține o înregistrare, mergem în avans la un server cunoscut. Dar dacă avem o gamă de chei, atunci în toată această gamă trebuie să parcurgem toate valorile cheilor și, în limită, să mergem fie la atâtea cioburi câte chei avem în gamă, fie chiar la fiecare server. Situația s-a îmbunătățit, desigur, dar nu pentru toate solicitările. Unele interogări au fost afectate.

Fragmentare naturală (F = object.date % num_shards)

Uneori, adică, adesea, 95% din trafic și 95% din încărcare sunt solicitări care au un fel de sharding natural. De exemplu, 95% dintre interogările analitice social-condiționale afectează datele numai pentru ultima zi, 3 zile, 7 zile, iar restul de 5% se referă la ultimii câțiva ani. Dar 95% dintre solicitări sunt astfel împărțite în mod natural după dată, interesul utilizatorilor de sistem fiind concentrat pe ultimele zile.

În acest caz, puteți împărți datele după dată, de exemplu, cu o zi și puteți urmări răspunsul la cererea de raport pentru o zi sau un obiect din această zi la acest fragment și mergeți.

Viața se îmbunătățește - acum nu numai că știm locația unui anumit obiect, dar știm și despre gamă. Dacă ni se cere nu o serie de date, ci o serie de alte coloane, atunci, desigur, va trebui să trecem prin toate cioburi. Dar conform regulilor jocului, avem doar 5% din astfel de solicitări.

Se pare că am venit cu o soluție ideală pentru orice, dar există două probleme:

• Această soluție este adaptată pentru un caz anume, când 95% dintre solicitări implică doar ultima săptămână.
• Deoarece 95% dintre solicitări ating ultima săptămână, toate vor cădea într-un singur fragment care servește acest lucru săptămâna trecută. Acest ciob se va topi, în timp ce toate celelalte vor fi inactiv în acest timp. În același timp, nu le puteți arunca; datele de arhivă trebuie și ele stocate.

Ca să nu spun că aceasta este o schemă de sharding proastă - tăiem datele fierbinți, cu toate acestea, trebuie făcut ceva cu cel mai tare shard.

Problema se rezolvă prin trăsături, sărituri și cataplasme, adică o creștere a numărului de replici pentru ziua curentă care arde, apoi o scădere treptată a numărului de replici când această zi devine trecută și intră în arhivă. Nu există o soluție ideală numită „trebuie doar să răspândiți datele peste cluster cu o funcție magică hash într-un mod greșit”.

2.5 Preț de plătit

Formal, știm că acum știm „totul”. Adevărat, nu cunoaștem o durere de cap uriașă și două dureri de cap mai mici.

1. Durere simplă: mânjită rău

Acesta este un exemplu dintr-un manual, care nu apare aproape niciodată în luptă, ci brusc.

• Ca exemplu cu o întâlnire, doar fără o dată!
• Distribuție neuniformă (perceptibilă) neintenționată .

Ei au ales mecanismul de sharding și/sau datele s-au schimbat și, desigur, PM-ul nu a transmis cerințele (nu avem erori în cod, PM-ul nu raportează întotdeauna cerințele) și distribuția devenit monstruos de neuniform. Adică au ratat criteriul.

Pentru a prinde, trebuie să vă uitați la dimensiunea cioburi. Cu siguranță vom vedea problema în momentul în care unul dintre cioburi fie se supraîncălzește, fie devine de 100 de ori mai mare decât celelalte. Îl puteți repara pur și simplu prin înlocuirea cheii sau a funcției de fragmentare.

Aceasta este o problemă simplă, să fiu sincer, nu cred că cel puțin o persoană din o sută se va confrunta cu asta în viață, dar dintr-o dată va ajuta măcar pe cineva.

2. Durere „invincibilă”: agregare, unire

Cum să faci selecții care unesc un miliard de înregistrări dintr-un tabel pentru un miliard de înregistrări dintr-un alt tabel?

• Cum se calculează "rapid"... UNDE randcol ÎNTRE aaa ȘI bbb?
• Cum să faci „înțelept”... users_32shards JOIN posts_1024 shards?

Răspuns scurt: în niciun caz, suferi!

Dacă ați distribuit un miliard de înregistrări la o mie de servere din primul tabel, astfel încât acestea să funcționeze mai repede și ați făcut același lucru în cel de-al doilea tabel, atunci desigur, o mie până la o mie de servere ar trebui să vorbească între ele în perechi. Un milion de conexiuni nu vor funcționa bine. Dacă facem cereri către baza de date (căutare, stocare, depozit de documente sau sistem de fișiere distribuit) care nu se potrivesc bine cu sharding-ul, aceste solicitări vor încetini sălbatic.

Un aspect important este că unele solicitări vor fi întotdeauna murdare fără succes și vor încetini . Este important să încercați să minimizați procentul acestora. În consecință, nu este nevoie să faceți unități gigantice cu înregistrări de un miliard cu un miliard. Dacă este posibil să replicați un tabel mic, în raport cu care vă alăturați într-un tabel partajat gigant, la toate nodurile, ar trebui să o faceți. Dacă îmbinările sunt de fapt locale într-un fel, de exemplu, este posibil să plasați utilizatorul și postările sale unul lângă altul, să le fragmentați în același mod și să faceți toate îmbinările în cadrul aceleiași mașini - trebuie să faceți exact asta .

Acesta este un curs separat de prelegeri de trei zile, așa că să trecem la ultima durere infernală și la diferiți algoritmi pentru a face față acesteia.

2.6. Durere complexă/prelungită: reîncărcare

Pregătește-te: dacă ți-ai spart datele pentru prima dată în viață, atunci în medie le vei sparge încă de cinci ori.

Indiferent câte clustere configurați, tot trebuie să reîncărcați.

Dacă ești foarte deștept și norocos, atunci exagerează măcar o dată. Dar odată ce ești sigur, pentru că în momentul în care crezi că 10 unități sunt suficiente pentru utilizator, cineva chiar în acel moment scrie o cerere pentru 30 și plănuiește să aibă o cerere pentru 100 de unități de resurse necunoscute. Cioburile nu sunt niciodată suficiente. Cu prima schemă de sharding, în orice caz, veți rata - va trebui întotdeauna fie să creșteți numărul de servere de adăugat, fie să faceți altceva - în general, reambalați cumva datele.

Este bine dacă avem puteri frumoase de doi: erau 16 fragmente de server, acum sunt 32. Este mai distractiv dacă era 17, este 23 - două numere prime vasimală. Cum fac bazele de date, poate au un fel de magie înăuntru?

Răspunsul corect este: nu, nu există magie înăuntru, au iadul înăuntru.

În continuare, vom lua în considerare ce se poate face „de mână”, poate că vom înțelege „ca o mașină automată”.

Pe frunte #1. Mutați totul

Pentru toate obiectele, considerăm NewF(obiect), trecerea la un nou fragment.

Șansa de potrivire NewF()=OldF() este scăzută.

Să acoperim aproape totul.

Oh.

Sper că nu există un asemenea iad care să transfere toate cele 2 miliarde de înregistrări din cioburi vechi în altele noi. Abordarea naivă este de înțeles: au fost 17 mașini, au fost adăugate 6 mașini la cluster, au fost sortate 2 miliarde de înregistrări, au fost mutate de la 17 mașini la 23 de mașini. O dată la 10 ani, probabil că o poți face. Dar, per total, este o mișcare proastă.

Pe frunte #2. Mută ​​jumătate

Următoarea îmbunătățire naivă - să renunțăm la o astfel de schemă stupidă - va interzice reîmpărțirea a 17 mașini în 23 și vom reîmpărți întotdeauna 16 mașini în 32 de mașini! Apoi, conform teoriei, va trebui să schimbăm exact jumătate din date, iar în practică putem face și acest lucru.

Pentru toate obiectele, considerăm NewF(obiect), trecerea la un nou fragment.

Era strict 2^N, acum este strict 2^(N+1) cioburi.

Probabilitatea de potrivire NewF()=OldF() este 0,5.

Să transferăm aproximativ 50% din date.

Optim, dar funcționează doar pentru puteri de doi.

În principiu, totul este în regulă, cu excepția legării la puterea a doi în ceea ce privește numărul de mașini. Această abordare naivă, destul de ciudat, poate funcționa.

Vă rugăm să rețineți că împărțirea suplimentară a clusterului cu puteri de două în acest caz este, de asemenea, optimă. În orice caz, adăugând 16 mașini la un grup de 16, suntem obligați să deplasăm jumătate din date - exact jumătate și să schimbăm.

Bine, dar omenirea chiar nu a inventat altceva - întrebarea apare dintr-o minte curios.

Mai multă distracție #3. Hashing constant

Desigur, aici este necesară o imagine cu un cerc despre hashing consistent.

Dacă căutați pe Google „hashing consistent”, atunci cu siguranță va ieși un cerc, toate rezultatele sunt populate cu cercuri.

Idee: să desenăm identificatori de shard (hash) pe un cerc și să marchem identificatorii serverului hash deasupra. Când trebuie să adăugați un server, punem un nou punct pe cerc și ceea ce s-a dovedit a fi aproape de el (și doar ceea ce s-a dovedit a fi aproape de el), ne relocam.

La adăugarea unui ciob: ne uităm nu prin toate, ci doar prin 2 „vecini”, ne deplasăm în medie 1/n.

La ștergerea unui shard: ne uităm doar la shard-ul care este șters, îl deplasăm doar pe el. Un fel de optim.

Foarte eficient în ceea ce privește reducerea la minimum a traficului la adăugarea unui shard și absolut dezgustător în ceea ce privește echilibrarea normală a datelor. Pentru că atunci când împingem toate aceste obiecte pe care le distribuim unui număr mare de mașini, o facem relativ neuniform: punctele din jurul cercului sunt distanțate neuniform, iar sarcina fiecărui nod anume poate fi foarte diferită de restul.

Această problemă este rezolvată de ultima linie a nodului virtual. Fiecare nod, fiecare server de pe cerc este indicat de mai mult de un punct. Adăugând un server, un shard etc., adăugăm câteva puncte. De fiecare dată când eliminăm ceva, în consecință, eliminăm câteva puncte și deplasăm o mică parte din date.

Vorbesc despre acest spațiu cu cercuri, pentru că, de exemplu, o astfel de schemă este în interiorul Cassandrei. Adică, când a început să urmărească înregistrările între noduri, să știi că cercul se uită la tine și probabil că nu aprobă.

Cu toate acestea, în comparație cu primele metode, viața s-a îmbunătățit - atunci când adăugăm/eliminăm un ciob, examinăm deja nu toate înregistrările, ci doar o parte și schimbăm doar o parte.

Atenție, întrebarea este: se poate îmbunătăți în continuare? Și, de asemenea, să îmbunătățească uniformitatea cioburilor de încărcare? Ei spun că se poate!

Mai multă distracție #4. Întâlnire/HRW

Următoarea idee simplă (materialul este educațional, deci nimic complicat): shard_id = arg max hash(object_id, shard_id).

De ce se numește hashing Rendezvous, nu știu, dar știu de ce se numește Cea mai mare greutate aleatorie. Este foarte ușor să-l vizualizați astfel:

Avem, de exemplu, 16 cioburi. Pentru fiecare obiect (șir) care trebuie pus undeva, calculăm 16 hashe-uri în funcție de obiectul din numărul fragmentului. Cine are cea mai mare valoare hash câștigă.

Acesta este așa-numitul HRW-hashing, alias Rendezvous hashing. Mută ​​ca un băț, schema de calcul a numărului de cioburi, în primul rând, este mai ușoară pentru ochi decât cercurile și, pe de altă parte, oferă o sarcină uniformă.

Singurul negativ este că adăugarea unui nou ciob s-a înrăutățit pentru noi. Există riscul ca atunci când adăugați un nou shard, să avem în continuare niște hashe-uri care se vor schimba și poate fi necesar să revizuim totul. Tehnologia de îndepărtare a cioburilor nu s-a schimbat prea mult.

O altă problemă este că este greu din punct de vedere computațional cu un număr mare de cioburi.

Mai multă distracție #5. Mai multe tehnici

Interesant este că cercetările nu stau pe loc și Google publică o nouă tehnologie spațială în fiecare an:

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

Dacă ești interesat de subiect, poți citi multe disertații. Prezint aceste date pentru a face clar că problema nu a fost rezolvată, nu există o super-soluție care să poată fi implementată în toate bazele de date. Până acum, oamenii susțin disertații.

concluzii

Există o tehnică de bază importantă numită sharding numită după Gallius Julius Caesar: „Împărțiți și stăpâniți, stăpâniți și împărțiți!”. Dacă datele nu se potrivesc într-un singur server, este necesar să le împărțiți în 20 de servere.

După ce am învățat toate acestea, ar trebui să aveți impresia că ar fi mai bine să nu se ciobească. Dacă decideți că ar fi mai bine să nu ciobiți, acesta este sentimentul potrivit. Dacă puteți adăuga memorie la server pentru 100 USD și nu fragmentați nimic, atunci ar trebui să o faceți. La sharding, va apărea un sistem complex distribuit cu transferul de date înainte și înapoi, stivuind date în nimeni nu știe unde. Dacă poate fi evitat, trebuie evitat.

Este mai bine să nu o faceți manual, este mai bine ca „baza” (căutare, DFS, ...) să se poată sparge. În orice caz, mai devreme sau mai târziu, va veni încărcarea mare și, cumva, datele vor trebui împărțite. Nu este un fapt că, chiar dacă baza o poate face singură, nu vei întâmpina probleme. Amintiți-vă despre fundamentalismul algoritmic - trebuie să înțelegeți cum funcționează totul în interior.

Când configurați sharding-ul pentru prima dată, alegeți cu atenție F(), gândiți-vă la solicitări, rețea etc. Dar pregătiți-vă, probabil că va trebui să alegeți de 2 ori și măcar o dată va trebui să refaceți totul.