分散探索木の妄想はとりあえずやめようか
例の新幹線の中で考えていた妄想を妄想し続けているのだけど、なかなかうまくいかないので、いつまでもこんなことをかんがえていてもらちがあかん！と思って、先に既存のDHTについて勉強して、１つ実装を作ってみようと思う。
んで、いちおうここ２，３日で考えたことを最後に書いとく。
- 追記
10行くらいでやめようと思ったら、えらいだらだら書いてしまった。
よろしければ下技術者のたわごとをご覧ください。
＠ 木
まず、検索と聞くと真っ先に木が思いついた。
で、木構造でハッシュ空間をどう表現するのか、どう検索するのか、どうネットワークを維持するのかということを考えた。
＠ 定義とか
木は４本足。（これはテキトウ。丈夫にするなら２がいいのだけど、効率と負荷を考えると多いほうがいい感じ）
ハッシュ値は0-0xffffの16bit。（これもテキトウ）
＠ 木の構築とハッシュ空間
まず、ネットワークは0から始まることを想定した。
同時に数千個のノードが生まれたとしても、その時点では１つ。
そのため、その時点で各ノードは全てのハッシュ空間をサポートしているルートになる。
次にすることは、どこからとも無く手に入れた初期ノード情報を元に、接続先を選択して、別のノードに接続する。接続される側のノードは接続される。
まず、世界にA,Bという2ノードしかいない状態を考えた。
A <- B
AとBは、生まれた時点では0-0xffffのハッシュ空間をサポートしている。
Aはノード情報を持っていないからボーとしている。
BはAのノード情報を持っていたのでAの足1へ接続した。
Aは4つの足を持っていて、各足には自分の管理するハッシュ空間(=0-0xffff)/足の本数(=4)の空間が割り当てられている。
つまり、A(0-0xffff) A.足1(0-0x3fff) A.足2(0x40000-0x7ffff) A.足3(0x8000-
0xbfff) A.足4(0xc0000-0xffff)となっている。
Bは、A.足1へ接続(connect)した。このとき接続認証が行われ、その足が0-0x3fffをサポートする足だと知らされると、Bは(0-0x3fff)をサポートするノードとなる。
Bに接続されたAは、自分の足1にBが接続したことを確認すると、自分のサポートするハッシュ値の範囲を空いている足2,3,4の0x4000-0xffffの空間に変更し、0-0x3fffに関する情報をBへ受け渡す。分割が起きた。
そこへノードC、D、Eが生まれた。
同様に、ノードC、D、EがノードAに接続するとAは自分の管理するハッシュ空間を受け渡し、全ての足に接続を受けた時点で何も管理しなくなる。
この仕組みは再起していて、B、C、D、Eも４つの足ノードであり、各足に自分の管理するハッシュ空間/足の本数を割り当てており、接続があるたびに管理空間を受け渡す。
これで、木の構築とハッシュ空間の分割がきれいに行える。
＠ 突然だけど木の構造
木というと１つのルートから始まって、ノードが下に広がっているものを想像するのだけど、この木の場合、上に広いハッシュ空間を割り当てているため、上層ノードの離脱によって構造が大きく壊れてしまう問題がある。
そこで、木の上層ほど多くのミラーをつくり、全体として各層のノード数を同じかかなり近い数に保つ。
次のようになる。
2
2 2
2 2 2 2
2 2 2 2 2 2 2 2
わかりにくいけど、これは4層ある普通の２分木の図。「2」はノード。
これを次のようにする。
4 4 4 2 4 4 4
4 2 4 4 2 4
2 4 2 2 4 2
2 2 2 2 2 2 2 2
「4」が増えた。「4」は隣りや近所の「2」のミラーであり、隣の「2」に繋がっている上と下のノードへ同じように接続を張っている。これで「2」が突然いなくなった場合も「4」が代わりに働くことができる。もちろん、減ったノードがあれば、そこを復旧するために、新規ノードや、下のほうにいるノードを上に持ってくる努力をする。
これは、検索時にルートに集中する負荷の分散にも役立つ。
// 具体的にどうするかはまだ考えてない
＠ 木のマージ
木の構築で述べたとおり、ノードは生まれ瞬間は全てルートである。
世界に木が１つということは考えにくく、同時にいくつもの小さな木がネットワークに多数登場することになる。
ここで、木2、木3 があるとして、偶然にも木2に属するあるノードが木3の情報を入手し、その情報ーを木2のネットワークに流してしまったものだから、ノードの離脱による接続復旧時に木3に接続するノードが出てくる。こうなると、各ノードは自分がどのネットワークに所属するのかという意識が無いから、木2と木3は、そのうちマージされるか、破壊される可能性が出てる。
これは、木の再構築をどうするのかに依存する話なのでここでは問題だけを挙げて、放置しておく。
// 具体的にどうするかはまだ考えてない
＠ ノード情報と検索の関係とか
ノード情報とはIPアドレス、ポート番号、管理するハッシュ空間(開始-終了)、状態フラグの32バイト程度のデータで、これ1つが1ノードを表す。
各ノードのは、このノード情報を交換しつつネットワーク上に拡散する。
方法は次のようなもの。
Ⅰ. 経路取得要求1
1. 各ノードは定期的に木の上層に向けてノード情報取得要求を投げる
2. ノード情報取得要求を受けたノードはそれに自分のノード情報を付加してさらに上に投げる
3. この要求は発信元から6ホップするとたどった順に送信元まで返ってくる
これで、各ノードは6ホップ上までノード情報を保持することになる。
次はこの仕組みにもう１つ条件を追加する。
1. スキップ数を指定する
各ノードは自分の6つ上のノードまで経路情報を既に持っているから、最大6つスキップすることができる。
例えば、スキップ数=6の要求は、6つ先のノードに送信され、さらにそのノードから6つ先のノードに送信され･･･と、6つ飛ばしで36つ先の上層ノードまで到達する。
36つ上層というのは、木の高さにすると非常に大きな数値で、4本足の木なら10つ上層が存在する時点で、全体で100万ノードを超えている計算になるから実際はもっと少ないスキップ数で最上層まで届く。
ここまでで、とりあえず木のルートから検索を開始できる状態になったはずである。前述の通り上層ほど多くのミラーが存在するので、少数のノードに負荷がかかりすぎることは無いが、もう少し負荷を下げる方法を考える。
I. ノード情報の拡散
ノード情報は、32バイト程度である。これは非常に小さい。ざっと計算してみよう。50万ノードの情報でたったの16メガバイト。メモリに保持するのはきついけど、外部DBに吐き出せば100万ノード(32MB)の情報を全てのノードが保持することも現実に可能である。
ということでー、ノード情報を積極的に分散してかき集める。
対象としてはできるだけ上層のノード情報を重複なしで集める。
これは、経路取得と同じ方法で行う。違いは、経路取得では、自分のノード情報のみを返したが、この場合は自分の保持するノード情報をいくらか付加する。
この付加するノード数は、始点から近い距離ほど多くのノード情報を付加するパターンと、逆に始点から遠い距離ほど多くのノード情報を付加するようにするパターンを作る。前者の方法で各ノードは自ノード周辺の情報を収集しておき、後者の方法で最上層-上層部周辺のノード情報を得る。
理想は、木の高さの半分より上の全ノード情報を全のノードが保持すること。
木の上は、ミラーが沢山いるのだけど、それは結局ミラーなので、実質検索に必要なノードは上にいくほどかなり少ない。
2分木の場合、全体で100万ノードいるとすると、最下層だけで、50万ノードいることを考えると、4本足の木の場合は高さの半分より上は、その下に比べて格段に少ない検索経路しか存在しないはず。
んで、これで、実ネットワークを検索することなく半分まで検索することができる。
各ノードは保持するノード情報から、検索経路をシュミーレートし、その結果から実ネットワークへ検索クエリを投げる位置を決定させる。そして検索クエリを投げると。
＠ 妄想おつ！
あと、木の再構築に関して云々あるんだけど
妄想は永久に広がりそうなのでもうやめます。
実際、作ろうとしていたんだけど、実装できない問題がいくつかあるから、既存をみようと思ったわけで、こりゃぜんぜんだめですわ！
とりあえず、既存のDHTを勉強してから出直します。
