Tuple を実装する

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

はじめに

どうも、最近バイトに卒研にアドカレと目を酷使しまくっていつも目が充血しているけんつです。眼球ってどうやって休ませたらいいんでしょうか。
そろそろ結構勉強だけという状況に飽きてきたので、ストレージから実装していきます。
まずは Tuple です。
行を表現するため本来であれば色々考慮する必要がありますが、比較的妥協を重ねてシンプルにしています。

実装

といっても、github で Pull Request を作りながら開発しているのでそちらを見ると全体像が見えてきます。
なのでここでは実装していて色々と考えたこと、妥協したことなどまとめます。

タプルの構成

Tuple は次の様に構成されます。

name	length
Magic Number	2byte
MinTxId	8byte
MaxTxId	8byte
Len	2byte
Tuple Body	var-length
total	128byte

Tuple Body

name	length
Magic Number	2byte
Data Type	2byte
Data Size	4byte
Data	var-length

コード上では以下の通りです。

type Tuple struct {
        Magic uint16
        MinTxId uint64
        MaxTxId uint64
        Len uint16
        Body [TupleBodySize]TupleData // TODO: fix length
}

type TupleData struct {
        Magic uint16
        Type uint16
        Size uint32
        Number int32
        String_ string
}

先行事例では、この部分は Protocol Buffer を使用していましたが、 TableSpace などでまとめて管理したい場合に
Protocol Buffer にまかせてしまうとかゆいところに手が届かなかったので
バイナリへのシリアライズは自作して byte 列に直しています。

gob をつかえばよいという声もあるかもしれませんが、あれはバイナリを構造体に変換するための情報もバイナリにシリアライズされるため 128 byte という固定長が困難と判断して使用しませんでした。

データ型の扱い

今回、自作する DBMS では int32 相当の int 型と varchar or text 相当の string 型があります。
これらは interface{} 型で扱ってしまうと gob を使うしかバイナリにシリアライズする方法がなくなってしまうので
TupleData 構造体でデータ型の分だけ専用にフィールドを持っています。

CMU の講義内では浮動小数点数の記載もありますがあれを実現しようとすると IEE754 あたりに準拠させる必要があるので今回はシンプルに実装できる文字列と整数としています。

タプルサイズ問題

これは完全に妥協点です。
タプルを固定長にしたせいで、構造体⇔バイナリの変換が複雑になってしまったために実際に保持できるデータは 70 ~ 80 byte 程しかないはずです。
これは明日まとめる Page の構成に大きく関係しているのでその時にまたまとめますが、1 Page = 16 KB という容量制限を確実に設けるために妥協しました。

おわりに

今回は複雑な処理の割にシンプルなタプルになったのでここまでです。
明日はページについて書きます。