それが僕には楽しかったんです。

ミドルウェアとかやってます

CMU Database Systems をひたすら追っていく ~09 Index Concurrency Control ~

この記事は「 けんつの1人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar 」 7日目の記事です。

はじめに

どうも、最近このアドカレの一週間分をみてこれあと二週間半分やるのかと思うとすごく辛い気持ちになっているケンツです。
今回はインデックス、つまりここでは B+ Tree の同時実行制御についてやっていきます。

Index Concurrency Control

同時実行制御プロトコルは共有オブジェクトでの同時操作において正しい結果を確保するために DBMS が使用する方法を指す。
ここで言う「正しい」とは主に2つの意味合いがあり、

  • 論理的正確性: 表示されるはずのデータを表示できるかどうか。スレッドが読み取りを許可する必要のある値を読み取ることが出来るかどうかに関わってくる。
  • 物理的正確性: オブジェクトの内部表現が適切かどうか。データ構造内にスレッドが向こうなメモリ位置を読み取るポインタが存在しないことに関わってくる。

ここでは論理的正確性に重点を置いて進めていく。

Locks vs Latches

以前にもどこかで書いた記憶があるけど、ロックとラッチの話。インデックスにおけるロックやラッチの話なので再度ここにまとめおく。

Lock
Latches
  • Index の内部データ構造の重要なセクションを他のスレッドから保護する。
  • 処理が行われている間適宜発生する
  • DBMS は変更をロールバックさせる必要はない

またラッチには2つのモードが存在する

  • READ: 複数のスレッドが同時に同じアイテムを読み込むことを許可する。スレッドは別スレッドが読み取りモードで持っている場合読み取りラッチを取得することができる。
  • WRITE: 1つのスレッドのみがアイテムにアクセスできる。他のスレッドがいずれかのモードでラッチを取得している場合、スレッドは書き込みラッチを取得できない。

Latches Crabbing/Coupling

Crabbing / Coupling*1 は複数のスレッドが同時に B+ Tree にアクセス/変更を許可するための決まりのこと。
次のような手順を取る。

  • 親のラッチを取得する
  • 子のラッチを取得する
  • 安全に操作できる場合は、親のラッチを解除する。

ここでいう安全に操作できる場合とは更新時にノードの分割が行われたり、マージされない状態を指す。

基本的なラッチの手順として更に細かく見ていく。

  • 検索: ルートから開始して下に移動し、子のラッチを確保してから親のラッチを解除する
  • 挿入/検索: ルートから開始して必要に応じて任意の数のラッチを取得する。その後、子をラッチを取得したら安全かどうか確認する。安全な場合は全ての親のラッチを解除する。
Improved Lock Crabbing Protocol

このように一見素晴らしく見えるラッチのプロトコルにもいくつか問題がある。というのもトランザクションが挿入・削除を行う場合排他的なラッチを取得するがこの排他的ラッチはルートから取られているというがまずい。
ルートから排他ラッチが取られている場合、その並行性は大きく制限されてしまうから。

その代わりと言っては何だが、サイズ変更が必要なマージや分割が必要になることはまれであるためトランザクションは共有ラッチををリーフノードまで取得することができる。それぞれのトランザクションはターゲットリーフノードへのパスが安全であるということを想定し、 READ ラッチを取得し、検証することができる。

仮にパス内のノードが安全で無い場合は以下の様に動作する。

  • 検索: 上のものと同じ挙動をする
  • 挿入/削除: READラッチを検索の場合と同様に設定し、リーフに移動する。そのあとリーフに WRITE ラッチを設定する。リーフが安全でない場合は全てのラッチを解除し、上記の挿入/削除プロトコルを使用してトランザクションを再開する。

Leaf Node Scans

ここまで紹介したラッチはトップダウン方式を取る。*2
しかし、それを許容すると目的のラッチが使用できないといった場合が想定できる。その場合は別のスレッドがラッチを開放するまで待機する必要がある。これによりデッドロッ具が発生しない。
しかし、リーフノードスキャンでは2つの異なる方向から*3走査されるため、デッドロックの影響を受けることがある。またインデックスラッチではデッドロックの検出、回避をサポートしないことが多い。
そのため、この問題への対処は待機しないというモードをサポートする必要がある。スレッドがリーフノードでラッチを取得しようとした場合、その操作を中止してラッチを開放し、操作を再開させる必要がある。

おわりに

今回はそれなりに短い分量だったがインデックスの同時実行制御についてだった。
ここまででストレージに関するところは一段落したと思っているので、次回以降は実際の RDBMS ではどのような実装がされているかをまとめていく。
それが終わり次第、実装していく簡易的な DBMS の特にストレージ周りの設計をしていく。

*1:この2つをどう訳せばいいかわからない

*2:現在探索しているノードの下にあるノードからのみラッチを取得できる。

*3:左右両端から探索される