În ultimii ani, odată cu apariția unor concepte precum cloud computing și big data, sistemele distribuite au câștigat popularitate și relevanță.
Un astfel de tip de sistem, cache-urile distribuite care alimentează multe site-uri web și aplicații web dinamice cu trafic ridicat, constau de obicei într-un caz particular de hashing distribuit. Acestea profită de un algoritm cunoscut sub numele de hashing consistent.
Ce este hashing-ul consistent? Care este motivația din spatele ei și de ce ar trebui să vă intereseze?
În acest articol, voi trece mai întâi în revistă conceptul general de hashing și scopul său, urmat de o descriere a hashing-ului distribuit și a problemelor pe care le implică. La rândul său, acest lucru ne va conduce la subiectul din titlu.
Ce este Hashing?
Ce înseamnă „hashing”? Merriam-Webster definește substantivul hash ca fiind „carne tocată amestecată cu cartofi și rumenită”, iar verbul ca fiind „a tăia (ca și carnea și cartofii) în bucăți mici”. Așadar, lăsând la o parte detaliile culinare, hash înseamnă, în linii mari, „tocat și amestecat” – și tocmai de aici provine termenul tehnic.
O funcție hash este o funcție care mapează o bucată de date – de obicei descriind un anumit tip de obiect, adesea de mărime arbitrară – cu o altă bucată de date, de obicei un număr întreg, cunoscută sub numele de cod hash, sau pur și simplu hash.
De exemplu, o funcție hash concepută pentru hasharea șirurilor de caractere, cu un interval de ieșire de 0 .. 100, poate să pună în corespondență șirul Hello cu, să zicem, numărul 57, Hasta la vista, baby cu numărul 33 și orice alt șir posibil cu un număr din acest interval. Deoarece există mult mai multe intrări posibile decât ieșiri, orice număr dat va avea multe șiruri diferite mapate pe el, un fenomen cunoscut sub numele de coliziune. Funcțiile hash bune ar trebui cumva să „taie și să amestece” (de unde și termenul) datele de intrare în așa fel încât ieșirile pentru diferite valori de intrare să fie răspândite cât mai uniform posibil în intervalul de ieșire.
Funcțiile hash au multe utilizări și pentru fiecare dintre ele pot fi dorite proprietăți diferite. Există un tip de funcții hash cunoscute sub numele de funcții hash criptografice, care trebuie să îndeplinească un set restrictiv de proprietăți și care sunt utilizate în scopuri de securitate – inclusiv în aplicații precum protecția parolelor, verificarea integrității și amprentarea mesajelor și detectarea corupției datelor, printre altele, dar acestea nu fac parte din domeniul de aplicare al acestui articol.
Funcțiile hash necriptografice au, de asemenea, mai multe utilizări, cea mai comună fiind utilizarea lor în tabelele hash, care este cea care ne interesează și pe care o vom explora mai detaliat.
Introducerea tabelelor hash (Hash Maps)
Imaginați-vă că avem nevoie să păstrăm o listă cu toți membrii unui club oarecare, putând în același timp să căutăm orice membru specific. Ne-am putea descurca păstrând lista într-un array (sau într-o listă legată) și, pentru a efectua o căutare, să iterăm elementele până când îl găsim pe cel dorit (am putea căuta pe baza numelui lor, de exemplu). În cel mai rău caz, acest lucru ar însemna verificarea tuturor membrilor (dacă cel pe care îl căutăm este ultimul sau nu este prezent deloc) sau, în medie, a jumătate dintre ei. În termenii teoriei complexității, căutarea ar avea atunci complexitatea O(n), și ar fi rezonabil de rapidă pentru o listă mică, dar ar deveni din ce în ce mai lentă în proporție directă cu numărul de membri.
Cum ar putea fi îmbunătățită? Să presupunem că toți acești membri ai clubului au un membru ID, care s-a întâmplat să fie un număr secvențial care reflectă ordinea în care s-au alăturat clubului.
Să presupunem că căutarea după ID ar fi acceptabilă, am putea plasa toți membrii într-un tablou, cu indicii lor potrivindu-se cu ID-urile lor (de exemplu, un membru cu ID=10 ar fi la indicele 10 în tablou). Acest lucru ne-ar permite să accesăm fiecare membru direct, fără nicio căutare. Acest lucru ar fi foarte eficient, de fapt, cât se poate de eficient, corespunzând celei mai mici complexități posibile, O(1), cunoscută și sub numele de timp constant.
Dar, trebuie să recunoaștem, scenariul nostru cu membrii clubului ID este oarecum artificial. Ce s-ar întâmpla dacă IDs-ar fi numere mari, nesecvențiale sau aleatoare? Sau, dacă căutarea după ID nu ar fi acceptabilă și ar trebui să căutăm în schimb după nume (sau după un alt câmp)? Ar fi cu siguranță util să ne păstrăm accesul direct rapid (sau ceva apropiat) și în același timp să putem gestiona seturi de date arbitrare și criterii de căutare mai puțin restrictive.
Iată unde funcțiile hash vin în ajutor. O funcție hash adecvată poate fi folosită pentru a cartografia o bucată arbitrară de date într-un număr întreg, care va juca un rol similar cu cel al membrului nostru de club ID, deși cu câteva diferențe importante.
În primul rând, o funcție hash bună are, în general, un interval de ieșire larg (de obicei, întregul interval al unui număr întreg de 32 sau 64 de biți), astfel încât construirea unei matrice pentru toți indicii posibili ar fi fie nepractică, fie pur și simplu imposibilă, și o risipă colosală de memorie. Pentru a depăși această problemă, putem avea o matrice de dimensiuni rezonabile (să zicem, doar de două ori mai mare decât numărul de elemente pe care ne așteptăm să le stocăm) și să efectuăm o operație modulo pe hash pentru a obține indexul matricei. Astfel, indexul ar fi index = hash(object) mod N, unde N este dimensiunea tabloului.
În al doilea rând, hașurile obiectelor nu vor fi unice (cu excepția cazului în care lucrăm cu un set de date fix și o funcție hash perfectă construită la comandă, dar nu vom discuta despre asta aici). Vor exista coliziuni (amplificate și mai mult de operația modulo) și, prin urmare, un simplu acces direct la index nu va funcționa. Există mai multe modalități de a gestiona acest lucru, dar una tipică este de a atașa o listă, cunoscută în mod obișnuit sub numele de bucket, la fiecare index al tabloului pentru a păstra toate obiectele care împart un anumit index.
Acum, avem un tablou de dimensiune N, cu fiecare intrare care indică un bucket de obiecte. Pentru a adăuga un nou obiect, trebuie să calculăm hash modulo N al acestuia și să verificăm bucket-ul la indexul rezultat, adăugând obiectul dacă nu se află deja acolo. Pentru a căuta un obiect, procedăm la fel, căutând doar în bucket pentru a verifica dacă obiectul se află acolo. O astfel de structură se numește tabel hash și, deși căutările în interiorul bucket-urilor sunt liniare, un tabel hash dimensionat corespunzător ar trebui să aibă un număr rezonabil de mic de obiecte per bucket, rezultând un timp de acces aproape constant (o complexitate medie de O(N/k), unde k este numărul de bucket-uri).
În cazul obiectelor complexe, funcția hash nu se aplică de obicei la întregul obiect, ci la o cheie. În exemplul nostru de membru al clubului, fiecare obiect ar putea conține mai multe câmpuri (cum ar fi nume, vârstă, adresă, e-mail, telefon), dar am putea alege, să zicem, e-mailul pentru a acționa ca cheie, astfel încât funcția hash să fie aplicată doar la e-mail. De fapt, cheia nu trebuie neapărat să facă parte din obiect; se obișnuiește să se stocheze perechi cheie/valoare, unde cheia este de obicei un șir de caractere relativ scurt, iar valoarea poate fi o bucată arbitrară de date. În astfel de cazuri, tabela hash sau harta hash este folosită ca un dicționar, și acesta este modul în care unele limbaje de nivel înalt implementează obiecte sau array-uri asociative.
Scaling Out: Hashing distribuit
Acum că am discutat despre hashing, suntem gata să ne ocupăm de hashing distribuit.
În unele situații, poate fi necesar sau de dorit să împărțim un tabel hash în mai multe părți, găzduite de servere diferite. Una dintre principalele motivații pentru aceasta este de a ocoli limitările de memorie ale utilizării unui singur calculator, permițând construirea unor tabele hash de dimensiuni arbitrar de mari (având în vedere un număr suficient de servere).
Într-un astfel de scenariu, obiectele (și cheile lor) sunt distribuite între mai multe servere, de unde și numele.
Un caz tipic de utilizare pentru acest lucru este implementarea de cache-uri în memorie, cum ar fi Memcached.
Aceste configurații constau dintr-un grup de servere de cache care găzduiesc multe perechi cheie/valoare și sunt folosite pentru a oferi acces rapid la datele stocate inițial (sau calculate) în altă parte. De exemplu, pentru a reduce încărcarea unui server de baze de date și, în același timp, pentru a îmbunătăți performanța, o aplicație poate fi proiectată pentru a prelua mai întâi datele de pe serverele de cache și numai dacă nu sunt prezente acolo – o situație cunoscută sub numele de cache miss – să apeleze la baza de date, executând interogarea relevantă și punând în cache rezultatele cu o cheie corespunzătoare, astfel încât să poată fi găsite data viitoare când este nevoie de ele.
Acum, cum are loc distribuția? Ce criterii sunt folosite pentru a determina ce chei să găzduiască în ce servere?
Cel mai simplu mod este de a lua hash-ul modulo al numărului de servere. Adică, server = hash(key) mod N, unde N este dimensiunea pool-ului. Pentru a stoca sau a prelua o cheie, clientul calculează mai întâi hash-ul, aplică o operație modulo N și utilizează indexul rezultat pentru a contacta serverul corespunzător (probabil prin utilizarea unui tabel de adrese IP). Rețineți că funcția hash utilizată pentru distribuirea cheilor trebuie să fie aceeași pentru toți clienții, dar nu este necesar să fie aceeași cu cea utilizată intern de către serverele de caching.
Să vedem un exemplu. Să presupunem că avem trei servere, A, B și C, și că avem niște chei de tip șir de caractere cu hash-urile lor:
| KEY | HASH | HASH mod 3 |
|---|---|---|
| „john” | 1633428562 | 2 |
| „bill” | 7594634739 | 0 |
| „jane” | 5000799124 | 1 |
| „steve” | 9787173343 | 0 |
| „kate” | 3421657995 | 2 |
Un client dorește să recupereze valoarea pentru cheia john. Caracterul său hash modulo 3 este 2, deci trebuie să contacteze serverul C. Cheia nu este găsită acolo, așa că clientul preia datele de la sursă și le adaugă. Grupul arată astfel:
| A | B | C |
|---|---|---|
| „john” |
În continuare, un alt client (sau același) dorește să recupereze valoarea pentru cheia bill. hash modulo 3 al acestuia este 0, deci trebuie să contacteze serverul A. Cheia nu este găsită acolo, așa că clientul preia datele de la sursă și le adaugă. Bazinul arată astfel acum:
| A | B | C |
|---|---|---|
| „bill” | „john” |
După ce cheile rămase sunt adăugate, bazinul arată astfel:
| A | B | C |
|---|---|---|
| „bill” | „jane” | „john” |
| „steve” | „kate” |
Problema refolosirii
Această schemă de distribuție este simplă, intuitivă și funcționează bine. Asta până când se schimbă numărul de servere. Ce se întâmplă dacă unul dintre servere se blochează sau devine indisponibil? Cheile trebuie să fie redistribuite pentru a ține cont de serverul lipsă, bineînțeles. Același lucru este valabil și în cazul în care unul sau mai multe servere noi sunt adăugate la pool;cheile trebuie redistribuite pentru a include noile servere. Acest lucru este valabil pentru orice schemă de distribuție, dar problema cu distribuția noastră simplă modulo este că, atunci când numărul de servere se schimbă, majoritatea hashes modulo N se va schimba, astfel încât majoritatea cheilor vor trebui mutate pe un alt server. Astfel, chiar dacă un singur server este eliminat sau adăugat, toate cheile vor trebui, probabil, să fie refăcute pe un alt server.
Din exemplul nostru anterior, dacă am eliminat serverul C, va trebui să refacem toate cheile folosind hash modulo 2 în loc de hash modulo 3, iar noile locații pentru chei ar deveni:
:
| KEY | HASH | HASH mod 2 | |
|---|---|---|---|
| „john” | 1633428562 | 0 | |
| „bill” | 7594634739 | 1 | |
| „jane” | 5000799124 | 0 | |
| „steve” | 9787173343 | 1 | |
| „kate” | 3421657995 | 1 |
| A | B |
|---|---|
| „john” | „bill” |
| „jane” | „steve” |
| „kate” |
Rețineți că toate locațiile cheie s-au schimbat, nu numai cele de pe serverul C.
În cazul tipic de utilizare pe care l-am menționat anterior (caching), acest lucru ar însemna că, dintr-o dată, cheile nu vor fi găsite deoarece nu vor fi încă prezente în noua lor locație.
Așa că, majoritatea interogărilor vor avea ca rezultat ratări, iar datele originale vor trebui probabil recuperate din nou de la sursă pentru a fi refăcute, punând astfel o sarcină mare pe serverul (serverele) de origine (de obicei o bază de date). Acest lucru poate foarte bine să degradeze grav performanța și, eventual, să prăbușească serverele de origine.
Soluția: Consistent Hashing
Atunci, cum poate fi rezolvată această problemă? Avem nevoie de o schemă de distribuție care să nu depindă direct de numărul de servere, astfel încât, atunci când se adaugă sau se elimină servere, numărul de chei care trebuie relocate să fie minimizat. O astfel de schemă – o schemă inteligentă, dar surprinzător de simplă – se numește hashing consistent și a fost descrisă pentru prima dată de Karger et al. de la MIT într-o lucrare academică din 1997 (conform Wikipedia).
Consistent Hashing este o schemă de hashing distribuită care funcționează independent de numărul de servere sau de obiecte dintr-un tabel hash distribuit prin atribuirea unei poziții pe un cerc abstract, sau inel hash. Acest lucru permite serverelor și obiectelor să se extindă fără a afecta întregul sistem.
Imaginați-vă că am cartografiat intervalul de ieșire hash pe marginea unui cerc. Aceasta înseamnă că valoarea hash minimă posibilă, zero, ar corespunde unui unghi de zero, valoarea maximă posibilă (un număr întreg mare pe care îl vom numi INT_MAX) ar corespunde unui unghi de 2𝝅 radiani (sau 360 de grade), iar toate celelalte valori hash s-ar potrivi liniar undeva între ele. Astfel, am putea lua o cheie, să-i calculăm hash-ul și să aflăm unde se află pe marginea cercului. Presupunând un INT_MAX de 1010 (de dragul exemplului), cheile din exemplul nostru anterior ar arăta astfel:
| KEY | HASH | ANGLE (DEG) | |
|---|---|---|---|
| „john” | 1633428562 | 58.8 | |
| „bill” | 7594634739 | 273.4 | |
| „jane” | 5000799124 | 180 | |
| „steve” | 9787173343 | 352.3 | |
| „kate” | 3421657995 | 123.2 |
Imaginați-vă acum că am plasat și serverele pe marginea cercului, atribuindu-le pseudo-aleatoriu și unghiuri. Acest lucru ar trebui să se facă într-un mod repetabil (sau cel puțin în așa fel încât toți clienții să fie de acord cu unghiurile serverelor). Un mod convenabil de a face acest lucru este prin hasharea numelui serverului (sau a adresei IP, sau a unui alt ID) – așa cum am face cu orice altă cheie – pentru a obține unghiul acestuia.
În exemplul nostru, lucrurile ar putea arăta astfel:
| KEY | HASH | ANGLE (DEG) | |
|---|---|---|---|
| „john” | 1633428562 | 58.8 | |
| „bill” | 7594634739 | 273.4 | |
| „jane” | 5000799124 | 180 | |
| „steve” | 9787173343 | 352.3 | |
| „kate” | 3421657995 | 123.2 | |
| „A” | 5572014558 | 200.6 | |
| „B” | 8077113362 | 290,8 | |
| „C” | 2269549488 | 81.7 |
Din moment ce avem cheile atât pentru obiecte, cât și pentru servere pe același cerc, putem defini o regulă simplă pentru a le asocia pe primele cu cele din urmă: Fiecare cheie de obiect va aparține serverului a cărui cheie este cea mai apropiată, în sens invers acelor de ceasornic (sau în sensul acelor de ceasornic, în funcție de convențiile utilizate). Cu alte cuvinte, pentru a afla ce server trebuie să cerem pentru o anumită cheie, trebuie să localizăm cheia pe cerc și să ne deplasăm în direcția unghiului ascendent până când găsim un server.
În exemplul nostru:
| KEY | HASH | ANGLE (DEG) | |
|---|---|---|---|
| „john” | 1633428562 | 58.7 | |
| „C” | 2269549488 | 81.7 | |
| „kate” | 3421657995 | 123.1 | |
| „jane” | 5000799124 | 180 | |
| „A” | 5572014557 | 200.5 | |
| „bill” | 7594634739 | 273.4 | |
| „B” | 8077113361 | 290.7 | |
| „steve” | 787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| „john” | 1632929716 | 58.7 | „C” | C |
| „kate” | 3421831276 | 123.1 | „A” | A |
| „jane” | 5000648311 | 180 | „A” | A |
| „bill” | 7594873884 | 273.4 | „B” | B |
| „steve” | 9786437450 | 352.3 | „C” | C |
Din punct de vedere al programării, ceea ce am face este să păstrăm o listă ordonată a valorilor serverului (care pot fi unghiuri sau numere în orice interval real) și să parcurgem această listă (sau să folosim o căutare binară) pentru a găsi primul server cu o valoare mai mare sau egală cu cea a cheii dorite. Dacă nu se găsește o astfel de valoare, trebuie să ne întoarcem, luându-l pe primul din listă.
Pentru a ne asigura că cheile obiectului sunt distribuite în mod egal între servere, trebuie să aplicăm un truc simplu: să atribuim nu una, ci mai multe etichete (unghiuri) fiecărui server. Astfel, în loc să avem etichete A, B și C, am putea avea, să zicem, A0 .. A9, B0 .. B9 și C0 .. C9, toate intercalate de-a lungul cercului. Factorul cu care se mărește numărul de etichete (chei de server), cunoscut sub numele de pondere, depinde de situație (și poate fi chiar diferit pentru fiecare server) pentru a ajusta probabilitatea ca cheile să ajungă pe fiecare. De exemplu, dacă serverul B ar fi de două ori mai puternic decât restul, i s-ar putea atribui de două ori mai multe etichete și, ca urmare, ar ajunge să dețină de două ori mai multe obiecte (în medie).
Pentru exemplul nostru vom presupune că toate cele trei servere au o pondere egală de 10 (acest lucru funcționează bine pentru trei servere, pentru 10 până la 50 de servere, o pondere în intervalul 100 – 500 ar funcționa mai bine, iar grupurile mai mari pot avea nevoie de ponderi chiar mai mari):
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| „C6” | 408965526 | 14.7 |
| „A1” | 473914830 | 17 |
| „A2” | 548798874 | 19.7 |
| „A3” | 1466730567 | 52.8 |
| „C4” | 1493080938 | 53.7 |
| „john” | 1633428562 | 58.7 |
| „B2” | 1808009038 | 65 |
| „C0” | 1982701318 | 71.3 |
| „B3” | 2058758486 | 74.1 |
| „A7” | 2162578920 | 77.8 |
| „B4” | 2660265921 | 95,7 |
| „C9” | 3359725419 | 120.9 |
| „kate” | 3421657995 | 123.1 |
| „A5” | 3434972143 | 123.6 |
| „C1” | 3672205973 | 132.1 |
| „C8” | 3750588567 | 135 |
| „B0” | 4049028775 | 145.7 |
| „B8” | 475552525684 | 171.1 |
| „A9” | 4769549830 | 171.7 |
| „jane” | 5000799124 | 180 |
| „C7” | 5014097839 | 180.5 |
| „B1” | 5444659173 | 196 |
| „A6” | 6210502707 | 223.5 |
| „A0” | 6511384141 | 234.4 |
| „B9” | 7292819872 | 262,5 |
| „C3” | 7330467663 | 263.8 |
| „C5” | 7502566333 | 270 |
| „bill” | 7594634739 | 273.4 |
| „A4” | 8047401090 | 289.7 |
| „C2” | 8605012288 | 309.7 |
| „A8” | 8997397092 | 323,9 |
| „B7” | 9038880553 | 325,3 |
| „B5” | 9368225254 | 337.2 |
| „B6” | 9379713761 | 337.2 |
| „B6” | 9379713761 | 337.6 |
| „steve” | 9787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| „john” | 1632929716 | 58.7 | „B2” | B |
| „kate” | 3421831276 | 123.1 | „A5” | A |
| „jane” | 5000648311 | 180 | „C7” | C |
| „bill” | 7594873884 | 273.4 | „A4” | A |
| „steve” | 9786437450 | 352.3 | „C6” | C |
Atunci, care este beneficiul acestei abordări în cerc? Imaginați-vă că serverul C este eliminat. Pentru a ține cont de acest lucru, trebuie să eliminăm etichetele C0 .. C9 din cerc. Acest lucru face ca cheile obiect anterior adiacente etichetelor eliminate să fie acum etichetate aleatoriu Ax și Bx, realocându-le serverelor A și B.
Dar ce se întâmplă cu celelalte chei obiect, cele care aparțineau inițial în A și B? Nimic! Aceasta este frumusețea lucrurilor: Absența etichetelor Cx nu afectează în niciun fel aceste chei. Așadar, eliminarea unui server are ca rezultat realocarea aleatorie a cheilor obiect ale acestuia la restul serverelor, lăsând toate celelalte chei neatinse:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| „A1” | 473914830 | 17 |
| „A2” | 548798874 | 19.7 |
| „A3” | 1466730567 | 52.8 |
| „john” | 1633428562 | 58.7 |
| „B2” | 1808009038 | 65 |
| „B3” | 2058758486 | 74.1 |
| „A7” | 2162578920 | 77,8 |
| „B4” | 2660265921 | 95.7 |
| „kate” | 3421657995 | 123.1 |
| „A5” | 3434972143 | 123.6 |
| „B0” | 4049028775 | 145.7 |
| „B8” | 475552525684 | 171.1 |
| „A9” | 4769549830 | 171.7 |
| „jane” | 5000799124 | 180 |
| „B1” | 5444659173 | 196 |
| „A6” | 6210502707 | 223.5 |
| „A0” | 6511384141 | 234.4 |
| „B9” | 7292819872 | 262.5 |
| „bill” | 7594634739 | 273.4 |
| „A4” | 8047401090 | 289.7 |
| „A8” | 8997397092 | 323.9 |
| „B7” | 9038880553 | 325.3 |
| „B5” | 9368225254 | 337.2 |
| „B6” | 9379713761 | 337.6 |
| „steve” | 9787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| „john” | 1632929716 | 58.7 | „B2” | B |
| „kate” | 3421831276 | 123.1 | „A5” | A |
| „jane” | 5000648311 | 180 | „B1” | B |
| „bill” | 7594873884 | 273.4 | „A4” | A |
| „steve” | 9786437450 | 352.3 | „A1” | A |
Se întâmplă ceva similar dacă, în loc să eliminăm un server, adăugăm unul. Dacă am dori să adăugăm serverul D la exemplul nostru (să zicem, ca înlocuitor pentru C), ar trebui să adăugăm etichetele D0 .. D9. Rezultatul ar fi că aproximativ o treime din cheile existente (toate aparținând lui A sau B) ar fi realocate lui D și, din nou, restul ar rămâne la fel:
| KEY | HASH | ANGLE (DEG) | |
|---|---|---|---|
| „D2” | 439890723 | 15.8 | |
| „A1” | 473914830 | 17 | |
| „A2” | 548798874 | 19.7 | |
| „D8” | 796709216 | 28,6 | |
| „D1” | 1008580939 | 36.3 | |
| „A3” | 1466730567 | 52,8 | |
| „D5” | 1587548309 | 57.1 | |
| „john” | 1633428562 | 58.7 | |
| „B2” | 1808009038 | 65 | |
| „B3” | 2058758486 | 74.1 | |
| „A7” | 2162578920 | 77,8 | |
| „B4” | 2660265921 | 95.7 | |
| „D4” | 2909395217 | 104.7 | |
| „kate” | 3421657995 | 123.1 | |
| „A5” | 3434972143 | 123.6 | |
| „D7” | 3567129743 | 128.4 | |
| „B0” | 4049028775 | 145.7 | |
| „B8” | 475552525684 | 171.1 | |
| „A9” | 4769549830 | 171.7 | |
| „jane” | 5000799124 | 180 | |
| „B1” | 5444659173 | 196 | |
| „D6” | 5703092354 | 205.3 | |
| „A6” | 6210502707 | 223,5 | |
| „A0” | 6511384141 | 234.4 | |
| „B9” | 7292819872 | 262.5 | |
| „bill” | 7594634739 | 273.4 | |
| „A4” | 8047401090 | 289.7 | |
| „D0” | 8272587142 | 297.8 | |
| „A8” | 8997397092 | 323.9 | |
| „B7” | 9038880553 | 325.3 | |
| „D3” | 9048608874 | 325.7 | |
| „D9” | 9314459653 | 335.3 | |
| „B5” | 9368225254 | 337.2 | |
| „B6” | 9379713761 | 337.6 | |
| „steve” | 9787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| „john” | 1632929716 | 58.7 | „B2” | B |
| „kate” | 3421831276 | 123.1 | „A5” | A |
| „jane” | 5000648311 | 180 | „B1” | B |
| „bill” | 7594873884 | 273.4 | „A4” | A |
| „steve” | 9786437450 | 352.3 | „D2” | D |
Acesta este modul în care hashing-ul consistent rezolvă problema rehashing-ului.
În general, doar k/N chei trebuie refăcute atunci când k este numărul de chei și N este numărul de servere (mai exact, maximul dintre numărul inițial și cel final de servere).
Am observat că atunci când se utilizează caching distribuit pentru a optimiza performanța, se poate întâmpla ca numărul de servere de caching să se schimbe (motivele pot fi o defecțiune a unui server sau necesitatea de a adăuga sau de a elimina un server pentru a crește sau a reduce capacitatea generală). Utilizând hashing consistent pentru a distribui cheile între servere, putem fi siguri că, în cazul în care se întâmplă acest lucru, numărul de chei care sunt refăcute – și, prin urmare, impactul asupra serverelor de origine – va fi minimizat, prevenind potențiale întreruperi sau probleme de performanță.
Există clienți pentru mai multe sisteme, cum ar fi Memcached și Redis, care includ suport pentru hashing consistent din start.
Alternativ, puteți implementa singur algoritmul, în limbajul pe care îl alegeți, iar acest lucru ar trebui să fie relativ ușor odată ce conceptul este înțeles.
Dacă știința datelor vă interesează, Toptal are unele dintre cele mai bune articole pe această temă pe blog
.