WikiDer > Verteilte Hash-Tabelle

Verteilte Hash-Tabellen

EIN verteilte Hash-Tabelle, oder verteilte Hash-Tabelle, ist eine Art dezentralisiertes Verteilungssystem, in dem man Suchen durchführen kann, ähnlich wie a Hash-tabelle. In einem DHT entspricht jedes Element einer numerischen Taste. Jeder teilnehmende Knoten kann daher effizient den Wert für einen gegebenen Schlüssel nachschlagen. Die Verantwortung für die Pflege der Schlüssel-Wert-Beziehung teilen sich die Knoten. Dies geschieht so, dass bei einer Änderung bei einem der Teilnehmer nur minimale Störungen auftreten. Dadurch wird sichergestellt, dass DHT auf eine sehr große Anzahl von Knoten skaliert und kontinuierlich neue, abgehende und ausgefallene Knoten verarbeiten kann.

DHTs sind eine Infrastruktur, mit der komplexe Dienste wie verteilte Dateisysteme und Peer-to-Peer-Dateifreigabe, kooperatives Web-Caching, Multicast, DNS und Instant Messaging bereitgestellt werden können. Bekannte verteilte Netzwerke, die DHT verwenden, umfassen BitTorrent, es Kad-Netzwerk, das Storm-Botnetz, YaCy und das Coral Content Distribution Network.

Eigenschaften

DHTs betonen die folgenden Eigenschaften:

• Dezentralisierung: Die Knoten bilden zusammen das System ohne jegliche zentrale Koordination.
• Skalierbarkeit: Das System sollte auch mit Tausenden oder Millionen von Knoten effizient funktionieren.
• Fehlertoleranz: Das System sollte zuverlässig sein, auch wenn Knoten kontinuierlich eintreten, austreten oder ausfallen.

Die Haupttechnik zum Erreichen dieser Ziele besteht darin, dass sich einer der Knoten koordinieren muss, normalerweise mit einer begrenzten Anzahl anderer – oft sind dies O(log nein) des nein Teilnehmer – so dass bei jedem Teilnehmerwechsel nur ein begrenzter Arbeitsaufwand anfällt.

Einige DHT-Designs versuchen, gegen Teilnehmer mit bösen Absichten vorzugehen und es den Teilnehmern zu ermöglichen, anonym zu bleiben, obwohl dies weniger üblich ist als bei anderen Peer-to-Peer-Systemen (für die gemeinsame Nutzung von Dateien).

DHT muss noch mehr Probleme traditioneller verteilter Systeme lösen, wie beispielsweise Lastverteilung, Datenintegrität und Leistungsprobleme (insbesondere die Gewährleistung einer schnellen Abwicklung von Vorgängen wie Routing und Datenspeicherung).

Struktur

Die Struktur von DHT kann in mehrere Hauptteile unterteilt werden. Die Grundlage ist eine Zusammenfassung Schlüsselraum, zum Beispiel ein Satz von 160-Bit-Strings. EIN Schlüsselraum-Partitionierungsschema teilt den Besitz dieses Schlüsselraums unter den teilnehmenden Knoten auf. Ein Overlay-Netzwerk, das die Knoten verbindet, ermöglicht es ihnen, den Besitzer eines bestimmten Schlüssels im Schlüsselspeicher zu finden.

Sobald alle diese Komponenten vorhanden sind, sieht ein typisches Speicher- und Lookup-DHT-Nutzungsszenario wie folgt aus. Angenommen, der Keystore ist ein Satz von 160-Bit-Strings. So öffnen Sie eine Datei mit Daten Dateiname und Termine in DHT gespeichert werden, die sha-1hash des Dateiname generiert, das ist ein 160-Bit-Schlüssel k produziert und eine Nachricht wird gesendet put(k,Daten) an einen Knoten des DHT gesendet. Die Nachricht wird dann von Knoten zu Knoten über das Overlay-Netzwerk gesendet, bis sie den einen Knoten erreicht, der für den Schlüssel verantwortlich ist k wie durch die Schlüsselraumpartitionierung angegeben. Dieser Knoten speichert dann den Schlüssel und die Daten. Ein anderer Client kann dann den Inhalt der Datei abrufen, indem er de Dateiname Hash, um k zu generieren und einen anderen DHT-Knoten zu bitten, die mit k durch eine Nachricht verknüpften Daten zu finden bekommen (k). Die Nachricht wird über das Overlay-Netzwerk an den Knoten weitergeleitet, der für . verantwortlich ist k, die ihrerseits mit den gespeicherten Daten antwortet.

DHT-Implementierungen

Die Hauptunterschiede zwischen den verschiedenen praktischen DHT-Implementierungen sind die folgenden:

• Der Adressraum ist ein Parameter von DHT. Mehrere DHTs verwenden 128-Bit- oder 160-Bit-Speicherplatz.
• Einige DHTs verwenden andere Hashfunktionen als SHA1.
• In der realen Welt wäre der Schlüssel k a hash des Inhalts der Datei statt des Dateinamens. Auf diese Weise kann die Datei auch bei einer Änderung des Dateinamens gefunden werden.
• Einige DHTs können auch andere Objekttypen veröffentlichen. Ein Schlüssel k könnte beispielsweise eine Knoten-ID sein und die zugehörigen Daten könnten beschreiben, wie dieser Knoten zu kontaktieren ist. Dies ermöglicht die Veröffentlichung von Informationen über die Anwesenheit, wie sie häufig in IM-Anwendungen.
• Redundanz kann hinzugefügt werden, um die Zuverlässigkeit zu verbessern. Das (k,data)-Schlüsselpaar kann in mehr als einem Knoten gespeichert werden. Normalerweise werden anstelle eines Knotens i geeignete Knoten ausgewählt, wobei i ein implementierungsspezifischer von DHT ist.

Einige fortgeschrittene DHTs führen zuerst iterative Suchen durch das DHT durch, um einen Satz geeigneter Knoten auszuwählen, und senden dann put(k,data)-Nachrichten nur an diese Knoten. Somit wird der nutzlose Verkehr erheblich reduziert, da die veröffentlichten Nachrichten nur an die Knoten gesendet werden, die geeignet erscheinen, den Schlüssel k zu speichern.