動手打造 MiniDB

為什麼要自己寫一個

前 18 章的每個概念——slotted page、latch crabbing、clock sweep、WAL 的兩條規則、可見性判定、Selinger DP——在實作它們之前都只是知識； 實作之後才會變成直覺。MiniDB 的目標不是取代任何資料庫，而是一個約 10–15k 行、你完全理解每一行的系統。 三個原則：正確優先（每個版本都有完整測試）、小步前進（每個版本都是可用的資料庫）、抄最好的設計（命名與架構盡量跟隨 PostgreSQL 與 BusTub，閱讀它們的原始碼時會輕鬆很多）。

架構總覽

專案佈局與工具鏈

minidb/
  CMakeLists.txt            # C++20, -Wall -Wextra -Werror, 可選 -fsanitize=address,undefined / thread
  src/
    common/                 # 型別、錯誤、config（PAGE_SIZE = 8192）、RID、Value
    storage/disk/           # disk_manager.{h,cc}
    storage/page/           # page.h、slotted_page.{h,cc}、b_plus_tree_page.{h,cc}
    storage/table/          # tuple.{h,cc}、table_heap.{h,cc}、table_iterator
    storage/index/          # b_plus_tree.{h,cc}、index_iterator
    buffer/                 # buffer_pool_manager.{h,cc}、lru_k_replacer / clock_replacer、page_guard.h
    catalog/                # catalog.{h,cc}、schema.h、column.h、statistics.h
    parser/                 # lexer.{h,cc}、parser.{h,cc}、ast.h
    binder/                 # 名稱解析、型別檢查 → bound statement
    planner/                # logical plan、optimizer（v6）、physical plan
    execution/              # executor_context、executors/*.cc、expressions/*.cc
    concurrency/            # transaction.h、transaction_manager.{h,cc}、lock_manager.{h,cc}
    recovery/               # log_record.h、log_manager.{h,cc}、checkpoint、recovery_manager.{h,cc}
    network/                # pg_protocol.{h,cc}、server.{h,cc}（v7）
    replication/            # wal_sender、wal_receiver、raft/（v7）
  test/                     # GoogleTest：每個模組一個 *_test.cc
  test/sql/                 # sqllogictest 格式的 .slt 檔
  tools/                    # shell（REPL）、crash_test harness、bench
  third_party/              # googletest、fmt、（可選）antlr 或 lemon

工具鏈建議：CMake + Ninja；GoogleTest；clang-format／clang-tidy；AddressSanitizer + UBSan 常開、ThreadSanitizer 跑並行測試； libFuzzer 對 parser 與 tuple 反序列化做模糊測試；／Instruments 看熱點。所有測試在 CI（GitHub Actions）上跑三種建置：Debug+ASan、Debug+TSan、Release。

v1：SQL 子集合、Heap File、Page Manager

目標：能 、、（含兩表 join）、、，資料持久化在單一檔案，重啟後仍在。

• SQL 子集合與 parser：手寫 lexer；陳述式用遞迴下降、表達式用 Pratt parser（運算子優先序）。支援型別 、、、、； 運算子 ； 的三值邏輯從第一天就做對。先不要用 parser generator——手寫 parser 約 800 行，而且錯誤訊息更好。

• Catalog：／ 的迷你版：兩張系統表存在固定頁面，啟動時載入成記憶體結構；表 id、欄位名稱／型別／位置、first page id。

• Tuple 格式：標頭（長度、null bitmap）+ 固定長度欄位 + 變長欄位的（offset, length）+ 變長資料區。 不需要反序列化整筆。

• Slotted page：第 2 章的設計，；標頭含 LSN（為 v4 預留）、slot 數、free space 指標；。

• TableHeap：頁面以雙向鏈結（prev/next page id）串起；插入時從最後一頁開始找空間（v6 可加 FSM）； 依序走訪。

• DiskManager：以 讀寫第 \(n\) 頁； 從檔尾或 free list。v1 可以直接「每次讀寫都碰磁碟」或放一個最簡單的 map 快取，v3 再換成真正的 buffer pool。

• Executor：第 5 章的 Volcano 介面，、、、、、、、。 Planner 先是「規則式」：AST \(\to\) 運算子樹的直接對應。

• REPL：，支援 、。

struct RID { page_id_t page_id; uint32_t slot; };

class DiskManager {
 public:
  explicit DiskManager(const std::string &path);
  void ReadPage(page_id_t id, char *out);        // 讀 PAGE_SIZE bytes
  void WritePage(page_id_t id, const char *data); // 不保證 fsync；Sync() 另外呼叫
  page_id_t AllocatePage();
  void Sync();
};

class TableHeap {
 public:
  std::optional<RID> InsertTuple(const Tuple &t, Transaction *txn);
  std::optional<Tuple> GetTuple(RID rid, Transaction *txn) const;
  bool MarkDelete(RID rid, Transaction *txn);
  bool UpdateTuple(const Tuple &t, RID rid, Transaction *txn);  // 放不下則 delete + insert
  TableIterator Begin(Transaction *txn);  TableIterator End();
};

class AbstractExecutor {
 public:
  virtual void Init() = 0;
  virtual bool Next(Tuple *tuple, RID *rid) = 0;
  virtual const Schema &GetOutputSchema() const = 0;
  virtual ~AbstractExecutor() = default;
};

驗收：100 個 sqllogictest 案例通過（含 NULL 語意、字串比較、join 正確性）；插入 10 萬列後重啟能全部讀回；ASan 無報告。

v2：B+Tree 索引

目標：；等值與範圍查詢走索引；索引與表同步維護。

• 頁面式 B+Tree（第 3 章）：（root id）、（\(n\) 個 key、\(n+1\) 個 child）、（key、RID、next leaf id）。 階數由 與鍵長算出；先支援固定長度鍵（整數、定長字串），再加變長鍵。

• API：、、、／ 回傳 做範圍掃描。

• 分裂與合併／重分配完整實作；根節點的升降；空樹與單一葉節點的邊界。

• 與 planner 規則： 或範圍條件且 有索引時使用； 執行器同步更新所有索引。

• 並行（可延後到 v3 之後）：latch crabbing（讀：一路 read latch；寫：樂觀先用 read latch，發現需分裂再重來用 write latch）。

驗收：以 為 oracle 的隨機插入／刪除／查詢 100 萬次對照測試；重啟後索引可用； （並行版）TSan 乾淨，多執行緒混合讀寫結果與單執行緒一致。這與 CMU 15-445 Project #2 幾乎等價，可參考其測試設計。

v3：Buffer Pool

目標：所有頁面存取經過 ；可以用 64 個 frame 跑 1 GB 的資料庫；多執行緒安全。

• ；page table（ + mutex，進階：分區）；free list。

• Replacer：先做 Clock（第 4 章），再做 LRU-K（BusTub 的選擇）；可淘汰的條件是 pin count = 0。

• PageGuard：RAII 物件在解構時 unpin（並釋放 latch）——這會消滅一整類「忘記 unpin」的 bug。／ 同時取得頁面 latch。

• 把 v1、v2 所有直接呼叫 的地方換掉；加入命中率統計； 風格的輸出。

• 進階：背景寫出執行緒；disk scheduler（I/O 佇列由專用執行緒處理，BusTub Project #1）；掃描用 ring buffer 避免沖掉熱資料。

驗收：pool size 遠小於資料量時所有 v1/v2 測試仍通過；pin 計數在每個測試結束時為 0；並行壓測無死鎖、TSan 乾淨。

v4：交易、WAL 與復原

目標：； 後重啟不遺失已 commit 的交易、未 commit 的交易消失；多個交易並行正確。

• （id、狀態、持有的鎖、undo 用的寫入集合、prevLSN）；。

• ：表鎖與列鎖，模式 S/X（進階 IS/IX/SIX），strict 2PL，等待圖死結偵測執行緒（第 10 章）。先用表級鎖讓一切正確，再細化。

• （第 8 章）：記憶體緩衝、背景 flush、group commit； 型別：BEGIN/COMMIT/ABORT/INSERT/DELETE/UPDATE/NEW_PAGE/CLR/CHECKPOINT。 頁面標頭的 LSN 開始發揮作用：寫出任何頁面前，先確保該頁 LSN 之前的日誌已落盤（在 內呼叫 ）。

• ：ARIES 三階段（第 11 章），或在 v5 之後改為 redo-only。Checkpoint 以背景執行緒定期進行。

• 隔離等級：此版本以 2PL 提供 SERIALIZABLE（讀也要鎖），v5 再換成 MVCC。

驗收：當機注入測試——測試程式 出資料庫程序執行隨機轉帳負載，在隨機時刻 ，重啟後驗證「總額守恆」與「所有已回覆成功的交易存在」，重複 500 次； 死結測試中恰好一方被中止； 後資料與索引一致。

v5：MVCC

目標：讀不阻塞寫、寫不阻塞讀；提供 READ COMMITTED 與 REPEATABLE READ（snapshot isolation）；垃圾回收。

• Tuple 標頭加 、、（RID）；UPDATE 走 append-only + 版本鏈（第 9 章）。

• 由 產生；RC 每語句一個、RR 每交易一個； 實作第 9 章的規則。

• 寫寫衝突：等待對方結束；RR 下對方 commit 則回報 serialization failure；RC 下重新讀最新版本並重新評估條件。

• 索引：指向所有版本，掃描時過濾可見性（PostgreSQL 做法）；或實作 HOT 的簡化版。

• ：找出對所有活動快照都不可見的死版本回收 slot；維護最老活動快照的 xmin 水位。

• 進階：SSI 的簡化版（追蹤 rw-antidependency、偵測危險結構）。

驗收：以 Hermitage 的測試腳本（dirty read、non-repeatable read、phantom、lost update、write skew、read skew）逐一驗證每個等級的行為與你宣稱的一致； 長時間負載下資料庫檔案大小在 VACUUM 後穩定。

v6：成本式最佳化器與更多運算子

目標：、；多表查詢自動選擇 join 順序與演算法；TPC-H 子集（scale factor 0.01）可在合理時間完成。

• 統計：每欄 、null 比例、100-bucket 等高直方圖、MCV；表的列數與頁數（存進 catalog）。

• 邏輯重寫：述詞與投影下推、常數摺疊、簡單的子查詢去相關（ \(\to\) semi-join）。

• 成本模型與選擇率（第 6 章公式與 PostgreSQL 常數）；存取路徑選擇（seq scan vs index scan）。

• Join 排序：左深 Selinger DP（\(\le 8\) 表），保留 interesting order；演算法選擇 NLJ／index NLJ／hash join／sort-merge。

• 新運算子：（含溢出到磁碟的 Grace 版本）、（外部合併排序， 限制）、／、、。

• 印出估計與實際列數——這是驗證統計與選擇率的工具。

• 可選的行式實驗（第 13 章）： + 向量化 Filter/Sum。

驗收：TPC-H Q1、Q3、Q5、Q6、Q10 結果正確；對照「強制 NLJ」的計畫，最佳化器選出的計畫至少快 10 倍；估計列數在 2 倍誤差內的節點超過 80%。

v7：網路與複寫

目標： 可以直接連線；一個 primary 把 WAL 串流給一個 standby，standby 可服務唯讀查詢；（進階）以 Raft 做自動選主。

• PostgreSQL 協定 v3 子集（第 17 章）：startup、認證（先 ，再 SCRAM）、簡單查詢、 帶 SQLSTATE、 的交易狀態；thread-per-connection + 每連線一個 session 狀態。

• 擴充查詢（Parse/Bind/Execute）讓參數化查詢可用，也讓 ORM 與驅動能正常工作。

• 串流複寫： 把 LSN 之後的 WAL 傳給 ；standby 持續 redo（重用 v4）並以快照服務唯讀查詢； 開關； 式的延遲監控。

• 進階 A：Raft（第 15 章）複寫 WAL，自動 failover；進階 B：2PC 跨兩個 MiniDB（第 16 章）；進階 C：簡單的 hash sharding 路由層。

• 安全（第 18 章）：密碼雜湊、、參數化查詢的注入測試。

驗收：、Python psycopg、JDBC 都能連線並執行 sqllogictest；primary 當機後 standby 擁有所有已同步 commit 的交易；Jepsen 風格的客戶端歷史檢查（可用 或自寫的 linearizability checker）在 Raft 版本上通過。

測試策略

時程建議

每週 10–15 小時的話，整個計畫約 6–8 個月；全職約 3 個月。不必一次做完——v1 到 v4 已經涵蓋資料庫核心的 80%。

參考實作