シリーズ一覧
| Part | タイトル | 内容 |
|---|---|---|
| 1 | B-Treeって何？データ構造から理解する | B-Treeの実装 |
| 2 | ページ管理とバッファプール | ← 今ここ |
| 3 | SQLパーサーを書く | SQL文を解析する |
| 4 | クエリ実行エンジン | 実行計画と処理 |
| 5 | トランザクションとWAL | ACID特性の実装 |
| 6 | インデックスとクエリ最適化 | 高速化の仕組み |
はじめに
前回はB-Treeを実装した。でもあれはメモリ上で動くだけ。
本物のデータベースはディスクにデータを保存する必要がある。
でもディスクI/Oはめちゃくちゃ遅い...
じゃあどうする？
→ バッファプールでキャッシュする！
今回はデータベースのストレージ層、特に「ページ」と「バッファプール」を実装していく。
ページとは
データベースはページ単位で管理する
ディスクから1バイトずつ読み書きするのは効率が悪い。
だからデータベースは固定サイズのページ単位でI/Oする。
┌─────────────────────────────────────────────────┐
│ データベースファイル │
├────────┬────────┬────────┬────────┬────────────┤
│ Page 0 │ Page 1 │ Page 2 │ Page 3 │ ... │
│ 4KB │ 4KB │ 4KB │ 4KB │ │
└────────┴────────┴────────┴────────┴────────────┘
一般的なページサイズ：
- SQLite: 4KB（デフォルト）
- PostgreSQL: 8KB
- MySQL InnoDB: 16KB
ページの構造
/// ページサイズ（4KB）
pub const PAGE_SIZE: usize = 4096;
/// ページ
pub struct Page {
/// ページID
pub id: PageId,
/// ページデータ（固定サイズのバイト配列）
pub data: [u8; PAGE_SIZE],
/// ダーティフラグ（変更されたかどうか）
pub is_dirty: bool,
/// ピンカウント（このページを使用中のトランザクション数）
pub pin_count: u32,
}
重要なフィールド：
-
is_dirty: 変更されたかどうか。ディスクに書き戻す必要があるか判断 -
pin_count: 使用中の数。0でないとメモリから追い出せない
ページヘッダー
各ページの先頭にはメタデータを格納する「ヘッダー」がある。
ページ構造:
┌──────────────────────────────────────────┐
│ Header (16 bytes) │
│ ┌──────────┬──────────┬────────────────┐ │
│ │ PageId │ Type │ Record Count │ │
│ │ (4 bytes)│ (1 byte) │ (2 bytes) etc │ │
│ └──────────┴──────────┴────────────────┘ │
├──────────────────────────────────────────┤
│ Data (4080 bytes) │
│ │
│ 実際のキーや値が入る │
│ │
└──────────────────────────────────────────┘
impl Page {
/// ページIDをヘッダーから読み取る
pub fn get_page_id(&self) -> PageId {
u32::from_le_bytes([self.data[0], self.data[1], self.data[2], self.data[3]])
}
/// ページIDをヘッダーに書き込む
pub fn set_page_id(&mut self, id: PageId) {
let bytes = id.to_le_bytes();
self.data[0..4].copy_from_slice(&bytes);
self.id = id;
}
/// 特定のオフセットにデータを書き込む
pub fn write_bytes(&mut self, offset: usize, data: &[u8]) {
self.data[offset..offset + data.len()].copy_from_slice(data);
self.is_dirty = true;
}
}
ディスクマネージャー
ページとファイルの対応を管理する。
/// ディスクマネージャー
pub struct DiskManager {
/// データベースファイル
file: File,
/// 次に割り当てるページID
next_page_id: PageId,
}
ページの読み書き
impl DiskManager {
/// ページをディスクから読み込む
pub fn read_page(&mut self, page_id: PageId, page: &mut Page) -> std::io::Result<()> {
// ページID × ページサイズ = ファイル内オフセット
let offset = page_id as u64 * PAGE_SIZE as u64;
self.file.seek(SeekFrom::Start(offset))?;
self.file.read_exact(&mut page.data)?;
page.id = page_id;
Ok(())
}
/// ページをディスクに書き込む
pub fn write_page(&mut self, page: &Page) -> std::io::Result<()> {
let offset = page.id as u64 * PAGE_SIZE as u64;
self.file.seek(SeekFrom::Start(offset))?;
self.file.write_all(&page.data)?;
self.file.flush()?;
Ok(())
}
}
シンプルな対応：
- Page 0 → ファイルの 0〜4095 バイト目
- Page 1 → ファイルの 4096〜8191 バイト目
- Page N → ファイルの N×4096 バイト目から
バッファプールとは
なぜバッファプールが必要か
毎回ディスクから読み書きすると遅すぎる。
メモリアクセス: ～100ns
ディスクアクセス: ～10,000,000ns (10ms)
約10万倍の差！
だからよく使うページをメモリにキャッシュする。これがバッファプール。
┌───────────────────────────────────────────┐
│ Buffer Pool │
│ ┌────────┬────────┬────────┬────────┐ │
│ │ Frame │ Frame │ Frame │ Frame │ │
│ │ 0 │ 1 │ 2 │ 3 │ │
│ │ Page 5 │ Page 2 │ Page 0 │ (empty)│ │
│ └────────┴────────┴────────┴────────┘ │
│ ↑↓ │
└────────────────────┼─────────────────────┘
│
↓
┌───────────────────────────────────────────┐
│ Disk (Database File) │
│ Page 0 Page 1 Page 2 Page 3 ... │
└───────────────────────────────────────────┘
バッファプールの構造
pub struct BufferPool {
/// ページID -> バッファ内インデックスのマッピング
page_table: HashMap<PageId, usize>,
/// ページバッファ（固定サイズ）
pages: Vec<Page>,
/// 空きフレームのリスト
free_list: VecDeque<usize>,
/// LRUリスト（最近使われた順）
lru_list: VecDeque<usize>,
/// ディスクマネージャー
disk_manager: DiskManager,
}
主要な操作
1. ページの取得（fetch_page）
pub fn fetch_page(&mut self, page_id: PageId) -> Option<&mut Page> {
// すでにバッファにあるか確認
if let Some(&frame_id) = self.page_table.get(&page_id) {
// ピンカウントを増やす
self.pages[frame_id].pin_count += 1;
// LRUリストを更新
self.update_lru(frame_id);
return Some(&mut self.pages[frame_id]);
}
// バッファにない：ディスクから読み込む
let frame_id = self.get_free_frame()?;
// ディスクから読み込む
if self.disk_manager.read_page(page_id, &mut self.pages[frame_id]).is_err() {
self.free_list.push_back(frame_id);
return None;
}
// 設定を更新
let page = &mut self.pages[frame_id];
page.pin_count = 1;
page.is_dirty = false;
// ページテーブルに追加
self.page_table.insert(page_id, frame_id);
self.lru_list.push_front(frame_id);
Some(&mut self.pages[frame_id])
}
処理の流れ：
- まずバッファ（メモリ）を確認
- あればそれを返す（ヒット）
- なければディスクから読み込む（ミス）
2. ピンの解除（unpin_page）
pub fn unpin_page(&mut self, page_id: PageId, is_dirty: bool) -> bool {
if let Some(&frame_id) = self.page_table.get(&page_id) {
let page = &mut self.pages[frame_id];
if page.pin_count == 0 {
return false; // すでに0
}
page.pin_count -= 1;
if is_dirty {
page.is_dirty = true; // 変更されたことを記録
}
true
} else {
false
}
}
なぜピンが必要？
ページを使ってる最中に追い出されたら困る。
トランザクションA: Page 5を読み込み中...
バッファプール: 空きがないからPage 5追い出すか
トランザクションA: え？？？
ピンカウントが0より大きいページは追い出し対象にならない。
3. ページの追い出し（LRU）
バッファが満杯のとき、どのページを追い出すか？
LRU（Least Recently Used）: 最も長く使われていないページを追い出す
fn evict_page(&mut self) -> Option<usize> {
// LRUリストの末尾から、ピンされていないページを探す
for i in (0..self.lru_list.len()).rev() {
let frame_id = self.lru_list[i];
if self.pages[frame_id].pin_count == 0 {
// ダーティなら書き込む
if self.pages[frame_id].is_dirty {
let _ = self.disk_manager.write_page(&self.pages[frame_id]);
}
// 追い出し処理
let page_id = self.pages[frame_id].id;
self.page_table.remove(&page_id);
self.lru_list.remove(i);
self.pages[frame_id].reset();
return Some(frame_id);
}
}
None // 全部ピンされてて追い出せない
}
追い出すときは必ずダーティチェックする。変更されていたらディスクに書き戻す。
動作確認
実際に動かしてみよう。
fn main() {
let mut pool = BufferPool::new(4, "demo.db").unwrap();
// 新しいページを3つ作成
let page1 = pool.new_page().unwrap();
let page2 = pool.new_page().unwrap();
let page3 = pool.new_page().unwrap();
println!("Created pages: {}, {}, {}", page1, page2, page3);
// ページにデータを書き込み
if let Some(page) = pool.fetch_page(page1) {
page.write_bytes(16, b"Hello from Page 1!");
}
pool.debug_print();
}
実行結果：
--- 新しいページを3つ作成 ---
Created pages: 0, 1, 2
--- バッファプールの状態 ---
=== Buffer Pool Status ===
Pool size: 4
Pages in buffer: 3
Free frames: 1
PageId=0, Frame=0, Dirty=true, PinCount=2
PageId=1, Frame=1, Dirty=true, PinCount=2
PageId=2, Frame=2, Dirty=true, PinCount=1
3つのページがバッファに載ってる。PinCount=2はnew_pageとfetch_pageで2回ピンされたから。
永続化の確認
// フラッシュしてファイルを閉じる
pool.flush_all();
drop(pool);
// 再度開く
let mut pool2 = BufferPool::new(4, "demo.db").unwrap();
// 読み込み
if let Some(page) = pool2.fetch_page(page1) {
let data = page.read_bytes(16, 18);
let text = String::from_utf8_lossy(data);
println!("Read from page {}: \"{}\"", page1, text);
}
--- バッファプールを再作成してディスクから読み込み ---
Read from page 0: "Hello from Page 1!"
ちゃんとディスクに保存されて、再読み込みできてる！
追い出しのテスト
// 小さいバッファプール（2ページ分）
let mut pool = BufferPool::new(2, "test.db").unwrap();
// 3ページ作成（1つは追い出される）
let page1 = pool.new_page().unwrap();
pool.unpin_page(page1, false);
let page2 = pool.new_page().unwrap();
pool.unpin_page(page2, false);
let page3 = pool.new_page().unwrap(); // ここでpage1が追い出される
pool.unpin_page(page3, false);
// でもディスクにはあるので読み込める
let page = pool.fetch_page(page1);
assert!(page.is_some()); // OK!
2フレームしかないのに3ページ使おうとすると、LRUで最も古いページが追い出される。でもディスクには保存されてるので、再度fetch_pageすれば読み込める。
バッファプール置換アルゴリズム
LRU以外にもいろんなアルゴリズムがある。
| アルゴリズム | 特徴 |
|---|---|
| LRU | シンプル、実装が簡単 |
| Clock | LRUの近似、低オーバーヘッド |
| LRU-K | 直近K回のアクセスを考慮 |
| 2Q | 一時的なアクセスとホットデータを区別 |
| ARC | 自己チューニング型LRU |
PostgreSQLはClock Sweep、MySQLはLRU変種を使ってる。
実際のデータベースとの比較
PostgreSQLのバッファプール
- 共有メモリにバッファプールを配置
-
shared_buffersパラメータでサイズを設定（デフォルト128MB） - Background Writerがダーティページを書き出す
SQLiteのPage Cache
- デフォルトで最大2000ページ（約8MB）
-
PRAGMA cache_sizeで変更可能 - WALモードで効率的な書き込み
まとめ
今回作ったもの：
- Page: 固定サイズのデータ単位
- DiskManager: ファイルI/Oの抽象化
- BufferPool: ページのキャッシュ管理
バッファプールはデータベースの性能を決める重要なコンポーネント。
メモリに収まるデータへのアクセスは超高速、ディスクI/Oは極力減らす。この発想がデータベースエンジンの基本。
次回はいよいよSQLパーサーを実装して、SQL文を解析できるようにしていく！
この記事が役に立ったら、いいね・ストックしてもらえると嬉しいです！