# CMU DB 9. Index Concurrency Control
tags: CMU DB
今回はConcurrent(並行)とParallel(並列)という概念が登場します.前者は複数のタスクを同時に実行状態にすること,後者は複数を同時にすることという違いがあるっぽいです.1
授業
今までに話していたのはsingle-threadedの話.しかし,multi threadsを許すことでより有利に使える.実際のDMBSはこのようになっている.
a concurrency control protocolは共有したobjectに対する並行処理への結果が正しいことを保証するためにDBMSが使う.
- logical correctness
- スレッドが読みことが許されているべき値を読める
- physical correctness
- スレッドが不適切なメモリの位置を読むようにするポインターが我々のデータ構造にはない
latches overview
- locks
- latches
- 他のスレッドからDBMSの内部データ構造の大事な部分を守る
- 処理の間保持される
- 変化を巻き戻せる必要はない
- つまり短い
今回はlatchに注目する.lockは17回目に言及するらしい.
latch modes
- read mode
- 複数のスレッドが同じオブジェクトを同時に読める
- 別のスレッドがread modeでread latchを持っていたら,それを取得できる
- write mode
- オブジェクトを1つのスレッドしかアクセスできない
- どんなモードでも別のスレッドがlatchを保持していたら,write latchを取得できない
実装するには
- blocking os mutex
- 簡単
- 大規模化しにくい(時間がかかるから)
std::mutex
など
- test-andset spin latch(TAS)
- とても早い(single instruction to latch/unlatch)
- 大規模化しにくく,キャッシュに優しくない
- `std::atomic
- reader-writer latch
- 並行で読むことを許す
- starvation(あるプロセスにCPU時間が割り当てられないこと)を差来るためにread/write queuesを管理しなければならない
- spinlockの上に実装できる
hash table latching
並行アクセスを制限された方法でしかスレッドがデータ構造にアクセス出来ないことから簡単にサポートしている.全てのスレッドが同じ方向に動き,単一のページ/スロットしか同時にアクセスしない.デッドロックはありえない.
- page latches
- 各ページが全ての内容を守るそれ自身のreader-writer latchを持っている
- スレッドはread か write latechをページにアクセスする前に取得する
- slot latches
- 各スロットはそれぞれのlatchを持っている
- メタデータと計算的なオーバーヘッドを削減するために単一モードのlatchを使える
年のために言うとページ内にスロットはあります.
B+Tree latching
複数のスレッドがB+tree を同時に読み,更新できるようにしたい.
- あるノードの中身を同時に複数のスレッドが更新しようとしている.
- 別のスレッドがノードをsplit/mergeしている間にあるスレッドが木を走査する
という問題に対処する必要がある.
latch crabbing/coupling という手法で解消する.
複数のスレッドにB+ Treeに同時にaccess/modifyすることを許すプロトコル
基本的な考えは
- 親のlatchを手に入れる
- 子のlatchを手に入れる
- 「安全」ならば,親のlatchを解放する
safe nodeとは更新されたとき,splitもmergeもしないようもの
- findする時
- 根から降りる
- 子への
R
latchを取得する - そして,親のlatchを解放する
- insert/deleteするとき
- 根から必要に応じて
W
latchを手に入れながら降りる - 一旦子のlatchを取得されたら,それが安全か調べる
- 子が安全なら全ての祖先のlatchを解放する
- 根から必要に応じて
leaf node scans
ある葉から別の葉に行くときデッドロックが起こる可能性がある.
コーディングを練習することでしか,latchによるデッドロックの発見と回避に対応することは出来ない.
leaf node sibling latch acquisitionのプロトコルは"no-wait" mode(つまり,デッドロックを避けるため,次に行くノードのlatchが解放されていなかったらその処理を再始動するとうこと)を支持しなkればならない.
DBMSのデータ構造はlatchの取得の失敗に対応しなければならない.
delayed parent updates
葉がオーバーフローした際に,いつも少なくとも3つのノードを更新しなければならない
- 分割される葉ノード
- 新しく作られる葉ノード
- 親ノード
$B^{link}$Tree optionmization:親ノードの更新を遅延させるという最適化のための手法.
結論
スレッドセーフなデータ構造を作ることは実際には悪名高く難しい.
B+Treesに注目してきたが,同じくらい高いテクニックが他のデータ構造に応用できる
感想
今回はかなり面白かった.スレッドセーフをOSに頼らず実装する必要があるのが面白い.