526互联

CMU_15_445_project_1_buffer_pool

发布时间 2023-05-30 22:41:21作者: autumn814

CMU_15_445_project_1_buffer_pool

Overview

实现一个基于磁盘的存储管理器，其中包括一个缓冲池。缓冲池是数据库管理器在主存中分配的一块区域，用于缓存从磁盘读取的表和索引数据。缓冲池可以让数据库支持比可用内存大的数据，并且对其他系统部分是透明的。缓冲池可以减少数据库文件的输入输出，提高数据检索的响应时间。实现需要是线程安全的。多个线程将同时访问内部数据结构。需要实现以下几个存储管理器组件：

  • LRU-K 替换策略
  • 缓冲池管理器
  • 读/写页面保护

Task 1 - LRU-K Replacement Policy

这个任务是实现LRU-K替换策略，它是一个用于跟踪缓冲池中页面使用情况的组件。LRU-K替换策略的基本思想是，它记录了每个页面的最近K次访问时间，当缓冲池满时，它会淘汰那些后向K距离最大的页面。后向K距离是指当前时间与第K次访问时间的差值。如果一个页面的历史访问次数少于K次，那么它的后向K距离被视为无穷大。如果有多个页面的后向K距离都是无穷大，那么它会淘汰那个总体时间戳最早的页面，也就是说，那个最近一次访问时间最久远的页面。

Evict(frame_id_t* frame_id)：这个方法是用来淘汰一个页面的，它会选择后向K距离最大的页面，也就是最不可能再被访问的页面，把它从缓冲池中移除，并把它的标识符存储在输出参数中，然后返回真值。如果没有可以淘汰的页面，就返回假值。

RecordAccess(frame_id_t frame_id)：这个方法是用来记录一个页面被访问的时间的，它会把给定的页面标识符和当前的时间戳保存起来。这个方法应该在一个页面被固定在缓冲池中后调用。

Remove(frame_id_t frame_id)：这个方法是用来清除一个页面的访问历史的，它会删除和给定的页面标识符相关联的所有时间戳。这个方法应该只在一个页面被缓冲池中删除时调用。

SetEvictable(frame_id_t frame_id, bool set_evictable)：这个方法是用来控制一个页面是否可以被淘汰的，它会根据给定的真假值来设置一个页面的可淘汰性。这个方法也会影响LRU-K替换策略的大小。你会在实现缓冲池管理器时知道什么时候调用这个函数。具体来说，当一个页面的固定计数变为0时，它对应的页面就被标记为可淘汰，并且替换策略的大小会增加。

Size()：这个方法是用来返回LRU-K替换策略中当前可淘汰页面的数量的。

这里用两个双向链表和一个哈希表来实现,当一个新的frame_id被记录,则插入history_queue_,同时把这个节点的迭代器保存到哈希表方便之后在链表中删除节点,当frame_id在哈希表中存在,判断是在history_queue_还是cache_queue_,当第k次访问的时候需要把节点移动到cache_queue_的头部.删除元素的话优先删除history_queue_的队尾,如果history_queue_为空则删除cache_queue_的队尾.

std::unordered_map<frame_id_t, std::list<LRUKNode>::iterator> node_store_;
std::list<LRUKNode> history_queue_;
std::list<LRUKNode> cache_queue_;

Task 2 - Buffer Pool Manager

缓冲池管理器是负责从磁盘管理器获取数据库页面并存储在内存中的。缓冲池管理器也可以在被明确指示或者需要为新的页面腾出空间时，把脏页面写回磁盘。

系统中所有的内存页面都由Page对象表示。缓冲池管理器不需要理解这些页面的内容。但是对于你作为系统开发者来说，重要的是要明白Page对象只是缓冲池中内存的容器，而不是特定于一个唯一的页面。也就是说，每个Page对象包含了一块内存，磁盘管理器会用这块内存作为复制从磁盘上读取的物理页面内容的位置。缓冲池管理器会重复使用同一个Page对象来存储随着时间变化而移动到磁盘上或者从磁盘上移动下来的数据。这意味着同一个Page对象可能在系统的生命周期中包含了不同的物理页面。Page对象的标识符（page_id）用来跟踪它包含了哪个物理页面；如果一个Page对象没有包含一个物理页面，那么它的page_id必须被设置为INVALID_PAGE_ID。

每个Page对象也维护了一个计数器，用来记录有多少个线程“固定”了那个页面。你的缓冲池管理器不允许释放一个被固定的页面。每个Page对象也跟踪它是否是脏的。你的工作是在一个页面被解除固定之前记录它是否被修改过。你的缓冲池管理器必须在重用那个对象之前把一个脏页面的内容写回磁盘。

成员变量:

  • pool_size_：缓冲池中的页数，是一个常量。
  • next_page_id_：下一个要分配的页的id，是一个原子变量，可以保证线程安全。
  • pages_：缓冲池中的页的数组，每个页是一个Page类的对象，包含了数据和元信息。
  • disk_manager_：指向磁盘管理器的指针，磁盘管理器负责读写磁盘上的页。
  • log_manager_：指向日志管理器的指针，日志管理器负责记录事务的日志。这个变量在P1中不需要考虑。
  • page_table_：一个哈希表，用来记录缓冲池中每个页的id和对应的帧的id。帧是缓冲池中的一个槽位，可以存放一个页。
  • replacer_：一个智能指针，指向一个LRUK替换器的对象，LRUK替换器是一种缓冲池页面置换算法，可以找到最不常用的页进行替换。
  • free_list_：一个链表，用来存放没有分配给任何页的空闲帧的id。
  • latch_：一个互斥锁，用来保护共享的数据结构，比如page_table_、replacer_和free_list_等。

FetchPage(page_id_t page_id):

这个函数是用来获取一个页面的，它会根据给定的页面标识符从缓冲池或者磁盘中找到对应的页面，并返回一个指向该页面的指针。

  1. 在缓冲池中搜索page_id，如果找到了，则直接返回该页的指针，并将该页的引用计数加一。
  2. 如果没有找到，从空闲列表或替换器中找到一个可用的帧，如果没有找到，则返回nullptr。
  3. 检查被替换的帧上的页是否是脏页，如果是，则将其写回磁盘。
  4. 调用disk_manager_->ReadPage()方法，从磁盘上读取page_id对应的页，并将其放入该帧中，并更新该页的元数据。
  5. 将该帧设置为不可替换，并记录其访问历史和访问类型。

这里注意被替换的frame上的页,需要在page_table_中删除page_id,同时replacer中的frame需要置为not_evict

UnpinPage(page_id_t page_id, bool is_dirty)：

这个函数是用来解除固定一个页面的，它会根据给定的真假值来设置该页面是否是脏的，并把该页面的固定计数减一。

  1. 在缓冲池中搜索page_id，如果没有找到，或者该页的引用计数已经为0，则返回false。
  2. 将该页的引用计数减一，并根据is_dirty参数决定是否将该页标记为脏页。
  3. 如果引用计数为0，则将该页设置为可替换，并记录其访问历史和访问类型。
  4. 返回true表示成功解锁该页。

FlushPage(page_id_t page_id)：

这个函数是用来刷新一个页面到磁盘上的，参数是一个页的id，不能是无效的id。它的返回值是一个布尔值，表示是否成功刷新该页。

  1. 在缓冲池中搜索page_id，如果没有找到，则返回false。
  2. 调用disk_manager_->WritePage()方法，将该页的数据写入磁盘上，不管该页是否是脏页。
  3. 将该页的脏标志清除，表示该页已经和磁盘上的数据一致。
  4. 返回true表示成功刷新该页。

NewPage(page_id_t* page_id)：

用来在缓冲池中创建一个新的页, 参数是一个指向页id的指针，返回值是一个指向新页的指针。

  1. 从空闲列表或替换器中找到一个可用的帧，如果没有找到，则返回nullptr。
  2. 调用AllocatePage()方法，获取一个新的页id，并将其赋值给page_id参数。
  3. 检查被替换的帧上的页是否是脏页，如果是，则将其写回磁盘。
  4. 重置新页的内存和元数据，比如将LSN设为0。
  5. 调用replacer.SetEvictable(frame_id, false)方法，将该帧设置为不可替换，以防止在缓冲池管理器解锁之前被替换器替换掉。同时，记录该帧的访问历史，以便LRUK算法工作。

DeletePage(page_id_t page_id)：

这个函数是用来删除一个页面的，参数是一个页的id，它的返回值是一个布尔值，表示是否成功删除该页。

  1. 在缓冲池中搜索page_id，如果没有找到，则什么都不做，返回true。
  2. 检查该页的引用计数是否为0，如果不为0，则表示该页被锁定，不能删除，返回false。
  3. 从page_table中删除该页的记录，并停止在替换器中跟踪该帧，并将该帧加入到空闲列表中。
  4. 重置该页的内存和元数据，比如将LSN设为0。
  5. 调用disk_manager_->DeallocatePage()方法，模拟在磁盘上释放该页。
  6. 返回true表示成功删除该页

DEBUG

Running main() from gmock_main.cc
[==========] Running 2 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 2 tests from BufferPoolManagerTest
[ RUN      ] BufferPoolManagerTest.BinaryDataTest
[       OK ] BufferPoolManagerTest.BinaryDataTest (0 ms)
[ RUN      ] BufferPoolManagerTest.SampleTest
/home/autumn/Study/bustub-private/test/buffer/buffer_pool_manager_test.cpp:137: Failure
Expected equality of these values:
  nullptr
    Which is: NULL
  bpm->FetchPage(0)
    Which is: 0x618000000488
[  FAILED  ] BufferPoolManagerTest.SampleTest (0 ms)
[----------] 2 tests from BufferPoolManagerTest (1 ms total)

[----------] Global test environment tear-down
[==========] 2 tests from 1 test suite ran. (1 ms total)
[  PASSED  ] 1 test.
[  FAILED  ] 1 test, listed below:
[  FAILED  ] BufferPoolManagerTest.SampleTest

 1 FAILED TEST

当调用NewPage()方法的时候,如果free_list_已经满了,是从LRUKreplacer中替换出一个页面的话,需要把page_table_内替换出的page_id删除.

Task 3 - Read/Write Page Guards

这个任务是要在缓冲池管理器中使用页面守卫来自动固定和解锁页面的。页面守卫是一种类，可以存储指向缓冲池管理器和页面对象的指针，并在不再需要页面时调用UnpinPage方法。页面守卫还可以提供只读/写数据API，以确保正确地设置is_dirty标志。

我们只要实现移动操作符、Drop方法和析构函数以及BPM中的几个包装方法就可以了.

做一下格式校验就可以提交了,初始化类用花括号的列表初始化,不然ClangTidy会报错.

return ReadPageGuard{this, page};

DEBUG

第一次提交,发现居然还有很多额外测试全都没过,在学习群里拿到测试源码一个个debug.

很花时间,开始写代码时候很多小细节导致测试没过.

img

Leaderboard

第一次排行榜64名

img

官方给了两个优化的思路

  1. 更好的替换算法。考虑到获取工作负载是倾斜的（即，有些页面比其他页面更频繁地被访问），你可以设计你的LRU-k替换器，使其考虑页面访问类型，从而减少页面缺失。页面缺失是指程序请求一个不在当前内存中的页面时发生的情况，这时操作系统需要从磁盘上找到并恢复该页面，这会影响程序的执行速度。

针对这一点在LRUKnode记录history的时候同时记录AccessType,然后为Get设置2的权重,scan设置1的权重,当替换frame的时候如果权重大于阈值则不替换这个页面,防止替换掉经常Get请求的frame,可以有效减少磁盘io.成绩上升到34名.

img

  1. 并行I/O操作。在访问磁盘管理器时，不要持有全局锁，而是同时向磁盘管理器发出多个请求。这种优化在现代存储设备中非常有用，因为并发访问磁盘可以更好地利用磁盘带宽。磁盘带宽是指磁盘在单位时间内能够传输的数据量。此外，一些内部数据结构需要全局锁来保护访问。例如，如果两个线程都试图将页面加载到缓冲池中，就需要一个全局锁来让它们找到一个空闲的页面。一个线程抓住这个锁，做完它的工作，然后释放锁。另一个线程在此期间一直在等待。这种情况每秒发生很多次，但是线程越多，争用就越多。

这里我设想的是当与磁盘交互的时候另开一个线程去执行磁盘的读写,std::unordered_map<page_id_t, bool> page_available_ 来保存当前页是否可用,同时操作此变量需要获取page_av_map_mutex_锁,当开始磁盘读写的时候拿到锁把标志位置false再释放锁,完成读写的时候拿到锁把标志位置true再释放锁,这样可以保证每次读取的时候磁盘上的数据都是最新写入的.

但是,尴尬的是名次掉到了129 doge...看来只能用更细粒度的锁来操作了,等做完整个project再回头来优化.

img