前々から一度じっくり勉強しないとなぁと思っていた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を使いました。

基本的な動かし方

import kademlia_tcp
kademlia_tcp.DEBUG = True
n = kademlia_tcp.KademliaNode("ip address", port)
n.join(n)
remote = kademlia_tcp.ContactNode("ip address", port)
n.join(remote)

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

key = n.hash("key")
n.publish(key, "value")
n.find_value(key)
n.ping(other_node)
n.store(other_node, key, value)
n.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

    • RendererHelper を追加。詳しくはソースファイルヘッダ部分のドキュメントを参照してください。
  • 2009/02/17 version 0.5.0

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

result = Embpy("<%=r b %>", filter=cgi.escape).render({"v":"<b>"})
# result.__class__ => EmbpyString
Embpy("<%= b %>", filter=cgi.escape).render({"v":result})
# => "<b>"
  • re.Scannerscan メソッドがスレッドセーフだったのでインスタンスをモジュールグローバルにしました。また、 re.Scanner インスタンスの初期化をLazyにしました。このことにより re.Scanner インスタンスの生成数が減り、さらにキャッシュのみの利用時にはインスタンスを生成しないのでパフォーマンスが向上しました。
  • 2009/02/16 version 0.4.0

    • パフォーマンス改善
  • 2009/02/15 version 0.3.0

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

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

  • 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重でフィルタが適応されない。
  • もちろんマルチバイトでも大丈夫。

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

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

<%-
class Hoge(object):
  def __init__(self):
    pass
  end
end
hoge = Hoge()
a = "< title >"
-%>
<%=r a %>
<%- def format(v) {: return "%4d"%v; :} -%>
<%- def format2(v) {: return "%2d"%v; :} -%>
  <% for y in xrange(1,xx):%><%= format(y) %><% end %>
<%- for x in xrange(1,xx): -%>
<%= format2(x) -%>
  <%- for y in xrange(1,xx): -%>
<%= format(x*y) -%>
  <%- end %>
<%- end -%>

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

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

ダウンロード

embpy

コード

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

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


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

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

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

Pythonをインストール

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

mkdir -p ~/root/usr/local/src
cd ~/root/usr/local/src
wget http://www.python.org/ftp/python/2.5.4/Python-2.5.4.tgz
tar zxvf Python-2.5.4.tgz
cd Python-2.5.4
./configure --prefix=~/root/usr/local
make
make install

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

hashlibをインストール

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

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

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

105   if (ssl_inc_dir and
106     ssl_lib is not None and
107     openssl_ver >= 0x00907000):
108
109     print 'Using OpenSSL version 0x%08x from' % openssl_ver
110     print ' Headers:\t', ssl_inc_dir
111     print ' Library:\t', ssl_lib
112
113     # The _hashlib module wraps optimized implementations
114     # of hash functions from the OpenSSL library.
115     exts.append( Extension('_hashlib', ['_hashopenssl.c'],
116                include_dirs = [ ssl_inc_dir ],
117                library_dirs = [ os.path.dirname(ssl_lib) ],
118                libraries = osNameLibsMap[os.name]) )
119   exts.append( Extension('_sha', ['shamodule.c']) )         
120   exts.append( Extension('_md5',                  
121           sources = ['md5module.c', 'md5.c'],
122           depends = ['md5.h']) )

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

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

hashlib が入ります。

easy_installをインストール

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

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

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

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

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

というわけで

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