前排提醒
本项目需要在linux/mac环境下进行开发，如果是windows最好是整个linux的环境，比如云服务器、虚拟机、wsl等。
整个课程需要仔细看文档，包括bustub的readme，每篇project的描述。
整个课程需要仔细看文档，包括bustub的readme，每篇project的描述。
整个课程需要仔细看文档，包括bustub的readme，每篇project的描述。
项目大意
水平较差，只能拿到很低的分数。
本项目分为3个部分：
- 实现LRU-K算法
- 实现缓冲池管理
- 实现RAII思想的PageGuard
大概难度是2最难，因为需要实现的函数最多。
提醒，改了代码文件但没改测试代码文件时候，也需要指定测试目标重新生成
Task #1 - LRU-K Replacement Policy
这个任务要求实现LRU-K替换策略。
大概意思为将硬盘中的一个page(页)存入内存中形成一个frame(页)。内存中能存入的frame有限，当需要存入新的page，但frame已经满了的时候，该把哪个旧的替换下去？这就是LRU-K解决的问题。
它
LRU-K记录了每个frame的访问记录，将访问时间戳存储成一个数组，下标小的表示最近的访问。当需要进行替换的时候，他先检测有没有frame的访问次数是小于k的，如果有就根据FIFO进行踢出(这里注意，项目网站和代码注释不同，正确的是FIFO)；如果所有的都大于等于k次，那么数组[k-1]项(数组起始下标为0)最小的被踢出(表示第前k次访问最早)。
这里的时间戳应该为逻辑时间戳，用来分清楚操作的前后即可。
RecordAccess：增加一次记录。变更current_timestamp_, cur_size_, node_store_
Evict： 踢出 evictable 且符合上面条件的 frame。注意这里不足k次的话是FIFO。
SetEvictable： 设置 frame 是否可被踢出。变更cur_size_
Remove： 删除选中的 frame。变更cur_size_
Size：返回curr_size_的值。
线程安全方面，可以简单的加个大锁，一进函数就加锁(笑
Task #2 - Buffer Pool Manager
Buffer Pool Manager 用来从硬盘中获取实际数据，并控制替换下来的frame进行写入(假如有更改)。
NewPage： 生成一个新的 page 对象，将生成的 page_id通过参数传出，需要 pin
FetchPage：获取一个 page 对象，如果Bufferpool 里没有还需要从硬盘中获取，需要 pin
UnpinPage：减少 pin 计数。如果计数为 0 则需要将此frame标记为可被踢出的。需要注意 is_dirty_ |= is_dirty
FlushPage：把 page 内容写回到磁盘上
FlushAllPages：将所有page进行FlushPage
DeletePage： 删除一个evictable的page，replacer_将其设置为Remove，page这一块metadata需要重新设置(不要free
这里最关键的就是维护pin_count_。线程安全方面依旧可以加大锁(笑
Task #3 - Read/Write Page Guards
程序员使用Page的时候可能会忘记加锁，或者加了锁忘记释放，这时候有个PageGuard把Page封装起来，自动加锁释放锁就很方便，这是RAII思想。
程序员可以通过Buffer Pool Manager里提供的 FetchPagexxx来获取对应的PageGuard。
Drop、析构函数: unpin / 释放锁。注意在PageGuard的生命周期里，只能够执行一次。
移动构造函数、重载移动赋值运算符: 旧的Drop(如果有)，新的变成unavailable，注意不是Drop
这里卡了我2天，因为我弱智地把获取锁写到了.h里面，大家以此为鉴。结尾我放了一些测试可以参考。
结语
要写每个task时候还是要先把整体先看完，抓住理解再去动手写。实在不会可去找人交流，在cmu选这门课的同学们还经常问助教呢，不要怕交流嘛hh
欢迎加群152391370一起搞cmu15-445，也可以搞他课程例如6.824，6.828（6.S081），15-213等相关内容。
附：page_guard_test
// 参考https://zhuanlan.zhihu.com/p/615312257
TEST(PageGuardTest, ReadTest) {
const std::string db_name = "test.db";
const size_t buffer_pool_size = 5;
const size_t k = 2;
auto disk_manager = std::make_shared<DiskManagerUnlimitedMemory>();
auto bpm = std::make_shared<BufferPoolManager>(buffer_pool_size, disk_manager.get(), k);
page_id_t page_id_temp;
auto *page0 = bpm->NewPage(&page_id_temp);
// test ~ReadPageGuard()
{
auto reader_guard = bpm->FetchPageRead(page_id_temp);
EXPECT_EQ(2, page0->GetPinCount());
}
EXPECT_EQ(1, page0->GetPinCount());
// test ReadPageGuard(ReadPageGuard &&that)
{
auto reader_guard = bpm->FetchPageRead(page_id_temp);
EXPECT_EQ(2, page0->GetPinCount());
auto reader_guard_2 = ReadPageGuard(std::move(reader_guard));
EXPECT_EQ(2, page0->GetPinCount());
}
EXPECT_EQ(1, page0->GetPinCount());
// test ReadPageGuard::operator=(ReadPageGuard &&that)
{
auto reader_guard_1 = bpm->FetchPageRead(page_id_temp);
auto reader_guard_2 = bpm->FetchPageRead(page_id_temp);
EXPECT_EQ(3, page0->GetPinCount());
reader_guard_1 = std::move(reader_guard_2);
EXPECT_EQ(2, page0->GetPinCount());
}
EXPECT_EQ(1, page0->GetPinCount());
// test ReadPageGuard::Drop()
{
auto reader_guard_1 = bpm->FetchPageRead(page_id_temp);
auto reader_guard_2 = bpm->FetchPageRead(page_id_temp);
EXPECT_EQ(3, page0->GetPinCount());
auto reader_guard_3 = std::move(reader_guard_1);
EXPECT_EQ(3, page0->GetPinCount());
reader_guard_1.Drop();
EXPECT_EQ(3, page0->GetPinCount());
reader_guard_3.Drop();
EXPECT_EQ(2, page0->GetPinCount());
reader_guard_3.Drop();
EXPECT_EQ(2, page0->GetPinCount());
}
EXPECT_EQ(1, page0->GetPinCount());
// Shutdown the disk manager and remove the temporary file we created.
disk_manager->ShutDown();
}
TEST(PageGuardTest, WriteTest) {
const std::string db_name = "test.db";
const size_t buffer_pool_size = 5;
const size_t k = 2;
auto disk_manager = std::make_shared<DiskManagerUnlimitedMemory>();
auto bpm = std::make_shared<BufferPoolManager>(buffer_pool_size, disk_manager.get(), k);
page_id_t page_id_temp;
auto *page0 = bpm->NewPage(&page_id_temp);
// test ~WritePageGuard()
{
auto writer_guard = bpm->FetchPageWrite(page_id_temp);
EXPECT_EQ(2, page0->GetPinCount());
}
EXPECT_EQ(1, page0->GetPinCount());
// test WritePageGuard(ReadPageGuard &&that)
{
auto writer_guard = bpm->FetchPageWrite(page_id_temp);
auto writer_guard_2 = WritePageGuard(std::move(writer_guard));
EXPECT_EQ(2, page0->GetPinCount());
}
EXPECT_EQ(1, page0->GetPinCount());
// Shutdown the disk manager and remove the temporary file we created.
disk_manager->ShutDown();
}
// 参考https://zhuanlan.zhihu.com/p/629006919
TEST(PageGuardTest, HHTest) {
const std::string db_name = "test.db";
const size_t buffer_pool_size = 5;
const size_t k = 2;
auto disk_manager = std::make_shared<DiskManagerUnlimitedMemory>();
auto bpm = std::make_shared<BufferPoolManager>(buffer_pool_size, disk_manager.get(), k);
page_id_t page_id_temp = 0;
page_id_t page_id_temp_a;
auto *page0 = bpm->NewPage(&page_id_temp);
auto *page1 = bpm->NewPage(&page_id_temp_a);
auto guarded_page = BasicPageGuard(bpm.get(), page0);
auto guarded_page_a = BasicPageGuard(bpm.get(), page1);
// after drop, whether destructor decrements the pin_count_ ?
{
auto read_guard1 = bpm->FetchPageRead(page_id_temp_a);
EXPECT_EQ(2, page1->GetPinCount());
read_guard1.Drop();
EXPECT_EQ(1, page1->GetPinCount());
}
EXPECT_EQ(1, page0->GetPinCount());
EXPECT_EQ(1, page1->GetPinCount());
// test the move assignment
{
auto read_guard1 = bpm->FetchPageRead(page_id_temp);
auto read_guard2 = bpm->FetchPageRead(page_id_temp_a);
EXPECT_EQ(2, page0->GetPinCount());
EXPECT_EQ(2, page1->GetPinCount());
read_guard2 = std::move(read_guard1);
EXPECT_EQ(2, page0->GetPinCount());
EXPECT_EQ(1, page1->GetPinCount());
}
EXPECT_EQ(1, page0->GetPinCount());
// test the move constructor
{
auto read_guard1 = bpm->FetchPageRead(page_id_temp);
auto read_guard2(std::move(read_guard1));
auto read_guard3(std::move(read_guard2));
EXPECT_EQ(2, page0->GetPinCount());
}
EXPECT_EQ(1, page0->GetPinCount());
EXPECT_EQ(page_id_temp, page0->GetPageId());
// repeat drop
guarded_page.Drop();
EXPECT_EQ(0, page0->GetPinCount());
guarded_page.Drop();
EXPECT_EQ(0, page0->GetPinCount());
disk_manager->ShutDown();
}