教育目的で作成されたディスクベースのデータベースエンジン。以下の機能を実装しています：
- ディスクベースストレージ - ページ構造、バッファプール（LRU）
- WAL (Write-Ahead Logging) - クラッシュリカバリのためのログ先行書き込み
- ARIES Recovery - 3フェーズリカバリ（Analysis → Redo → Undo）
- MVCC - スナップショット分離による並行制御
- B-Treeインデックス - カラム値ベースのキー、自動メンテナンス、SELECT WHERE最適化
- SQLパーサー - CREATE, INSERT, SELECT, UPDATE, DELETE
- VACUUM - MVCCデッドタプルのガベージコレクション
graph TD
subgraph REPL["REPL (cmd/minidb)"]
Main["main.go"]
end
subgraph Engine["Engine (engine.go)"]
E["Engine"]
end
subgraph SQL["SQL Layer"]
Lexer --> Parser --> Executor
end
subgraph Txn["Transaction Layer"]
TxnManager["TxnManager<br/>BEGIN / COMMIT / ROLLBACK"]
Snapshot["MVCC Snapshot<br/>Visibility Check"]
TxnManager --> Snapshot
end
subgraph Storage["Storage Layer"]
Catalog["Catalog<br/>Schema"]
TableHeap["TableHeap<br/>Rows"]
BTree["B-Tree Index"]
BufferPool["BufferPool<br/>LRU Cache"]
DiskManager["DiskManager<br/>Page I/O"]
Catalog --> BufferPool
TableHeap --> BufferPool
BTree --> BufferPool
BufferPool --> DiskManager
end
subgraph WAL["WAL Layer"]
Writer["WAL Writer<br/>Log + fsync"]
Recovery["RecoveryManager<br/>ARIES 3-Phase"]
end
subgraph Disk["Disk Files"]
data["data.db<br/>4KB Pages"]
wallog["wal.log<br/>Log Records"]
meta["minidb.meta<br/>Catalog PageID"]
end
Main --> E
E --> Executor
Executor --> TxnManager
Executor --> Writer
Executor --> Catalog
Executor --> BufferPool
TxnManager --> Writer
E --> Recovery
Recovery --> Writer
DiskManager --> data
Writer --> wallog
E --> meta
minidb/
├── .github/workflows/test.yml # CI（GitHub Actions）
├── cmd/minidb/main.go # エントリーポイント（REPL）
├── internal/
│ ├── engine/engine.go # データベースエンジン
│ ├── storage/
│ │ ├── page.go # ページ構造（4KB固定サイズ）
│ │ ├── disk.go # ディスクマネージャー
│ │ ├── buffer.go # バッファプール（LRU）
│ │ └── heap.go # テーブルヒープ & カタログ
│ ├── index/
│ │ └── btree.go # B-Treeインデックス
│ ├── sql/
│ │ ├── lexer.go # 字句解析
│ │ ├── parser.go # 構文解析
│ │ └── executor.go # 実行エンジン
│ ├── txn/
│ │ ├── transaction.go # トランザクション管理
│ │ └── mvcc.go # MVCCスナップショット可視性
│ └── wal/
│ ├── log.go # ログレコード定義
│ ├── writer.go # ログ書き込み
│ └── recovery.go # ARIESリカバリ
├── pkg/types/types.go # 共通型定義
├── go.mod
└── README.md
# ビルド
cd minidb
go build -o minidb ./cmd/minidb
# 実行
./minidb -data ./mydata -buffer 1024
# オプション:
# -data データディレクトリ (default: ./minidb-data)
# -buffer バッファプールサイズ (default: 1024 pages = 4MB)minidb> CREATE TABLE users (id INT, name TEXT, active BOOL)
CREATE TABLE users (id=1)
minidb> INSERT INTO users (id, name, active) VALUES (1, 'Alice', true)
INSERT 1 (page=1, slot=0)
minidb> INSERT INTO users (id, name, active) VALUES (2, 'Bob', false)
INSERT 1 (page=1, slot=1)
minidb> SELECT * FROM users
├──────┼───────┼────────┤
│ id │ name │ active │
├──────┼───────┼────────┤
│ 1 │ Alice │ true │
│ 2 │ Bob │ false │
├──────┼───────┼────────┤
SELECT 2 rows
minidb> BEGIN
BEGIN (txn 5)
minidb> UPDATE users SET active = true WHERE id = 2
UPDATE 1
minidb> COMMIT
COMMIT (txn 5)
minidb> DELETE FROM users WHERE id = 1
DELETE 1
minidb> vacuum
VACUUM: removed 1 dead tuples.
users: scanned 2, removed 1minidb> CREATE TABLE products (id INT, name TEXT)
minidb> INSERT INTO products VALUES (1, 'Apple')
minidb> INSERT INTO products VALUES (2, 'Banana')
minidb> INSERT INTO products VALUES (3, 'Cherry')
-- カラム値ベースのインデックスを作成
minidb> create index on products(id)
Index created on products(id)
-- インデックス経由の高速検索（フルスキャンではなくB-Tree探索）
minidb> SELECT * FROM products WHERE id = 2
├────┼────────┤
│ id │ name │
├────┼────────┤
│ 2 │ Banana │
├────┼────────┤
SELECT 1 rows
-- INSERT/UPDATE後もインデックスは自動メンテナンスされる
minidb> INSERT INTO products VALUES (4, 'Date')
minidb> SELECT * FROM products WHERE id = 4
├────┼──────┤
│ id │ name │
├────┼──────┤
│ 4 │ Date │
├────┼──────┤
SELECT 1 rows
-- VACUUM後はインデックスが再構築される
minidb> DELETE FROM products WHERE id = 1
minidb> vacuum
VACUUM: removed 1 dead tuples.minidb> stats
╔══════════════════════════════════════════╗
║ Database Statistics ║
╠══════════════════════════════════════════╣
║ WAL Current LSN: 15 ║
║ WAL Flushed LSN: 14 ║
║ Active Txns: 0 ║
╠══════════════════════════════════════════╣
║ Disk Pages: 2 ║
║ Tables: 1 ║
╠══════════════════════════════════════════╣
║ Buffer Pool Hits: 12 ║
║ Buffer Pool Misses: 2 ║
║ Buffer Pool Cached: 2 ║
║ Buffer Hit Rate: 85.7% ║
╚══════════════════════════════════════════╝各コンポーネントの理論背景と実装の詳細は docs/ にまとめています。
| ドキュメント | 内容 |
|---|---|
| ストレージエンジン | スロットページ、ディスクマネージャ、バッファプール、テーブルヒープ、カタログ |
| WAL と ARIES リカバリ | Write-Ahead Logging のプロトコル、ログレコード形式、ARIES 3 フェーズリカバリ |
| トランザクションと MVCC | トランザクション管理、スナップショット分離、MVCC 可視性ルール |
| B-Tree インデックス | B-Tree の基礎、ノードフォーマット、検索・挿入・分割アルゴリズム |
| SQL パーサーと実行エンジン | 字句解析、再帰下降パーサー、各 SQL 文の実行フロー |
1. ページ構造 (storage/page.go) — 詳細
┌────────────────────────────────────────┐
│ Header (28 bytes) │
│ PageID(4) | Type(1) | Reserved(3) │
│ LSN(8) | SlotCount(2) │
│ FreeSpaceOffset(2) | FreeSpaceEnd(2)│
│ NextPageID(4) | Reserved(2) │
├────────────────────────────────────────┤
│ │
│ Free Space │
│ │
├────────────────────────────────────────┤
│ ← Tuple Data (grows downward) │
├────────────────────────────────────────┤
│ Slot Array (grows upward) → │
│ [offset|len] [offset|len] ... │
└────────────────────────────────────────┘
ヒープページは NextPageID フィールドによりリンクリストで連結されます（連続ページ番号を仮定しません）。
2. バッファプール (storage/buffer.go) — 詳細
type BufferPool struct {
pages map[PageID]*Page // ページキャッシュ
lruList *list.List // LRU順序
capacity int // 最大ページ数
}
// ページ取得: キャッシュにあればヒット、なければディスクから読む
func (bp *BufferPool) FetchPage(pageID) (*Page, error) {
if page := bp.pages[pageID]; page != nil {
bp.hits++
bp.touchLRU(pageID) // LRUを更新
return page, nil
}
bp.misses++
page := bp.diskManager.ReadPage(pageID)
bp.evictIfNeeded() // 必要ならLRUページを追い出し
bp.pages[pageID] = page
return page, nil
}3. WAL書き込み (wal/writer.go) — 詳細
// コミット時の処理
func (w *Writer) LogCommit(txnID) (LSN, error) {
// 1. COMMITレコードをバッファに追加
lsn := w.Append(&LogRecord{Type: COMMIT, TxnID: txnID})
// 2. 【重要】ディスクに強制書き込み（fsync）
// これにより、クラッシュしてもコミットが失われない
w.Force(lsn)
return lsn, nil
}4. MVCC可視性 (txn/mvcc.go) — 詳細
func (s *Snapshot) IsVisible(tuple *Tuple) bool {
// 作成トランザクションが可視か？
if !s.isTxnVisible(tuple.XMin) {
return false
}
// 削除されていないか？
if tuple.XMax == InvalidTxnID {
return true // 削除されていない
}
// 削除トランザクションがまだ見えない？
if !s.isTxnVisible(tuple.XMax) {
return true // まだ削除は見えない
}
return false // 削除済み
}5. B-Treeインデックス (index/btree.go) — 詳細
[30|60] ← 内部ノード
/ | \
[10|20] [40|50] [70|80] ← リーフノード
↓ ↓ ↓
RIDs RIDs RIDs ← 行位置（PageID + SlotNum）
カラム値をソート順保持エンコーディングでキー化し、SELECT ... WHERE col = val でインデックス探索を行う。INSERT/UPDATE 時にインデックスは自動メンテナンスされ、VACUUM 時に再構築される。
6. ARIESリカバリ (wal/recovery.go) — 詳細
Phase 1: Analysis
└─ ログを走査してATT（アクティブTxn）とDPT（ダーティページ）を再構築
Phase 2: Redo
└─ DPTの最小RecLSNから全ての変更を再適用（コミット済み/未コミット両方）
Phase 3: Undo
└─ ATT内の未コミットTxnをPrevLSNチェーンを逆順に辿ってロールバック
┌─────────────────────────────────────────┐
│ File Header (16 bytes) │
│ Magic: "MINIDBPD" | Version | NumPages│
├─────────────────────────────────────────┤
│ Page 0 (4096 bytes) - Catalog │
├─────────────────────────────────────────┤
│ Page 1 (4096 bytes) - Table Data │
├─────────────────────────────────────────┤
│ Page 2 (4096 bytes) - ... │
└─────────────────────────────────────────┘
┌─────────────────────────────────────────┐
│ File Header (16 bytes) │
│ Magic: "MINIDBWA" | Version │
├─────────────────────────────────────────┤
│ LogRecord 1: [len][LSN|PrevLSN|TxnID|...│
├─────────────────────────────────────────┤
│ LogRecord 2: [len][LSN|PrevLSN|TxnID|...│
├─────────────────────────────────────────┤
│ ... │
└─────────────────────────────────────────┘
- ARIES論文: "ARIES: A Transaction Recovery Method" (Mohan et al., 1992)
- 書籍: "Database Internals" by Alex Petrov
- PostgreSQLソース:
src/backend/access/transam/,src/backend/storage/buffer/ - CMU 15-445: Database Systems (Andy Pavlo)
| 機能 | 説明 |
|---|---|
| WAL圧縮 | 古いログの削除・圧縮 |
| 並列スキャン | 複数スレッドでのテーブルスキャン |
| クエリオプティマイザ | 実行計画の最適化 |
| JOIN | 複数テーブルの結合 |
| 複合インデックス | 複数カラムにまたがるインデックス |
| 非ユニークインデックス | 重複キーのサポート（現在は同一キーで上書き） |
MIT License