存储管理

任务一 缓冲池管理器

1.1 磁盘存储管理器

本任务要求补全DiskManager类，要求实现读写指定页面、以及对文件进行操作。

前置知识： linux 系统下的 write ，open ，read ，unlink ，close ，leek 等函数。

注意事项： 一些系统函数比如 open 可能需要权限，所以最好在 root 用户下进行实验。还有对于什么时候抛出什么异常，文档里没细说，最后测试的时候根据测试文件的代码一个一个补充即可。

write_page 实现：

文档提示里已经告诉了我们每页的字节大小是个已定义的常数 PAGE_SIZE ，通过 page_no * PAGE_SIZE 即可确定要写入的位置的字节偏移量，再通过 leek 定位， 最后调用 write 函数进行写入即可。

void DiskManager::write_page(int fd, page_id_t page_no, const char *offset, int num_bytes) {
    off_t off = page_no * PAGE_SIZE;
    lseek(fd, off, SEEK_SET);
    int num = write(fd, offset, num_bytes);
    if (num != num_bytes) {
        throw InternalError("DiskManager::write_page Error");
    }
}

read_page 实现：

思路和上一个类似，让文件定位到要读的位置后，再调用 read 函数即可。

void DiskManager::read_page(int fd, page_id_t page_no, char *offset, int num_bytes) {
    off_t off = page_no * PAGE_SIZE;
    lseek(fd, off, SEEK_SET);
    int num = read(fd, offset, num_bytes);
    if (num != num_bytes) {
        throw InternalError("DiskManager::read_page Error");
    }
}

create_file 实现：

需要判断文件是否存在，当然我对于我的代码还有疑问，主要在于用 open 去新建一个文件的细节，虽然它确实通过了测试，但 gpt 告诉我 open(path.c_str(), O_CREAT); 没有指定打开模式的话，是不会创建文件的。

upd: 亲自去做了测试，发现参数只设置为 O_CREAT ，当 open 的文件不存在时，依旧会新建一个文件并打开，也就是返回值不是 -1 。 gpt 给的解释是这是未定义行为，libc 实现将其理解为了 O_CREAT | O_RDONLY 。

void DiskManager::create_file(const std::string &path) {
    if (!is_file(path)) {
        open(path.c_str(), O_CREAT);
        close(fd);
    } else
        throw FileExistsError("");
}

open_file 实现：

从这里开始我们就必须去维护打开文件的集合，事实上 gpt 告诉我 linux 是允许多次打开一个文件的，彼此之间相互独立，但我们的数据库似乎并不允许， 所以需要我们维护当前打开的文件集合，可以看到 disk_manager.h 文件中有如下定义：

// 文件打开列表，用于记录文件是否被打开
std::unordered_map<std::string, int> path2fd_;  //<Page文件磁盘路径,Page fd>哈希表
std::unordered_map<int, std::string> fd2path_;  //<Page fd,Page文件磁盘路径>哈希表

所以我们直接用这两个哈希表去维护就好了。

int DiskManager::open_file(const std::string &path) {
    if (!is_file(path)) {
        throw FileNotFoundError("");
    }
    if (!path2fd_.count(path)) {
        int fd = open(path.c_str(), O_RDWR);
        path2fd_[path] = fd;
        fd2path_[fd] = path;
    }
    return path2fd_[path];
}

close_file 实现：

注意维护打开文件集合即可。

void DiskManager::close_file(int fd) {
    if (fd2path_.count(fd)) {
        close(fd);
        path2fd_.erase(fd2path_[fd]);
        fd2path_.erase(fd);
    }
}

destory_file 实现：

这一关只需要注意当我们要删除的文件还在打开状态时，要先关闭再删除。

void DiskManager::destroy_file(const std::string &path) {
    if (!is_file(path)) throw FileNotFoundError("");

    if (path2fd_.count(path)) {
        close_file(path2fd_[path]);
    }

    unlink(path.c_str());
}

1.2 缓冲池替换策略

本任务要求补全Replacer类，并且实现的替换策略为最近最少使用（LRU）算法。

前置知识： 了解页(page) ，帧(frame)，pin，unpin 的概率。 注意事项： 每个函数都需要有 std::scoped_lock lock{latch_}; 这条语句，作用大概是用于避免死锁，但具体原理我也不太清楚。

事实上只要知道上述概念再结合测试就能很快完成。

victim 实现：

头文件中给我们提供了 LRUlisk_ 这个链表维护没有被固定的帧的最近访问时间顺序，其中链头是最先访问的。 然后还提供了 LRUhash_ 这个哈希表便于快速定位到某帧对应的迭代器。

根据上述内容可知：弹出尾部元素即可。

bool LRUReplacer::victim(frame_id_t* frame_id) {
    // C++17 std::scoped_lock
    // 它能够避免死锁发生，其构造函数能够自动进行上锁操作，析构函数会对互斥量进行解锁操作，保证线程安全。
    std::scoped_lock lock{latch_};  //  如果编译报错可以替换成其他lock

    if (!LRUlist_.empty()) {
        *frame_id = LRUlist_.back();
        LRUhash_.erase(LRUlist_.back());
        LRUlist_.pop_back();
    } else
        return false;
    return true;
}

pin 实现：

该函数用于固定一个帧，避免多线程操作中一边还在访问，另一边已经将其替换了。

实现上其实就是将其从链表和哈希表中删去，注意删去前要保证其存在。

void LRUReplacer::pin(frame_id_t frame_id) {
    std::scoped_lock lock{latch_};
    if (LRUhash_.count(frame_id)) {
        auto it = LRUhash_[frame_id];
        LRUlist_.erase(it);
        LRUhash_.erase(frame_id);
    }
}

unpin 实现：

用于解除对一个帧的固定，实现上很简单，但有一个让我疑惑的点就是多次 unpin 同一个帧时居然不需要重新放在链头，只是单纯的将其忽视（没办法，测试样例是这样写的）。

void LRUReplacer::unpin(frame_id_t frame_id) {
    std::scoped_lock lock{latch_};
    if (!LRUhash_.count(frame_id)) {
        LRUlist_.push_front(frame_id);
        LRUhash_[frame_id] = LRUlist_.begin();
    }
}

1.3 缓冲池管理器

本任务要求补全BufferPoolManager类，其负责管理缓冲池中的页面与磁盘文件中的页面之间的来回移动。

相比于前两个任务，这一关多了一个难点就是处理并发， Todo 指明了两个加锁的地方，虽然我目前不是特别理解其中的逻辑，并且似乎只在哪个位置加锁还是会出现并发问题。 所以选择了一个无脑的方法：就是把每个作为上层接口的函数都加上锁。

前置知识： 最好熟悉并发和加锁的逻辑，否则只能像我一样无脑加锁，然后需要了解 PageId 这个类对应于文件中具体某一页， 而 Page 这个类对应于缓冲池的一帧，所以 Page 会有 PageId 类成员用于标记该帧具体是哪个文件的哪个页。 最后是本关最后一个测试点需要跑 6s ，所以不需要着急。

find_victim_page 实现：

需要我们实现返回一个缓冲池中的可用帧的函数，思路很简单，跟着 Todo 做即可。

bool BufferPoolManager::find_victim_page(frame_id_t* frame_id) {
    if (free_list_.empty()) {
        // 缓冲池已满
        return replacer_->victim(frame_id);
    } else {
        *frame_id = free_list_.front();
        free_list_.pop_front();
    }
    return true;
}

update_page 实现：

实现一个替换可用帧的函数，通常调用了 find_victim_page 函数后就需要调用此函数。

void BufferPoolManager::update_page(Page* page, PageId new_page_id, frame_id_t new_frame_id) {
    if (page->is_dirty()) {
        disk_manager_->write_page(page->id_.fd, page->id_.page_no, page->data_, PAGE_SIZE);
        page->is_dirty_ = false;
    }

    page_table_.erase(page->get_page_id());
    page_table_[new_page_id] = new_frame_id;

    page->reset_memory();
    page->id_ = new_page_id;
}

以上两个均属于辅助函数，减少重复的逻辑。

fetch_page 实现：

获取需要的页，类似于访问磁盘某页的数据，那我自然需要把它放到缓冲池，涉及到的逻辑有点多， 跟着 Todo 做不难。

Page* BufferPoolManager::fetch_page(PageId page_id) {
    std::scoped_lock lock{latch_};
    Page* targetPage = nullptr;

    if (page_table_.count(page_id)) {
        auto fid = page_table_[page_id];
        replacer_->pin(fid);
        targetPage = &(pages_[fid]);
        targetPage->pin_count_++;
    }
    else {
        frame_id_t fid(INVALID_FRAME_ID);
        if (!find_victim_page(&fid)) return nullptr;
        targetPage = &(pages_[fid]);
        update_page(targetPage, page_id, fid);
        disk_manager_->read_page(page_id.fd, page_id.page_no, targetPage->data_, PAGE_SIZE);
        replacer_->pin(fid);
        targetPage->pin_count_ = 1;
    }
    return targetPage;
}

unpin_page 实现：

该函数用于取消某一帧的一次固定，类似于修改完某页的操作，所以当 is_dirty == true ，也就是只要有一次修改了帧， 都需要将该帧标记为脏。

bool BufferPoolManager::unpin_page(PageId page_id, bool is_dirty) {

    std::scoped_lock lock{latch_};

    if (!page_table_.count(page_id)) return false;
    auto fid = page_table_[page_id];
    Page* targetPage = &(pages_[fid]);

    if (targetPage->pin_count_ == 0) return false;

    targetPage->pin_count_--;
    if (targetPage->pin_count_ == 0) {
        replacer_->unpin(fid);
    }

    if (is_dirty) {
        targetPage->is_dirty_ = true;
    }
    return true;
}

flush_page 实现：

该函数用于将当前帧的数据无条件地写回磁盘，注意写回磁盘后 is_dirty 需要标记为 false 。

bool BufferPoolManager::flush_page(PageId page_id) {
    std::scoped_lock lock{latch_};

    if (!page_table_.count(page_id)) {
        return false;
    }
    frame_id_t fid = page_table_[page_id];
    Page* page = &(pages_[fid]);

    disk_manager_->write_page(page->id_.fd, page->id_.page_no, page->data_, PAGE_SIZE);
    page->is_dirty_ = false;

    return true;
}

new_page 实现：

该函数用于分配文件的一个新的页并访问，所以要调用之前实现的接口 allocate_page ，其余按照 Todo 完成问题不大。

Page* BufferPoolManager::new_page(PageId* page_id) {
    std::scoped_lock lock{latch_};
    frame_id_t fid(INVALID_FRAME_ID);

    if (!find_victim_page(&fid)) return nullptr;

    page_id->page_no = disk_manager_->allocate_page(page_id->fd);

    Page* page = &(pages_[fid]);

    update_page(page, *page_id, fid);

    replacer_->pin(fid);
    page->pin_count_ = 1;

    return page;
}

delete_page 实现：

逻辑上按照 Todo 去实现问题不大，最容易被忽视的地方在于进行删除该页时也算访问操作，所以必须固定避免并发冲突。 当然注意一种情况需要 unpin 。

bool BufferPoolManager::delete_page(PageId page_id) {
    std::scoped_lock lock{latch_};
    if (!page_table_.count(page_id)) {
        return true;
    }

    auto fid = page_table_[page_id];
    replacer_->pin(fid);

    Page* page = &pages_[fid];
    if (page->pin_count_ != 0) {
        replacer_->unpin(fid);
        return false;
    }

    disk_manager_->write_page(page->id_.fd, page->id_.page_no, page->data_, PAGE_SIZE);
    page_table_.erase(page_id);
    free_list_.push_back(fid);

    return true;
}

flush_all_pages 实现：

直接 for 一遍即可，当然我也不确定中间判断 page_no 的条件必不必要，反正加不加都能过测试。

void BufferPoolManager::flush_all_pages(int fd) {
    for (size_t i = 0; i < pool_size_; i++) {
        Page* page = &pages_[i];
        if (page->id_.fd == fd && page->id_.page_no != INVALID_PAGE_ID) {
            disk_manager_->write_page(page->id_.fd, page->id_.page_no, page->data_, PAGE_SIZE);
            page->is_dirty_ = false;
        }
    }
}

任务二 记录管理器

2.1 记录操作

本任务要求补全RMFileHandle类，其负责对文件中的记录进行操作。

前置知识： 完成代码前了解一点该数据库的存储结构大有帮助。首先每张表都有一个表文件，但存储的基本单位是页， 每条记录就存储于页上，并且第一个页不存储记录，用于记录表的相关信息，未满的页彼此之间会构成一张支持头插法的链表，第一个页中会记录链表头， 存储记录的页在头部会先维护链表的后继和该页具体信息（比如该页已经写了多少条记录以及哪些位置是有效的记录），剩余的位置才用于存放具体的记录。 更具体地，在此处用到了 Bitmap 这个类记录哪些位置属于有效的记录，我们可以调用它实现了静态函数完成我们想要的功能。