CS15445-lab1

实验1-BufferPoolManager

实验要求

第一个实验任务需要我们实现一个缓存池，需要保证线程安全（使用锁保证）

任务一：LRU替换算法

任务简介

需要我们在src/include/buffer/lru_replacer.h和src/buffer/lru_replacer.cpp这两个文件中完成代码编写。LRUReplacer类是继承自Replacer类。每一个LRURplacer初始化时不包含任何一个frame条目，只有在unppined的进程释放某一个frame后，该frame条目才会被添加进入LRURplacer中。需要实现的方法：

Victim(T*):移除LRURplacer中最近未访问的对象，把淘汰的条目信息放到输出变量中并返回True，如果Replacer是空的就返回False。
Pin(T):当一个页面被BufferPoolManager固定，需要在LRUReplacer中把对应的frame条目移除。
Unpin(T):这个方法会在一个页面的计数器pin_count变为0时被调用。会把对应页面的frame添加进入LRURplacer中，观察测试文件发现unpin不会更新已经存在的条目在lru队列中的位置。
Size():返回当前在LRURplacer中的条目个数。

实现思路

头文件：为了实现LRU替换算法，开始考虑使用c++标准库中的list数据结构，实际上就是一个链表，每次把最新添加的frame条目添加到链表头。为了加快淘汰时的速度，使用hashmap来记录每一个链表结点的位置信息便于快速删除。latch变量使用互斥锁保证线程安全，capacity变量代表lru队列中的frame条目数。

// src/include/buffer/lru_replacer.h
private:
// TODO(student): implement me!
std::list<frame_id_t> lru_queue;
std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> quick_map;
std::mutex latch;
size_t capacity;

Victim方法实现：

auto LRUReplacer::Victim(frame_id_t *frame_id) -> bool {
//lock
latch.lock();
//if lru_queue is empty
if(lru_queue.empty()){
    latch.unlock();
    return false;
}

//delete frame which accessed least currently
frame_id_t del_frame = lru_queue.back();
quick_map.erase(del_frame);
lru_queue.pop_back();
*frame_id = del_frame;

//unlock
latch.unlock();
return true;
}

Pin方法实现：

void LRUReplacer::Pin(frame_id_t frame_id) {
    latch.lock();
    //delete frame_id
    if(quick_map.count(frame_id)){
        quick_map.erase(frame_id);
        lru_queue.remove(frame_id);
    }
    latch.unlock();
}

Unpin方法实现：

void LRUReplacer::Unpin(frame_id_t frame_id) {
    latch.lock();
    //add frame_id
    if (quick_map.count(frame_id)) {
        latch.unlock();
        return;
    }
    //oversize
    while (Size() >= capacity) {
        frame_id_t del_frame = lru_queue.front();
        quick_map.erase(del_frame);
        lru_queue.remove(del_frame);
    }
    // insert
    lru_queue.push_front(frame_id);
    quick_map[frame_id] = lru_queue.begin();

    latch.unlock();
}

修改test/buffer/lru_replacer_test.cpp中的TEST参数，去掉DISABLE参数后在build目录下执行：

1 2	make lru_replacer_test ./test/lru_replacer_test

最终显示测试通过。

任务二：缓存池管理

任务简介

缓存池管理器是一个从磁盘管理器获取数据库的页面信息并且加载到内存中，同时也会进行缺页中断来进行内存空间大小维护。DiskManager部分需要我们进行完成，该模块的主要目的是向磁盘进行数据读写。

最终需要我们完成src/include/buffer/buffer_pool_manager_instance.h和src/buffer/buffer_pool_manager_instance.cpp这两个文件中的以下几个方法：

FetchPageImpl(page_id)：如果在未分配队列中并且所有其他的页面都是处在pinned的状态时，需要返回null值。
NewPageImpl(page_id)：分配一个新的页面
UnpinPageImpl(page_id, is_dirty)
FlushPageImpl(page_id)：清空一个页面，无论其是否处在被pinned的状态下
DeletePageImpl(page_id)
FlushAllPagesImpl()

任务分析

首先观察.h文件中的变量并分析其作用：

pages_变量：代表缓存池中的page页。
disk_manager变量：指向一个磁盘管理器的指针。
log_manager变量：指向一个日志管理器的指针。
page_table变量：追踪所有在缓存池中的页面。
replacer变量：进行替换算法的替换器。
free_list变量：在内存中但是没有被使用的页面号。
在编写代码之前需要理解一些参数的具体含义：
首先，整个过程是需要把在物理块中的存储块映射到内存中。page_id_t代表了物理块在硬盘中的位置，frame_id代表了对应的page页在内存中的位置，内存中的页是以数组的形式进行存储的。相当于frame_id代表了内存池中的偏移页编号
buffer_pool_manager_instance.h中的变量介绍：
1. pages_:指向了内存池的起始页地址，后续需要访问内存池中的某一页，只需要通过pages[frame_id]的方式进行访问
2. page_table_:记录了当前的物理块映射在内存池中的信息
3. replacer_:这里是我们之前实现的页淘汰器
4. free_list_:记录了当前空余页的信息
5. latch:互斥锁

接下来根据提示完成代码编写：

FetchPageImpl方法实现：

auto BufferPoolManagerInstance::FetchPgImp(page_id_t page_id) -> Page * {
    latch_.lock();
    // 1.     Search the page table for the requested page (P).
    auto iter = page_table_.find(page_id);

    if (iter != page_table_.end()) {
        frame_id_t frame_id = iter->second;
        Page *page = &pages_[frame_id];
        page->pin_count_++;
        replacer_->Pin(frame_id);
        latch_.unlock();
        return page;
    }
    frame_id_t frame_id = -1;
    Page *page = nullptr;
    if (!free_list_.empty()) {
        frame_id = free_list_.front();
        free_list_.pop_front();
        page = &pages_[frame_id];
    } else if (replacer_->Victim(&frame_id)) {
        page = &pages_[frame_id];

        if (page->IsDirty()) {
        disk_manager_->WritePage(page->GetPageId(), page->GetData());
        }
        page_table_.erase(page->GetPageId());
    } else {
        latch_.unlock();
        return nullptr;
    }

    page->page_id_ = page_id;
    page->pin_count_ = 1;
    page->is_dirty_ = false;

    disk_manager_->ReadPage(page_id, page->GetData());

    page_table_[page_id] = frame_id;
    replacer_->Pin(frame_id);
    latch_.unlock();
    return page;
}

NewPageImpl实现：

auto BufferPoolManagerInstance::NewPgImp(page_id_t *page_id) -> Page * {
    latch_.lock();
    // 0.   Make sure you call AllocatePage!
    //  printf("new pages:%ld\n",page_table_.size());
    // 1.   If all the pages in the buffer pool are pinned, return nullptr.
    frame_id_t frame_id = -1;
    Page *page = nullptr;
    if (!free_list_.empty()) {
        frame_id = free_list_.front();
        free_list_.pop_front();
        page = &pages_[frame_id];
    } else if (replacer_->Victim(&frame_id)) {
        page = &pages_[frame_id];
        if (page->IsDirty()) {
        disk_manager_->WritePage(page->GetPageId(), page->GetData());
        }
        page_table_.erase(page->GetPageId());
    } else {
        latch_.unlock();
        return nullptr;
    }

    page_id_t new_page_id = AllocatePage();
    page->page_id_ = new_page_id;
    page->pin_count_ = 1;
    page->is_dirty_ = false;
    page->ResetMemory();

    page_table_[new_page_id] = frame_id;
    *page_id = new_page_id;
    replacer_->Pin(frame_id);
    latch_.unlock();
    return page;
}

UnpinPageImpl方法实现：

auto BufferPoolManagerInstance::UnpinPgImp(page_id_t page_id, bool is_dirty) -> bool {
    latch_.lock();
    //not find in page table
    //  printf("unpin pages:%ld\n",page_table_.size());
    if(page_table_.find(page_id) == page_table_.end()){
        latch_.unlock();
        return false;
    }
    else{
        frame_id_t unpin_frame_id_ = page_table_[page_id];
        Page *unpin_page_ = &pages_[unpin_frame_id_];
        if(is_dirty){
        unpin_page_->is_dirty_ = true;
        }
        if(unpin_page_->pin_count_ == 0){
        latch_.unlock();
        return false;
        }
        else if(unpin_page_->pin_count_ == 1){
        unpin_page_->pin_count_ = 0;
        replacer_->Unpin(unpin_frame_id_);
    //      printf("%d\n",page_id);
        page_table_.erase(page_id);
        latch_.unlock();
        return true;
        }
        else{
        unpin_page_->pin_count_--;
        latch_.unlock();
        return true;
        }
    }
}

FlushPageImpl方法实现：

auto BufferPoolManagerInstance::FlushPgImp(page_id_t page_id) -> bool {
    // Make sure you call DiskManager::WritePage!
    // find if page is already in page_table_
    latch_.lock();
    if (page_id == INVALID_PAGE_ID) {
        latch_.unlock();
        return false;
    }
    auto iter = page_table_.find(page_id);
    if (iter == page_table_.end()) {
        latch_.unlock();
        return false;
    }
    frame_id_t frame_id = iter->second;
    Page *page = &pages_[frame_id];
    disk_manager_->WritePage(page_id, page->GetData());
    page->is_dirty_ = false;
    latch_.unlock();
    return true;
    }

DeletePageImpl方法实现：

auto BufferPoolManagerInstance::DeletePgImp(page_id_t page_id) -> bool {
    latch_.lock();
    // 0.   Make sure you call DeallocatePage!
    // 1.   Search the page table for the requested page (P).
    DeallocatePage(page_id);
    auto iter = page_table_.find(page_id);
    if (iter == page_table_.end()) {
        // DeallocatePage(page_id);
        latch_.unlock();
        return true;
    }
    frame_id_t frame_id = iter->second;
    Page *page = &pages_[frame_id];
    if (page->GetPinCount() > 0) {
        latch_.unlock();
        return false;
    }
    if (page->IsDirty()) {
        disk_manager_->WritePage(page->GetPageId(), page->GetData());
    }
    replacer_->Pin(frame_id);
    page_table_.erase(page->page_id_);
    page->is_dirty_ = false;
    page->pin_count_ = 0;
    page->page_id_ = INVALID_PAGE_ID;
    page->ResetMemory();
    free_list_.push_back(frame_id);
    latch_.unlock();
    return true;
}

FlushAllPagesImpl方法实现：

void BufferPoolManagerInstance::FlushAllPgsImp() {
    // You can do it!
    latch_.lock();
    auto iter = page_table_.begin();
    while (iter != page_table_.end()) {
        page_id_t page_id = iter->first;
        frame_id_t frame_id = iter->second;
        Page *page = &pages_[frame_id];
        disk_manager_->WritePage(page_id, page->GetData());
        iter++;
    }
    latch_.unlock();
}

修改test/buffer/buffer_pool_manager_instance_test.cpp中的TEST参数，去掉DISABLE参数后在build目录下执行：

1 2	make buffer_pool_manager_instance_test ./test/buffer_pool_manager_instance_test

最终显示测试通过。

任务三：并发缓存池管理

任务简介

之前编写的缓存池都添加了互斥锁变量latch，保证了线程安全，这有可能导致多个线程对同一个缓存池产生竞争的情况。一种解决办法是在一个系统中创建多个缓存池，每一个缓存池都拥有自己的互斥锁。

这里使用页面id来决定使用哪一个缓存池实例进行保存。针对每一个操作并发缓存池管理器会选择一个缓存池实例进行操作。这里使用页面编号对缓存池个数取模来确定页面存储在某个缓存池中。

实现思路

除了newpage那里需要稍作修改，其余的部分基本上就是一行了事，下面贴出添加的数据结构：

private:
 std::vector<BufferPoolManager*> parallel_buffer_;
 size_t num_instances_;
 size_t pool_size_;
 std::atomic<size_t> start_ = 0;

然后是NewPgImp方法的实现：

auto ParallelBufferPoolManager::NewPgImp(page_id_t *page_id) -> Page * {
  // create new page. We will request page allocation in a round robin manner from the underlying
  // BufferPoolManagerInstances
  // 1.   From a starting index of the BPMIs, call NewPageImpl until either 1) success and return 2) looped around to
  // starting index and return nullptr
  // 2.   Bump the starting index (mod number of instances) to start search at a different BPMI each time this function
  // is called
  for (size_t i = start_; i < start_ + num_instances_; i++) {
    Page *page = parallel_buffer_[i % num_instances_]->NewPage(page_id);
    if (page != nullptr) {
      start_ = i % num_instances_;
      return page;
    }
  }
  return nullptr;
}

最终进行测试

1 2	make parallel_buffer_pool_manager_test ./test/parallel_buffer_pool_manager_test

显示测试全部通过

实验一小结

这个实验主要了解了数据库页面在内存中是如何进行管理的，很好的帮助我理解了磁盘页面刷回的知识。