分散探索木

今日は、新幹線に往復で5時間ほど乗っていて暇だったので、分散ハッシュテーブルの実装について考えてみてた。
もともと基礎知識が薄いのに、なにも参考がない環境で、しかも5時間で決めるのはどうかと思うが、なんとなく考えた。
で、どうもこれは(俺の思っている)ハッシュテーブルというより、ハッシュ値をキーにした探索木の気がしたので、本当の木構造で、どうにかできないかと考えた末、思いついた仕組み全体を評価するとまったくもって現実的じゃーないと思った。
ただ、個々の機能ではそこそこ今後使えそうなネタを思いついたので、これだけは価値があった。
んで、それというのは、深くは書かないけど概要的には以下のようなものたち。

  1. ハッシュ値の管理担当を決めるアルゴリズム(誰かどの範囲のハッシュ値を管理するか)にノードの足の数+1進数を使って桁単位で管理すれば楽
  2. 木構造にするとルートや節に負担がかかりすぎなので、そのままじゃぜんぜんだめ
  3. 木構造にするなら回線速度の速いノードを上に持っていく
  4. 検索は、ネットワークを直接検索するのではなく、ある程度集めたノード情報から検索シュミレートを行って、その結果を少し戻った時点から検索を開始すると実ネットワークの負担が少なくて、そこそこうまく動くはず
  5. 各ノードは単なる構造体ではなく、高度な処理機能を備えている
  6. ミラー構造を作って節ノード離脱時の回復処理中でも検索できるようにする
  7. 「検索ワード」で検索する探索木なら、ハッシュ値は小さくてよい(検索ワード自体が平均8バイト程度なのに、20バイトのハッシュ値を使うのはバカけてる)