###### tags: `TransactionalInformationSystems`

# 9章 インデックスにおけるConcurrency Control

## 概要

インデックスの中でも特にB+木に着目して同時実行制御を考える。

2層スケジュールで、上層はアクセスレイヤ、下層はページレイヤを想定する。アクセスレイヤにおいてはphantom records問題を避けるため述語指向のロックを考える。ページレイヤについては2PLに類似するプロトコルを用いるが、B+木の特殊な構造と限定されたアクセスパターンに起因して、それ専用に効率を上げたチューンができる。最後に2層ロックプロトコル全体のオーバヘッドを減らすための最適化を考える。

## B+木の概要

B+木はページを葉ノードとする木構造で、葉の深さが均一である。葉ノードは、DBに存在するインデックス対象の値を全て保持し、それらのキーに対応するレコードのRIDリストが続く。キーと対応するRIDリストの組をleaf node index entryといい、各葉ノードは複数のentryからなる。内部ノードは複数のinner node index entryからなり、これはキー値と下のレベルのノードへのポインタの組である。

最も右の子へのポインタを持つような、葉以外のノードにおけるindexエントリは、キーを持たずポインタのみ保持する。

最も右のエントリは、その部分木のキーが全てその左のエントリのキーよりも大きい。また、それ以外のエントリは、部分木のキーが全てそのキーよりも小さい。各内部ノードは、キーの数よりちょうど1つ多い子を保持し、それら部分木のキー値が間の値をとるということ。

この性質から、根から葉への$\log n$時間キー探索が可能。範囲検索も効率よく可能にするために、葉ノードをソート順で連結するポインタを保持することも一般的である。

通常のB木と同様、ノードの追加時に葉ノードに余白が無ければ、ノード分割が葉レベルから根まで順次伝播していく。ノードの削除も、キーの数がしきい値を下回ったらノードを再帰的に統合する。

## アクセスレイヤにおけるキー範囲ロック

インデックス構造のアクセスレイヤ、つまりキー・キー範囲のレベルでのロック制御を考えていく。

インデックスが提供すべき4つのADTインタフェース$insert(key,RID), delete(key,RID), search(key), range\_search(lowkey, highkey)$を考える。

インデックスに対するCCで考える必要がある問題：

1. 値の区間に対するロックを管理できる必要がある。各値がどの区間に包含されるかの判定も効率よく行いたい。
2. 値の区間を一括でロックした場合、冒頭の値は即座にアクセスを終えるにもかかわらずトランザクション終了時まで保持されることになってしまい、効率が悪い。

このような問題に対処するため、インデックスに対するロックはインクリメンタルに構築する。
操作$next(currentkey,currentpage,highkey)$を定義する。これは、現在のキー番号とページ番号、上限キー値を受け取ったうえで次のキーとそのページ番号を返す操作。これを定義すると、$range\_search$は最初の$search(key)$と、その後に連続する$next$で記述することができる。
従って、考える必要があるのは$search, next, insert, delete$においてどのようにロックを制御するか。

もう一つ重要な要素は、区間をロックすることの意味をはっきりさせること。あるキーをロックすることと、そのキーから始まって直後のキーまで続く区間をロックすることを同値とみなす。

例えば、キー$1,3,5$がインデックスに存在していたとき、キー$3$は半開区間$[3,5)$を表しており、キー$3$をロックするとその区間がロックされたものと考える。

このように考えることで、範囲検索中に区間内の値が追加されたり欠損したりする事故を予防できる。

### Incremental Previous Key Range Locking Rules

- $search(x)$は、$x$がインデックスに存在すれば$x$に対するread lockを要求する。インデックスに存在しなければ、$x$より小さい中で最大のキーに対するread lockを要求する。
- $next(currentkey,currentpage,highkey)$は$currentkey$に対するread lockを要求する。
- $insert(y,RID)$は、$y$と$y$より小さい中で最大のキーに対するwrite lockを要求する。
- $delete(y,RID)$は、$y$と$y$より小さい中で最大のキーに対するwrite lockを要求する。

insertやdeleteが、その値自体だけでなく、直前の存在するキー(previous key)にもロックを必要とするのがポイント。これらのロック獲得規則に加えて2PLを適用したものがprevious key lockingで、以下の定理で正当性が保証される。

### 定理9.1

Previous key lockingは、インデックス操作に関する限りconflict serializableなスケジュールを出力する。

#### 証明

もともと実現しようとしていた操作search, range_search, insert, deleteの間の衝突関係が、インクリメンタルなロックによって実際に正しく認識されることを証明すればよい。インクリメンタルなロックは2PLに従って適用されるのでそれで十分。

まず、$search(x)$と$insert/delete(y,RID)$の衝突は、$x=y$ の場合のみ生じうる。$search(x)$が失敗した際に、そのトランザクションが終了するまで$x$が挿入されないことがserializabilityのために必要であるが、$insert$も失敗する$search$も、$x$より小さい最大のキーに対してロックを要求するのでこのようなケースは検出され、予防される。

また、$range\_search(lowkey,highkey)$と$insert/delete(y,RID)$の間の衝突は、$y$がlowkeyとhighkeyの間にあるときに起こりうる。この場合も、$range_search$はlowkeyとhighkeyの間のキーをnext操作でロックをかけながら渡っていき、$insert/delete$は少なくとも一つのそのようなキーに対してロックを要求することになるため、これらの間の衝突はきちんと検出される。

最後に、インデックスが同じ値を一つしか許さない場合、二つの同一値$insert$が衝突しうる。この場合も直前のキーへのロックが競合するため検出される。$\square$

## ページレイヤでの技術

次にB+木の内部構造を考えたページレベルでのロックを考える。

各search,insert,deleteといった操作は、B+木の根から始まって葉へ下りていき、辿り着いたノードに何かしら操作するようなサブトランザクションとなる。

B+木はノードの分離や併合といった構造の変化をともなうため、insertやdeleteといった操作の並列実行に問題が生じうる。

問題を防ぐためにもっとも容易なのは、サブトランザクションの制御に2PLを用いてしまうことであるが、B+木特有の構造とアクセスパターンを用いてより洗練されたロック制御を考えていくことにする。

3種類のアプローチを考える。

1. ロック連結：4章でのツリーロックを洗練させたもの
2. リンクテクニック：B+木様の構造の実装特有の性質を利用した技術
3. ギブアップ：楽観的な方法

### ロック連結

まずロック連結のロック獲得規則を記述する。

1. searchとrange_searchは、ノードにアクセスする際、そのノードへのread lockを必要とする。insertはwrite lockを必要とする。
2. search, insert, およびrange_search冒頭の根から葉への降下において、ノードへのロックが許可されるのは、そのノードがフリーかつ、そのノードの親のロックを保有している場合のみである。
3. searchは、子へのロックを獲得したとき、そのノードのロックを解放してもよい。
4. insertは、(a)子へのロックを獲得し、(b)そのノードがsplit-safe(キーをもう一つ足しても分割が起こらない) なときのみ、そのノードへのロックを解放してもよい。
5. range_searchが葉ノードへのロックを許可されるのは、その親ノードか直前の葉へのロックを保持している場合のみである。前者は冒頭の根から葉の降下に、後者はnext操作による葉の連鎖に関連する。
6. next(currentkey, currentpage, highkey)はcurrentpageへのread lockを必要とし、直前の葉へのread lockを保持している場合に許可される。

このように、ツリーロックにinsertの例外を設け、またrange_search,next用の規則を追加した形になっている。これが成立する根拠としては

- searchは根から葉の一方向、1つのパスに沿ってしかアクセスしない。
- insertも同じアクセスパターンだが、パスの道中にsplit-safeでないノードがあった場合、そこでノード分割が起きる=アクセスが葉から根の方向へ伝播する可能性があるためロックを保持しておく必要がある
- range_searchは根から葉への降下、葉の間の移動という2つの過程から成り立ち、前者はsearchと同様に、後者はprevious key lockingのように制御すればよい。

ということがある。

#### 定理9.2-9.3

insert, search, nextに対するロック連結が出力するスケジュールはOCSRである。

##### 証明

insertとsearchに関しては、読み書き可能なツリーロックを拡張したプロトコルになっており、読み書き可能ツリーロックで問題になるのは読み込み操作にともなうロックの追い越しだった。一方、ロック連結では、insertは常に根から一貫してwrite lockを獲得していくためそのようなpitfall問題は発生せず、OCSR性が維持される。

nextに関して示す。インデックス操作の間に衝突サイクルが存在すると仮定し、その中に、葉$p$から$q$へ移るnext操作が含まれるとする。このようなサイクルが生じうるには、少なくとも1つのinsertもしくはdeleteが$r(p)$と$r(q)$の間に挟まれなければならない。insert/deleteが$p$で起こる場合には、nextが$p$を読み終わってからでないと$p$に対するロックを獲得できないので問題ない。$q$で起こる場合は、ノード分割が発生した場合は$q$の右側の葉にしか影響がなく、$p$は影響を与えない。したがってnextとinsert/deleteは逐次的に実行される。

ツリーロックがOCSRであり、またnext操作の追加もこの性質を変えないためOCSRである。$\square$

---

insertのノード分割のためのロック逆伝播にともなうオーバヘッドを緩和するため、葉以外のノードはread lockで始め、ノード分割が起きたときのみwrite lockに変換するという方法が考えられる。ただしこれはlock conversionを含むためデッドロックの危険がある。他にも、葉以外のノードはread lockで進め、ノード分割の必要が発生した時点でabortしてinsertをやり直すという方法も考えられる。ノード分割の頻度がそれほど多くないことを踏まえると、効率的。

ページレイヤでのロック連結とアクセスレイヤでのインクリメンタルなキー範囲ロックを組み合わせると次を得る。

#### 定理9.4

ページレイヤでのロック連結とアクセスレイヤでのインクリメンタルなキー範囲ロックによる2層スケジューラは、木削減可能なスケジュールを出力する。

##### 証明

search, insert, delete については、6章から、下層のOCSR性と上層のCSR性が全体の木削減可能性を保証することにより示される。問題となるのはやはりrange_search内のnext操作になる。

定理9.3より、search/insert/deleteと単一のnextの間の分離性は示されているのだが、searchに続くnextの連続としてのrange_searchについては示されていない。

考える必要があるケースとしては

$$search_i(lowkey)\rightarrow insert_k(x,RID1)\rightarrow next_i(currentkey1,highkey)\rightarrow insert_l(y,RID2)\rightarrow next_i(currentkey2,highkey)$$

のように、range_searchの中途にinsertが挟まれるような場合になる。deleteについても同様。

このような実行順になっていたとき、キー$x$は$[lowkey,currentkey1]$に含まれない。なぜなら、含まれていたらロック競合を起こし、このような実行順にならないため。同様に$y$も$[lowkey,currentkey2]$に含まれず、これらのinsertによるサブトランザクションはrange_searchの左側に孤立した部分木として括り出すことができる。

このように、range_searchが既に参照したキーに対して、その実行中にinsertを織り交ぜることはできず、逆にrange_searchの見るキーをinsertしたいのなら、完全に独立した順序で行う必要がある。

以上より、4種のアクセスレベルでの操作は全て孤立させることができ、定理9.1と合わせて木削減可能である。$\square$

最後にdelete操作も加える。普通にキーを削除するとB+木の構造変化が起こってしまうが、それでは面倒なため、キー削除の際には少し特殊な処理をする。ノードから全てのキーが削除されて完全に空になるまでは木につないだまま保持し、完全に空になって初めて親、及び隣接する葉から切り離す。並列実行しているトランザクションの問題を避けるため、ノードが空になった時点でアクティブだったトランザクションが全て実行終了した時点で切り離しを行う。これを*drain technique*と呼ぶ。空になったノードは、切り離しまでの間次の葉へのリンクを保持し続けることに注意。

### リンクテクニック

ロック連結からさらにロック条件を緩和し、効率を上げることを考える。着目するのは、「search/range_search中に、乗っかっているノードでノード分割が起こっても別に問題なくね？」ということ。

例えば、葉ノードがキー$(11,12,14,15,16,17,18)$を含み、区間$[15,18]$に対するrange_searchが現在$16$にいる状態を考える。このタイミングで$insert(13)$が実行されたとすると、ノード分割が起こって$(11,12,13,14), (15,16,17,18)$に分かれる。次に実行されるrange_searchのnextは、現在いるノード$(11,12,13,14)$にいったんはロックをかけるが、次のキー$17$を見つけるために葉のリンクを即座に辿ってしまう。つまり、ノード分割の並列実行がrange_searchに問題を起こしていない。

このような自動でノード分割に対応する現象は、単一キーのsearchにも一般化できる。searchはキーが現在のノードになければひたすら右へリンクをたどればよいため。

これを踏まえて、searchやrange_searchにおける根から葉への降下、およびrange_searchにおける葉のリンク連鎖の過程において、現在のノードに対するロックしか保持する必要がなくなる。親/直前の葉に対するロックはいらない。

その一方、insertについては、insert同士の制御を適切に行うため、ロック連結に従う必要がある。deleteはdrain techniqueを用いる限りにおいてはsearch同様ロックを緩和してよい。

このようにロックのオーバヘッドを減らせるリンクテクニックであるが、葉のリンクを逆方向にもたどりたい場合(逆順のrange_search)には使えないことに注意。B+木の双方向リンクは多くの商用システムで採用されている構造であり、その場合リンクテクニックは適用されていない。

### ギブアップ

楽観的な手法で、根から葉への降下の際にロックを使わない。(あるいは簡単なラッチ程度)

代わりに、各ノードが、それ以下のノードが持ちうるキーの値の上界と下界を保持し、ノード分割が起こった際に更新する。

searchの途中で、検索中のキーの値がそのノードの区間に収まっていないことが判明した場合、ノード分割が起こっていることを意味する。このようなケースのみ、ロールバックして最初からsearchをやり直せばよい。

ノード分割の頻度が低いようなケースではオーバヘッドが少なくて優秀なアルゴリズム。

## さらなる最適化

### デッドロックフリーなページラッチ

トランザクションのロック要求パターンがDAGを形成しているときにはデッドロックが起きない。インデックス操作においても、insertがロック連結の規則に従うorノード分割が起きるときは2回目のサブトランザクションでwrite lockを用いて分割するなどすれば、デッドロックフリーになる。

そうなると、明示的なロックテーブルを使う必要はなくなり、簡易的なラッチで問題なくなる。ラッチは多くの場合ページヘッダのフラグで実装されており、ページ単位での排他制御を機械語レベルの効率で実現できる。

### キー範囲ロックの強化

ここまで考えてきたアクセス制御では、2つの同じキー範囲に対するinsertはロックが競合してしまう。だが、実際のところ、2つのinsertはどちらが先に実行されても全く問題ないため、これらの並列実行を許したい。

もう一つの問題として、searchとinsertの間の非対称性がある。searchが先に実行されている場合には、insertがブロックされるためにはprevious keyへのロックも要求する必要があり、previous key lockingは必要不可欠な過程である。その一方で、insertが先に実行されている場合には、ブロックされる必要があるのは新しく挿入されたキーのみであり、previous keyまではsearchも読んでいいはずである。つまり、こちらではprevious key lockingは冗長である。

一つ目の問題を解決するために、insert専用のロックモードinsert lockを導入する。これはキー範囲をロックするもので、insert lock同士は共有可能で、read/write lockとは競合する。

二つ目の非対称性を利用してより無駄を減らすために、insertの挙動を少し変える。previous keyがフリーであることのチェックは行うが、ロックは要求せずに新たなキーの挿入を行う。実装においては、instant duration(瞬間)ロックを用いる。これは、取得の直後に解放されるようなロックである。新たに挿入されるキーの方は従来通りロックされる必要があるのに注意。

deleteについても、RIDリストが空になってもキー自体は残すようにすれば、削除したいキーへのwrite lockのみで適切なアクセス制御が可能になる。RIDリストが空になったゴーストキーは、それを参照したトランザクションが全て終了したようなタイミングでガーベジコレクションすればよい。

以上から、insert/deleteに対するインクリメンタルなキー範囲ロック規則は以下のように緩和できる。

- insert(y,RID)は、yへのinsert lockと、直前のキーへのinstant duration insert lockを要求する。
- delete(y,RID)は、yへのwrite lockを要求する。

### ロックのオーバヘッドを減らす

アクセスレイヤとページレイヤでそれぞれロックを用いた場合、n個のインデックスがあるテーブルでinsert/deleteを行うと、同時に(n+1)個のロックを管理する必要が出てきてオーバヘッドが大きい。

ロックをまとめてしまい、キーとRIDの組、もしくはRIDのみに対するロックのみを考えると、並列性は低下するがメモリのオーバヘッドが減少する。時空間トレードオフ。

特に、RIDのみに対するロック、かつ同じレコードに対する全ての属性を一括ロックするものを考えると、ロックは一個しか必要なくなる。これは基本的には並列実行性を悪化させるのだが、「一つのキーに対して多数のRIDが紐づいている」ような特殊ケースにおいてはむしろ並列性が高まる場合がある。

### 透明なバージョニングの利用

インデックスのエントリを複数バージョン保存し、ROMVのようなプロトコルを用いれば並列性は高まる。

## 演習問題

### 9.1

インクリメンタルキー範囲ロックは、正当性の証明からも分かるように変更なく唯一値制約インデックスにも適用できる。

instant duration lockとinsert lockを用いた最適化を適用する場合は、insert lockどうしが競合するように設定する。唯一値しか許容されないため、競合が検出された時点でそのinsertは諦める。

### 9.2

インデックス内の最小のキーよりもさらに小さいキーをinsertしたいとき、このままだと直前の葉が存在せず、適切なロックができない。

従って、どの値よりも小さい最小の葉を番兵として最初から配置しておくことにする。

### 9.3

#### Q

2つの最初存在していないキーのInsertは競合してブロックを生じうるが(例：27も28もインデックスにないとき、先のInsert(27)は後のInsert(28)をブロックする)、本来可換なはず。この競合を避けるための方法はあるか？

類似する状況におけるDelete/DeleteどうしやInsert/Deleteについては？

#### A

**キー範囲ロックの強化**で論じられた最適化を用いれば解決する。

- 直前のキーへのinstant duration lockは一瞬しかロックをかけないので、2つのInsert操作の間にブロックは起こらない。
- Deleteは削除するキーにしかロックをかけないので、異なるキーの削除は互いに競合しない。
- Insert-Deleteについても、全く同じ理由で互いに競合しない。

### 9.4

ユニーク制約のあるインデックスで、キーが既に存在して失敗する場合のロックの要件は？