簡易データベースを自作する

何を作るか

作るのは、put(key, value) と get(key) と delete(key) だけを持つ、単一ファイルの永続的なkey-valueストアです。設計の核はただ一つ、「書き込みは常にファイルの末尾へ追記するだけ」という制約です。既存レコードを上書きせず、更新も削除も新しいレコードを足して表現します。読み取りを速くするために、keyごとに「その値がファイルのどこにあるか（バイトオフセット）」をインメモリのハッシュマップで持ちます。これは実在のストレージエンジン Bitcask（Riak のデフォルトエンジン）とほぼ同じ構造です。

これを作ると、データベースの土台にある問いが具体的に分かります。なぜ追記専用は速いのか（ランダム書き込みをシーケンシャル書き込みに変える）、なぜ fsync を呼ばないとクラッシュでデータが消えるのか、肥大化するログをどう掃除するのか（コンパクション）、そしてこの最小構成が原理的に何を諦めていて、その限界をB木やLSMツリーがどう引き継ぐのか。数百行で動く実装を通り道にして、本物のDBが足している要素の「理由」まで辿ります。

最小実装の全体像

横にスクロール

パーツは3つだけです。(1)レコードを直列化してファイル末尾へ追記する書き込み器、(2)key → オフセット を保持するインメモリのハッシュ索引（keydir と呼びます）、(3)起動時にログ全体を走査して索引を復元する回復処理。get は索引でオフセットを引き、ファイルをそこへシークして1レコードだけ読みます。ディスクI/Oが原理的に1回で済むのが、この方式の速さの源です。

レコードのバイト列表現を先に決めます。可変長のkeyとvalueを扱うため、それぞれの長さを固定長ヘッダに書いておき、読み手が境界を復元できるようにします。

索引が保持する値も決めておきます。get に必要なのは「どのオフセットから何バイト読むか」なので、keydir の各エントリは (オフセット, 全レコード長) を持ちます。全レコード長を持てば、1回のシークと1回の読み取りでヘッダごとレコードを取得できます。

段階を追って作る

まず書き込み経路です。put は、レコードをエンコードし、現在のファイル末尾のオフセットを記録してから追記し、そのオフセットで keydir を更新します。ポイントは、追記の「前に」書き込み先オフセットを掴むこと。ここが後の get が指す位置になります。

def put(self, key, value):
    record, size = encode(key, value)   # crc+長さ+key+value
    offset = self.file.tell()           # 追記先＝現在の末尾
    self.file.write(record)
    self.file.flush()                   # ユーザー空間バッファをOSへ
    os.fsync(self.file.fileno())        # OSバッファをディスクへ（後述）
    self.keydir[key] = (offset, size)   # 索引を最新の位置へ

読み取りは索引を1回引くだけです。keydir にkeyが無ければ存在しない（または削除済み）とみなします。

def get(self, key):
    if key not in self.keydir:
        return None
    offset, size = self.keydir[key]
    self.file.seek(offset)              # 1回シーク
    record = self.file.read(size)       # 1回読み取り
    return decode_value(record)         # crc検証して値を取り出す

更新は新しいレコードの追記そのものです。同じkeyへ put すると、より後ろのオフセットに新しい版が書かれ、keydir がそのオフセットを指すよう上書きされます。古い版はファイルに残ったままですが、索引が指さないので二度と読まれません。削除も追記で表現します。 「墓標（tombstone）」という特別なレコード（例: value_size を -1 に）を追記し、keydir からそのkeyを外します。物理的に消さないのは、追記専用の不変条件を崩さないためです。

def delete(self, key):
    record, size = encode(key, TOMBSTONE) # 削除マーカーを追記
    self.file.write(record)
    self.file.flush(); os.fsync(self.file.fileno())
    self.keydir.pop(key, None)             # 索引からのみ外す

次がクラッシュ回復です。keydir はメモリ上にしか無いので、再起動後は空です。ログを先頭から末尾まで順に走査し、レコードごとに keydir を更新し直します。同じkeyが複数回現れたら、後に読んだ（＝ファイル上でより後ろの）版が勝つ。tombstone に出会ったらそのkeyを keydir から外します。走査し終えれば、クラッシュ前の最新状態が復元されます。

def recover(self):
    offset = 0
    while offset < filesize:
        key, value, size = read_record_at(offset)
        if value is TOMBSTONE:
            self.keydir.pop(key, None)
        else:
            self.keydir[key] = (offset, size)  # 後勝ちで上書き
        offset += size

ここで fsync が要る理由がはっきりします。write はデータをOSのページキャッシュに置くだけで、実際のディスク書き込みは後回しにされます。この状態で電源断が起きると、アプリは書けたつもりでもディスクには届いておらず、回復時にそのレコードは存在しません。fsync はOSに「このファイルのバッファを今すぐ物理ディスクへ書き出せ」と強制し、戻ってきた時点で永続化を保証します。ただし fsync はディスクの物理I/Oを待つため遅く、1書き込みごとに呼ぶとスループットが大きく落ちます。

最後にコンパクションです。更新・削除のたびに古い版がログに残り続けるので、ファイルは実データ量を超えて無限に肥大化します。掃除役がコンパクションで、ログを読みながら「各keyの最新版だけ」を新しいファイルへ書き出し、古いファイルを丸ごと差し替えます。keydir は生きているkeyの最新オフセットしか指していないので、実装上は「keydir に載っている全keyの現在値を新ファイルへ順に put し直す」形になります。実運用のBitcaskはログを一定サイズで区切って複数セグメントにし、書き込み中のアクティブセグメント以外の古いセグメント群だけをバックグラウンドでコンパクションします。

発展と本物との違い

この最小DBは意図的に多くを諦めています。最大の制約は「全keyがメモリに載る前提」です。keydir は全keyぶんのエントリをRAMに持つため、keyの総数がメモリを超えると破綻します（valueはディスクなので、valueが大きい用途には向く一方、key数が莫大な用途には向かない）。また、点引き（1個のkeyを引く）は速いものの、x以上y以下のkeyを全部 といった範囲検索は、ハッシュ索引が順序を持たないため原理的にできません。ここから先が、本物のストレージエンジンが引き継ぐ領域です。

範囲検索が要るならB木です。データをkey順に並べた固定長ページの木で保持し、ページを更新する（＝上書きする）方式のため、ランダムI/Oと引き換えに順序走査を可能にします。上書き途中のクラッシュ対策として、多くのDBは更新前に先行書き込みログ（WAL）へ変更を追記してから本体を更新します。実は本記事の追記ログは、このWALと同じ「まずシーケンシャルに追記して耐久性を確保する」発想の縮図です。

書き込み偏重ならLSMツリーです。まずメモリ上のソート済み表に書き、一定量たまったらkey順のファイル（SSTable）としてディスクへ順次フラッシュし、背後で層を段階的にマージ（これもコンパクションの一種）します。本記事の「追記＋定期コンパクション」を、複数の整列した層に一般化したものと捉えると理解しやすいはずです。ログ構造化ストレージの詳しい機序はデータベースのトピックにまとまっています。

作ってみると、DBの階層が「速い書き込み・確実な永続化・肥大化の回収・効率的な索引」という独立した関心事の積み重ねだと体感できます。まず動く最小版を持ち、諦めた点を一つずつ埋めていくと、本物のストレージエンジンの設計が自分の言葉で説明できるようになります。土台となる永続化やI/Oの原理はOS、実装言語のバイト操作はプログラミングの各トピックも参照してください。