In den letzten Jahren, mit dem Aufkommen von Konzepten wie Cloud Computing und Big Data, haben verteilte Systeme an Popularität und Bedeutung gewonnen.
Eine solche Art von System, verteilte Caches, die viele dynamische Websites und Webanwendungen mit hohem Datenverkehr betreiben, bestehen typischerweise aus einem besonderen Fall von verteiltem Hashing. Sie nutzen einen Algorithmus, der als konsistentes Hashing bekannt ist.
Was ist konsistentes Hashing? Was ist die Motivation dahinter, und warum sollten Sie sich dafür interessieren?
In diesem Artikel werde ich zunächst das allgemeine Konzept des Hashings und seinen Zweck erläutern, gefolgt von einer Beschreibung des verteilten Hashings und der damit verbundenen Probleme. Das wiederum führt uns zu unserem Titelthema.
Was ist Hashing?
Was hat es mit „Hashing“ auf sich? Merriam-Webster definiert das Substantiv Hash als „gehacktes Fleisch, das mit Kartoffeln vermischt und angebraten wird“, und das Verb als „(Fleisch und Kartoffeln) in kleine Stücke schneiden“. Abgesehen von den kulinarischen Details bedeutet Hash also in etwa „hacken und mischen“ – und genau daher stammt der Fachbegriff.
Eine Hash-Funktion ist eine Funktion, die ein Datenelement – das typischerweise eine Art von Objekt, oft von beliebiger Größe, beschreibt – auf ein anderes Datenelement, typischerweise eine ganze Zahl, abbildet, bekannt als Hash-Code oder einfach Hash.
Eine Hash-Funktion, die für das Hashing von Zeichenketten entwickelt wurde und einen Ausgabebereich von 0 .. 100 hat, kann beispielsweise die Zeichenkette Hello auf die Zahl 57, Hasta la vista, baby auf die Zahl 33 und jede andere mögliche Zeichenkette auf eine Zahl innerhalb dieses Bereichs abbilden. Da es viel mehr mögliche Eingaben als Ausgaben gibt, werden einer bestimmten Zahl viele verschiedene Zeichenketten zugeordnet, ein Phänomen, das als Kollision bekannt ist. Gute Hash-Funktionen sollten die Eingabedaten irgendwie „zerhacken und mischen“ (daher der Begriff), so dass die Ausgaben für verschiedene Eingabewerte so gleichmäßig wie möglich über den Ausgabebereich verteilt sind.
Hash-Funktionen haben viele Verwendungszwecke, und für jeden können unterschiedliche Eigenschaften gewünscht sein. Es gibt eine Art von Hash-Funktionen, die als kryptografische Hash-Funktionen bekannt sind, die einen restriktiven Satz von Eigenschaften erfüllen müssen und für Sicherheitszwecke verwendet werden – einschließlich Anwendungen wie Passwortschutz, Integritätsprüfung und Fingerprinting von Nachrichten und Erkennung von Datenverfälschungen, unter anderem, aber das ist nicht Gegenstand dieses Artikels.
Nichtkryptografische Hash-Funktionen haben ebenfalls mehrere Verwendungszwecke, wobei der häufigste ihre Verwendung in Hash-Tabellen ist, die uns am meisten interessieren und die wir genauer untersuchen werden.
Einführung in Hash-Tabellen (Hash-Maps)
Stellen Sie sich vor, wir müssten eine Liste aller Mitglieder eines Vereins führen und gleichzeitig nach einem bestimmten Mitglied suchen können. Man könnte die Liste in einem Array (oder einer verknüpften Liste) aufbewahren und bei der Suche die Elemente durchlaufen, bis man das gewünschte Mitglied gefunden hat (z. B. anhand des Namens). Im schlimmsten Fall würde das bedeuten, dass alle Elemente überprüft werden müssen (wenn das gesuchte Element das letzte ist oder gar nicht vorhanden ist), oder im Durchschnitt die Hälfte. Aus Sicht der Komplexitätstheorie hätte die Suche dann eine Komplexität von O(n), und sie wäre für eine kleine Liste einigermaßen schnell, aber sie würde in direktem Verhältnis zur Anzahl der Mitglieder immer langsamer werden.
Wie könnte das verbessert werden? Nehmen wir an, alle Mitglieder hätten ein Mitglied ID, das zufällig eine fortlaufende Nummer ist, die die Reihenfolge ihres Beitritts zum Club widerspiegelt.
Angenommen, die Suche nach ID wäre akzeptabel, dann könnten wir alle Mitglieder in einem Array ablegen, wobei ihre Indizes mit ihren ID übereinstimmen (ein Mitglied mit ID=10 hätte zum Beispiel den Index 10 im Array). Auf diese Weise könnten wir direkt auf jedes Element zugreifen, ohne überhaupt zu suchen. Das wäre sehr effizient, und zwar so effizient wie nur möglich, was der geringstmöglichen Komplexität O(1) entspricht, die auch als konstante Zeit bezeichnet wird.
Aber zugegebenermaßen ist unser Szenario mit dem Vereinsmitglied ID etwas konstruiert. Was wäre, wenn ID große, nicht-sequenzielle oder zufällige Zahlen wären? Oder wenn die Suche nach ID nicht zulässig wäre und wir stattdessen nach dem Namen (oder einem anderen Feld) suchen müssten? Es wäre sicherlich nützlich, den schnellen Direktzugriff (oder etwas Ähnliches) beizubehalten und gleichzeitig in der Lage zu sein, mit beliebigen Datensätzen und weniger restriktiven Suchkriterien umzugehen.
Hier kommen die Hash-Funktionen zur Hilfe. Eine geeignete Hash-Funktion kann verwendet werden, um ein beliebiges Datenstück auf eine Ganzzahl abzubilden, die eine ähnliche Rolle wie unser Clubmitglied ID spielt, wenn auch mit einigen wichtigen Unterschieden.
Erstens hat eine gute Hash-Funktion im Allgemeinen einen großen Ausgabebereich (typischerweise den gesamten Bereich einer 32- oder 64-Bit-Ganzzahl), so dass es entweder unpraktisch oder schlicht unmöglich wäre, ein Array für alle möglichen Indizes zu erstellen, und eine kolossale Speicherverschwendung wäre. Um dieses Problem zu lösen, können wir ein Array mit einer vernünftigen Größe anlegen (z. B. die doppelte Anzahl der zu speichernden Elemente) und eine Modulo-Operation mit dem Hash durchführen, um den Array-Index zu erhalten. Der Index wäre also index = hash(object) mod N, wobei N die Größe des Arrays ist.
Zweitens werden Objekt-Hashes nicht eindeutig sein (es sei denn, wir arbeiten mit einem festen Datensatz und einer maßgeschneiderten perfekten Hash-Funktion, aber darauf gehen wir hier nicht ein). Es wird Kollisionen geben (die durch die Modulo-Operation noch verstärkt werden), und deshalb wird ein einfacher direkter Indexzugriff nicht funktionieren. Es gibt mehrere Möglichkeiten, damit umzugehen, aber eine typische besteht darin, jedem Array-Index eine Liste anzuhängen, die allgemein als Bucket bezeichnet wird und alle Objekte enthält, die sich einen bestimmten Index teilen.
Wir haben also ein Array der Größe N, bei dem jeder Eintrag auf einen Objekt-Bucket verweist. Um ein neues Objekt hinzuzufügen, müssen wir dessen hash modulo N berechnen und den Bucket mit dem resultierenden Index überprüfen und das Objekt hinzufügen, wenn es dort noch nicht vorhanden ist. Um ein Objekt zu suchen, machen wir dasselbe, wir schauen nur in den Bucket, um zu prüfen, ob das Objekt dort vorhanden ist. Eine solche Struktur wird als Hash-Tabelle bezeichnet, und obwohl die Suchvorgänge innerhalb der Buckets linear sind, sollte eine richtig dimensionierte Hash-Tabelle eine relativ kleine Anzahl von Objekten pro Bucket haben, was zu einem Zugriff in fast konstanter Zeit führt (eine durchschnittliche Komplexität von O(N/k), wobei k die Anzahl der Buckets ist).
Bei komplexen Objekten wird die Hash-Funktion normalerweise nicht auf das gesamte Objekt, sondern auf einen Schlüssel angewendet. In unserem Beispiel mit den Vereinsmitgliedern könnte jedes Objekt mehrere Felder enthalten (z. B. Name, Alter, Adresse, E-Mail, Telefon), aber wir könnten z. B. die E-Mail als Schlüssel wählen, so dass die Hash-Funktion nur auf die E-Mail angewandt würde. In der Tat muss der Schlüssel nicht Teil des Objekts sein; es ist üblich, Schlüssel/Wert-Paare zu speichern, wobei der Schlüssel normalerweise eine relativ kurze Zeichenkette ist und der Wert ein beliebiges Datenelement sein kann. In solchen Fällen wird die Hash-Tabelle oder Hash-Map als Wörterbuch verwendet, und das ist die Art und Weise, wie einige Hochsprachen Objekte oder assoziative Arrays implementieren.
Scaling Out: Verteiltes Hashing
Nachdem wir nun das Hashing besprochen haben, sind wir bereit, uns mit dem verteilten Hashing zu befassen.
In manchen Situationen kann es notwendig oder wünschenswert sein, eine Hash-Tabelle in mehrere Teile aufzuteilen, die von verschiedenen Servern gehostet werden. Eine der Hauptmotivationen dafür ist die Umgehung der Speicherbeschränkungen bei der Verwendung eines einzelnen Computers, was die Konstruktion beliebig großer Hash-Tabellen ermöglicht (vorausgesetzt, es gibt genügend Server).
In einem solchen Szenario werden die Objekte (und ihre Schlüssel) auf mehrere Server verteilt, daher der Name.
Ein typischer Anwendungsfall hierfür ist die Implementierung von In-Memory-Caches wie Memcached.
Solche Setups bestehen aus einem Pool von Caching-Servern, die viele Schlüssel/Wert-Paare hosten und für den schnellen Zugriff auf Daten verwendet werden, die ursprünglich an anderer Stelle gespeichert (oder berechnet) wurden. Um beispielsweise die Belastung eines Datenbankservers zu verringern und gleichzeitig die Leistung zu verbessern, kann eine Anwendung so konzipiert werden, dass sie zunächst Daten von den Cache-Servern abruft und nur dann, wenn sie dort nicht vorhanden sind – eine Situation, die als Cache-Miss bekannt ist – auf die Datenbank zurückgreift, die entsprechende Abfrage durchführt und die Ergebnisse mit einem geeigneten Schlüssel zwischenspeichert, so dass sie beim nächsten Mal gefunden werden können.
Wie erfolgt nun die Verteilung? Welche Kriterien werden verwendet, um zu bestimmen, welche Schlüssel auf welchen Servern gespeichert werden?
Die einfachste Möglichkeit ist, den Hash modulo der Anzahl der Server zu nehmen. Das heißt, server = hash(key) mod N, wobei N die Größe des Pools ist. Um einen Schlüssel zu speichern oder abzurufen, berechnet der Client zunächst den Hash, wendet eine modulo N-Operation an und verwendet den daraus resultierenden Index, um den entsprechenden Server zu kontaktieren (wahrscheinlich unter Verwendung einer Nachschlagetabelle mit IP-Adressen). Beachten Sie, dass die Hash-Funktion, die für die Schlüsselverteilung verwendet wird, für alle Clients dieselbe sein muss, aber es muss nicht dieselbe sein, die intern von den Caching-Servern verwendet wird.
Lassen Sie uns ein Beispiel sehen. Angenommen, wir haben drei Server, A, B und C, und wir haben einige String-Schlüssel mit ihren Hashes:
| KEY | HASH | HASH mod 3 |
|---|---|---|
| „john“ | 1633428562 | 2 |
| „bill“ | 7594634739 | 0 |
| „jane“ | 5000799124 | 1 |
| „steve“ | 9787173343 | 0 |
| „kate“ | 3421657995 | 2 |
Ein Client möchte den Wert für Schlüssel john abrufen. Sein hash modulo 3 ist 2, also muss er den Server C kontaktieren. Der Schlüssel wird dort nicht gefunden, also holt der Client die Daten von der Quelle und fügt sie hinzu. Der Pool sieht wie folgt aus:
| A | B | C |
|---|---|---|
| „john“ |
Nächste möchte ein anderer Client (oder derselbe) den Wert für Schlüssel bill abrufen. Sein hash modulo 3 ist 0, also muss er den Server A kontaktieren. Der Schlüssel wird dort nicht gefunden, also holt sich der Client die Daten von der Quelle und fügt sie hinzu. Der Pool sieht nun wie folgt aus:
| A | B | C |
|---|---|---|
| „bill“ | „john“ |
Nach dem Hinzufügen der restlichen Schlüssel sieht der Pool wie folgt aus:
| A | B | C |
|---|---|---|
| „bill“ | „jane“ | „john“ |
| „steve“ | „kate“ |
Das Rehashing-Problem
Dieses Verteilungsschema ist einfach, intuitiv und funktioniert gut. Das heißt, bis sich die Anzahl der Server ändert. Was passiert, wenn einer der Server abstürzt oder nicht mehr verfügbar ist? Die Schlüssel müssen natürlich neu verteilt werden, um den fehlenden Server zu ersetzen. Dasselbe gilt, wenn dem Pool ein oder mehrere neue Server hinzugefügt werden; die Schlüssel müssen neu verteilt werden, um die neuen Server zu berücksichtigen. Dies gilt für jedes Verteilungsschema, aber das Problem bei unserer einfachen Modulo-Verteilung ist, dass sich bei einer Änderung der Anzahl der Server auch die meisten hashes modulo N ändern, so dass die meisten Schlüssel auf einen anderen Server verschoben werden müssen. Selbst wenn also ein einziger Server entfernt oder hinzugefügt wird, müssen wahrscheinlich alle Schlüssel auf einem anderen Server neu aufbereitet werden.
Wenn wir in unserem vorherigen Beispiel den Server C entfernen, müssen wir alle Schlüssel unter Verwendung von hash modulo 2 statt hash modulo 3 neu aufbereiten, und die neuen Speicherorte für die Schlüssel wären:
| Schlüssel | 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“ |
Beachten Sie, dass alle Schlüsselpositionen geändert wurden, nicht nur die vom Server C.
In dem typischen Anwendungsfall, den wir bereits erwähnt haben (Caching), würde dies bedeuten, dass die Schlüssel plötzlich nicht mehr gefunden werden, weil sie an ihrem neuen Speicherort noch nicht vorhanden sind.
Die meisten Abfragen führen also zu Fehlern, und die ursprünglichen Daten müssen wahrscheinlich erneut von der Quelle abgerufen werden, um neu aufbereitet zu werden, was die Ursprungsserver (in der Regel eine Datenbank) stark belastet. Dies kann die Leistung stark beeinträchtigen und möglicherweise die Ursprungsserver zum Absturz bringen.
Die Lösung: Konsistentes Hashing
Wie kann dieses Problem also gelöst werden? Wir brauchen ein Verteilungsschema, das nicht direkt von der Anzahl der Server abhängt, so dass beim Hinzufügen oder Entfernen von Servern die Anzahl der Schlüssel, die verlagert werden müssen, minimiert wird. Ein solches Schema – ein cleveres und doch überraschend einfaches – wird als konsistentes Hashing bezeichnet und wurde erstmals von Karger et al. am MIT in einer akademischen Arbeit aus dem Jahr 1997 beschrieben (laut Wikipedia).
Konsistentes Hashing ist ein verteiltes Hashing-Schema, das unabhängig von der Anzahl der Server oder Objekte in einer verteilten Hash-Tabelle funktioniert, indem es ihnen eine Position auf einem abstrakten Kreis oder Hash-Ring zuweist. Dadurch können Server und Objekte skaliert werden, ohne das Gesamtsystem zu beeinträchtigen.
Stellen Sie sich vor, wir würden den Hash-Ausgabebereich auf den Rand eines Kreises abbilden. Das bedeutet, dass der kleinstmögliche Hash-Wert, Null, einem Winkel von Null entsprechen würde, der größtmögliche Wert (eine große ganze Zahl, die wir INT_MAX nennen) würde einem Winkel von 2𝝅 Radiant (oder 360 Grad) entsprechen, und alle anderen Hash-Werte würden linear irgendwo dazwischen liegen. Wir könnten also einen Schlüssel nehmen, seinen Hash-Wert berechnen und herausfinden, wo er auf dem Rand des Kreises liegt. Unter der Annahme eines INT_MAX von 1010 (als Beispiel) würden die Schlüssel aus unserem vorherigen Beispiel wie folgt aussehen:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| „john“ | 1633428562 | 58.8 |
| „bill“ | 7594634739 | 273.4 |
| „jane“ | 5000799124 | 180 |
| „steve“ | 9787173343 | 352.3 |
| „kate“ | 3421657995 | 123.2 |
Stellen Sie sich nun vor, wir hätten auch die Server am Rand des Kreises platziert, indem wir ihnen ebenfalls pseudozufällig Winkel zugewiesen hätten. Dies sollte auf eine wiederholbare Art und Weise geschehen (oder zumindest so, dass sich alle Clients über die Winkel der Server einig sind). Eine bequeme Art, dies zu tun, ist das Hashing des Servernamens (oder der IP-Adresse oder einer anderen ID) – wie wir es mit jedem anderen Schlüssel tun würden – um den Winkel zu ermitteln.
In unserem Beispiel könnte es so aussehen:
| 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 |
Da wir die Schlüssel sowohl für die Objekte als auch für die Server auf demselben Kreis haben, können wir eine einfache Regel definieren, um die Ersteren mit den Letzteren zu verbinden: Jeder Objektschlüssel gehört zu dem Server, dessen Schlüssel am nächsten liegt, und zwar gegen den Uhrzeigersinn (oder im Uhrzeigersinn, je nach den verwendeten Konventionen). Mit anderen Worten: Um herauszufinden, welcher Server für einen bestimmten Schlüssel zu fragen ist, müssen wir den Schlüssel auf dem Kreis lokalisieren und uns in Richtung des aufsteigenden Winkels bewegen, bis wir einen Server finden.
In unserem Beispiel:
| 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 |
Aus der Sicht der Programmierung würden wir eine sortierte Liste von Serverwerten führen (die Winkel oder Zahlen in einem beliebigen realen Intervall sein können) und diese Liste durchgehen (oder eine binäre Suche verwenden), um den ersten Server mit einem Wert zu finden, der größer oder gleich dem des gewünschten Schlüssels ist. Wenn kein solcher Wert gefunden wird, müssen wir umkehren und den ersten aus der Liste nehmen.
Um sicherzustellen, dass die Objektschlüssel gleichmäßig auf die Server verteilt sind, müssen wir einen einfachen Trick anwenden: Wir weisen jedem Server nicht nur ein, sondern mehrere Labels (Winkel) zu. Anstelle der Bezeichnungen A, B und C könnten wir also z. B. A0 .. A9, B0 .. B9 und C0 .. C9 haben, die alle entlang des Kreises verteilt sind. Der Faktor, um den die Anzahl der Etiketten (Server-Schlüssel) erhöht wird, das so genannte Gewicht, hängt von der Situation ab (und kann sogar für jeden Server unterschiedlich sein), um die Wahrscheinlichkeit, dass die Schlüssel auf jedem Server landen, anzupassen. Wäre beispielsweise Server B doppelt so leistungsfähig wie die anderen, könnten ihm doppelt so viele Labels zugewiesen werden, was zur Folge hätte, dass er (im Durchschnitt) doppelt so viele Objekte aufnehmen würde.
Für unser Beispiel nehmen wir an, dass alle drei Server die gleiche Gewichtung von 10 haben (dies funktioniert gut für drei Server, für 10 bis 50 Server wäre eine Gewichtung im Bereich von 100 bis 500 besser, und größere Pools benötigen möglicherweise noch höhere Gewichtungen):
| 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 |
So, was ist der Nutzen dieses Kreisansatzes? Stellen Sie sich vor, der Server C wird entfernt. Um dies zu berücksichtigen, müssen wir die Etiketten C0 .. C9 aus dem Kreis entfernen. Dies führt dazu, dass die Objektschlüssel, die zuvor an die gelöschten Etiketten angrenzten, nun zufällig mit Ax und Bx bezeichnet werden, wodurch sie den Servern A und B neu zugewiesen werden.
Aber was passiert mit den anderen Objektschlüsseln, denjenigen, die ursprünglich zu A und B gehörten? Nichts! Das ist das Schöne daran: Das Fehlen der Cx-Etiketten wirkt sich in keiner Weise auf diese Schlüssel aus. Das Entfernen eines Servers führt also dazu, dass seine Objektschlüssel nach dem Zufallsprinzip den übrigen Servern neu zugewiesen werden, wobei alle anderen Schlüssel unberührt bleiben:
| 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 |
Etwas Ähnliches passiert, wenn wir, anstatt einen Server zu entfernen, einen hinzufügen. Wenn wir in unserem Beispiel den Server D hinzufügen wollten (z. B. als Ersatz für C), müssten wir die Etiketten D0 .. D9 hinzufügen. Das Ergebnis wäre, dass etwa ein Drittel der vorhandenen Schlüssel (die alle zu A oder B gehören) D neu zugewiesen würden, während der Rest unverändert bliebe:
| 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“ | 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 |
So löst das konsistente Hashing das Rehashing-Problem.
Im Allgemeinen müssen nur k/N Schlüssel neu zugeordnet werden, wenn k die Anzahl der Schlüssel und N die Anzahl der Server ist (genauer gesagt, das Maximum aus der anfänglichen und der endgültigen Anzahl der Server).
Wir haben festgestellt, dass es bei der Verwendung von verteiltem Caching zur Leistungsoptimierung vorkommen kann, dass sich die Anzahl der Caching-Server ändert (Gründe dafür können ein Serverabsturz oder die Notwendigkeit sein, einen Server hinzuzufügen oder zu entfernen, um die Gesamtkapazität zu erhöhen oder zu verringern). Durch die Verwendung von konsistentem Hashing für die Verteilung von Schlüsseln zwischen den Servern können wir sicher sein, dass in einem solchen Fall die Anzahl der Schlüssel, die neu gehasht werden, und damit die Auswirkungen auf die Ursprungsserver minimiert werden, wodurch potenzielle Ausfallzeiten oder Leistungsprobleme vermieden werden.
Es gibt Clients für verschiedene Systeme, wie Memcached und Redis, die von Haus aus Unterstützung für konsistentes Hashing bieten.
Alternativ können Sie den Algorithmus auch selbst in der Sprache Ihrer Wahl implementieren, was relativ einfach sein sollte, sobald Sie das Konzept verstanden haben.
Wenn Sie sich für Data Science interessieren, finden Sie bei Toptal einige der besten Artikel zu diesem Thema im Blog