Negli ultimi anni, con l’avvento di concetti come cloud computing e big data, i sistemi distribuiti hanno guadagnato popolarità e rilevanza.
Un tale tipo di sistema, le cache distribuite che alimentano molti siti web dinamici ad alto traffico e applicazioni web, consistono tipicamente in un caso particolare di hashing distribuito. Questi sfruttano un algoritmo noto come hashing coerente.
Che cos’è l’hashing coerente? Qual è la motivazione dietro, e perché dovrebbe interessarti?
In questo articolo, per prima cosa passerò in rassegna il concetto generale di hashing e il suo scopo, seguito da una descrizione dell’hashing distribuito e dei problemi che comporta. A sua volta, questo ci porterà all’argomento del titolo.
Che cos’è l’hashing?
Che cos’è l'”hashing”? Il Merriam-Webster definisce il sostantivo hash come “carne tritata mescolata con patate e rosolata”, e il verbo come “tagliare (come carne e patate) in piccoli pezzi”. Quindi, dettagli culinari a parte, hash significa approssimativamente “tagliare e mescolare” – ed è proprio da qui che deriva il termine tecnico.
Una funzione hash è una funzione che mappa un pezzo di dati – tipicamente descrivendo qualche tipo di oggetto, spesso di dimensioni arbitrarie – ad un altro pezzo di dati, tipicamente un intero, noto come codice hash, o semplicemente hash.
Per esempio, una funzione di hash progettata per l’hash delle stringhe, con un intervallo di uscita di 0 .. 100, può mappare la stringa Hello su, diciamo, il numero 57, Hasta la vista, baby sul numero 33, e qualsiasi altra possibile stringa su qualche numero entro quell’intervallo. Poiché ci sono molti più input possibili che output, ogni dato numero avrà molte stringhe diverse mappate su di esso, un fenomeno noto come collisione. Una buona funzione hash dovrebbe in qualche modo “tagliare e mescolare” (da qui il termine) i dati di input in modo tale che gli output per diversi valori di input siano distribuiti il più uniformemente possibile nell’intervallo di output.
Le funzioni hash hanno molti usi e per ognuno di essi si possono desiderare diverse proprietà. C’è un tipo di funzione hash conosciuta come funzioni hash crittografiche, che devono soddisfare un insieme restrittivo di proprietà e sono utilizzate per scopi di sicurezza, comprese applicazioni come la protezione delle password, il controllo dell’integrità e l’impronta digitale dei messaggi, e il rilevamento della corruzione dei dati, tra gli altri, ma questi sono fuori dallo scopo di questo articolo.
Anche le funzioni hash non crittografiche hanno diversi usi, il più comune è il loro uso nelle tabelle hash, che è quello che ci interessa e che esploreremo più in dettaglio.
Introduzione alle tabelle hash (mappe hash)
Immaginiamo di dover tenere una lista di tutti i membri di un club e di poter cercare qualsiasi membro specifico. Potremmo gestire la cosa mantenendo la lista in un array (o lista collegata) e, per eseguire una ricerca, iterare gli elementi fino a trovare quello desiderato (potremmo cercare in base al loro nome, per esempio). Nel peggiore dei casi, questo significherebbe controllare tutti i membri (se quello che stiamo cercando è ultimo, o non è affatto presente), o la metà di essi in media. In termini di teoria della complessità, la ricerca avrebbe quindi una complessità O(n), e sarebbe ragionevolmente veloce per una piccola lista, ma diventerebbe sempre più lenta in proporzione diretta al numero di membri.
Come si potrebbe migliorare? Supponiamo che tutti questi membri del club abbiano un membro ID, che è un numero sequenziale che riflette l’ordine in cui sono entrati nel club.
Assumendo che la ricerca per ID sia accettabile, potremmo mettere tutti i membri in un array, con i loro indici corrispondenti ai loro ID (per esempio, un membro con ID=10 sarebbe all’indice 10 nell’array). Questo ci permetterebbe di accedere ad ogni membro direttamente, senza alcuna ricerca. Questo sarebbe molto efficiente, in effetti, il più efficiente possibile, corrispondente alla più bassa complessità possibile, O(1), conosciuta anche come tempo costante.
Ma, ammettiamo che il nostro scenario del membro del club ID è un po’ artificioso. E se i ID fossero numeri grandi, non sequenziali o casuali? Oppure, se la ricerca per ID non fosse accettabile, e avessimo invece bisogno di cercare per nome (o qualche altro campo)? Sarebbe certamente utile mantenere il nostro accesso diretto veloce (o qualcosa di simile) e allo stesso tempo essere in grado di gestire insiemi di dati arbitrari e criteri di ricerca meno restrittivi.
Ecco dove le funzioni hash vengono in soccorso. Una funzione hash adatta può essere usata per mappare un pezzo arbitrario di dati in un intero, che giocherà un ruolo simile a quello del nostro membro del club ID, sebbene con alcune importanti differenze.
In primo luogo, una buona funzione hash ha generalmente un ampio intervallo di uscita (tipicamente, l’intero intervallo di un intero a 32 o 64 bit), quindi costruire un array per tutti i possibili indici sarebbe o poco pratico o semplicemente impossibile, e un colossale spreco di memoria. Per ovviare a ciò, possiamo avere un array di dimensioni ragionevoli (diciamo solo il doppio del numero di elementi che ci aspettiamo di memorizzare) ed eseguire un’operazione modulo sull’hash per ottenere l’indice dell’array. Quindi, l’indice sarebbe index = hash(object) mod N, dove N è la dimensione dell’array.
In secondo luogo, gli hash degli oggetti non saranno unici (a meno che non stiamo lavorando con un set di dati fisso e una funzione hash perfetta costruita su misura, ma non ne parleremo qui). Ci saranno collisioni (ulteriormente aumentate dall’operazione modulo), e quindi un semplice accesso diretto all’indice non funzionerà. Ci sono diversi modi per gestire questo, ma uno tipico è quello di allegare una lista, comunemente nota come bucket, ad ogni indice dell’array per contenere tutti gli oggetti che condividono un dato indice.
Quindi, abbiamo un array di dimensione N, con ogni voce che punta ad un bucket di oggetti. Per aggiungere un nuovo oggetto, dobbiamo calcolare il suo hash modulo N, e controllare il secchio all’indice risultante, aggiungendo l’oggetto se non è già presente. Per cercare un oggetto, facciamo la stessa cosa, solo guardando nel secchio per controllare se l’oggetto è lì. Una tale struttura è chiamata tabella hash, e sebbene le ricerche all’interno dei bucket siano lineari, una tabella hash correttamente dimensionata dovrebbe avere un numero ragionevolmente piccolo di oggetti per bucket, con conseguente accesso in tempo quasi costante (una complessità media di O(N/k), dove k è il numero di bucket).
Con oggetti complessi, la funzione hash non è tipicamente applicata all’intero oggetto, ma ad una chiave. Nel nostro esempio di membro del club, ogni oggetto potrebbe contenere diversi campi (come nome, età, indirizzo, email, telefono), ma potremmo scegliere, ad esempio, l’email come chiave in modo che la funzione hash sia applicata solo all’email. In effetti, la chiave non deve necessariamente essere parte dell’oggetto; è comune memorizzare coppie chiave/valore, dove la chiave è di solito una stringa relativamente breve e il valore può essere un pezzo arbitrario di dati. In questi casi, la tabella hash o la mappa hash è usata come un dizionario, e questo è il modo in cui alcuni linguaggi di alto livello implementano gli oggetti o gli array associativi.
Scaling Out: Hashing distribuito
Ora che abbiamo discusso l’hashing, siamo pronti ad esaminare l’hashing distribuito.
In alcune situazioni, può essere necessario o desiderabile dividere una tabella hash in più parti, ospitate da server diversi. Una delle principali motivazioni è quella di aggirare le limitazioni di memoria dell’uso di un singolo computer, permettendo la costruzione di tabelle hash arbitrariamente grandi (dato un numero sufficiente di server).
In un tale scenario, gli oggetti (e le loro chiavi) sono distribuiti tra diversi server, da cui il nome.
Un tipico caso d’uso per questo è l’implementazione di cache in-memoria, come Memcached.
Queste configurazioni consistono in un pool di server di caching che ospitano molte coppie chiave/valore e sono utilizzate per fornire un accesso veloce ai dati originariamente memorizzati (o calcolati) altrove. Per esempio, per ridurre il carico su un server di database e allo stesso tempo migliorare le prestazioni, un’applicazione può essere progettata per recuperare prima i dati dai server di cache, e solo se non è presente lì – una situazione nota come cache miss-resort al database, eseguendo la query pertinente e mettendo in cache i risultati con una chiave appropriata, in modo che possa essere trovato la prossima volta che è necessario.
Ora, come avviene la distribuzione? Quali criteri sono usati per determinare quali chiavi ospitare in quali server?
Il modo più semplice è prendere l’hash modulo del numero di server. Cioè server = hash(key) mod N, dove N è la dimensione del pool. Per memorizzare o recuperare una chiave, il client calcola prima l’hash, applica un’operazione modulo N e usa l’indice risultante per contattare il server appropriato (probabilmente usando una tabella di ricerca di indirizzi IP). Si noti che la funzione hash usata per la distribuzione delle chiavi deve essere la stessa per tutti i client, ma non è necessario che sia la stessa usata internamente dai server di caching.
Vediamo un esempio. Diciamo che abbiamo tre server, A, B e C, e abbiamo alcune chiavi stringa con i loro hash:
| KEY | HASH | HASH mod 3 |
|---|---|---|
| “john” | 1633428562 | 2 |
| “bill” | 7594634739 | 0 |
| “jane” | 5000799124 | 1 |
| “steve” | 9787173343 | 0 |
| “kate” | 3421657995 | 2 |
Un cliente vuole recuperare il valore della chiave john. Il suo hash modulo 3 è 2, quindi deve contattare il server C. La chiave non si trova lì, quindi il client recupera i dati dalla fonte e li aggiunge. Il pool si presenta così:
| A | B | C |
|---|---|---|
| “john” |
In seguito un altro cliente (o lo stesso) vuole recuperare il valore della chiave bill. Il suo hash modulo 3 è 0, quindi deve contattare il server A. La chiave non si trova lì, quindi il client recupera i dati dalla fonte e li aggiunge. Il pool appare così ora:
| A | B | C |
|---|---|---|
| “bill” | “john” |
Dopo aver aggiunto le chiavi rimanenti, il pool appare così:
| A | B | C |
|---|---|---|
| “bill” | “jane” | “john” |
| “steve” | “kate” |
Il problema del Rehashing
Questo schema di distribuzione è semplice, intuitivo e funziona bene. Questo fino a quando il numero di server non cambia. Cosa succede se uno dei server si blocca o diventa non disponibile? Le chiavi devono essere ridistribuite per tenere conto del server mancante, ovviamente. Lo stesso vale se uno o più nuovi server vengono aggiunti al pool; le chiavi devono essere ridistribuite per includere i nuovi server. Questo è vero per qualsiasi schema di distribuzione, ma il problema con la nostra semplice distribuzione modulo è che quando il numero di server cambia, la maggior parte dei hashes modulo N cambierà, quindi la maggior parte delle chiavi dovrà essere spostata su un server diverso. Quindi, anche se un singolo server viene rimosso o aggiunto, tutte le chiavi avranno probabilmente bisogno di essere spostate in un server diverso.
Dal nostro esempio precedente, se rimuoviamo il server C, dovremmo riformulare tutte le chiavi usando hash modulo 2 invece di hash modulo 3, e le nuove posizioni delle chiavi diventerebbero:
| KEY | HASH | HASH mod 2 |
|---|---|---|
| “john” | 1633428562 | 0 |
| “bill” | ||
| “jane” | “steve” | |
| “kate” |
Nota che tutte le posizioni chiave sono cambiate, non solo quelle del server C.
Nel tipico caso d’uso che abbiamo menzionato prima (caching), questo significherebbe che, all’improvviso, le chiavi non saranno trovate perché non saranno ancora presenti nella loro nuova posizione.
Quindi, la maggior parte delle query risulterà in miss, e i dati originali dovranno probabilmente essere recuperati di nuovo dalla fonte per essere riformulati, ponendo così un pesante carico sul server o sui server di origine (tipicamente un database). Questo potrebbe degradare gravemente le prestazioni ed eventualmente mandare in crash i server di origine.
La soluzione: Consistent Hashing
Come può essere risolto questo problema? Abbiamo bisogno di uno schema di distribuzione che non dipenda direttamente dal numero di server, in modo che, quando si aggiungono o rimuovono server, il numero di chiavi che devono essere ricollocate sia ridotto al minimo. Uno di questi schemi – intelligente, ma sorprendentemente semplice – è chiamato hashing coerente, ed è stato descritto per la prima volta da Karger et al. al MIT in un documento accademico del 1997 (secondo Wikipedia).
Consistent Hashing è uno schema di hashing distribuito che opera indipendentemente dal numero di server o oggetti in una tabella hash distribuita assegnando loro una posizione su un cerchio astratto, o hash ring. Questo permette ai server e agli oggetti di scalare senza influenzare l’intero sistema.
Immaginate di mappare l’intervallo di uscita dell’hash sul bordo di un cerchio. Ciò significa che il minimo valore di hash possibile, zero, corrisponderebbe ad un angolo di zero, il massimo valore possibile (un grande intero che chiameremo INT_MAX) corrisponderebbe ad un angolo di 2𝝅 radianti (o 360 gradi), e tutti gli altri valori di hash si adatterebbero linearmente da qualche parte nel mezzo. Quindi, potremmo prendere una chiave, calcolare il suo hash, e scoprire dove si trova sul bordo del cerchio. Assumendo un INT_MAX di 1010 (per esempio), le chiavi del nostro esempio precedente apparirebbero così:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| “john” | 1633428562 | 58.8 |
| “bill” | 7594634739 | 273.4 |
| “jane” | 5000799124 | 180 |
| “steve” | 9787173343 | 352.3 |
| “kate” | 3421657995 | 123.2 |
Ora immaginiamo di posizionare anche i server sul bordo del cerchio, assegnando loro angoli in modo pseudocasuale. Questo dovrebbe essere fatto in modo ripetibile (o almeno in modo tale che tutti i client siano d’accordo sugli angoli dei server). Un modo conveniente per farlo è l’hashing del nome del server (o dell’indirizzo IP, o di qualche ID) – come faremmo con qualsiasi altra chiave – per ottenere il suo angolo.
Nel nostro esempio, le cose potrebbero apparire così:
| 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 |
Siccome abbiamo le chiavi degli oggetti e dei server sullo stesso cerchio, possiamo definire una semplice regola per associare i primi ai secondi: Ogni chiave di oggetto apparterrà al server la cui chiave è più vicina, in senso antiorario (o orario, a seconda delle convenzioni utilizzate). In altre parole, per scoprire a quale server chiedere una data chiave, dobbiamo localizzare la chiave sul cerchio e muoverci nella direzione dell’angolo ascendente fino a trovare un server.
Nel nostro esempio:
| 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 |
Dal punto di vista della programmazione, quello che dovremmo fare è mantenere una lista ordinata di valori di server (che potrebbero essere angoli o numeri in qualsiasi intervallo reale), e percorrere questa lista (o usare una ricerca binaria) per trovare il primo server con un valore maggiore o uguale a quello della chiave desiderata. Se non viene trovato nessun valore, dobbiamo fare un giro, prendendo il primo dalla lista.
Per assicurarci che le chiavi dell’oggetto siano distribuite uniformemente tra i server, dobbiamo applicare un semplice trucco: assegnare non una, ma molte etichette (angoli) a ciascun server. Così, invece di avere le etichette A, B e C, potremmo avere, diciamo, A0 .. A9, B0 .. B9 e C0 .. C9, tutte intervallate lungo il cerchio. Il fattore di cui aumentare il numero di etichette (chiavi del server), noto come peso, dipende dalla situazione (e può anche essere diverso per ogni server) per regolare la probabilità che le chiavi finiscano su ciascuno. Per esempio, se il server B fosse due volte più potente degli altri, gli si potrebbe assegnare il doppio delle etichette e, di conseguenza, finirebbe per avere il doppio degli oggetti (in media).
Per il nostro esempio assumeremo che tutti e tre i server abbiano un peso uguale a 10 (questo funziona bene per tre server, per 10-50 server, un peso nell’intervallo 100-500 funzionerebbe meglio, e pool più grandi potrebbero aver bisogno di pesi ancora più alti):
| 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” | 4755525684 | 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.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 |
Quindi, qual è il vantaggio di tutto questo approccio circolare? Immaginate che il server C venga rimosso. Per tenerne conto, dobbiamo rimuovere le etichette C0 .. C9 dal cerchio. Questo fa sì che le chiavi oggetto prima adiacenti alle etichette eliminate siano ora etichettate casualmente Ax e Bx, riassegnandole ai server A e B.
Ma cosa succede con le altre chiavi oggetto, quelle che originariamente appartenevano a A e B? Niente! Questo è il bello: L’assenza delle etichette Cx non influisce in alcun modo su quelle chiavi. Quindi, rimuovendo un server, le sue chiavi oggetto vengono riassegnate casualmente al resto dei server, lasciando tutte le altre chiavi intatte:
| 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” | 4755525684 | 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 |
Succede qualcosa di simile se, invece di rimuovere un server, ne aggiungiamo uno. Se volessimo aggiungere il server D al nostro esempio (diciamo, come sostituzione di C), dovremmo aggiungere le etichette D0 .. D9. Il risultato sarebbe che circa un terzo delle chiavi esistenti (tutte appartenenti a A o B) verrebbero riassegnate a D, e, di nuovo, il resto rimarrebbe uguale:
| KEY | HASH | ANGOLO (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” | 4755525684 | 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 |
Ecco come il consistent hashing risolve il problema del rehashing.
In generale, solo k/Nchiavi devono essere rimappate quando k è il numero di chiavi e N è il numero di server (più specificamente, il massimo del numero iniziale e finale di server).
Abbiamo osservato che quando si usa il caching distribuito per ottimizzare le prestazioni, può succedere che il numero di server di caching cambi (le ragioni di questo possono essere un crash del server, o la necessità di aggiungere o rimuovere un server per aumentare o diminuire la capacità complessiva). Usando l’hashing coerente per distribuire le chiavi tra i server, possiamo essere sicuri che, se ciò dovesse accadere, il numero di chiavi che vengono riascoltate – e quindi l’impatto sui server di origine – sarà ridotto al minimo, prevenendo potenziali tempi morti o problemi di prestazioni.
Ci sono client per diversi sistemi, come Memcached e Redis, che includono il supporto per l’hashing coerente fuori dalla scatola.
In alternativa, potete implementare voi stessi l’algoritmo, nel vostro linguaggio preferito, e questo dovrebbe essere relativamente facile una volta che il concetto è stato compreso.
Se la scienza dei dati vi interessa, Toptal ha alcuni dei migliori articoli sull’argomento sul blog
.