バッファプール

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

ディスクのページとメモリの間に立つ、たった1つの窓口を作る。読み書きは全部ここを通し、よく使うページはメモリに留めておく。どれだけディスクを読まずに済むか(ヒット率)がデータベースの実速度を決めて、そのヒット率はアクセスの偏りで決まる。B-Tree の昇順挿入がなぜ速いのか、その答えがここで数字になって出る。

この章で作るもの

db 編の第3段。ディスクのページとメモリの間に立つ唯一の窓口、バッファプール(ページキャッシュ)を作る。追い出しには LRU の章で作ったものをそのまま使う。

順に見ていく。

読み書きはすべてこの窓口を通る: 出入口が1つなら、記録も監視もそこに集められる
書き込みは後回しにする: 印を付けるだけで返す。速さの源泉であり、危うさの源泉でもある
ヒット率がすべてを決める: そしてヒット率は、上の層がどの順で触るかで決まる

前提章

ディスクとページ(ページ・キャッシュ・局所性)と LRU(追い出しアルゴリズム)の上に立つ。

① すべての読み書きは窓口を通る

素朴なコードは「読みたいページを直接ファイルから読む」が、これだと同じページを何度読んでも毎回ディスクに行く。バッファプールを1枚挟んで、 アプリはページIDを言うだけ、実際にディスクに行くかはプールが決める形にする。

  アプリ ──「page 5 ちょうだい」──▶ バッファプール
                                      │
                          ┌───────────┴───────────┐
                     キャッシュにある?          無い(ミス)
                       (ヒット)                    │
                          │                    ディスクから読む
                          ▼                         │
                    そのまま返す  ◀────  キャッシュに入れて返す

バッファプールを通す読み。キャッシュにあれば(ヒット)ディスクに触らない。無ければ(ミス)読んで、キャッシュに入れてから返す

読みの実装。ヒット/ミスを数えているのは、後でヒット率を見るため。

// fetch はページをキャッシュ経由で手に入れる。
// キャッシュに無ければディスクから読み(miss)、キャッシュに入れる。
// そのとき誰かが追い出されたら、dirty なら先にディスクへ書き戻す — ここが肝。
func (p *Pool) fetch(id int) (*page, error) {
	if id < 0 {
		return nil, fmt.Errorf("bufferpool: page id %d out of range", id)
	}
	if pg, ok := p.cache.Get(id); ok {
		p.hits++
		return pg, nil
	}
	p.misses++

	// ディスクから読む。まだ書かれたことのないページはゼロで埋まっていることにする。
	buf := make([]byte, PageSize)
	if _, err := p.f.ReadAt(buf, int64(id)*PageSize); err != nil && err != io.EOF {
		return nil, fmt.Errorf("bufferpool: read page %d: %w", id, err)
	}

	pg := &page{data: buf}
	if victimID, victim, evicted := p.cache.Put(id, pg); evicted && victim.dirty {
		if err := p.writeBack(victimID, victim); err != nil {
			return nil, err
		}
	}
	return pg, nil
}

② 書き込みは後回しにする

書き込みも同じ窓口を通るが、ディスクには書かない。キャッシュ上のページを書き換えて dirty の印を付けるだけ。実際にディスクへ書くのは、そのページが追い出されるときか、明示的な FlushAll のとき。

// Write はページを書き換える。書き先はディスクではなく**キャッシュ上のページ**で、
// dirty の印を付けるだけ。ディスクへの書き戻しは追い出されるときか FlushAll まで遅延する。
// 「書き込みをまとめて遅らせる」ことが速さの源泉で、その代償がクラッシュ時の消失
// (これを守るのが WAL 編)。
func (p *Pool) Write(id int, data []byte) error {
	if len(data) != PageSize {
		return fmt.Errorf("bufferpool: data must be %d bytes, got %d", PageSize, len(data))
	}
	p.mu.Lock()
	defer p.mu.Unlock()

	pg, err := p.fetch(id)
	if err != nil {
		return err
	}
	copy(pg.data, data)
	pg.dirty = true
	return nil
}

書き込みをまとめて遅らせられるから速い。ただし裏を返せば「dirty なままメモリにある変更は、クラッシュで消える」。これを守るのが前章の WAL で、両者は組で使う。

追い出しと書き戻し

キャッシュが満杯のとき新しいページを載せるには、誰かを追い出す。 LRU が犠牲者を選ぶが、その犠牲者が dirty なら、捨てる前にディスクへ書き戻す。ここを怠ると「キャッシュから消えた = 変更が消えた」になる。

1新ページを要求キャッシュは満杯

2犠牲者を選ぶLRU の末尾

3dirty なら書き戻すここを怠ると変更が消える

4新ページを載せる空いた枠へ

キャッシュ

探す

選定

載せる

ディスク

書戻

満杯時の追い出し。犠牲者が dirty(3)なら必ずディスクに書き戻してから枠を空ける。ここが LRU を DB に使うときの追加責任

LRU の章の Put が追い出した要素を返していたのは、この書き戻しのため。

③ ヒット率はアクセスパターンで決まる

同じ「100回の読み」でも、どのページを触るかでヒット率がまるで変わる。テストでこの両極端を固定してある。

同じページを触り続ける: 最初の1回だけミス、あとは全部ヒット(99%)
毎回違うページ: 容量を超えた瞬間から全部ミス(0%)

試してみる: 3つのパターンを試して、ヒット率のバーの伸び方を見比べてほしい。

デモバッファプール(容量4ページ)未計測

アクセスパターン:

キャッシュ(最近使った順)

空き空き空き空き

集計

ヒット(メモリで完結)0

ミス(ディスクまで読む)0

B-Tree の伏線がここで回収される

ID Generation と B-Tree で見た「昇順キー(UUIDv7)の挿入は速い / ランダムキー(UUIDv4)は遅い」は、最終的にこのヒット率の話だった。

昇順キー: 挿入が常に右端の同じページに当たる → そのページはキャッシュに居続ける → ほぼ全部ヒット → ディスクに触らないから速い
ランダムキー: 挿入が毎回バラバラのページに当たる → テーブルが大きくなるとキャッシュに乗り切らない → ミスだらけ → 挿入のたびにディスク読み

B-Tree のデモで「触るノードが光る」のを見て、ディスクとページで「ページ読みは重い」を知り、ここで「ヒット率が実速度」を数字で見た。3つが揃って初めて「なぜ主キーの選び方でDBの挿入性能が変わるのか」が腑に落ちる。

設計の観点

出入口を1つに絞る: 全部の読み書きが窓口を通るなら、ロックも記録も監視もそこに集約できる
書き戻しを遅らせる: すぐ書かないことで、同じページへの複数回の更新を1回にまとめられる
遅らせた代償を別の仕組みで払う: メモリにある間に落ちると消えるので、WAL が要る
ヒット率を出せるようにする: これが無いと、容量を増やすべきかどうかを議論できない
追い出し方を差し替えられるようにする: 素の LRU が刺さる場面があると分かっているなら
上の層の選択がここに効く: 主キーの選び方が、そのままヒット率になって返ってくる

対照と実例

	単位	書き戻し	追い出し	落ちたとき
バッファプール	ページ	遅らせる	LRU など	WAL が無いと消える
OS のページキャッシュ	ページ	遅らせる	近似 LRU	`fsync` するまで消える
LRU キャッシュ	任意	(該当なし)	LRU	(該当なし)
ライトスルー	任意	すぐ書く	任意	消えない。ただし遅い

裏どり:

PostgreSQL の shared_buffers: まさにこれ。既定値が小さめなのは OS のページキャッシュと二重に持つのを避けるためで、二重キャッシュをどう扱うかは今も議論がある
MySQL InnoDB の buffer pool: 追い出しに素の LRU ではなく midpoint 挿入を使う。新しく読んだページをリストの先頭ではなく 5/8 の位置に入れて、一巡なめる読みで温まった側が押し出されるのを防ぐ。LRU の章で測った崖への、実物の答えになる
書き戻しの順序: dirty なページを書き戻す前に、対応する WAL が先にディスクへ届いていなければならない。これを破ると、クラッシュ後に「ログに無い変更がデータにある」状態になる
主キーの選び方: ID Generation の UUIDv4 と UUIDv7 の差は、最終的にここのヒット率の差になる
ページ単位であること: 1バイトしか要らなくてもページまるごと居座る。行が小さいほど、1ページに詰まる行数が効いてくる

簡略化したこと

pin/unpin なし: 実物は「今まさに使用中のページ」を追い出さないよう固定する。並行アクセスがある DB では必須
WAL 統合なし: 「dirty ページを書き戻す前に、対応する WAL が先にディスクに届いていること」(WAL の順序規則)は実装していない。WAL と本章を繋ぐのが db 編の次の宿題
追い出しは素の LRU: clock 近似も midpoint 挿入も入れていない
先読みなし: 実物は連続したページをまとめて読み込む
書き戻しをまとめない: 追い出すたびに1ページずつ書く。実物は並べ替えてまとめて書く

参考資料

CMU 15-445: Buffer Pools — バッファプールの決定版の講義
PostgreSQL: shared_buffers — 実物の設定
Alex Petrov『Database Internals』4章 — バッファ管理の詳細

バッファプール ​

この章で作るもの ​

① すべての読み書きは窓口を通る ​

② 書き込みは後回しにする ​

追い出しと書き戻し ​

③ ヒット率はアクセスパターンで決まる ​

B-Tree の伏線がここで回収される ​

設計の観点 ​

対照と実例 ​

簡略化したこと ​

参考資料 ​