Verteilte Hash-Tabelle - Distributed hash table

Eine verteilte Hash-Tabelle ( DHT ) ist ein verteiltes System , das einen Suchdienst ähnlich einer Hash-Tabelle bereitstellt : Schlüssel-Wert-Paare werden in einem DHT gespeichert, und jeder teilnehmende Knoten kann den mit einem bestimmten Schlüssel verknüpften Wert effizient abrufen . Der Hauptvorteil eines DHT besteht darin, dass Knoten mit minimalem Aufwand für die Neuverteilung von Schlüsseln hinzugefügt oder entfernt werden können. Schlüssel sind eindeutige Bezeichner, die bestimmten Werten zugeordnet sind , die wiederum alles sein können, von Adressen über Dokumente bis hin zu beliebigen Daten . Die Verantwortung für die Aufrechterhaltung der Zuordnung von Schlüsseln zu Werten wird so auf die Knoten verteilt, dass eine Änderung des Teilnehmerkreises eine minimale Störung verursacht. Dies ermöglicht es einem DHT, auf eine extrem große Anzahl von Knoten zu skalieren und kontinuierliche Knotenankünfte, -abgänge und -ausfälle zu verarbeiten.

DHTs bilden eine Infrastruktur, die verwendet werden kann, um komplexere Dienste wie Anycast , kooperatives Web-Caching , verteilte Dateisysteme , Domain-Name-Dienste , Instant Messaging , Multicast und auch Peer-to-Peer-Dateifreigabe- und Inhaltsverteilungssysteme aufzubauen. Zu den bemerkenswerten verteilten Netzwerken, die DHTs verwenden, gehören der verteilte Tracker von BitTorrent , das Coral Content Distribution Network , das Kad-Netzwerk , das Storm-Botnet , der Tox Instant Messenger , Freenet , die YaCy- Suchmaschine und das InterPlanetary File System .

Geschichte

Die DHT-Forschung wurde ursprünglich zum Teil durch Peer-to-Peer (P2P)-Systeme wie Freenet , Gnutella , BitTorrent und Napster motiviert, die über das Internet verteilte Ressourcen nutzten, um eine einzige nützliche Anwendung bereitzustellen. Insbesondere nutzten sie die erhöhte Bandbreite und Festplattenkapazität , um einen File-Sharing-Dienst bereitzustellen.

Diese Systeme unterschieden sich darin, wie sie die von ihren Kollegen angebotenen Daten lokalisierten. Napster, das erste groß angelegte P2P-Content-Delivery-System, benötigte einen zentralen Indexserver: Jeder Knoten sendete beim Beitritt eine Liste der lokal gespeicherten Dateien an den Server, der Suchen durchführte und die Abfragen an die Knoten weiterleitete, die die Ergebnisse. Diese zentrale Komponente machte das System anfällig für Angriffe und Klagen.

Gnutella und ähnliche Netzwerke wechselten zu einem Query-Flooding- Modell – im Wesentlichen würde jede Suche dazu führen, dass eine Nachricht an jede andere Maschine im Netzwerk gesendet wird. Obwohl ein Single Point of Failure vermieden wurde , war diese Methode deutlich weniger effizient als Napster. Spätere Versionen von Gnutella-Clients wechselten zu einem dynamischen Abfragemodell , das die Effizienz erheblich verbesserte.

Freenet ist vollständig verteilt, verwendet jedoch ein heuristisches schlüsselbasiertes Routing, bei dem jede Datei einem Schlüssel zugeordnet ist und Dateien mit ähnlichen Schlüsseln dazu neigen, sich auf einer ähnlichen Gruppe von Knoten zu gruppieren. Anfragen werden wahrscheinlich über das Netzwerk zu einem solchen Cluster geleitet, ohne dass viele Peers besucht werden müssen. Freenet garantiert jedoch nicht, dass Daten gefunden werden.

Verteilte Hash-Tabellen verwenden ein strukturierteres schlüsselbasiertes Routing, um sowohl die Dezentralisierung von Freenet und Gnutella als auch die Effizienz und garantierten Ergebnisse von Napster zu erreichen. Ein Nachteil besteht darin, dass DHTs, wie Freenet, nur die Suche nach exakter Übereinstimmung und nicht die Suche nach Schlüsselwörtern direkt unterstützen, obwohl der Routing-Algorithmus von Freenet auf jeden Schlüsseltyp verallgemeinert werden kann, bei dem eine Näherungsoperation definiert werden kann.

Im Jahr 2001 entzündeten vier Systeme – CAN , Chord , Pastry und Tapestry – DHTs als beliebtes Forschungsthema. Ein Projekt namens Infrastructure for Resilient Internet Systems (Iris) wurde 2002 mit einem Zuschuss von 12 Millionen US-Dollar von der United States National Science Foundation finanziert . Zu den Forschern gehörten Sylvia Ratnasamy , Ion Stoica , Hari Balakrishnan und Scott Shenker . Außerhalb der akademischen Welt wurde die DHT-Technologie als Bestandteil von BitTorrent und im Coral Content Distribution Network übernommen .

Eigenschaften

DHTs betonen charakteristischerweise die folgenden Eigenschaften:

• Autonomie und Dezentralisierung : Die Knoten bilden gemeinsam das System ohne zentrale Koordination.
• Fehlertoleranz : Das System sollte (in gewissem Sinne) zuverlässig sein, auch wenn Knoten ständig hinzukommen, verlassen und ausfallen.
• Skalierbarkeit : Das System sollte auch mit Tausenden oder Millionen von Knoten effizient funktionieren.

Eine Schlüsseltechnik zur Erreichung dieser Ziele besteht darin, dass sich ein Knoten nur mit wenigen anderen Knoten im System – am häufigsten O (log n ) der n Teilnehmer (siehe unten) – koordinieren muss, sodass nur eine begrenzte Anzahl von Bei jedem Mitgliedswechsel muss gearbeitet werden.

Einige DHT-Designs versuchen, vor böswilligen Teilnehmern sicher zu sein und den Teilnehmern die Möglichkeit zu geben, anonym zu bleiben , obwohl dies weniger üblich ist als bei vielen anderen Peer-to-Peer- Systemen (insbesondere File-Sharing ). siehe anonymes P2P .

Schließlich müssen sich DHTs mit eher traditionellen verteilten Systemproblemen wie Lastausgleich , Datenintegrität und Leistung befassen (insbesondere um sicherzustellen, dass Vorgänge wie Routing und Datenspeicherung oder -abruf schnell abgeschlossen werden).

Struktur

Die Struktur eines DHT kann in mehrere Hauptkomponenten zerlegt werden. Die Grundlage bildet ein abstrakter Schlüsselraum , wie beispielsweise der Satz von 160-Bit- Strings . Ein Schlüsselraum- Partitionierungsschema teilt den Besitz dieses Schlüsselraums unter den teilnehmenden Knoten auf. Ein Overlay-Netzwerk verbindet dann die Knoten und ermöglicht es ihnen, den Besitzer eines bestimmten Schlüssels im Schlüsselraum zu finden.

Sobald diese Komponenten an Ort und Stelle sind, kann eine typische Verwendung des DHT zum Speichern und Abrufen wie folgt ablaufen. Angenommen, der Schlüsselraum ist der Satz von 160-Bit-Strings. Um eine Datei mit einem gegebenen Dateinamen und Daten im DHT zu indizieren , wird der SHA-1- Hash des Dateinamens erzeugt, der einen 160-Bit-Schlüssel k erzeugt , und eine Nachricht put ( k, data ) wird an jeden Knoten gesendet, der am DHT teilnimmt. Die Nachricht wird von Knoten zu Knoten durch das Overlay-Netzwerk weitergeleitet, bis sie den einzelnen Knoten erreicht, der für den Schlüssel k verantwortlich ist, wie durch die Schlüsselraumpartitionierung spezifiziert. Dieser Knoten speichert dann den Schlüssel und die Daten. Jeder andere Client kann dann den Inhalt der Datei abrufen, indem er erneut den Dateinamen hash , um k zu erzeugen und einen beliebigen DHT-Knoten aufzufordern, die mit k assoziierten Daten mit einer Nachricht get ( k ) zu finden . Die Nachricht wird wieder durch das Overlay an den für k zuständigen Knoten geleitet , der mit den gespeicherten Daten antwortet .

Die Keyspace-Partitionierung und die Overlay-Netzwerkkomponenten werden im Folgenden mit dem Ziel beschrieben, die den meisten DHTs gemeinsamen Grundideen zu erfassen; viele Designs unterscheiden sich im Detail.

Keyspace-Partitionierung

Die meisten DHTs verwenden eine Variante von konsistentem Hashing oder Rendezvous-Hashing , um Schlüssel auf Knoten zuzuordnen. Die beiden Algorithmen scheinen unabhängig und gleichzeitig entwickelt worden zu sein, um das Problem der verteilten Hash-Tabellen zu lösen.

Sowohl konsistentes Hashing als auch Rendezvous-Hashing haben die wesentliche Eigenschaft, dass das Entfernen oder Hinzufügen eines Knotens nur den Satz von Schlüsseln ändert, der den Knoten mit benachbarten IDs besitzt, und alle anderen Knoten unberührt lässt. Vergleichen Sie dies mit einer herkömmlichen Hash-Tabelle, bei der das Hinzufügen oder Entfernen eines Buckets dazu führt, dass fast der gesamte Schlüsselraum neu zugeordnet wird. Da jeder Eigentümerwechsel typischerweise einer bandbreitenintensiven Bewegung von im DHT gespeicherten Objekten von einem Knoten zu einem anderen entspricht, ist eine Minimierung einer solchen Reorganisation erforderlich, um hohe Abwanderungsraten (Knotenankunft und -ausfall) effizient zu unterstützen .

Konsistentes Hashing

Konsistenter Hashing verwendet eine Funktion , die einen abstrakten Begriff des Abstandes zwischen den Tasten definiert und , das ist unabhängig von geographischer Entfernung oder Netzwerklatenz . Jedem Knoten wird ein einzelner Schlüssel zugewiesen, der seine Kennung (ID) genannt wird. Ein Knoten mit ID besitzt alle Schlüssel, für die die nächstgelegene ID ist, gemessen nach . ${\displaystyle \delta (k_{1},k_{2})}$${\displaystyle k_{1}}$${\displaystyle k_{2}}$${\displaystyle i_{x}}$${\displaystyle k_{m}}$${\displaystyle i_{x}}$${\displaystyle \delta (k_{m},i_{x})}$

Das Chord DHT verwendet beispielsweise konsistentes Hashing, das Knoten als Punkte auf einem Kreis behandelt und die Entfernung darstellt, die im Uhrzeigersinn von bis um den Kreis zurückgelegt wird . Somit wird der kreisförmige Schlüsselraum in zusammenhängende Segmente aufgeteilt, deren Endpunkte die Knotenkennungen sind. Wenn und zwei benachbarte IDs sind, mit einem kürzeren Abstand von bis im Uhrzeigersinn , dann besitzt der Knoten mit ID alle Schlüssel, die zwischen und liegen . ${\displaystyle \delta (k_{1},k_{2})}$${\displaystyle k_{1}}$${\displaystyle k_{2}}$${\displaystyle i_{1}}$${\displaystyle i_{2}}$${\displaystyle i_{1}}$${\displaystyle i_{2}}$${\displaystyle i_{2}}$${\displaystyle i_{1}}$${\displaystyle i_{2}}$

Rendezvous-Hashing

Beim Rendezvous-Hashing, auch HRW-Hashing (Highest Random Weight) genannt, verwenden alle Clients dieselbe Hash-Funktion (im Voraus ausgewählt), um einem der n verfügbaren Server einen Schlüssel zuzuordnen. Jeder Client hat dieselbe Liste von Identifikatoren { S ₁ , S ₂ , ..., S _n } , eine für jeden Server. Bei einem gegebenen Schlüssel k berechnet ein Client n Hash-Gewichte w ₁ = h ( S ₁ , k ), w ₂ = h ( S ₂ , k ), ..., w _n = h ( S _n , k ) . Der Client ordnet diesen Schlüssel dem Server zu, der dem höchsten Hash-Gewicht für diesen Schlüssel entspricht. Ein Server mit ID besitzt alle Schlüssel, für die das Hash-Gewicht höher ist als das Hash-Gewicht jedes anderen Knotens für diesen Schlüssel. ${\displaystyle h()}$${\displaystyle S_{x}}$${\displaystyle k_{m}}$${\displaystyle h(S_{x},k_{m})}$

Lokalitätserhaltendes Hashing

Lokalitätserhaltendes Hashing stellt sicher, dass ähnliche Schlüssel ähnlichen Objekten zugewiesen werden. Dies kann eine effizientere Ausführung von Bereichsabfragen ermöglichen, jedoch ist im Gegensatz zum konsistenten Hashing nicht mehr gewährleistet, dass die Schlüssel (und damit die Last) gleichmäßig zufällig auf den Schlüsselraum und die beteiligten Peers verteilt werden. DHT-Protokolle wie Self-Chord und Oscar adressieren solche Probleme. Self-Chord entkoppelt Objektschlüssel von Peer-IDs und sortiert Schlüssel entlang des Rings mit einem statistischen Ansatz, der auf dem Schwarmintelligenz- Paradigma basiert . Durch die Sortierung wird sichergestellt, dass ähnliche Schlüssel von Nachbarknoten gespeichert werden und dass Ermittlungsverfahren, einschließlich Bereichsabfragen , in logarithmischer Zeit durchgeführt werden können. Oscar konstruiert ein navigierbares Small-World-Netzwerk basierend auf Random-Walk- Sampling, das auch die logarithmische Suchzeit sicherstellt.

Overlay-Netzwerk

Jeder Knoten unterhält eine Reihe von Verbindungen zu anderen Knoten (seinen Nachbarn oder Routing-Tabelle ). Zusammen bilden diese Links das Overlay-Netzwerk. Ein Knoten wählt seine Nachbarn nach einer bestimmten Struktur aus, die als Netzwerktopologie bezeichnet wird .

Alle DHT-Topologien teilen eine Variante der wichtigsten Eigenschaft: Für jeden Schlüssel k hat jeder Knoten entweder eine Knoten-ID, die k besitzt, oder hat eine Verbindung zu einem Knoten, dessen Knoten-ID näher an k liegt , in Bezug auf den oben definierten Schlüsselraumabstand . Es ist dann leicht, eine Nachricht an den Besitzer eines beliebigen Schlüssels k zu leiten, indem der folgende Greedy-Algorithmus verwendet wird (der nicht unbedingt global optimal ist): Bei jedem Schritt die Nachricht an den Nachbarn weiterleiten, dessen ID am nächsten zu k liegt . Wenn es keinen solchen Nachbarn gibt, müssen wir am nächsten Knoten angekommen sein, der der Eigentümer von k ist, wie oben definiert. Diese Art des Routings wird manchmal als schlüsselbasiertes Routing bezeichnet .

Neben der grundlegenden Routing-Korrektheit bestehen zwei wichtige Einschränkungen der Topologie darin, zu garantieren, dass die maximale Anzahl von Hops in jeder Route (Routenlänge) niedrig ist, damit Anforderungen schnell abgeschlossen werden; und daß die maximale Anzahl der Nachbarn eines Knotens (maximaler Knotengrad ) niedrig ist , so dass Wartungsaufwand nicht zu groß ist. Für kürzere Strecken ist natürlich ein höherer Maximalgrad erforderlich . Einige gängige Optionen für den maximalen Grad und die Routenlänge sind wie folgt, wobei n die Anzahl der Knoten in der DHT ist, wobei die Big-O-Notation verwendet wird :

max. Grad	Maximale Streckenlänge	Benutzt in	Notiz
${\displaystyle O(1)}$	${\displaystyle O(n)}$		Schlechteste Suchlängen, mit wahrscheinlich viel langsameren Suchzeiten
${\displaystyle O(1)}$	${\displaystyle O(\log n)}$	Koorde (mit konstantem Grad)	Komplexer zu implementieren, aber akzeptable Lookup-Zeiten können mit einer festen Anzahl von Verbindungen gefunden werden
${\displaystyle O(\log n)}$	${\displaystyle O(\log n)}$	Chord Kademlia Gebäck Wandteppich	Am häufigsten, aber nicht optimal (Grad/Routenlänge). Chord ist die einfachste Version, wobei Kademlia die beliebteste optimierte Variante zu sein scheint (sollte die durchschnittliche Suche verbessert haben)
${\displaystyle O(\log n)}$	${\displaystyle O(\log n/\log(\log n))}$	Koorde (mit optimaler Suche)	Die Implementierung ist komplexer, aber die Suche kann schneller sein (mit einer niedrigeren Grenze für den schlimmsten Fall)
${\displaystyle O({\sqrt {n}})}$	${\displaystyle O(1)}$		Größte lokale Speicheranforderungen, mit viel Kommunikation, nachdem ein Knoten verbunden oder getrennt wurde

Die häufigste Wahl, Grad/Routenlänge, ist im Hinblick auf Grad/Routenlänge-Kompromiss nicht optimal, aber solche Topologien ermöglichen typischerweise mehr Flexibilität bei der Auswahl von Nachbarn. Viele DHTs nutzen diese Flexibilität, um Nachbarn auszuwählen, die in Bezug auf die Latenz im zugrunde liegenden physischen Netzwerk nahe beieinander liegen. Im Allgemeinen konstruieren alle DHTs navigierbare Small-World-Netzwerktopologien, die einen Kompromiss zwischen Routenlänge und Netzwerkgrad eingehen. ${\displaystyle O(\log n)}$

Die maximale Routenlänge hängt eng mit dem Durchmesser zusammen : die maximale Anzahl von Sprüngen auf einem kürzesten Pfad zwischen Knoten. Offensichtlich ist die Routenlänge des Netzwerks im ungünstigsten Fall mindestens so groß wie sein Durchmesser, sodass DHTs durch den Grad/Durchmesser-Kompromiss begrenzt sind, der in der Graphentheorie grundlegend ist . Die Routenlänge kann größer als der Durchmesser sein, da der Greedy-Routing-Algorithmus möglicherweise nicht die kürzesten Pfade findet.

Algorithmen für Overlay-Netzwerke

Abgesehen vom Routing gibt es viele Algorithmen, die die Struktur des Overlay-Netzwerks zum Senden einer Nachricht an alle Knoten oder eine Teilmenge von Knoten in einem DHT ausnutzen. Diese Algorithmen werden von Anwendungen verwendet, um Overlay-Multicast , Bereichsabfragen oder Statistiken zu sammeln. Zwei Systeme, die auf diesem Ansatz basieren, sind Structella, das Fluting und Random Walks auf einem Pastry-Overlay implementiert, und DQ-DHT, das einen dynamischen Abfragesuchalgorithmus über ein Chord-Netzwerk implementiert.

Sicherheit

Aufgrund der Dezentralisierung, Fehlertoleranz und Skalierbarkeit von DHTs sind sie von Natur aus widerstandsfähiger gegen feindliche Angreifer als ein zentralisiertes System.

Offene Systeme zur verteilten Datenspeicherung , die robust gegenüber massiven feindlichen Angreifern sind, sind machbar.

Ein DHT-System, das sorgfältig auf byzantinische Fehlertoleranz ausgelegt ist, kann eine Sicherheitsschwäche abwehren, die als Sybil-Angriff bekannt ist und alle aktuellen DHT-Designs betrifft.

Petar Maymounkov, einer der ursprünglichen Autoren von Kademlia , hat einen Weg vorgeschlagen, die Schwäche des Sybil-Angriffs zu umgehen, indem er soziale Vertrauensbeziehungen in das Systemdesign einbezieht. Das neue System mit dem Codenamen Tonika oder auch unter dem Domainnamen 5ttt bekannt, basiert auf einem Algorithmusdesign namens "electric routing" und wurde gemeinsam mit dem Mathematiker Jonathan Kelner verfasst. Maymounkov hat dieses neue System nun umfassend implementiert. Die Erforschung effektiver Abwehrmaßnahmen gegen Sybil-Angriffe wird jedoch im Allgemeinen als offene Frage angesehen, und jedes Jahr werden auf führenden Konferenzen zur Sicherheitsforschung eine Vielzahl potenzieller Abwehrmaßnahmen vorgeschlagen.

Implementierungen

Zu den bemerkenswertesten Unterschieden, die in praktischen Beispielen von DHT-Implementierungen angetroffen werden, gehören mindestens die folgenden:

• Der Adressraum ist ein Parameter von DHT. Mehrere reale DHTs verwenden 128-Bit- oder 160-Bit-Schlüsselraum.
• Einige reale DHTs verwenden andere Hashfunktionen als SHA-1 .
• In der realen Welt ist der Schlüssel k könnte ein Hash einer Akte sein Gehalt eher als ein Hash eines Dateinamen zur Verfügung zu stellen Content-Addressed Storage , so dass der Umbenennungs von nicht verhindern , dass Benutzer , es zu finden.
• Einige DHTs können auch Objekte unterschiedlichen Typs veröffentlichen. Schlüssel k könnte zum Beispiel die Knoten- ID sein und zugehörige Daten könnten beschreiben, wie dieser Knoten kontaktiert wird. Dies ermöglicht die Veröffentlichung von Anwesenheitsinformationen und wird häufig in IM-Anwendungen usw. verwendet. Im einfachsten Fall ist ID nur eine Zufallszahl, die direkt als Schlüssel k verwendet wird (also in einer 160-Bit-DHT- ID eine 160-Bit- ID ist). Nummer, meist zufällig gewählt). In einigen DHTs wird die Veröffentlichung von Knoten-IDs auch verwendet, um DHT-Operationen zu optimieren.
• Redundanz kann hinzugefügt werden, um die Zuverlässigkeit zu verbessern. Das (k, data) -Schlüsselpaar kann in mehr als einem dem Schlüssel entsprechenden Knoten gespeichert werden. Anstatt nur einen Knoten auszuwählen, wählen reale DHT-Algorithmen normalerweise i geeignete Knoten aus, wobei i ein implementierungsspezifischer Parameter des DHT ist. In einigen DHT-Entwürfen stimmen Knoten zu, einen bestimmten Schlüsselraumbereich zu handhaben, dessen Größe dynamisch gewählt werden kann, anstatt fest codiert zu sein.
• Einige fortgeschrittene DHTs wie Kademlia führen zuerst iterative Lookups durch das DHT durch, um einen Satz geeigneter Knoten auszuwählen und senden put(k, data) -Nachrichten nur an diese Knoten, wodurch der nutzlose Verkehr drastisch reduziert wird, da veröffentlichte Nachrichten nur an Knoten gesendet werden, die als geeignet erscheinen, den Schlüssel k zu speichern ; und iterative Lookups decken nur eine kleine Gruppe von Knoten ab und nicht das gesamte DHT, wodurch nutzlose Weiterleitungen reduziert werden. In solchen DHTs kann die Weiterleitung von put(k, data) -Nachrichten nur als Teil eines selbstheilenden Algorithmus erfolgen: wenn ein Zielknoten eine put(k, data) -Nachricht empfängt , aber glaubt, dass k außerhalb seines verarbeiteten Bereichs liegt und ein näherer Knoten (in Bezug auf den DHT-Schlüsselraum) bekannt ist, wird die Nachricht an diesen Knoten weitergeleitet. Andernfalls werden die Daten lokal indiziert. Dies führt zu einem etwas selbstausgleichenden DHT-Verhalten. Natürlich erfordert ein solcher Algorithmus, dass Knoten ihre Präsenzdaten im DHT veröffentlichen, damit die iterativen Lookups durchgeführt werden können.
• Da das Versenden von Nachrichten auf den meisten Rechnern deutlich teurer ist als der Zugriff auf lokale Hash-Tabellen, ist es sinnvoll, viele Nachrichten zu einem bestimmten Knoten in einem einzigen Batch zu bündeln. Unter der Annahme, dass jeder Knoten einen lokalen Stapel hat, der aus höchstens b Operationen besteht, ist die Bündelungsprozedur wie folgt. Jeder Knoten sortiert zunächst seinen lokalen Stapel nach der Kennung des für die Operation verantwortlichen Knotens. Mit Bucket sort kann dies in O(b + n) erfolgen , wobei n die Anzahl der Knoten im DHT ist. Wenn innerhalb eines Stapels mehrere Vorgänge denselben Schlüssel adressieren, wird der Stapel vor dem Versand komprimiert. Beispielsweise können mehrere Nachschlagevorgänge desselben Schlüssels auf einen oder mehrere Inkremente auf einen einzigen Add-Vorgang reduziert werden. Diese Reduzierung kann mit Hilfe einer temporären lokalen Hash-Tabelle realisiert werden. Schließlich werden die Operationen an die jeweiligen Knoten gesendet.

Beispiele

DHT-Protokolle und -Implementierungen

• Apache Kassandra
• BATON-Overlay
• Mainline DHT – Standard-DHT, das von BitTorrent verwendet wird (basierend auf Kademlia, wie von Khashmir bereitgestellt)
• Inhaltsadressierbares Netzwerk (CAN)
• Akkord
• Koorde
• Kademlia
• Gebäck
• P-Gitter
• Riak
• Tapisserie
• TomP2P
• Voldemort

Anwendungen mit DHTs

• BTDigg : BitTorrent DHT-Suchmaschine
• Codeen : Web-Caching
• Coral Content Distribution Network
• Freenet : ein zensurresistentes anonymes Netzwerk
• GlusterFS : ein verteiltes Dateisystem zur Speichervirtualisierung
• GNUnet : Freenet-ähnliches Distributionsnetzwerk mit einer DHT-Implementierung
• I2P : Ein anonymes Open-Source-Peer-to-Peer-Netzwerk
• I2P-Bote : serverlose sichere anonyme E-Mail
• IPFS : Ein inhaltsadressierbares Peer-to-Peer-Hypermedia-Verteilungsprotokoll
• JXTA : Open-Source-P2P-Plattform
• Oracle Coherence : ein In-Memory-Datengrid, das auf einer Java DHT-Implementierung basiert
• Perfect Dark : eine Peer-to-Peer -Filesharing- Anwendung aus Japan
• Retroshare : ein Netzwerk von Freund zu Freund
• Jami : eine die Privatsphäre schützende Sprach-, Video- und Chat-Kommunikationsplattform, basierend auf einem Kademlia-ähnlichen DHT
• Tox : ein Instant-Messaging- System, das als Skype- Ersatz dienen soll
• Twister : eine Microblogging- Peer-to-Peer- Plattform
• YaCy : eine verteilte Suchmaschine

Siehe auch

• Couchbase Server : ein persistentes, repliziertes, geclustertes verteiltes Objektspeichersystem, das mit dem Memcached-Protokoll kompatibel ist.
• Memcached : ein hochleistungsfähiges, verteiltes Speicherobjekt-Caching-System.
• Präfix-Hash-Baum : ausgeklügelte Abfragen über DHTs.
• Merkle-Baum : Baum, bei dem jeder Nicht-Blatt-Knoten mit dem Hash der Labels seiner Kinderknoten beschriftet ist.
• Die meisten verteilten Datenspeicher verwenden eine Form von DHT für die Suche.
• Skip-Graphen sind eine effiziente Datenstruktur zum Implementieren von DHTs.

Verweise

Externe Links

• Verteilte Hash-Tabellen, Teil 1 von Brandon Wiley.
• Distributed Hash Tables verlinkt Carles Pairots Seite zur DHT- und P2P-Forschung
• kademlia.scs.cs.nyu.edu Archive.org Schnappschüsse von kademlia.scs.cs.nyu.edu
• Eng-Keong Lua; Crowcroft, Jon; Pias, Marcelo; Sharma, Ravi; Lim, Steve (2005). "IEEE-Umfrage zu Overlay-Netzwerkschemata". CiteSeerX  10.1.1.111.4197 : Cite Journal erfordert |journal=( Hilfe ) die Abdeckung unstrukturierter und strukturierter dezentraler Overlay-Netzwerke, einschließlich DHTs (Chord, Pastry, Tapestry und andere).
• Mainline-DHT-Messung am Institut für Informatik der Universität Helsinki, Finnland.