Skip Graph の concurrent JOIN を考える - その1
id:kibayos さんの PDF「構造化オーバレイの一貫性保証」 に書かれている Skip Graph の一貫性保証の例を読み解く。
http://live-e.naist.jp/sensor_overlay/3/doc/yoshida.pdf （PDF）
探索処理は任意のタイミングで実行可能
資料 P14 。
- Join は下位レベルから上位へ
- Remove は上位レベルから下位へ
なので上位から下位に検索する処理には影響がないとの事。
直感的に理解できなかったので具体例を考える。
各レベルでの処理は atomic であると仮定する。
以下のような初期状態の Skip Graph に対して [10] をスタートに key = [9] で検索。
level1: [5]<->[15] [7]<->[10] level0: [5]<->[7]<->[10]<->[15]
この状態では検索結果はない。
key = [9] が Join の途中でレベル 0 にのみに Join された以下の状態のとき。
検索結果はないが、「他の検索には一切影響がない」。
level1: [5]<->[15] [7]<->[10] level0: [5]<->[7]<->[9]<->[10]<->[15]
つづいて Remove 。上位レベルだけで [7] が Remove された状態。
level1: [5]<->[15] [10] level0: [5]<->[7]<->[10]<->[15]
問題なく検索できる。
各レベルでの操作が atomic であれば検索には影響ないことが理解できた。
レベル単位の処理を atomic にできる
資料 P14 。
前提は「一貫性保証のために、処理を小さく分けたい」というモチベーション。この場合「 atomic にできる」とは、同一 key の別レベルの操作も atomic にする必要がないという意味だと思う。
Join / Remove ともに
- リンク更新のための情報取得（Buddy は誰？とか）
- 各レベルでリンク更新
という順序で行われる。
Remove はレベル単位の処理を atomic にできる？
資料には「自明」とある。考えてみよう。
Remove は上位レベルからスタートし、各レベルで左右のリンクを切って Graph から離脱する。
各レベルでの処理は「そのレベルの左右のノードしか参照しない」という特徴がある。つまり別レベルでの処理に依存しないので atomic にできる。
Join はレベル単位の処理を atomic にできる？
資料には「addKeyの場合は、挿入ポイントを下位レベルの処理後に決定（調整）することで可能になる」とある。
これはつまり、Skip Graph の Join アルゴリズムそのままで、下位の Join が終わってから、下位の buddy を探す方法を指しているのだと思う。
まずは単純な例。 level0 に [9] が Join された状態。level1 の Join は level 0 を参照して正しく行われる。
level1: [5]<->[15] [7]<->[10] level0: [5]<->[7]<->[9]<->[10]<->[15]
次に [9] が level0 に Join 後、level1 に Join されるまえに [10] が削除された場合。
level1: [5]<->[15] [7]<->[10] level0: [5]<->[7]<->[9]<->[15]
level1 の Join 時には、level0 の buddy が検索されるのだが、正しい buddy [5] が見つけられるので OK 。
その2 に続く。
