Transactional Database を作りたい

Rust

セキュリティキャンプ2018のデータベースの講義に関するツイートがTLに流れてきたのを見て、自分もデータベース作ってみたいなぁと思ったので作り始めることにした。 データベースを作るのは初めてなので、まずは「トランザクションのあるデータベース」と言い張れる最小限のものを作りたい。

ということで「ぼくのかんがえたさいじゃくのデータベース」の仕様を作った。明日から頑張る。

概要

  • 表形式ではなく、key-value store にする
    • key も value も String 型
  • トランザクションをサポート
  • クライアントは逐次的に処理する
  • データの総量がメモリに収まると仮定する

コマンド

以下の4つのコマンドをサポートする。

read KEY
write KEY VALUE
commit
rollback

クライアントは TCP でデータベースサーバーに接続してコマンドを送りつける。

ACID

Atomicity

トランザクションの結果が、コマンドが全て実行された結果か、全く実行されなかった結果のどちらかになる性質。

Consistency

……このデータベースの場合、満たすべき制約は存在しない？

Isolation

トランザクションの過程が他のトランザクションから観測されない性質。 このデータベースではそもそも複数のトランザクションを同時に実行しないので自動的に満たされる。

Durability

成功したトランザクションの結果が（たとえデータベースやコンピュータがクラッシュしても）失われない性質。

設計

  • Rust で作る。
  • メモリ上に HashMap として key-value store を持つ。
  • ディスクに WAL を書く。
  • 起動時に WAL を先頭から全部読んで HashMap を再生する。
    • このとき、WAL の末尾の未コミットのレコード列は truncate する。
    • 中途半端に書かれた WAL のレコードは truncate する。このために WAL のレコードには CRC64 をつけておく。