この記事は「 けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar 」 7日目の記事です。
はじめに
どうも、最近このアドカレの一週間分をみてこれあと二週間半分やるのかと思うとすごく辛い気持ちになっているケンツです。
今回はインデックス、つまりここでは B+ Tree の同時実行制御についてやっていきます。
Index Concurrency Control
同時実行制御プロトコルは共有オブジェクトでの同時操作において正しい結果を確保するために DBMS が使用する方法を指す。
ここで言う「正しい」とは主に２つの意味合いがあり、
- 論理的正確性: 表示されるはずのデータを表示できるかどうか。スレッドが読み取りを許可する必要のある値を読み取ることが出来るかどうかに関わってくる。
- 物理的正確性: オブジェクトの内部表現が適切かどうか。データ構造内にスレッドが向こうなメモリ位置を読み取るポインタが存在しないことに関わってくる。
ここでは論理的正確性に重点を置いて進めていく。
Locks vs Latches
以前にもどこかで書いた記憶があるけど、ロックとラッチの話。インデックスにおけるロックやラッチの話なので再度ここにまとめおく。
Lock
Latches Crabbing/Coupling
Crabbing / Coupling*1 は複数のスレッドが同時に B+ Tree にアクセス/変更を許可するための決まりのこと。
次のような手順を取る。
- 親のラッチを取得する
- 子のラッチを取得する
- 安全に操作できる場合は、親のラッチを解除する。
ここでいう安全に操作できる場合とは更新時にノードの分割が行われたり、マージされない状態を指す。
基本的なラッチの手順として更に細かく見ていく。
- 検索: ルートから開始して下に移動し、子のラッチを確保してから親のラッチを解除する
- 挿入/検索: ルートから開始して必要に応じて任意の数のラッチを取得する。その後、子をラッチを取得したら安全かどうか確認する。安全な場合は全ての親のラッチを解除する。
Improved Lock Crabbing Protocol
このように一見素晴らしく見えるラッチのプロトコルにもいくつか問題がある。というのもトランザクションが挿入・削除を行う場合排他的なラッチを取得するがこの排他的ラッチはルートから取られているというがまずい。
ルートから排他ラッチが取られている場合、その並行性は大きく制限されてしまうから。
その代わりと言っては何だが、サイズ変更が必要なマージや分割が必要になることはまれであるためトランザクションは共有ラッチををリーフノードまで取得することができる。それぞれのトランザクションはターゲットリーフノードへのパスが安全であるということを想定し、 READ ラッチを取得し、検証することができる。
仮にパス内のノードが安全で無い場合は以下の様に動作する。
Leaf Node Scans
ここまで紹介したラッチはトップダウン方式を取る。*2
しかし、それを許容すると目的のラッチが使用できないといった場合が想定できる。その場合は別のスレッドがラッチを開放するまで待機する必要がある。これによりデッドロッ具が発生しない。
しかし、リーフノードスキャンでは２つの異なる方向から*3走査されるため、デッドロックの影響を受けることがある。またインデックスラッチではデッドロックの検出、回避をサポートしないことが多い。
そのため、この問題への対処は待機しないというモードをサポートする必要がある。スレッドがリーフノードでラッチを取得しようとした場合、その操作を中止してラッチを開放し、操作を再開させる必要がある。