存储结构
本文章是对CMU-15445-2024fall的project1的一些总结。从开始编写到完成这个项目前后花了大概六天的时间。刚开始时，由于自己太菜，在写代码时十分痛苦，完全不知道从何下手。不过，还好自己没有放弃，在经历了六天的拷打后，总算是在gradescope上拿到了满分，不过我还没有对我的代码进行优化，所以性能不是很好，在排行榜上也只是100多名。后续，有时间的话可能会去优化吧。总之，这个项目对于我们理解数据库内核的存储结构还是很有帮助的，同时项目中也有对并发的控制。可以很好的锻炼我们并发编程的能力。其 实，该项目总体上不算很难，只要你理清楚它的架构，一切就迎刃而解了。
这是我理解的项目的架构。其中lru-k 负责在内存的帧满时，选出一个需要淘汰的页。dis-scheduler将产生的读写请求放入请求队列中。startwork 后台工作线程取出请求，并调用disk manager的接口。当请求完成时，通知调用者。
lru-k replacer
这里，我用的是两个队列来实现lru-k算法。该算法比较简单，如果第一次知道该算法，推荐去网上搜一些教程。
disk_scheduler
这里需要实现两个方法，一个是Schedule(DiskRequest r)，这个只需要将请求放入请求队列即可。另一个是StartWorkerThread()。思路是写一个死循环，不断取出队列中的元素，在根据请求类型调用对应的接口即可。这里需要知道std::promise和future。简单来说，promise相当于承诺，比如，我承诺你我会在某个时间给你答复，当任务完成时，给你结果。set_value方法相当于通知你任务完成，并给你答复。future为期望，它会一直等待承诺完成，get方法会一直阻塞，直到上述的承诺完成，也就是调用set_value方法的时候。
buffer manager
这里是本项目最难的部分，折磨了我好久。这里难的部分在于对并发和死锁的控制，需要充分理解bpm_latch和page_guard的功能。bpm_latch表示的是对buffer manager 中管理的共享资源的锁。比如frame的引用数，页表，和帧的可驱逐状态。这些共享资源代表此刻这个内存的状态，不是为buffer manager所独有的。上述的架构图仅仅是单线程模型，在测试样例中，会有多个buffer manager 对buffer pool 进行操作。而page_guard相当于内存页的读者写者锁，buffer pool manager 必须持有这个锁才能对页中的内容进行修改。所以bpm_latch管理的是整个内存，只有一个。page_guard管理的是单个页，每个页都有。关于获取的的顺序是十分重要的，我是先获取bpm_latch，在获取page_guard。一定要注意的是，在获取page_guard前，一定要先释放bpm_latch，不然就会死锁。例如，一个线程获取Page0的写锁，另一个线程在拥有page1的写锁时，想要获取page0的写锁。这时，page1拿到了bpm_latch,但还没拿到page0的写锁，所以它会等待这个线程释放page0的写锁，而想要释放page0的写锁，也必须要拿到bpm_latch。此时两个线程就形成了环路等待，死锁发生。读到这里，你们可能还没有理解为什么要这样。这里有几个要点。
第一：在拿page的锁时，必须先拿bpm锁。为什么，因为，我们在拿到page的锁时，必须确保页面不会被淘汰。不然得话，当我们对页面的内容进行修改时，可能会发生页面被逐出内存的情况。所以我们在拿page锁之前，先拿bpm锁，将页面的引用数加一，并设置为不可淘汰。
第二：在拿到bpm锁并更新完页面状态后，必须先释放bpm锁再去拿page锁。否则就会发生上述的死锁问题。
第三：page锁只是用于更改页的内容。页的引用数，可淘汰状态必须拿bpm锁改。
理解了这些，那么代码就十分好写了。