Consistent hashing è una tecnica di hashing che funziona molto bene quando si opera in un ambiente dinamico in cui il sistema distribuito aumenta e diminuisce frequentemente. Il concetto di base del Consistent Hashing è stato introdotto nell’articolo Consistent Hashing and RandomTrees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web ma ha guadagnato popolarità dopo il famoso articolo che introduce DynamoDB – Dynamo: Amazon’s Highly Available Key-value Store. Da allora l’hashing coerente ha guadagnato trazione e ha trovato una tonnellata di casi d’uso nel progettare e scalare sistemi distribuiti in modo efficiente. I due esempi famosi che usano esaustivamente questa tecnica sono Bit Torrent, per le loro reti peer-to-peer e Akamai, per le loro cache web. In questo articolo ci immergiamo in profondità nella necessità del Consistent Hashing, i suoi elementi interni e, cosa più importante, la implementiamo usando array e Binary Search.

Prima di addentrarci nella tecnica del Consistent Hashing, dobbiamo prima chiarire alcune cose, una delle quali sono le Hash Functions. Le funzioni Hash sono tutte le funzioni che mappano il valore da un dominio di dimensioni arbitrarie ad un altro dominio di dimensioni fisse, solitamente chiamato spazio Hash. Per esempio, mappando gli URL a 32-bit interi o il contenuto HTML delle pagine web a una stringa di 256 byte. I valori generati come output di queste funzioni hash sono tipicamente usati come chiavi per permettere ricerche efficienti dell’entità originale.

Un esempio di una semplice funzione hash è una funzione che mappa un intero a 32 bit in uno spazio hash a 8 bit. La funzione potrebbe essere implementata usando l’operatore aritmetico modulo e possiamo ottenere questo prendendo un modulo 256 che produce numeri nell’intervallo occupando 8-bit per la sua rappresentazione. Una funzione hash, che mappa le chiavi a tale dominio intero, il più delle volte applica il modulo N in modo da restringere i valori, o lo spazio hash, a un intervallo .

Una buona funzione hash ha le seguenti proprietà

• La funzione è computazionalmente efficiente e i valori generati sono facili da cercare
• La funzione, per la maggior parte dei casi d’uso generali, si comporta come un generatore pseudorandom che sparge i dati in modo uniforme senza alcuna correlazione evidente

Ora che abbiamo visto cos’è una funzione hash, diamo uno sguardo a come potremmo usarla e costruire un sistema distribuito in qualche modo scalabile.

Costruire un sistema di archiviazione distribuito

Si supponga che stiamo costruendo un sistema di archiviazione distribuito in cui gli utenti possono caricare file e accedervi su richiesta. Il servizio espone le seguenti API agli utenti

• upload per caricare il file
• fetch per recuperare il file e restituire il suo contenuto

Dietro le quinte il sistema ha nodi di archiviazione su cui i file sono memorizzati e a cui si accede. Questi nodi espongono le funzioni put_file e fetch_file che mettono e ricevono il contenuto del file da/al disco e inviano la risposta al server API principale che a sua volta la rimanda all’utente.

Per sostenere il carico iniziale, il sistema ha 5 nodi Stogare che memorizzano i file caricati in modo distribuito. Avere più nodi assicura che il sistema, nel suo complesso, non sia sopraffatto, e che lo stoccaggio sia distribuito in modo quasi uniforme.

Quando l’utente invoca la funzione upload con il percorso del file, il sistema deve prima identificare il nodo di stoccaggio che sarà responsabile della conservazione del file e lo facciamo applicando una funzione hash al percorso e ottenendo a sua volta l’indice del nodo di stoccaggio. Una volta ottenuto il nodo di archiviazione, leggiamo il contenuto del file e mettiamo quel file sul nodo invocando la funzione put_file del nodo.

# 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)

La funzione hash usata qui somma semplicemente i byte e prende il modulo per 5 (dato che ci sono 5 nodi di archiviazione nel sistema) e quindi genera l’output nello spazio hash . Questo valore di output rappresenta ora l’indice del motore di archiviazione che sarà responsabile della conservazione del file.

Sumiamo di avere 5 file ‘f1.txt’, ‘f2.txt’, ‘f3.txt’, ‘f4.txt’, ‘f5.txt’ se applichiamo la funzione hash a questi troviamo che sono memorizzati sui nodi di archiviazione E, A, B, C, e D rispettivamente.

Le cose diventano interessanti quando il sistema guadagna un po’ di trazione e deve essere scalato a 7 nodi, il che significa che ora la funzione hash dovrebbe fare mod 7 invece di un mod 5. Cambiare la funzione di hash implica cambiare la mappatura e l’associazione dei file con i nodi di stoccaggio. Dobbiamo prima amministrare le nuove associazioni e vedere quali file devono essere spostati da un nodo all’altro.

Con la nuova funzione hash gli stessi 5 file ‘f1.txt’, ‘f2.txt’, ‘f3.txt’, ‘f4.txt’, ‘f5.txt’ saranno ora associati ai nodi di stoccaggio D, E, F, G, A. Qui vediamo che cambiare la funzione di hash richiede di spostare ognuno dei 5 file su un nodo diverso.

Se dobbiamo cambiare la funzione di hash ogni volta che scaliamo verso l’alto o verso il basso e se questo ci richiede di spostare non tutti ma anche solo metà dei dati, il processo diventa super costoso e a lungo termine non fattibile. Quindi abbiamo bisogno di un modo per minimizzare il movimento di dati richiesto durante gli scale-up o scale-down, e questo è dove il Consistent Hashing si inserisce e minimizza il trasferimento di dati richiesto.

Consistent Hashing

Il principale punto dolente del sistema di cui sopra è che è soggetto a eventi come scale-up e scale-down poiché richiede molte alterazioni nelle associazioni. Queste associazioni sono puramente guidate dalla sottostante funzione di hash e quindi se potessimo in qualche modo rendere questa funzione di hash indipendente dal numero dei nodi di archiviazione nel sistema, affronteremmo questo difetto.

Consistent Hashing affronta questa situazione mantenendo l’Hash Space enorme e costante, da qualche parte nell’ordine di e il nodo di archiviazione e gli oggetti mappano entrambi su uno degli slot di questo enorme Hash Space. A differenza del sistema tradizionale in cui il file era associato al nodo di archiviazione all’indice in cui era stato hashato, in questo sistema le possibilità di una collisione tra un file e un nodo di archiviazione sono infinitesimamente piccole e quindi abbiamo bisogno di un modo diverso per definire questa associazione.

Invece di usare un approccio basato sulla collisione definiamo l’associazione come – il file sarà associato al nodo di archiviazione che è presente alla destra immediata della sua posizione hash. Definire l’associazione in questo modo ci aiuta

• a mantenere la funzione hash indipendente dal numero di nodi di memorizzazione
• a mantenere le associazioni relative e non guidate da collisioni assolute

Consistent Hashing in media richiede solo k/n unità di dati da migrare durante lo scale up e down; dove k è il numero totale di chiavi e n è il numero di nodi nel sistema.

Un modo molto ingenuo per implementare questo è allocare un array di dimensioni pari allo spazio di hash e mettere i file e il nodo di archiviazione letteralmente nell’array sulla posizione di hash. Per ottenere l’associazione iteriamo dalla posizione hashed dell’elemento verso destra e troviamo il primo Storage Node. Se raggiungiamo la fine dell’array e non troviamo nessuno Storage Node torniamo indietro all’indice 0 e continuiamo la ricerca. L’approccio è molto facile da implementare ma soffre delle seguenti limitazioni

• richiede un’enorme memoria per contenere un array così grande
• trovare l’associazione iterando ogni volta verso destra è O(hash_space)

Un modo migliore per implementare questo è usare due array: uno per contenere gli Storage Nodes, chiamato nodes e un altro per contenere le posizioni degli Storage Nodes nello spazio hash, chiamato keys. C’è una corrispondenza uno-a-uno tra i due array – lo Storage Node nodes è presente nella posizione keys nello spazio hash. Entrambi gli array sono tenuti ordinati secondo l’array keys.

Funzione di hash in Consistent Hashing

Definiamo total_slots come la dimensione di questo intero spazio hash, tipicamente dell’ordine 2^256 e la funzione hash potrebbe essere implementata prendendo SHA-256 seguito da un mod total_slots. Poiché il total_slots è enorme e costante, la seguente implementazione della funzione di hash è indipendente dal numero effettivo di nodi di archiviazione presenti nel sistema e quindi non è influenzata da eventi come scale-up e scale-down.

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

Aggiungere un nuovo nodo nel sistema

Quando c’è bisogno di scalare e aggiungere un nuovo nodo nel sistema, nel nostro caso un nuovo Storage Node, noi

• troviamo la posizione del nodo dove risiede nell’Hash Space
• popoliamo il nuovo nodo con i dati che deve servire
• aggiungiamo il nodo nell’Hash Space

Quando un nuovo nodo viene aggiunto nel sistema, questo influisce solo sui file che hanno un hash nella posizione a sinistra e associati al nodo a destra, della posizione in cui il nuovo nodo si troverà. Tutti gli altri file e associazioni rimangono inalterati, minimizzando così la quantità di dati da migrare e la mappatura da cambiare.

Dall’illustrazione sopra, vediamo che quando un nuovo nodo K viene aggiunto tra i nodi B ed E, cambiamo le associazioni dei file presenti nel segmento B-K e li assegniamo al nodo K. I dati appartenenti al segmento B-K potrebbero essere trovati al nodo E al quale erano precedentemente associati. Quindi gli unici file interessati e che necessitano di migrazione sono nel segmento B-K; e la loro associazione cambia dal nodo E al nodo K.

Per implementare questo a basso livello usando gli array nodes e keys, prima otteniamo la posizione del nuovo nodo nello spazio Hash usando la funzione hash. Poi troviamo l’indice della chiave più piccola maggiore della posizione nell’array keys ordinato usando la ricerca binaria. Questo indice sarà dove la chiave e il nuovo nodo Storage saranno posizionati rispettivamente nell’array keys e 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

Rimozione di un nuovo nodo dal sistema

Quando è necessario ridimensionare e rimuovere un nodo esistente dal sistema, noi

• troviamo la posizione del nodo da rimuovere dall’Hash Space
• popoliamo il nodo a destra con i dati che erano associati con il nodo da rimuovere
• rimuoviamo il nodo dall’Hash Space

Quando un nodo viene rimosso dal sistema, ciò influisce solo sui file associati al nodo stesso. Tutti gli altri file e associazioni rimangono inalterati, minimizzando così la quantità di dati da migrare e la mappatura da cambiare.

Dall’illustrazione sopra, vediamo che quando il nodo K viene rimosso dal sistema, cambiamo le associazioni dei file associati al nodo K al nodo che si trova alla sua immediata destra, cioè al nodo E. Così, quando il nodo K viene rimosso dal sistema, cambiamo le associazioni dei file associati al nodo E.Quindi gli unici file interessati e che necessitano di migrazione sono quelli associati al nodo K.

Per implementare questo a basso livello usando nodes e l’array keys, otteniamo l’indice dove si trova il nodo K nell’array keys usando la ricerca binaria. Una volta ottenuto l’indice, rimuoviamo la chiave dall’array keys e il nodo di stoccaggio dall’array nodes presente su quell’indice.

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

Associare un elemento a un nodo

Ora che abbiamo visto come l’hashing coerente aiuta a mantenere la migrazione dei dati, durante gli scale-up e scale-down, al minimo; è il momento di vedere come trovare in modo efficiente il “nodo a destra” per un dato elemento. L’operazione per trovare l’associazione deve essere super veloce ed efficiente in quanto è qualcosa che verrà invocata per ogni singola lettura e scrittura che avviene sul sistema.

Per implementare questo a basso livello, sfruttiamo ancora una volta la ricerca binaria ed eseguiamo questa operazione in O(log(n)). Prima passiamo l’elemento alla funzione hash e recuperiamo la posizione in cui l’elemento è hashato nello spazio hash. Questa posizione viene poi cercata in modo binario nell’array keys per ottenere l’indice della prima chiave che è maggiore della posizione (ottenuta dalla funzione hash). Se non ci sono chiavi maggiori della posizione, nell’array keys, torniamo indietro e restituiamo l’indice 0. L’indice così ottenuto sarà l’indice del nodo di memorizzazione nell’array nodes associato all’elemento.

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

Il codice sorgente con l’implementazione del Consistent Hashing in Python può essere trovato su github.com/arpitbbhayani/consistent-hashing.

Conclusione

Consistent Hashing è uno degli algoritmi più importanti per aiutarci a scalare e gestire orizzontalmente qualsiasi sistema distribuito. L’algoritmo non funziona solo nei sistemi sharded ma trova anche la sua applicazione nel bilanciamento del carico, nel partizionamento dei dati, nella gestione delle sessioni appiccicose basate su server, negli algoritmi di routing e in molti altri. Molti database devono la loro scala, le prestazioni e la capacità di gestire l’enorme carico al Consistent Hashing.

• Funzioni Hash – Wikipedia
• Consistent Hashing – Wikipedia
• Consistent Hashing – Stanford
• Consistent Hashing and RandomTrees
• Dynamo: Amazon’s Highly Available Key-value Store

Altri articoli che potrebbero interessarti:

• Python cache interi
• Fractional Cascading – accelerare le ricerche binarie
• Copy-on-Write Semantics
• Cosa rende MySQL LRU cache scan resistente
• Costruire macchine a stati finiti con Python Coroutines

Questo articolo è stato pubblicato sul mio blog – Consistent Hashing.

Se ti è piaciuto quello che hai letto, iscriviti alla mia newsletter e ricevi il post direttamente nella tua casella di posta e fammi un saluto @arpit_bhayani.