Project #1 - Buffer Pool
本文是对CMU15-445课程第1个项目的一个粗略总结和翻译。仅供个人(M1kanN)复习使用。
1. Overview
-
本学期要求为 BusTub DBMS实现一个新的面向磁盘的存储管理器(disk-oriented storage manager)。这样的存储管理器假定数据库的主要存储位置是磁盘上。
-
第一个编程项目是实现一个缓冲池(buffer pool)。缓冲池负责将物理页从主存中来回移动到磁盘。它允许DBMS支持大于系统可用内存量的数据库。缓冲池的操作对系统的其他部分是透明(transparent)的。比如：系统使用其唯一的标识符(page_id_t)向缓冲池要(ask)一个页面，它不知道这个页面是否已经在内存中，或者系统是否必须从磁盘中检索它。
-
注意：实现必须是线程安全的(thread-safe)。多个线程都将同时访问数据结构，所以必须确保他们的关键部分收到latch的保护。（即：锁）
-
我们需要在我们的存储管理器中实现以下3个部分：
2. Project Specification
- 对此次任务实现的每个组件，都提供了包含所需要我们实现的API的存根类(stub class)。我们不应该修改这些类中预先定义的函数签名(function signatures)。如果修改了，用来评分的测试代码可能会被破坏。就评分不了了。
- 如果一个类已经包含了数据成员，我们不应该删除它们。例如
BufferPoolManagerInstance里面的DiskManager,ExtendibleHashTable和LRUKReplacer对象。这些都是实现系统其他部分所需要的功能所需要的。另一方面，我们可能要向这些类来添加数据成员，以便正确实现所需要的功能。也可以给这些类添加辅助函数。 - 除非有规定，我们可以在项目中使用任何的C++17容器。可以自行选择。注意多线程安全和锁的使用，来保护它们。但是我们不能带入额外的第三方依赖，比如boost。
Task #1 - Extendible Hash Table
-
在这个项目的第一部分，我们将建立一个通用的哈希表，使用无序的桶(unordered buckets)来存储唯一的键值对(key/value pairs)。
我们的哈希表必须支持- 插入/ 删除 键值对的能力。
- 我们无需指定表的最大size，表应该可以根据需要逐步增加大小，但是我们不需要缩小表。也就是说，我们不需要实现对缩小或者压缩哈希表的功能。
- 我们还需要支持检查一个键是否存在于哈希表中，并返回相应的值。
-
在正式开始编程之前，建议先着手一些分割和目录增长的小例子。
-
我们必须在项目源代码的指定文件中实现哈希表。而且只允许修改哈希表头文件(
src/include/container/hash/extendible_hash_table.h)和对应的实现文件(src/container/hash/extendible_hash_table.cpp)。我们不需要修改任何其他文件，在视线中，我们不能在内部使用另一个内置哈希表。而且我们必须在ExtendibleHashTable类中实现以下函数：-
Find(K, V): 给定键K，检查它是否存在于哈希表中，如果存在，则在V中存储指向其对应值的指针并返回true。如果键不存在，返回false。 -
Insert(K, V): 将键值对插入哈希表。如果K已经存在，则用新的值V覆盖其值，并返回true。如果键值对不能被插入到桶中（因为桶已经满了，而且键没有更新现有的对），在重试之前做以下步骤：- 如果桶的本地深度(local depth)等于全局深度(global depth)。递增全局深度。并将目录(directory)的大小增加一倍。
- 增加桶的局部深度。
- 分割桶。并重新分配目录指针和桶中的K/V对。
有限实现是在插入后，如果桶满了就分割桶，但是在这个项目桶，请检测桶是否溢出，并在插入之前执行分割！
-
Remove(K)：给定K, 从哈希表删除其对应的键值对，并返回true。如果不存在，返回false。 -
GetGlobalDepth(): 返回整个哈希表的当前全局深度。 -
GetLocalDepth(dir_index)：返回给定目录索引所指向的桶的当前本地深度。 -
GetNumBuckets(): 返回在哈希表中分配的桶的总数。
-
-
我们可以利用给定的
IndexOf(K)的私有函数来计算一个给定键所切分的目录索引。此外，还提供了一个Bucket嵌套类，表示可扩展哈希表中的桶。通过遵循代码文档，首先完成Bucket类的TODOs可以让我们更容易实现``ExtendibleHashTable`的API。但也可以自由的表写我们自己的内部类和辅助函数。 -
我们需要使用
std::mutex确保哈希表中的所有操作都是线程安全的。如何保护数据机构由我们自己决定。
Task #2 - LRU-K Replacement Policy
LRU-K算法参考：LRU-K和2Q缓存算法介绍
- 这个组件负责跟踪缓冲池中的页面使用情况。我们将在
src/include/buffer/lru_k_replacer.h中实现一个名为LRUKReplacer的新类。并在src/buffer/lru_k_replacer.cpp中实现相应的实现文件。
注意：LRUKReplacer是一个独立的类，它与其他的Replacer类没有关系。我们应该只实现LRU-K替换策略，而不需要实现LRU或者时钟(clock)替换策略，即使有相应的文件。 - LRU-K算法驱逐一个帧，该帧的后向k-距离(Backward k-distance)是替换器中所有帧的最大值。后向k-距离的计算方法是当前时间戳和第k 次访问的时间戳之间的时间差。一个少于k次历史访问的帧被赋予
+inf来作为它的后向k-距离。
当多个帧有+inf的后向k-距离的时候，替换器会驱逐具有最早时间戳的帧。 LRUReplacer的最大尺寸与缓冲池的尺寸相同，因为它包含BufferPoolManager中所有帧的占位符（记录每个page的访问次数）。然而在任何给定的时刻，并不是复制器中的所有帧都被认为是可驱逐的。LRUReplacer的大小由可驱逐的数量表示。LRUReplacer被初始化为里面没有帧，然后只有当一个帧标记为可驱逐后，替换器(replacer)的大小才会增加。- 我们需要实现课堂上讨论的LRU-K策略。我们将实现以下方法:
Evict(frame_id_t*)
驱逐Replacer正在跟踪的所有其他可驱逐帧相比，具有最大后向k-距离的帧。在输出参数中存储该帧的ID，并返回true。如果没有可驱逐帧，返回false。RecordAccess(frame_id_t)
记录给定的帧ID在当前时间戳被访问，这个方法应该在一个页面被pin在BufferPoolManager后被调用。Remove(frame_id_t)
清除与一个帧相关的所有访问历史。只有在BufferPoolManager中删除一个页面的时候，才应该调用这个方法。SetEvictable(frame_id_t, bool set_evictable)
该方法控制一个帧是否可以被驱逐。它还控制LRUReplacer的大小。
当我们实现BufferPoolManager的时候，我们就会知道啥时候调用这个函数。
具体来说，当一个页面的pin count达到0的时候，其对应的帧就会标记为可驱逐(Evictable)。Replacer的大小也会增加。Size()
这个方法返回当前在LRUReplacer中可驱逐帧的数量。
- 实现的方法取决于我们。我们被允许使用内置的STL容器。而且可以假定不会耗尽内存，但必须保证操作是线程安全的(thread-safe)。