Dr.ChAoS (Offline)

Hallo zusammen,

da ich für ein anderes Projekt eine P2P Funktionalität benötige und ich so etwas in dieser Richtung noch nie gemacht habe, habe ich eine kleine Implementierung von Kademlia in Python geschrieben. Für alle die Kademlia nicht kennen, das ist das Protokoll auf welches z.B. BitTorrent und Gnutella (LimeWire und co.) aufbauen. Um schnell eine lauffähige Version hinzubekommen habe ich das ganze in Python umgesetzt. Jetzt fange ich dann mit der C/C++ Variante an sobald ich mich für eine der Sprachen entschieden habe^^.

Da ich am Anfang mangels guter bzw halbwegs verständlicher Lektüre zu dem Thema Probleme hatte einen Einstieg zu finden, dachte ich dass meine Version vielleicht auch für andere interessant sein könnte. Darum veröffentliche ich diese Proof of Concept Implementierung jetzt hier. Diese Implementierung sollte keinesfalls in einem echten Projekt eingesetzt werden, da diese fast keine Fehlerbehandlung beinhaltet und nur die Funktionsweise von Kademlia veranschaulichen soll. Ich habe versucht mich so gut wie möglich an die Vorgaben aus der offiziellen Spezifikation zu halten und ich glaube das sollte so weit auch passen.

Zur Implementierung

Die Implementierung besteht aus folgenden Modulen
- kadserver.py: Dient dazu den Kontakt zwischen den Nodes herzustellen.
- kad.py: Ist die eigentliche Implementierung von Kademlia.
- kadtypes.py: Beinhaltet spezielle Datentypen für Kademlia, wie z.B. die NodeID.
- rpc.py: Da alle RPC-Libraries welche ich getestet habe total beschissen waren habe ich selbst eine schreiben müssen.
- interface.py: Zum komfortablen Testen der Implementierung habe ich hier ein kleines CLI geschrieben.

Benutzung

Um den Kontakt zwischen den einzelnen Nodes herstellen zu können braucht man einen kleinen Server, das kann man sich wie den Tracker im Torrent Netzwerk vorstellen. Der macht in meinem Fall jetzt nichts weiter als an jeden neuen Node im Netzwerk eine Liste aus 10 zufällig gewählten Kontakten zu senden.

Dieser muss als erstes gestartet werden:
Standardmäßig läuft dieser Server unter localhost:1337, um das zu ändern muss man die betreffende Stelle in kadserver.py ändern.

Anschließend können die Nodes deployed werden. Dazu muss man nur
das Interface starten:
Auf der "root" Ebene, wenn kein Node ausgewählt wurde, gibt es die folgenden Kommandos:
deploy <Anzahl Nodes>
Startet die angegebene Anzahl Nodes. Begonnen wird ab Port 10000
exit
Stoppt alle Nodes und beendet das Programm.
stopAll
Stoppt alle Nodes.
select <NodeID | Port>
Wählt einen Node aus.
nodesWithValue <value>
Gibt alle Nodes aus auf denen der angegebene Wert gespeichert ist.
nodesWithoutValue <value>
Gibt alle Nodes aus auf denen der angegebene Wert nicht gespeichert ist.
printAllBuckets
Gibt alle Nodes + die Anzahl der jeweils damit verbundenen Kontakte aus.
storeFindCheck <value>
Dieser Befehl generiert einen zufälligen Wert falls keiner angegeben wurde und speichert diesen von einem zufälligen Node aus
im Netzwerk. Anschließend wird von allen Nodes aus auf denen der Wert nicht gespeichert wurde, versucht den Wert zu finden.


Wenn ein Node selektiert wurde, stehen einem folgende Kommandos zur Verfügung:
nodeId
Gibt die NodeID des aktuell selektierten Nodes aus.
leave
"Verlässt" den aktuell ausgewählten Node.
stop
Stoppt den Node und verlässt diesen dann.
ping <NodeID>
Pingt einen Node an.
store <value>
Speichert einen Wert im Netzwerk
findValue <hash>
Findet einen gespeicherten Wert anhand des Hashwertes.
findNode <NodeID>
Sucht naheliegende Nodes zu der angegebenen NodeID.
printStored
Gibt alle auf dem Node gespeicherten Key/Value Paare zurück.
printBuckets
Gibt die Kontakte in den einzelnen Buckets aus.

Wenn man die Befehle ohne Parameter eingibt, bekommt man die möglichen Parameter auch angezeigt. Allerdings gibts auch hier fast keine Fehlerbehandlung bei der Benutzereingabe. Wenns hier knallt muss man den Prozess abschießen und neu starten. Ich hatte schlichtweg keine Lust dazu das einzubauen, da es eh nur zum Testen und Lernen dient.

Kleines Beispiel

Als erstes deployed man dann ein paar Nodes. Hier sollte man schon etwas großzügiger sein, da man Kademlia erst richtig mit ein paar hundert Nodes testen kann. Am Anfang würde ich mal mit
150 Nodes starten und schauen ob alles sauber läuft:
In der Konsole des Servers kann man jetzt sehen wie sich alle Nodes beim Server bekannt manchen und sich eine Liste mit weiteren Nodes holen.
Das Interface ist so eingestellt dass die Nodes ab Port 10000 beginnen.

Wenn keine Fehler aufgetreten sind kann man sich z.B. alle Nodes und die Anzahl deren Kontakte ausgeben lassen:
Dann sollte man eine Liste bekommen welche in etwa so aussieht:
"534B9FD41AFB4BEA47D5DCFBC23EAAA9D498E915" z.B. ist hierbei die NodeID
und 10 die Anzahl der Nodes mit denen der Node verbunden ist. Das kann stark variieren und hängt davon ab wie weit diese Nodes virtuell voneinander entfernt sind. Dazu aber später mehr.

Um das Interface jetzt mit einem Node zu verbinden und von diesem Node aus Befehle ins Netzwerk zu senden, verwendet man den select Befehl. Dazu schreibt man einfach "select" und dann die Port Nummer oder die NodeID,
also z.B:
Anschließend sollte man so etwas zu sehen bekommen:
Die Zahl ist der Port des Nodes.

Hier kann man jetzt beliebige Befehle ausführen. Als einfaches Beispiel einen Ping:
Hier ging alles gut und der andere Node konnte erfolgreich angepingt werden da er in den eigenen Buckets vorhanden war.

Jetzt verlassen wir den ausgewählten Node wieder mit leave:
Und machen zum testen mal einen storeFindCheck:
Das Ergebnis von diesem Test hängt von mehreren Faktoren ab:
- Der Entfernung des Hashwertes zu der Eigenen NodeID und somit zu den Nodes in den eigenen Buckets
- Die Anzahl der Nodes in den eigenen Buckets
- An der allgemeinen Verteilung der Nodes im Netz.
Es kann sein dass der Wert nur auf einer Handvoll Nodes erreichbar ist oder durchweg auf allen.
Nach dem erneuten Ausführen des Befehls mit dem selben Wert kann das Ergebnis bereits viel besser aussehen:
Auch Interessant ist, dass wenn neue Nodes ins Netzwerk dazukommen und deren NodeID näher an dem gespeicherten Wert liegen als die eigene NodeID wird der Wert auf dem betreffenden Node gespeichert. Testen kann man das durch das Deployen von weiteren Nodes.
Allerdings erst schauen auf wie vielen Nodes der Wert bereits vorhanden ist:
Dann weitere Nodes deployen:
Und schauen auf wie vielen Nodes der Wert jetzt gespeichert ist:
Das sollte jetzt aber erstmal reichen. An manchen Stellen ist die Implementierung ziemlich "hacky", sorry dafür^^.
Ich denke aber dass man diese einigermaßen verstehen kann.

Kademlia Grundlagen
Um das ganze besser verstehen zu können möchte ich an dieser Stelle die wichtigsten Grundkonzepte von Kademlia
nochmal zusammenfassen.

Was ist Kademlia jetzt genau?
Kademlia ist eine verteilte Hashtabelle oder auch "Distributed hash table" (DHT) für P2P Overlay Netzwerke, welche es ermöglicht Key/Value Paare in einem verteilten Netz zu speichern und wieder zu finden.
Jeder Node und jeder zu speichernde Wert erhält eine NodeID, das ist ein 160 Bits großer Wert, anhand der Node/Wert im Netzwerk identifiziert wird.
Dabei wird immer versucht sich mit Nodes zu umgeben welche die kürzeste Distanz zur eigenen NodeID aufweisen.

Die Distanz zwischen den Nodes
Die Distanz hat dabei nichts mit der physikalischen Distanz zu tun sondern wird per XOR berechnet.
Die Berechnung funktioniert vereinfacht so:

Wenn man die Distanz zwischen zwei Nodes berechnen will xor'ed man einfach deren NodeIDs.
Angenommen die Nodes haben die ID 5 und die ID 2: 5 xor 2 = 7
Die Distanz wäre in diesem Fall 7.

Weiteres Beispiel: 5 xor 4 = 1

Auch wenn man die Distanz zu sich selbst ermitteln möchte funktioniert die Rechnung: 5 xor 5 = 0

Alles andere würde an dieser Stelle aber zu weit führen. Ich denke als Einstieg sollte das erstmal reichen.

Quellen
Für alle die mehr über Kademlia lernen möchten, hier die Quellen die ich
hauptsächlich verwendet habe:
http://www.cs.rice.edu/Conferences/IPTPS02/109.pdf (Kurzversion)
http://pdos.csail.mit.edu/~petar/pap...emlia-lncs.pdf (Langversion)
http://xlattice.sourceforge.net/comp...lia/specs.html (Gute Zusammenfassung des Protokolls, teils aber etwas zu knapp)
http://blog.notdot.net/2009/11/Imple...T-in-Go-part-1 (Implementierung in Go, welche mir beim Einstieg sehr geholfen hat, leider aber unvollständig ist.)
http://de.wikipedia.org/wiki/Kademlia (Muss ich eigentlich nicht extra erwähnen, oder? )

Falls ihr Fragen habt könnt ihr gerne fragen. Ich bin zwar kein Experte auf dem Gebiet aber ich kann versuchen Licht ins Dunkel zu bringen^^.

Ich habe übrigens ausschließlich die Python Standard Library verwendet, sollte also mit jeder Python 2.7 Installation problemlos laufen. Getestet habe ich es jetzt nur unter Linux, aber dank Python sollte das ja auch sonst überall funktionieren.

// EDIT 18.02.2013: Neue Version hochgeladen. Bugs beseitigt und Broadcast hinzugefügt (Der ist allerdings eher experimentell).

Angehängte Dateien

Kademlia.zip (11,1 KB, 4x aufgerufen)

__________________
MfG
Dr.ChAoS

pr0st (Offline)

coole sache!
habe mal gestöbert und ein seminar in pdf form gefunden.
ist einiges auf deutsch dabei.

http://www.p2p.tu-darmstadt.de/filea...p2p-sose10.pdf