SimpleRoutingAlgorithm (r2435), SimpleIterativeRouter (r2432)
KademliaっぽいDHTの実装をしたのだけど、先日のテストの時に
ノードが離脱するとDHTのGetがすぐに失敗するという不具合が。一応、複製数3でやってるのに･･･
原因を調べてみたら、ルート候補を取得する部分に問題があった。
ルーティングテーブルには 2^i<=key<2^(i+1) (0<=i<160) の範囲のキーを格納する入れ物があるんだけど
その入れ物には数個のノード情報しか入れないようになっている。
担当ノードを見つける普通のルックアップではこれで十分なんだけど、
担当ノード候補を見つけなければいけないDHTの場合は、これでは必ずしも
検索キーに近いノードから順に選出されるとは限らなくなる。
なぜならルーティングテーブルの入れ物にはその範囲の適当なノードしか入っていないので、
一番近いノードの情報が入れ物に入っていない可能性が十分あり得るからだ。
これを解決するには、Kademlia擬きのアルゴリズムを使っている現状では、
サブツリーに対して検索をかけるしか方法が無いように思える。はぁ･･･
これが所謂範囲検索ってやつに相当するんだろうか？