Page を実装する

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

はじめに

どうも、なんかブログ記事を書きまくってたら右手親指の付け根が痛くてたまらないけんつです。
今日は Page の実装に関する話です。

BufferPool あたりの実装が完了した段階で思ったことなどなど書いていきます。

Page の実装

基本的に Page Header と Tuple の塊となっている。
先頭 4byte を Page Header として、残りの領域で Tuple を追加された順番で保持する単純な構造になっている。
全体の容量は約 16 KB で固定。mmap は使用しない。

バイナリへのシリアライズなどなどは、前回実装したタプルのシリアライズをそのまま使う。
というのも、Page Header が今のところ 4 byte しかなく、あとはタプルが列挙するだけどとわかっているからバイナリにシリアライズするのは比較的簡単にできるようになっている。

また、ページは単にテーブル毎のディレクトリに格納されているだけでヒープや単方向リストを使って参照を持っているわけではない。

削除を考慮しない

削除を考慮しないのであれば、ただタプルを列挙すればいいだけとなる。
しかし、これで削除を考えようとすると一気に考えることが多くなる。

というのも、テーブル単位でそれぞれページを複数もっているが、タプルが追加されるだけとわかっていれば既に存在しているページを探索して空きスロットを探すとかしなくても良いため。

もしも削除を考慮するとするなら、同時実行制御をどのように実装するかを考える必要がある。
というのも、仮にデータを追加・更新する際に、PostgreSQL のように追記型を採用しているなら単にページを追加していき、タプルを末尾に追加すればいいだけとなる。削除なら単に論理削除すればいいだけなのでそこまで難しくない。

しかし MySQL の様に、更新型を取る場合は削除を考慮すると空きスロットが発生する可能性がある。
これを単にタプルを並べただけの構造から見つけ出すのは明らかにコストとなる。

これは CMU の講義のなかでも触れられている。
それらの問題を解決するために Slotted Page や Log-Structured File Organization などがある。
今回はそういった実装を現段階ではしないこととしている。

番外

特にタプルとページは愚直に実装したので特に話すことがない。
だから少しだけ Golang でこまった配列、スライス周りの話をする。

これら固定長のページやタプルを実現するために、固定長の配列を基本的には使用している。
例えばページを扱う構造体はこうなっている。

// Max Size: 16KB
type Page struct {
        Header PageHeader // 4byte
        Tuples [PageBodySize]Tuple // 128 byte per Tuple
}

そう、ここから固定長にしている。
ただこれの問題は色々あって、この配列を扱う場合はその関数やメソッドの引数や戻り値の型を全て固定長にしないといけない。
そのため、スライスで扱ったあり配列として扱ったりとかなり処理が忙しないことになっている。

Golang, 排他制御とかめちゃくちゃ便利なのに配列、スライスまわりとリスト、循環リストなど
データ構造に関わる部分が柔軟でないから少し実装にこまるときがある。
これは Clock Sweep の実装と、 Buffer Pool の実装でも同様に頭を悩ませた。

おわりに

次は Clock Sweep だったかな、そろそろメモリ上でページやタプルを管理する話になる。