Python: 勉強がてらDHT(Kademliaっぽいもの)を実装しました

前々から一度じっくり勉強しないとなぁと思っていたDHTまわりの勉強がてらKademliaっぽいものをPythonで実装してみました。

Kademliaはいろいろ実装があるので、ソースを読んじゃうと答えみちゃった感じになるかなーと思って、元論文と 首藤様の資料 くらいしか見ずに実装してみました。ので、いろいろ間違ってるかも知れませんが･･･。

本家Kademliaとの主な違いは

  • UDPではなくTCPを使っている

    • ローカル環境しかもっていないので、UDPパケットがロスしやすい場合(WAN)を想定して実装するのがめんどくさい。
    • よってRPC-IDをつけていない。
    • パケットの分割や再送もTCPにおまかせ。

  • original publisherから一定時間publishを受けなくてもインデックス情報をexpireしていない

    • 実装するのは簡単です。

  • ノードがネットワークに参加したとき、Index情報を移動させていません

    • これも実装は簡単です。

ダウンロード

適当なのですが、置いておけば誰かの役に立つこともなきにしもあらず、かもしれないので置いておきます。jsonつかっているので2.6以上で動きます。

実装について

以前Chordもちょっと実装したことがあるのですが、やっぱりいろんなソフトで採用されているだけあって、Kademliaはかなり実装が楽ですね。論文読んで素直に実装すれば動きます。

えーと、内部についてはmultiprocessing使えよとか、TCPサーバを自前で書くって標準ライブラリにあるだろ、とか、twisted,eventlet使えよとか、スレッド周り適当じゃね？とかまぁいろいろあるんですが分かりやすさ重視ということで。

通信にはjsonを使いました。

基本的な動かし方

1import kademlia_tcp
2kademlia_tcp.DEBUG = True
3n = kademlia_tcp.KademliaNode("ip address", port)
4n.join(n)
5remote = kademlia_tcp.ContactNode("ip address", port)
6n.join(remote)

という感じでネットワークを作れます。DEBUGをセットすると、通信情報など、様々な情報が出力されます。あとは

1key = n.hash("key")
2n.publish(key, "value")
3n.find_value(key)
4n.ping(other_node)
5n.store(other_node, key, value)
6n.find_node(other_node)

というようなメソッドが使えます。

動かしてみて

ローカル環境でですが、100ノードほどで動かしてみました。元論文以外には特にchurnの対策はしてないのですが、そこそこ耐性があるんですね。3スレッド、0.1秒間隔で参加と脱退を繰り返したのですがちゃんとpublishしたものが取得できました。もうちょっとchurn対策をすればかなり使えそうだな、と感じました。

ルート探索は今回はTCPなのですが、そもそもKademliaは反復的探索なのでこの部分はやはりUDPにしてしかるべき、だなとも思いました。現実的にはルート探索などではUDPを使って、FIND_VALUE(値の取得)ではTCPにするなどの併用が一番現実的っぽいかなあ、とも感じました。

というわけで

P2P実装楽しいですね。実際のマシンで実験できる環境があればもっと楽しいんでしょうけど。

comments powered by Disqus