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

Question

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

Nichts zu schwer, nur die Grundlagen.

Answer 1

Ok, sie sind im Grunde eine recht einfache Idee. Ein DHT gibt Ihnen eine wörterbuchähnliche Schnittstelle, aber die Knoten sind über das Netzwerk verteilt. Der Trick bei DHTs besteht darin, dass der Knoten, der einen bestimmten Schlüssel ablegen soll, durch Hashing dieses Schlüssels gefunden wird, so dass Ihre Hash-Tabellen-Buckets jetzt unabhängige Knoten in einem Netzwerk sind.

Dies gibt eine Menge Fehlertoleranz und Zuverlässigkeit und möglicherweise einige Leistungsvorteile, aber es wirft auch eine Menge Kopfschmerzen auf. Was passiert zum Beispiel, wenn ein Knoten das Netzwerk verlässt, durch einen Fehler oder auf andere Weise? Und wie verteilen Sie Schlüssel neu, wenn ein Knoten verbunden wird, sodass die Last in etwa ausgeglichen ist. Wenn ich darüber nachdenke, wie verteilst du Schlüssel gleichmäßig? Und wenn ein Knoten sich anschließt, wie vermeidest du es, alles neu zu speichern? (Denken Sie daran, dass Sie dies in einer normalen Hash-Tabelle tun müssten, wenn Sie die Anzahl der Buckets erhöhen).

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

Zum Beispiel sagen in einem Ring mit drei Knoten der erste Knoten hat die Schlüssel 0-10, der zweite 11-20 und der dritte 21-30. Wenn ein vierter Knoten kommt und sich zwischen Knoten 3 und 0 einfügt (denken Sie daran, dass sie in einem Ring sind), kann er die Verantwortung für den halben Schlüsselraum übernehmen, so dass er jetzt 26-30 behandelt und Knoten 3 mit 21 befasst -25.

Es gibt viele andere Overlay-Strukturen wie diese, die inhaltsbasiertes Routing verwenden, um den richtigen Knoten zu finden, auf dem ein Schlüssel gespeichert werden soll. Das Auffinden eines Schlüssels in einem Ring erfordert das Durchsuchen des Rings um jeweils einen Knoten (es sei denn, Sie behalten eine lokale Nachschlagetabelle bei, die in einer DHT von Tausenden von Knoten problematisch ist), nämlich O (n) -Hop-Routing. Andere Strukturen - einschließlich erweiterter Ringe - garantieren O (log n) -Hop-Routing und einige beanspruchen O (1) -Hop-Routing auf Kosten von mehr Wartung.

Lesen Sie die Wikipedia-Seite, und wenn Sie wirklich in ein bisschen Tiefe wissen wollen, überprüfen Sie diese coursepage in Harvard, die eine ziemlich umfassende Leseliste hat.

Answer 2

DHTs bieten dem Benutzer den gleichen Schnittstellentyp wie eine normale Hashtabelle (einen Wert nach Schlüssel suchen), aber die Daten werden über eine beliebige Anzahl verbundener Knoten verteilt. Wikipedia hat eine gute grundlegende Einführung, die ich im Wesentlichen regurgitating würde, wenn ich schreibe mehr -

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

Answer 3

Check out this Wikipedia article Oder diese powerpoint slide

Answer 4

check out Amazon Dynamo, erklärt es eine einfache, aber neuartige DHT-Implementierung basierend auf Kreis konsistente Hashing.

Answer 5

Ich würde gern HenryRs nützliche Antwort hinzufügen, da ich gerade einen Einblick in konsistentes Hashing hatte. Ein normales/naives Hash-Lookup ist eine Funktion von zwei Variablen, von denen die Anzahl der Buckets ist. Das Schöne an konsistentem Hashing ist, dass wir die Anzahl der Buckets "n" aus der Gleichung eliminieren.

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

Vergleichen Sie dies mit konsistent Hashing. Definieren wir "R" als den Bereich einer Hash-Funktion. R ist nur eine Konstante. Bei konsistentem Hashing befindet sich die Adresse eines Objekts bei Hash (x)/R. Da unser Lookup nicht mehr von der Anzahl der Buckets abhängt, haben wir weniger Neuzuordnung, wenn wir die Anzahl der Buckets ändern.

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