昨日の続き，KademliaもどきのDHTの実装の問題
これらのメモのまとめ。
まず、上の図のようなネットワークを想定する。ノードは0011, 1000, 1100, 1111の四つがネットワークに参加していて、ノード0011のルーティングテーブルには距離(1000)2以上(10000)2未満として1000の情報が登録されている。このルーティングテーブルの状態は整合性が取れており、なんら問題はない。
そして、ルート候補選出数を2として0101を検索すると、0011が ルートノードとして選出され、ルート候補として、1000が 選び出される。
しかし、実際に候補として相応しいのは 距離が(1101)2となる1000ではなく、距離が(1001)2と(1010)2 となる1100と1111なので、もし0011が離脱した場合 1000に保存されたDHTの複製データには到達することができない。
こうなる可能性は結構低いと思ったんだけど、複製のうち1つが想定するノードに到達するのが大体8割ぐらい？、二つ目は5割未満ぐらいなんで、churnも発生する実環境だと、複製はあまり意味を成さなくなるのかなぁ。実際、先日の数ノード程度の小規模ネットワークのテストでも1ノードが離脱した後にDHTのgetが再putされるまで成功しないという現象が、比較的多く見られたので・・・
授業が18時までだから、結構厳しいぜ･･･というわけで、実家に帰るのは明日の朝に変更っと。
僕のDHT実装のバグについて考えたんだけど、
検索するキーの担当ノードが見つかったら、候補ノードを探すためにまた探索しなくちゃいけない。
おそらく1～3回ぐらいの問い合わせが必要なんだけど、この問い合わせはKBR層でやるべきなのかなぁ。
とか思ったり思わなかったり。
なので、問い合わせのタイムアウトも実装しなくちゃなとか思いつつ、実家に帰るので当分お休みっと。