はじめに & TupleのSerDe （一人自作RDBMS Advent Calendar 2025 1日目）

この記事は「一人自作RDBMS Advent Calendar 2025」1日目の記事です。

はじめに

私は数年前から趣味でRDBMSを実装して遊んでいる一介のエンジニアです。
といっても、アカデミックなレベルでの造詣が特段深いわけではなく、CMUのIntro to Database Systemsなどを参考に見よう見まねで楽しんでいる、といったレベル感です。

今年もアドベントカレンダーの季節がやってきたタイミングで、「LLMの力を一定借りれば、一人アドカレという酔狂な取り組みも完走できるのでは？」と思いたち、始めてみることにしました。
（カレンダーの半分くらいまでは既に実装できており今年は行けそうな気がしています。）

本アドベントカレンダーでは、Rustを使ってRDBMSをゼロから構築していきます。
単に動くコードを書くだけでなく、「なぜRDBMSはそのように作られているのか」という本質の部分を、実装を通じ体感できるところを目指していきます。
興味を持っていただけたら、CMUの講義や私よりも詳しい先人の記事なども追ってみることをお勧めします。

全コードはGitHubに日付ごとに区切って置いています。
なお、全ての記事とコードは私の監修/レビューを通していますが、時間の都合上、LLMによって生成された部分も多分に含まれていますのでご了承ください。

今日のゴール

RDBMSの最も基本的な単位である行、すなわちTupleと、そのバイナリ表現を実装します。

テーブルの1行をバイト列に変換してファイルに書き込み、読み出すだけです。
インデックスも更新も削除もトランザクションもない、ただの追記型ストレージから始めていきます。

なぜバイナリなのか？

念のため確認しておくと、JSONやCSVではなくバイナリを採用するのは以下の理由からです。

1. 容量: バイナリはコンパクト。例えば64bit整数の9223372036854775807はテキストだと19バイト必要だが、バイナリなら常に8バイトで済む。また、CSVやJSONでは,や{や"などの区切り文字も冗長になる
2. ランダムアクセス: バイナリなら特定の場所に直接ジャンプしやすい。テキスト形式では都度パースが必要で、UTF-8のような可変長エンコーディングではN文字目へのジャンプもできない

Tupleのバイナリ表現

今回は簡略化のためにテーブルは1つに固定し、スキーマもid（INT）とname（VARCHAR）の2カラムで固定とします。

users(id INT, name VARCHAR)

これをバイト列にするとき、素朴に考えると：

+--------+------------+-----------+
| ID(4B) | NameLen(4B)| Name(可変) |
+--------+------------+-----------+

INTは4バイト固定。VARCHARは長さを先に書いて、その後に実データ。このようにすれば、前から順に読み取っていくことができます。

Null Bitmap

NULLをどう表現するか。

NULLを単に「0バイト」で表現してしまうと、次のバイト列がそのカラムの値なのか次のカラムなのか区別がつかなくなります。
かと言ってフラグバイトを各カラムに付けると、NOT NULLのカラムでも1バイト無駄になります。

そこでNull Bitmapを使います。
Tupleの先頭に、各カラムがNULLかどうかを示すビットマップを置きます。

+-------------+--------+------------+-----------+
| Bitmap(1B)  | ID(4B) | NameLen(4B)| Name(可変) |
+-------------+--------+------------+-----------+

ビットが立っていれば値あり、立っていなければNULL。
NULLのカラムはデータ部分を書き込まないので、容量も節約できます。

例えば2カラムで(NULL, "Alice")の場合、Bitmapは以下のようになります：

Bitmap (1 byte)
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |  ← bit0=0: id is NULL
+---+---+---+---+---+---+---+---+     bit1=1: name has value
  7   6   5   4   3   2   1   0

8カラムまでなら1バイト、16カラムまでなら2バイトと効率的です。

Serialize / Deserialize

実装の核となる部分を見ていきます。
（実際のコードではserialize_value/deserialize_valueなど関数を分割していますが、ここでは説明のため一つの関数にまとめています。）

Serialize

fn serialize_tuple(values: &[Value], schema: &Schema) -> Vec<u8> {
    let mut buf = Vec::new();

    // Null Bitmap: 値があればビットを立てる
    let bitmap_size = schema.columns.len().div_ceil(8);
    let mut bitmap = vec![0u8; bitmap_size];
    for (i, value) in values.iter().enumerate() {
        if !matches!(value, Value::Null) {
            bitmap[i / 8] |= 1 << (i % 8);
        }
    }
    buf.extend(&bitmap);

    for value in values {
        match value {
            Value::Null => {} // NULLは何も書き込まない
            Value::Int(v) => buf.extend(v.to_ne_bytes()),
            Value::Varchar(s) => {
                buf.extend((s.len() as u32).to_ne_bytes()); // 長さを先に書く
                buf.extend(s.as_bytes());
            }
        }
    }
    buf
}

Deserialize

fn deserialize_tuple(data: &[u8], schema: &Schema) -> Result<(Vec<Value>, usize)> {
    let bitmap_size = schema.columns.len().div_ceil(8);
    let bitmap = &data[0..bitmap_size];
    let mut offset = bitmap_size;
    let mut values = Vec::new();

    for (i, column) in schema.columns.iter().enumerate() {
        // ビットが立っていなければNULL
        let is_null = bitmap[i / 8] & (1 << (i % 8)) == 0;
        if is_null {
            values.push(Value::Null);
            continue;
        }
        match column.data_type {
            DataType::Int => {
                let v = i32::from_ne_bytes(data[offset..offset + 4].try_into()?);
                values.push(Value::Int(v));
                offset += 4;
            }
            DataType::Varchar => {
                // 先頭4バイトが長さ
                let len = u32::from_ne_bytes(data[offset..offset + 4].try_into()?) as usize;
                offset += 4;
                let s = String::from_utf8(data[offset..offset + len].to_vec())?;
                values.push(Value::Varchar(s));
                offset += len;
            }
        }
    }
    Ok((values, offset))
}

永続化

ファイルへの書き込みで注意すべき点が一つあります。

file.write_all(&data)?; // Serializeしたデータを書き込む
file.flush()?;  // これだけでは不十分

flush()はバッファをカーネル空間に渡すだけで、ディスクへの書き込みを保証しません。
電源が落ちたら消える可能性があります。

file.write_all(&data)?;
file.sync_all()?;  // fsync相当、ディスクまで書き込む

sync_all()（POSIXのfsync）を呼ぶことで、不揮発性ストレージへの書き込みが保証されます。
パフォーマンスは落ちますが、Durabilityのためには必要です。

後の章でWALを実装する際に、この辺りはもう少し掘り下げます。

動作確認

実際にサンプルデータを書き込んだ後に読み込んでみます。

insert(&[Value::Int(1), Value::Varchar("Alice".to_string())], &schema)?;
insert(&[Value::Int(2), Value::Null], &schema)?;
insert(&[Value::Null, Value::Varchar("Charlie".to_string())], &schema)?;

let tuples = scan(&schema)?;
for values in tuples {
    println!("{:?}", values);
}

実行結果（stdout）:

Scanned 3 tuples:
  [Int(1), Varchar("Alice")]
  [Int(2), Null]
  [Null, Varchar("Charlie")]

NULLを含むTupleも正しく読み書きできています。

今日の実装の限界

正直、この実装は極めて原始的です。

• 全件スキャン: 可変長データがあるのでN番目のTupleに直接ジャンプできず、特定のIDを見つけるにはファイル全体をスキャンする必要がある
• 追記のみ: 更新・削除ができない。一度書いたデータは変えられない

これらは次回以降で解決していきます。

次回予告

明日はPageを実装します。

データを固定サイズのブロック（ページ）に整理することで、Tupleの管理が効率的に行えるようになり、後のBuffer Poolなどへの布石となります。