Transaction Management (2)

技術的なこと

CS 4611 Home Pageを見て、勉強してみる。特に、Transaction Management。次は、http://www.d.umn.edu/~rmaclin/cs4611/notes/Ch17_CC.pdf。

  • 衝突の順番が同じスケジュール？
    • 衝突の概念と定義がよくわからない。
  • 依存関係グラフ
    • ノードは、トランザクションを示す。TiからTjへのエッジは、Tjは、Tiの書き込み後に読み書きするということを意味する。
    • conflict serializableであることとグラフが閉路を持たないことは等価。証明が見たいが、どこにあるんだろう。
  • ビューシリアライザビリティ
    • よくわからない。特に、二つ目の条件と例がマッチしていないように見える。
  • ロック管理
    • ロックマネージャにより、ロック、アンロックは管理される
    • ロックテーブルのエントリには、以下の情報を含む
      • 並行してひとつのロックを保持するトランザクションの数
      • 保持しているロックの種類
      • ロックリクエストキューへのポインタ
  • デッドロック回避
    • タイムスタンプベースで、優先順位をつける。すでにTjによって保持されたロックに対して、Tiがロック取得を要求した場合、二つのアプローチがある。
      • TiがTjより高い優先順位の場合、Tjによるロックの開放を待つ。それ以外は、アボート。
      • TiがTjより高い優先順位の場合、Tjをアボートさせる。それいがは待つ。
    • トランザクションを再開するときに、元々のタイムスタンプを持っていることを保証すること。これは、もし変わってしまったら、livelockみたいなことが起こるのかな。
  • デッドロック検知
    • ロック待ちグラフを作成し、閉路ができてないか定期的にチェックする。
    • ノードは、トランザクション。Ti -> Tj のエッジはTiがTjを待っていることを示している。
  • ロック粒度
    • タプル、ページ、テーブル等々のネストしたロック粒度がある。
    • それらのどれを利用するべきか決定するのは難しい。
  • ロックモードとプロトコル
    • ある粒度でのロックを取得する時に、その粒度を含む、全ての粒度でintentionロックを取得する。
    • 解放する際には、小さい粒度から大きい粒度へ。
    • SIXモードは、よくわからない。ロックの排他性をORをとっただけならISと同じになるので、多分また違うのだろう。
  • ロックプロトコル
    • ここで言うノードとは、タプル、ページ、テーブルなどの排他制御対象となるツリー構造を持ったリソースのこと。
    • トランザクションは、粒度ツリーの根からスタートする。
    • あるノードのS、ISロックを取得する場合には、親ノードのIS、IXロックを取得しなければならない。
      • もし、このとき、親ノードでSIXやSをとるとどうなるか。SIXは定義わからない。Sを取得してしまったら、IXが取得できなくなるので、無関係な子ノードの更新を止めてしまうことになる。
    • あるノードのX、IX、SIXロックを取得する場合には、親ノードのIX、SIXロックを取得しなければならない。
    • ロックの解放は、取得の逆の順番で行う。つまり、ボトムアップの順番で解放する。
    • プロトコルは、ツリーの葉に当たるノードを直接排他制御するのと等価という意味で、正しい。
  • 例
    • トランザクションT1は、テーブルRをスキャンして、数行のタプルを更新する場合を考える
      • T1は、Rに対してSIXロックを取得する、次にRのタプルに対してSロックを次々に取得する、時たま、このSロックはXロックに昇格する。
    • T2は、Rの一部分のみを読み込むためにインデックスを利用する。
      • T2は、Rに対して、ISロックを取得し、次々とRのタプルに対するSロックを取得する。あれ？インデックスはどこにいったんだろうか、とりあえず関係ないのかな。
    • T3は、R上の全てのレコードを読み込む
      • T3は、R上のSロックを取得する。もしくは、T2と同じように動作しても良い。
  • 動的なデータベース（というか、普通のデータベース）
    • 読み込んでいる最中に、読み込んでいる対象のデータに関わるレコードの更新がかかる例を考える。
      • T1は、軍曹で最古参の兵士を取得する。この際、「軍曹」で引っ掛けたレコードが属するページ全てをロックする。取得したのは、71才。
      • T2は、軍曹で新たな兵士を登録する。96才。
      • T2は、士官で最古参の兵士(80才)を削除し、コミット。
    • T1は、士官のレコードを含むページを全てロック。士官で最古参は、63才。
    • ということで、T1が正しいと思っていることに関して、一貫性が破られている。
  • 問題
    • T1は、暗に軍曹のレコードを全てロック取れていると仮定している
      • T1実行中に、軍曹へのレコードの追加がないことが、その仮定の成立条件。
      • 新たなメカニズムが必要になる(index lockやpredicate lock)
    • conflict serializabilityは、更新がないときにのみ、serializabilityを保証する。
  • Index locking
    • もし、階級に関するフィールドにインデックスがはられているなら、軍曹を含んでいるインデックスページをロックしなければならない。
      • もし、軍曹がないなら、インデックスまるごとロックしなければならない。
    • もし、インデックスがないなら、ページ・ファイル含めて全てロックしなければならない。追加されたりするのを防ぐため。
  • Predicate locking
    • 述語（なんらかの条件のこと）に対して、ロックを取る。
    • インデックスロックは、述語ロックの特別な場合と考えられる。
      • 最古参の例ではどうか？「階級==軍曹」
    • 一般的に、述語ロックのオーバヘッドは大きい。
  • B+-treeでのロック
    • うまいことリーフノードへのロックはできるか？
      • さっき出てきたリソースへのロックとはちがうからね！
    • 木構造を考えずに、2相ロックを用いて、走査時にロックすることも考えられる。ただ、ルートノードがボトルネックになる。
  • 考察
    • より高いレベルのノードは、単にリーフへの道のりを示しているだけ。
    • 挿入に対しては、ルートノードから、修正されるリーフノードまでのパスをロックしないといけない、もちろん排他ロックで。
    • 上記の考察により、２PLを破っているにも関わらず、シリアライザビリティを保証する効果的なロックプロトコルをデザインできる。
  • シンプルなロックシステム
    • 検索：ルートから検索する。走査する際に、子ノードの共有ロックがとれたら、親ノードのロックを解放する。
    • 追加・削除：ルートから検索する。走査する際に、必要に応じて排他ロックを取る。
      • 子ノードのロックがとれたときに、そのノードが「安全」であれば、先祖のロックを解放する。
    • 安全なノードの定義：更新が起こったとしたときに、その更新がそのノードに閉じることを安全という。
      • 追加：ノードのエントリが埋まっていない場合
      • 削除：ノードのエントリが半分以下の場合
  • 良いロックシステム
    • 検索：前と同じ
    • 追加・削除：検索と同じようにリーフまでの間はロックする。リーフに対しては、排他ロック
    • リールノードのみの変更がかかると賭けている。もし、はずしたとるすると、最初の検索ルートで取得する共有ロックが無駄になる。でも、ひとつ前のアルゴリズムより、経験上よい。
  • さらによいロックシステム
    • 検索：前と同じ
    • 追加・削除：シンプルと同じアルゴリズムを利用する。ただし、排他ロックではなく、IXロックを取得する。リーフがロックされると、IXロックを排他ロックにtop-downでロックしていく。top-downとは、ルートのほうからという意味。ルートから始めることで デッドロックの可能性が小さくなる。
  • ハイブリッドシステム
    • ルートに近いほど、排他ロックの必要性は減らせるようになる。

続く。