CMU 15-445 Project 1

Task 1 Extendible Hash Table

内容

这个任务是要我们实现一个 extebdible hash table. 有以下要求：

• 具有插入、删除、插值键值对的功能

• 能够在冲突发生的时候自动增加空间大小, 不需要在创建的时候指定大小

• 不需要实现空间减小的功能

• 只能修改以下文件

  • src/include/container/hash/extendible_hash_table.h
  • src/container/hash/extendible_hash_table.cpp

• 可以使用任何内置的 C++17 containers 来实现

具体来说, 需要实现 ExtendibleHashTable 类的以下函数：

• Find(K, V)：对于一个给定的键 K, 查看其是否存在与 hash table 当中.

  • 是：把指针指向对应值 V , 返回 true

  • 否：返回 false

• Insert(K, V)：向 hash table 里插入键值对.

  • 如果键 K 已经存在, 用新值 V 覆盖其值并返回 true（更新操作）

  • 如果无法插入（bucket 已经满了且不是更新操作）, 执行以下操作

    1. 如果 bucket 的 local depth 等于 global depth, 把 global depth 增大 1, 并且把 dictionary 的大小翻倍

    2. 把 local depth 的值增加 1

    3. 拆分 bucket 并且重新分配 dictionary 和键值对

  • 一些其他的实现方法会在 bucket 在一次插入操作后刚好满的时候进行拆分. 但是在这个 project 里, 请在一次插入操作之前判断 bucket 是否为满并且进行拆分操作.

• Remove(K)：对于一个给定的键 K, 删除其对应的键值对, 返回 true. 如果该键不存在, 返回 false

• GetGlobalDepth()：返回当前 hash table 的 global depth

• GetLocalDepth(dir_index)：返回 dir_index 所指向的 bucket 的 local depth

• GetNumBuckets()：返回 hash table 里 buckets 的总数

你可以使用我们所提供的 IndexOf(K) 私有成员函数来计算给定的 K 的 index. 额外地, 我们还提供了 Bucket 类来实现 extendible hash table 里的 bucket. 先完成 Bucket 类里的 TODOs 来更轻松地实现本 task.

你需要保证你的所有在 hash table 里的操作都是通过 std::mutex 来实现了线程安全, 你可以自己决定你要如何保护数据结构.

题解

按照题目的要求, 可以先实现 Bucket 类. 这一部分的内容比较基础, 直接按照其函数的功能和参数的定义调用 STL 函数即可.

对于 ExtendibleHashTable 类的 Find(K, V) 和 Remove(K, V) 函数的实现也都比较简单, 直接调用 Bucket 类中对应的函数并进行一些判断.

难点在于 Insert(K, V) 函数. 大致步骤如下:

1. 判断 global depth 是否等于 local depth. 若相等, 则:

   1. 将 dictionary 的空间翻倍;

   2. 将原有的 dictionary 内容复制一份 (也就是说 dictionary 的下半部分所存的 bucket 指针与上半部分所存的 bucket 指针相同);

2. 新建 2 个 buckets, 其 local depth 为满 bucket 加 1, 用于拆分满了的 bucket;

3. 修改对应 dictionary 使其指向新的 buckets;

4. 将满了的 bucket 里的键值对重新分配.

修改对应 dictionary 的时候, 需要把所有拆分后依然相同的 hash 指向一个 bucket.

Task 2 LRU-K Replacement Policy

内容

这个任务是要我们实现 LRU-K 的调度算法. 有以下要求:

• 对 replacer 里 k-distance 最大的 frame 进行 evict 操作;

• k-distance 是指当前时间戳和 k 次前访问时候的时间差的差;

• 如果一个 frame 访问次数少于 k 次, 则其 k-distance 等于 +inf;

• 如果有多个 frame 的 k-distance 都是 +inf, 则 evict 当前时间戳最早的那个;

• 只能修改以下文件:

  • src/include/buffer/lru_k_replacer.h

  • src/buffer/lru_k_replacer.cpp

具体来说, 就是需要我们实现以下 LRUKReplacer 类中的方法:

• Evict(frame_id_t*): 将拥有最大的 k-distance 的, 被 Replacer 所跟踪的, 可 evict 的 frame 进行 evict 操作. 将其 frame id 存储在输出参数当中并且返回 true. 如果没有可 evict 的 frame 则返回 false.

• RecordAccess(frame_id_t): 记录给定的 frame 当前时刻被访问了. 这个方法应当在一个页面被 BufferPoolManager 给 pin 之后调用.

• Remove(frame_id_t): 清理给定的 frame 的所有时间戳. 这个方法只需要在一个 page 在 BufferPoolManager 当中被删除后被调用.

• SetEvictable(frame_id_t, bool set_evictable): 这个方法用于控制一个 frame 是否可以被 evict. 其同时控制了 LURReplacer 的大小. 你会在实现 BufferPoolManager 的时候知道何时需要调用这个方法. 具体来说, 当一个 page 的 pin 次数达到 0时, 其对应的 frame 被标记为可 evict, 并且 replacer 的大小增加.

• Size(): 这个方法返回了当前 LRUReplacer 里可被 evict 的 frame 的数量.

具体实现细节由你自己决定. 你可以使用内置的 STL 容器. 你可以假设不会耗尽内存, 但必须确保操作是线程安全的.

题解

本题的自由度较高, 我们可以使用自己的方法来实现对每个 frame 的时间戳的追踪. 这里我使用的是 vector 和 deque 来实现. deque 用于存储 k 个时间戳. vector 用于存储每个 frame 的 deque. 这里我们默认 frame id 的值就是 0 到 replacer_size_ - 1, 因为这个细节是我们可以在 task 3 里自己控制的.

每次 evict 一个 frame 的时候, 优先查找时间戳数量未达到 k 次的, 最早的时间戳最小的 frame. 如果一个 frame 的时间戳数量达到了 k 次, 即使其最早的时间戳比其他未达到 k 次的 frame 的时间戳还要早, 也不使用这个 frame. 这个逻辑可以用一个 bool 变量来实现.

Task 3 Buffer Pool Manager Instance

内容

task 3 是关于实现 buffer pool manager 的实现. buffer pool manager 的作用是通过 disk manager (已经提供) 把数据库的内容从物理磁盘里读取到内存中, 把修改过的 page (dirty page) 写入到磁盘中为新的读取操作腾出空间.

所有在内存中的 page 都用 Page 类来表示. buffer pool manager 不需要知道 page 里的具体内容是什么. 有一点一定要知道的是, Page 所表示的是 buffer pool 中的 page, 而不是特指某一个特定的. 也就是说, 每个 Page 对象都包含一个内存块, disk manager 将使用该块作为从磁盘读取的物理页内容的存储位置. buffer pool manager 将重复使用相同的 Page 对象, 在数据在内存和磁盘之间来回移动时存储数据. 这意味着同一个Page对象在系统运行期间可能包含不同的物理 page. Page 对象的标识符 (page_id) 用于跟踪其包含的物理 page, 如果一个 Page 对象不包含物理页, 那么它的 page_id 必须设置为 INVALID_PAGE_ID.

每个 Page 对象还维护了一个计数器, 用于记录已经"固定"（pinned）该页的线程的数量. buffer pool manager 不允许释放被固定的 Page. 每个 Page 对象还会跟踪其是否被修改（dirty）。在解除固定之前，你的任务是记录页面是否在修改过。你的 buffer pool manager 必须在可以重新使用该对象之前将脏页的内容写回磁盘。

你会用前面实现了的 ExtendibleHashTable 来实现 page_id 到 frame_id 的映射, 用 LRUKReplacer 来跟踪每个 Page 是否被访问, 以及哪个 frame 可以被释放.

题解

本题相对于上面两个 tasks 来说是最简单的, 只是把前两个 tasks 打包调用就可以了. 不过本题新出现了很多新的类, 比如 Page, DiskManager. 对于这些不熟悉的类, 需要打开他们的头文件来查看一下他们所拥有的属性与方法.

需要注意的几个点有: 在 DeletePgImp(page_id) 函数里面, 当 page_id 无法在 page_table_ 里找到的时候, 需要返回的是 true, 而不是 false. 在 FetchPgImp(page_id) 函数里面, 如果能直接在 page_table_ 里找到, 需要调用 replacer_ 的相关函数来更新该 frame 的访问次数.