inforno

しました。

ダウンロード

yahooapi

使い方

うむ。

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

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

本家Kademliaとの主な違いは

• UDPではなくTCPを使っている
  • ローカル環境しかもっていないので、UDPパケットがロスしやすい場合(WAN)を想定して実装するのがめんどくさい。
  • よってRPC-IDをつけていない。
  • パケットの分割や再送もTCPにおまかせ。
• original publisherから一定時間publishを受けなくてもインデックス情報をexpireしていない
  • 実装するのは簡単です。
• ノードがネットワークに参加したとき、Index情報を移動させていません
  • これも実装は簡単です。

ダウンロード

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

• kademlia_tcp.zip

実装について

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

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

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

基本的な動かし方

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

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

動かしてみて

ローカル環境でですが、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 %>でフィルターをオフにできます。

    python code

    1. Embpy("<%= b %>", filter=cgi.escape).render({"v":"<b>"})
    2. # => "<b>"
    3. Embpy("<%=r b %>", filter=cgi.escape).render({"v":"<b>"})
    4. # => "<b>"
    5.  
    6. result = Embpy("<%=r b %>", filter=cgi.escape).render({"v":"<b>"})
    7. # result.__class__ => EmbpyString
    8. Embpy("<%= b %>", filter=cgi.escape).render({"v":result})
    9. # => "<b>"
    10.  

  • 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の代わりに<% %>も使えるようにしました。

     code

    1. <%- if True: -%>
    2.    ok
    3.    <% %>
    4.  

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

• 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引数にはファイルではなく文字列も渡せます。

出力はこう。

ダウンロード

embpy

コード

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

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