Multi-key Skip Graph の改善を考えてみる

以下「単一ピアに複数キーを保持可能とする Skip Graph 拡張の提案 」という論文で提案されている Multi-key Skip Graph の話。論文は id:kibayos さんなどによって書かれたもの。
Multi-key Skip Graph の目的は、検索時に物理ピア同士の通信を減らす事。上位レベルの検索時にできるだけ同一物理ピアで探索が行われるようにしている。具体的には同一物理ピア内の仮想ピアは全て同じ membership vector を持つようにしているのだ。そうすれば最上位での検索は必ず同一物理ピアになるし、その下のレベルも同一物理ピアになりやすくなる。


ただ自分の用途では Multi-key Skip Graph はうまく使えなそう。なぜならば物理ピアの数が Max Level を決めてしまう仕組みだから。10万件の仮想ピアを3台で保持する場合を考える。最上位のレベルには 8 個のリストがあり、それらのリストは平均で 1.25 万件の要素を持つ。これでは検索のコストが大きすぎる。


改善案は「各物理ピアは自分が担当する複数の membership vector をランダムに仮想ピアに振り分ける」。
例えば Level 12 かつ物理ピア 3 台で運用するならば、各物理ピアは 2^12 / 3 個の membeship vector を自分の仮想ピアに振り分ける。
Level 2 で物理ピア 2 台なら「000,001,010,011」「100,101,110,111」と分けるのが良さそう。

次の一手

  • 物理ピア 2 台で試して速度を測る。

課題

  • 動的に物理ピアを増やしたときの、membership 振り分け戦略。