write-all approach を解説する

執筆動機

日本語解説する文章があっても良いと思った．

参考

Philip A Bernstein, Vassos Hadzilacos, and Nathan Goodman. Concurrency control and recovery in database systems. 1987.

Write-all approach

Read(x) は Read(x_A) に変換され，x_A というのはサイト A の x の全てのコピーを意味する．Write (x) は {Write(x_A1), …, Write(x_Am)} に変換され， {x_A1, …, x_Am} は全ての x のコピーである．つまり Write(x) は全サイトにおける該当データに書く．

振る舞い

DBS は serializable concurrency control algorithm を使っているので，その実行は何か直列実行したものと等価となる．そのようなシリアル実行において，各トランザクションは x データへの書き込みが，x のコピー全てに対する書き込みとなる．シリアル実行における次のトランザクションビューにおいて，全ての x のコピーは同時に書き込まれたようになる．それゆえ，次のトランザクションがどのコピーを読むとかは関係ない．なぜなら，どれを読んでも同じ値であるし，その値は直前のトランザクションが全ての x のコピーに対して書き込んだ値と一緒であるから．それゆえ，実行はまるでシングルコピー DB に対して行なっているかのように振る舞う．

不幸なことに，世界は理想通りではないため，サーバーは故障したりリカバーしたりする．これがきつい．write-all approach において，どっかのサーバーが故障してても，x の全てのコピーを書かなきゃいけない．いくつかの x のコピーが落ちていることも考えられるし，Write(x) を受け取った時点で，常に必ず全ての x のコピーに対する書き込みが可能ってわけじゃない．この状況下でもしっかり write-all approach を守るなら，全部の x のコピーへの書き込みが可能になるまで，DBS の Write(x) の処理は遅延しなきゃいけない．

そのような遅延は明白に更新 tx がきつくなる．何か一つでも x のコピーが落ちてたら，完全に x に対する write を完了することはできない．コピーが多ければ多いほど，何か一つでもコピーが落ちている可能性は高くなる．レプリカデータが多ければ多いほど，update tx の可用性はゲキ落ち．

このような理由で， write-all approach は残念．