前々から一度じっくり勉強しないとなぁと思っていた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実装楽しいですね。実際のマシンで実験できる環境があればもっと楽しいんでしょうけど。

更新履歴

  • 2009/02/20 version 1.0.0

    • Renderer と Helper を追加。詳しくはソースファイルヘッダ部分のドキュメントを参照してください。

  • 2009/02/17 version 0.5.0

    • <%= %> で自動的にフィルタを適応できるようになりました。また、 render メソッドが unicode オブジェクトではなく unicode のサブクラス EmbpyString オブジェクトを返すようになりました。filterは EmbpyString オブジェクトをスルーします。これにより2重でfilterが適応されることがなくなります。<%=r %>でフィルターをオフにできます。
1Embpy("<%= b %>", filter=cgi.escape).render({"v":"<b>"})
2# => "&lt;b&gt;"
3Embpy("<%=r b %>", filter=cgi.escape).render({"v":"<b>"})
4# => "<b>"
5
6result = Embpy("<%=r b %>", filter=cgi.escape).render({"v":"<b>"})
7# result.__class__ => EmbpyString
8Embpy("<%= b %>", filter=cgi.escape).render({"v":result})
9# => "<b>"

  • re.Scanner の scan メソッドがスレッドセーフだったのでインスタンスをモジュールグローバルにしました。また、 re.Scanner インスタンスの初期化をLazyにしました。このことにより re.Scanner インスタンスの生成数が減り、さらにキャッシュのみの利用時にはインスタンスを生成しないのでパフォーマンスが向上しました。

  • 2009/02/16 version 0.4.0

    • パフォーマンス改善

  • 2009/02/15 version 0.3.0

    • epy の中の人から「end.. orz」という反応をいただいたので、endの代わりに <% %> も使えるようにしました。
1<%- if True: -%>
2   ok
3   <% %>

と書けるようになりました。

  • 2009/02/14 version 0.2.0
    • “{” と “}“が辞書リテラルとかぶっていたので、”{:“と”:}“に変更しました。
    • 変換後コードでなく、コンパイル済みcodeオブジェクトをキャッシュするようにしました。

はじめに

このブログはweb.pyで作られており、テンプレートエンジンもweb.py標準のものを使っています。でもこのweb.pyのテンプレートエンジン、罠が多い。なので他のテンプレートエンジンに置き換えようかなあ、とか思ってました。

んで個人的にはわざわざテンプレート用に文法覚えるのはめんどいので、埋め込み形式でコードが短くて軽そうなのはないかと探したところ、 epy がヒット。

ただ、この実装 %> が文字列の中にあると動かなかったり( a= "hoge%>" みたいな)、コードの短さゆえに割り切っている部分が多いので同じくらい短いコードでもうちょっと高機能版を実装してみました。以前紹介した re.Scanner を活用すれば、見やすいコードで短く実装できました。

  • キャッシュ
  • インラインでPythonを書くことも出来る: def format(v) {: return "%4d"%v; :} みたいに。
  • eRubyのtrim modeの”<%-“と”-%>” : これがあると無いではテンプレートの見易さが段違い。
  • 自動的にフィルタを適応。しかも2重でフィルタが適応されない。
  • もちろんマルチバイトでも大丈夫。

といったところが特徴ですかね。

例

テンプレートはこんな感じにかけます。

 1<%-
 2class Hoge(object):
 3  def __init__(self):
 4    pass
 5  end
 6end
 7hoge = Hoge()
 8a = "< title >"
 9-%>
10<%=r a %>
11<%- def format(v) {: return "%4d"%v; :} -%>
12<%- def format2(v) {: return "%2d"%v; :} -%>
13  <% for y in xrange(1,xx):%><%= format(y) %><% end %>
14<%- for x in xrange(1,xx): -%>
15<%= format2(x) -%>
16  <%- for y in xrange(1,xx): -%>
17<%= format(x*y) -%>
18  <%- end %>
19<%- end -%>

んでこんな感じに使います。第1引数にはファイルではなく文字列も渡せます。

1e = embpy.Embpy(codecs.open("path_to_template", encoding="utf8"),
2          cache_path = "path_to_cache_file",
3          template_globals = {}, filter=cgi.escape)
4print e.render({"xx": "10"})

ダウンロード

embpy

コード

先読みはいらないので、 re.Scanner で一発。

あと "(((?<=\\)")|[^"])\*((?<!\\)")" という正規表現は自分的には常套句。“で囲まれていて\“は"自身を表す、というよくある文字列の仕様に使える正規表現です。

やんごとなき事情によりxrea内でWEBサーバを移動しました。

というわけで、このブログ(web.pyによる自作ブログ)を移したわけですが、今までのようにバイナリ化して動かすにはサーバと似た環境が手元にないといけません。が、移動した先のサーバでは環境がだめ。

ということで、python2.5をxreaにインストールしました。virtual-pythonもいいんですが、xreaのサーバはpython2.4なので。ちょっと工夫すれば入るし、快適ですね。以下作業ログ。

Pythonをインストール

まずはPythonのソースをダウンロードしてコンパイル。 ~/root/usr/local にいれます。

1mkdir -p ~/root/usr/local/src
2cd ~/root/usr/local/src
3wget http://www.python.org/ftp/python/2.5.4/Python-2.5.4.tgz
4tar zxvf Python-2.5.4.tgz
5cd Python-2.5.4
6./configure --prefix=~/root/usr/local
7make
8make install

サクっと入ります。で、次にeasy_installを入れるわけですが、はいりません。OpenSSLとの絡みで hashlib.md5 が使えないから。 easy_install を入れるときに md5 を検証するのに使ってるんですよね。

hashlibをインストール

なんで、自前でhashlibを単体でいれます。

1cd ~/root/usr/local/src
2wget http://code.krypto.org/python/hashlib/hashlib-20081119.tar.gz
3tar zxvf hashlib-20081119.tar.gz
4cd hashlib-20081119
5vi setup.py

はい、 setup.py を編集しましょう。普通にbuildするとこれでも md5 が入りません。

 1105　　 if (ssl_inc_dir and
 2106　　　　 ssl_lib is not None and
 3107　　　　 openssl_ver >= 0x00907000):
 4108
 5109　　　　 print 'Using OpenSSL version 0x%08x from' % openssl_ver
 6110　　　　 print ' Headers:\t', ssl_inc_dir
 7111　　　　 print ' Library:\t', ssl_lib
 8112
 9113　　　　 # The _hashlib module wraps optimized implementations
10114　　　　 # of hash functions from the OpenSSL library.
11115　　　　 exts.append( Extension('_hashlib', ['_hashopenssl.c'],
12116　　　　　　　　　　　　　　　　include_dirs = [ ssl_inc_dir ],
13117　　　　　　　　　　　　　　　　library_dirs = [ os.path.dirname(ssl_lib) ],
14118　　　　　　　　　　　　　　　　libraries = osNameLibsMap[os.name]) )
15119　　 exts.append( Extension('_sha', ['shamodule.c']) )　　　　　　　　　
16120　　 exts.append( Extension('_md5',　　　　　　　　　　　　　　　　　　
17121　　　　　　　　　　 sources = ['md5module.c', 'md5.c'],
18122　　　　　　　　　　 depends = ['md5.h']) )

119-120あたり、強制的に _md5 を入れるようにします。あとは

1~/root/usr/local/bin/python setup.py build
2~/root/usr/local/bin/python setup.py install

で hashlib が入ります。

easy_installをインストール

これで md5 が使えるようになったので

1cd ~/root/usr/local/src
2wget http://peak.telecommunity.com/dist/ez_setup.py
3~/root/usr/local/bin/python ez_setup.py

これで無事 easy_install が入ります。あとは

1~/root/usr/local/bin/easy_install -U -Z MySQL_Python

てな感じで必要なモジュールを入れていきましょう。

というわけで

わりと普通にxreaでPythonが使えています。