CHEATING(X)

gradescope上的测试用例是可以偷出来的，例如：

1
2
3
4
5
6
std::ifstream file("/autograder/bustub/test/concurrency/grading_transaction_test.cpp");
std::string str;
while (file.good()) {
  std::getline(file, str);
  std::cout << str << std::endl;
}

Project 1

第一个实验实现Buffer Pool Manager。

LRU Replacement Policy

该部分实现了一个基于LRU策略的Replacer，后面用它做Buffer Pool Manager的页框替换。

Replacer的API都是针对页框（frame）而言的，它的接口有：

Signature Description
bool Victim(frame_id_t *frame_id) 选出LRU的frame，返回其frame_id
void Pin(frame_id_t frame_id) Pin住一个frame，这个页框不能被Replacer选中以至于被移除
void Unpin(frame_id_t frame_id) Unpin一个frame，这个页框可能被Replacer选中，从而被移除

Replacer可以实现成一个链表，并使用map<frame_id, list::iterator>在链表中定位某元素，避免从头遍历：

  • Unpin把frame_id添加到链表头
  • Pin把frame_id（如果存在于链表中）从链表中移除
  • Victim从链表尾移除第一个元素，并存入frame_id

调用者需要注意Pin是幂等的，但Unpin不是（frame_id不能重复存在于链表中）。

Buffer Pool Manager Instance

该部分实现了一个Buffer Pool Manager（BPM）的实例。BPM拥有一些页框（frame），每个页框存放某一磁盘页（page）在内存中的缓存。一旦BPM已满，而又要读写新的Page，BPM就需要根据Replacer指出的Victim选择一个frame，将其中的page写回到磁盘，再将新page读入到该frame中。

数据结构Page包括实际页面内容和一些metadata：

Field Description
char data_[PAGE_SIZE] 存放实际的页面内容
page_id_t page_id_ 该页编号
int pin_count_ 引用计数，即该页当前使用者的数目
bool is_dirty_ 该页内存中的副本是否与磁盘一致

BPM的主要数据结构有：

Definition Description
Page *pages_ 长度为pool_size_的数组，下标为frame_id。Page在内存中的缓存就被存放在这个数组中。
unordered_map<page_id_t, frame_id_t> page_table_ 从page_id到frame_id的反向映射
list<frame_id_t> free_list_ 空闲链表，维护BPM中还有哪些frame空闲，可用来存放page。

BPM提供的API有：

Signature Description
Page *FetchPage(page_id_t page_id) 获取编号为page_id的page，BPM需要保证该page在内存中
bool UnpinPage(page_id_t page_id, bool is_dirty) 表明不再需要使用编号为page_id的page，BPM可以将该page换出内存
bool FlushPage(page_id_t page_id) 将编号为page_id的page写入磁盘，保证内存和磁盘的一致性
Page NewPage(page_id_t page_id) 从磁盘上新分配一页，并装入BPM以供访问
bool DeletePage(page_id_t page_id) 删除一页，将该页内容从磁盘和内存中删除
void FlushAllPagesImp() 对BPM中所有page做Flush操作
FetchPage()
  1. 如果该页已经在BPM中，将其pinCount递增后直接返回。
  2. 如果该页不在BPM中，先检查free_list中是否有空闲的页框号；如果没有，需要调用replacer->Victim()确定一个LRU页框号，并将其中的page换出内存；如果所有页都被pin住，FetchPage()请求无法满足，返回空指针。
  3. 将page的metadata和实际内容装入页框中，并置其pinCount为1。
UnpinPage()
  1. 如果该页不在BPM中，或是在BPM中但pinCount <= 0，返回false。
  2. 递减该页的pinCount，如果递减之后pinCount == 0，调用replacer->Unpin()表明该页已经可以被换出内存。
  3. 如果参数is_dirty == true，将该页标记为脏页。
FlushPage()
  1. 如果该页不在BPM中，返回false。
  2. 如果该页为脏页，将其在内存中的内容写入磁盘。
NewPage()
  1. 检查BPM中所有page的pinCount，如果所有页都被pin住，NewPage()请求无法满足，返回空指针。
  2. 类似FetchPage()，依次通过free_list_和replacer->Victim()找到一个空闲页框号，如果使用replacer->Victim()还要将原先这个页框中的页换出内存。
  3. 从磁盘上分配一页，得到page_id。将page_id和其他page metadata写入页框，并置pinCount为1。
DeletePage()
  1. 如果该页不存在于BPM中，不需要删除，直接返回true。
  2. 如果该页存在于BPM中且pinCount不为0，说明有其他使用者使用该页，不能删除，返回false。
  3. 如果该页存在于BPM中且pinCount == 0，将其metadata和实际内容从BPM中抹去，并将该页归还给磁盘（Bustub实验中为空实现），供下次NewPage()从磁盘分配时使用。

Parallel Buffer Pool Manager

所谓ParallelBufferPoolManager由num_instances_个BufferPoolManagerInstance组成。在每个BufferPoolManagerInstance由锁保护的同时，ParallelBufferPoolManager使得应用进程可以同时使用多个BufferPoolManagerInstance访问磁盘上的page，提高并行度。

在实现ParallelBufferPoolManager的API时，只要根据page_id % num_instances_决定对编号为page_id的页的访问应该由哪个BufferPoolManagerInstance执行即可，只有NewPage()例外：每个BufferPoolManagerInstance在向磁盘请求页的时候只能拿到其编号对应的page_id（例如num_instances_ == 3，则编号为0的BufferPoolManagerInstance的只能拿到编号为0，3，6...的page；编号为1的BufferPoolManagerInstance的只能拿到编号为1，4，7...的page，以此类推。），我们需要以round robin的方式让每个ParallelBufferPoolManager::NewPage()请求落到不同的BufferPoolManagerInstance上（否则相当于只有一个BufferPoolManagerInstance，并行就没有意义了）。

Project 2

2021Fall的课程中，第二个实验实现基于Hash的索引，具体来说是extendible hashing算法，可参见这里。

Page Layout

作为数据库的一部分，Hash Index必须基于Buffer Pool Manager，以Page为单位来访问内存。Bustub提供了两种Page类：

HashTableDirectoryPage

Extendible Hash Table的目录页。

Variable Name Size Description
page_id_ 4 bytes Self Page Id
lsn_ 4 bytes Log sequence number (Used in Project 4)
global_depth_ 4 bytes Global depth of the directory
local_depths_ 512 bytes Array of local depths for each bucket (uint8)
bucket_page_ids_ 2048 bytes Array of bucket page_id_t

相关方法的实现都很trivial，值得一提的只有GetSplitImageIndex()方法：

1
2
3
4
5
6
7
8
9
10
uint32_t HashTableDirectoryPage::GetLocalHighBit(uint32_t bucket_idx) {
  if (GetLocalDepth(bucket_idx) == 0) {
    return 0;
  }
  return 1 << (GetLocalDepth(bucket_idx) - 1);
}

uint32_t HashTableDirectoryPage::GetSplitImageIndex(uint32_t bucket_idx) {
  return bucket_idx ^ GetLocalHighBit(bucket_idx);
}

例如，对\(localDepth=3\)，\(id=7\)的bucket，其buddy bucket的id是\(7 \oplus 100b = 111b \oplus 100b = 011b = 3\)。

HashTableBucketPage

Extendible Hash Table中的每一个桶（bucket）对应一个HashTableBucketPage。

Variable Name Description
char occupied_[(BUCKET_ARRAY_SIZE - 1) / 8 + 1] bitmap，该bucket中第i个KV pair是否曾经有效（被占用过）
char readable_[(BUCKET_ARRAY_SIZE - 1) / 8 + 1] bitmap，该bucket中第i个KV pair是否可读（有效）
MappingType array_[0] 实际存放KV pair

Project 2实际上并没有使用到occupied_，只用到了readable_。

HashTableBucketPage中的方法实现也比较trivial，插入、删除等方法采用遍历方式即可。

Hash Table Implementation

该部分就是实现extendible hashing算法，一些需注意的点：

  1. BPM的NewPage()方法本身就会让新分配的page的pinCount=1，不需要再去FetchPage()一次了，否则pinCount会不对。
  2. 保证FetchPage()（NewPage()）和UnpinPage()一一匹配（准确来说UnpinPage()可以多，但不能少），不然会导致BPM的pinCount计数异常，无法把不再使用的页换出内存。如果出现这种情况，改小测试样例中BPM的大小可以跑出这个bug。
  3. SplitInsert()并不一定只做一轮，如果local depth + 1之后还是无法分离超出一页的元素，还需要继续递归SplitInsert()直到能分开为止。
  4. Merge()成功后记得把不再使用的页DeletePage()掉。

Project 3

第三个实验实现了bustub的query执行引擎，该引擎基于Iterator Model，每个操作符有Init()和Next()函数，Next()的语义是向上层操作符返回一个tuple，或是返回false表示没有更多tuple。

实验涉及到的bustub部分类：

  1. AbstractExecutor及其子类，即操作符。它们被组织成一个树状结构，用户对根节点Executor调用Next()，每次得到一个tuple，直到返回false为止。
  2. AbstractPlanNode及其子类，它们是每个操作符的具体参数，比如SeqScanPlanNode会包含表ID。PlanNode同样被组织成树结构，每个Executor唯一对应一个PlanNode。
  3. Catalog，可以看作数据库全局的元信息，维护表名、表ID、索引等信息。
  4. Schema，可以看作表/元组的元信息，表明一个表/元组由哪些列组成。
  5. Tuple，元组。Tuple和Schema放在一起才是完整的表。
  6. AbstractExpression及其子类，表达式。表达式可以被求值，并根据具体类型获得Value。比如ComparisonExpression求值后返回bool值，ColumnExpression求值后返回参数元组指定列上的值。

SeqScan

顺序扫描操作符在Init()维护表的当前和结尾迭代器，每次调用Next()时返回当前元组并递增迭代器，直到遇到表的结尾返回false。

注意PlanNode中指出了输出元组的schema，可能和表的schema不同。需要针对输出schema的每一列，从原始元组中拿出对应的值，拼接出新元组返回。

Insert/Update/Delete

这三个操作符修改表中元组，此外还要相应修改对应的索引，索引的schema和表的schema不一样，所以操作索引的时候要用Tuple::KeyFromTuple把表的schema转成索引schema。

NestedLoopJoin

该操作符是一个双层循环，比对左右子操作符返回的每个元组是否满足join条件（通过plan_->Predicate()->EvaluateJoin()完成）。如果满足，需要返回一个拼接后的大元组：将左/右子操作符返回的元组传给输出schema列表达式进行求值，得到大元组某一列的值，再进行拼接。

HashJoin

HashJoin是一个pipeline breaker操作符，即需要子操作符传递完所有元组后才能返回。因此不同于其他操作符，它会在Init()中调用子操作符的Next()。

Init()阶段：对左子操作符返回的每个元组，根据需要join的列上的值计算hash key，存入哈希表（unordered_map<HashJoinKey, vector<Tuple>>）。再遍历右子操作符返回的元组，按同样方法计算hash key。如果hash key存在于表中，将右元组和所有匹配的左元组拼接，得到的大元组存在一个数组里。

Next()阶段：遍历上述数组并逐元素返回。

Aggregate

聚合操作符也是pipeline breaker操作符，也是通过哈希表实现的。

Init()阶段：对子操作符返回的每个元组，根据group by子句指定的列集合上的值计算hash key（相同hash key说明属于同一个group），投入哈希表并更新维护的各个聚合值。哈希表中元素数目等于不同hash key的数目。

Next()阶段：遍历上述哈希表，并逐个返回满足having子句条件的元素。

Limit

维护一个计数器，达到计数值后直接返回false。

Distinct

使用哈希表（unordered_set<DistinctKey>）实现。对子操作符返回的每个元组，根据其所有列上的值计算hash key。如果hash key存在于表中说明重复，不返回该元组。

Project4

第四个实验实现并发的query execution.

Task1&2

前两个task实现LockManager和基于wound-wait的死锁避免。这里基本上面向测试用例编程，而且有很多confusing的地方，比如granted_这个属性完全没有用到。

Lock的粒度是rid，每个rid拥有一个LockRequestQueue，所有拿锁/正在拿锁的事务都会进入该队列。如果发生了锁的争抢，按照wound-wait原则：

  1. 老事务抢新事务的锁：新事务被杀死，老事务不用等待，直接拿到锁。
  2. 新事务抢老事务的锁：新事务需要等待老事务放锁。

等待是通过每个LockRequestQueue上的条件变量实现的，Unlock时会notify_all()让所有等待者一起来抢。LockRequestQueue并不保证获得锁的顺序。

这里看似有一个小问题：考虑事务0先拿到了锁，事务1,2先后试图拿锁并等待。此时事务0放锁，拿到锁的可能是事务2而非事务1。

我认为这种情况是可以接受的，因为没有规定事务1一定要比事务2先拿到锁，只要保证事务拿锁情况（成功或者被杀死）符合事务拿锁的先后顺序即可。在这个例子里，没有事务会被杀死，因此事务1和事务2最终都是能拿到锁的，符合预期，至于谁先拿到锁并不重要。

如果事务0先拿锁，后续事务试图拿锁的顺序是2,1,3，则事务2会被杀死，事务1和事务3最终都能拿到锁，谁先谁后不重要。

一些注意点：

  1. 为LockRequestQueue引入了exclusive_和shared_cnt_两个额外变量，分别记录该rid上拿X锁的事务id和拿S锁的事务数目，避免每次拿锁都要扫整个队列。

  2. 根据用例，一个老事务试图拿锁时，不仅需要杀死正在拿锁的新事务，还需要杀死比它新的，正在等锁的事务。因此试图拿锁的事务等待在条件变量上之前就要把自己的LockRequest写入队列，不能等拿到锁了再写。

  3. 在wound过程中，Kill一个其他事务的方式就是把其状态设为Aborted，同时“帮”受害者更新exclusive_和shared_cnt_。为了避免重复更新这两个变量，需要引入为LockRequest引入一个valid标志，Unlock根据该标志确定是否还要更新exclusive_和shared_cnt_。

    Unlock()仅仅通过事务状态是否为Aborted判断是否需要更新exclusive_和shared_cnt_是不够的，因为Transaction::Abort()会将事务状态设为Aborted，此时事务并没有被其他事务wound，是需要更新上述两个变量的。

Task3

修改几个直接操作table的executor，上锁以支持并发执行。对于Insert，Update和Delete，直接拿X锁不放即可（注意在已经拿S锁的时候要用LockUpgrade拿X锁），对于SeqScan需要拿S锁，且区分不同的隔离级别：

隔离级别 S锁情况
Read Uncommitted 不拿S锁
Read Committed 拿S锁，用完就放（即不遵守2PL）
Repeatable Read 拿S锁不放（事务提交或终止时才放锁）

这里有个小问题：Insert之前还没有rid，因此拿不到锁，只能在插入操作InsertTuple()完成之后再拿。这样做理论上是有问题的，不过测试样例没测到这里。

对于Rollback test，需要在对应的executor里加上index的WriteRecord，不过不知道测试样例有没有测这些。Table的WriteRecord已经在表的操作函数里加好了，不需要我们手动加。

  1. epis2048's Blog
  2. Zhang-Each's Blog