昨日の続き，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されるまで成功しないという現象が、比較的多く見られたので・・・
New Comment