DBMSを作りました

セキュリティキャンプ2021のY-IIトラックに参加して簡単なDBMSを0から作りました。

概要

DataBase Management System略してDBMSです。

  • Key-value store (KeyとValueはどちらもC++のstd::stringのみ)
  • select, insert, update, deleteができる。
  • S2PL(Strict two phase lock)でTransactionの並行実行制御ができる。

のようなDBMSを作りました。 またB-treeを実装する時に可変長のデータに対応するのが難しかったのでKeyとValueは長さが400-8=392以下のみしか対応していません。

リポジトリはこちら

github.com

実装したこと

  • Write ahead logging
  • Crash recovery
  • Buffer manager
  • Disk manager
  • B-tree
  • S2PLとC++20 co_routineを用いた並行実行制御(Single threadで)
  • Deadlock preventionのためのWait-dieアルゴリズム

当初の自分の目標はIn-memoryではないファイル上のB-treeを実装することとC++20のco_routineを用いた並行実行制御でした。 それらが動くところまで実装することができました。

ちなみに https://github.com/kappybar/mydb/blob/main/examples/example1.cpp こんな感じで動きます。

my_task transaction1(Table *table) {
    Transaction txn(&table);
    co_yield txn.begin();
    std::optional<std::string> value = co_await txn.select("key");
    co_yield txn.commit();
    co_return;
}

上のようなTransactionがあったときにco_yield,co_awaitのところで実行が中断されて、他のTransactionに処理が移ります。 こうすることでSingle threadで並行実行制御を試すことができます。

全体の構成

f:id:kapibara100:20211003152915p:plain Data operation(select, insert, update, delete)は最初にWrite-setに入れられます。 Transactionのすべての操作が終わって、Commitすると、Logを書いた後に、B-treeに反映されます。 そしてプログラムが終了する前にCheckpointingをして、B-treeの内容をData-fileに書き込みます。Data fileはただKeyとValueが並んだだけのファイルです。

B-tree

ファイル上のB-treeを実装しました。

B-treeひとつのノードを4Kibのページとして実装しています。In-memoryではないインデクスを作ろうと思うとメモリとファイルの間でpageをやり取りする必要があるので、メモリ上のレイアウトとファイル上のレイアウトを共通化する必要があります。

このレイアウトの方法はSlotted pageなどの効率の良い方法が存在しているのですが、自分はそれをするのが面倒だったのでKeyとValueに使われている文字列の長さに制限をつけて、ただそれらを並べただけのレイアウトにしました。ちなみに文字列の長さを制限することによってKeyやValueが複数のページにまたがることも防げて、実装が簡単になります。

またメモリ上のページがいっぱいになってしまった時に、どのページを退避するか選択するページ置換アルゴリズムを考える必要があります。 OSの仮想メモリのページ置換アルゴリズムと同じようによくアクセスするページをメモリ上に残しておくと効率が良くなります。 自分は実装が簡単そうだったので、Clockアルゴリズムを採用しました。 Clockアルゴリズムは時計の針のようにページを見ながら、Access bitがたっていないページがあればそのページを置換対象にするアルゴリズムです。

並行実行制御

S2PLを実装しました。必要になるたびにLockを獲得していき、一度獲得したLockを解放することなく、最後にcommitした後にすべてのLockを解放します。こうしてできた操作の列はConflict serializabilityを満たしていて、直列に実行したTransactionと、ある意味で等価な操作列と見なすことができます。

なお単純にS2PLを実装すると簡単にDeadlockが起きるのでDeadlock preventionなりDeadlock detectionのアルゴリズムを何か考える必要があります。 自分はDeadlock preventionのアルゴリズムを実装しました。No-waitというWaitしたらそのTransactionをAbortするアルゴリズムが一番簡単そうだったのですが、つまらなそうだったのでWait-dieというアルゴリズムを実装しました。

Wait-dieはそれぞれトランザクションに優先度を割り振っておいて、Waitできるのは優先度が高いトランザクションが優先度の低いトランザクションの持っているLockを要求した場合のみで、そうでない場合はAbortするというアルゴリズムです。こうすることで循環したWaitが発生しないのでDeadlockに陥ることはありません。

f:id:kapibara100:20211003154357p:plain:w300

Coroutine

並行実行制御といいつつSingle threadで動かしているので、同時に複数のTransactionが動いているわけではありません。 C++20のco_routineを用いて、Transactionの操作をインターリーブして実行できるようにしています。C++20のco_routineはライブラリ実装者向けの低レベルな機能しかないため、もし使いたければ自分でco_routineを使えるようにランタイムライブラリをつくるか、boostやcppcoroなどのすでに実装されているライブラリなどを使うかどちらかになります。

f:id:kapibara100:20211004211702p:plain:w500

自分はco_routineの勉強も兼ねて自分でランタイムライブラリ(もどき)を実装しました。 リポジトリのdb.hppのmy_task構造体がそれにあたります。たいしたことはできていないですが、co_routineの動くコードがあまりネット上に落ちていなくて、動くまでにちょっと苦労しました。一番詳しく書かれていたのは コルーチン - cpprefjp C++日本語リファレンス です。(当たり前ですが)説明が形式的な感じで自分はちょっと分かりづらかったです。でも参考になるコードがここに載っているのでそれらをいじって、どういうふうに動いているのか理解しました。

改善点

  • B-treeのコードを書いていて、とても複雑になってしまった。特に他の人にソースコードを見せたりするつもりもなかったので、自分一人で書いていて、コードが汚くなりがちだった。
  • B-treeの真面目な永続化をサボってしまったので、データベースの実行に必要なファイルがB-tree, Data, Logの3種類になってしまって、奇妙なアーキテクチャになってしまった。
  • co_routineのライブラリを作ったとは言ったもののたいしたことはできていない。Waitとかもco_routineのライブラリの方で処理できるといいかなと思いました。

感想

授業とかでもともとの雛形があるところから、なにか機能を追加したことはありましたが、自分で0から設計を考えて、ソフトウェアをつくっていくのは初めてだったので新鮮でした。自分はC++で競技プログラミングしかやってこなかったけれど、競プロで培われた、コーナーケースを考える力というかすべてのケースを考える力みたいなのがバグのないソフトウェアの開発にも通ずるところがすこしはあるなあと思いました。 B-treeとかは競プロやってなかったらもっとバグらせたと思います。

今回簡単なDBMSを実装してみて、既存のDBMSとかに尊敬の感情しか湧きませんでした。なんだかんだDBMS作るの楽しかったです。 いろいろと時間を割いてくださったりアドバイスをくださった講師、チューターの方、ありがとうございました。