Distributed HashTables & Peer2Peer
TL;DR:
Im Wintersemester 07/08 habe ich zusammen mit Marc Hübner einen Vortrag über verteilte Hashtabellen ausgearbeitet und im Fach Verteilte Systeme II
gehalten. Wir legten den Fokus auf Peer2Peer-Anwendungen.
Verteilte Hashtabellen - oder auch abgekürzt DHT - ist ein langsam in die Mode kommender Ansatz, Verzeichnisse und Indexe aller Art verteilt im Netzwerk zu speichern. Auf solch einer DHT können die Operationen Knoten finden
, Value finden
und neuen Wert speichern
angewendet werden. FileSharing Programme wie BitTorrent nutzen diese Technik um ohne zentralen Tracker andere Knoten zu finden.
Von den eigentlichen Daten werden Hashwerte erzeugt (welche intern als ID fungieren), die der Datei einen eindeutigen Platz im Suchbaum geben (Folie 8). Jeder Knoten im Netzwerk erhält ebenfalls einen 160 Bit-Key zur Identifikation. Das besondere daran ist, dass Daten-Hashes und Knoten-IDs im selben Suchbaum untergebracht werden und jeder Knoten alle Key/Value-Paare (also die Hashwerte der Daten) deren Keys die geringste Entfernung zu einem selbst haben. Somit kann man mit dem XOR-Verfahren (Folie 19) in O(log n) ein garantiertes Suchergebnis bekommen.