In Memory DBMS 実装記録

この記事は自作DBMS Advent Calender 2020 の19日目の記事です。

セキュリティキャンプ全国大会に参加してきました。 ここでは、キャンプでフルスクラッチで作ったインメモリDBMSの紹介をしていきたいと思います。

実装したもの

DBMSを作るといっても一人で作るにはもちろん限界があります。 そのため、実装を進める前にがんばる方向性を決める必要があります。 僕が選んだのは「トランザクションの並行制御」です。

実装したDBMSは次のようなものです。

• Key-Value Store
• Read / Insert / Update / Delete 操作に対応
• Index は標準ライブラリの concurrent hash map
• データの永続化、Crash Recovery を行う
• Conflict Serializability
• CC protocol は S2PL, MVTO を採用

実装の流れは次のようになります。

• 1つのトランザクションがシングルスレッドで動く（Trivial scheduler）
• 複数トランザクションがマルチスレッドで動く（CC Protocol: S2PL）
• 複数トランザクションがマルチスレッドで動く（CC Protocol: MVTO）

2つの CC protocol に挑戦しました。

システムの構成を図で表すと次のようになります。

Atomicity と Durability を実現するために WAL (Write-ahead Logging) が存在します。 Log は Commit が確定するまで DB 本体への反映を待つようにしているため、 Redo log のみを採用しています。

Redo log のみを保持するということで Write set を用意しています。 Write set は DB 本体とは別に管理され、 キャッシュのように振る舞います。 Redo log は DB 本体への変更データそのものである Write set から生成しています。

Checkpointing は DB の起動時と正常終了時のみ行っています。Disk への永続化の際は、temporary なファイルを用意して 最後に rename することで atomic に更新しています。

Crash recovery は checksum の再計算を行い、データの信用性を高めています。checksum のアルゴリズムには crc32 を用いました。

次に、トランザクションの並行実行制御部分について紹介します。

S2PL

まず初めに挑戦したのは、S2PL (Strict 2-phase locking) です。

Record ごとに mutex object を用意し、 reader-writer lock で排他制御を行いました。S2PL では write lock の解放を Commit 完了後に一気に行います。

自分は Go で実装していたのですが、標準ライブラリの RWMutex では reader lock から writer lock へ upgrade ができず、 他に信頼できそうなライブラリも見つけられなかったので自作することになりました。

ログを書くときは、単純なシングル WAL を採用しました。ログの書き込み前にロックをとっています。

S2PL では Deadlock が発生しうるのですが、回避策として単純な No-wait を用いました。ロックが競合したら すぐに Abort します。Deadlock preventionは、他の方法で難易度が高いものも多いらしく、挑戦しがいがあるようです。

Index は S2PL、MVTO ともに concurrent hash map になっています。 今回 Index の実装はさぼっていて、標準ライブラリを使っています。

MVTO

S2PL を実装すると、read が失敗、wait しまくるのが嬉しくないという気持ちになります。 そこで MVTO (Multi-version timestamp ordering) を実装しました。

トランザクションは開始時にタイムスタンプを割り振られます。

Record は複数の Version を持ち、 Version はデータと、Write-timestamp、Read-timestamp の2つのタイムスタンプを持ちます。 Readの際は自分のタイムスタンプと Version の Write-timestamp を確認して読むべき Version を判断します。

具体的には、次のようにタイムスタンプを確認します。

• Read は、自分より古い Write-timestamp の中で最も新しい Version を読む
• Write は、Record の最新 Version の Read-timestamp よりも自分が古い、もしくは同じ場合に成功する

MVTO の理論的な側面は、講師の星野さんが書かれた記事 が参考になります。

Record には Version の連結リストへのポインタと、排他用の mutex object を持たせました。 mutex object を持たせたのは、Read 操作のときに Version の traverse が行われるため、排他を行う必要があるからです。

Update や Delete の際には、key の存在確認をし、タイムスタンプの確認をせず Write set に記録させ、 タイムスタンプの確認は Commit 時に行うようにしました。

Commit 処理の流れは次のようになります。

func Commit() {
    
    // 全 Record の一括 Lock
    // 及び整合性チェック

    // Write-set → Index に反映

    // wal file に反映

    // Version GC

    // 一括 Unlock

}

Commit 時には、ロールバックをする必要をなくすため、操作対象の Record の一括ロックを行ってから データの反映、Logの永続化を行うようにしました。このロックとをとる際にタイムスタンプの整合性を確認しました。

Version の GC はCommit 処理の最中、ロックをとったついでに行っています。 起動中のトランザクションのタイムスタンプを保持する配列から最小のタイムスタンプを見つけ、 そのタイムスタンプより古いバージョンを連結リストから削除します。

以上、簡単に説明しましたが、ソースコードはこんな感じです。(mainブランチはMVTOになっています)

github.com

セキュキャンでの発表資料はこちらになります。

まとめ

今後時間を見つけてベンチマークをとってちゃんとスケールするのか確認したいです（また記事を書く予定）。 今回は実装の容易さや、習熟度的に Go で実装したのですが、 時間を見つけてC++もしくは Rust で再度実装するつもりです。

感想

CC protocol を2つも実装することができました。 同ゼミの人たちが強そうだったので不安に駆られ、 初めから全力で開発したのがよかったのかもしれません。

講師の星野さんには、レビューはもちろん、DB 界隈の話をしてもらったり、 (進路相談的なことまでしてもらい)大変お世話になりました。

振り返ってみると充実した2ヶ月間でした。 今後もDB関連で遊んでいければなと思います。