Neunomizuの日記

俺だけが俺だけじゃない

# 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する時
    • 根から降りる
    • 子へのRlatchを取得する
    • そして,親のlatchを解放する
  • insert/deleteするとき
    • 根から必要に応じてWlatchを手に入れながら降りる
    • 一旦子の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に頼らず実装する必要があるのが面白い.