Kademliaについて細かい話

id:cooldaemonさんがErlangでKademlia実装をおこなったようで（http://d.hatena.ne.jp/cooldaemon/20080922/1222050692），ちょっとソースを眺めてみました．いくつかコメントがあるため，ブログのコメント欄に書こうと思ったのですが，結構長くなるので，こちらでコメントさせていただきます．ご容赦ください．

ざっと見た感じ，gen_serverなどをきちんと使ってあって，非常に良くできていると感じました．このままいくと，自分のよりも良いモノが出来上がりそうです．まぁ，何ヶ月も放置しておいて言う事じゃないんですけど．．．

とまぁ，そう言う話はいいとして，本題に移ります．Kademliaは基本的にUDPをつかって通信を行っています．TCPを利用していれば，コネクション管理などをやってくれるため，向こう側のノードが切断したことなどを発見することが出来ますが，UDPだとそうはいきません．これは実は，ルーティングテーブルの保持に問題が出てきて，ルーティングテーブルのアップデートが行われなかった場合，いつまでも，存在しないノードの情報を保持し続けてしまいます．

これを防ぐために必要なことは二つあります．

1つ目は，getやfind_nodeを行った際にタイムアウトが発生した場合，自分のルーティングテーブルからそのノードの情報を削除することです．こうすることで，いち早く不要な情報を削除することが出来ます．逆にこれを行わないと，いつまでも古い情報を使ってlookupしてしまうため，非効率的です．

2つ目は，タイムアウトが発生したノードの情報を保持しておくことです．自分のルーティングテーブルから削除を行っても，他のノードが古い情報を保持したままの場合，その古い情報を元にlookupを行う可能性があります．これを防ぐため，find_nodeなどを行うときは，結果として得られたノードから，タイムアウトしたノードを除く作業が必要となります．また，このタイムアウトしたノードの情報も，いつまでも保持しておく訳にはいかないので，一定時間後にexpireしてやる必要があります．

これらを行わないと，ある条件下では劇的にパフォーマンスが低下してします．これらは，元の論文には書かれていないため，ちょっとわかりにくかったかも知れません．ソースをちょっと見た感じ，無かったようなので書いておきましたが，もしかして見落としていただけならすいません．

あと，ついでに，実は，タイムアウトは3秒とかとしてありますが，Kaiのようなクローズドな環境を想定しているなら，1秒以下，500ミリ秒とかでも十分な気がします．事実，ダイレクトリンクなどでは，数ミリ秒から数十ミリ秒で応答が帰ってくるので，3秒のタイムアウトは長すぎのように思えます．

こういうことは，ちゃんと論文にして書いた方がいいんだろうなぁ・・・
しかし，論文書くよりブログの方がより早く広く伝わるという罠．