Erlangで分散ハッシュテーブルを実装してみた
並行言語であるErlangでPeer-to-Peer Network技術の一つである分散ハッシュテーブルを実装してみたところ，わずか1000行程度で実現できました．ノードが頻繁に出たり入ったりする，いわゆるchurn下でもそれなりの性能が出せたので，SourceForge.netで公開してみます．興味のある方はどうぞ．
http://sourceforge.net/projects/ermdia/
内部アルゴリズムはKademliaと呼ばれるものを利用しています．BitTorrent等でおなじみのアルゴリズムですが，データのput/getなどの通常のメッセージの交換時にルーティングテーブルをアップデートするため，ルーティングテーブルの維持コストがChord等に比べて低いという特徴があります．実装もそれなりに簡単で，過去にSymphonyと呼ばれる分散ハッシュテーブルを実装したのですが，それと比較しても，割と簡単でした．SymphonyをErlangで書いたら，もうすこし行くかなと思います（といっても，2000行ぐらいには収まると思う）．
C++とpthreadを駆使してSymphonyを書いたときは，1万行以上となり，想像通りスレッド関連のバグに悩まされましたが，Erlangではそれが（ほとんど）無くなり，非常に書きやすかったです．というわけで，Erlangおすすめですね．
以下，簡単な使い方の説明です．利用する前に，Erlangをインストールしておいてください（Ubuntuならaptを，MacならMacPortsを，NetBSDならpkgsrcを使えば簡単にインストールできます）．
1. 解凍して，cd
$ tar xzfv ermdia-1-0.tar.bz2
$ cd ermdia-1-0
2. コンパイル
$ make
3. bootstrapノードを起動
$ erl
1> ermdiacmd:start(5000).
4. 別のターミナルを立ち上げ，bootstrapノードに接続．
$ cd ermdia-1-0
$ erl
1> ermdiacmd:start(5000).
boot: Port = 5000
ok
2> ermdiacmd:join("localhost", 5000).
join: true
ok
という感じですが，たくさんノードを立ち上げるのは面倒なので，シェルスクリプトで起動させます．
5. 一度，erlangを終了させる
6. シェルでたくさん起動する
$ sh test.sh
とすると，1000のノードが起動します．ちなみにbootstrapノードは10000番のUDPポートを利用しています．シェルスクリプトを見れば分かりますが，1プロセス（OSでのプロセス）あたり100ノードとして，10プロセス立ち上げているので，1000ノードとなります．
7. 別のターミナルから，P2Pノード群に接続してみます
$ cd ermdia-1-0
$ erl
1> ermdiacmd:start(5000).
boot: Port = 5000
ok
2> ermdiacmd:join("localhost", 10000).
join: true
ok
8. データをput/getしてみます
3> ermdiacmd:put(100, 12345, 0). （100がKey，12345がValue，0がTTLとなります．ただし，TTL=0=無限大です）
{put,100,12345,0}
4> ermdiacmd:get(100).
get: Key = 100, Value = {ok,[{{143,0},12345}]} （143はデータがputされてからの経過時間[s]，0がTTL，12345がValueです）
ok
9. routing tableを見てみます
5> ermdiacmd:showTable().
i = 157
ID = 545207221063968172702339833175659735809196458384, IP = {127,0,0,1}, Port = 10014
ID = 531700281791683267704722411754405405263524377045, IP = {127,0,0,1}, Port = 10029
ID = 402747861140875649571786943383543094387797431721, IP = {127,0,0,1}, Port = 10035
...
10. nodeをlookupしてみます．
6> ermdiacmd:findNodes(100).
findNodes: Key = 100, ID = 496920712945187554401028479396231470869897037805
Distance = 49624918250086289334925657393158177936153324144, ID = 546545277875838087843588537485386879604883287453, IP = {127,0,0,1}, Port = 10401
Distance = 83577740999949689912693301110593680155202738656, ID = 511879060163414043818802950145092314519084375565, IP = {127,0,0,1}, Port = 10503
Distance = 86474852523940031102040007130101417687518073825, ID = 503441465525022756552201471220151194574791676940, IP = {127,0,0,1}, Port = 10403
...
てなぐあいです．
