Snapshot Isolation のおもちゃ・undo ログ MVCC 版

1ヶ月前に作ってみた「行持ち MVCC」では、 行ごとに並んでいる作業データの残骸を取り除くのにゴミ集めが必要になります。 一方、 同じ MVCC でも表単位での undo ログを利用すると、 ゴミ集めが不要になります。

undo ログ方式もいくつか流儀があり、 ここでは表にダーティー・ライトしていくことにします。 例を書いてみましょう、 次の例では、 左から右へと時間が流れていきます。 一行目がグローバルの表で、 各トランザクションが逐次変更を加えていきます。 変更と同時に、 トランザクションは自身の編集スクリプトを記録します。 編集スクリプトは二重線上に縦棒付き波括弧で書いています。 タプル (a0 等) の前にマイナス記号があると削除、 プラス記号で挿入を表すことにします。 さらに、 グローバルの表と全トランザクションの undo ログを更新します。 波括弧の前にプラス記号が付いているのが undo ログです。 undo ログの表記は編集スクリプトと同じで、 内容は編集スクリプトの逆操作です。 下では、 トランザクションが、 t1 から t5 まで走っています。 トランザクションの開始時点で、 グローバル undo ログをコピーして自身の undo ログにします。 t1 等の直後に波括弧でくくって、 スナップショットの内容を記入しています。 例では、 t1 がタプル a0 を a1 に更新し、 t2 がタプル c0 を削除し、 t1 がタプル b1 を挿入します。 その後で、 t2 をコミットし、 t4 を開始してから、 t1 をコミットしています。 コミット時に、 グローバル undo ログから編集内容を除去して、 グローバルの表の変更内容を確定します。

 {a0,c0}       {a1,c0}   {a1}           {a1,b1}            {a1,b1}         {a1,b1}
 +{}           +{-a1+a0} +{-a1+a0,+c0}  +{-a1+a0,-b1,+c0}  +{-a1+a0,-b1}   +{}
 --------------|---------|--------------|------------------|---------------|----------------------
  t1{a0,c0}====|{-a0+a1}=|{-a0+a1}======|{-a0+a1,+b1}=====================>
    +{}        +{}       +{+c0}         +{+c0}

   t2{a0,c0}===|{}=======|{-c0}=========|{-c0}============>
     +{}       +{-a1+a0} +{-a1+a0}      +{-a1+a0,-b1}

    t3{a0,c0}==|{}=======|{}============|{}==============================================>
      +{}      +{-a1+a0} +{-a1+a0,+c0}  +{-a1+a0,-b1,+c0}

                                                               t4{a1,b1}===|{}==============>
                                                                 +{-a1+a0,-b1}

                                                                             t5{a1,b1}==|{}======>
                                                                               +{}

上の例のやりかたで Snapshot Isolation になっているのですが、 トランザクション t2 が削除したタプル c0 を、 t1 と t3 が削除後も undo ログで復元するため、 グローバルの表に復元タプルをマージする必要が生じてしまいます。 もしも表にタプルを昇順に並べているときは、 順番を崩さないようにマージしなければならず、 削除されたタプルが多いときは undo ログも昇順に並べる工夫が必要になります。 そこで、 表からの削除をタプルが不要になるまで遅延させるように、 上の例を修正します。

今度は、 トランザクション t2 で表からタプル c0 を削除せずに、 削除予約の印を undo ログにつけます。 アスタリスクを前につけて削除する予定のタプルであることを表します。 t2 をコミットすると、 グローバルの undo ログの削除予約の印を削除に変えます。 この時点ではグローバルの表からは削除しません。 タプルを削除するのは、 削除予約の印がなくなったときで、 その時点でグローバル表から削除し、 undo ログの削除コマンドを取り除きます。 下の例では、 他のトランザクションの undo ログから削除コマンドを同時に取り除いていますが、 残しておいても問題はありません。

 {a0,c0}       {a1,c0}   {a1,c0}        {a1,b1,c0}         {a1,b1,c0}        {a1,b1,c0}    {a1,b1}
 +{}           +{-a1+a0} +{-a1+a0,*c0}  +{-a1+a0,-b1,*c0}  +{-a1+a0,-b1,-c0} +{-c0}        +{}
 --------------|---------|--------------|------------------|-----------------|--------------|-----
  t1{a0,c0}====|{-a0+a1}=|{-a0+a1}======|{-a0+a1,+b1}======|{-a0+a1,+b1}====>
    +{}        +{}       +{*c0}         +{*c0}             +{*c0}

   t2{a0,c0}===|{}=======|{-c0}=========|{-c0}============>
     +{}       +{-a1+a0} +{-a1+a0,-c0}  +{-a1+a0,-b1,-c0}

    t3{a0,c0}==|{}=======|{}============|{}================|{}=============================>
      +{}      +{-a1+a0} +{-a1+a0,*c0}  +{-a1+a0,-b1,*c0}  +{-a1+a0,-b1,*c0}

                                                               t4{a1,b1,c0}==|{}============|{}=>
                                                                 +{-a1+a0,-b1,-c0}       +{-a1+a0,-b1}

                                                                               t5{a1,b1,c0}=|{}==>
                                                                                 +{-c0}    +{}

後者の場合、 グローバル表とグローバル undo ログを使い、 削除予約を削除済みとみなすか、 削除コマンドを反映させるかで、 隔離レベルを緩めることができます。

隔離レベルを緩めるとしても、 ダーティー・リードを使うことはないため、 タプル変更をコミット時にグローバル表におこなうようにしましょう。 ただし、 タプル挿入は、 undo ログからの復元時のマージを避けるためにグローバル表に挿入することにします。 さらに、 タプル削除時の削除予約マークを undo ログに付けるのも、 コミット時点でおこなうようにします。

 {a0,c0}       {a0,c0}   {a0,c0}        {a0,b1,c0}         {a0,b1,c0}        {a1,b1,c0}         {a1,b1}
 +{}           +{}       +{}            +{-b1}             +{-b1,-c0}        +{-c0}             +{}
 --------------|---------|--------------|------------------|-----------------|------------------|-----------
  t1{a0,c0}====|{-a0+a1}=|{-a0+a1}======|{-a0+a1,+b1}======|{-a0+a1,+b1}====>
    +{}        +{-a0+a1} +{-a0+a1}      +{-a0+a1}          +{-a0+a1,*c0}

   t2{a0,c0}===|{}=======|{-c0}=========|{-c0}============>
    +{}        +{}       +{-c0}         +{-b1,-c0}

    t3{a0,c0}==|{}=======|{}============|{}================|{}===============|{}===============>
     +{}       +{}       +{}            +{-b1}             +{-b1,*c0}        +{-a1+a0,-b1,*c0}

                                                               t4{a0,b1,c0}==|{}================|{}====>
                                                                 +{-b1,-c0}  +{-a1+a0,-b1,-c0}  +{-a1+a0,-b1}

                                                                                 t5{a1,b1,c0}===|{}========>
                                                                                   +{-c0}       +{}

ところで、 上のどれでも undo ログは楽観的排他制御版の一種の書き込みレコード・ロックの働きをしています。 なので、 ここにタプル読み出しも追加してやることで、 たぶんですが、 Serializable Snapshot Isolation のきわどい組み合わせ検出をおこなうことができるのではと考えたりしています。