minisql 个人报告

成员: 杨悦然 (单人完成)

学号: 3230102221

1 DISK AND BUFFER POOL MANAGER

Disk Manager 和 Buffer Pool Manager 模块位于架构的最底层, Disk Manager 负责数据库文件中数据页的分配和回收，以及数据页中数据的读取和写入, Buffer Pool Manager 负责将磁盘中的数据页读到内存中, 进行操作并写回

1.1 Bitmap

数据页的分配和回收通过 Bitmap 这一数据结构实现，位图中每一位对应一个数据页的分配情况，用于标记该数据页是否空闲, 0 为空闲, 1 为已分配

在 AllocatePage() 中维护一个 next_free_page_, 每次从 next_free_page_ + 1 开始调用 IsPageFree() 找到第一个空闲的页, 并将 bitmap 对应的位置为 1, 计数器加一
同时在 DeAllocatePage() 回收已经被分配的页, 将对应的 bitmap 置为 0, 计数器减一

同时如果释放的 page_offset < next_free_page_, 需要将 next_free_page_ 回退

1.2 Disk Manager

一个位图页加一段连续的数据页看成数据库文件中的一个分区 (Extent), 再通过一个额外的元信息页来记录这些分区的信息

Disk Meta Page 是数据库文件中的第 0 个数据页
在 AllocatePage() 中, 从磁盘中分配一个空闲页, 并返回空闲页的逻辑页号, 并用 DeAllocatePage() 释放磁盘中逻辑页号对应的物理页

同时这样的嵌套设计会使得数据页的物理页号不连续, 中间隔着位图页

所以在 MapPageId() 中对页号做一个映射, 将物理页号映射成连续的逻辑页号

1.3 LRU and Clock Replacer [Bonus]

在 LRU 替换中使用一个 lru_list_ 来维护一个访问顺序队列, 每次访问一个页就将这个页放在队列最前面

替换时替换掉队列最后面的页

同时 Pin 时将页从队列中删除
在 Clock 替换中对每个页维护一个状态, 初始为 1, 同时维护一个指针指向某一个页, 每次在队列中迭代并将状态从 1 变 0, 直到找到一个状态为 0 的页, 就将这个页替换掉

1.4 Buffer Pool Manager

维护一个空闲列表 free_list

在 NewPage() 时先从 free_list 中找一个空闲的页, 如果没有空闲, 使用 LRU 或 Clock 替换掉一个页

然后写回并刷空这个页, 把第 page_id 的页加入内存的 frame_id

同时维护一个 page_table 将 page_id 映射到 frame_id
在 FetchPage() 时尝试找到对应的页, 把它 Pin() 掉, pin_count++ 并返回

如果没找到就 NewPage() 一个
在 DeletePage() 时使用 FlushPage() 将页写回, 并调用 Disk Manager 释放掉这个页
在 UnpinPage() 时判断参数中是否页为脏, 如果脏并且 --pin_count == 0, 需要使用 FlushPage() 写回

2 RECORD MANAGER

2.1 Field, Row, Column and Schema

在 Row 中需要维护 RowId, 以及 Field 的个数, 并使用 null_bitmap 来标记哪一位置的 Field 为空, 最后使用 Field::SerializeTo() 和 Field::DeserializeFrom() 来完成序列化 / 反序列化
在 Column 中需要序列化 COLUMN_MAGIC_NUM 来保证正确性
在 Schema 中维护 SCHEMA_MAGIC_NUM 来保证正确性, 同时维护 Column 的个数, 使用 Column::SerializeTo() 和 Column::DeserializeFrom()

2.2 Table Heap

每一页中前面维护 Meta 信息, 从后向前存储记录, 并维护一个 FreeSapcePointer 来存储记录
对于所有页维护一个链表结构

每次 InsertTuple() 时从链表头开始遍历每一个页, 调用 TablePage::InsertTuple() 来尝试插入一条记录, 如果成功了就将记录插入, 并将 FreeSapcePointer 移动到新记录位置

如果失败说明这个页满了, 就便历链表其他页

直到最后没有页空闲, 就分配一个新页, 加在链表最后, 新记录插在这个页
在 UpdateTuple() 时使用 TablePage::UpdateTuple() 尝试直接更改

如果更改失败, 说明记录太大这页装不下, 就用 MarkDelete() 把旧记录删除, 按照 InsertTuple() 相同方式插入新记录
在 ApplyDelete(), RollbackDelete(), MarkDelete(), GetTuple() 中分别调用 TablePage 对应方法

2.3 Table Iterator

每次在 TableHeap 第一页中调用 TablePage::GetFirstTupleRid() 来得到第一个记录的位置 Begin(), 之后在同一页中遍历记录, 遍历完后链表跳到下一页继续重复这个步骤, 直到链表遍历完返回 End() 为 Invalid

3 INDEX MANAGER

3.1 Leaf Page / Internal Page

在 BPlusTreePage 的基础上派生两个类 BPlusTreeLeafPage 和 BPlusTreeInternalPage

在两个页中使用 Insert() 插入索引, 将后一部分索引向后移动一位, 将新索引插到空出来的位置
每个页中的索引按照 <key, value> 对存储

对于 LeafPage 的 value 存储 RowId, 对于 InternalPage 存储 page_id

其中 InternalPage 的第一个 key 为空

3.2 B+ Tree

在 Insert() 时先新建一个 LeafPage, 如果这一页插入满了, 就分裂成两个各包含一半索引的 LeafPage 并新建一个 InternalPage 指向这两个页, 在 InternalPage 中新加一条索引指向后一个 LeafPage
在 Remove() 时对于一个页如果删空了, 有三种处理方式: 借左兄弟, 借右兄弟, 合并

如果左 / 右兄弟有余量, 就向左右兄弟借一个索引

如果左右兄弟都没余量, 就和任意一个兄弟结合
由于删除的可能是一个 LeafPage 的第一个索引, 可能导致上面的某个 InternalPage 的索引个数减少

所以需要一个 ChangeParent() 函数从下到上判断是否有被删除的 key

如果有就将其替换成新的 key

如果 LeafPage 没有删空, 就有一个 new_key 可以替换

如果页容量较小 (= 3), LeafPage 被删空, 那就用 null 替换旧的 key

例如, 如果此时的页是 LeafPage, 需要借右兄弟, 就需要先将 LeafPage 中的索引删除, 调用 ChangeParent() 将上面祖先的索引删除, 如果需要的话

然后从右兄弟借来的第一对 <key, value> 插入这一页的最后位置

所以从右兄弟上调用 ChangeParent() 更改祖先

最后如果上面自己将祖先索引删除并替换成了 null, 需要再次用从右兄弟借来的 key 替换 null

如果是 InternalPage 借右兄弟, 同样可能删除第一个索引, 调用 ChangeParent()

然后从父亲拿下来对应的 key, 与从右兄弟借来的 value 一起作为键值对插入这一页的最后位置, 调用右兄弟的 ChangeParent()

即右兄弟的第一个 value 给这一页, 第二个 key 送给父亲, 保证新的右兄弟的第一个 key 位置为空

这样的 ChangeParent() 函数不会让复杂度变差, 因为只有叶子节点会调用 ChangeParent() 函数, 并且如上面情况, 最多调用 3 次 ChangeParent()

3.3 B+ Tree Iterator

每一次从最左的 LeafPage 的第一个索引开始遍历, 遍历完一个页就跳到右兄弟, 直到最底层的节点都遍历完, 返回 End() 为 Invalid

4 CATALOG MANAGER

4.1 Meta

在 Catalog Manager Meta 中保存所有的 Table Meta 和 Index Meta
同时需要 CATALOG_MAGIC_NUM 保证序列化的正确性

4.2 Catalog Manager

在 Catalog Manager() 初始化时创建一个新页存储 Meta, 清空所有的 Index Meta 和 Table Meta

如果不需要初始化, 则遍历整个 Catalog Meta, 得到所有的 Index Meta 和 Table Meta 信息, 重新构建 index_names_ 和 table_names_ 两个映射
在 ~CatalogManager() 时, 需要将每个表和每个索引写回, 将 Catalog Meta 写回, 释放内存
在 CreateTable() 时需要深拷贝 Schema, 并创建一个 Table Heap
在 CreateIndex() 时, 需要先判断这个表是否存在, 在判断表中的索引是否已经存在, 之后创建一个新的 B+ Tree, 并且将表中的所有数据加入索引中
在 DropTable() 时, 需要将表以及其对应的所有索引的 Meta 页全部删除
在 DropIndex() 时需要将索引对应的 Meta 页删除, 并释放内存

5 PLANNER AND EXECUTOR

5.1 Execute Engine

ExecuteCreateTable() 时, 需要遍历语法树的 ast->child_->next_->child_, 此为 Column 定义树

遍历每个节点时获得其数据类型, 名字以及是否为 unique

在树的最后获取 primary keys

对于 primary keys 和 unique, 需要他们创建索引, 其中 primary 索引名字为 PRIMARY, unique 名字为 column 名字
ExecuteDropTable() 时调用 Catalog Manager 的 DropTable()
ExecuteCreateIndex() 时同样对 ast->child_->next_->child_进行扫描, 得到要创建索引的 Column
ExecuteDropIndex() 需要在每个表中遍历, 找到一个对应的索引并调用 Catalog Manager 的 DropIndex() 删除索引
ExecuteExecfile() 中使用与 main.cpp 相同的读入方式, 只是将 std::istream 换成 std::ifstream 即可, 随后对读入的每个指令依次执行

6 RECOVERY MANAGER

6.1 Log

对于 LogRec 的创建 Log 函数, 需要先表明操作的类型, 之后查找 txn_id 号事务之前的 lsn_id 是多少

如果 prev_lsn_map_[txn_id] 是空, 说明这个操作是事务的第一个操作, 则 prev_lsn_ = INVALID_LSN

不然有 prev_lsn_ = prev_lsn_map_[txn_id], 在 Undo 阶段需要靠这个链表结构回滚

之后维护这个操作更改的 key, old_val, new_val

6.2 Check Point

对于一个 CheckPoint, 里面保存了最后一个 lsn_id, 以及当时对应的所有数据和活跃的事务

6.3 Redo Phase

从 CheckPoint 的最后一个 lsn_id 开始, 遍历所有日志中的操作, 对 CheckPoint::persist_data_ 进行更改, 恢复数据库到最新状态
对于 insert, delete, update, 直接维护数据即可
对于 begin, 在 CheckPoint::active_txns_ 中加入新事务
对于 commit, abort, 在 CheckPoint::active_txns_ 中删除事务

同时 abort 需要将从这条 Log 开始向前回滚到 begin 位置

6.4 Undo Phase

对于 CheckPoint::active_txns_ 中的所有事务, 根据链表结构向前回滚至 begin 位置, 将其从活跃事务中删除

6.5 思考题

如果要将 Recovery Manager 整合进系统中, 需要在更改时对于内存中的页进行更改, 并在 Commit 时进行数据页的落盘

同时 Check Point 可以参照 Aries 算法, 维护脏页表 DPT 与活跃事务表 ATT, 在创建 Check Point 时将这些写入日志中
即, 加入一个 Analysis 阶段, 从 Master Record 中获取最近的检查点起始 LSN

扫描检查点起始 LSN 之后的所有日志记录, 重建崩溃时的 DPT 和 ATT

确定需要重做的最小 LSN (Redo LSN) 和需要撤销的事务列表
对于 Redo 阶段, 从 DPT 中最小的 RecLSN 开始, 顺序重做所有已提交事务的修改操作

通过日志中的事务状态 (如 COMMIT 或 ABORT) 判断哪些操作需要提交或回滚
对于逆序处理未提交事务的操作 (Undo), 从 ATT 中最大 LastLSN 开始, 回滚所有未提交事务的修改

通过日志中的 PrevLSN 链式结构定位事务的修改历史

7 LOCK MANAGER [Bonus]

7.1 Lock Manager

对于 LockShared(), 先判断是否为 ReadUncommited 级别或是否处于 Shrinking 阶段, 如果满足则加锁失败

之后设置阶段为 Growing

同时对于要加锁的数据 rid 上的等待队列加入这条请求, 并让这个线程等待这个等待队列的 cv_:
```
req_queue.cv_.wait(lock, [&req_queue, txn]() {
    return (!req_queue.is_writing_ && !req_queue.is_upgrading_) || txn->GetState() == TxnState::kAborted;
});
```
即只有当这个线程被 Abort, 或者等待队列中没有需要写或升级的请求, 才能加锁

此时给这条枷锁记录 lock_req.granted_ = LockMode::kShared, 并给这个事务加上一个共享锁 txn->GetSharedLockSet().emplace(rid), 并给等待队列的 req_queue.sharing_cnt_++

并且如果上面是因为 Abort 使得 cv_ 被唤醒, 则需要抛出死锁异常, 说明被死锁检测程序解开了
对于 LockExclusive(), 同样判断是否处于 Shrinking 阶段

同样对于要加锁的数据 rid 上的等待队列加入这条请求, 并让这个线程等待这个等待队列的 cv_

并且需要多等待一个条件 req_queue.sharing_cnt_ == 0, 即排它锁与共享锁是互斥的

唤醒后给这条枷锁记录给等待队列的 req_queue.is_writing_ = true, 其他与共享锁相同
对于 LockUpgrade(), 同样判断是否处于 Shrinking 阶段

同时如果等待队列正在升级另一个锁, 则这个锁升级失败

在等待时条件改为 return (!req_queue.is_writing_ && req_queue.sharing_cnt_ <= 1) || txn->GetState() == TxnState::kAborted

即在 rid 上必须只有自己一个共享锁, 才能升级为排它锁

同时如果一个 rid 上的两个事务的共享锁中有一个需要升级, 则需要等待另一个事务的锁释放

而另一个事务有在等待这个事务的另一个锁释放, 就会死锁

所以如果这个事务被 Abort, 需要抛出死锁异常, 特判为升级失败
对于 Unlock(), 需要判断是否阶段为 Growing, 将阶段改为 Shrinking

对于对应的等待队列, 将 sharing_cnt_-- 或 is_writing_ = false, 之后 cv.notify_all() 来唤醒其他线程继续加锁

7.2 Dead Lock Detection

在 AddEdge(), RemoveEdge() 中向 waits_for_ 中加入一个元组 <t1, t2> 表示从 t1 到 t2 的一条边, 不允许重边
在 HasCycle() 中, 从 waits_for_ 中获取所有节点

之后从每个点开始 dfs, 同时维护 visited_set_, visited_path_ 来判断是否搜索到了走过的点, 如果搜到的点之前走过, 说明存在环, 就将最新的节点返回作为要解开的节点
在 RunCycleDetection() 中, 对于每个资源 RowId, 将等待队列中 granted_ == LockMode::kNone 的事务向 granted_ != LockMode::kNone 的事务连边, 表示一个等待关系

在 RunCycleDetection() 每次循环时即时构建这个等待图

之后使用 HasCycle() 判断所有的环并一一解开, 将环中的某个事务 Abort 并唤醒其他在等待的事务

7.3 思考题

对于 B+ 树来说, 不同的隔离级别对应了不同的锁粒度
Read Uncommitted 允许脏读, 不可重复读, 幻读, 所以在修改数据时加排他锁直至事务结束, 读操作无需加锁, 直接读取最新数据
Read Committed 避免脏读, 但允许不可重复读和幻读, 所以在修改数据时加排他锁直至事务结束; 读操作需要加共享锁, 读取后立即释放锁
Repeatable Read 避免脏读和不可重复读, 但允许幻读

所以写操作加排他锁, 直到事务提交时释放

对于读操作加共享锁, 直到事务提交时释放
Serializable 完全避免脏读, 不可重复读和幻读, 所以对于所有读写操作加表级锁, 强制事务串行执行

对于 B+ Tree 操作, 对整个 B+ Tree 加锁, 禁止其他事务并发访问

或者加入范围锁, 锁定 B+ Tree 查询索引之间的索引, 防止插入新数据