CMU15445 (FALL 2021) Lab1-4 满分收获与踩坑

前言

在入学前的暑假，我开始自学CMU15445课程的部分内容，当时仅凭导师的指引和网上搜索资料开始动手实践。面对课程的复杂性和深度，我感到有些措手不及，特别是对Lab1-Lab3的理解较为浅薄。在知乎上找到了胡神的文章，加入了他的15445交流群，一边参考大佬们的刷题文档，一边在群内交流学习，最终完成了Lab3。在第一学期末，我投入到研究生工作中，Lab4的进度因此被搁置。直到近期加入胡神15721群，为了通关15421，我重新审视和完成了Lab4，这次的体验让我感觉从大玩具转变为小玩具，整个项目完成得较为轻松。

项目一 - 缓冲池管理器

回顾整个学习过程，我意识到最初做这三个Lab时有些过于注重通过测试，而对概念的理解较为表面化。现在回过头来看，对项目的概念理解清晰了许多，尽管之前的文章记录可能显得有些匆忙。

问题#0 - 在Gradescope上的测试陷阱

在Gradescope上进行代码测试时，遇到案例显示超时，并不意味着是死锁或死循环造成的。需要仔细分析和排除其他可能的原因。

任务#1 - LRU替换策略

面对线程安全的要求，一开始没有明确的指导，直到最后才考虑到了上锁的问题。实现上锁只需在头文件中声明一个锁，然后在每个函数的开始和结束时进行上锁和释放。需要记住在每个return之前释放锁，并确保在一个函数中调用另一个使用锁的函数时，先释放当前锁再申请新锁。

理解pin和upin的含义：pin()代表有人正在使用页面，不能轻易释放，因此需要删除当前frame_id；unpin()则理解为当前frame_id可以作为牺牲id，直接放入队列。

优化搜索效率：使用STL自带的unordered_map作为hash表，key是frame_id，value是对应元素的迭代器，操作复杂度降低至O(1)级别。

任务#2 - 缓冲池管理器实例

理解frame_id和page_id的关系，以及DeletePgImp()函数的返回值问题。这个坑卡了我一整个下午，一个简单的返回值问题导致分数从62分降至96分。回顾时发现，失败返回true，成功返回false的设计在某些语言中可能是合理的解释。

UnpinPgImp()函数的注意事项，理解脏页面标记的处理方式。

任务#3 - 并行缓冲池管理器

这部分需求较为简单，主要涉及对前两个部分的调用，实现过程没有遇到太大问题。需要注意的是，对于并行管理器本身无需设置锁，只需要在replacer和bpli中设置锁即可。

项目二 - 哈希索引

针对Hash Index的项目，尽管排名不高，但在优化上投入了精力。

任务#1 - 页面布局

理解bucket_page和directory_page的用途，其中bucket_page用于存储键值对，directory_page作为哈希表信息的存储地。提出了一些简单的优化思路，如提前判断空位、优化isfull()和isempty()函数。

任务#2 - 哈希表实现

遇到关于需要实现文件的困惑，文档没有明确告知，需在提交文件列表中查找。解决这个问题后，理解了extendible_hash_table的概念和构造函数的使用方法。SplitInsert()和Merge()函数的实现涉及对bucket_page的管理。为了检测函数是否正常工作，编写了内置的打印函数。

任务#3 - 并发控制

使用了目录页的锁，理解了官方文档中关于锁的使用方法，避免了不必要的数据修改。在unlatch和unpin的时机上，确保了线程安全。

项目三 - 查询执行

这个项目耗时最长，完成时感觉脑袋一片蒙蒙。文档对实现需求描述较为笼统，需要从测试文件、Executor构造函数等处获取信息。理解后才能实际使用并完成任务。总结时发现，这个项目更像一个读代码任务。

问题#0 - GradingScope的格式问题

遇到GradingScope格式检查失败的问题，通过社区的帮助，找到了解决办法：将最新的src/include/storage/page/tmp_tuple_page.h文件一起打包提交即可。

开始之前

理解了value、tuple、table、column、schema等概念，以及AbstractExecutor、ExecutorContext、AbstractPlanNode等关键类的作用。AbstractExecutor用于执行SQL查询，AbstractPlanNode存储节点信息，ExecutorContext提供执行上下文信息，AbstractExpression用于表示查询表达式，Value作为数据最小单位，Index用于存储和更新索引，TableHeap和TableIterator用于操作数据表，Catalog用于存储表格信息，schema和column则用于指定表格列。

任务#1 - 执行器

Sequential Scan执行器的实现涉及遍历表并使用Predicate判断是否满足条件，理解了如何将TableIterator传递给Predicate进行匹配。在插入、更新、删除、内联连接、哈希连接、聚合、限制和去重等操作中，分别理解了其原理和具体实现。

项目四 - 并发控制

在并发控制项目中，感谢社区成员提供的测试代码，帮助我顺利进行学习和实践。

任务#1 - 锁管理器

理解隔离级别的实现，包括READ_UNCOMMIT、READ_COMMITED和REPEATABLE_READ级别的事务处理。理解了LockRequestQueue的使用方法，包括如何避免在队列插入时的错误。

任务#2 - 死锁预防

理解WOUND-WAIT策略，即在尝试获取锁之前，检查请求是否会导致阻塞，并根据事务的年龄来决定是否删除请求。

任务#3 - 并发查询执行

了解了TableWriteSet的使用，理解了在执行器中如何获取和释放锁。在Update操作中，理解了IndexWriteSet的作用和管理。理解了在READ_COMMITED隔离级别下扫描数据后需要解锁，而在READ_UNCOMMITED级别下无需锁操作。

总结

回顾整个学习过程，发现虽然在学习初期对项目的理解较为浅薄，但在不断实践中逐渐深化了对各模块的理解。通过加入交流群、参考大佬的文档和代码，以及与社区成员的交流，项目完成度得到了提高。在后续的回顾中，计划将Lab1-Lab4的项目进行全面复盘，加深对整个课程的理解。