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

erlang

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


その2の続き。双方向リンクリストに conncurrent Join / Remove する話。
続いて Remove 。以下の状態から [A] を削除する。

[X] <-> [A] <-> [Y]

資料にある手順は以下の通り。

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

step1. (lock at A)

A がそのレベルで削除されている場合。何もせず処理を返す。
ロックが失敗した場合、wait する。ロックが獲得できたら、両隣が X, Y ではなくなっているかもしれないが気にしない。

step2. (lock at X)

ここでの X とは A の左という意味で、元の X とは違う可能性がある。
A がロックされているので X が削除される事はない。
X がロックされている場合は wait する。


これデッドロックすると思う。

[X:locked by hige] <-> [A:locked by foo] <-> [Y]

同時期に X と A の間に B を Join している場合、X がロックされているため、wait が発生する。
hige は hoo がもつ A のロック解放を待ち、foo は hige の X ロックを待っていてデッドロックしそう。
これを防ぐには A を unlock して、少し寝て A のロックからやり直す事で防げる（複雑だなあ）

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

A がロックされているので Y が削除される可能性はない。

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

X がロックされているので問題ない。

step5. (unlock at X)

問題ない。

step6. remove A->X, A->Y

問題ない。

step7. (unlock at A)

問題ない

所感

Join / Remove の混在によるロックが複雑になり、自分の理解に考慮漏れがありそう。
きちんと Formalize? して検証した方が良い気がする。既に存在してそうだけど。どうだろうか。

あとなぜ、X, Y 両方ともロックしないかも理解できていない。