www.wikidata.de-de.nina.az

Verteilte Hashtabelle Eine verteilte Hashtabelle englisch distributed hash table DHT ist eine Datenstruktur die zum Beis

Verteilte Hashtabelle

Eine verteilte Hashtabelle (englisch 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 (< 1 kB) an, da sonst das System zu unflexibel werden würde.

Eigenschaften Bearbeiten

Eigenschaften von DHTs sind:

  • Fehlertoleranz: Das System sollte zuverlässig funktionieren, auch wenn Knoten ausfallen oder das System verlassen.
  • Lastenverteilung: Schlüssel werden gleichmäßig auf alle Knoten verteilt.
  • 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.
  • 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.

Prinzipielle Arbeitsweise Bearbeiten

Mittels einer Hashfunktion werden den Datenobjekten Schlüssel in einem linearen Wertebereich vergeben, welcher möglichst gleichmäßig über die Knoten der Knotenmenge verteilt wird. Für jeden Teilbereich des Schlüsselraumes ist dabei mindestens ein Knoten 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 physischen 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.

Partitionierung des Schlüsselraums Bearbeiten

Bei den meisten DHTs geschieht die Abbildung von Schlüsseln auf Knoten mittels einer Variante von konsistentem Hashing oder Rendezvouz-Hashing. Diese beiden Varianten wurden wohl gleichzeitig, aber unabhängig entwickelt, um das DHT-Problem zu lösen.

Sowohl konsistentes Hashing als auch Rendezvouz-Hashing haben die grundlegende Eigenschaft, dass sich bei Beitritt oder Austritt eines Knotens nur die Schlüssel der benachbarten Knoten ändern und alle anderen Knoten nicht beeinträchtigt werden. In konventionellen Hashtabellen hingegen wird bei hinzufügen oder entfernen eines Buckets fast der vollständige Schlüsselbereich neu verteilt. Wenn sich die Zuständigkeit von Datenobjekten ändert, ist eine Daten-Umverteilung notwendig. Diese belastet das Netzwerk und die Datenbandbreite. Deshalb werden DHTs so gestaltet, dass sie auch häufige Ein- und Austritte von Knoten effizient unterstützen können.

Konsistentes Hashing Bearbeiten

Beim konsistenten Hashing wird eine Distanzfunktion verwendet. Diese gibt die Distanz zwischen zwei Schlüsseln und an. Die Distanz ist dabei unabhängig von der geographischen Distanz oder der Latenz im Netzwerk. Außerdem erhält jeder Knoten des Netzwerks einen Schlüssel, welchen wir seinen Identifikator (ID von Knoten ) nennen. Jeder Knoten ist dann für die Speicherung derer Elemente zuständig, deren Distanz zu seiner ID am geringsten ist: .

Beispielsweise setzt Chord konsistentes Hashing ein, wobei die Knoten als Punkte auf einem Kreis und als der Kreisbogen von  nach im Uhrzeigersinn aufgefasst werden. Der kreisförmige Schlüsselraum besteht also aus zusammenhängenden Segmenten, deren Endpunkte die Knoten-IDs sind. Wenn also zum Beispiel und zwei im Kreis aufeinander folgende Knoten-IDs sind, dann ist der Knoten für alle Schlüssel zwischen und zuständig.

Rendezvous-Hashing Bearbeiten

Beim Rendezvouz-Hashing benutzen alle Clients, welche einen Schlüssel auf einen der Knoten abbilden wollen, die gleiche, zu Beginn gewählte Hashfunktion . Außerdem haben alle Clients die gleiche Liste von IDs , eine für jeden Knoten. Um den richtigen Knoten für einen Schlüssel zu bestimmen, werden zunächst Hash-Gewichte berechnet. Der Schlüssel wird dann mit dem dem Maximum dieser Werte entsprechenden Knoten assoziiert. Ein Knoten mit ID ist also für alle Schlüssel zuständig, deren Hash-Gewicht höher als die Hash-Gewichte aller anderen Knoten für den Schlüssel ist.

Lokalitätserhaltendes Hashing Bearbeiten

Lokalitätserhaltendes Hashing stellt sicher, dass ähnliche Schlüssel auch ähnlichen Knoten zugeteilt werden. Dadurch können effizientere Range Queries ermöglicht werden. Dabei kann es allerdings vorkommen, dass die Verteilung des Schlüsselraums auf die Knoten und damit deren Auslastung nicht mehr uniform zufällig ist. Das Framework Self-Chord zum Beispiel macht Objektschlüssel von Knoten-IDs unabhängig und sortiert Schlüssel entlang eines Ringspeichers mit Hilfe eines statistischen Ansatzes, der auf dem Schwarmintelligenz-Paradigma beruht. Das Sortieren stellt sicher, dass benachbarte Knoten für ähnliche Schlüssel zuständig sind und Abfragen wie z. B. Range Queries so in logarithmischer Zeit ausgeführt werden können.

Overlay-Netz Bearbeiten

Das Overlay-Netz verbindet die Knoten, sodass diese den jeweiligen zuständigen Knoten für Schlüssel finden können. Dabei hält jeder Knoten in einer Routingtabelle Verbindungen zu anderen Knoten (seinen Nachbarn). Ein Knoten wählt seine Nachbarn entsprechend der Netzwerktopologie (Struktur des Netzwerks).

Alle DHT-Topologien verbindet eine grundlegende Eigenschaft: für jeden Schlüssel weiß jeder Knoten entweder die ID des Knotens, der für zuständig ist, oder er hat einen Link zu einem Knoten, dessen ID näher an ist, definiert durch ein Distanzmaß in Abschnitt Partitionierung des Schlüsselraums. Eine Nachricht kann dann einfach an den zuständigen Knoten von geroutet werden: Bei jedem Schritt wird die Nachricht an denjenigen Knoten weitergeleitet, dessen ID am nächsten ist, bis der zuständige Knoten erreicht wird. Dieser Algorithmus ist im Allgemeinen nicht global optimal. Manchmal wird dieses Verfahren Schlüssel-basiertes Routing genannt.

Das Overlay-Netz hat zwei Parameter, welche einen großen Einfluss auf seine Leistung haben. Die maximale Routenlänge sollte klein sein, damit Pakete schnell ankommen, und der maximale Knotengrad sollte klein sein, damit der Overhead pro besuchtem Knoten klein ist. Dabei stehen die beiden Parameter in einem Tradeoff-Verhältnis. Einige typische Verhältnisse sind in der folgenden Tabelle beschrieben.

Max. Knotengrad Max. Routenlänge Benutzt in Bemerkung
Schlechtestmögliche Routenlänge, Anfragen werden sehr langsam
Chord
Kademlia
Pastry
Tapestry		 Am verbreitetsten aber nicht optimal (Nachbargrad/Routenlänge-Verhältnis). Chord ist die einfachste Version, Kademlia scheint die beliebteste optimierte Variante zu sein (sollte verbesserte durschn. Zeit für Anfragen haben)
Koorde

Wohl komplexere Implementierung aber Anfragen können schneller sein (niedrigere Worst-Case-Schranke)

Höchste lokale Speicherplatzanforderungen, hohe Kommunikationslast nach Beitritt und Austritt eines Knotens

als maximaler Nachbargrad und maximale Routenlänge ist die am weitesten verbreitete Parametrisierung. Obwohl der Nachbargrad/Routenlänge-Tradeoff bei ihr nicht optimal ist, ermöglicht sie oft eine höhere Flexibilität bei der Wahl der Nachbarn. Viele DHTs nutzen diese Flexibilität, um Nachbarn mit möglichst geringer Latenz im darunterliegenden physikalischen Netzwerk auszuwählen. Im Allgemeinen erstellen DHTs navigierbare kleine-Welt-Netzwerk-Topologien mit dem Tradeoff zwischen Routenlänge und Netzwerkgrad.

Die maximale Routenlänge ist eng verwandt mit dem Durchmesser (des Netzwerks): der maximalen Anzahl Hops in einem beliebigen kürzesten Pfad zwischen zwei Knoten. Die Worst-Case-Routenlänge des Netzwerks ist offensichtlich mindestens so groß wie der Durchmesser, folglich haben DHTs die in der Graphentheorie fundamentale Limitierung des Knotengrad/Durchmesser-Tradeoffs. Die Routenlänge kann auch größer als der Durchmesser sein, da der greedy Routingalgorithmus kürzeste Pfade eventuell nicht findet.

Algorithmen für Overlay-Netze Bearbeiten

Neben Routing gibt es viele Algorithmen, welche die Struktur von Overlay-Netzen in DHTs ausnutzen, um Nachrichten an alle Knoten oder eine Teilmenge zu senden. Diese Algorithmen werden von Anwendungen für Overlay-Multicasts, Range Queries oder zum Sammeln von Statistiken eingesetzt. Zwei auf diesem Ansatz basierende Systeme sind Structella, das Flooding und Random Walks auf einem Pastry-Overlay implementiert, sowie DQ-DHT, das einen dynamischen Query-Suchalgorithmus über einem Chord-Netzwerk implementiert.

Implementierungen Bearbeiten

Auf vielen Rechnern ist das Senden von Nachrichten deutlich teurer als lokale Hashtabellen-Zugriffe. Deshalb ist eine Bündelung vieler Nachrichten in einen Batch sinnvoll. Die Nachrichten werden unter der Annahme, dass jeder Knoten einen lokalen Batch von maximal Nachrichten hat, wie folgt gebündelt. Jeder Knoten sortiert seinen lokalen Batch zunächst nach der ID des für die Nachricht zuständigen Knotens. Dies ist in Zeit mit Bucketsort möglich, wobei die Knotenanzahl in der DHT ist. Falls es in einem Batch mehrere Operationen für denselben Key gibt, wird der Batch noch vor dem Senden reduziert. Zum Beispiel können mehrere Anfragen für denselben Key zu einer reduziert werden oder mehrere inkrement-Operationen zu einer add-Operation. Dies kann mit einer lokalen Hashtable realisiert werden. Schließlich werden die Operationen an die jeweiligen Knoten geschickt.

Derzeit existieren unter anderem folgende Implementierungen verteilter Hashtabellen:

  • IPFS
  • Kademlia – Strukturen basierend auf diesem Algorithmus existieren in mehreren P2P-Netzwerken, sind allerdings meist nicht untereinander kompatibel. Implementierungen:
    • 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 Bearbeiten

DHTs zur Datenspeicherung Bearbeiten

Software Bearbeiten

DHT-Forschung Bearbeiten

  • @1@2Vorlage:Toter Link/iris.csail.mit.eduProject IRIS (Seite nicht mehr abrufbar, festgestellt im November 2017. Suche in Webarchiven.) (Infrastructure for Resilient Internet Systems)

Einzelnachweise Bearbeiten

  1. Agostino Forestiero, Emilio Leonardi, Carlo Mastroianni, Michela Meo: Self-Chord: A Bio-Inspired P2P Framework for Self-Organizing Distributed Systems. In: IEEE/ACM Transactions on Networking. 18. Jahrgang, Nr. 5, Oktober 2010, S. 1651–1664, doi:10.1109/TNET.2010.2046745 (polito.it).
  2. Sarunas Girdzijauskas: Designing peer-to-peer overlays a small-world perspective. EPFL, 2009 (epfl.ch).
  3. Maite71.upc.es, archiviert vom Original am 17. Februar 2012; abgerufen am 10. Januar 2012.
  4. Gurmeet Singh Manku, Moni Naor, Udi Wieder: "Know thy Neighbor's Neighbor: the Power of Lookahead in Randomized P2P Networks". Proc. STOC, 2004.
  5. Ali Ghodsi: (Memento vom 22. Mai 2007 im Internet Archive). KTH – Royal Institute of Technology, 2006.
  6. Miguel Castro, Manuel Costa, Antony Rowstron: Should we build Gnutella on a structured overlay? In: ACM SIGCOMM Computer Communication Review. 34. Jahrgang, Nr. 1, 1. Januar 2004, S. 131, doi:10.1145/972374.972397 (mit.edu [PDF]).
  7. Domenico Talia, Paolo Trunfio: Enabling Dynamic Querying over Distributed Hash Tables. In: Journal of Parallel and Distributed Computing. 70. Jahrgang, Nr. 12, Dezember 2010, S. 1254–1265, doi:10.1016/j.jpdc.2010.08.012.
  8. Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger, Roman Dementiev: Sequential and Parallel Algorithms and Data Structures. Springer, S. 135 f.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Eine verteilte Hashtabelle englisch 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 moglichst gleichmassig uber 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 fur verteilte Hashtabellen bilden konsistente Hash Funktionen Man unterscheidet DHTs nach dem Speicherschema Die Daten konnen 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 fur kleine Daten lt 1 kB an da sonst das System zu unflexibel werden wurde Inhaltsverzeichnis 1 Eigenschaften 2 Prinzipielle Arbeitsweise 3 Partitionierung des Schlusselraums 3 1 Konsistentes Hashing 3 2 Rendezvous Hashing 3 3 Lokalitatserhaltendes Hashing 4 Overlay Netz 4 1 Algorithmen fur Overlay Netze 5 Implementierungen 6 Anwendungen 6 1 DHTs zur Datenspeicherung 6 2 Software 6 3 DHT Forschung 7 EinzelnachweiseEigenschaften BearbeitenEigenschaften von DHTs sind Fehlertoleranz Das System sollte zuverlassig funktionieren auch wenn Knoten ausfallen oder das System verlassen Lastenverteilung Schlussel werden gleichmassig auf alle Knoten verteilt Robustheit Das System sollte korrekt funktionieren konnen auch wenn ein Teil moglicherweise ein Grossteil der Knoten versucht das System zu storen Selbstorganisation Es ist keine manuelle Konfiguration notig Skalierbarkeit Das System sollte in der Lage sein auch mit einer grossen Anzahl von Knoten funktionsfahig zu bleiben Prinzipielle Arbeitsweise BearbeitenMittels einer Hashfunktion werden den Datenobjekten Schlussel in einem linearen Wertebereich vergeben welcher moglichst gleichmassig uber die Knoten der Knotenmenge verteilt wird Fur jeden Teilbereich des Schlusselraumes ist dabei mindestens ein Knoten zustandig Oft sind jedoch auch mehrere Knoten fur denselben Bereich verantwortlich wobei sich die Zustandigkeiten dynamisch andern Ein Beitrittsprotokoll regelt die Aufnahme neuer Knoten in das existierende System Das Protokoll stellt dann die Verbindungen zu den Nachbarknoten her und regelt ublicherweise auch die Konstruktion von Routingtabellen Die Routingtabellen werden von den DHT Knoten zur Ermittlung anderer Knoten benutzt die fur bestimmte Datensatze zustandig 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 physischen Organisation der Knoten ubereinstimmen Eine verteilte Hashtabelle die ihre Knoten in einem euklidischen Raum platziert konnte den Knoten mit dem geringsten euklidischen Abstand zu einem Schlussel wahlen Die Routingtabellen sollen es jedem Knoten erlauben den nachsten Knoten zu einem Schlussel in O log n Suchschritten zu erreichen Durch eine generische Schnittstelle die nur zwei Funktionen publish Schlussel Inhalt und lookup Schlussel anbietet lassen sich die implementierten Algorithmen auswechseln Partitionierung des Schlusselraums BearbeitenBei den meisten DHTs geschieht die Abbildung von Schlusseln auf Knoten mittels einer Variante von konsistentem Hashing oder Rendezvouz Hashing Diese beiden Varianten wurden wohl gleichzeitig aber unabhangig entwickelt um das DHT Problem zu losen Sowohl konsistentes Hashing als auch Rendezvouz Hashing haben die grundlegende Eigenschaft dass sich bei Beitritt oder Austritt eines Knotens nur die Schlussel der benachbarten Knoten andern und alle anderen Knoten nicht beeintrachtigt werden In konventionellen Hashtabellen hingegen wird bei hinzufugen oder entfernen eines Buckets fast der vollstandige Schlusselbereich neu verteilt Wenn sich die Zustandigkeit von Datenobjekten andert ist eine Daten Umverteilung notwendig Diese belastet das Netzwerk und die Datenbandbreite Deshalb werden DHTs so gestaltet dass sie auch haufige Ein und Austritte von Knoten effizient unterstutzen konnen Konsistentes Hashing Bearbeiten Beim konsistenten Hashing wird eine Distanzfunktion d k 1 k 2 displaystyle delta k 1 k 2 nbsp verwendet Diese gibt die Distanz zwischen zwei Schlusseln k 1 displaystyle k 1 nbsp und k 2 displaystyle k 2 nbsp an Die Distanz ist dabei unabhangig von der geographischen Distanz oder der Latenz im Netzwerk Ausserdem erhalt jeder Knoten x displaystyle x nbsp des Netzwerks einen Schlussel welchen wir seinen Identifikator i x displaystyle i x nbsp ID von Knoten x displaystyle x nbsp nennen Jeder Knoten ist dann fur die Speicherung derer Elemente zustandig deren Distanz zu seiner ID am geringsten ist x argmin y d k i y displaystyle x operatorname argmin y delta k i y nbsp Beispielsweise setzt Chord konsistentes Hashing ein wobei die Knoten als Punkte auf einem Kreis und d k 1 k 2 displaystyle delta k 1 k 2 nbsp als der Kreisbogen von k 1 displaystyle k 1 nbsp nach k 2 displaystyle k 2 nbsp im Uhrzeigersinn aufgefasst werden Der kreisformige Schlusselraum besteht also aus zusammenhangenden Segmenten deren Endpunkte die Knoten IDs sind Wenn also zum Beispiel i 1 displaystyle i 1 nbsp und i 2 displaystyle i 2 nbsp zwei im Kreis aufeinander folgende Knoten IDs sind dann ist der Knoten i 1 displaystyle i 1 nbsp fur alle Schlussel zwischen i 1 displaystyle i 1 nbsp und i 2 displaystyle i 2 nbsp zustandig Rendezvous Hashing Bearbeiten Beim Rendezvouz Hashing benutzen alle Clients welche einen Schlussel auf einen der n displaystyle n nbsp Knoten abbilden wollen die gleiche zu Beginn gewahlte Hashfunktion h displaystyle h nbsp Ausserdem haben alle Clients die gleiche Liste von IDs S 1 S 2 S n displaystyle S 1 S 2 S n nbsp eine fur jeden Knoten Um den richtigen Knoten fur einen Schlussel k displaystyle k nbsp zu bestimmen werden zunachst n displaystyle n nbsp Hash Gewichte w 1 h S 1 k w 2 h S 2 k w n h S n k displaystyle w 1 h S 1 k w 2 h S 2 k w n h S n k nbsp berechnet Der Schlussel wird dann mit dem dem Maximum dieser Werte entsprechenden Knoten assoziiert Ein Knoten mit ID S x displaystyle S x nbsp ist also fur alle Schlussel k m displaystyle k m nbsp zustandig deren Hash Gewicht h S x k m displaystyle h S x k m nbsp hoher als die Hash Gewichte aller anderen Knoten fur den Schlussel ist Lokalitatserhaltendes Hashing Bearbeiten Lokalitatserhaltendes Hashing stellt sicher dass ahnliche Schlussel auch ahnlichen Knoten zugeteilt werden Dadurch konnen effizientere Range Queries ermoglicht werden Dabei kann es allerdings vorkommen dass die Verteilung des Schlusselraums auf die Knoten und damit deren Auslastung nicht mehr uniform zufallig ist Das Framework Self Chord zum Beispiel macht Objektschlussel von Knoten IDs unabhangig und sortiert Schlussel entlang eines Ringspeichers mit Hilfe eines statistischen Ansatzes der auf dem Schwarmintelligenz Paradigma beruht 1 Das Sortieren stellt sicher dass benachbarte Knoten fur ahnliche Schlussel zustandig sind und Abfragen wie z B Range Queries so in logarithmischer Zeit ausgefuhrt werden konnen Overlay Netz BearbeitenDas Overlay Netz verbindet die Knoten sodass diese den jeweiligen zustandigen Knoten fur Schlussel finden konnen Dabei halt jeder Knoten in einer Routingtabelle Verbindungen zu anderen Knoten seinen Nachbarn Ein Knoten wahlt seine Nachbarn entsprechend der Netzwerktopologie Struktur des Netzwerks Alle DHT Topologien verbindet eine grundlegende Eigenschaft fur jeden Schlussel k displaystyle k nbsp weiss jeder Knoten entweder die ID des Knotens der fur k displaystyle k nbsp zustandig ist oder er hat einen Link zu einem Knoten dessen ID naher an k displaystyle k nbsp ist definiert durch ein Distanzmass in Abschnitt Partitionierung des Schlusselraums Eine Nachricht kann dann einfach an den zustandigen Knoten von k displaystyle k nbsp geroutet werden Bei jedem Schritt wird die Nachricht an denjenigen Knoten weitergeleitet dessen ID k displaystyle k nbsp am nachsten ist bis der zustandige Knoten erreicht wird Dieser Algorithmus ist im Allgemeinen nicht global optimal Manchmal wird dieses Verfahren Schlussel basiertes Routing genannt Das Overlay Netz hat zwei Parameter welche einen grossen Einfluss auf seine Leistung haben Die maximale Routenlange sollte klein sein damit Pakete schnell ankommen und der maximale Knotengrad sollte klein sein damit der Overhead pro besuchtem Knoten klein ist Dabei stehen die beiden Parameter in einem Tradeoff Verhaltnis Einige typische Verhaltnisse sind in der folgenden Tabelle beschrieben Max Knotengrad Max Routenlange Benutzt in BemerkungO 1 displaystyle O 1 nbsp O n displaystyle O n nbsp Schlechtestmogliche Routenlange Anfragen werden sehr langsamO log n displaystyle O log n nbsp O log n displaystyle O log n nbsp Chord Kademlia Pastry Tapestry Am verbreitetsten aber nicht optimal Nachbargrad Routenlange Verhaltnis Chord ist die einfachste Version Kademlia scheint die beliebteste optimierte Variante zu sein sollte verbesserte durschn Zeit fur Anfragen haben O log n displaystyle O log n nbsp O log n log log n displaystyle O log n log log n nbsp Koorde Wohl komplexere Implementierung aber Anfragen konnen schneller sein niedrigere Worst Case Schranke O n displaystyle O sqrt n nbsp O 1 displaystyle O 1 nbsp Hochste lokale Speicherplatzanforderungen hohe Kommunikationslast nach Beitritt und Austritt eines KnotensO log n displaystyle O log n nbsp als maximaler Nachbargrad und maximale Routenlange ist die am weitesten verbreitete Parametrisierung Obwohl der Nachbargrad Routenlange Tradeoff bei ihr nicht optimal ist ermoglicht sie oft eine hohere Flexibilitat bei der Wahl der Nachbarn Viele DHTs nutzen diese Flexibilitat um Nachbarn mit moglichst geringer Latenz im darunterliegenden physikalischen Netzwerk auszuwahlen Im Allgemeinen erstellen DHTs navigierbare kleine Welt Netzwerk Topologien mit dem Tradeoff zwischen Routenlange und Netzwerkgrad 2 Die maximale Routenlange ist eng verwandt mit dem Durchmesser des Netzwerks der maximalen Anzahl Hops in einem beliebigen kurzesten Pfad zwischen zwei Knoten Die Worst Case Routenlange des Netzwerks ist offensichtlich mindestens so gross wie der Durchmesser folglich haben DHTs die in der Graphentheorie fundamentale Limitierung des Knotengrad Durchmesser Tradeoffs 3 Die Routenlange kann auch grosser als der Durchmesser sein da der greedy Routingalgorithmus kurzeste Pfade eventuell nicht findet 4 Algorithmen fur Overlay Netze Bearbeiten Neben Routing gibt es viele Algorithmen welche die Struktur von Overlay Netzen in DHTs ausnutzen um Nachrichten an alle Knoten oder eine Teilmenge zu senden 5 Diese Algorithmen werden von Anwendungen fur Overlay Multicasts Range Queries oder zum Sammeln von Statistiken eingesetzt Zwei auf diesem Ansatz basierende Systeme sind Structella 6 das Flooding und Random Walks auf einem Pastry Overlay implementiert sowie DQ DHT das einen dynamischen Query Suchalgorithmus uber einem Chord Netzwerk implementiert 7 Implementierungen BearbeitenAuf vielen Rechnern ist das Senden von Nachrichten deutlich teurer als lokale Hashtabellen Zugriffe Deshalb ist eine Bundelung vieler Nachrichten in einen Batch sinnvoll Die Nachrichten werden unter der Annahme dass jeder Knoten einen lokalen Batch von maximal b displaystyle b nbsp Nachrichten hat wie folgt gebundelt Jeder Knoten sortiert seinen lokalen Batch zunachst nach der ID des fur die Nachricht zustandigen Knotens Dies ist in O b n displaystyle O b n nbsp Zeit mit Bucketsort moglich wobei n displaystyle n nbsp die Knotenanzahl in der DHT ist Falls es in einem Batch mehrere Operationen fur denselben Key gibt wird der Batch noch vor dem Senden reduziert Zum Beispiel konnen mehrere Anfragen fur denselben Key zu einer reduziert werden oder mehrere inkrement Operationen zu einer add Operation Dies kann mit einer lokalen Hashtable realisiert werden Schliesslich werden die Operationen an die jeweiligen Knoten geschickt 8 Derzeit existieren unter anderem folgende Implementierungen verteilter Hashtabellen IPFS Kademlia Strukturen basierend auf diesem Algorithmus existieren in mehreren P2P Netzwerken sind allerdings meist nicht untereinander kompatibel Implementierungen 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 BearbeitenDHTs zur Datenspeicherung Bearbeiten OpenDHT Bamboo The Chord DHash Project FreePastry TomP2PSoftware Bearbeiten apt p2p Paketverwaltungssystem Verteiltes Update auf Basis von apt Vuze BitTorrent Client BitComet BitTorrent Client BitTorrent ab Version 4 1 0 Coral Verteilungsnetzwerk fur Inhalte CSpace Instant Messenger mit Kademlia 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 µTorrent BitTorrent Client qBittorrent BitTorrent Client RetroShare serverloser Instant Messenger anonymes Filesharing Newsgroup Voice over IP E Mail rTorrent BitTorrent Client Tox Instant Messenger Transmission Software BitTorrent Client YaCy verteilte SuchmaschineDHT Forschung Bearbeiten 1 2 Vorlage Toter Link iris csail mit edu Project IRIS Seite nicht mehr abrufbar festgestellt im November 2017 Suche in Webarchiven Infrastructure for Resilient Internet Systems Einzelnachweise Bearbeiten Agostino Forestiero Emilio Leonardi Carlo Mastroianni Michela Meo Self Chord A Bio Inspired P2P Framework for Self Organizing Distributed Systems In IEEE ACM Transactions on Networking 18 Jahrgang Nr 5 Oktober 2010 S 1651 1664 doi 10 1109 TNET 2010 2046745 polito it Sarunas Girdzijauskas Designing peer to peer overlays a small world perspective EPFL 2009 epfl ch The Degree Diameter Problem for Graphs Maite71 upc es archiviert vom Original am 17 Februar 2012 abgerufen am 10 Januar 2012 Gurmeet Singh Manku Moni Naor Udi Wieder Know thy Neighbor s Neighbor the Power of Lookahead in Randomized P2P Networks Proc STOC 2004 Ali Ghodsi Distributed k ary System Algorithms for Distributed Hash Tables Memento vom 22 Mai 2007 im Internet Archive KTH Royal Institute of Technology 2006 Miguel Castro Manuel Costa Antony Rowstron Should we build Gnutella on a structured overlay In ACM SIGCOMM Computer Communication Review 34 Jahrgang Nr 1 1 Januar 2004 S 131 doi 10 1145 972374 972397 mit edu PDF Domenico Talia Paolo Trunfio Enabling Dynamic Querying over Distributed Hash Tables In Journal of Parallel and Distributed Computing 70 Jahrgang Nr 12 Dezember 2010 S 1254 1265 doi 10 1016 j jpdc 2010 08 012 Peter Sanders Kurt Mehlhorn Martin Dietzfelbinger Roman Dementiev Sequential and Parallel Algorithms and Data Structures Springer S 135 f Abgerufen von https de wikipedia org w index php title Verteilte Hashtabelle amp oldid 238040692