B-Tree + WAL

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

db 編の最終回。前章の B-Treeページストアには穴があった。1回の挿入で split が起きると複数ページが書き換わるので、その途中でクラッシュすると木が壊れる。この穴を、WAL 編で送金を守ったのと同じ手で塞ぐ。挿入を丸ごと1トランザクションにして、先にログ、後でページ。これで「永続化・インデックス付き・キャッシュ効き・クラッシュセーフ」なストレージが完成する。

この章で塞ぐ穴

B-Treeページストアは木を永続化できたが、 WAL で送金に見た問題をそのまま抱えていた。1回の Insert が split で複数ページを書き換えるのに、それが原子的でない。

Insert(10) で split が起きると:
  ページ3(親) を書き換え
  ページ5(左) を書き換え     ← この途中でクラッシュしたら?
  ページ8(右) を書き換え

親だけ新しくて左右が古い、という半分だけ適用された木が残ると、 木の不変条件が壊れて検索が狂う。WAL の送金とまったく同じ構図で、 違うのは「2つの口座」が「splitで変わる複数ページ」になっただけ。

前提章

B-Treeページストア(ページ上の B-Tree)と WAL(先にログ・後でページ、commit+fsync、冪等な redo)の上に立つ。

解法: 挿入を1トランザクションにする

やることは WAL 編と同じ4ステップ。違いは、変更が「2スロット」ではなく 「split で書き換わる全ページ」になること。

1変更をためるsplit の全ページ

2WAL に書く全ページ + commit

3実ページに適用bufferpool へ

4checkpointWAL を空に

txn

積む

wal.log

fsync

空に

data.db

書換

Insert の4ステップ。どのファイルに触るかに注目 — data.db(3)より先に必ず wal.log(2)へ書く。2 の fsync より前に死ねば無かったこと、後なら必ず完遂

中心になるのは txn(トランザクション) という一時置き場だ。Insert 中の全 writeNode は 実ページに書かず、まず txn にため込む:

// Tree は WAL で守られた永続 B-Tree。
// txn は「今の Insert でまだ確定していないページ変更」の一時置き場。
type Tree struct {
	pool   *bufferpool.Pool
	wal    *os.File
	t      int
	rootID uint64
	nextID uint64
	txn    map[uint64][]byte // pageID -> 新しいページ内容(未確定)

	reads int // readNode を通った回数(問い合わせの代償を数えるため)
}

// Open はデータファイルと WAL を開き、リカバリしてから返す。
func Open(dir string, degree int) (*Tree, error) {
	if degree < 2 {
		return nil, errors.New("btreewal: degree must be >= 2")
	}
	maxKeys := 2*degree - 1
	if 3+maxKeys*8*2+(maxKeys+1)*8 > bufferpool.PageSize {
		return nil, fmt.Errorf("btreewal: degree %d too large for page size %d", degree, bufferpool.PageSize)
	}
	pool, err := bufferpool.New(filepath.Join(dir, "data.db"), 128)
	if err != nil {
		return nil, fmt.Errorf("btreewal: open data: %w", err)
	}
	wal, err := os.OpenFile(filepath.Join(dir, "wal.log"), os.O_RDWR|os.O_CREATE, 0o644)
	if err != nil {
		pool.Close()
		return nil, fmt.Errorf("btreewal: open wal: %w", err)
	}
	tr := &Tree{pool: pool, wal: wal, t: degree, txn: map[uint64][]byte{}}

	if err := tr.recover(); err != nil {
		tr.closeFilesOnly()
		return nil, err
	}

	meta, err := pool.Read(metaPage)
	if err != nil {
		tr.closeFilesOnly()
		return nil, err
	}
	tr.rootID = binary.BigEndian.Uint64(meta[0:8])
	tr.nextID = binary.BigEndian.Uint64(meta[8:16])
	if tr.nextID == 0 {
		tr.rootID = 1
		tr.nextID = 2
		tr.writeNode(tr.rootID, &node{leaf: true})
		tr.stageMeta()
		if err := tr.commit(); err != nil {
			tr.closeFilesOnly()
			return nil, err
		}
	}
	return tr, nil
}

// Close は木を閉じる。
func (tr *Tree) Close() error {
	return tr.closeFilesOnly()
}

// closeFilesOnly はファイルを閉じるだけ(checkpoint やメタ書き込みをしない)。
// テストでは「ページ適用の前にプロセスが死ぬ」クラッシュの再現に使う。
func (tr *Tree) closeFilesOnly() error {
	err1 := tr.pool.Close()
	err2 := tr.wal.Close()
	if err1 != nil {
		return err1
	}
	return err2
}

func (tr *Tree) stageMeta() {
	buf := make([]byte, bufferpool.PageSize)
	binary.BigEndian.PutUint64(buf[0:8], tr.rootID)
	binary.BigEndian.PutUint64(buf[8:16], tr.nextID)
	tr.txn[metaPage] = buf
}

func (tr *Tree) allocate() uint64 {
	id := tr.nextID
	tr.nextID++
	return id
}

// readNode は txn にあればそれを、なければ実ページを読む。
// prepareInsert 中に自分が書いた(まだ未確定の)ノードを読み返すために txn を優先する。
func (tr *Tree) readNode(id uint64) (*node, error) {
	tr.reads++
	if buf, ok := tr.txn[id]; ok {
		return deserialize(buf), nil
	}
	buf, err := tr.pool.Read(int(id))
	if err != nil {
		return nil, err
	}
	return deserialize(buf), nil
}

// writeNode は変更を txn にため込むだけ。実ページにはまだ書かない。
func (tr *Tree) writeNode(id uint64, n *node) {
	tr.txn[id] = serialize(n)
}

コードの読みどころ: readNode が txn を先に見る

readNode が tr.txn[id] を先に調べているのが要点。split の途中で親を 書き換えて(txn に積んで)、直後にその親を読み直すとき、実ページはまだ古い。 txn を優先することで、「まだ確定していないが、この Insert の中では見えている」 という一貫した世界を作る。これがないと split の最中に古いページを読んで壊れる。

挿入アルゴリズム自体はB-Treeページストアと一字一句同じ。 writeNode の中身が「実ページに書く」から「txn に積む」に変わっただけ:

// Insert は key=value を1トランザクションとして挿入する。
// prepareInsert で全変更をため、commit で WAL 経由に確定する。
func (tr *Tree) Insert(key, value uint64) error {
	tr.prepareInsert(key, value)
	return tr.commit()
}

// prepareInsert は B-Tree 挿入を実行するが、変更は txn に積むだけで確定しない。
// アルゴリズムは btreestore と同一(proactive split)。
func (tr *Tree) prepareInsert(key, value uint64) {
	root, _ := tr.readNode(tr.rootID)
	if len(root.keys) == 2*tr.t-1 {
		newRootID := tr.allocate()
		tr.writeNode(newRootID, &node{leaf: false, children: []uint64{tr.rootID}})
		tr.rootID = newRootID
		tr.splitChild(newRootID, 0)
	}
	tr.insertNonFull(tr.rootID, key, value)
	tr.stageMeta()
}

func (tr *Tree) insertNonFull(id, key, value uint64) {
	n, _ := tr.readNode(id)
	pos := sort.Search(len(n.keys), func(i int) bool { return n.keys[i] >= key })
	if pos < len(n.keys) && n.keys[pos] == key {
		n.vals[pos] = value
		tr.writeNode(id, n)
		return
	}
	if n.leaf {
		n.keys = insertUint64(n.keys, pos, key)
		n.vals = insertUint64(n.vals, pos, value)
		tr.writeNode(id, n)
		return
	}
	child, _ := tr.readNode(n.children[pos])
	if len(child.keys) == 2*tr.t-1 {
		tr.splitChild(id, pos)
		n, _ = tr.readNode(id)
		if key > n.keys[pos] {
			pos++
		} else if key == n.keys[pos] {
			n.vals[pos] = value
			tr.writeNode(id, n)
			return
		}
	}
	tr.insertNonFull(n.children[pos], key, value)
}

func (tr *Tree) splitChild(parentID uint64, i int) {
	parent, _ := tr.readNode(parentID)
	childID := parent.children[i]
	child, _ := tr.readNode(childID)
	t := tr.t

	rightID := tr.allocate()
	right := &node{leaf: child.leaf}
	right.keys = append(right.keys, child.keys[t:]...)
	right.vals = append(right.vals, child.vals[t:]...)
	if !child.leaf {
		right.children = append(right.children, child.children[t:]...)
		child.children = child.children[:t]
	}
	midKey, midVal := child.keys[t-1], child.vals[t-1]
	child.keys = child.keys[:t-1]
	child.vals = child.vals[:t-1]

	parent.keys = insertUint64(parent.keys, i, midKey)
	parent.vals = insertUint64(parent.vals, i, midVal)
	parent.children = insertUint64(parent.children, i+1, rightID)

	tr.writeNode(childID, child)
	tr.writeNode(rightID, right)
	tr.writeNode(parentID, parent)
}

func insertUint64(s []uint64, i int, x uint64) []uint64 {
	s = append(s, 0)
	copy(s[i+1:], s[i:])
	s[i] = x
	return s
}

// commit は txn を「WAL に書く → 実ページに適用 → WAL を空にする」で確定する。
func (tr *Tree) commit() error {
	if len(tr.txn) == 0 {
		return nil
	}
	if err := tr.logToWAL(); err != nil {
		return err
	}
	if err := tr.applyTxn(); err != nil {
		return err
	}
	return tr.checkpoint()
}

commit: 先にログ、後でページ

prepareInsert で txn に全変更がたまったら、commit がそれを確定する。 WAL に全ページを書いて fsync し、それから実ページに適用する:

// WAL レコード(固定長): [op 1B][pageID 8B][data PageSize]
// op=1: page(この内容にする)、op=2: commit(このバッチを確定。pageID/data は未使用)
const opPage = 1
const opCommit = 2

var recordSize = 9 + bufferpool.PageSize

// logToWAL は txn の全ページを WAL に書き、commit レコード + fsync で確定させる。
// この fsync が完了した瞬間が「この Insert はやる」と決まる境界線。
func (tr *Tree) logToWAL() error {
	for id, data := range tr.txn {
		rec := make([]byte, recordSize)
		rec[0] = opPage
		binary.BigEndian.PutUint64(rec[1:9], id)
		copy(rec[9:], data)
		if _, err := tr.wal.Write(rec); err != nil {
			return fmt.Errorf("btreewal: wal write: %w", err)
		}
	}
	commit := make([]byte, recordSize)
	commit[0] = opCommit
	if _, err := tr.wal.Write(commit); err != nil {
		return fmt.Errorf("btreewal: wal commit: %w", err)
	}
	return tr.wal.Sync()
}

// applyTxn は txn の全ページを実ページ(bufferpool)に書く。
func (tr *Tree) applyTxn() error {
	for id, data := range tr.txn {
		if err := tr.pool.Write(int(id), data); err != nil {
			return fmt.Errorf("btreewal: apply page %d: %w", id, err)
		}
	}
	return nil
}

// checkpoint は適用済みの WAL を空にし、txn をクリアする。
func (tr *Tree) checkpoint() error {
	tr.txn = map[uint64][]byte{}
	if err := tr.wal.Truncate(0); err != nil {
		return fmt.Errorf("btreewal: checkpoint: %w", err)
	}
	_, err := tr.wal.Seek(0, 0)
	return err
}

// recover は起動時に WAL を読み、commit 済みバッチのページを実ページに redo する。
// commit の無い書きかけバッチは捨てる。redo は full-page write なので冪等。
func (tr *Tree) recover() error {
	raw, err := os.ReadFile(tr.wal.Name())
	if err != nil {
		return fmt.Errorf("btreewal: read wal: %w", err)
	}

	pending := map[uint64][]byte{}
	for off := 0; off+recordSize <= len(raw); off += recordSize {
		rec := raw[off : off+recordSize]
		switch rec[0] {
		case opPage:
			id := binary.BigEndian.Uint64(rec[1:9])
			data := append([]byte(nil), rec[9:]...)
			pending[id] = data
		case opCommit:
			for id, data := range pending {
				if err := tr.pool.Write(int(id), data); err != nil {
					return err
				}
			}
			pending = map[uint64][]byte{}
		}
	}
	// commit されなかった書きかけは捨てる。WAL を空に戻す。
	if err := tr.wal.Truncate(0); err != nil {
		return err
	}
	_, err = tr.wal.Seek(0, 0)
	return err
}

各レコードはページ全体(full-page write)。差分ではなくページまるごとを記録するので、 recover の redo は「そのページをこの内容にする」を繰り返すだけ。 何度適用しても結果が同じ(冪等)だから、適用の途中で死んでも全部やり直せば必ず直る。 WAL 編で「+100 ではなく 1100 にする」と書いたのと同じ発想を、ページに広げたもの。

試す: クラッシュ地点を変えて挙動を見る

10 を挿入すると split で3ページが書き換わる、という筋書き。 クラッシュ地点を選んで、txn / wal.log / data.db の3つがどう動くか、 そしてリカバリで木が整合に戻るかを確かめてほしい。

デモInsert の原子性木は整合

クラッシュ地点

なしcommit 前commit 直後適用途中

txn (未確定の変更)

空

wal.log (先行書き込み)

空

data.db (実ページ)

ページ3 (親) 旧ページ5 (左) 旧ページ8 (右・新規) 旧

• commit 前: WAL に何もないので、リカバリはバッチを捨てる。木は挿入前のまま(整合)
• commit 直後 / 適用途中: WAL に commit 済み。リカバリが3ページを redo して完遂。 「適用途中」で一度は不整合になっても、redo が全ページを揃え直す

どの地点で死んでも、木は「完全に挿入された」か「まったく挿入されていない」の どちらかにしかならない。半分だけが存在することはない。 これがWALの原子性を、実データ構造の上で実現したということ。

db 編、完成

ここまでで作った部品が全部つながった。

• 二分探索木 → B-Tree: 検索の速い木
• ディスクとページ → B-Treeページストア: 木をディスクへ
• LRU → バッファプール: ページのキャッシュ
• ログ構造KV → WAL → この章: クラッシュ耐性

組み上がったのは「永続化された、インデックス付きの、キャッシュの効く、 クラッシュしても壊れないキーバリューストア」。実データベースの心臓部そのもの。 残る大物は「このストレージに SQL でアクセスする」層で、それがミニSQL編。

設計の観点

• 木の更新は複数ページに散る: 分割が起きると子も親も、ときには根まで書き換わる。1ページずつは正しくても、まとまりとしては中途半端になりうる。だから原子性は木の外で与える
• ページ丸ごとで冪等を買う: 差分ではなくページの結果をログに置けば、何度適用しても同じになる。復旧が「commit 済みを全部やり直す」だけで済む
• 代償はログの太さ: 冪等さをページ丸ごとで買っているので、ログの量が増える。実物が差分や圧縮へ向かうのは、この代償を薄めるため
• 確定線は木の形に依存しない: 木がどんな形になっていても、確定したかどうかを決めるのはログの commit レコード1点だけになる
• fsync の回数が commit の速さ: 更新が何ページに散っても、commit で待つのはログ1本への追記だけ。散らばる書き込みを待たなくてよいことが、この構成の速さそのものになる
• 完成の判定を持つ: 「クラッシュしても壊れないインデックス付きストレージ」という目標に対して、どのクラッシュ地点でも整合が戻ることを測れる形にしておく

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

論点	この章(ページ単位 WAL)	差分ログ
ログの中身	変更後のページ全体	変更した部分だけ
冪等さ	何度適用しても同じ	適用済みかの判定が要る
ログの量	太い	細い
torn page	ページ全体があるので直せる	別の備えが要る
実例	SQLite の WAL モード	InnoDB の redo log

得るものは、複数ページにまたがる木の更新に原子性が付くこと、そして commit で待つのが ログへの追記1回で済むことになる。払うのは、全変更が2回書かれること(write amplification)と、 ページ丸ごとを書くログの太さだ。

裏どり:

• doublewrite buffer: InnoDB は torn page の対策を WAL でなく別領域への二度書きで行う。ページを一度専用領域へ書き、そこから本来の位置へ書く。PostgreSQL の full-page write と目的は同じで、置き場所が違うという対比になる
• PostgreSQL は両方持つ: 通常は差分に近いレコードを書きつつ、checkpoint 後にそのページを最初に触るときだけページ全体を書く(full_page_writes)。この章の作りは、その「全体を書く」側だけを常に行う形になる
• checkpoint の頻度が綱引き: 頻繁だと定常の書き込みが増え、まれだと復旧が長い。PostgreSQL の checkpoint_timeout と max_wal_size が、その調整つまみになっている
• redo だけで足りる条件: commit 前のページを絶対に書き出さないと決めれば undo は要らない。実物がそう決めないのは、メモリに収まらない量の変更を抱えられなくなるからで、WAL で触れた ARIES はその制約を外した設計になる
• SQLite の WAL は読みを止めない: ページを本体でなく WAL 側に積むので、読み手は古い本体を読み続けられる。ロールバックジャーナル方式では本体を書き換えるため、読み手が待たされていた

簡略化したこと

• full-page write のみ: 実物は before/after 差分や圧縮でログ量を減らす
• checkpoint 毎回: 実物は WAL を溜めて定期実行し、fsync 回数を減らす
• 同時実行なし: 1トランザクションずつ。分離レベルは扱わない
• 削除・フリーリストなし: B-Treeページストアに揃えた

参考資料

• SQLite: WAL Mode — ページ単位 WAL の実物
• PostgreSQL: WAL Configuration — full-page write の設定
• ARIES(1992) — undo/redo リカバリの古典。この章は redo のみの簡略版