sharin

Appearance

バッファプール ​

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

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

この章で作るもの ​

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

この章の肝は3つ。

  • 読み書きはすべてこの窓口を通る。よく使うページをメモリに留めて 「同じページなら2回目からタダ同然」(ディスクとページ)を実現する
  • 書き込みはキャッシュ上のページに dirty の印を付けるだけ。 ディスクへの書き戻しは追い出されるときまで遅らせる(速さの源泉)
  • ヒット率がすべてを決める。そしてヒット率はアクセスの局所性で決まる —— ここでB-Treeの右端挿入がなぜ速いかが最後まで繋がる

前提章

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

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

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

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

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

go
// 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 のとき。

go
// 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の挿入性能が変わるのか」が腑に落ちる。

メリット / デメリット ​

メリット

  • ディスクI/Oを局所性のぶんだけ削れる。DBの実効性能を左右する中心部品
  • 書き込みをまとめて遅延できる(ランダム書き込みをシーケンシャルに近づけられる)
  • ページの出入り口が1箇所なので、WAL 連携やロックをここに集約できる

デメリット

  • dirty ページがメモリにある間はクラッシュに弱い(WAL とセットで初めて安全)
  • 素の LRU はスキャン耐性がない(LRU 参照)
  • ページ単位のキャッシュなので、1バイトしか要らなくてもページまるごと居座る

実例

  • PostgreSQL の shared_buffers、MySQL InnoDB の buffer pool — まさにこれ
  • OS のページキャッシュ(mmap されたファイルの裏で動いている)
  • SQLite の page cache

簡略化したこと ​

  • pin/unpin なし: 実物は「今まさに使用中のページ」を追い出さないよう固定する。 並行アクセスがある DB では必須
  • WAL 統合なし: 「dirty ページを書き戻す前に、対応する WAL が先にディスクに 届いていること」(WAL の順序規則)は実装していない。WAL と本章を 繋ぐのが db 編の次の宿題
  • 追い出しは素の LRU: 実物は clock 近似や midpoint 挿入の変種

参考資料 ​