Consistent Hashing este o tehnică de hashing care se comportă foarte bine atunci când este operată într-un mediu dinamic în care sistemul distribuit crește și scade frecvent. Conceptul de bază al hashing-ului consecvent a fost introdus în lucrarea Consistent Hashing and RandomTrees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, dar a câștigat popularitate după celebra lucrare de prezentare a DynamoDB – Dynamo: Amazon’s Highly Available Key-value Store. De atunci, hashing-ul consistent a câștigat popularitate și a găsit o mulțime de cazuri de utilizare în proiectarea și scalarea eficientă a sistemelor distribuite. Cele două exemple faimoase care utilizează în mod exhaustiv această tehnică sunt Bit Torrent, pentru rețelele peer-to-peer și Akamai, pentru cache-urile lor web. În acest articol ne scufundăm adânc în nevoia de Consistent Hashing, în elementele sale interne și, mai important, pe parcurs o implementăm folosind array-uri și Binary Search.

Înainte de a trece la tehnica de bază Consistent Hashing, trebuie mai întâi să clarificăm câteva lucruri, dintre care unul este Hash Functions. Funcțiile Hash sunt orice funcții care mapează valoarea dintr-un domeniu de mărime arbitrară într-un alt domeniu de mărime fixă, numit de obicei spațiu Hash. De exemplu, maparea URL-urilor în numere întregi pe 32 de biți sau a conținutului HTML al paginilor web într-un șir de 256 de octeți. Valorile generate la ieșirea acestor funcții hash sunt utilizate de obicei ca chei pentru a permite căutări eficiente ale entității originale.

Un exemplu de funcție hash simplă este o funcție care mapează un întreg de 32 de biți într-un spațiu hash de 8 biți. Funcția ar putea fi implementată folosind operatorul aritmetic modulo și putem realiza acest lucru prin luarea unui modulo 256 care produce numere în intervalul ocupând 8 biți pentru reprezentarea sa. O funcție hash, care mapează cheile către un astfel de domeniu de numere întregi, aplică de cele mai multe ori modulo N astfel încât să restrângă valorile, sau spațiul hash, la un interval .

O bună funcție hash are următoarele proprietăți

• Funcția este eficientă din punct de vedere computațional, iar valorile generate sunt ușor de consultat
• Funcția, pentru majoritatea cazurilor generale de utilizare, se comportă ca un generator pseudo-aleator care distribuie datele în mod egal, fără nicio corelație notabilă

Acum că am văzut ce este o funcție hash, aruncăm o privire asupra modului în care am putea să le folosim și să construim un sistem distribuit oarecum scalabil.

Construirea unui sistem de stocare distribuit

Să spunem că construim un sistem de stocare distribuit în care utilizatorii pot încărca fișiere și le pot accesa la cerere. Serviciul expune următoarele API-uri utilizatorilor

• upload pentru a încărca fișierul
• fetch pentru a prelua fișierul și a returna conținutul acestuia

În spatele scenei, sistemul are Noduri de stocare pe care sunt stocate și accesate fișierele. Aceste noduri expun funcțiile put_file și fetch_file care pun și obțin conținutul fișierului pe/din disc și trimit răspunsul către serverul principal API care, la rândul său, îl trimite înapoi către utilizator.

Pentru a susține sarcina inițială, sistemul are 5 noduri Stogare care stochează fișierele încărcate în mod distribuit. Având mai multe noduri se asigură că sistemul, în ansamblu, nu este copleșit, iar stocarea este distribuită aproape uniform.

Când utilizatorul invocă funcția upload cu calea fișierului, sistemul trebuie mai întâi să identifice nodul de stocare care va fi responsabil pentru păstrarea fișierului și facem acest lucru prin aplicarea unei funcții hash la cale și, la rândul său, prin obținerea indexului nodului de stocare. După ce obținem nodul de stocare, citim conținutul fișierului și punem fișierul respectiv pe nodul respectiv prin invocarea funcției put_file a nodului.

# storage_nodes holding instances of actual storage node objectsstorage_nodes = def hash_fn(key): """The function sums the bytes present in the `key` and then take a mod with 5. This hash function thus generates output in the range . """ return sum(bytearray(key.encode('utf-8'))) % 5def upload(path): # we use the hash function to get the index of the storage node # that would hold the file index = hash_fn(path) # we get the StorageNode instance node = storage_nodes # we put the file on the node and return return node.put_file(path)def fetch(path): # we use the hash function to get the index of the storage node # that would hold the file index = hash_fn(path) # we get the StorageNode instance node = storage_nodes # we fetch the file from the node and return return node.fetch_file(path)

Funcția hash utilizată aici însumează pur și simplu octeții și ia modulul cu 5 (deoarece există 5 noduri de stocare în sistem), generând astfel ieșirea în spațiul hash . Această valoare de ieșire reprezintă acum indexul motorului de stocare care va fi responsabil pentru păstrarea fișierului.

Să spunem că avem 5 fișiere „f1.txt”, „f2.txt”, „f3.txt”, „f4.txt”, „f5.txt’, dacă aplicăm funcția hash la acestea, aflăm că sunt stocate pe nodurile de stocare E, A, B, C, respectiv D.

Lucrurile devin interesante atunci când sistemul câștigă ceva tracțiune și trebuie să fie scalat la 7 noduri, ceea ce înseamnă că acum funcția hash ar trebui să facă mod 7 în loc de un mod 5. Schimbarea funcției hash implică schimbarea cartografierii și asocierii fișierelor cu nodurile de stocare. Mai întâi trebuie să administrăm noile asocieri și să vedem ce fișiere au necesitat să fie mutate de la un nod la altul.

Cu noua funcție hash, aceleași 5 fișiere „f1.txt”, „f2.txt”, „f3.txt”, „f4.txt”, „f5.txt” vor fi acum asociate cu nodurile de stocare D, E, F, G, A. Aici observăm că schimbarea funcției hash ne obligă să mutăm fiecare dintre cele 5 fișiere într-un nod diferit.

Dacă trebuie să schimbăm funcția hash de fiecare dată când mărim sau micșorăm dimensiunea și dacă acest lucru ne obligă să mutăm nu toate datele, ci chiar și jumătate dintre ele, procesul devine foarte costisitor și, pe termen lung, nefezabil. Așadar, avem nevoie de o modalitate de a minimiza mișcarea de date necesară în timpul creșterilor sau descreșterilor de scară, iar aici se potrivește Consistent Hashing, care minimizează transferul de date necesar.

Consistent Hashing

Problema majoră a sistemului de mai sus este că este predispus la evenimente precum creșterile și descreșterile de scară, deoarece necesită o mulțime de modificări în asociații. Aceste asocieri sunt pur și simplu determinate de funcția Hash care stă la baza sistemului și, prin urmare, dacă am putea face cumva această funcție hash independentă de numărul de noduri de stocare din sistem, am rezolva acest defect.

Consistent Hashing rezolvă această situație prin menținerea spațiului Hash uriaș și constant, undeva în jurul valorii de , iar nodul de stocare și obiectele se mapează la unul dintre sloturile din acest spațiu Hash uriaș. Spre deosebire de sistemul tradițional, în care fișierul era asociat cu nodul de stocare la indexul la care a fost hashat, în acest sistem șansele de coliziune între un fișier și un nod de stocare sunt infinitezimale și, prin urmare, avem nevoie de un mod diferit de a defini această asociere.

În loc să folosim o abordare bazată pe coliziune, definim asocierea astfel: – fișierul va fi asociat cu nodul de stocare care este prezent în dreapta imediată a locației sale hashate. Definirea asocierii în acest mod ne ajută

• să menținem funcția hash independentă de numărul de noduri de stocare
• să menținem asociațiile relative și nu determinate de coliziuni absolute

Consistent Hashing necesită în medie doar k/n unități de date care să fie migrate în timpul creșterii și descreșterii scalei; unde k este numărul total de chei și n este numărul de noduri din sistem.

Un mod foarte naiv de a implementa acest lucru este prin alocarea unui array de dimensiune egală cu spațiul de hașurare și plasarea fișierelor și a nodurilor de stocare literalmente în array pe locația hașurată. Pentru a obține asocierea, iterăm de la locația hașurată a elementului spre dreapta și găsim primul nod de stocare. Dacă ajungem la capătul matricei și nu găsim niciun nod de stocare, ne întoarcem la indexul 0 și continuăm căutarea. Abordarea este foarte ușor de implementat, dar suferă de următoarele limitări

• necesită o memorie imensă pentru a păstra o matrice atât de mare
• găsirea asocierii prin iterație de fiecare dată spre dreapta este O(hash_space)

O modalitate mai bună de implementare este folosirea a două matrice: una pentru a păstra nodurile de stocare, numită nodes și alta pentru a păstra pozițiile nodurilor de stocare în spațiul hash, numită keys. Există o corespondență biunivocă între cele două matrici – nodul de stocare nodes este prezent la poziția keys în spațiul hash. Ambele matrici sunt păstrate ordonate conform matricei keys.

Funcția hash în hașurarea consecventă

Definim total_slots ca fiind dimensiunea întregului spațiu hash, de obicei de ordinul 2^256, iar funcția hash poate fi implementată prin luarea SHA-256 urmată de un mod total_slots. Deoarece total_slots este imensă și constantă, următoarea implementare a funcției hash este independentă de numărul real de noduri de stocare prezente în sistem și, prin urmare, nu este afectată de evenimente precum creșterile și descreșterile de scară.

def hash_fn(key: str, total_slots: int) -> int: """hash_fn creates an integer equivalent of a SHA256 hash and takes a modulo with the total number of slots in hash space. """ hsh = hashlib.sha256() # converting data into bytes and passing it to hash function hsh.update(bytes(key.encode('utf-8'))) # converting the HEX digest into equivalent integer value return int(hsh.hexdigest(), 16) % total_slots

Adăugarea unui nou nod în sistem

Când este necesar să se mărească și să se adauge un nou nod în sistem, în cazul nostru un nou nod de stocare, găsim

• găsim poziția nodului în care acesta se află în Hash Space
• populăm noul nod cu datele pe care trebuie să le deservească
• adăugăm nodul în Hash Space

Când se adaugă un nou nod în sistem, acesta afectează doar fișierele care se află în hash la locația din stânga și asociate nodului din dreapta, din poziția în care se va încadra noul nod. Toate celelalte fișiere și asocieri rămân neafectate, reducând astfel la minimum cantitatea de date care trebuie migrate și cartografierea necesară pentru a fi modificată.

Din ilustrația de mai sus, observăm că atunci când se adaugă un nou nod K între nodurile B și E, modificăm asocierile fișierelor prezente în segmentul B-K și le atribuim nodului K. Datele aparținând segmentului B-K ar putea fi găsite în nodul E, la care au fost asociate anterior. Astfel, singurele fișiere afectate și care au nevoie de migrare sunt cele din segmentul B-K; iar asocierea lor se schimbă de la nodul E la nodul K.

Pentru a implementa acest lucru la un nivel scăzut, folosind matricele nodes și keys, mai întâi obținem poziția noului nod în spațiul Hash folosind funcția hash. Apoi, găsim indexul celei mai mici chei mai mari decât poziția în matricea keys sortată, utilizând căutarea binară. Acest indice va fi locul în care cheia și noul nod de stocare vor fi plasate în matricele keys și, respectiv, nodes.

def add_node(self, node: StorageNode) -> int: """add_node function adds a new node in the system and returns the key from the hash space where it was placed """ # handling error when hash space is full. if len(self._keys) == self.total_slots: raise Exception("hash space is full") key = hash_fn(node.host, self.total_slots) # find the index where the key should be inserted in the keys array # this will be the index where the Storage Node will be added in the # nodes array. index = bisect(self._keys, key) # if we have already seen the key i.e. node already is present # for the same key, we raise Collision Exception if index > 0 and self._keys == key: raise Exception("collision occurred") # Perform data migration # insert the node_id and the key at the same `index` location. # this insertion will keep nodes and keys sorted w.r.t keys. self.nodes.insert(index, node) self._keys.insert(index, key) return key

Îndepărtarea unui nou nod din sistem

Când este necesar să se reducă dimensiunea și să se îndepărteze un nod existent din sistem, noi

• găsim poziția nodului care urmează să fie eliminat din Hash Space
• populăm nodul din dreapta cu datele care au fost asociate cu nodul care urmează să fie eliminat
• eliminăm nodul din Hash Space

Când un nod este eliminat din sistem, acesta afectează doar fișierele asociate cu nodul în sine. Toate celelalte fișiere și asocieri rămân neafectate, minimizând astfel cantitatea de date care trebuie migrate și cartografierea necesară pentru a fi schimbată.

Din ilustrația de mai sus, vedem că atunci când nodul K este îndepărtat din sistem, schimbăm asocierile fișierelor asociate cu nodul K în nodul care se află în dreapta sa imediată i.adică nodul E. Astfel, singurele fișiere afectate și care au nevoie de migrare sunt cele asociate nodului K.

Pentru a pune în aplicare acest lucru la un nivel scăzut, folosind matricele nodes și keys, obținem indexul în care se află nodul K în matricea keys folosind căutarea binară. Odată ce avem indexul, eliminăm cheia din matricea keys și nodul de stocare din matricea nodes prezent pe acel index.

def remove_node(self, node: StorageNode) -> int: """remove_node removes the node and returns the key from the hash space on which the node was placed. """ # handling error when space is empty if len(self._keys) == 0: raise Exception("hash space is empty") key = hash_fn(node.host, self.total_slots) # we find the index where the key would reside in the keys index = bisect_left(self._keys, key) # if key does not exist in the array we raise Exception if index >= len(self._keys) or self._keys != key: raise Exception("node does not exist") # Perform data migration # now that all sanity checks are done we popping the # keys and nodes at the index and thus removing the presence of the node. self._keys.pop(index) self.nodes.pop(index) return key

Asocierea unui element la un nod

Acum că am văzut cum hashing-ul consistent ajută la menținerea la minimum a migrării datelor, în timpul creșterilor și descreșterilor de scară; este timpul să vedem cum putem găsi în mod eficient „nodul din dreapta” pentru un anumit element. Operația de găsire a asocierii trebuie să fie super rapidă și eficientă, deoarece este ceva ce va fi invocat pentru fiecare citire și scriere care are loc în sistem.

Pentru a implementa acest lucru la nivel scăzut, ne folosim din nou de căutarea binară și efectuăm această operație în O(log(n)). Mai întâi transmitem elementul către funcția hash și recuperăm poziția în care elementul este hașurat în spațiul hash. Această poziție este apoi căutată binar în matricea keys pentru a obține indexul primei chei care este mai mare decât poziția (obținută de la funcția hash). Dacă nu există chei mai mari decât poziția, în matricea keys, ne întoarcem și returnăm indexul 0. Indicele astfel obținut va fi indicele nodului de stocare din array-ul nodes asociat elementului.

def assign(self, item: str) -> str: """Given an item, the function returns the node it is associated with. """ key = hash_fn(item, self.total_slots) # we find the first node to the right of this key # if bisect_right returns index which is out of bounds then # we circle back to the first in the array in a circular fashion. index = bisect_right(self._keys, key) % len(self._keys) # return the node present at the index return self.nodes

Codul sursă cu implementarea lui Consistent Hashing în Python poate fi găsit la github.com/arpitbbhayani/consistent-hashing.

Concluzie

Consistent Hashing este unul dintre cei mai importanți algoritmi care ne ajută să creștem și să gestionăm orizontal orice sistem distribuit. Algoritmul nu funcționează doar în sistemele sharded, ci își găsește aplicații și în echilibrarea încărcăturii, partiționarea datelor, gestionarea sesiunilor lipicioase bazate pe server, algoritmi de rutare și multe altele. O mulțime de baze de date își datorează scara, performanța și capacitatea de a face față încărcăturii colosale lui Consistent Hashing.

• Hash Functions – Wikipedia
• Consistent Hashing – Wikipedia
• Consistent Hashing – Stanford
• Consistent Hashing and RandomTrees

Dynamo: Amazon’s Highly Available Key-value Store

Alte articole care v-ar putea interesa:

• Python Caches Integers
• Fractional Cascading – Speeding up Binary Searches
• Copy-on-Write Semantics
• Ce face ca MySQL LRU să fie rezistent la scanarea cache-ului LRU
• Building Finite State Machines with Python Coroutines

Acest articol a fost publicat inițial pe blogul meu – Consistent Hashing.

Dacă v-a plăcut ceea ce ați citit, abonați-vă la newsletter-ul meu și primiți postarea direct în căsuța dvs. de e-mail și dați-mi un strigăt @arpit_bhayani.

.