Mit6.830 – simpledb – 總覽
- 2021 年 12 月 17 日
- 筆記
- mit6.830 - 題解
總覽
github 地址: //github.com/CreatorsStack/CreatorDB
在開始 simpledb 旅途之前, 我們先從整體上來看看
SimpleDb 是一個 DBMS 資料庫管理系統, 包含存儲, 運算元, 優化, 事務, 索引 等, 全方位介紹了如何從0實現一個 DBMS, 可以說, 這門課是學習 TIDB 等其他分散式資料庫的前提.
項目文檔:
lab1 – Storage
lab1 主要涉及存儲 — 也即和各種 file, page, bufferPool 等打交道
- TupleDesc: td 描述了一個表每一列的元數據, 也即每個列的類型等等
- Tuple: 代表了一行的數據
- Page: 代表一個表的某個 page, page 由 header 和 body 組成, header 是一個 bitmap, 記錄了body 中哪個位置是存在數據的. body 中存儲了一個個 Tuple
- DbFile: SimpleDb 中, 一個 Table 用一個 file 進行存儲, 每個 file 包含了若干個 page
- BufferPool: SimpleDb 的快取組件, 可以搭配 Lru 快取, 效果更佳. 是整個系統最核心的組件, 任何地方訪問一個 page 都需要通過 bufferPool.getPage() 方法
- CataLog: SimpleDb 等全局目錄, 包含了tableid 和 table 的映射關係等
lab2 – Operators & Volcano
lab2 主要涉及運算元的開發: 也即各種 Operator, 如 seqScan, join, aggregation 等
需要注意的是, SimpleDb 採用了的 process model 是 volcano model, 每個運算元都實現了相同的介面 — OpIterator
- SeqScan: 順序掃描表的運算元, 需要做一些快取
- Join + JoinPredicate: join 運算元, 可以自己實現 簡單的 nestedLoopJoin, 或者 sortMergeJoin
- Filter + Predicate: filter 運算元, 主要用於 where 後面的條件判斷
- Aggregate: aggregation 運算元, 主要用於 sum() 等聚合函數
- Insert / Delete: 插入/刪除運算元
關於 Volcano model, 舉個例子, 在 lab2 中會更詳細的介紹
lab3 — Query Optimization
這個實驗主要介紹了如何簡單的進行數據估算和 join 優化
- 利用直方圖進行謂詞預估統計
- 利用 left-deep-tree 和動態規劃演算法進行 Join Optimizer
- 程式碼量較少
流程圖如下:
lab4 — Transaction
實驗四要求我們實現基於 2pl 協議的事務, 先來說一下在 simpleDB 中是如何實現事務的:
在SimpleDB中，每個事務都會有一個Transaction對象，我們用TransactionId來唯一標識一個事務，TransactionId在Transaction對象創建時自動獲取。事務開始前，會創建一個Transaction對象，trasactionId 會被傳入到 sql 執行樹的每一個 operator 運算元中，加鎖時根據加鎖頁面、鎖的類型、加鎖的事務id去進行加鎖。
比如, 底層的 A, B seqScan 運算元, 就會給對應的 page 加讀鎖.
我們知道, page 是通過 bufferPool.getPage() 來統一獲取的, 因此, 加鎖的邏輯就在 bufferPool.getPage() 中
具體的方法就是實現一個 lockManager, lockManager 包含每個 page 和其持有其鎖的事務的隊列
當事務完成時，調用transactionComplete去完成最後的處理。transactionComplete會根據成功還是失敗去分別處理，如果成功，會將事務id對應的臟頁寫到磁碟中，如果失敗，會將事務id對應的臟頁淘汰出bufferpool並從磁碟中獲取原來的數據頁。臟頁處理完成後，會釋放事務id在所有數據頁中加的鎖。
- 需要實現一個 LockManager, 跟蹤每一個 transaction 持有的鎖, 並進行鎖管理.
- 需要實現 LifeTime lock, 也即有限等待策略
- 需要實現 DeadLock detect, 可以採用超時等待, 也可以通過依賴圖進行檢查
lab5 — B+ tree
lab5主要是實現B+樹索引，主要有查詢、插入、刪除等功能
- 查詢主要根據B+樹的特性去遞歸查找即可
- 插入要考慮節點的分裂（節點tuples滿的時候）
- 刪除要考慮節點內元素的重新分配（當一個頁面比較空，相鄰頁面比較滿的時候），兄弟節點的合併（當相鄰兩個頁面的元素都比較空的時候）
lab6 — log & rollback & recover
lab6 主要是實現一個 redo log & undo log 日誌系統, 使得 simpledb 支援日誌回滾和崩潰恢復
總結
總的來說, 實驗難度不大, 但是可以讓我們快速入門資料庫領域, 可以說是頂級的資料庫課程了.
