それが僕には楽しかったんです。

ミドルウェアとかやってます

ストレージ周りの設計を考える

この記事は「 けんつの1人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar 」 11日目の記事です。

はじめに

どうも、最近書き溜めた記事がなくなってきてエクストリーム開発になりそうであせっているけんつです。
今日はとりあえず、雑にストレージの全体構造を考えてみようかなと思っています。

詳細は、それぞれ実装した記事で書くのでかなり短くなりそう。

ストレージの設計を考える

ひとまずデータベースストレージから作っていくことにしたのでザッと設計を考えていく。
ただあくまでもこうやって実装したいなという目安なので今後変更する部分はありそう。

実装する DBMS の仕様

まず先に大まかな仕様から考える。
今回は次のような限定的な仕様とする。

  • SQL はCREATE, SELECT, INSERT の単純なもののみで削除などは考慮しない
  • 複数のクライアントからの接続を想定する
  • データ型は int32 相当の整数型と、文字列型の2つのみ
  • 各行はタプルのヘッダーなどを考慮しても 128 byte まで
  • 1 Page = 16 KB とする
  • 各行の先頭には必ず整数型の PK が存在する
  • PK には B Tree を使ってクラスタインデックスを貼る
  • タプルは固定長で、 128 byte 未満でもバイナリファイルになる場合に必ず 128 byte となる

ストレージの全体像を考える

f:id:RabbitFoot141:20191210005729p:plain

現状は次のように実装することを考える。

メモリ上の処理

今のところはメモリ上に置くものはバッファプールのみとしている。
これが同時実行制御を考慮し始め MySQL のような更新型を取る場合はチェンジバッファや、ロックも Two-Phase Locking などを採用する場合は
それ単体では ACID 特性を満たすのに不十分なことからログバッファを追加して、 WAL を実装する可能性も考慮している。

また図中にはないがこのバッファプールには、インデックスを保持する領域も存在している。

ディスク上の処理

基本的にデータを最大 16 KB のページとして保持することを考える。テーブルはページをひとつ以上保持することで実現する。
またテーブルには 128 byte が上限のタプルを 127 個最大で配置する。*1
ページはバイナリにシリアライズして保持するが、それは Protocol Buffer を利用するのではなく気合で byte 列にすることまずやってみる。
gob は事前にシリアライズをテストしていて、構造体を素直にシリアライズするとデシリアライズするために必要なデータとして 280 byte ほど容量が増えるため使用しない。

これらのディスク上に永続化する必要があるものは DiskManager のような何かを用いて行うが、出来るなら Direct I/O を使いながらやってみたい。

おわりに

これ、実はいくつかもう実装しているけど詳しいことはそれぞれのパートで書くことにする。
ここにまとめるには要素が多い。あと、DBMSってストレージがほとんどな気がしてきた。

*1:ページヘッダーを考慮するとタプルの最大数を127にする必要がありそう