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件目は消え、その後も普通に書き続けられる。

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

デモ追記ログとインデックス0 レコード

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

まだ空です

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

空(キーなし)

設計の観点 ​

  • 壊れる場所を1か所に閉じ込める: 追記しかしないので、クラッシュで壊れうるのは末尾だけになる。「どこが壊れているか」を探さなくてよいことが、復旧を単純にしている
  • 書き換えないことで、順序を手に入れる: その場を書き換えないと決めると、ディスク上の並びが「起きた順」そのものになる。復旧も複製も、この並びを頭からたどるだけで済む
  • 新しさは位置で決まる: 同じキーが何度出てきても、後ろにあるほうが新しい。削除すら「消した」というレコードの追記で表せる
  • 速い場所と遅い場所を分ける: 位置の索引はメモリ、中身はディスク。読みがディスクを触るのは1回だけになる
  • 伸び続けることを前提に置く: 追記だけの設計は、掃除の仕組みとセットでしか完成しない。掃除をいつやるかが運用の主題になる
  • 索引の形が、できることを決める: ハッシュにすると1件引きは速いが範囲が引けない。何を引きたいかが先にあって、索引の形が決まる

メリット・デメリットと実例 ​

論点追記だけの設計その場で書き換える設計
書き込み常に連続。ヘッドが飛ばない散らばる。書く場所を探す必要がある
クラッシュ壊れるのは末尾だけどのページが中途半端かを判定する仕組みが要る(WAL)
読み索引を引いて1回シーク木を降りる
容量古い版が残り続ける。掃除が要る上書きされるので増えない
範囲検索ハッシュ索引では引けないB-Tree なら並んでいるので得意

実例:

  • Bitcask: Riak のストレージエンジンで、この章の設計の出典。全キーの位置をメモリに置き、読みは必ずディスク1回
  • Redis の AOF: コマンドを追記し、再起動時に再生する。BGREWRITEAOF が掃除にあたる
  • Kafka: 追記だけのログ自体をデータの正本として配る。この章の「ログが正本」を、1台の中でなくシステム全体でやっている
  • WAL: PostgreSQL も SQLite も、ページを上書きする前に変更を追記ログに書く。追記の性質を「安全網」として使う形で、次段の主題になる

裏どり:

  • 掃除の呼び方: 生きているレコードだけを新しいファイルに書き写す作業を、Bitcask ではマージ、LSM ツリーではコンパクションと呼ぶ。追記だけの設計はどれも、どこかで同じ作業を持っている
  • 書き込み増幅と空間増幅: 掃除を頻繁にやれば容量は締まるが、同じデータを何度も書き直す(書き込み増幅)。やらなければ古い版が場所を食う(空間増幅)。RocksDB のチューニングはほぼこの2つの綱引きになる
  • メモリに載る前提の限界: 全キーの索引をメモリに置く設計は、キーが億を超えると成り立たない。LSM ツリーが索引を階層化してディスクへ逃がしたのは、この制約への答えになる
  • 末尾の切り捨てで足りない場合: この章は「読めなくなったら切る」で済ませているが、途中のビットが化けると読めてしまう。実物がレコードごとに CRC を持つのはこのため
  • fsync との関係: この章は OS のバッファに書けた時点で成功にしている。停電をまたいで残る保証はそこにはなく、その線引きは WAL の主題になる

簡略化したこと ​

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

参考資料 ​