Zenn
🫥

[メモ] B-Tree の Latch と Lock と Logging について

2024/02/18に公開
Database
logging
dbms
btree
tech

B-Tree の Latch と Lock と Logging について、以下の主に [1] と [2] の資料を読んだ際のメモです。

  • [1] A Survey of B-Tree Locking Techniques
  • [2] A Survey of B-Tree Logging and Recovery Techniques
  • [3] Hierachical locking in B-Tree indexes
  • [4] Efficient Locking Techniques for Databases on Modern Hardware
  • [5] Modern B-Tree Techniques

論文に書いてあることと筆者の感想や解釈が入り混じっているのでここにあるすべてのことが論文に書かれているわけではないことに注意してください。

[1] A Survey of B-Tree Locking Techniques

色々

  • Latch と Lock の違いは略。
  • Key range locking は Predicate locking の一種である。Key range locking は、B-Tree の Key と Sort-Order を用いる。
  • Lock table の Key には、Non-Redundant Storage (Clustered Index や HeapFile) の Key (ValueID) が使われる。Redundant Storage (Unclustered Index) の Key は使われない。
  • B-Tree のリカバリ時（ログの Redo と Undo 時）には、並行して新たなトランザクションを許容しない限り、Lock を取る必要はない。Latch は取る必要がある。なぜなら、ログを書くことができたことは、トランザクション同士の　Lock Conflict がないことを意味しているからである。
  • ARIES では Undo 時に新たなトランザクションを受けつけることができる。その場合、Undo 開始前にトランザクションの全ての Lock を取る必要がある。Log Analysis 時に Lock をとってしまえば、 Redo 時に新たなトランザクションを受け付けることができるようになる。これを Early New Transaction と呼ぶ。Checkpoint 時に、ログレコードに各トランザクションがどの Lock を保持しているか書き込むことでこれは簡単に実装できる。
  • あるページに対して 2 つのトランザクションが変更を加えたログが残っていた場合、ログの Redo は同一ページに対する変更は（LSN によって）直列化されて実行されるため、リカバリ前と論理的に異なる結果になることはない。
  • データベース（B-Tree) の内容を論理的に変更しないが、物理的な構造へ変更を加えるトランザクションを System Transaction と呼ぶ。System Transaction の例として、B-Tree ページの Split, Compaction, Ghost Record の Delete/Insert などが挙げられる。通常のトランザクションは、これに対して User Transaction と呼ぶ。User Transaction は必要に応じて System Transaction を呼び出す。
  • リカバリ時に、終了していないトランザクションは、通常であれば Rollback するが、System Transaction に限っては、論理的にデータベースの内容を変更しないため、最後まで実行しても良い。最後まで実行することを Forward Recovery と呼ぶ。System Transaction の Delete 操作（Ghost Record の削除や、論理的には削除された Index の物理削除）は、基本的に Forward Recovery した方が良さそうである。

B-Tree の物理的な構造を並行アクセスからどう守るか (Latch)

  • B-Tree の並行性を正しく実装するには 次の 4 つの問題への対処法を考える必要がある。
    1. あるトランザクションが B-Tree のあるページに変更を加えている間に、他のトランザクションがそのページに変更を加えたり、読んだりする問題。
    2. あるトランザクションが B-Tree の親ページから子ページに辿る瞬間に、他のトランザクションが子ページを（ページの Split や Deallocation によって）破壊してしまうかもしれない問題。
    3. あるトランザクションが B-Tree の Scan 時などに、葉ページから葉ページへポインタを使ってたどっている場合、他のトランザクションがポインタの参照先を破壊してしまうかもしれない問題。さらに、Forward Scan と Backward Scan の二つの Latch が噛み合って Dead-lock が起きてしまう問題。
    4. 葉ノードの Split が親ノードの Split を誘起し、さらにそれが根の Split を引き起こす可能性がある。また葉から根の方向で Latch を取ってしまい、通常の根から葉への Travarse と噛み合うことで Dead-lock が起きてしまうかもしれない問題。
  • 1.の問題は、ページに Latch を設けることで解決するが、Reader-Writer Mutex を使う場合、どのように　Starvation を回避するか考える必要がある。
  • 2.の問題は、Lock(Latch) Coupling によって回避することができる。Lock(Latch) Coupling とは親ノードの Latch を先に取り、その後子ノードにアクセスし、子ノードの Latch を取得後、親ノードの Latch を外すことである。あるノードの Latch を取ることは、そのノードを根とする部分木への変更を防ぐことを意味するため、親ノードの Latch を取った状態で安全に子ノードにアクセスすることができる。子ページが Buffer Pool に存在しないときに、子ページをメモリに読み出す待ち時間の間、親ページの Latch を持っていることは防ぎたいため、親ページの Latch を外して、ReTraverse する。ページの Page LSN をバージョンとして用いれば、親ノードに変更が加わったかどうかを判別することができるため、Travarse を短縮することができる。これはほぼ Optimistic Latch Coupling と同じことを行なっている。Page LSN を Optimistic 実装時に必要な Version と同一しているのが興味深い。
  • 3.の問題のポインタ参照先が壊れているかもしれない問題は、（言及されていないが）葉ページの Split や Delete をするときに左右の葉ページの Latch を取ることで解決できる。Dead lock の問題は、No-Wait を採用することで解決する。
  • 4.の Split 誘起問題は、B-Tree への Insert 時に、根から葉にかけて Exclusive Latch を取ることで解決できるが、これは明らかに並行性に悪影響を与える。例えば、根から葉にかけて Exclusive Latch で辿っていき、確実に Split しないノードをを見つけた時点でそのノードより上流にある全ての Exclusive Latch を解放すると言う方法などが考えられる。
  • Split 誘起問題に対する全く異なる解決法として B-link Tree がある。B-link Tree ではあるノードの Split を、次の三つのステップに分解する。
    1. 新たなノードを Allocate して Split 対象のノードにあるキーの半分を、新たなノードに移す。本来なら次に、新たなノードと Split 対象のノードの親ノードをつなぐが、B-link Tree では親ノードへ Split を伝搬させたくないので、代わりに Split 対象のノードから新たなノードへのポインタを貼る。これにより、新たなノードは親ノードから直接は辿れないが、Split 対象のノードを経由して辿ることができる。
    2. 親ノードに Split Key を置いて、新たなノードを親ノードと繋ぐ。親ノードは Split する可能性があるが、 Split が必要になった場合は 1. と同じように解決する。
    3. Split 対象のノードから新たなノードへのポインタを消す。
  • 各ステップ終了後、B-link Tree は一貫した状態（辿れないページや Key が存在しない状態）を保っているのが特徴である。これは各ステップを System Transaction として実装できることを意味する。System Transaction は物理的な変更を加えることはあっても論理的な変更を加えることはないので、Latch は必要とするが Lock は必要としない。

B-Tree の論理的な内容を並行アクセスからどう守るか (Lock)

  • Lock Deescalation (Lock の Downgrade) とリカバリ時に Lock を再確保するときは、Lock Conflict の確認はいらない。
  • Key Range Locking は Predicate Locking の一種であり、B-Tree の Sort Order 上のインターバルが Predicate である。インターバルの境界（左端と右端）は、B-Tree に存在している Key である。
  • Key Range Locking では、 ある Key に対して 2 つの（重なり合わない） Lock を取ることができる。その Key 自体の Lock と、その Key から Sort Order で次の Key までの区間 (Gap) の Lock である。B-Tree へ実行する操作によって、どちらの Lock を取るのか、またそれらの Lock Mode についても考慮する必要がある。例えば、Key を Deletion するときは、Delete 対象の Key とその Previous-Key の Gap の 2 つの Lock を取る必要がある。なぜなら、Delete が Rollback した際に Previous-Key から Next-Key までの Gap への挿入を可能としなければならないからである。逆に言うと、この Gap を Lock しておくことで、トランザクションが　Commit するまでに、他のトランザクションがその Gap へ挿入をするのを防ぐことができる。
  • 実際には、Deletion は B-Tree 内の物理レコードを消去せず、ページスロットの Ghost-bit を立てることで論理削除した方が実装が楽になる。Ghost-bit が立っているレコードを Ghost Record と呼ぶ。論理削除された Key (Ghost Record の Key) は、その物理レコードが存在している限り、Lock Table の Key となりうる。Key の Deletion は、まず Key を論理削除した後、非同期に物理削除する。物理削除時には、他のトランザクションはその Key に対して Lock を保持していてはいけない。他のトランザクションが論理削除された Key の Lock を保持する、と言うのはそのトランザクションが Ghost Record と同一の Key を Insert しようとしていることを意味する。本文では、物理削除を行うトランザクションは、データベースの論理的な内容を変更しないため、対象の　Key への Lock を取る必要はないと書かれている。しかし並行した　Insert から Key を守るためには何かしらの排他をする必要があると考えられる。
  • Ghost Record を導入する利点はいくつかある。まず、論理削除の実装が楽になることである。論理削除は、Ghost bit を立てるだけなのでただの Update と同一視できる。トランザクションのロールバックも簡単に行える。なぜなら、Update として実装されているので Previous-Key の Gap Lock を取る必要もないし、再度スペースの Allocation をしなくて良いからである。次に、削除を論理削除と物理削除の二つのステップに分割することで、ログに Before-Image を書く必要がなくなる。通常、削除を Undo するために、削除前のレコードををログに含める必要があるが、論理削除のログは、単なる Bit の Update なので、削除前のレコードを必要とせず、論理削除 Commit 後に非同期で行われる物理削除は、データベースの論理的な内容を改変しない操作のため、Undo の必要がない (Forward Recovery)。結果的に、論理削除、物理削除ともにログに削除前のレコードを書く必要がなくなる。
  • Ghost Record は、B-Tree へ Key を物理 Insert をする時にも使える。ここでは物理 Insert する Key は、必ずしも Ghost Record ではないことに注意する。物理 Insert 時には、Previous-Key の　Gap Lock を取る必要があるが、B-Tree の葉ページに辿ったときに Insert 対象の Key の Previous-Key が丁度一つ隣の葉ページにある場合、隣の葉ページへ辿って　Previous-Key を取得する必要がある。しかし、Dead-lock の問題があるので、元々いた葉ページの　Latch を解除して、隣の葉ページの Latch を取る必要がある。Ghost Record を用いれば、隣の葉ページを辿って Previous-Key を取得しにいく必要がなくなる。葉ページに、親ページの Separator Key を Ghost Record 挿入しておく。つまり、Previous-Key が葉ページに必ず存在する状態にする。そうすると隣の葉ページに遷移する必要がなくなり、Dead-lock などの煩わしい問題を考える必要がなくなる。
  • Ghost Record の物理 Insert や物理 Delete は論理的にデータベースの内容を変更しないため、　Lock を取らずに実行することができる。これは、通常の物理 Insert であれば、あるトランザクションが適切な Gap Lock を取って B-Tree をスキャンしている間には、その Lock のレンジに Insert することは　（Repeatable Read ができなくなると言う点で）御法度とされていたが、Ghost Record の物理　Insert であれば可能であることを意味する。物理削除でも同様である。しかし、Lock Table の Key と B-Tree に存在する物理レコードの Key は同期されていると考えるため、B-Tree に Ghost Record を挿入すると、 Lock Table でそれまで Lock していた　Gap の範囲が変わる。例えば、[10, 20) というレンジを Lock しているトランザクションがあったときに、B-Tree に 15 の Key を持つ Ghost Record を挿入すると Gap Lock のレンジが [10, 15) に変わってしまう。そのため、15 の Ghost Record を物理 Insert するトランザクションは、[15, 20) の Gap Lock を [10, 15) の Gap Lock を持つトランザクションに渡さなければならない。物理削除でも同様に、[3, 7) と [7, 12) の 2 つの Gap Lock があるとき、7 の Ghost Record を物理削除したトランザクションは、この二つの Gap Lock をマージしなければならない。このとき、[3, 7) と [7, 12) に Lock の Conflict があってはならない。Lock の Conflict などを考えずに実装するには、[7, 12) への Lock が全て解除されるのを待てば良い。これはつまり、Ghost Record の物理削除には、Key とその Gap の Exclusive Lock を取ることを意味する。
  • 以上をまとめると、Ghost Record の物理 Insert や物理 Delete は Lock を取らずに実行できると言う優れた点があるが、Range Lock の Split や Merge を正しく実装するのはやや難しそうに感じる。
  • Insert を Ghost Record の物理 Insert と Ghost bit を flip するだけの論理 Insert に分けることで、トランザクションの並行性を上げることができる。なぜなら、Ghost Record の物理 Insert には Lock はいらず、論理 Insert は実質 Update と同じ操作なので、Insert 対象の Key のみの　Lock を取れば良く、Gap Lock が不必要になるからである。
  • Delete も同様である。Delete を Ghost bit を flip するだけの論理 Delete と、物理 Delete に分けることで、論理 Delete 時には、対象の Key のみを Lock すれば良く、ロールバックを考慮して Gap を Lock する必要はない。物理 Delete には、例外はあるが基本的に Lock を必要としないと言える。
  • 最初に言ったように、Key Range Locking では、Key 自体の Lock とその Key から次の Key までの開区間 ((Key, NextKey)) を Lock することができる。また、これらを組み合わせた半開区間 ([Key, NextKey)) の Lock を必要とすることもある。[Key, NextKey) は [Key]　と (Key, NextKey)　を含み、ここには階層構造があり、Intention Lock を使うことができる。
  • Intention Lock とは、データベース、テーブル、タプルなどといった階層構造のあるオブジェクトへのアクセスを排他するときに用いられる Lock である。ある階層の S Lock を取るには、それより上のすべての階層で IS Lock を取る必要があり、X Lock も同様に IX Lock を上階で取る必要がある。Intention Lock を導入するメリットは、Lock Conflict を簡単に判定できることである。Intention Lock が存在しない世界では、テーブル全体をスキャンしたいとき、テーブルないのタプルに書き込みをしているトランザクションが存在しているかどうかを各タプルの Lock の状態を確認する必要がある。Intention Lock を用いれば、すべてのタプルの Lock を見る必要がなくなる。テーブルスキャンをするときは、テーブル全体を読みたいので S Lock をとる。もし、テーブルのタプルに書き込みをしているトランザクションが同時に走っている場合、テーブルに　IX Lock, タプルに X Lock が取られているはずである。S Lock と IX Lock は Conflict するため、テーブルスキャンはすべての IX Lock が解放されるのを待つ必要がある。このようにして、Intention Lock は階層構造の Lock Conflict 判定を簡略化する。
  • Key Range Locking では、半開区間 [Key, NextKey) が [Key] と (Key, NextKey) を含み、階層構造がある。先ほどの議論をこれに当てはめると、[Key] を S Lock するために [Key, NextKey) をまず IS Lock とることが考えられる。
  • Intention Lock を導入すると、まず半開区間の Lock をとり、その後 [Key] か (Key, NextKey) の Lock を取ることになり、Lock Manager へ 2 回 Lock の問い合わせを行う必要がある。この問い合わせの回数は、Lock のモードを増やすことで解消することができる。つまり Lock のモードの個数と Lock Manager への問い合わせの回数はトレードオフの関係にある。
  • Lock は [Key] と (Key, NextKey) の 2 つのオブジェクトに対して、それぞれ Lock を取らない（ N と表現される）、S Lock を取る、X Lock を取るの 3 つの可能性があるので、Lock モードの総数は、9 個（NN, NS, NX, SN, SS, SX, XN, XS, XX）である。どちらの Lock も取らない場合（NN）を除くと 8 個である。また簡単のため、SS　は S とし、XX は X とする。例えば、NS は開区間に対してのみ S Lock を取るモードで、このモードは Intention Lock での、半開区間で IS, 開区間で S を暗に意味している。S は Key と開区間両方の S Lock を取る操作で、これは Intention Lock での半開区間で S Lock を取っていることに等しい。ある Key に対して、8 つの Lock モードを用意することで、Lock Manager への 1 度の呼び出しで Lock の取得が完了することになる。
  • Unclustered Index の場合の Key Range Lock は少し状況が異なる。Unclustered Index では、一つの Key が複数の ValueID （Clustered Index の Key ）に対応する。Lock の取り方は大きく 2 つあり、Key を Lock することで同じ Key に属する ValueID のクラスタをすべて Lock する方法や、<Key, ValueID> のペアで Lock することでより小さい粒度で　Lock することもできる。ValueID のクラスタに対して Intention Lock の考え方を導入し、クラスタを IS Lock で守り、特定の ValueID に対して S Lock を取ることができる。同様に、Intention Lock ではなく、先ほどの 8 つの Lock Mode を駆使することができる。これはつまり、Unclustered Index においてKey Range Locking を使える階層が 2 つあることを意味している。例えば、 {Shoes: {1, 2, 3, 4}}, {Toys: {1, 3}} があるとき、[Shoes, Toys) と、[<Shoes, 1>, <Shoes, 4>) の 2 つの半開区間に先ほどの Key Range Locking の考え方を導入できる。Insert や Select などそれぞれの操作に合った Lock を取る必要があると本文に書かれているが、具体的にどのように実装するべきかの記述はない。
  • Clustered Index と Unclustered Index 両方操作するトランザクションが複数あるとき、これらの排他は、それぞれの Index が持つ Lock Table を介して行われるはず。
  • Increment Lock という名前の Lock も存在する。これは、その Lock を保持しているトランザクションがオブジェクトを Increment/Decrement することを許可する。Increment Lock 同士は Conflict せず、Shared Lock と Exclusive Lock は Increment Lock と Conflict する。注意しなければならないのは、Increment Lock は必ずしも Shared Lock を意味しないことである。一つのトランザクションが Increment Lock と Shared Lock を同時に取ることは、Lock Compatibility Matrix から、Exclusive Lock を取ることに等しい。Increment Lock は 2 つのトランザクションがあるオブジェクトの値を同時に Increment したとき、その適用順序に関わらず結果が最終的に同じであるため成立する。そのため、より一般的に、 Increment Lock は CRDT 的なオブジェクトを守るのに用いることができる。Increment Lock の使い所としては、Sum や Count を含む Materialized View があげられる。Increment Lock によって Materailized View のメンテナンス時に Exclusive Lock を取る必要がなくなり、並行性を高めることができる。Incremental View Maintenance を行う際、Materailized View の各レコードはカウンタを必ず持つため、そのカウンタの Increment/Decrement は Increment Lock を用いて行うことができる。このカウンタは Ghost Record の Ghost bit を一般化したものであると言える。カウントが 0 なら、そのレコードは論理的には存在していないことになる。これは Increment Lock で論理 Delete と論理 Insert ができることを意味している。先ほど見たように物理 Delete や Insert 時は、Lock は必要なく、Latch で十分である。
  • Increment Lock は Scan と Insert に用いられると、これまでの Lock にはない面白い挙動を示す。あるトランザクションが Gap の Increment Lock を保持しているとき、その Gap に存在するタプルの Increment が可能である。Ghost Record がその Gap に Insert されたとする。（Ghost Record の Insert は Lock を必要としない。） そのとき、Gap の Increment Lock を保持しているトランザクションは、Ghost Record の Ghost bit を Increment して、Ghost Record を存在するレコードに変えることができる。この挙動が具体的に何に使えるかは書かれていないが、面白くはある。
  • Increment Lock を導入すると、Key Range Lock の Lock Compatibility Matrix が 16 * 16 のサイズになり、とても大きい。この場合、Lock の Compatibility Matrix をプログラムの Static なメモリに保持しておき、適宜参照して Lock の互換性を検証すると実装が少し楽になる。

[2] A Survey of B-Tree Logging and Recovery Techniques

色々

  • データベースの障害は次の 3 つに分類される。トランザクション障害、メディア障害、システム障害。トランザクション障害は、あるトランザクションが何らかの理由によって Abort される障害。そのトランザクションの実行は Rollback する必要があるが、それ以外のトランザクションは通常通り実行する。メディア障害は、何らかの理由によってディスクが機能しなくなる障害。この場合、バックアップのメディアからディスクのデータを復元して、データベースをリカバリする必要がある。システム障害は、プログラミングのバグや OS のクラッシュなどにより生じる障害。この場合、Commit したトランザクションの変更をすべて復元し、クラッシュ時に進行途中だったトランザクションを Abort させる。
  • チェックポイントをすることで、読むべきリカバリログを減らすことができる。そのためには最新のチェックポイントログレコードがどこに書かれているのか（ログレコードの LSN) を別途記録する必要がある。
  • データベースの論理的な概念 (table, row, columns, primary keys, foreign keys) を表す言葉と物理的な概念 (index, record, field, sort order, partition) を表す言葉を分けて使う。
  • B-Tree への変更は次の 2 種類に分類される。論理的な内容を改変するものと論理的な内容を変更せず物理的な表現のみを変更するものである。論理的な内容を改変する操作は　User Transaction として実装され、物理的な構造のみ変更する操作は System Transaction として実装される。
  • ログを Redo するとき、 Aborted なトランザクションは Redo する必要がない。
  • クラッシュ時に実行途中で、Commit していないトランザクションは、Abort される。Abort するためには、適切に Rollback する必要がある。Rollback の記録も Compensation Log Record (CLR) としてログに記録する。Compensation Log Record は Redo することはあっても Undo することはない。これによりリカバリ時に再度クラッシュしても Rollback をさらに Rollback されるのを防ぐ。Undo する必要がないので CLR には Before-Image を書く必要はない。
  • Write-Ahead Logging (WAL) とは Dirty なページをディスクに flush する前に、そのページを Dirty たらしめた操作のログをディスクに flush すると言うこと。
  • WAL Buffer は、ただの配列ではなく、いくつかの Page でできており、LSN はただの Incremental Counter ではなく、PageID + SlotID である。
  • チェックポイントは、リカバリを高速に行うために必要である。チェックポイントログレコードには、その時実行中のトランザクションと Dirty なページを書き込む。
  • Redo と Undo が終わったら、チェックポイントログレコードを書く。リカバリと並行して新たなトランザクション受け付けず、さらにリカバリ中に生じた Dirty なページも flush してしまえば、Undo 終了時に書くチェックポイントログレコードは実質無である。これをやることで、一度行ったリカバリをもう一度行う必要がなくなる。

トランザクションの種類

  • [1] でも出てきたが、もう一度繰り返しておくと、データベースの論理的な内容を変更する操作は User Transaction と呼ばれており、論理的な内容を変更せず、物理的な表現のみを変更する操作を System Transaction と呼ぶ。この分類は、ロギングにも関わってくる。
  • トランザクションの Undo は、データベースの論理的な内容が一致しているのなら、内部でそれをどのように実装してもユーザへの影響を与えない。例えば、レコードの Insert を　Rollback するのに、そのレコードを物理的に削除してもいいし、Delete flag を立てて論理削除しても、どちらでもユーザにはそのレコードの存在が見えないので構わない。
  • System Transaction は論理的な内容を変更せず、データの物理的な並べ方や構造を変更する操作のことをいう。あるページを Split/Merge したり、Ghost Record を挿入/削除したりする操作がこれに該当する。User Transaction は System Transaction を呼び出すことがある。例えば、レコードを Insert するとき、まず System Transaction を呼び出し Ghost Record を挿入する。System Transaction が Commit したら、Ghost bit を flip して論理挿入を終了する。この場合、System Transaction は User Transaction による同期的な関数呼び出しとして実装され、User Transaction が保持している Latch をそのまま継承することができる。[1] でも述べられているように System Transaction は基本的に Lock を保持する必要はない。しかし、論理削除された Key を物理削除する System Transaction は、他のトランザクションがその Key の Lock を保持していないか確認する必要がある。
  • System Transaction は、その変更をログに書く必要がある。そして、実行中に障害が発生した場合には、リカバリ時に元に戻さなければならない。しかしながら、System Transaction は User Transaction と異なり、Commit 時に WAL Buffer を flush する必要がない。なぜなら、System Transaction はデータベースに論理的な変更を加えないため、ユーザは System Transaction が Commit したか否かに関わらず、正しいクエリの結果を得るからである。例えば、ある B-Tree のあるページが Split した状態でも、Split していない状態でもその B-Tree に対するクエリは、論理的な内容が同じなら同じ結果が返ってくるはずである。しかしながら、先ほどの User Transaction が Insert 時に System Transaction を呼び出す例では、User Transaction の Commit は System Transaction の成功に依存している。だが、この場合、System Transaction のログレコードは User Transaction の Commit ログレコードより前に書かれているため、User Transaction が Commit するときに自動的に System Transaction のログも flush される。そのため、System Transaction は相変わらず、その Commit 時にログを flush する必要はない。
  • System Transaction はなぜ "Transaction" と呼ばれるだろうか？答えは、System Transaction を呼び出した User Transaction と独立して Commit することができるからである。もし、System Transaction が User Transaction によるただの操作の一つとしてログに記録されると次のような問題が生じる。例えば、2 つの User Transaction (A, B) が走っていて、A が先ほどの Insert の例のように Ghost Record の挿入を呼び出したとする。A はこの Ghost Record の存在に依存していることは明白だが、同時に走っている B もその Ghost Record の存在に依存しているとする。この場合、Ghost Record の挿入を呼び出した A が Abort しても、Ghost Record の挿入自体を Undo することは防ぐ必要がある。なぜなら、B は Ghost Record の存在に依存しているからである。このために、Ghost Record の挿入を別のトランザクションとして切り分けて、Commit させることで Rollback できないようにする必要がある。
  • Abort された User Transaction は Abort のログをバッファに書くが、 flush する必要がないという意味で、System Transaction に似ている。
  • System Transaction が System Transaction を呼び出すことがある。これはページの Split が親ページの Split を誘起した時などに見られる。
  • トランザクションが User Transaction と System Transaction を用いてどのように実装されるべきなのかを軽くまとめる。
    • Read: User Transaction で普通に読む。
    • Update: User Transaction で普通に Update する。
    • Insert: System Transaction で Ghost Record を物理 Insert する。そして User Transaction で Ghost Record の bit を flip して論理 Insert を完了する。bit flip は実質 Update の操作と等しい。
    • Delete: User Transaction で Ghost Record の bit を flip する。そして Commit 後、非同期に System Transaction で Ghost Record の物理 Delete をする。
  • 論理的な操作と物理的な操作を User Transaction と System Transaction にわけて別々に行うのは、レコードに対してだけではない。いわゆる Utility Transaction と呼ばれるトランザクションも論理的な操作と物理的な操作にわけて実行することができる。Utility Transaction とは、例えば Index の作成、削除、バックアップの作成、リカバリ、データの圧縮、ファイルの Defragmentation、Incremental View Maintenance などである。Index の削除の例では、論理的な削除はカタログに削除タグを付けることで達成可能である。後続の System Transaction が Index が確保していたディスクスペースを物理的に削除する。
  • Index を構築するときに、Index へ挿入するすべての Key のログを書き込むと、ログのサイズが大きくなってしまう。ログのサイズを緩和するために、Key 単位ではなくページ単位で変更を書き込むことも考えられる。これによってログヘッダ分の節約ができる。しかし一番良いのは、Index の中身に関するログを一切書かないことである。これは "minimal logging" または "allocation logging" と呼ばれる。これは必要なときに Rollback が正しくできるようにログを書くだけで、Index 構築途中の特定の時刻の状態への復元はサポートしないログの書き方である。つまり、Rollback 時にどのページを削除すれば良いかわかるようにページの Allocation 情報だけをログに書き、Index の中身を一切ログに残さないことで、ログのサイズを劇的に小さくすることができる。トランザクションが Commit した場合は今後一切このログを Redo する必要はないし、Abort した場合は Allocation 情報を用いて Insert をすべて巻き戻せば良い。この場合、Buffer Pool は Force である必要がある。つまり、トランザクションが Commit するときに Dirty なページを flush する必要がある。また、Index の構築時に並行して別のトランザクションが Index にアクセスするのを禁止する必要がある。"minimal logging" は空の Index への Bulk Insert だけでなくすでに存在している Heap-File に対して新たなページをバッチで追記するときにも使える。これは SQL-Server で実装されている。[参考]
  • チェックポイントログレコードを書く際は、一貫したチェックポイントを書くために、アクティブなトランザクションのリストや Dirty Page のリストなどのインメモリの構造を適切に Latch する必要がある。
  • System Transaction に関して少しまとめる。User Transaction によって同期的に呼び出された System Transaction は、User Transaction の Latch を引き継ぐことができる。System Transaction は User Transaction と同じようにログを書く。しかし System Transaction は Commit 時にログを flush しなくても良いと言う性質を持つ。

Logging のテクニック

  • 大きくわけて 3 つのログを書く方法がある。Physical Logging と Logical Logging、そして Physiological Logging である。Physical Loggging はどのページにどんな物理的な変更が加えられたのかをログに記録する。例えば、"page_id X の Y byte から Z byte までが hogehoge に変更された" などである。Logical Logging は実行された論理的な操作が記録される。例えば、"B-Tree X に Key Y が挿入された" などである。Physiological Logging はこれらの中間である。Physiological Logging は "physical to a page, logical within a page" と説明されている。ログには、どの物理ページにどのような論理的な変更が加えられたのかを記録する。Physiological Logging の例は "page_id X に Key Y が挿入された" である。Physical Logging は、byte offset をログに含む必要があり、各ログのサイズが大きくなる傾向がある。Logical Logging は論理的な操作だけを記録するのでログを小さく保つことができるが、ログを復元するのが難しいらしい（具体的になぜかは説明されていない）。こちら によると、並行実行された 2 つのロジカルな操作が、ログ上では直列化され、リカバリ時に直列に実行するとクラッシュ前とは異なる結果になってしまう可能性があるらしいが、これは本当に起きうることなのかやや疑問である。と言うのも、ロジカルな操作のログを書く前に必要な Latch を全て取得していれば上のスライドで説明されている問題は起きなさそうだからである。Physiological Logging では、ページ内の論理的な操作のみをログに書くので、Page Compaction や Page の中での Key の移動はログに書かなくても良い。Compaction のログを書く必要はない代わりに、クラッシュ前と同じ挙動をするために、Insert 時にスペースが足りなかった場合必ず Compaction を走らせる必要がある。

  • Delete 時に物理 Deletion をするのではなく、Ghost Record を導入して論理 Delete をする User Transaction と物理 Delete をする System Transaction の 2 つの操作に分けることができる。Deletion 時に Ghost Record を導入するメリットは 3 つある。1.Deletion の並列性を高めることができる。通常 Key の Deletion をする際には、Rollback のことを考えて、Key そのものだけでなく Key が含まれている Gap の Lock も取得する必要があるが、Ghost Record を導入すると Rollback 時には Bit の flip を行えばいいだけなのでこの Gap の Lock が必要なくなる。2.Rollback の実装が楽になる。Key の Deletion はスペースを Deallocate しないので、Rollback 時に再度スペースの Allocation をしなくて済む。3.ログに書く量が減る。User Transaction による Delete はただの Bit の flip なので実質 Update と同じである。また、System Transaction による　Delete 時には、誰もその Key に対応する Record に依存していないので、ログに　Record を書く必要がない。

  • 整理すると、あるページの (Key, Record) には次の 4 つの状態があると言える。1.Key も Record も Visible である状態。2. Key のみ Visible である　(Ghost Record) 状態。3. Key も Record も Visible ではない状態。4. Key も　Record も物理的に存在していない状態。「Visible ではない」は「存在しない」と一致しないことに注意する必要がある。Delete 時に、まず User Transaction は、1 から 2 へと (Key, Record) の状態を変える。System Transaction は 2 から 4 へと Key の状態を変える。3 から 4 の操作は Page Compaction と呼ばれる。1 から 2　への遷移では、Ghost bit の変更をログに書く。2 から 3 への遷移では、Key をログに書く。3 から 4 への遷移はログに何も書かない。

  • ここで残る疑問としては、User Transaction Commit 後、 System Transaction 実行前のでクラッシュしたとしてどのように 2 から 4 まで実行するか、であるが、User Transaction のログの中に、「この User Transaction が Commit したらその Ghost Record を回収するための System Transaction を実行する」というようなログを残しておく必要がありそう。「　Centralized Ghost Record Collector みたいな構造に、User Transaction ID と Ghost Record の Key を入れておく」っていう操作をログに書いておけば、その User Transaction が Committed なら消す 2->4 までやると言うことができる。まあ最悪 Ghost Record は消さなくても良さそう。

  • B-Tree の Page の Latch と Key の Lock の関係をおさらいする。まず、Key の Lock を取る前に、Root-Leaf Traversal をして、Key の存在を確かめる。（ B-Tree に存在しない Key は Lock することができないため。）その際、Leaf-Page に到達したとき、ページに読み書きするために Page Latch を取る必要がある。Page Latch を保持している間に、Lock Manager を通して、Key の Lock を取る。これはつまり、あるトランザクションが Page Latch を保持している間に、新たなトランザクションがその Page に書かれている Key の Lock を取ることができないことを意味している。しかし、これは　Page Latch を取得できたからといって、誰も Key を Lock していないことを意味しない。ページに対する物理的な操作と Lock の取得が完了すれば、Page Latch は解放されるが、Lock が解放されるのは、2PL ではトランザクションの Commit 時であるから、Page Latch が解放されていても、誰かがそのページに書かれた Key に対する Lock を保持している可能性は大いにある。

  • Insert も Select, Update, Delete も必ず leaf-page の Latch をとってから、Key を Lock する。この順序を徹底することが重要である。

  • Select

leaf_page = B.Traverse(key); // hold S latch on the page
slot = leaf_page.find(key);
if slot.key == key then // Exact match
  L.Request-Lock(key, SN);
  if slot is not ghost then
    return (slot.data)
  else
    return (Error: Not-FOUND)
else // Non existent key
  if slot < 0 then // hit left boundary of the page
    L.Request-Lock(leaf_page.low_fence_key, NS);
  else
    L.Request-Lock(slot.key, NS);
  return (Error: NOT-FOUND)
  • Insert
leaf_page = B.Traverse(key); // hold X latch on the page
slot = leaf_page.find(key);
if slot.key == key then // Exact match
  L.Request-Lock(key, XN);
  if slot is not ghost then
    return (Error: DUPLICATE)
  leaf_page.replace_ghost(key);
else
  if slot < 0 then
    L.Check-Lock(leaf_page.low_fence_key, NX); // Check if there is any conflict
  else
    L.Check-Lock(slot.key, NX);
  begin System Transaction
    leaf_page.CreateGhost(key);
  L.RequestLock(key, XN); // lock the ghost
  leaf_page.ReplaceGhost(key);
  • Delete (User Transaction)
leaf_page = B.Traverse(key); // hold X latch on the page
slot = leaf_page.find(key);
if slot.key == key then // Exact match
  L.Request-Lock(key, XN);
  if slot is not ghost then
    leaf_page.to_ghost(key);
  • Delete (System Transaction)
    • System Transaction は Lock をとらないことに注意。ただし Lock に Conflict があるかをチェックはする。
leaf_page = B.Traverse(key); // hold X latch on the page
slot = leaf_page.find(key);
if slot.key == key then // Exact match
  prev_key = slot.get_prev_key(slot.key);
  if (L.Check-Lock(key, NS) && L.Check-Lock(prev_key, NS)) || (L.Check-Lock(key, NN) && L.Check-Lock(NN)):
    leaf_page.compact(key);
    L.Merge-Lock(prev-key, key); // merge this key's lock with prev's. remove this key's lock.
  • Update
leaf_page = B.Traverse(key); // hold X latch on the page
slot = leaf_page.find(key);
if slot.key == key then // Exact match
  L.Request-Lock(key, XN);
  if slot is ghost then:
    return (Error: GHOSTED)
  leaf_page.update(key, val);
else
  return (Error: NOTFOUND);
  • System Transaction の Log は一行で済むことが多い。最悪のケースだと BEGIN, DO, COMMIT の 3 行書かないといけないわけだが、これらをまとめて一行のログで済ませることができる。また、Rollback をすることもないので、Before-Image を書く必要もない。After-Image を節約する方法も存在する。Careful Write Ordering といって、例えば B-Tree の Page Split をするとき（ A -> A', B と Split されるとする。）このとき、B -> A' の順番で Dirty なページをディスクに flush する場合、書くべきログの量が減る。もし A' -> B の順番でページをディスクに書いてしまうと、例えば、A' がディスクに書かれていて B がディスクに書かれていない時、B のページを復元するためには、ログに B のページに Split 後に挿入された全てのレコード情報がなければならない。しかしもし B -> A' の順番でディスクに Dirty なページが書かれている場合、B のログには、A の Split Key だけで済む。B のページがディスクに書かれる前にクラッシュしてしまった場合、A のページがバックアップとして働くので、B のページは A のページと Split Key から復元できるからだ。
  • Partitioned B-Tree については面白いが Log に大きく関係してこないので詳細は略。特に面白いのが、巨大な B-Tree に大量のデータを Insert したいとき、各データに対して Insert を呼ぶか、巨大な B-Tree を再構築する必要があるが、Partitioned B-Tree だと大量のデータを別 Partition として入れるだけで済むこと。Partition の追記には minimal logging と Careful write ordering が使える。

リカバリのテクニック

  • WAL はページ単位で書かれているという前提である。
  • Redo 時に、ログページを読み、そのページに書かれている各ログレコードがどの B-Tree ページを参照しているのかを確認して、非同期に B-Tree ページを Prefetch できる。
  • Undo 時には、トランザクションの開始時まで戻る必要があり、そのログか書かれているログページが Buffer Pool に存在するとは限らないため、Undo 時に新たにログページを読まないといけないことがある。
  • リカバリ時にログレコードを (page_id, lsn) でソートしておくと良い。こうすると、Redo 時にページが Buffer-Pool から evict されて再度読み出すような無駄がなくて良い。
  • チェックポイントログレコードに書くトランザクションが保持しているロックを書くことで、Log Analysis Phase でロックを取ることができる。これをやると、Analysis Phase で全てのロックを取り終えて、Redo Phase から他のトランザクションを受け入れることができる。チェックポイントに書かれているロックに関しては Conflict を気にする必要はない。なぜならクラッシュが起きる前にそれらのロックに Conflict がないことが保証されているからである。
  • リカバリ時に必ずしも進行途中のトランザクションを Rollback する必要はない。

Discussion