Einfache grundlegende Erklärung einer Distributed Hash Table (DHT)
https://stackoverflow.com/questions/144360
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Könnte jemand eine Erklärung geben, wie ein DHT funktioniert?
Nichts zu schwer, nur die Grundlagen.
Lösung
Ok, sie sind im Grunde eine recht einfache Idee. Ein DHT gibt Ihnen eine Wörterbuch-ähnliche Oberfläche, aber die Knoten im Netzwerk verteilt. Der Trick mit DHTs ist, dass der Knoten, der eine bestimmte Taste zu speichern, wird durch Hashing diesen Schlüssel gefunden wird, so in der Tat Ihre Hash-Tabelle Eimer sind jetzt unabhängig Knoten in einem Netzwerk.
Das gibt eine Menge von Fehlertoleranz und Zuverlässigkeit, und möglicherweise einige Leistungsvorteil, aber es wirft auch viele Kopfschmerzen auf. Zum Beispiel, was passiert, wenn ein Knoten das Netzwerk verlässt, indem sie nicht oder anders? Und wie Sie die Schlüssel verteilen, wenn ein Knoten verbindet, so dass die Belastung in etwa ausgeglichen ist. Kommen Sie, daran zu denken, wie verteilen Sie gleichmäßig Schlüssel überhaupt? Und wenn ein Knoten verbindet, wie vermeiden Sie alles wieder aufzuwärmen? (Denken Sie daran, Sie müßten dies tun, in einer normalen Hash-Tabelle, wenn Sie die Anzahl der Schaufeln erhöhen).
Ein Beispiel DHT, dass einige dieser Probleme anpackt ist ein logischer Ring von n Knoten, die jeweils die Verantwortung für 1 / n des Schlüsselraums. Sobald Sie einen Knoten zum Netzwerk hinzufügen, findet er einen Platz auf dem Ring zwischen zwei anderen Knoten zu sitzen, und übernimmt die Verantwortung für einige der Schlüssel in seinem Geschwister-Knoten. Die Schönheit dieses Ansatzes ist, dass keiner der anderen Knoten im Ring betroffen ist; nur die beiden Geschwister-Knoten haben Schlüssel zu verteilen.
Angenommen, in einem Drei-Knoten-Ring der erste Knotenschlüssel 0-10 hat, die zweite und die dritte 11-20 21-30. Wenn ein vierter Knoten entlang kommt und fügt sich zwischen den Knoten 3 und 0 (denken Sie daran, sie sind in einem Ring), kann er die Verantwortung für etwa die Hälfte der 3 des Schlüsselraums, jetzt geht es um 26 bis 30 und Knoten 3 befasst sich mit 21 -25.
Es gibt viele andere Overlay-Strukturen wie diese, die inhaltsbasierte Routing verwenden, um die richtigen Knoten, auf das finden, um einen Schlüssel zu speichern. einen Schlüssels in einem Ring Ortung erfordert zu einem Zeitpunkt, um den Ring eines Knoten suchen (es sei denn, Sie eine lokale Look-Up-Tabelle, problematisch in einem DHT von Tausenden von Knoten zu halten), die O (n) -hopfen blüten Routing ist. Andere Strukturen - auch Augmented-Ringe - Garantie O (log n) -hopfen blüten Routing und einige Anspruch O (1) -Hop auf Kosten von mehr Wartung Routing.
Lesen Sie die Wikipedia-Seite, und wenn Sie wirklich ein bisschen in der Tiefe wissen wollen, lesen Sie in diesem coursepage in Harvard, die eine ziemlich umfassende Leseliste hat.
Andere Tipps
DHTs bieten die gleiche Art der Schnittstelle an den Benutzer als eine normale Hashtable (look Wert von Taste nach oben), aber die Daten werden über eine beliebige Anzahl von verbundenen Knoten verteilt. Wikipedia hat eine gute grundlegende Einführung, die ich im Wesentlichen regurgitating würde, wenn ich schreibe mehr -
Ich möchte auf HenryR die sachdienliche Antwort hinzufügen, wie ich nur einen Einblick in die konsistente Hashing hatte. Ein normal / naiver Hash-Lookup, ist eine Funktion von zwei Variablen, von denen die Anzahl der Schaufeln. Die Schönheit des konsequenten Hashing ist, dass wir die Anzahl der Eimer „n“ aus der Gleichung.
beseitigenIn naivem Hashing erster Variable ist der Schlüssel des Objekts in der Tabelle gespeichert werden. Wir werden die Schlüssel „x“ nennen. Die zweite Variable ist die Anzahl der Schaufeln, „n“. Also, um festzustellen, welche bucket / Maschine wird das Objekt gespeichert, muss man berechnen: hash (x) mod (n). Deshalb, wenn Sie die Anzahl der Schaufeln ändern, ändern Sie auch die Adresse, an der fast jedes Objekt gespeichert wird.
Vergleichen Sie dies mit konsistentem Hashing. Lassen Sie uns „R“ als der Bereich einer Hash-Funktion definieren. R ist nur eine Konstante. In konsistentem Hashing, die Adresse eines Objekts wird bei hash (x) / R liegt. Da unsere Lookup nicht mehr eine Funktion der Anzahl der Schaufeln ist, landen wir mit weniger Remapping, wenn wir die Anzahl der Schaufeln ändern.
Schauen Sie sich diesem Wikipedia-Artikel Oder diese Powerpoint-Folie
Besuche Amazon Dynamo, erklärt es eine einfache, aber neue DHT Implementierung basiert auf Kreis konsistente Hashing.
