前言
通过本地测试大概花了三天,第一次提交线上测试只有45分😭😭😭。后来又陆陆续续修改,又花了两天时间终于过了。不过这个实现基本毫无性能可言,bpm的每个函数都是简单粗暴地直接上scope lock锁住整个函数作用域,所以QPS rank排在200靠后了,后面再做优化吧。
Buffer Pool
对Buffer Pool做一个简单的介绍
更详细的可以看揭开 Buffer Pool 的面纱
温故知新——虚拟内存
首先复习一下操作系统的知识。在每个进程创建加载的时候,会被分配一定的内存和一个连续的虚拟地址空间。与实际的内存空间不同,虚拟内存地址空间在物理上是不存在的,仅仅是每个进程在逻辑层面上拥有的内存,他的真实位置位于磁盘中。等到进程真正运行的时候,需要某些数据但是数据不在物理内存中,就会触发缺页异常,然后进行数据拷贝,将数据从磁盘中拷贝到内存中。
在虚拟存储机制中,系统将虚拟地址空间划分为固定大小的虚拟页(Virtual Page,VP),而物理内存则划分为相同大小的物理页(Physical Page,PP),也被称为页帧(Page Frame)。每个虚拟页和物理页的大小通常是相等的,并且由系统设置。常见的页大小为4KB、2MB或4MB。虚拟页和物理页之间的映射关系由操作系统的内存管理单元(Memory Management Unit,MMU)进行管理。MMU中包含页表(Page Table),用于存储虚拟页和物理页之间的映射信息,当进程访问虚拟地址时,MMU根据页表的映射信息将虚拟页转换为对应的物理页。如果虚拟页已经在物理内存中,那么访问将直接转向物理页。如果虚拟页不在物理内存中(即发生了缺页异常),操作系统将负责将该虚拟页从磁盘加载到物理内存中,并更新页表的映射关系。
当物理内存的页已满时,OS使用页面置换算法来选择哪些物理页将被逐出并加载新的虚拟页。页面置换算法的目标是尽量减少页面置换的次数,同时尽量减少对性能的影响。一些常见的置换算法如下:
- 最佳(Optimal)算法:理想情况下,最佳算法会选择最长时间内不会被访问的物理页进行置换。然而,最佳算法需要预先知道未来访问模式,因此在实际中无法实现,仅被用作评估其他算法的性能上限。
- 先进先出(FIFO)算法:FIFO算法简单地选择最早进入物理内存的物理页进行置换。它维护一个页队列,当需要逐出页时,选择队列中最前面的页面进行置换。然而,FIFO算法可能会导致"Belady's Anomaly"问题,即物理页数增加时,缺页率反而增加。
- 最近最久未使用(LRU)算法:LRU算法基于页面最近的访问情况进行置换。它将物理页按照最近访问的时间顺序排列,当需要逐出页时,选择最久未被访问的物理页进行置换。LRU算法的实现较为复杂,包括硬件和软件支持。
- 时钟(Clock)算法:时钟算法使用一个类似于时钟的数据结构来维护物理页的访问情况。每个物理页都有一个访问位(或称为引用位),当页面被访问时,访问位被设置为1。当需要逐出页时,算法从时钟的当前位置开始扫描物理页,如果访问位为0,则选择该页进行置换;如果访问位为1,则将访问位置为0,继续扫描。这样,算法会尽量保留最近被访问的物理页。
- 最近未使用(NRU)算法:NRU算法将物理页分为多个类别,根据页的访问位和修改位进行分类。然后,从最低优先级的类别中选择一个物理页进行置换。这样,算法会优先选择长时间未被访问且未被修改的物理页进行置换。
引入了虚拟内存机制后,在逻辑上拓展了计算机的物理内存。一个仅有4GB物理内存的计算机,可能能够运行8GB的应用程序,而仅仅只需要付出维护页表和进行缺页中断时的磁盘I/O的较小的代价。
InnoDB的Buffer Pool
数据库系统的Buffer Pool和虚拟内存机制相似,但是目标却不同。因为数据库系统的数据本身就是存储在磁盘中,虚拟内存机制是为了在逻辑层面扩展计算机的计算资源,而Buffer Pool机制则是为了减少磁盘的I/O操作。(注意,Buffer Pool位于InnoDB存储引擎层,与MySQL 8.0 版本摒弃的查询缓存不是同一个东西)
下面的结构图中展示了Buffer Pool是InnoDB内存结构的四大组件之一,不属于MySQL的Server层,是InnoDB存储引擎层的缓冲池。
InnoDB存储引擎的逻辑存储结构大致如下图:
在DBMS中,记录是按照行来存储的,但是数据库的读取并不是以行为单位的,否则一次读取(也就是一次 I/O 操作)只能处理一行数据,效率会非常低。因此,InnoDB 的数据是按「页」为单位来读写的,也就是说,当需要读一条记录的时候,并不是将这个行记录从磁盘读出来,而是以页为单位,将其整体读入内存。InnoDB 默认每个页的大小为 16KB,也就是最多能保证 16KB 的连续存储空间。页是 InnoDB 存储引擎磁盘管理的最小单元,意味着数据库每次读写都是以 16KB 为单位的,一次最少从磁盘中读取 16K 的内容到内存中,一次最少把内存中的 16K 内容刷新到磁盘中。
为了减少磁盘I/O操作,Buffer Pool的作用就是把最热的数据页缓存在内存中,下次需要这个数据页时可以直接从内存读取,而不是进行一次磁盘I/O。当需要读取或写入数据时,存储引擎首先检查缓冲池中是否已经存在所需的数据页。如果数据页在缓冲池中,DBMS可以直接从内存中读取或写入数据,避免了磁盘IO的开销。如果数据页不在缓冲池中,DBMS就需要从磁盘加载数据页到缓冲池,并进行相应的操作。
相应的,缓冲池的管理也涉及到数据页的替换策略。当缓冲池已满时,需要替换一些数据页以腾出空间来存储新的数据页。常见的数据页替换策略包括最近最少使用(LRU)和时钟(Clock)算法。
在接下来的实现中,page表示在磁盘,frame表示在内存
Task #1 - LRU-K Replacement Policy
第一步实现一个LRU-K的页置换策略。与一般的LRU算法不同。K表示历史访问的数量。该算法选择一个具有最大的后向K距离的页面进行替换。后向K距离是指当前时间戳与第K次之前访问的时间戳之间的差异。如果一个页面的历史访问次数少于K次,则将其后向K距离设为正无穷。当有多个页面的后向K距离都为正无穷时,算法会选择具有最早整体时间戳(即最早一次的访问时间最早)的页面进行替换。这种算法的目标是增加对最近访问的页面的优先级,同时考虑到页面的历史访问模式。通过调整K的值,可以控制算法对历史访问的敏感程度。较小的K值更关注最近的访问,而较大的K值更平衡最近和历史访问的影响。
首先让每个frame都关联一个LRUKNode数据结构如下。std::list<size_t> history_
记录该节点的历史访问记录、k_
为策略设置的K值、fid_
为关联的frame id、is_evictable_
记录当前节点关联的页是否可以驱逐。
为该结构实现了几个关键函数,比如获取最近的一次访问时间戳、最早的一次访问时间戳、清空历史记录、计算后向K距离等。
class LRUKNode {
public:
LRUKNode() = default;
LRUKNode(size_t id, size_t k) : k_(k), fid_(id) {}
auto GetEvictable() -> bool { return is_evictable_; }
void SetEvictable(bool evictable) { is_evictable_ = evictable; }
auto GetHistory() { return history_; }
void AddHistory(size_t timestamp) { history_.push_front(timestamp); }
void RemoveHistory() {
while (!history_.empty()) {
history_.pop_back();
}
}
auto GetFid() { return fid_; }
void SetK(size_t k) { k_ = k; }
auto GetKDistance(size_t cur) -> uint64_t {
// 如果一个帧的历史访问次数少于k次,则将其后向k距离设置为正无穷大(+inf)
if (history_.size() < k_) {
return UINT32_MAX;
}
// 获取k次前访问的时间戳
size_t k_distance;
auto it = history_.begin();
std::advance(it, k_ - 1);
k_distance = *it;
return cur - k_distance;
}
auto GetLastAccess() -> size_t {
if (history_.empty()) {
return UINT32_MAX;
}
return history_.front();
}
auto GetBackAccess() -> size_t {
if (history_.empty()) {
return UINT32_MAX;
}
return history_.back();
}
private:
/** History of last seen K timestamps of this page. Least recent timestamp stored in front. */
// Remove maybe_unused if you start using them. Feel free to change the member variables as you want.
// 访问历史——时间戳链表,最近的访问时间戳在头部
[[maybe_unused]] std::list<size_t> history_;
// k距离
[[maybe_unused]] size_t k_;
// 帧id
[[maybe_unused]] frame_id_t fid_;
// 是否可驱逐
[[maybe_unused]] bool is_evictable_{false};
};
LRUKReplacer
结构如下,node_store_
维护的frame id与LRUKNode节点的映射关系、current_timestamp_
记录当前的时间戳、curr_size_
表示当前可以驱逐的frame数量、replacer_size_
表示维护的frame数量、k_
为策略设置的K大小、latch_
用于实现并发安全。
class LRUKReplacer {
public:
explicit LRUKReplacer(size_t num_frames, size_t k);
DISALLOW_COPY_AND_MOVE(LRUKReplacer);
~LRUKReplacer() = default;
// need to implement
auto Evict(frame_id_t *frame_id) -> bool;
void RecordAccess(frame_id_t frame_id, AccessType access_type = AccessType::Unknown);
void SetEvictable(frame_id_t frame_id, bool set_evictable);
void Remove(frame_id_t frame_id);
auto Size() -> size_t;
private:
[[maybe_unused]] std::unordered_map<frame_id_t, LRUKNode> node_store_;
[[maybe_unused]] size_t current_timestamp_{0};
// 当前维护的页个数
[[maybe_unused]] size_t curr_size_{0};
[[maybe_unused]] size_t replacer_size_;
[[maybe_unused]] size_t k_;
[[maybe_unused]] std::mutex latch_;
};
接下来实现 LRUKReplacer
结构的四个函数
- LRUKReplacer::Evict
驱逐Replacer中的一个元素。首先一把大锁先加上(先最大化锁的粒度,保证逻辑正确再来优化)。然后遍历一下frame id对应的LRUKNode,如果目标元素可驱逐,获取其后向K距离,如果为正无穷,则放入数组中,如果不为正无穷更新最大的后向K距离frame id。
如果有后向K距离为正无穷的节点,则遍历数组驱逐其中最早一次的访问时间最早的frame,否则驱逐刚刚遍历得到的拥有最大的后向K距离frame id。
/*******************************************************
* @brief 淘汰一个元素
*
* @param frame_id
* @return true
* @return false
* @author Andromeda (ech0uname@qq.com)
* @date 2024-01-20
*******************************************************/
auto LRUKReplacer::Evict(frame_id_t *frame_id) -> bool {
// 加锁
std::lock_guard<std::mutex> access_lock(latch_);
bool find = false;
// k距离为无穷的页id
std::vector<size_t> inf_k_d_frame_id;
// 记录最大的k距离
size_t max_k_d = 0;
// 记录最大的k距离页id
frame_id_t max_k_d_id = replacer_size_;
// 遍历存储的node
for (auto &node : node_store_) {
// 该节点是否可淘汰
if (!node.second.GetEvictable()) {
continue;
}
size_t tmp = node.second.GetKDistance(current_timestamp_);
// 如果当前节点的k距离更大,更新页id
if (tmp > max_k_d) {
find = true;
max_k_d = tmp;
max_k_d_id = node.first;
}
// 如果k距离为无穷
if (tmp == UINT32_MAX) {
inf_k_d_frame_id.push_back(node.first);
}
}
*frame_id = max_k_d_id;
// 如果有inf
size_t min_k_d = UINT32_MAX;
for (size_t &i : inf_k_d_frame_id) {
// 可淘汰且最近访问时间小
if (node_store_[i].GetBackAccess() < min_k_d) {
min_k_d = node_store_[i].GetBackAccess();
*frame_id = i;
}
}
// 清空历史记录
if (find) {
node_store_[*frame_id].RemoveHistory();
node_store_[*frame_id].SetEvictable(false);
curr_size_--;
// node_store_.erase(*frame_id);
return true;
}
return false;
}
- LRUKReplacer::RecordAccess
给一个frame添加一个访问记录。如果frame_id存在,则直接更新历史记录并移动时间戳。如果frame_id不存在且合法,初始化一个frame_id对应的LRUKNode。
/*******************************************************
* @brief 访问一页
*
* @param frame_id
* @param access_type
* @author Andromeda (ech0uname@qq.com)
* @date 2024-01-20
*******************************************************/
void LRUKReplacer::RecordAccess(frame_id_t frame_id, [[maybe_unused]] AccessType access_type) {
// 加锁
std::lock_guard<std::mutex> access_lock(latch_);
// 如果页id不合法
if (static_cast<size_t>(frame_id) > replacer_size_) {
throw Exception("LRUKReplacer::RecordAccess: frame_id is invalid");
}
if (node_store_.find(frame_id) == node_store_.end()) {
// 节点已满
if (node_store_.size() == replacer_size_) {
return;
}
// 如果不存在,则添加
node_store_[frame_id] = LRUKNode(frame_id, k_);
}
// 给当前页添加访问历史
node_store_[frame_id].AddHistory(current_timestamp_);
// 时间自增
current_timestamp_++;
}
- LRUKReplacer::SetEvictable
frame_id的is_evictable_属性,这个没啥说的,注意更新 cur_size_
。
/*******************************************************
* @brief 设置是否可淘汰
*
* @param frame_id
* @param set_evictable
* @author Andromeda (ech0uname@qq.com)
* @date 2024-01-20
*******************************************************/
void LRUKReplacer::SetEvictable(frame_id_t frame_id, bool set_evictable) {
// 加锁
std::lock_guard<std::mutex> access_lock(latch_);
// 如果页id不合法
if (node_store_.find(frame_id) == node_store_.end()) {
throw Exception("LRUKReplacer::RecordAccess: frame_id is invalid");
}
if (!set_evictable && node_store_[frame_id].GetEvictable()) {
curr_size_--;
} else if (set_evictable && !node_store_[frame_id].GetEvictable()) {
curr_size_++;
}
node_store_[frame_id].SetEvictable(set_evictable);
}
- LRUKReplacer::Remove
不管后向K距离,直接驱逐一个frame(如果frame存在且可驱逐)。注意更新 curr_size_
。
/*******************************************************
* @brief 移除
*
* @param frame_id
* @author Andromeda (ech0uname@qq.com)
* @date 2024-01-20
*******************************************************/
void LRUKReplacer::Remove(frame_id_t frame_id) {
// 加锁
std::lock_guard<std::mutex> access_lock(latch_);
if (node_store_.find(frame_id) == node_store_.end()) {
return;
}
// 如果页id不合法或不可驱逐
if (!node_store_[frame_id].GetEvictable()) {
throw Exception("LRUKReplacer::Remove: frame_id can not be remove");
}
// 移除
node_store_[frame_id].RemoveHistory();
node_store_[frame_id].SetEvictable(false);
node_store_.erase(frame_id);
curr_size_--;
}
- LRUKReplacer::Size()
直接return cur_size_即可。
Task #2 - Disk Scheduler
第二个任务是实现一个磁盘调度程序。磁盘管理程序已经给出了,不需要我们自己实现,完成了对磁盘的读取与写入,
稍微看看DiskManager的部分实现吧。(GPT阅读)
1、构造函数,用于打开或创建数据库文件和日志文件。首先根据提供的数据库文件名确定日志文件名,然后打开或创建日志文件。接着在互斥锁的保护下打开或创建数据库文件。
/**
* Constructor: open/create a single database file & log file
* @input db_file: database file name
*/
DiskManager::DiskManager(const std::string &db_file) : file_name_(db_file) {
std::string::size_type n = file_name_.rfind('.');
if (n == std::string::npos) {
LOG_DEBUG("wrong file format");
return;
}
log_name_ = file_name_.substr(0, n) + ".log";
log_io_.open(log_name_, std::ios::binary | std::ios::in | std::ios::app | std::ios::out);
// directory or file does not exist
if (!log_io_.is_open()) {
log_io_.clear();
// create a new file
log_io_.open(log_name_, std::ios::binary | std::ios::trunc | std::ios::out | std::ios::in);
if (!log_io_.is_open()) {
throw Exception("can't open dblog file");
}
}
std::scoped_lock scoped_db_io_latch(db_io_latch_);
db_io_.open(db_file, std::ios::binary | std::ios::in | std::ios::out);
// directory or file does not exist
if (!db_io_.is_open()) {
db_io_.clear();
// create a new file
db_io_.open(db_file, std::ios::binary | std::ios::trunc | std::ios::out | std::ios::in);
if (!db_io_.is_open()) {
throw Exception("can't open db file");
}
}
buffer_used = nullptr;
}
2、DiskManager::ShutDown()
: 关闭所有文件流,即关闭数据库文件和日志文件。
/**
* Close all file streams
*/
void DiskManager::ShutDown() {
{
std::scoped_lock scoped_db_io_latch(db_io_latch_);
db_io_.close();
}
log_io_.close();
}
3、DiskManager::WritePage(page_id_t page_id, const char *page_data)
: 将指定页面的内容写入磁盘文件。函数首先获取页面在文件中的偏移量,然后将写入游标定位到该偏移量处,并写入指定大小的页面数据。最后,将文件内容刷新到磁盘。
/**
* Write the contents of the specified page into disk file
*/
void DiskManager::WritePage(page_id_t page_id, const char *page_data) {
std::scoped_lock scoped_db_io_latch(db_io_latch_);
size_t offset = static_cast<size_t>(page_id) * BUSTUB_PAGE_SIZE;
// set write cursor to offset
num_writes_ += 1;
db_io_.seekp(offset);
db_io_.write(page_data, BUSTUB_PAGE_SIZE);
// check for I/O error
if (db_io_.bad()) {
// std::cout << "write bad" << std::endl;
LOG_DEBUG("I/O error while writing");
return;
}
// std::cout << "write" << page_data << std::endl;
// needs to flush to keep disk file in sync
db_io_.flush();
}
4、DiskManager::ReadPage(page_id_t page_id, char *page_data)
: 将指定页面的内容读取到给定的内存区域中。函数首先获取页面在文件中的偏移量,然后将读取游标定位到该偏移量处,并读取指定大小的页面数据。如果读取过程中发生错误,函数会进行相应的错误处理。
/**
* Read the contents of the specified page into the given memory area
*/
void DiskManager::ReadPage(page_id_t page_id, char *page_data) {
std::scoped_lock scoped_db_io_latch(db_io_latch_);
int offset = page_id * BUSTUB_PAGE_SIZE;
// check if read beyond file length
if (offset > GetFileSize(file_name_)) {
LOG_DEBUG("I/O error reading past end of file");
// std::cerr << "I/O error while reading" << std::endl;
} else {
// std::cout << page_id << " " << strlen(page_data) << std::endl;
// set read cursor to offset
db_io_.seekp(offset);
db_io_.read(page_data, BUSTUB_PAGE_SIZE);
if (db_io_.bad()) {
// std::cout << "read bad" << std::endl;
LOG_DEBUG("I/O error while reading");
return;
}
// if file ends before reading BUSTUB_PAGE_SIZE
int read_count = db_io_.gcount();
if (read_count < BUSTUB_PAGE_SIZE) {
LOG_DEBUG("Read less than a page");
db_io_.clear();
// std::cerr << "Read less than a page" << std::endl;
memset(page_data + read_count, 0, BUSTUB_PAGE_SIZE - read_count);
}
}
}
日志操作目前不关注。
- DiskScheduler::Schedule
该函数的作用仅仅把DiskRequest放入请求队列。
void DiskScheduler::Schedule(DiskRequest r) { request_queue_.Put(std::move(r)); }
- DiskScheduler::ProcessDiskRequest
自己实现一个函数用于处理DiskRequest(调用disk_manager_完成读写操作)
void DiskScheduler::ProcessDiskRequest(DiskRequest r) {
// 写请求
if (r.is_write_) {
disk_manager_->WritePage(r.page_id_, r.data_);
} else {
// 读请求
disk_manager_->ReadPage(r.page_id_, r.data_);
}
r.callback_.set_value(true);
}
- DiskScheduler::StartWorkerThread
磁盘调度后台进程的函数。不断从request_queue_请求队列中取出DiskRequest,然后创建一个线程进行处理,使用join串行等待。
void DiskScheduler::StartWorkerThread() {
std::optional<DiskRequest> r;
while ((r = request_queue_.Get()) != std::nullopt) {
std::thread t = std::thread(&DiskScheduler::ProcessDiskRequest, this, std::move(r.value()));
t.join();
}
}
观察DiskScheduler的析构函数,向请求队列中放入 std::nullopt
,并等待后台处理线程结束来实现优雅的退出。因此 DiskScheduler::StartWorkerThread
函数的结束条件是 (r = request_queue_.Get()) != std::nullopt
。
DiskScheduler::~DiskScheduler() {
// Put a `std::nullopt` in the queue to signal to exit the loop
request_queue_.Put(std::nullopt);
if (background_thread_.has_value()) {
background_thread_->join();
}
}
Task #3 - Buffer Pool Manager
先看一下这些数据的作用吧。
/**
* BufferPoolManager reads disk pages to and from its internal buffer pool.
*/
class BufferPoolManager {
public:
/**
* @brief Creates a new BufferPoolManager.
* @param pool_size the size of the buffer pool
* @param disk_manager the disk manager
* @param replacer_k the LookBack constant k for the LRU-K replacer
* @param log_manager the log manager (for testing only: nullptr = disable logging). Please ignore this for P1.
*/
BufferPoolManager(size_t pool_size, DiskManager *disk_manager, size_t replacer_k = LRUK_REPLACER_K,
LogManager *log_manager = nullptr);
/**
* @brief Destroy an existing BufferPoolManager.
*/
~BufferPoolManager();
auto GetPoolSize() -> size_t { return pool_size_; }
auto GetPages() -> Page * { return pages_; }
auto NewPage(page_id_t *page_id) -> Page *;
auto NewPageGuarded(page_id_t *page_id) -> BasicPageGuard;
auto FetchPage(page_id_t page_id, AccessType access_type = AccessType::Unknown) -> Page *;
auto FetchPageBasic(page_id_t page_id) -> BasicPageGuard;
auto FetchPageRead(page_id_t page_id) -> ReadPageGuard;
auto FetchPageWrite(page_id_t page_id) -> WritePageGuard;
auto UnpinPage(page_id_t page_id, bool is_dirty, AccessType access_type = AccessType::Unknown) -> bool;
auto FlushPage(page_id_t page_id) -> bool;
void FlushAllPages();
auto DeletePage(page_id_t page_id) -> bool;
private:
/** Number of pages in the buffer pool. */
const size_t pool_size_;
/** The next page id to be allocated */
std::atomic<page_id_t> next_page_id_ = 0;
/** Array of buffer pool pages. */
Page *pages_;
/** Pointer to the disk sheduler. */
std::unique_ptr<DiskScheduler> disk_scheduler_ __attribute__((__unused__));
/** Pointer to the log manager. Please ignore this for P1. */
LogManager *log_manager_ __attribute__((__unused__));
/** Page table for keeping track of buffer pool pages. */
std::unordered_map<page_id_t, frame_id_t> page_table_;
/** Replacer to find unpinned pages for replacement. */
std::unique_ptr<LRUKReplacer> replacer_;
/** List of free frames that don't have any pages on them. */
std::list<frame_id_t> free_list_;
/** This latch protects shared data structures. We recommend updating this comment to describe what it protects. */
std::mutex latch_;
/**
* @brief Allocate a page on disk. Caller should acquire the latch before calling this function.
* @return the id of the allocated page
*/
auto AllocatePage() -> page_id_t;
void DeallocatePage(__attribute__((unused)) page_id_t page_id) {
// This is a no-nop right now without a more complex data structure to track deallocated pages
}
};
成员变量的描述:
-
pool_size_:Buffer Pool缓存的frame容量
-
next_page_id_:分配的下一page id(使用atomic保证原子性)
-
pages_:Buffer Pool缓存page数组
-
disk_scheduler_:磁盘调度器
-
log_manager_:日志管理器(不关注)
-
page_table_:维护page id到frame id的映射
-
-
free_list_:可用的frame id链表
-
latch_:用于保证并发安全
需要实现的函数描述:
-
NewPage:创建一个空的page
-
FetchPage:从Buffer Pool取出一个frame,如果没有则从磁盘读取
-
UnpinPage:减少对frame的引用
-
FlushPage:将page写回磁盘
-
FlushAllPages:将所有page写回磁盘
-
DeletePage:删除一个frame
frame id数量是固定的,Buffer Pool中只能维护1~n的frame id,这些frame id映射到不固定的page id
来一个一个实现
1、BufferPoolManager::NewPage
先从free_list_取出一个可用的frame id,如果没有可用的则使用replacer_驱逐一个frame,如果也没有可驱逐的直接返回nullptr。
找到可用的frame id之后,如果之前为脏页,先将脏页写回到磁盘,然后重新分配该frame的内存和引用计数并更新replacer_的记录。
/*******************************************************
* @brief 新建一页
*
* @param page_id
* @return Page*
* @author Andromeda (ech0uname@qq.com)
* @date 2024-01-24
*******************************************************/
auto BufferPoolManager::NewPage(page_id_t *page_id) -> Page * {
Page *page;
frame_id_t frame_id = -1;
std::scoped_lock lock(latch_);
if (!free_list_.empty()) {
// ! get frame id from free list
frame_id = free_list_.back();
free_list_.pop_back();
page = pages_ + frame_id;
} else {
// ! get frame id from replacer
if (!replacer_->Evict(&frame_id)) {
return nullptr;
}
page = pages_ + frame_id;
}
// ! write back dirty page
if (page->IsDirty()) {
auto promise = disk_scheduler_->CreatePromise();
auto future = promise.get_future();
disk_scheduler_->Schedule({true, page->GetData(), page->GetPageId(), std::move(promise)});
future.get();
// ! clean
page->is_dirty_ = false;
}
// ! alloc a page id
*page_id = AllocatePage();
// ! delete old map
page_table_.erase(page->GetPageId());
// ! add new map
page_table_.emplace(*page_id, frame_id);
// ! set page id
page->page_id_ = *page_id;
page->pin_count_ = 1;
page->ResetMemory();
// ! update replacer
replacer_->RecordAccess(frame_id);
replacer_->SetEvictable(frame_id, false);
return page;
}
2、BufferPoolManager::FetchPage
从Buffer Pool取出一页,如果page不在Buffer Pool中,和NewPage的逻辑类似,找到可用的frame id后,如果之前为脏页,先将脏页写回到磁盘,然后重新分配该frame的内存(与NewPage不同,这里是发起一个磁盘读取请求来更新frame的内存)和引用计数并更新replacer_的记录。如果page在Buffer Pool中,直接更新引用计数并更新replacer_的记录。
/*******************************************************
* @brief 取出一页,如果 buffer pool 没有则从磁盘读取
*
* @param page_id
* @param access_type
* @return Page*
* @author Andromeda (ech0uname@qq.com)
* @date 2024-01-24
*******************************************************/
auto BufferPoolManager::FetchPage(page_id_t page_id, [[maybe_unused]] AccessType access_type) -> Page * {
if (page_id == INVALID_PAGE_ID) {
return nullptr;
}
// ! if exist
std::scoped_lock lock(latch_);
if (page_table_.find(page_id) != page_table_.end()) {
// ! get page
auto frame_id = page_table_[page_id];
auto page = pages_ + frame_id;
// ! uodate replacer
replacer_->RecordAccess(frame_id);
replacer_->SetEvictable(frame_id, false);
// ! update pin count
page->pin_count_ += 1;
return page;
}
// ! if not exist
Page *page;
frame_id_t frame_id = -1;
if (!free_list_.empty()) {
// ! get frame id from free list
frame_id = free_list_.back();
free_list_.pop_back();
page = pages_ + frame_id;
} else {
// ! get frame id from replacer
if (!replacer_->Evict(&frame_id)) {
return nullptr;
}
page = pages_ + frame_id;
}
// ! write back dirty page
if (page->IsDirty()) {
auto promise = disk_scheduler_->CreatePromise();
auto future = promise.get_future();
disk_scheduler_->Schedule({true, page->GetData(), page->GetPageId(), std::move(promise)});
future.get();
// ! clean
page->is_dirty_ = false;
}
// ! erase old map
page_table_.erase(page->GetPageId());
// ! add new map
page_table_.emplace(page_id, frame_id);
// ! update page
page->page_id_ = page_id;
page->pin_count_ = 1;
page->ResetMemory();
// ! update replacer
replacer_->RecordAccess(frame_id);
replacer_->SetEvictable(frame_id, false);
// ! read page from disk
auto promise = disk_scheduler_->CreatePromise();
auto future = promise.get_future();
disk_scheduler_->Schedule({false, page->GetData(), page->GetPageId(), std::move(promise)});
future.get();
return page;
}
3、BufferPoolManager::UnpinPage
如果page不在Buffer Pool中,直接返回false。否则先检查引用计数,如果为0,直接返回false,如果不为0,设置脏位为 is_dirty
同时减少引用计数,如果减为0,将该frame设为可驱逐。
/*******************************************************
* @brief 减少对一页的引用
*
* @param page_id
* @param is_dirty
* @param access_type
* @return true
* @return false
* @author Andromeda (ech0uname@qq.com)
* @date 2024-01-24
*******************************************************/
auto BufferPoolManager::UnpinPage(page_id_t page_id, bool is_dirty, [[maybe_unused]] AccessType access_type) -> bool {
if (page_id == INVALID_PAGE_ID) {
return false;
}
// ! if exist
std::scoped_lock lock(latch_);
if (page_table_.find(page_id) != page_table_.end()) {
// ! get page
auto frame_id = page_table_[page_id];
auto page = pages_ + frame_id;
// ! set dirty
if (is_dirty) {
page->is_dirty_ = is_dirty;
}
// ! if pin count is 0
if (page->GetPinCount() == 0) {
return false;
}
// ! decrement pin count
page->pin_count_ -= 1;
if (page->GetPinCount() == 0) {
replacer_->SetEvictable(frame_id, true);
}
return true;
}
return false;
}
4、BufferPoolManager::FlushPage和BufferPoolManager::FlushAllPages
这个就是把对应的page写回磁盘即可,注意设置脏位为false。
/*******************************************************
* @brief 将一页写回
*
* @param page_id
* @return true
* @return false
* @author Andromeda (ech0uname@qq.com)
* @date 2024-01-24
*******************************************************/
auto BufferPoolManager::FlushPage(page_id_t page_id) -> bool {
if (page_id == INVALID_PAGE_ID) {
return false;
}
std::scoped_lock lock(latch_);
if (page_table_.find(page_id) == page_table_.end()) {
return false;
}
// ! get page
auto page = pages_ + page_table_[page_id];
// ! write back
auto promise = disk_scheduler_->CreatePromise();
auto future = promise.get_future();
disk_scheduler_->Schedule({true, page->GetData(), page->GetPageId(), std::move(promise)});
future.get();
// ! clean
page->is_dirty_ = false;
return true;
}
/*******************************************************
* @brief 将所有页写回
*
* @author Andromeda (ech0uname@qq.com)
* @date 2024-01-24
*******************************************************/
void BufferPoolManager::FlushAllPages() {
std::scoped_lock lock(latch_);
for (size_t i = 0; i < pool_size_; i++) {
auto page = pages_ + i;
if (page->GetPageId() == INVALID_PAGE_ID) {
continue;
}
// ! write back
auto promise = disk_scheduler_->CreatePromise();
auto future = promise.get_future();
disk_scheduler_->Schedule({true, page->GetData(), page->GetPageId(), std::move(promise)});
future.get();
page->is_dirty_ = false;
}
}
5、BufferPoolManager::DeletePage
、replacer_
_/*******************************************************
* @brief 删除页
*
* @param page_id
* @return true
* @return false
* @author Andromeda (ech0uname@qq.com)
* @date 2024-01-24
*******************************************************/
auto BufferPoolManager::DeletePage(page_id_t page_id) -> bool {
if (page_id == INVALID_PAGE_ID) {
return true;
}
// ! page exist
std::scoped_lock lock(latch_);
if (page_table_.find(page_id) != page_table_.end()) {
// ! get page
auto frame_id = page_table_[page_id];
auto page = pages_ + frame_id;
// ! if can not delete
if (page->GetPinCount() > 0) {
return false;
}
// ! delete page
page_table_.erase(page_id);
free_list_.push_back(frame_id);
replacer_->Remove(frame_id);
// ! reset page memory
page->ResetMemory();
page->page_id_ = INVALID_PAGE_ID;
page->is_dirty_ = false;
page->pin_count_ = 0;
}
DeallocatePage(page_id);
return true;
}
性能优化
从头到尾都是直接上一把大锁,后面还是要针对锁的粒度进行一些优化的。
- 最新
- 最热
只看作者