データベースにおけるキャッシュ置換ポリシー
この記事ではDBMS（データベースマネージメントシステム）で使われる様々なキャッシュ置換ポリシーについて解説します。
紹介するキャッシュ置換ポリシー
| ポリシー | 概要 |
|---|---|
| FIFO | 最初に入れたものを最初に出す（先入れ先出し） |
| LRU | 最も長く使われていないものを削除 |
| LRU-K | 過去K回のアクセス履歴を考慮して削除 |
| Clock | 時計の針のように巡回してチェック |
| LFU | 最もアクセス回数が少ないものを削除 |
| TinyLFU | LRUとLFUの良いとこどり |
目次
DBMSの構成
DBMSは以下4つのサブシステムから構成されています。
各サブシステムは異なる役割を担い、①→②→③→④の順でSQLステートメントを処理します。
| # | サブシステム | 役割 |
|---|---|---|
| ① | Transport Layer | SQLステートメントの受信・転送 |
| ② | Query Processor | SQLのパース・最適化・実行計画の生成 |
| ③ | Execution Engine | 実行計画の実行・結果の集約 |
| ④ | Storage Engine | データの読み書き・トランザクション管理 |
Storage Engineの内部構成
Storage Engine（④）は以下5つのコンポーネントで構成されます。
| コンポーネント | 役割 |
|---|---|
| Transaction Manager | トランザクションの開始・コミット、ACID属性の維持 |
| Lock Manager | 並列操作の制御 |
| Access Methods | ディスク上にデータを配置する方法とアクセス方法を定義 |
| Buffer Manager | ページのキャッシュを担当 ← 本記事のメイントピック |
| Recovery Manager | クラッシュからのリカバリ（例: WAL） |
キャッシュの役割
Storage Engineでは、クエリ実行に必要なデータをページ単位でディスクからキャッシュ（Buffer Pool）に読み込みます。
データ取得の2つのパターン
Cache Miss（ページがキャッシュに存在しない）
Cache Hit（ページがキャッシュに存在する）
なぜキャッシュが重要なのか？
アクセス速度: ディスク ≪ メモリ
容量: ディスク ≫ メモリ
メモリは高速だが容量が限られているため、どのページをキャッシュから削除し、どのページを残すかがデータベースのパフォーマンスを大きく左右します。
キャッシュ置換ポリシー
キャッシュが満タンのとき、どのページを削除（Evict）するかを決めるルールです。
FIFO
First In, First Out - 最初に入ったものを最初に出す
| 項目 | 内容 |
|---|---|
| メリット | シンプルで実装コストが低い |
| デメリット | ページの直近性や利用頻度を考慮しない |
| Bélády's anomaly（キャッシュ増加でMiss増加）が発生 | |
| 採用DB | なし |
Bélády's Anomaly
FIFOでは、キャッシュサイズを増やしてもCache Missが増加することがあります。
LRU
Least Recently Used - 最も長く使われていないものを削除
| 項目 | 内容 |
|---|---|
| メリット | アクセスの直近性を考慮できる |
| デメリット | Lock Contention（アクセス毎にキュー更新が必要） |
| Scan Pollution（大量スキャンで重要でないページが残る） | |
| 採用DB | なし |
Scan Pollution
大量のシーケンシャルスキャンが発生すると、重要でないページがキャッシュに残ってしまいます。
LRU-K
LRU with K references - 過去K回のアクセス履歴を考慮
| 項目 | 内容 |
|---|---|
| メリット | Scan Pollutionを防げる（1回アクセスのページは削除されやすい） |
| デメリット | アクセス履歴の保持コスト |
| Lock Contention（メタデータ更新が必要） | |
| 採用DB | SQL Server（類似ポリシー） |
Scan Pollution Prevention
LRU-KではK回のアクセス履歴を考慮するため、1回だけのスキャンページは削除されやすくなります。
Clock
Clock Algorithm
時計の針のように巡回してアクセスフラグをチェックします。フラグが1の場合は0にし、0の場合は削除（Evict)します。サッカーの違反に対するルールである、『1回目はイエローカードの提示→2回目のイエローカード（レッドカード）で退場する』形に似ています。
| 項目 | 内容 |
|---|---|
| メリット | Lock Contentionを防げる（CAS操作でフラグ更新） |
| デメリット | Cache Pollution（大量スキャン時） |
| アクセス頻度を考慮しない | |
| 採用DB | PostgreSQL（CLOCK-sweep: 頻度カウンター版） |
Compare-and-Swap (CAS)
ClockアルゴリズムではCAS操作を使用してロックなしでフラグを更新します。
LFU
Least Frequently Used - 最もアクセス回数が少ないものを削除
| 項目 | 内容 |
|---|---|
| メリット | 頻繁にアクセスされるページ（インデックスルートなど）が残る |
| 1回だけのアクセスは残りにくい | |
| デメリット | 直近のトレンドを考慮できない |
| 過去に多くアクセスされたが今後不要なページが残り続ける | |
| 採用DB | なし |
LFUのデメリット: トレンドを考慮できない
過去のアクセス頻度が高くても、直近でアクセスがないページが残り続けてしまいます。
TinyLFU
Tiny Least Frequently Used - LRUとLFUの良いとこどり
JavaのキャッシュライブラリCaffeineで採用されています。
アーキテクチャ
各キューの役割
| キュー | サイズ | 役割 |
|---|---|---|
| Admission | 1% | 新規ページの入口。LRUで管理 |
| Probation | 20% | メインキャッシュ。再アクセスでProtectedへ昇格。LRUで管理 |
| Protected | 79% | 高頻度アクセスページ。キャッシュ満タン時はProbationへ降格。LRUで管理 |
Evictの判定
キャッシュが満タンのとき（AdmissionとProbationの両方が満タン）:
- AdmissionのLRUページの頻度を取得
- ProbationのLRUページの頻度を取得
- 1,2で取得したページを比較して頻度が低い方をEvict
| 項目 | 内容 |
|---|---|
| メリット | LRU（直近性）とLFU（頻度）の両方を考慮 |
| Cache Pollutionを防ぎつつトレンドも反映 | |
| デメリット | 実装が複雑（3キュー + 頻度計算 + 判定ロジック） |
| 採用DB | なし（Caffeineライブラリで使用） |
ポリシー比較表
| ポリシー | 直近性 | 頻度 | Lock Contention | 実装難易度 | 採用例 |
|---|---|---|---|---|---|
| FIFO | ✗ | ✗ | 低 | 簡単 | - |
| LRU | ✓ | ✗ | 高 | 簡単 | - |
| LRU-K | ✓ | △ | 高 | 中程度 | SQL Server |
| Clock | ✓ | ✗ | 低 | 中程度 | PostgreSQL |
| LFU | ✗ | ✓ | 中 | 中程度 | - |
| TinyLFU | ✓ | ✓ | 中 | 複雑 | Caffeine |