CMU15-445的作业断断续续做了差不多将近两个月，博客也鸽了有好一段时间了。现在来攒波大的，把所有的project的笔记和总结一口气全写完。关于作业环境的配置可以参考下之前写的如何使用VSCode配置和调试bustub的文章

课程网址:https://15445.courses.cs.cmu.edu/fall2021

头图来源:雷鳴-mocha@新刊委託中-pixiv

Content

• PROJECT 1 - BUFFER POOL

  • 1.LRU Replacement Policy
  • 2.Buffer Pool Manager Instance
  • 3.PARALLEL BUFFER POOL MANAGER

• PROJECT 2 - EXTENDIBLE HASH INDEX

  • 1.PAGE LAYOUTS
  • 2.HASH TABLE IMPLEMENTATION
  • 3.CONCURRENCY CONTROL

• PROJECT 3 - QUERY EXECUTION

  • 1.SEQUENTIAL SCAN
  • 2.Hash Join

• PROJECT 4 - CONCURRENCY CONTROL

  • 1.LOCK MANAGER
  • 2.CONCURRENT QUERY EXECUTION

PROJECT 1 - BUFFER POOL (EASY)

这部分需要实现一个缓冲池用于管理内存，至于为什么不让操作系统来帮我们管理内存，DBMS有个原则就是：尽可能地掌握资源的控制权而不是交给操作系统管理（很多时候操作系统并不能像我们期望地那样去工作）

1.LRU Replacement Policy

Replacer决定将哪些当前没有用到的页写回磁盘，因此当页的pin_count为零时需要将页放入replacer中，而当replacer满时需要通过所采用的页置换算法将页写回磁盘以添加新页。缓冲池的页置换策略为LRU（最近最少使用）。关于LRU的实现网上有许多资料，我这里则是以双向链表来实现。这部分没什么可以说的，关于需要实现的接口以及它们的作用作业页面也给出了解释，照着实现即可。

2.Buffer Pool Manager Instance

这部分是proj1的重点，具体逻辑照着课程ppt实现即可。

Attention

• NewPgImp(page_id)中需要将pin_count设置为1。
• UnpinPgImp(page_id, is_dirty)中只有当is_dirty == true时才更新page中的is_dirty，且当页的pin_count为零时需要调用replacer_->Unpin()将页加入到replacer中。

3.PARALLEL BUFFER POOL MANAGER

这部分是2021新加入的内容，仅仅需要在实现了GetBufferPoolManager(page_id_t page_id)之后用相应的buffer pool manager调用对应的方法即可。注意这里需要使用static_cast对GetBufferPoolManager(page_id_t page_id)的返回值向下转型（BufferPoolManager->BufferPoolManagerInstance）。

PROJECT 2 - EXTENDIBLE HASH INDEX (HARD)

实现一个可扩展哈希索引，虽然没有像之前课程要求实现B+树索引，但这部分的代码实现还是比较复杂的，有挺多细节。

1.PAGE LAYOUTS

需要实现哈希表的导航页和桶页，作业页面对各字段的含义和用处作出了解释，参照着实现即可。

2.HASH TABLE IMPLEMENTATION

关于可扩展哈希的概念和实现可以参考一下资料：

• https://en.wikipedia.org/wiki/Extendible_hashing
• https://www.geeksforgeeks.org/extendible-hashing-dynamic-approach-to-dbms/

3.CONCURRENCY CONTROL

这部分有些细节要注意，注意不应在要加共享锁的地方加互斥锁，不然很容易超时。

Attention

可扩展哈希表的并发需要控制两种锁（Page持有的rwlatch和哈希表持有的table_latch），我们需要弄清楚它们分别所保护的共享资源。

• rwlatch:如果操作只是对页进行读取，则只需加共享锁；否则，应加互斥锁。
• table_latch:如果操作会造成导航页的修改（因insert()可能引发的split()或因remove()可能引发的merge()）,则需要加互斥锁；其余情况，加共享锁即可。

ps:第一名跑0.04s的是什么神仙……

PROJECT 3 - QUERY EXECUTION (MEDIUM)

这部分要实现的比较多，但总体难度适中，且其中很多接口已经帮我们写好了，很多时候我们只需要实现Init()和Next()即可。需要注意的是查询操作每调用一次Next()返回一个tuple，直到Next()为false；而insert,update和delete操作不返回tuple。
下面就挑一些比较复杂和一些需要注意的点分别叙述下。

1.SEQUENTIAL SCAN

返回符合条件的tuple即可，但要注意返回的tuple其schema要符合plan中的output schema。

/* 将tuple从原schema转成输出schema。 */
std::vector<Value> values;
values.reserve(plan_->OutputSchema()->GetColumnCount());
for (const auto &column : plan_->OutputSchema()->GetColumns()) {
   values.emplace_back(column.GetExpr()->Evaluate(&cur_tuple, &table_info_->schema_));
}
*tuple = Tuple(std::move(values), plan_->OutputSchema());

2.Hash Join

与Nest Loop Join不同的是Hash Join通过构建outer table的哈希表来降低IO Cost(O(M+m*N)->O(M+N))，gradescope会对IO Cost进行测试，并假设内存足够能装进整个哈希表。
我的做法是在Init()里进行建表，然后Next()进行probe。

PROJECT 4 - CONCURRENCY CONTROL (HARD)

这部分需要实现行锁（lock），这和线程并发控制所用的锁（latch）有所不同，它们的区别如下图

1.LOCK MANAGER

可参考

• LockShared(Transaction, RID): Transaction txn tries to take a shared lock on record id rid. This should be blocked on waiting and should return true when granted. Return false if transaction is rolled back (aborts).
• LockExclusive(Transaction, RID): Transaction txn tries to take an exclusive lock on record id rid. This should be blocked on waiting and should return true when granted. Return false if transaction is rolled back (aborts).
• LockUpgrade(Transaction, RID): Transaction txn tries to upgrade a shared to exclusive lock on record id rid. This should be blocked on waiting and should return true when granted. Return false if transaction is rolled back (aborts). This should also abort the transaction and return false if another transaction is already waiting to upgrade their lock.
• Unlock(Transaction, RID): Unlock the record identified by the given record id that is held by the transaction.

Attention

• 要遵循二阶段锁原则，transaction在开始时为growing阶段，解锁需将状态切换为shrinking。shrinking阶段不能上任何锁以及升级锁；而当隔离级别为Read Committed时，解共享锁无需将状态设置为shrinking，因为Read Committed在读取完数据后就立即释放读锁。
• 只有在其他共享锁没有处于Upgrading时才能进行Upgrade，如果在Upgrade时发现upgrading==true，则Upgrade失败，LockUpgrade()返回false。
• Cycle Detection在2021中无需实现，仅需实现Wound wait即可，不然可能会超时。
• Wound wait中会出现需要abort其他事务的情况，这里要调用TransactionManager::GetTransaction()获取事务，需要注意C++的类交叉引用规范

2.CONCURRENT QUERY EXECUTION

这部分需要对之前proj3中的部分代码进行补充：

• src/execution/seq_scan_executor.cpp
• src/execution/insert_executor.cpp
• src/execution/update_executor.cpp
• src/execution/delete_executor.cpp
  具体就是在seq_scan_executor中需要先上共享锁，然后之后在update和delete中升级锁/加互斥锁(insert属于添加新行，不用加锁，后InsertTuple()会将整个页上锁)；当然如果隔离级别是Read Committed，则要在seq_scan_executor读取完tuple后释放锁。

Attention

• 我们需要维护table_write_set和index_write_set用于事务的回滚，而table_write_set的维护已经帮我们实现了，所以只需要在写操作时注意更新index_write_set即可。