SImpleDB 包含:
- Classes that represent fields, tuples, and tuple schemas;
- A catalog that stores information about available tables and their schemas.
- One or more access methods (e.g., heap files) that store relations on disk and provide a way to iterate through tuples of those relations;
- A buffer pool that caches active tuples and pages in memory and handles concurrency control and transactions
- Classes that apply predicates and conditions to tuples;
- A collection of operator classes (e.g., select, join, insert, delete, etc.) that process tuples;
不包括
- Views.
- Data types except integers and fixed length strings.
- Indices.
- DDL
儲(chǔ)存
Catalog 儲(chǔ)存了所有表的信息晶框。每個(gè)表的信息包括：name份氧，schema，相應(yīng)的 DbFile鹃栽，以及 primary key。
SImpleDB 只支持兩種 field，Interger 和 fixed length string。
每個(gè)表的 schema 用 TupleDesc 定義后控，其儲(chǔ)存每個(gè) filed 的 type 和 name。其除了支持用 index (offset) 獲得 field 的 type 或 name空镜，用 name 獲得 field 的 index浩淘，還提供一個(gè)靜態(tài)方法用于 merge 兩個(gè) TupleDesc 獲得一個(gè)新的 TupleDesc （Join operator 使用）
tuple 用來儲(chǔ)存 field，其除了提供第 i 個(gè) field 的 getter/setter吴攒，還提供了所有 field 的 iterator张抄。
tuple 有一個(gè) record id 標(biāo)志其在磁盤中的位置。
HeapPage 實(shí)現(xiàn)了 Page 接口洼怔。用一個(gè) PageId 唯一標(biāo)志署惯，用來儲(chǔ)存 tuples，其用一個(gè) byte[] header 作為bitmap镣隶。
其支持在該 page 上插入/刪除 tuple极谊，標(biāo)志該 page 為 dirty什荣。還提供了迭代器用來迭代 page 中所有的tuple。
其支持將 page 實(shí)例序列化為 byte[] 和由 byte[] 構(gòu)建 page 實(shí)例怀酷。
HeapFile 實(shí)現(xiàn)了 DbFile 的接口，其提供唯一的 ID嗜闻，以及獲得文件系統(tǒng) File蜕依，table schema 的 API。
其支持從從磁盤獲取數(shù)據(jù)(byte []), 并構(gòu)建相應(yīng) page 實(shí)例琉雳。和將 page 序列化到磁盤样眠。
buffer pool 存放了當(dāng)前所有的 page 實(shí)例，如果已滿翠肘，則會(huì)剔除某個(gè)page(如果 page 為 dirty檐束，則 flush 到磁盤)。
所有對(duì)數(shù)據(jù)(都是以 page束倍，也就是構(gòu)建 HeapPage 實(shí)例)的訪問都要經(jīng)由 buffer pool （調(diào)用 getPage API）
這里必須要理清：
數(shù)據(jù)是儲(chǔ)存在磁盤中的（支持序列化）被丧，當(dāng)需要訪問時(shí)，都會(huì)通過 bufferpool 獲得绪妹。后者調(diào)用相應(yīng)的 HeapFile 從磁盤中獲得數(shù)據(jù)并生成 HeapPage 實(shí)例放入 bufferpool甥桂。
當(dāng) bufferpool 已滿，會(huì) kick out 一個(gè)page邮旷，如果那個(gè) page 是 dirty 的黄选，會(huì)先 flush 到磁盤（通過調(diào)用 HeapFile 的 writePage API）。
Operator
Operator 就是迭代器的連接婶肩，其實(shí)現(xiàn) DbIterator 接口办陷，其接受 child DbIterator。
SimpleDB 實(shí)現(xiàn)了 SeqScan律歼，project, filter, join, aggregate, order_by民镜。
除了 SeqScan，其他都由子 DbIterator 獲得 tuples苗膝。
SeqScan 由 DbFileIterator (所有 DbFile 都要實(shí)現(xiàn)殃恒，用于獲得 file 的所有數(shù)據(jù)) 獲得 tuples
Transaction
Lab3 是實(shí)現(xiàn) Transaction 功能
代碼的變動(dòng)不大，只要在 BufferPool read page 時(shí)添加獲得鎖的代碼就行辱揭。
這是因?yàn)?SimpleDB 設(shè)計(jì)上所有對(duì)磁盤文件的獲取都要經(jīng)由 BufferPool离唐。
所以 BufferPool 特別適合用來獲得鎖保證線程同步。
OS 中針對(duì) IO 慢的問題也有類似的 Block Cache问窃，其往往也是在這里實(shí)現(xiàn)同步亥鬓。
關(guān)鍵是如何以正確的姿勢(shì)獲得鎖和釋放鎖。
我這里添加了個(gè) LockManager 類專門用來管理鎖域庇。
如果對(duì)性能要求不高嵌戈，可以對(duì)獲得鎖的方法(accquireLock)專門上個(gè)鎖覆积，保證一個(gè)時(shí)間所有事務(wù)只有一個(gè)能使用該方法獲得鎖。
但這里我是保證要求同一個(gè)page 的多個(gè)事務(wù)只有一個(gè)能調(diào)用方法（通過 Java 中 synchronized (Object)）熟呛。
這里我犯了一個(gè)錯(cuò)誤宽档，我誤認(rèn)為所有 PageId 對(duì)象都是相同的，就用 synchronized (pid) 來保證同步化庵朝，但實(shí)際上每次訪問 page 時(shí)會(huì)生成一個(gè)新的 PageId 對(duì)象吗冤，他們相等但不相同 (定義了 equals 和 hashcode 保證相等，但他們是不同對(duì)象)九府，所以使用 synchronized (pid) 并沒有起到同步化的作用椎瘟。正確的姿勢(shì)是用一個(gè)Map，Map相等的 PageId 到同一個(gè)對(duì)象侄旬。
死鎖檢測(cè)沒有什么好說的肺蔚，就是檢測(cè) wait-lock-graph 有沒有環(huán)的問題。
在 lab3 時(shí)儡羔，并沒有使用 log 進(jìn)行 recovery
其使用 NO-STEAL/FORCE
- You shouldn't evict dirty (updated) pages from the buffer pool if they are locked by an uncommitted transaction (this is NO STEAL).
- On transaction commit, you should force dirty pages to disk (e.g., write the pages out) (this is FORCE).
- 假設(shè)數(shù)據(jù)庫在執(zhí)行 transactionComplete 命令時(shí)不會(huì)崩潰宣羊，
以上三點(diǎn)使得不需要 log-based recovery，因?yàn)?you will never need to undo any work (you never evict dirty pages) and you will never need to redo any work (you force updates on commit and will not crash during commit processing).
