Skip Graph の concurrent JOIN を考える - その2

erlang

id:kibayos さんの PDF「構造化オーバレイの一貫性保証」 に書かれている Skip Graph の一貫性保証の例を読み解く。
http://live-e.naist.jp/sensor_overlay/3/doc/yoshida.pdf


その1の続き。双方向リンクリストに conncurrent Join / Remove する話。
その1 で述べたように下位レベルと当該レベルで、Join / Remove が発生する事を考慮しないといけない。
まずは Join から。


資料 P16 。
左側のノードをロックする事で実現。自分は「当該ノードの全てのレベル」をロックするものと解釈した。

[X] <-> [Y]

の 間に [A] を Join するケースを考える。


資料に書かれている手順は以下の通り。

  • step1. add A->X
  • step2. (lock at X)
  • step3. add A->Y
  • step4. change Y->X to Y->A
  • step5. change X->Y to X->A
  • step6. (unlock at X)


各 step で発生する conncurrent ならではの事象を考えてみる。

step1. add A->X

X がそのレベルで Remove されてしまうケース。
この場合は

  • 削除された事が分かる可視なフラグ
  • そのレベルでの A の隣接ノードを再度検索し、そのレベルで処理をやり直す必要がある。

step2 の lock を先にやっておけば問題ないのでは？。


[X] と [A] の間に下位レベルで Join が発生するケース。
step2 の lock を先にやっておけば問題ないのでは？。

step2. (lock at X)

  • ロック獲得失敗（誰かがロックしている）
  • X が削除された（これもロック失敗か）

が考えられる。この場合は wait するか、エラーを返す。
エラー処理が楽なのは wait 。


作業中に[X] と [A] の間に、ノードが Join する可能性があるので、ロック後に [X] の右が [Y] ではなかった場合、処理をやり直す。

step3. add A->Y

  • Y が削除される。
  • A が削除される

が起こる可能性がある。
Y が削除された場合はそのレベルでの Join を一からやり直す。


A が削除されるのは、検索で A が reachable な場所にいる場合。こういう場合はあるだろうか。
X, Y から A がリンクされていないので、そのような状況は発生しない。

step4. change Y->X to Y->A

[Y] が削除される可能性がある。この場合はそのレベルでの Join を一からやり直す。
[X] がロックされているので [Y] の左ノードが変更される事はない。

step5. change X->Y to X->A

A が削除される可能性がある。なぜならばそのレベルで　Y->A というリンクがあるから。
と思ったけど、X がロックされているので A の削除は失敗するはず。なので OK 。

step6. unlock

Ok

ロックの実現方法

Erlang の gen_server はリクエストが serialize される事を利用すれば良さそう。
State にロックしているプロセス（もしくはロックを待っているプロセスの一覧）を持っておき、link_op の際に参照し From とマッチングする。

まとめ

concurrent Join に必要な機能は

  • ノードのロック
  • insert 失敗のエラー通知
  • リトライの仕組み
    • どこにいれるべきか？大本の Join 司る部分かな。

の 3 つ。


その 3 に続く。