Kademlia

Überblick

Der Kademlia-Algorithmus wurde 2002 an New York University von Petar Maymounkov and David Mazieres entwickelt. Es handelt sich um die Implementation einer "Distributed Hash Table", sie baut ein selbstorganisierendes, strukturiertes P2P-Netz auf und regelt Kommunikation und Austausch zwischen den Netzwerkknoten.
Dabei wird ein sehr effizientes Vorgehen angewendet, so daß verhältnismäßig wenig Overhead entsteht.

Schlüssel-Wert-Paare

Das besondere Kennzeichen von Kademlia ist der gemeinsame virtuelle Adreßraum für Knoten-IDs und Schlüssel mit 160 Bit Breite. Damit eine Information im Netzwerk gefunden werden kann, wird ihr Hashwert (der Schlüssel) als Schlüssel-Wert-Paar auf mehreren Knoten mit einer zum Schlüssel ähnlichen ID gespeichert. Ein Knoten, der den dort gespeicherten Schlüssel sucht, kann dann den Wert des Schlüssel-Wert-Paars enthalten und anhand dessen bestimmen, von welchem Netzwerkknoten er die Information erhalten kann.

XOR-Metrik

Als Abstandsfunktion wird das bitweise XOR verwendet. Da Schlüssel und Knoten-IDs auf dem gleichen Raum definiert sind, kann auch der Abstand eines Schlüssels von einer Knoten-ID ermittelt werden.

  Abstand(Argument_1, Argument_2) = Argument_1 XOR Argument_2

z.B.:

  1011 XOR 1000 = 0011

Das Ergebnis dieser Operation wird als Abstand aufgefaßt.
Die Verwendung der XOR-Funktion bedingt dabei, daß unterschiedliche niederwertige Bits der Operanden sich weit weniger auf den Abstand auswirken als höherwertige Bits - daher werden Knoten mit ähnlichen Knoten-IDs im Netzwerk Nachbarn sein.

Routingtabellen: "k-Buckets"

Bekannte Knoten werden in Kademlia als Listen gehandhabt. Hierzu wird der Adreßraum in Intervalle von je $2^{i}$ bis $2^{i+1}$ mit $0<=i<160$ zerlegt, jeder Knoten führt also 160 solche Listen, um den ganzen Adreßraum erfassen zu können.
In einer solchen Liste ist jeweils Platz für "k" viele Tupel aus (IP-Adresse, UDP-Port und Node-ID), wobei jedes Tupel einen Knoten des Netzwerks beschreibt. Die Liste ist nach dem letzten Kontaktzeitpunkt mit dem jeweiligen Tupel sortiert, die jüngsten Kontakte stehen dazu am Ende der Liste.
"k" ist ein systemweiter Parameter, der so gewählt werden sollte, daß ein Ausfall aller Knoten einer solchen Liste innerhalb von einer Stunde sehr unwahrscheinlich ist, in der Praxis ist $k=20$ ein Richtwert.
Aus diesem Aufbau ergibt sich, daß ein Knoten über ein hohes Wissen über seine Nachbarn verfügt, aber über nur wenige Knoten, die sehr weit von ihm entfernt sind, kennt.

Um diese Listen stets aktuell zu halten, werden aus dem Netzwerk eingehende Nachrichten zur Aktualisierung der "k-Buckets" verwendet:

• ist der Absenderknoten bereits in den "k-Buckets" vorhanden, wird er in seiner Liste an das Ende der Liste sortiert
  
• ist der Absenderknoten noch nicht in den "k-Buckets" vorhanden und ist das entsprechende Bucket noch nicht voll, wird der Knoten am Ende der Liste eingefügt
  
• ist der Absenderknoten noch nicht in den "k-Buckets" vorhanden und ist das entsprechende Bucket voll, wird der am Kopf der Liste stehende Knoten angepingt. Reagiert dieser nicht, wird der neue Knoten am Ende der Liste eingefügt - andernfalls wird der neue Knoten verworfen.
  

Dieses Verfahren bietet einen gewissen Schutz gegen "einfache" Denial-Of-Service-Angriffe, da dem Knoten bekannte Knoten bei Flutung mit Nachrichten nicht verworfen werden, bis diese tatsächlich das Netzwerk verlassen.

Operationen

Kademlia kommt mit vier Operationen aus:

  PING

-> Dient lediglich der Ermittlung, ob ein Knoten online ist

  FIND_NODE

-> Ermitteln der "k" nächsten Knoten zu einer Knotenadresse

  FIND_VALUE

-> Suche und Abfragen des Wertes aus dem Schlüssel-Wert-Paares zu einem Schlüssel

  STORE

-> Abspeichern eines Schlüssel-Wert-Paares auf einem Knoten

Knotensuche mit FIND_NODE

FIND_NODE ermittelt die "k" nächsten Knoten zu der übergebenen Knoten-ID. Dazu werden aus dem passenden "k-Bucket" die "i" nächsten Knoten parallel angefragt. Diese liefern ihre zur gesuchten Knoten-ID "k" nächsten Tupel aus ihren "k-Buckets" an den Anfrager zurück, wobei diese bereits näher an der gesuchten Knoten-ID als sie selbst liegen.
Der Anfragende wiederholt dieses Verfahren, bis in einem Durchlauf keine weitere Annähernung an den gesuchten Knoten mehr erreicht werden kann und schickt an diesem Punkt noch abschließend "k" Anfragen an die nächsten Knoten, die er noch nicht angefragt hat.
"i" ist für dieses Verfahren ein systemweiter Paramter, der in der Praxis mit $i=3$ angegeben ist.

Bootstrapping

Ein dem Netzwerk beitretender Knoten hat anfangs keine Kenntnis über das Netzwerk - und demnach keine Knoten in seinen "k-Buckets". Um dem Netzwerk beizutreten, generiert er nun seine eigene Knoten-ID mit einer konsistenten Hashfunktion. Auf irgendeine - nicht durch Kademlia selbst spezifierte - Weise muß der Knoten nun einen Erstkontakt mit einem Knoten aus dem Netzwerk erhalten.

Diesen Knoten fügt er dann in seine "k-Buckets" ein und führt ein FIND_NODE nach seiner eigenen Knoten-ID durch, um seine nächsten Nachbarn kennenzulernen und seine "k-Buckets" zu füllen. Dies hat gleichzeitig den positiven Effekt, daß sich der neue Knoten im Netzwerk bekannt macht.

Schlüsselsuche mit FIND_VALUE

Nach dem gleichen Schema wie bei der Knotensuche mit FIND_NODE wird hier nach einem Schlüssel gesucht. Der Knoten startet also eine parallele Anfrage und bekommt in der Regel die "k" nächsten Knoten zurück - besitzt jedoch einer der angefragten Knoten das gesuchte Schlüssel-Wert-Paar, bricht die Suche ab.
Abschließend prüft der Anfragende noch, ob die ihm bekannten "k" nächsten Knoten zum Schlüssel alle das Schlüssel-Wert-Paar besitzen und speichert dieses gegebenenfalls auf ihnen.

Publizierung von Schlüssel-Wert-Paaren

Um ein Schlüssel-Wert-Paar im Netzwerk abzulegen, wird zuerst ein FIND_NODE nach dem entsprechenden Schlüssel durchgeführt, um die "k" nächsten Knoten zu bestimmen.
Im zweiten Schritt wird mit STORE auf diesen Knoten das Paar abgelegt.
Die Knoten, die ein Paar erhalten haben, kümmern sich fortan selbsttätig darum, dieses auf neu ins Netzwerk gekommenen Knoten, die noch näher am Schlüssel des Paares liegen als sie selbst, abzulegen.

Aktualität von Schlüssel-Wert-Paaren

Um veraltete Verweise zu verhindern, verfallen Schlüssel-Wert-Paare nach 24 Stunden im Netzwerk durch einen Zeitstempel. Dementsprechend müssen diese Paare vom Inhaber der dem Schlüssel entsprechenden Information auch alle 24 Stunden wieder neu mit STORE in das Netzwerk eingebracht werden.
Weiterhin speichern die Knoten, auf denen die Schlüssel-Wert-Paare gespeichert sind, diese im Stundentakt neu im Netzwerk ab - um sicherzustellen, daß diese Paare stets auf mindestens "k" Knoten gespeichert sind, da in der Zwischenzeit sich möglicherweise andere Knoten, die dasselbe Paar gespeichert hatten, vom Netz gegangen sein könnten.

Schlußfolgerung

• Suchaufwand praktisch identisch: O(log n)
• Höherer Aufwand für Kademlias Routingtabellen
• Keine Beachtung der Distanz von virtuellen Nachbarknoten im Netzwerk – leistet nur Pastry
• Gleicht Nichtbeachtung von Netzwerkkosten durch Schlüssel-Wert-Paar-Caching aus
• Bei Knotenausfall: Schlüsselsuche in Kademlia ohne Latenzsteigerung durch parallele Anfragen
• Besondere Eignung für sehr dynamische Netze
• Hohe Effizienz des Datenverkehrs

Kademlia realisiert eine Suchfunktion in einem strukturierten Peer-To-Peer-Netz mit logarithmischer Komplexität, was für DHT-Ansätze allgemein typisch ist.
Im Vergleich mit anderen DHTs ist der Aufwand für Kademlias Routingtabellen / "k-Buckets" höher, aber z.B. für den Einsatz als Protokoll für Filesharing ist dieser Mehraufwand zu vernachlässigen.
Kademlia bezieht die realen Netzwerkkosten nicht mit ein - Nachbarn im erzeugten Netz können also im Trägernetz weit voneinander entfernt oder sehr verschieden angebunden sein. Dieser Nachteil wird jedoch durch das Caching der Schlüssel-Wert-Paare ausgeglichen. Diese Eigenschaft führt überdies dazu, daß bei Suchanfragen in Kademlia auch beim Ausfall vieler beteiligter Knoten keine wesentliche Latenzsteigerung zu erwarten ist.
Kademlia eignet sich demnach besonders für sehr dynamische Netze und kann mit einer hohen Effizienz des Datenverkehrs aufwarten.
Diese Eigenschaften haben wahrscheinlich auch zu der derzeitigen Verbreitung geführt (Overnet, eMule, BitTorrent, …).

Weiterführende Links

Die erste Anlaufstation zum Verständnis der Funktionsweise von Kademlia ist das Paper von Petar Maymounkov and David Mazieres:

• Kademlia: A of Peer to peer information system Based on the XOR Metric (englisches PDF)