MiniDB

教育目的で作成されたディスクベースのデータベースエンジン。以下の機能を実装しています：

ディスクベースストレージ - ページ構造、バッファプール（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 1

インデックスの利用

minidb> 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チェーンを逆順に辿ってロールバック

ディスクファイル形式

data.db (ページファイル)

┌─────────────────────────────────────────┐
│ File Header (16 bytes)                  │
│   Magic: "MINIDBPD" | Version | NumPages│
├─────────────────────────────────────────┤
│ Page 0 (4096 bytes) - Catalog           │
├─────────────────────────────────────────┤
│ Page 1 (4096 bytes) - Table Data        │
├─────────────────────────────────────────┤
│ Page 2 (4096 bytes) - ...               │
└─────────────────────────────────────────┘

wal.log (WALファイル)

┌─────────────────────────────────────────┐
│ 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

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Repository files navigation

MiniDB

アーキテクチャ

ディレクトリ構造

ビルド & 実行

使用例

インデックスの利用

統計情報

詳細ドキュメント

主要コンポーネントの解説

1. ページ構造 (`storage/page.go`) — 詳細

2. バッファプール (`storage/buffer.go`) — 詳細

3. WAL書き込み (`wal/writer.go`) — 詳細

4. MVCC可視性 (`txn/mvcc.go`) — 詳細

5. B-Treeインデックス (`index/btree.go`) — 詳細

6. ARIESリカバリ (`wal/recovery.go`) — 詳細

ディスクファイル形式

data.db (ページファイル)

wal.log (WALファイル)

学習リソース

今後の拡張案

ライセンス

About

Uh oh!

Releases

Packages

Contributors 2

Uh oh!

Languages

Name		Name	Last commit message	Last commit date
Latest commit History 15 Commits
.github/workflows		.github/workflows
cmd/minidb		cmd/minidb
docs		docs
internal		internal
pkg/types		pkg/types
.gitignore		.gitignore
LICENSE		LICENSE
README.md		README.md
go.mod		go.mod
minidb		minidb

License

kyosu-1/minidb

Folders and files

Latest commit

History

Repository files navigation

MiniDB

アーキテクチャ

ディレクトリ構造

ビルド & 実行

使用例

インデックスの利用

統計情報

詳細ドキュメント

主要コンポーネントの解説

1. ページ構造 (storage/page.go) — 詳細

2. バッファプール (storage/buffer.go) — 詳細

3. WAL書き込み (wal/writer.go) — 詳細

4. MVCC可視性 (txn/mvcc.go) — 詳細

5. B-Treeインデックス (index/btree.go) — 詳細

6. ARIESリカバリ (wal/recovery.go) — 詳細

ディスクファイル形式

data.db (ページファイル)

wal.log (WALファイル)

学習リソース

今後の拡張案

ライセンス

About

Resources

License

Uh oh!

Stars

Watchers

Forks

Releases

Packages 0

Contributors 2

Uh oh!

Languages

1. ページ構造 (`storage/page.go`) — 詳細

2. バッファプール (`storage/buffer.go`) — 詳細

3. WAL書き込み (`wal/writer.go`) — 詳細

4. MVCC可視性 (`txn/mvcc.go`) — 詳細

5. B-Treeインデックス (`index/btree.go`) — 詳細

6. ARIESリカバリ (`wal/recovery.go`) — 詳細

Packages