sharin

Appearance

ログ構造KV ​

実装: db/kvlog/ / 実行: go test ./db/kvlog/

ファイルには追記しかしない、という縛りだけで KV ストアを作る。値の上書きも削除も、全部「新しいレコードを末尾に足す」で表す。既存の場所を書き換えないので、クラッシュで壊れうるのは書きかけの末尾だけ。今どの値が最新かはメモリ側のインデックスが覚えていて、再起動したらログを頭から読み直して復元する。

この章で作るもの ​

db 編の第1段。ログ構造(log-structured) — 「ファイルには追記しかしない」という 縛りだけで、Put / Get / Delete とクラッシュ耐性を持つ KV ストア(Bitcask 型)を作る。

この章の肝は3つ。

  • 上書きも削除も「新しいレコードの追記」で表現する。既存バイトを一切触らないから、 クラッシュで壊れうるのは末尾の書きかけだけ
  • ディスクは全履歴を持ち、**メモリのインデックスが「各キーの最新の場所」**を知っている
  • 再起動 = ログを先頭から再生してインデックスを組み直すこと。 これが WAL とイベントソーシングに共通する核

前提章

ディスクとページの「追記(シーケンシャル書き込み)は書き込みの中で最速」 「壊れる単位・読み書きの単位はページ」を前提にする。

問題設定: 上書きは怖い ​

素朴な KV ストアは「キーごとの場所を決めて、値をその場で上書きする」形を考えたくなる。 しかし上書きの途中でクラッシュしたら? 古い値でも新しい値でもない、 中途半端なバイト列が残る。しかも壊れたのがどこか、後から見分ける方法がない。

追記オンリーにするとこの問題が消える。書き込みが既存のデータに触らないので、 クラッシュの被害は常に「末尾の書きかけ1件」に限定され、しかも場所が末尾と分かっている。 おまけに追記はシーケンシャル書き込みなので、ディスクにとって最速の書き方でもある。

レコードの形 ​

ログファイルは、この形のレコードがひたすら並んだだけのもの:

keyLen4B
valLen4B
tomb1B
key可変
value可変
1レコードのバイトレイアウト。長さを先頭に書く(length-prefix)ことで、どこからどこまでが1レコードかを自己記述する
go
// レコードの並び: [keyLen 4B][valLen 4B][tombstone 1B][key][value]
// tombstone(墓石) = 1 は「このキーは削除された」という印のレコード。
const headerSize = 9

func encodeRecord(key, value string, tombstone bool) []byte {
	buf := make([]byte, headerSize+len(key)+len(value))
	binary.BigEndian.PutUint32(buf[0:4], uint32(len(key)))
	binary.BigEndian.PutUint32(buf[4:8], uint32(len(value)))
	if tombstone {
		buf[8] = 1
	}
	copy(buf[headerSize:], key)
	copy(buf[headerSize+len(key):], value)
	return buf
}

// readRecord は off の位置のレコードを読む。ファイル末尾や書きかけのレコードなら
// io.EOF / io.ErrUnexpectedEOF を返す(replay がこれを「ここまで」の合図に使う)。
func readRecord(r io.ReaderAt, off int64) (key, value string, tombstone bool, size int64, err error) {
	var header [headerSize]byte
	if _, err = r.ReadAt(header[:], off); err != nil {
		return
	}
	keyLen := binary.BigEndian.Uint32(header[0:4])
	valLen := binary.BigEndian.Uint32(header[4:8])
	tombstone = header[8] == 1

	body := make([]byte, keyLen+valLen)
	if _, err = r.ReadAt(body, off+headerSize); err != nil {
		return
	}
	key = string(body[:keyLen])
	value = string(body[keyLen:])
	size = headerSize + int64(len(body))
	return
}

tombstone(墓石)は「このキーは削除された」という印。削除すら追記で表すのが この方式の徹底ぶりで、ファイルからは本当に何も消えない。

ログは歴史、インデックスは現在 ​

同じキーを上書きすると、古いレコードはログに残ったままになる。 「今の値はどれか」を知っているのはメモリ上のインデックスだけ:

a=1#0 古い
b=2#1 ← index[b]
a=3#2 ← index[a]
c=4#3 古い
c 墓石#4 削除の印
Put(a,1) → Put(b,2) → Put(a,3) → Put(c,4) → Delete(c) の後のログ。インデックスは a→#2、b→#1 だけを指し、薄いレコードは誰からも参照されない過去
go
// Put は「key の最新は value」というレコードを末尾に追記する。
// 古い値はログに残り続けるが、インデックスが新しいオフセットを指すので見えなくなる。
func (s *Store) Put(key, value string) error {
	if key == "" {
		return errors.New("kvlog: key must not be empty")
	}
	s.mu.Lock()
	defer s.mu.Unlock()

	rec := encodeRecord(key, value, false)
	if _, err := s.f.WriteAt(rec, s.end); err != nil {
		return fmt.Errorf("kvlog: append: %w", err)
	}
	s.index[key] = s.end
	s.end += int64(len(rec))
	return nil
}

// Get はインデックスでオフセットを引き、その1レコードだけを読む。
// ログ全体を走査することはない。
func (s *Store) Get(key string) (string, bool, error) {
	s.mu.Lock()
	defer s.mu.Unlock()

	off, ok := s.index[key]
	if !ok {
		return "", false, nil
	}
	_, value, _, _, err := readRecord(s.f, off)
	if err != nil {
		return "", false, fmt.Errorf("kvlog: read: %w", err)
	}
	return value, true, nil
}

// Delete は tombstone(削除の印)を追記し、インデックスから外す。
// ファイルからは何も消えない。「削除も追記」なのがこの方式の徹底ぶり。
func (s *Store) Delete(key string) error {
	if key == "" {
		return errors.New("kvlog: key must not be empty")
	}
	s.mu.Lock()
	defer s.mu.Unlock()

	rec := encodeRecord(key, "", true)
	if _, err := s.f.WriteAt(rec, s.end); err != nil {
		return fmt.Errorf("kvlog: append: %w", err)
	}
	delete(s.index, key)
	s.end += int64(len(rec))
	return nil
}

Get はインデックスでオフセットを引いてその1レコードだけを読む。 ログがどれだけ伸びても、読みは1回で済む(インデックスがメモリにある限り)。

再起動 = ログの再生 ​

インデックスはメモリ上にしかないので、プロセスが死ねば消える。 どう復元するか。ログを先頭からもう一度読めばいい。 Put と Delete を順に「再生」すれば、最後には死ぬ直前と同じインデックスができあがる。

go
// replay はログを先頭から読めるところまで読み、インデックスを組み立てる。
// 途中で切れたレコード(クラッシュの痕跡)が見つかったら、そこから後ろを切り捨てる。
// 「再起動 = ログの再生」であり、これが WAL とイベントソーシングに共通する核。
func (s *Store) replay() error {
	var off int64
	for {
		key, _, tombstone, size, err := readRecord(s.f, off)
		if err != nil {
			break // 末尾に到達、または書きかけレコード。ここまでが有効
		}
		if tombstone {
			delete(s.index, key)
		} else {
			s.index[key] = off
		}
		off += size
	}
	s.end = off
	// 書きかけの末尾を物理的にも捨てて、次の追記が壊れた上に乗らないようにする。
	return s.f.Truncate(off)
}

コードの読みどころ: 壊れた末尾の切り捨て ​

再生ループは、レコードが読めなくなったところで止まる。それは正常な末尾かもしれないし、 クラッシュで途中まで書かれたレコードかもしれない。どちらでも扱いは同じ、 「そこから後ろは無かったことにする」(Truncate)。

テストではこれをクラッシュの再現として固定してある: 2件書いてからファイル末尾を3バイト削って開き直すと、1件目は生きていて、 切れた2件目は消え、その後も普通に書き続けられる。

試してみる: 書き込みでログが右に伸び、インデックスが最新を指し替える様子と、 「クラッシュして再起動」で書きかけの末尾が切り捨てられて復元される様子を確認してほしい。

ログファイル(追記のみ。何も上書きされない)

まだ空です

インデックス(メモリ上。key がどのレコードにあるか)

空(キーなし)

メリット / デメリット ​

メリット

  • 書き込みが速い(常にシーケンシャル追記)
  • クラッシュ安全の理屈が単純(壊れるのは末尾だけ。復旧は再生 + 切り捨て)
  • 実装が小さい(この章の Go 実装は200行足らず)

デメリット

  • ログは伸び続ける。古いレコードを掃除するコンパクション(生きているレコードだけを 新ファイルに書き写す)が別途必要になる
  • 全キーのインデックスがメモリに載る前提。キーが億単位なら成り立たない
  • インデックスがハッシュなので範囲検索(a〜c のキー全部)に弱い。 範囲が欲しければ B-Tree 系のインデックスに戻ってくる

実例

  • Bitcask(Riak のストレージエンジン。この章の設計の出典)
  • Redis の AOF(Append Only File) — コマンドを追記し、再起動時に再生する
  • Kafka — 「追記だけのログ」自体をデータの正本として配るシステム
  • そして WAL(Write-Ahead Log)。PostgreSQL も SQLite も、B-Tree を上書きする前に 「これからやる変更」を追記ログに書く。次段の主題

簡略化したこと ​

  • チェックサムなし: 実物は各レコードに CRC を付け、「末尾が切れた」だけでなく 「途中のビットが化けた」も検出する
  • fsync の制御なし: 追記が OS のバッファに乗った時点で成功扱いにしている。 「いつディスクに確実に届いたと言えるか」は WAL 編の主題
  • コンパクションなし: ログは伸びる一方
  • 単一 mutex: 読み書きが全部直列。実物は読みを並行にする

参考資料 ​