Multi-key Skip Graph の仕組みを学ぶ

kvs

「単一ピアに複数キーを保持可能とするSkip Graph拡張の提案」という論文で提案されている Multi-key Skip Graph を学ぶ。
大変苦労して読み解いたので、以下にまとめた事は間違っている可能性が高いので注意。
誤りがありましたらぜひご指摘ください。

背景

Skip Graph は 1 ノードに 1 (key, value) を保持する事が前提のアルゴリズム。
これでは効率の良い Key-value storage として使えないので 1 ノードに複数の (key, value) を保持できる Multi-key Skip Graph アルゴリズムを導入したい。

Multi-key Skip Graph

論文の解説を補うまとめ。

  • 2 つの大事なポイントがある
    • 1. 物理ピア毎に membership vector が発行される
      • これにより各レベルでの検索が同一物理ピアで行われる事が保証され効率が良い
    • 2. Range Search のときにのみ、物理ピアを意識したテクニックが必要とされる
  • 論文中に「検索範囲を仮想ピアによって分けられる部分領域に分割し、各部分領域毎にクエリを送る」が分かりづらかった。
    • 検索範囲 [1, 6] を部分領域1, 2 に分けるとは、membership vector 00 において見つかった [1, 6] にマッチする仮想ピア 1 -> 3 -> 6 において、1 と 3 の間、3 と 6 の間に別の物理ピアの仮想ピアがあるかもしれない事を考慮することを意味する。
    • つまり [1, 3]、[3, 6] というクエリを別の物理ピアに投げてクエリを完結させる。

論文では触れられていない事

  • 通常の key 検索
    • 仮想ピア内で隣接ペアを探す。あとは Skip Graph と同様。
  • membership の発行
    • 新たな物理ピアの追加時に membership vector を発行する
    • 現在の最大 membership vector を問い合わせる仕組みが必要そう
    • ここはかなり理解が怪しい。
  • 検索スタート時のノードはどうやって見つける？適当な物理ピアを指定してそこからランダムに選択。
  • ノード（仮想ピア）の追加
    • introducer が membership vector を発行し該当物理ピアに追加
  • 通常の key 検索で物理ピアに無駄なクエリが行かないか
    • 行かない