WAL
実装:
db/wal// 実行:go test ./db/wal/
「口座Aから引いてBに足す」のように複数箇所を書き換える処理を、途中でクラッシュしても中途半端にならないよう守る。コツは、ページを書き換える前に「これからやること」をログに書いておくこと。ログに commit を書き終えた瞬間が「やる」の確定線で、そこより前に死ねば無かったことに、後なら必ずやり切る。半分だけ実行、が起きない。
この章で作るもの
db 編の第2段、Write-Ahead Log。題材は送金 — 「口座Aから引いて口座Bに足す」という 2ページの書き換えを、クラッシュがいつ起きても中途半端にならないように行う。
この章の肝は3つ。
- 原則は1つ:「ページを書き換える前に、やることをログに書け」(write-ahead = 先行書き込み)
- commit レコード + fsync が「やる」と確定する境界線。リカバリは commit 済みなら redo(やり直し)、なければ捨てる。「半分だけ実行」が絶対に起きない
- redo は冪等(「+100する」ではなく「1100にする」と記録する)だから、 どこで死んでも「全部やり直す」で必ず正しい状態になる
問題設定: 2ページの書き換えは割り込まれる
送金は本質的に2つの書き込みでできている。素朴にページを直接書き換えると:
ログ構造KVでは「追記だけにする」ことでこの問題を避けたが、 B-Tree のようなその場で書き換えたい構造ではそうもいかない。 書き換えはしたい、でも途中で死んでも壊れたくない。その答えが WAL。
解法: 先にログ、後でページ
ログへの追記はディスクとページで見た通りシーケンシャル書き込みで速い。 つまり WAL は「速い書き込み(ログ追記)で保険をかけてから、遅くて危険な書き込み(ページ)をやる」 という構造になっている。
レコードの形はログ構造KVとほぼ同じ length は固定13バイト:
// WAL レコード: [op 1B][slot 4B][value 8B]
// op=1: set(変更内容)、op=2: commit(このバッチを確定する印。slot/value は未使用)
const recordSize = 13
const (
opSet = 1
opCommit = 2
)
func encodeRecord(op byte, s Set) []byte {
buf := make([]byte, recordSize)
buf[0] = op
binary.BigEndian.PutUint32(buf[1:5], uint32(s.Slot))
binary.BigEndian.PutUint64(buf[5:13], uint64(s.Value))
return buf
}送金の本体。「先にログ、後でページ」の順序がすべて:
// Transfer は from から to へ amount を送金する。
// 「先にログ、後でページ」の順序がこの関数のすべて。
func (db *DB) Transfer(from, to int, amount int64) error {
db.mu.Lock()
defer db.mu.Unlock()
if amount <= 0 {
return errors.New("wal: amount must be positive")
}
if from == to {
return errors.New("wal: from and to must differ")
}
a, err := db.readSlot(from)
if err != nil {
return err
}
b, err := db.readSlot(to)
if err != nil {
return err
}
if a < amount {
return fmt.Errorf("wal: insufficient balance in slot %d", from)
}
sets := []Set{
{Slot: int32(from), Value: a - amount},
{Slot: int32(to), Value: b + amount},
}
if err := db.logCommitted(sets); err != nil { // 1-2. ログに書いて commit
return err
}
if err := db.applySets(sets); err != nil { // 3. ページを書き換える
return err
}
return db.checkpoint() // 4. 完了したので WAL を空にする
}4つのステップの中身:
// logSets は変更内容を WAL に追記する(まだ「やる」とは決まっていない)。
func (db *DB) logSets(sets []Set) error {
for _, s := range sets {
if _, err := db.wal.Write(encodeRecord(opSet, s)); err != nil {
return fmt.Errorf("wal: append: %w", err)
}
}
return nil
}
// logCommitted は変更内容 + commit レコードを書き、fsync でディスクに届いたことを保証する。
// この fsync が完了した瞬間が「送金は実行される」と確定する境界線。
func (db *DB) logCommitted(sets []Set) error {
if err := db.logSets(sets); err != nil {
return err
}
if _, err := db.wal.Write(encodeRecord(opCommit, Set{})); err != nil {
return fmt.Errorf("wal: append commit: %w", err)
}
return db.wal.Sync()
}
// applySets は変更をデータファイルに適用する。
func (db *DB) applySets(sets []Set) error {
for _, s := range sets {
if err := db.writeSlot(s); err != nil {
return err
}
}
return nil
}
// checkpoint は適用済みの WAL を空にする。次のリカバリで再生するものが無くなる。
func (db *DB) checkpoint() error {
if err := db.wal.Truncate(0); err != nil {
return fmt.Errorf("wal: checkpoint: %w", err)
}
_, err := db.wal.Seek(0, 0)
return err
}コードの読みどころ: fsync の位置
logCommitted の最後の db.wal.Sync() がこの章で一番重い1行。 Write はOSのバッファに書くだけで、停電すればまだ消える。 Sync(fsync)が返ってきて初めて「ディスクに物理的に届いた」と言える。 だから commit の後、ページ書き換えの前という位置に fsync がある — ここが「送金をやる」と外部に約束できる最初の瞬間で、 データベースのトランザクションの「コミット完了」の実体はこの fsync。
リカバリ: commit があれば redo、なければ捨てる
// recover は起動時に WAL を読み、commit 済みバッチだけをデータファイルに再適用(redo)する。
// commit の無い書きかけバッチは捨てる。redo は冪等(Set は絶対値)なので、
// 前回どこまで適用済みだったかを知らなくても、全部やり直せば必ず正しい状態になる。
func (db *DB) recover() error {
raw, err := os.ReadFile(db.wal.Name())
if err != nil {
return fmt.Errorf("wal: read wal: %w", err)
}
var pending []Set
for off := 0; off+recordSize <= len(raw); off += recordSize {
rec := raw[off : off+recordSize]
s := Set{
Slot: int32(binary.BigEndian.Uint32(rec[1:5])),
Value: int64(binary.BigEndian.Uint64(rec[5:13])),
}
switch rec[0] {
case opSet:
pending = append(pending, s)
case opCommit:
if err := db.applySets(pending); err != nil { // redo
return err
}
pending = nil
}
}
// ループを抜けた時点で pending に残っているものは commit されていない書きかけ。
// 何もせず捨てる。
return db.checkpoint()
}コードの読みどころ: 冪等な redo
recover は「前回どこまで適用したか」を一切知らない。知らなくていい。 Set レコードが「A に +100」ではなく「A を 900 にする」という絶対値だから、 適用済みのレコードをもう一度適用しても結果が変わらない(冪等)。 「途中まで済んでいるかもしれない作業を、全部やり直しても壊れない」ようにしておくのが、 クラッシュリカバリを単純にする最大のコツ。
クラッシュの3地点とリカバリの動きを整理すると:
| クラッシュ地点 | WAL の状態 | リカバリの動き | 結果 |
|---|---|---|---|
| commit を書く前 | set のみ | commit が無いので捨てる | 送金は無かったことに |
| commit 直後(適用前) | set + commit | redo で両ページを書く | 送金は完遂される |
| ページ適用の途中 | set + commit | redo で両ページを書き直す(冪等) | 送金は完遂される |
3地点ともテストで固定してある。どの行き先も「完全にやる」か「完全にやらない」かで、 「半分だけ」だけが存在しない — これが原子性(atomicity)の実体。
試してみる: クラッシュ地点を選んで送金し、データファイルが不整合になる瞬間 (適用途中なら合計が 1900 になる)と、リカバリで整合が戻る様子を確認してほしい。
ログ構造KVとの関係
前章と合わせると、ログの使い方が2通りあることになる。
- ログ構造KV: ログ自体が正本。読みもログから
- WAL: 正本はページ(B-Tree 等)で、ログは書き換えを守る一時的な安全網。 適用が終われば checkpoint で捨てる
実務のデータベースはほぼ後者(+ 前者の発展形である LSM-Tree)。 B-Tree のページストアと WAL を組み合わせると、ようやく「クラッシュしても壊れない インデックス付きストレージ」になる — db 編の次の段はそこ。
メリット / デメリット
メリット
- 複数ページの書き換えに原子性を与えられる(トランザクションの土台)
- commit 時に必要な fsync はWAL 1本へのシーケンシャル追記だけ。 ページ本体の書き込みは後でまとめてよいので、速さと安全を両立できる
- レプリケーションにも流用できる(WAL をそのまま他のサーバーに送れば複製になる)
デメリット
- すべての変更が2回書かれる(ログ + ページ)。write amplification
- WAL は伸び続けるので checkpoint の運用が要る(頻度が高いと遅く、低いと復旧が長い)
- fsync は数ms かかる。commit のたびに払う税金になる(グループコミットで緩和する)
実例
- PostgreSQL の WAL(
pg_wal/)、MySQL InnoDB の redo log — 仕組みはこの章と同型 - SQLite の WAL モード(
PRAGMA journal_mode=WAL) - etcd / Raft のログ複製 — 「ログを確定してから状態機械に適用」は分散版の同じ発想
簡略化したこと
- redo のみで undo がない: ページ適用を commit 後に限っているため、 巻き戻しが必要な状態がそもそも生まれない設計にした。実物(ARIES 系)は性能のために commit 前のページ書き出しを許し、その分 undo ログも持つ
- 同時実行なし: トランザクション分離(ロック、MVCC)は db 編の後の段で
- CRC なし・torn page 対策なし: 実物はレコードにチェックサムを付け、 ページ書き込みが途中で切れる問題には full-page write などで対処する
- checkpoint を毎回実行: 実物は WAL を溜めて定期的に行う
参考資料
- PostgreSQL: WAL Introduction — 本物の設計思想。この章の内容がそのまま出てくる
- SQLite: Write-Ahead Logging — 単一ファイルDBでの WAL の作り方
- ARIES(1992) — undo/redo 両対応のリカバリの古典。名前だけでも知っておくと文献が読める