Verteilte Hashtabelle

aus Wikipedia, der freien Enzyklopädie

Eine verteilte Hashtabelle (VHT) (engl. distributed hashtable (DHT)) ist eine Datenstruktur, die versucht das allgemeine Problem in P2P-Systemen – den Speicherort einer gesuchten Datei zu finden – mit möglichst geringem Aufwand effizient zu lösen. 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.

Inhaltsverzeichnis 1 Eigenschaften 2 Prinzipielle Arbeitsweise 3 Implementierungen 4 Anwendungen 4.1 VHTs zur Datenspeicherung 4.2 Applikationen 4.3 VHT Forschung

[Bearbeiten] 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.
• Sicherheit/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.

[Bearbeiten] 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 den selben 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(logn) zu erreichen.

Inhalte können direkt, d.h. 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.

[Bearbeiten] Implementierungen

Derzeit existieren folgende Implementierungen verteilter Hashtabellen:

• CAN (Content Addressable Network)
• Chord
• Kademlia
• Pastry
• Tapestry

[Bearbeiten] Anwendungen

[Bearbeiten] VHTs zur Datenspeicherung

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

[Bearbeiten] Applikationen

• Askemos: störfest replizierte, kommunizierende Prozesse
• Azureus (Filesharing-Client): BitTorrent-Client
• BitComet: BitTorrent-Client
• BitSpirit: BitTorrent-Client
• BitTorrent (ab Version 4.1.0, Betaphase)
• eDonkey2000, Name: Overnet
• Coral: Verteilungsnetzwerk für Inhalte
• eMule (ab Version 0.42) und aMule (ab Version 2.1.0), Name: Kad
• Freenet: Anonymer Datenspeicher.
• KTorrent: BitTorrent-Client
• MLDonkey (Overnet und Kademlia)
• OceanStore: Archivspeicher.
• P-Grid
• The Circle: File sharing und chat.
• µTorrent: BitTorrent-Client
• VarVar [1] (erster Client mit Kademlia, eigenes Netz)
• YaCy: verteilte Suchmaschine

[Bearbeiten] VHT Forschung

• Project IRIS (Infrastructure for Resilient Internet Systems)