构建一个新的面向磁盘的存储管理器,这样的存储管理器假定数据库的主要存储位置在磁盘上。
在存储管理器中实现缓冲池。缓冲池负责将 pag
从主存到磁盘来回移动。允许 DBMS 支持大于系统可用内存量的数据库。缓冲池的操作对系统中的其他部分是透明的。例如,系统使用其唯一标识符 ( page_id_t
)向缓冲池请求页面,但它不知道该页面是否已经在内存中,或者系统是否必须从磁盘中检索它。
实现需要是线程安全的。多个线程将同时访问内部数据结构,因此需要确保临界区受到 latches
的保护。
需要在存储管理器中实现以下两个任务:
(1)LRU 替换原则
(2)缓冲池管理器
任务 1 - LRU 替换策略
(1)该组件负责跟踪缓冲池中的页面使用情况。将在 src/include/buffer/lru_replacer.h 中实现一个新的子类 LRUReplacer
,它相应的实现文件在 src/buffer/lru_replacer.cpp 。LRUReplacer
继承了抽象类 Replacer
(src/include/buffer/replacer.h)。
(2) LRUReplacer
的大小与 BufferPoolManager
相同,因为在 BufferPoolManager
中包含了所有 frames
的 placeholders
。 但是,并非所有 frames
都被视为 LRUReplacer
. 将 LRUReplacer
被初始化为有没有 frames
。然后,LRUReplacer
将只考虑新的没有划分的那些。
(3)需要实现课程中讨论的 LRU
策略。您将需要实现以下方法:
Victim(T*)
: Replacer
跟踪与所有元素相比最近访问次数最少的对象并删除,将其删除页号存储在输出参数中,并返回 True
。如果 Replacer
为空则返回 False
。Pin(T)
:在将 page
固定到 BufferPoolManager
中的 frame
之后,应该调用此方法。它应该从 LRUReplacer
中删除固定包含固定 page
的 frame
。Unpin(T)
:当页面的引用计数变为 0 时,应该调用此方法。这个方法应该将未包含固定 page
的 frame
添加到 LRUReplacer
。(注意,需要判断是否超出了内存大小,如果超过了,则删除较新的页面,然后再添加。)Size()
:这个方法返回当前在 LRUReplacer
中的页面数。任务 2 - 缓冲池管理器
BufferPoolManager
)。该 BufferPoolManager
负责从 DiskManager
中读取数据库页并将它们存储在内存中。BufferPoolManager
还可以在明确指示或需要为新页腾出空间时,将脏页写入磁盘。DiskManager
)。Page
对象表示。BufferPoolManager
并不需要了解这些页的内容。但是,作为系统开发人员,重要的是要理解 Page
对象只是缓冲池中用于存储内存的容器,因此不是特定于唯一的页面。也就是说,每个Page
对象都包含一个内存块,DiskManager
将它用作复制从磁盘读取的 page
内容的位置。当它来回移动到磁盘时,BufferPoolManager
将重用相同的 Page
对象来存储数据。这意味着相同的 Page
在系统的整个生命周期中可能包含不同的物理页面。Page
对象的标识符 (page_id
) 跟踪它所包含的物理页面,如果 Page
对象不包含物理页,则必须将其 page_id
设置为INVALID_Page_id
。Page
对象还维护了一个计数器,用于表示 “固定” 该页面的线程数。BufferPoolManager
不允许释放被 ”固定“ 的页面。每个 Page
对象还跟踪它标记的脏页。我们需要判断页面在解除绑定之前是否被修改过。BufferPoolManager
必须将 dirty Page
的内容写回磁盘,然后才能重用该对象。BufferPoolManager
的实现将使用上述步骤中创建的 LRUReplacer
类。它将使用LRUReplacer
来跟踪 Page
对象被访问的时间,以便在必须释放 frame
来腾出空间给从磁盘复制的新物理页时决定删除哪个对象。FetchPageImpl(page_id)
NewPageImpl(page_id)
UnpinPageImpl(page_id, is_dirty)
FlushPageImpl(page_id)
DeletePageImpl(page_id)
FlushAllPagesImpl()
FetchPageImpl
,如果空闲列表中没有页面可用,并且所有其他页面当前都被固定,则应该返回 NULL
。不管 FlushPageImpl
的引用状态如何,都应该刷新页面。测试
LRUReplacer
:
test/buffer/lru_replacer_test.cpp
BufferPoolManager
:
test/buffer/buffer_pool_manager_test.cpp
本地测试:
// 别忘了删除测试中的 disabled
$ mkdir build
$ cd build
$ make lru_replacer_test
$ ./test/lru_replacer_test
$ mkdir build
$ cd build
$ make buffer_pool_manager_test
$ ./test/buffer_pool_manager_test
// 检查
$ cd build
$ make format
$ make check-lint
$ make check-clang-tidy
提交:
src/include/buffer/lru_replacer.h
src/buffer/lru_replacer.cpp
src/include/buffer/buffer_pool_manager.h
src/buffer/buffer_pool_manager.cpp
打包
// 下面的最好是写个bash脚本,比较方便。
zip project1.zip \\
src/include/buffer/lru_replacer.h \\
src/buffer/lru_replacer.cpp \\
src/include/buffer/buffer_pool_manager.h \\
src/buffer/buffer_pool_manager.cpp
LRU(Least-Recently Used)
的策略:
LRU
正是页面置换算法的一种,最近最少使用的策略,它有一个潜在的假设,如果某个页的数据被访问过一次,那么下次再被访问的机率也就更高。LRU
的思路:
Clock
策略:
Clock
也是页面置换算法的一种。Clock
置换算法分为两种,一种是简单的置换算法,与 LRU
算法类似。另一种是改进型的,相比于前一种,减少了磁盘IO,性能更加高效。Clock
的思想是先将内存中的所有页面想象成一个环形队列,通过维护一个访问位,每次更新的时候,如果访问位为 0,表示最近没有被访问,则可以置换;否则,将访问位置 0,继续寻找。Clock
设计思路:
Clock
设计思路。维护一个访问位数组和一个指针。每次当成环形数组循环查找当前需要被置换的页面。<aside> 💡 C++ :std::scoped_lock 能够避免死锁的发生。它的构造函数能够自动进行上锁操作,析构函数会对互斥量进行解锁操作。能够保证线程安全。
</aside>
根据上面 LRU
的设计思路,我们可以定义出 LRUReplacer
的数据结构,如下。
class LRUReplacer : public Replacer {
private:
// TODO(student): implement me!
// 为了线程安全需要加的锁
std::mutex latch;
// 这个表示 LRUReplacer 的大小,Buffer Pool大小相同。
size_t capacity;
// 我们使用 双向链表 + 哈希表 的数据结构。
std::list<frame_id_t> LRUList;
// 使用 unordered_map(注意加头文件),从 frame_id 映射到 Node。
std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> LRUHash;
};
根据上面 Clock
的设计思路,我们可以定义出 ClockReplacer
的数据结构,如下。
class ClockReplacer : public Replacer {
private:
// TODO(student): implement me!
// 对于每个 frame_id,都需要标记两个元素。isPin 表示当前 frame 是正在被引用。
// ref 表示当前的 frame 最近是否被使用过。
struct clockItem {
bool isPin;
bool ref;
};
// 为了线程安全需要加的锁
std::mutex latch;
// 这个表示 ClockReplacer 的大小,Buffer Pool大小相同。
size_t victim_number;
// clock 指针当前所指位置。
size_t clockHand;
// clockItem 数组,数组下表表示 frame_id。
std::vector<clockItem> victimArray;
};
Replacer
:追踪 page
使用情况的抽象类。类中不包含 page
的具体信息,只是为 Buffer Pool Manager
服务,提供了一个可以替换的 frame_id
。这个类包含了四个主要的函数。这里为了方便,将两个实现 LRUReplacer
ClockReplacer
根据功能写在了一起,看的时候如果不舒服可以一次看一种实现方法。
class Replacer {
public:
Replacer() = default;
virtual ~Replacer() = default;
/**
* Remove the victim frame as defined by the replacement policy.
* @param[out] frame_id id of frame that was removed, nullptr if no victim was found
* @return true if a victim frame was found, false otherwise
*/
virtual bool Victim(frame_id_t *frame_id) = 0;
/**
* Pins a frame, indicating that it should not be victimized until it is unpinned.
* @param frame_id the id of the frame to pin
*/
virtual void Pin(frame_id_t frame_id) = 0;
/**
* Unpins a frame, indicating that it can now be victimized.
* @param frame_id the id of the frame to unpin
*/
virtual void Unpin(frame_id_t frame_id) = 0;
/** @return the number of elements in the replacer that can be victimized */
virtual size_t Size() = 0;
};
(1)Victim
函数:
frame
。 其中参数 frame_id
是【out】参数,也就是需要将 victim
的 frame_id
写给调用者。而返回值是 bool
类型,如果成功删除了一个最近最少使用的 frame
则返回 true
,否则,返回 false
。LRUReplacer
实现:ClockReplacer
实现:(2)Pin
函数:
Pin
一个页面,是指当调用了一个页面的时候,那么这个页面由于有了引用,则不能从缓冲区中移除,一直到当前页面的引用为 0 ,才可以。LRUReplacer
实现:
LRUList
中维护的是可以被 victem
的页面,当 Pin
的时候,如果在 LRUList
中,则需要从中移除。ClockReplacer
实现:
ClockReplacer
中 capacity
维护能够被置换的页面的总的数量。victimArray
维护所有页面的信息。(3)Unpin
函数:
Unpin
一个页面,是指当一个页面的引用计数为0的时候,就把当前页面放入到待置换的数据结构中。LRUReplacer
实现:ClockReplacer
实现:(4)Size
函数:
返回一个当前待置换的 fame
数量。
LRUReplacer
实现:
size_t LRUReplacer::Size() { return LRUList.size(); }
ClockReplacer
实现:
size_t ClockReplacer::Size() { return victim_number; }
(5)构造函数:
需要补充完整构造函数。
LRUReplacer
实现:
LRUReplacer::LRUReplacer(size_t num_pages) { capacity = num_pages; }
ClockReplacer
实现:
ClockReplacer::ClockReplacer(size_t num_pages) {
victim_number = 0;
clockHand = 0;
// 初始化 victimArray。isPin 最开始为 true 是因为我们把页面加载到 Buffer pool 的时候,一定是因为 page 被引用了。
// ref 为 false,因为当前这个 page 的引用还没有结束。
for (size_t i = 0; i < num_pages; i++) {
victimArray.emplace_back(clockItem{true, false});
}
}
Buffer Pool Manager
:对缓冲池进行管理。其主要的数据结构是一个 page
数组,下标表示 frame_id
。还有一个哈希表,表示从 page_id
到 frame_id
的映射。为了各种需要,省略代码。
FindPage
把查找一个 frame
的操作单独拿出来,方便调用。FetchPageImpl
UnpinPageImpl
FlushPageImpl
NewPageImpl
deletePageImpl
FlushAllPagesImpl