Verteilte Hashtabelle

Verteilte Hashtabelle

Eine verteilte Hashtabelle (engl. distributed hash table, DHT) ist eine Datenstruktur, die zum Beispiel dazu genutzt werden kann, den Speicherort einer Datei in einem P2P-System zu speichern. Dabei steht die Dezentralisierung und die Effizienz der Datenspeicherung im Vordergrund.

Die Daten werden möglichst gleichmäßig über die vorhandenen Speicherknoten verteilt. Jeder Speicherknoten entspricht dabei einem Eintrag in der Hashtabelle. Die selbstorganisierende Datenstruktur kann den Ausfall, Beitritt und Austritt von Knoten abbilden. Die Grundlage für verteilte Hashtabellen bilden konsistente Hash-Funktionen.

Man unterscheidet DHTs nach dem Speicherschema. Die Daten können direkt innerhalb der DHT abgelegt werden (direct storage) oder in der DHT kann ein Verweis auf die Daten vorgehalten werden (indirect storage). Direct Storage bietet sich nur für kleine Daten (<1KB) an, da sonst das System zu unflexibel würde.

Inhaltsverzeichnis

Eigenschaften

Eigenschaften von DHTs 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 versucht, 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 das existierende System. Das Protokoll stellt dann die Verbindungen zu den Nachbarknoten her und regelt üblicherweise auch die Konstruktion von Routingtabellen.

Die Routingtabellen werden von den DHT-Knoten zur Ermittlung anderer Knoten benutzt, die für bestimmte Datensätze zuständig sind. Die Definition der "Entfernung" ist dabei mit der Struktur und der Topologie verbunden und variiert in unterschiedlichen Systemen. Sie muss nicht zwingend mit der physikalischen Organisation der Knoten übereinstimmen. Eine verteilte Hashtabelle, die ihre Knoten in einem euklidischen Raum platziert, könnte den Knoten mit dem geringsten euklidischen Abstand zu einem Schlüssel wählen. Die Routingtabellen sollen es jedem Knoten erlauben, den nächsten Knoten zu einem Schlüssel in O(log n) Suchschritten zu erreichen.

Durch eine generische Schnittstelle, die nur zwei Funktionen publish(Schlüssel, Inhalt) und lookup(Schlüssel) anbietet, lassen sich die implementierten Algorithmen auswechseln.

Implementierungen

Derzeit existieren unter anderem folgende Implementierungen verteilter Hashtabellen:

  • Chord
  • Kademlia - Strukturen basierend auf diesem Algorithmus existieren in mehreren P2P-Netzwerken, sind allerdings meist nicht untereinander kompatibel. Beispiele sind die DHT-Implementierungen von mehreren BitTorrent-Programmen, Mojito und KAD:
    • KAD - Entwicklung des eMule-Entwicklungsteams, basierend auf dem Kademlia-Algorithmus, um die mit der Zeit ausfallenden Server des eDonkey2000-Netzwerks zu ersetzen.
    • Mojito - Entwicklung des LimeWire-Entwicklungsteams zur schnellen Quellenermittlung innerhalb des gnutella-Netzwerks.

Anwendungen

DHTs zur Datenspeicherung

Software

DHT-Forschung

  • Project IRIS (Infrastructure for Resilient Internet Systems)

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Hashtabelle — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Hash-Tabelle — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Hashmap — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Hashtable — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Hashverfahren — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Key-to-Address Transform Techniques — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Streuspeicherverfahren — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Streuwerttabelle — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Datenstrukturen — In der Informatik ist eine Datenstruktur ein mathematisches Objekt zur Speicherung von Daten. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre… …   Deutsch Wikipedia

  • Distributed Hash Table — 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… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”