Einfache grundlegende Erklärung einer Distributed Hash Table (DHT)

Ok, Sie sind im Grunde eine ziemlich einfache Idee. Ein DHT gibt Sie ein dictionary-ähnliches interface, aber die Knoten verteilt sind, über das Netzwerk. Der trick mit DHTs ist, dass der Knoten, der wird zum speichern ein bestimmter Schlüssel gefunden wird, indem hashing-Schlüssel, so in der Tat Ihre hash-Tabelle, die Eimer sind jetzt unabhängige Knoten in einem Netzwerk.

Dies gibt eine Menge von Fehlertoleranz und Zuverlässigkeit, und möglicherweise einige performance-Vorteile, aber auch wirft eine Menge Kopfschmerzen. Was passiert zum Beispiel, wenn ein Knoten verlässt das Netzwerk, zu scheitern oder nicht? Und wie wollen Sie das verteilen von Schlüsseln, wenn ein Knoten verbindet, so dass die Last ist in etwa ausgeglichen. Kommen Sie, daran zu denken, wie Sie gleichmäßig zu verteilen-Tasten überhaupt? Und wenn ein Knoten verbindet, wie vermeiden Sie Aufwärmen alles? (Denken Sie daran, Sie müssten dies tun, in einer normalen hash-Tabelle, wenn Sie erhöhen die Anzahl der buckets).

Einem Beispiel DHT bekämpft und einige dieser Probleme ist eine logische ring aus n Knoten, die jeweils die Verantwortung für die 1/n der Schlüsselraum. Sobald Sie einen Knoten hinzufügen, um das Netzwerk, findet es einen Platz auf dem ring sitzt zwischen zwei anderen Knoten, und übernimmt die Verantwortung für einige der Schlüssel in der Geschwister-Knoten. Die Schönheit dieses Ansatzes ist, dass keiner der anderen Knoten im ring sind betroffen; nur die beiden Geschwister-Knoten zum verteilen von Schlüsseln.

Sagen wir zum Beispiel, in einem drei-Knoten-ring der erste Knoten hat die Schlüssel 0-10, die zweite 11-20 und die Dritte 21-30. Wenn eine vierte Knoten kommt und fügt sich selbst zwischen den Knoten 3 und 0 (denken Sie daran, Sie sind in einem ring), der es verantworten kann sagen, die Hälfte von 3 ist der Schlüsselraum, also, nun es beschäftigt sich mit 26-30 und Knoten 3 befasst sich mit 21-25.

Gibt es viele weitere overlay-Strukturen wie diese, die Verwendung von " content-basierte routing zu finden, den richtigen Knoten zur Speicherung der Schlüssel. Suchen eines Schlüssels in einem ring erfordert die Suche durch den ring von einem Knoten zu einem Zeitpunkt (es sei denn, Sie halten eine local look-up-Tabelle, die problematisch in einer DHT von tausenden von Knoten), die O(n)-hop-routing. Andere Strukturen - einschließlich der augmented-Ringe - garantiert in O(log n)-hop-routing, und einige behaupten, dass der O(1)-hop-routing an den Kosten der Wartung.

Lesen Sie die wikipedia-Seite, und wenn Sie wirklich wollen, zu wissen, ein wenig Tiefe, überprüfen Sie heraus dieses coursepage an der Harvard-Universität hat eine Recht umfassende Literaturliste.

InformationsquelleAutor der Antwort HenryR

Ich möchte noch hinzufügen, auf HenryR die nützliche Antwort, da hatte ich nur einen Einblick in das konsistente hashing. Ein normal/naiv hash-lookup ist eine Funktion von zwei Variablen, von denen die Anzahl der buckets. Die Schönheit von konsistenten hashing ist, dass wir beseitigen die Anzahl der buckets "n", aus der Gleichung.

In naive hashing erste variable ist der Schlüssel zu dem Objekt werden in der Tabelle gespeichert. Wir nennen die Taste "x". Die zweite variable ist die Anzahl der buckets, "n". Also, um zu bestimmen, welche Eimer/Maschine das Objekt gespeichert ist, müssen Sie berechnen: hash(x) mod(n). Daher, wenn Sie ändern die Anzahl der buckets, ändern Sie auch die Adresse, an der fast jedes Objekt gespeichert ist.

Vergleichen, um konsistente hashing. Definieren wir "R" als der Bereich der hash-Funktion. R ist nur einige Konstanten. In der konsistenten hashing, die Adresse eines Objekts befindet sich bei hash(x)/R. Da unsere lookup ist nicht mehr eine Funktion von der Anzahl der Eimer, die wir am Ende mit weniger Neuzuordnung, wenn wir ändern die Anzahl der buckets.

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

InformationsquelleAutor der Antwort thebiggestlebowski

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

InformationsquelleAutor der Antwort Peiti Peter Li