CMU 15445 spring - project 1 Buffer Pool实验笔记

标签：15445 GetPinCount Buffer spring EXPECT auto EQ page page0

前排提醒

本项目需要在linux/mac环境下进行开发，如果是windows最好是整个linux的环境，比如云服务器、虚拟机、wsl等。

整个课程需要仔细看文档，包括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();
}

标签：15445,GetPinCount,Buffer,spring,EXPECT,auto,EQ,page,page0
From： https://www.cnblogs.com/1v7w/p/17620338.html