Distributed Hashtable

Eine verteilte Hashtabelle (VHT) [engl.: distributed hash table (DHT)] ist eine Datenstruktur, die versucht, das allgemeine Problem in P2P-Systemen – das Finden des Speicherorts einer gesuchten Datei – mit möglichst geringem Aufwand effizient zu lösen und zu dezentralisieren, um es von Ausfall, zum Beispiel durch Abschalten eines BitTorrent-Trackers unabhängig zu gestalten. Die Datenobjekte sollen dabei möglichst gleichmäßig über die Knotenmenge verteilt und ein von jedem beliebigen Einstiegsort ortsunabhängiges Routing zum verantwortlichen Knoten ermöglicht werden. Jeder Knoten ist dabei analog zu einem Behälter einer Hashtabelle. Die Datenstruktur muss ständige Anpassungen durch Ausfall, Beitritt und Austritt von Knoten überstehen, sich selbst organisieren und skalierbar sein. Die Grundlage für verteilte Hashtabellen bilden konsistente Hash-Funktionen.

Eigenschaften

Eigenschaften von VHTs sind:

• Selbstorganisation: Es ist keine manuelle Konfiguration nötig.
• Skalierbarkeit: Das System sollte in der Lage sein, auch mit einer großen Anzahl von Knoten funktionsfähig zu bleiben.
• Lastenverteilung: Schlüssel werden gleichmäßig auf alle Knoten verteilt.
• Fehlertoleranz: Das System sollte zuverlässig funktionieren, auch wenn Knoten ausfallen oder das System verlassen.
• Robustheit: Das System sollte „korrekt“ funktionieren können, auch wenn ein Teil (möglicherweise ein Großteil) der Knoten versuchen, das System zu stören.

Prinzipielle Arbeitsweise

Mittels einer Hash-Funktion werden den Datenobjekten Schlüssel in einem linearen Wertebereich vergeben, welcher möglichst gleichmäßig über die Knoten der Knotenmenge verteilt wird. Jeder Knoten ist dabei mindestens für einen Teilbereich des Schlüsselraumes zuständig, oft sind jedoch auch mehrere Knoten für denselben Bereich verantwortlich, wobei sich die Zuständigkeiten dynamisch ändern. Ein Beitrittsprotokoll regelt die Aufnahme neuer Knoten in ein existierendes System, normalerweise indem mit einem anderen Knoten, der bereits Teil des Systems ist, verbunden wird. Das Protokoll stellt dann die Verbindungen zu den Nachbarknoten her und regelt üblicherweise auch die Konstruktion von Routingtabellen. Routingtabellen werden von VHT-Knoten benutzt, um effizient herausfinden zu können, welcher andere Knoten für einen bestimmten Satz Informationen zuständig ist. Die Definition von "Entfernung" ist dabei mit der Struktur und der Topologie verbunden und variiert in unterschiedlichen Systemen und muss nichts mit der physikalischen Organisation der Knoten zu tun haben. Eine VHT, die beispielsweise Knoten in einem euklidischen Raum platziert, könnte einfach den Knoten mit dem geringsten euklidischen Abstand zu einem Schlüssel wählen. Routingtabellen sollen es jedem Knoten erlauben, den nächsten Knoten zu einem Schlüssel in O(log n) zu erreichen.

Inhalte können direkt, das heißt bei dem für sie zuständigen Knoten, oder indirekt durch einen Verweis auf die Adresse des Knotens, welcher die Daten enthält, gespeichert werden.

Da Schlüssel keine semantische Bedeutung haben, sind die verwalteten Inhalte anwendungsunabhängig. Durch die generische Schnittstelle, welche nur die zwei Funktionen publish(Schlüssel, Inhalt) und lookup(Schlüssel) anbietet, lassen sich die implementierten Algorithmen auswechseln.

Implementierungen

Implementierungen verteilter Hashtabellen sind etwa Chord und Kademlia.

Anwendungen

VHTs zur Datenspeicherung

• OpenDHT
• Bamboo
• The Chord/DHash Project
• FreePastry

Applikationen

• Azureus (Filesharing-Client): BitTorrent-Client
• BitComet: BitTorrent-Client
• BitTorrent (ab Version 4.1.0, Betaphase)
• Coral: Verteilungsnetzwerk für Inhalte
• Deluge (BitTorrent-Client)
• eDonkey2000, Name: Overnet
• eMule (ab Version 0.40) und aMule (ab Version 2.1.0), Name: Kad
• Free Download Manager: freier Download-Manager, der auch BitTorrent und DHT beherrscht
• Freenet: Anonymer Datenspeicher.
• Halite: BitTorrent-Client
• KTorrent: BitTorrent-Client
• LimeWire (Name: Mojito)
• MLDonkey (Overnet und Kademlia)
• RetroShare serverloses Kommunikations-Programm
• rTorrent: BitTorrent-Client
• CSpace: Instant Messenger mit Kademlia
• µTorrent: BitTorrent-Client
• YaCy: verteilte Suchmaschine

VHT-Forschung

• Project IRIS (Infrastructure for Resilient Internet Systems)