Einfache grundlegende Erklärung einer verteilten Hash-Tabelle (DHT)

Könnte jemand eine Erklärung geben, wie ein DHT funktioniert?

Nichts zu schweres, nur die Grundlagen.

Ok, sie sind im Grunde eine ziemlich einfache Idee. Ein DHT bietet Ihnen eine wörterbuchähnliche Schnittstelle, die Knoten sind jedoch über das Netzwerk verteilt. Der Trick bei DHTs besteht darin, dass der Knoten, der einen bestimmten Schlüssel speichern kann, durch Hashing dieses Schlüssels gefunden wird. Tatsächlich sind Ihre Hash-Tabellen-Buckets nun unabhängige Knoten in einem Netzwerk.

Dies bietet viel Fehlertoleranz und Zuverlässigkeit und möglicherweise einen gewissen Leistungsvorteil, verursacht aber auch viele Kopfschmerzen. Was passiert beispielsweise, wenn ein Knoten das Netzwerk verlässt, indem er ausfällt oder auf andere Weise? Und wie verteilen Sie Schlüssel neu, wenn ein Knoten beitritt, damit die Last ungefähr ausgeglichen ist? Kommen Sie und denken Sie darüber nach, wie verteilen Sie die Schlüssel überhaupt gleichmäßig? Und wenn ein Knoten beitritt, wie vermeiden Sie es, alles erneut aufzuwärmen? (Denken Sie daran, dass Sie dies in einer normalen Hash-Tabelle tun müssen, wenn Sie die Anzahl der Buckets erhöhen.)

Ein Beispiel für DHT, das einige dieser Probleme angeht, ist ein logischer Ring von n Knoten, die jeweils die Verantwortung für 1 / n des Schlüsselraums übernehmen. Sobald Sie dem Netzwerk einen Knoten hinzugefügt haben, findet dieser einen Platz auf dem Ring zwischen zwei anderen Knoten und übernimmt die Verantwortung für einige der Schlüssel in seinen Geschwisterknoten. Das Schöne an diesem Ansatz ist, dass keiner der anderen Knoten im Ring betroffen ist. Nur die beiden Geschwisterknoten müssen die Schlüssel neu verteilen.

Angenommen, in einem Ring mit drei Knoten hat der erste Knoten die Schlüssel 0-10, der zweite 11-20 und der dritte 21-30. Wenn ein vierter Knoten vorbeikommt und sich zwischen die Knoten 3 und 0 einfügt (denken Sie daran, dass sie sich in einem Ring befinden), kann er beispielsweise die Hälfte des Schlüsselraums von 3 übernehmen, sodass er sich jetzt mit 26-30 und Knoten 3 mit 21 befasst -25.

Es gibt viele andere Überlagerungsstrukturen wie diese, die inhaltsbasiertes Routing verwenden, um den richtigen Knoten zum Speichern eines Schlüssels zu finden. Um einen Schlüssel in einem Ring zu finden, müssen Sie den Knoten Knoten für Knoten durchsuchen (es sei denn, Sie führen eine lokale Nachschlagetabelle, die bei einem DHT mit Tausenden von Knoten problematisch ist). Dies ist ein O (n) -Hop-Routing. Andere Strukturen - einschließlich erweiterter Ringe - garantieren O (log n) -Hop-Routing und einige behaupten, O (1) -Hop-Routing auf Kosten von mehr Wartung.

Lesen Sie die Wikipedia-Seite, und wenn Sie wirklich etwas mehr wissen möchten, lesen Sie diese Kursseite in Harvard, die eine ziemlich umfassende Leseliste enthält.

DHTs bieten dem Benutzer dieselbe Art von Schnittstelle wie eine normale Hashtabelle (suchen Sie einen Wert nach Schlüssel), die Daten werden jedoch auf eine beliebige Anzahl verbundener Knoten verteilt. Wikipedia hat eine gute grundlegende Einführung, die ich im Wesentlichen wieder erbrechen würde, wenn ich mehr schreibe -

http://en.wikipedia.org/wiki/Distributed_hash_table

Ich möchte die nützliche Antwort von HenryR ergänzen, da ich gerade einen Einblick in konsistentes Hashing hatte. Eine normale / naive Hash-Suche ist eine Funktion von zwei Variablen, von denen eine die Anzahl der Buckets ist. Das Schöne an konsistentem Hashing ist, dass wir die Anzahl der Eimer "n" aus der Gleichung streichen.

Beim naiven Hashing ist die erste Variable der Schlüssel des Objekts, das in der Tabelle gespeichert werden soll. Wir nennen den Schlüssel "x". Die zweite Variable ist die Anzahl der Buckets "n". Um festzustellen, in welchem ​​Bucket / in welcher Maschine das Objekt gespeichert ist, müssen Sie Folgendes berechnen: hash (x) mod (n). Wenn Sie also die Anzahl der Buckets ändern, ändern Sie auch die Adresse, unter der fast jedes Objekt gespeichert ist.

Vergleichen Sie dies mit konsistentem Hashing. Definieren wir "R" als den Bereich einer Hash-Funktion. R ist nur eine Konstante. Beim konsistenten Hashing befindet sich die Adresse eines Objekts bei Hash (x) / R. Da unsere Suche nicht mehr von der Anzahl der Buckets abhängt, werden wir weniger neu zugeordnet, wenn wir die Anzahl der Buckets ändern.

http://michaelnielsen.org/blog/consistent-hashing/