Closed7

"Database Design and Implementation" の SimpleDB に行ロックを実装

hmarui66hmarui66

概要

"Database Design and Implementation" で実装をする SimpleDB のロックの単位はブロック。行単位でロックしている自作 RDBMS を参考に、どのようにすれば行ロックを実装できるかメモしていく。

https://link.springer.com/book/10.1007/978-3-030-33836-7

配布ソース

http://www.cs.bc.edu/~sciore/simpledb/

実装ソース

https://github.com/hmarui66/simpledb/pull/2

参考

hmarui66hmarui66

SimpleDB のロック処理整理

概要

  • SS2PL を採用
    • commit まで共有ロックも排他ロックも保持
  • 10 秒以内にロックを取得できない場合は処理をアボート
  • ロック以前の pin buffer も空きが出るまで最大 10 秒待つ
    • storage に dirty write はしない

ブロックの read

next 呼び出し時

setInt 呼び出し時

参考

hmarui66hmarui66

SamehadaDB のロック実装の調査

参考ソース

行ロック処理の実装箇所

lock_manager.go に以下のメソッドが実装されている。

  • LockShared(txn *Transaction, rid *page.RID)
  • LockExclusive(txn *Transaction, rid *page.RID)
  • LockUpgrade(txn *Transaction, rid *page.RID)
  • Unlock(txn *Transaction, rid_list []page.RID)

ロックの呼び出し箇所をざっとまとめる

SamehadaDB の Next 呼び出し時のロック処理

※ LockManager 内部の処理は省略

###「RID に対応する tuple データ取得」の詳細

(mermaid のブロックが長すぎて描画エラーとなったので分割)

###「次のページから RID 取得」の詳細

(mermaid のブロックが長すぎて描画エラーとなったので分割)

メモ

SimpleDB の RecordPage は TableScan で使われている。

SamehadaDB の実装との対応関係は↓の感じ...?

  • table_heap, table_page: RecordPage
  • table_heap_iterator & seq_scan_executor: TableScan
  • Page に対するロック処理: ConcurrencyMgr & LockTable

table_heap, table_heap_iterator を見ると Page に対する WLatch や RLatch 操作をやっているが SimpleDB では ConcurrencyMgr & LockTable にページのロックは集約されている。

hmarui66hmarui66

SimpleDB の行ロック実装方針

  • LockTable を行単位に対応させる
  • Transaction で値を get/set する際に RID を特定して ConcurrencyMgr のロック処理に渡す
  • ConcurrencyMgr は渡された RID を用いて LockTable を呼び出し & 保持するロックの粒度を行単位にする
  • RID, 行ロック取得時にブロック(というかページ)単位で RLatch & RUnLatch する

疑問点

  • Phantom リードは起こるか？
    • 一度参照した行についてはロックを取得しているので書き換えられない
    • 初回には unused となっていた slot に insert がされると問題
      • 元々はページ単位でロックを取っていたので問題なかった
        • この対応は厳しいので一旦諦め
    • ページの追加が発生した場合も問題
      • 元々は end-of-file マーカーを用いて実質テーブル単位のロックを取っているので、問題は起きなかった
      • unused に対する Phantom を諦めたので、こちらも一旦諦め
  • 行ロックはいつ取るか？
    • TableScan の next 呼び出し時にとる
  • next 時に RID の特定と Tuple の取得タイミングを分ける必要があるか？
    • 特に分ける必要は無さそう
    • ただ、slot を参照する際に、事前に used flag を用いた有効性確認が必要になるので、有効性確認 & 値を読み込みの間に書き込みがされないようにする必要がある
      • SamehadaDB では page 単位の Latch で担保
hmarui66hmarui66

シンプルな TableScan だとまだ良いけど、次の段階では述語付きの SelectScan のことも考える必要ある

hmarui66hmarui66

TableScan 時の行ロック

  • 先頭から最後まで全てスキャンする TableScan において行ロックを実装してみた
  • 読み込み時には unused な slot 含めて lockShared
    • 実質的にテーブル全行を lock することになっている
  • 書き込み時には書き込み対象のフィールドに対するセッター(setInt, setString) 呼び出し時に lockExclusive
    • SimpleDB では tuple という概念がない
  • 手抜きでテーブルファイル末端の lock は外したので、ページ追加時の Phantom は発生する状況
    • ファイル末端を示す dummy ブロックと dummy の slot の値を用いて lock することで Phantom は発生しないようにできる
  • lockShared, lockExclusive ができない場合は Exception をスロー
    • 他によいやり方思いつかなかった

LockTable

元々ページ単位でロックを管理していたが、行単位で管理できるように変更。

https://github.com/hmarui66/simpledb/blob/2cf9e3fb168f58a9039015a5a1835517aeb4a7f9/src/main/kotlin/simpledb/tx/concurrency/rowlock/LockTable.kt#L7-L74

shared lock, exclusive lock 用の Map を RID 単位で管理するだけ。

BlockLatch

ページの latch を扱うクラスを実装した。

https://github.com/hmarui66/simpledb/blob/2cf9e3fb168f58a9039015a5a1835517aeb4a7f9/src/main/kotlin/simpledb/tx/concurrency/rowlock/BlockLatch.kt#L8-L40

  • 全ページの latch を集約管理する作りにした
    • SamehadaDB では各ページインスタンス自体に RWMutex を保持
  • ConcurrentHashMap の key が存在しない時に Atomic に put してくれる putIfAbsentを使ってみた

next 呼び出し時

setInt 呼び出し時

その他

新規ページ追加による Phantom read の防止も対応。

  • テーブルファイルのサイズ取得時にファイル末端を意味する dummy の block & slot の lockShared を取得
  • ファイルへのページ追加時に dummy の block & slot の lockExclusive を取得

対応箇所:
https://github.com/hmarui66/simpledb/blob/332ec65b4b522d13121cd0ee4a689de0fc365984/src/main/kotlin/simpledb/tx/rowlock/TransactionImpl.kt#L87-L107

実装内容

https://github.com/hmarui66/simpledb/pull/2

このスクラップは2023/09/02にクローズされました