CMU 15-445 Project 1

这个任务是要我们实现一个 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 来实现了线程安全, 你可以自己决定你要如何保护数据结构.

关于学术诚信
按照 Andy 的要求, 我不会把代码公布出来, 只会分享做法. 公开题解代码是违反学术诚信的行为!

按照题目的要求, 可以先实现 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.

vector 空间翻倍

在进行 dictionary 复制操作的时候, 第一个想到的肯定是使用迭代器遍历并且一个个 .push_back(). 但是这样会出现 vector 因加入新的元素, 自动申请更大的空间并将原本的空间释放. 这样会导致迭代器出现非法空间访问的问题.

要解决这个问题, 请使用 vector.reserve() 来在复制之前先申请更大的空间.

互斥锁 latch_

在编写代码的时候, 需要时刻注意互斥锁的状态, 及时打开和释放互斥锁. 要保证在涉及到读取结构相关数据的时候只有一个线程正在执行, 否则无法通过测试.

可以参考我自己定义的互斥锁的规则:

  • 所有 public 函数都需要判断互斥锁

  • 所有 private 函数都不需要判断互斥锁

  • public 函数里只调用 private 函数, 不调用其他 public 函数

split 操作
split 操作是把一个满了的 bucket 给拆分成两个 bucket, 以实现动态调整 hash table 大小的功能. 这里需要注意的是, split 完且重新分配键值对之后, 这些键值对还有可能被分配到同一个 bucket, 使得还需要再进行 split 操作, 因此需要循环检测 bucket 的状态而不是 split 完之后就不管了.

这个任务是要我们实现 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 容器. 你可以假设不会耗尽内存, 但必须确保操作是线程安全的.

关于学术诚信
按照 Andy 的要求, 我不会把代码公布出来, 只会分享做法. 公开题解代码是违反学术诚信的行为!
frame 和 page
在开始之前, 我们需要明确一下 frame 和 page 的区别. page 是数据库中的数据存储单位, 通常与磁盘块的大小相对应. 它是数据库在磁盘上存储和管理数据的最小单位. frame 通常指的是内存中的一个固定大小的数据块, 用于缓存数据库的一个 page. frame 是内存管理的单位, 它可以容纳一个或多个 pages.

本题的自由度较高, 我们可以使用自己的方法来实现对每个 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 变量来实现.

时间戳

题目要求我们实现用时间戳来计算 k-distance. 但是, 由于计算机的运行速度过快, 时间戳可能会出现精度不够的情况, 也就是无法保证每次 access 的时间戳都不一样. 这可能会导致出现直接跑测试不通过, 但是用 gdb 步进却能通过的情况. 这就是时间戳相同引起的问题.

其实我们可以使用自己的时间戳——计数. 我们每次 access 的时候让计数器加一, 直接用计数器的值当作时间戳. 毕竟我们只需要考虑时间戳的先后次序, 而不需要考虑具体的差值是多少. 这样我们就可以保证所有的 access 的时间戳都不一样了.

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 可以被释放.

关于学术诚信
按照 Andy 的要求, 我不会把代码公布出来, 只会分享做法. 公开题解代码是违反学术诚信的行为!

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

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

Page 类里的读写锁
在阅读 Page 类的时候会发现, 其有用于获取和释放读写锁的函数 RLatch(), RUnlatch(), WLatch(), WUnlatch(). 这些锁我们现在不需要使用, 不要在编写本 task 代码的时候调用这些函数.