CMU15445-Lab1

2023.5.1完成4个折磨的实验。今日，对lab1内容进行重温，**请不要将实现代码公开，尊重 Andy 和 TAs 的劳动成果！**需要代码的可以联系我~

Lab1中Buffer Pool Manager这个实验最可以体现出整体的思想。

Buffer Pool Manager

图片摘自：做个数据库：2022 CMU15-445 Project1 Buffer Pool Manager

Buffer Pool Manager 里有几个重要的成员：

• pages：buffer pool 中缓存 pages 的指针数组
• disk_manager：框架提供，可以用来读取 disk 上指定 page id 的 page 数据，或者向 disk 上给定 page id 对应的 page 里写入数据
• page_table：刚才实现的 Extendible Hash Table，用来将 page id 映射到 frame id，即 page 在 buffer pool 中的位置
• replacer：刚才实现的 LRU-K Replacer，在需要驱逐 page 腾出空间时，告诉我们应该驱逐哪个 page
• free_list：空闲的 frame 列表

Buffer Pool Manager 给上层调用者提供的两个最重要的功能是 new page 和 fetch page。

new page：创建新的page, 返回其指针与page_id

这里给出思路：

1. 上锁以保护缓冲池管理器的并发访问
   使用 std::scoped_lock< std::mutex > 来对缓冲池进行加锁，确保并发访问时的线程安全。

2. 检查缓冲池中页面是否都不可驱逐
   遍历缓冲池中的所有页面，检查是否有页面的 Pin Count 为 0（即页面没有被锁定，可以被驱逐）。
   如果所有页面的 Pin Count 都大于 0（即没有页面可以被驱逐），则返回 nullptr，表示没有可用的页面。

3. 分配一个新的页面 ID
   如果有页面可以被驱逐，调用 AllocatePage() 函数来分配一个新的页面 ID，并将其赋值给传入的 page_id 指针。

4. 优先从 free_list_ 中分配页面
   检查 free_list_ 是否非空：
   如果 free_list_ 中有空闲的框架（Frame），从 free_list_ 取出一个框架（Frame）ID 并从 free_list_ 中移除。
   建立哈希表关系：将新的页面 ID 和框架 ID 插入到页面表中。
   更新 LRU-K 替换器：记录该页面的访问，并设置该页面为不可驱逐（因为马上要用到该页面）。
   初始化页面：将页面 ID 分配给缓冲池数组中的该框架，并设置 Pin Count 为 1，表示页面被锁定。
   返回该页面的指针。

5. 从 LRU-K 替换器中选择页面进行驱逐
   如果 free_list_ 中没有空闲的框架，那么需要从 LRU-K 替换器 中 驱逐一个页面。
   调用 Evict() 方法让 LRU-K 替换器选择一个可驱逐的框架 ID。

6. 处理驱逐的页面
   获取驱逐页面的页面 ID，并检查该页面是否脏页（is_dirty_ 标志）。
   如果是脏页，则将页面的数据写回磁盘（调用 disk_manager_->WritePage()），并将脏页标志清除（is_dirty_ = false）。
   移除旧的页面表信息：将该页面 ID 从页面表中移除。
   清空旧页面的内存：重置该页面的内存内容（调用 ResetMemory()）。

7. 将新页面插入到驱逐的框架中
   建立哈希表关系：将新的页面 ID 和被驱逐的框架 ID 插入到页面表中。
   更新 LRU-K 替换器：记录该框架的访问，并设置该页面为不可驱逐。
   初始化页面：将新的页面 ID 分配给缓冲池数组中的该框架，并设置 Pin Count 为 1，表示页面被锁定。
   返回该页面的指针。

fetch page：根据page_id获取指定的页

1. 加锁以保护缓冲池的并发访问
   使用 std::scoped_lockstd::mutex 对缓冲池进行加锁，确保线程安全。
2. 尝试从哈希表中查找页面
   检查页面表（哈希表）中是否已经存在所需的页面 (page_id)。
   找到页面的情况：

• 找到页面对应的框架 ID（num_frame_id）。
• 增加该页面的 Pin Count（将页面锁定，表示正在使用）。
• 更新 LRU-K 替换器中的页面访问记录（RecordAccess）。
• 设置该页面为不可驱逐（SetEvictable(false)），因为页面正在使用。
• 返回该页面的指针。

3. 处理页面未找到的情况
   如果页面不在缓冲池中，接下来要考虑如何加载该页面。
   检查缓冲池中是否有可驱逐的页面：

• 遍历缓冲池，检查是否有页面的 Pin Count 为 0（表示该页面没有被锁定，可以驱逐）。
• 如果所有页面都不可驱逐（Pin Count 都不为 0），则返回 nullptr，表示无法获取新的页面。

4. 优先从 free_list_ 中分配页面
   检查 free_list_ 是否非空：

• 如果 free_list_ 中有空闲的框架，从 free_list_ 中取出一个框架 ID 并从 free_list_ 中移除。
• 建立页面表关系：将新的页面 ID 和框架 ID 插入页面表（page_table_）。
• 更新 LRU-K 替换器：记录该页面的访问，并设置该页面为不可驱逐（SetEvictable(false)）。
• 初始化页面：将页面 ID 分配给缓冲池数组中的该框架，并设置 Pin Count 为 1。
• 从 磁盘 中读取该页面的数据（ReadPage），并将数据加载到该框架中。
• 返回该页面的指针。

5. 使用 LRU-K 替换策略驱逐页面（如果 free_list_ 为空）
   如果 free_list_ 中没有空闲页面，则需要从 LRU-K 替换器 中选择一个页面进行驱逐。
   调用 Evict() 方法让 LRU-K 替换器选择一个可驱逐的框架 ID（num_frame_id）。
6. 处理驱逐的页面
   获取驱逐页面的页面 ID。
   检查是否为脏页：

• 如果该页面是脏页（is_dirty_ 为 true），先将页面内容写回磁盘（WritePage），并将脏页标志清除（is_dirty_ = false）。

  移除旧的页面表信息：将该页面 ID 从页面表中移除。
  清空旧页面的内存：重置该页面的内存内容（ResetMemory()）。

7. 将新页面插入到驱逐的框架中
   建立页面表关系：将新的页面 ID 和被驱逐的框架 ID 插入页面表（page_table_）。
   更新 LRU-K 替换器：记录该框架的访问，并设置该页面为不可驱逐（SetEvictable(false)）。
   初始化页面：将新的页面 ID 分配给缓冲池数组中的该框架，并设置 Pin Count 为 1。
   从 磁盘 中读取该页面的数据（ReadPage），并将数据加载到驱逐的框架中。
   返回该页面的指针。
8. 返回新加载的页面
   无论是从 free_list_ 中获取页面，还是通过 LRU 替换获得页面，最终都会返回相应的新页面指针。

UnpinPage

• 如果page_id不存在，或pin_count_已经为0，返回false_
• 通过page_id与page_table_获取frame_id，进一步可以获取Page *
• pin_count_–，如果pin_count_为0，SetEvictable(设置page为可驱逐)
• 设置Page的is_dirty_

DeletePage
删除内存中指定的page

• find page_table_: 没有必要删除不存在或者在磁盘中的page
• 如果Page不可驱逐(pin_count_ != 0)，return false
• replacer_->Remove()在LRUKReplacer删除page使用的frame, page_table_.erase(), free_list_.push_back_
• 重置Page的data_, 与剩下字段
• 最后象征性地调用DeallocatePage()

LRUK Replacer

std::unordered_map<frame_id_t, bool> mp_;           // 判断是否可以访问
std::unordered_map<frame_id_t, size_t> frame_num_;  // 判断一个元素出现次数
std::list<frame_id_t> hist_;                        // 存放左边的队列，也就是不满足K次的队列
std::list<frame_id_t> cur_;                         // 存放右边的队列，满足K次的队列

总结：

• 历史队列 (hist_) 存储那些访问次数未达到 K 次的缓存块。
• 当前队列 (cur_) 存储那些访问次数达到 K 次的缓存块。
• 当缓存块的访问次数达到 K 次时，会从历史队列移动到当前队列。
• 当缓存空间不足时，优先淘汰历史队列中的缓存块，如果历史队列为空，则淘汰当前队列中的缓存块。

Page

成员变量的含义

1. char data_[BUSTUB_PAGE_SIZE]{}:
   • 这是页面中存储实际数据的缓冲区。每个页面都有固定大小的存储空间，用于存储用户和系统的数据。BUSTUB_PAGE_SIZE 是页面的大小常量，定义了每个页面的字节数。
2. page_id_t page_id_ = INVALID_PAGE_ID;:
   • 当前页面的唯一标识符（ID）。page_id_t 是页面 ID 的类型，通常是一个整数类型值（比如 uint32_t），用于唯一标识每个页面。
   • INVALID_PAGE_ID 是一个特殊的常量，用于表示当前页面没有分配有效的页面 ID。
3. int pin_count_ = 0;:
   • 页面被固定（Pinned）的计数器。Pin Count 用于表示页面是否被某些进程或事务“锁定”在内存中。
   • 当 Pin Count > 0 时，页面不能被驱逐出缓冲池，因为某些操作正在使用它。
   • 当 Pin Count = 0 时，页面可以被替换算法（如 LRU-K）驱逐。
4. bool is_dirty_ = false;:
   • 标志位，表示页面是否是“脏页”。如果页面被修改（即页面内存中的数据与磁盘上的数据不一致），is_dirty_ 会被设置为 true。
   • 脏页需要在替换前被写回磁盘，以防止数据丢失。
5. ReaderWriterLatch rwlatch_;:
   • 页面级的读写锁，用于控制对页面的并发访问。
   • 读写锁（Reader-Writer Lock） 允许多个线程同时读取页面，但当页面被写入时，必须是独占的。

成员函数的含义

1. Page():

   • 构造函数，在页面对象创建时调用，调用 ResetMemory() 来将页面的存储空间清零。

2. ~Page():

   • 默认析构函数，不进行特殊操作。

3. char \*GetData():

   • 返回指向页面数据缓冲区的指针，允许访问和修改页面中的实际数据内容。

4. page_id_t GetPageId():

   • 返回页面的 ID，即 page_id_，用于区分不同页面。

5. int GetPinCount():

   • 返回当前页面的 Pin Count，表示该页面被锁定在缓冲池中的次数。

6. bool IsDirty():

   • 返回页面的脏页标志 is_dirty_，用于判断页面是否被修改过。

7. void WLatch():

   • 获取页面的写锁（独占锁），确保在修改页面数据时不会有其他线程同时读取或写入该页面。

8. void WUnlatch():

   • 释放页面的写锁。

9. void RLatch():

   • 获取页面的读锁，允许多个线程同时读取页面数据，但不能同时写入该页面。

10. void RUnlatch():

    • 释放页面的读锁。

11. lsn_t GetLSN():

    • 返回页面中的 日志序列号（LSN）。LSN 是数据库系统中用于日志记录的一个重要概念，通常用于保证恢复时的顺序一致性。
    • LSN 存储在页面数据的某个偏移位置上（在 OFFSET_LSN 处）。

12. void SetLSN(lsn_t lsn):

    • 设置页面的 日志序列号（LSN），将 LSN 写入页面数据的某个偏移位置。

13. void ResetMemory():

• 将页面的数据缓冲区初始化为指定的初始值（清零），即将 data_ 数组中的所有字节重置为 0。

//===----------------------------------------------------------------------===//
//
//                         BusTub
//
// page.h
//
// Identification: src/include/storage/page/page.h
//
// Copyright (c) 2015-2019, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#pragma once

#include <cstring>
#include <iostream>

#include "common/config.h"
#include "common/rwlatch.h"

namespace bustub {

/**
 * Page is the basic unit of storage within the database system. Page provides a wrapper for actual data pages being
 * held in main memory. Page also contains book-keeping information that is used by the buffer pool manager, e.g.
 * pin count, dirty flag, page id, etc.
 */
class Page {
  // There is book-keeping information inside the page that should only be relevant to the buffer pool manager.
  friend class BufferPoolManagerInstance;

 public:
  /** Constructor. Zeros out the page data. */
  Page() { ResetMemory(); }

  /** Default destructor. */
  ~Page() = default;

  /** @return the actual data contained within this page */
  inline auto GetData() -> char * { return data_; }

  /** @return the page id of this page */
  inline auto GetPageId() -> page_id_t { return page_id_; }

  /** @return the pin count of this page */
  inline auto GetPinCount() -> int { return pin_count_; }

  /** @return true if the page in memory has been modified from the page on disk, false otherwise */
  inline auto IsDirty() -> bool { return is_dirty_; }

  /** Acquire the page write latch. */
  inline void WLatch() { rwlatch_.WLock(); }

  /** Release the page write latch. */
  inline void WUnlatch() { rwlatch_.WUnlock(); }

  /** Acquire the page read latch. */
  inline void RLatch() { rwlatch_.RLock(); }

  /** Release the page read latch. */
  inline void RUnlatch() { rwlatch_.RUnlock(); }

  /** @return the page LSN. */
  inline auto GetLSN() -> lsn_t { return *reinterpret_cast<lsn_t *>(GetData() + OFFSET_LSN); }

  /** Sets the page LSN. */
  inline void SetLSN(lsn_t lsn) { memcpy(GetData() + OFFSET_LSN, &lsn, sizeof(lsn_t)); }

 protected:
  static_assert(sizeof(page_id_t) == 4);
  static_assert(sizeof(lsn_t) == 4);

  static constexpr size_t SIZE_PAGE_HEADER = 8;
  static constexpr size_t OFFSET_PAGE_START = 0;
  static constexpr size_t OFFSET_LSN = 4;

 private:
  /** Zeroes out the data that is held within the page. */
  inline void ResetMemory() { memset(data_, OFFSET_PAGE_START, BUSTUB_PAGE_SIZE); }

  /** The actual data that is stored within a page. */
  char data_[BUSTUB_PAGE_SIZE]{};
  /** The ID of this page. */
  page_id_t page_id_ = INVALID_PAGE_ID;
  /** The pin count of this page. */
  int pin_count_ = 0;
  /** True if the page is dirty, i.e. it is different from its corresponding page on disk. */
  bool is_dirty_ = false;
  /** Page latch. */
  ReaderWriterLatch rwlatch_;
};

}  // namespace bustub

Disk Manager

这里关键看2个函数ReadPage和WritePage。

//----------------------ReadPage----------------------
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 {
    // set read cursor to offset
    db_io_.seekp(offset);
    db_io_.read(page_data, BUSTUB_PAGE_SIZE);
    if (db_io_.bad()) {
      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);
    }
  }
}
//----------------------WritePage----------------------
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()) {
    LOG_DEBUG("I/O error while writing");
    return;
  }
  // needs to flush to keep disk file in sync
  db_io_.flush();
}

void DiskManager::WritePage(page_id_t page_id, const char *page_data)

• 功能：将指定页面的数据写入数据库文件。

• 具体操作

  • 计算页面在文件中的偏移量（根据页面 ID 和页面大小计算）。

• 将写指针移动到偏移位置并写入页面数据。

  • 检查写入是否成功，并确保将数据同步到磁盘（调用 flush()）。

• 加锁：使用锁来确保线程安全的写操作。

void DiskManager::ReadPage(page_id_t page_id, char *page_data)

• 功能：从数据库文件中读取一个页面的数据到内存中。

• 具体操作

  • 计算页面在文件中的偏移量。

• 检查是否超出文件长度（避免读取不存在的数据）。

  • 如果读取数据少于一整页（文件可能未完整），则将剩余部分填充为零。
  • 检查读取是否成功。

• 加锁：使用锁来确保线程安全的读操作。