OVERVIEW
在本学期中，你将为 BusTub DBMS 构建一个新的 disk-oriented storage manager。这种 storage manager 假定数据库的主存储位置在磁盘上。
第一个编程项目是在 storage manager 中实现一个 buffer pool。buffer pool 负责将 physical pages 在 main memory 和disk 之间来回移动。它允许 DBMS 支持大于系统可用内存量的数据库。buffer pool 的操作对于系统中的其他部分是透明的。例如，系统使用它的唯一标识符 (page_id_t) 向 buffer pool 请求一个 page，但它不知道该 page 是否已经在 memory 中，或者系统是否必须从 disk 中检索该页面。
你的实现需要是线程安全的。多个线程将同时访问内部数据结构，因此你需要确保它们的关键部分受到 latches (在操作系统中称为“locks”) 的保护。
你需要在存储管理器中实现以下三个组件：
PROJECT SPECIFICATION
对于每个组件，都已提供相应类，它们包含了需要实现的 API，你不能修改这些类中预定义的函数。若你修改了，我们用于评分的测试代码将会中断，你将不会得到该项目的学分。
如果类已经包含数据成员，则不应删除它们。例如，BufferPoolManagerInstance 包含 DiskManager、 ExtendibleHashTable 和 LRUKReplace 对象。这些是实现系统其他部分所需的功能所必需的。另一方面，为了正确实现所需的功能，可能需要向这些类中添加数据成员。还可以向这些类添加其他函数。选择权在你。
除非另有说明，否则允许在项目中使用任何内置的 C + + 17容器。你可以自己决定使用哪一个。请注意，这些容器不是线程安全的，你需要在实现中使用 latches 来保护它们。不要使用额外的第三方依赖 (e.g. boost)。
Task #1 - Extendible Hash Table
对于本项目的第一部分，你将构建一个通用哈希表，它使用 unordered buckets 来存储唯一的 key/value pair。散列表必须支持在不指定表的最大大小的情况下 insert/delete key/value entries 的能力。你的表需要根据需要逐渐增大大小，但不需要缩小它。也就是说，你不需要实现对缩小或压缩哈希表的支持。你还需要支持检查，以查看散列表中是否存在某个 key，并返回相应的 value。
我们鼓励你在开始实现之前首先手动浏览一些 split 和 directory growing 的小示例。
必须在项目源代码中的指定文件中实现哈希表。只允许修改哈希表头文件 (src/include/Container/hash/extdible_hash_table.h) 及其相应的实现文件 (src/container/hash/extdible_hash_table.cpp)。你不需要修改任何其他文件。在实现中不能在内部使用另一个内置哈希表。必须在 ExtendibleHashTable 类中实现以下函数:
Find(K, V): 对于给定的键 K，检查它是否存在于散列表中。若是，那么将指向其相应值的指针存储在 V 中并返回 true。否则返回 false。Insert(K, V): 将 key/value pair 插入散列表。如果键 K 已经存在，则用新值 V 覆盖它的值并返回 true。如果 key/value pair 不能插入到 bucket 中 (因为 bucket 已满，key 更新的不是已有的 pair) ，在重试之前执行以下步骤：- 如果 bucket 的 local depth = global depth，则增加全局深度并将 directory 的大小增加一倍
- 增加 bucket 的 local depth
- split bucket 并重新分配 directory 指针和 bucket 中的 kv 对
Remove(K): 对于给定的键 K，从散列表中删除相应的 key/value pair 并返回 true。若散列表中不存在键 K，则返回 false。GetGlobalDepth(): 返回整个哈希表当前的 global depth。GetLocalDepth(dir_index): 返回给定的 directory index 指针指向的 bucket 的 local depth。GetNumBuckets(): 返回哈希表中分配的 bucket 的总数。
你可以使用私有的函数 IndexOf(K) 来计算给定 key 会 hash 到的 directory index。此外，我们还提供一个嵌套类 Bucket 来表示可扩展哈希表中的 bucket。首先完成 Bucket 类中的 TODO 可使你更容易实现 ExtendibleHashTable APIs。但你可以随意编写自己的 internal class / helper functions。
您需要使用 std::mutex 确保散列表中的所有操作都是线程安全的。如何保护数据结构取决于您自己。
Task #2 - LRU-K Replacement Policy
此组件负责跟踪 buffer pool 中 page 的使用情况。您将在 src/include/buffer/lru_k_replacer.h 中实现一个名为 LRUKReplacer 的新类，并在 src/buffer/lru_k_replacer.cpp 中完成相应实现。请注意，LRUKReplacer 是一个独立的类，它与任何其他 Replacer 类都没有关系。您应该只实现 LRU-K 替换策略。您不必实现 LRU 或 clock replacement 替换策略，即使有一个相应的文件。
LRU-K 算法 evict 所有 frame 中 backword k-distance 最大的 frame。backword k-distance 是当前访问的 timestamp 与之前第 k 个访问的 timestamp 的时间差。若一个 frame 没有被访问过 k 次，设其 backword k-distance = +inf。若多个 frame 的 backword k-distance = +inf，则 evict timestamp 最早的那个 frame。
LRUKReplacer 的最大大小与 buffer pool 的大小相同，因为它包含 BufferPoolManager 中所有 frame 的 placeholder。然而 replacer 中不是所有 frame 都能被替换。LRUKReplacer 的大小是可被替换（evictable）的 frame 的数量。LRUKReplacer 初始化时不包含任何 frame，然后只有当一个 frame 被标记为可替换的（evictable），replacer 的 size 才会增加。
您需要实现类中讨论的 LRU-K 策略：
Evict(frame_id_t*)：与Replacer跟踪的所有其他 evictable frames 相比，evict 具有最大 backword k-distance 的 frame。 将 frame id 存储在 output parameter 中并返回 True。 如果没有可驱逐的 frame，则返回 False。RecordAccess(frame_id_t)：记录在当前时间戳访问了给定的 frame id。在BufferPoolManager中 pin 一个 page 后，应调用此方法。Remove(frame_id_t)：clear 一个 frame 的所有访问历史。当在BufferPoolManager中删除一个 page 时应调用此方法。SetEvictable(frame_id_t, bool set_evictable): 此方法设置一个 frame 是否 evictable，还能控制LRUReplaver的大小。当你实现 BufferPoolManager 时，你将知道何时调用此函数。 具体来说，当一个页面的 pin 计数达到 0 时，其对应的帧被标记为可驱逐的，并且 replacer 的大小增加。Size()：返回当前LRUKReplacer中 evictable 的 frame 的数目。
实现细节由您决定。您可以使用内置的 STL 容器。您可以假设不会耗尽内存，但是必须确保操作是线程安全的。
Task #3 - Buffer Pool Manager Instance
最后，需在系统中实现 buffer pool manager (BufferPoolManagerInstance)。
BufferPoolManagerInstance 负责从 DiskManager 获取 database page 并存储在内存中，BufferPoolManagerInstance 还可以在显式执行 or 需要清除 page 以为新 page 腾出空间时，将 dirty page 写入磁盘。
为了确保您的实现能够与系统的其他部分正确地工作，我们将提供一些已经填充的函数。您也不需要实现实际读写数据到磁盘的代码 (在我们的实现中称为 DiskManager)。我们将为您提供该功能。
系统内存中所有的 page 都采用 Page 对象表示，BufferPoolManagerInstance 无需理解这些 page 的内容。但是作为系统开发人员，重要的是要了解 Page 对象只是 buffer pool 中的内存容器，而不是对于一个特定 page 的。也就是说，每个 Page 对象都包含一块内存，DiskManager 将使用这块内存作为位置，以复制从磁盘读取的 physical page 的内容。BufferPoolManagerInstance 将重用同一个 Page 对象来存储数据，因为它在磁盘上来回移动。 这意味着在系统的整个生命周期中，同一个 Page 对象可能包含不同的 physical page。 Page 对象的标识符 (page_id) 跟踪它包含的 physical page；若 Page 对象不包含 physical page，则其 page_id 必须设置为 INVALID_PAGE_ID。
每个 Page 对象还为“pin”该 page 的线程数维护一个计数器。 你的 BufferPoolManagerInstance 不允许释放 pin 住的 page。 每个 Page 对象还跟踪它是否 dirty。 你的工作是记录 page 在取消 pin 前是否被修改。 你的 BufferPoolManagerInstance 必须先将 dirty page 的内容写回磁盘，然后才能重用该对象。
你的 BufferPoolManagerInstance 实现将使用到你在此作业的前面步骤中创建的 ExtendibleHashTable 和 LRUKReplacer 类。 使用 ExtendibleHashTable 将 page_id 映射到 frame_id 。 使用 LRUKReplacer 跟踪何时访问 Page 对象，以便它在必须释放一个 frame 来为从磁盘复制新 physical page 腾出空间时，能决定驱逐哪个对象。
您将需要在源文件 (src/buffer/buffer_pool_manager_instance.cpp) 中实现头文件 (src/include/buffer/buffer_pool_manager_instance.h) 中定义的以下函数：
FetchPgImp(page_id)：若 free list 没有可用的 page 且当前所有其他 page 都被 pin，则返回 nullptr。UnpinPgImp(page_id, is_dirty)：is_dirty 参数跟踪 page 在 pin 时是否被修改。FlushPgImp(page_id)：flush 一个 page，无视其 pin status。NewPgImp(page_id)：用此方法创建新 page 时，私有方法AllocatePage()会为BufferPoolManager提供一个新 page id。DeletePgImp(page_id)：需调用DeallocatePage()方法，该方法是个模拟释放 page 到磁盘的空操作。FlushAllPagesImpl()
最后，有关如何实现这些函数以及 BufferPoolManagerInstance 如何与 LRUKReplacer 交互的详细信息，请参阅 function documentation。
DiskManager
Disk Manager class (src/include/storage/disk/disk_manager.h) 从磁盘读取/写入 page 数据。 您的 buffer pool manager 将使用 DiskManager::ReadPage() 和 DiskManager::WritePage() 将 page 提取到 buffer pool 或将 page 刷新到磁盘。
Detailed Documentation
更详细的规范和文档，请参考头文件 (extendible_hash_table.h, lru_k_replacer.h, buffer_pool_manager_instance.h)。
INSTRUCTIONS
Testing
我们对单元测试用例使用 GTest。有三个单独的文件包含每个组件的测试：
ExtendibleHashTable: test/container/hash/extendible_hash_table_test.cppLRUKReplacer: test/buffer/lru_k_replacer_test.cppBufferPoolManagerInstance: test/buffer/buffer_pool_manager_instance_test.cpp
测试前要删掉测试文件中各函数前的 DISABLED_ 前缀。
$ mkdir build
$ cd build
$ make extendible_hash_table_test -j$(nproc)
$ ./test/extendible_hash_table_test
您还可以运行 make check-tests 检查测试来运行所有的测试用例。注意，有些测试是禁用的，因为您还没有实现以后的项目。可以通过在测试名称中添加 DISABLED _ 前缀来禁用 GTest 中的测试。
**Important: **这些测试只是我们将用来评估和评分项目的所有测试的一个子集。您应该自己编写额外的测试用例来检查实现的完整功能。
Fromatting
您的代码必须遵循 Google C++ Style Guide。我们使用 Clang 自动检查源代码的质量。如果您的提交没有通过任何这些检查，您的项目成绩将为零。
执行以下命令检查语法。 format将自动更正代码。 check-lint 和 check-clang-tidy 将打印错误，您必须手动修复，以符合我们的样式指南。
$ make format
$ make check-lint
$ make check-clang-tidy-p1
Development Hints
不要使用 printf 语句进行调试，而是使用 LOG_* macros 来记录信息：
LOG_INFO("# Pages: %d", num_pages);
LOG_DEBUG("Fetching page %d", page_id);
要在项目中启用 logging，需在 cmake 时添加 -DCMAKE_BUILD_TYPE=Debug 或在 IDE 中启用 debug mode。
src/include/common/logger.h 定义了不同的 logging level。enabling logging 后 logging level 默认为 LOG_LEVEL_INFO。任何级别等于或高于 LOG_LEVEL_INFO (e.g., LOG_INFO, LOG_WARN, LOG_ERROR) 的日志记录方法都将发出日志记录信息。
⚠️ 您需要将 #include "common/logger.h" 添加到希望使用日志记录基础结构的文件中。
我们鼓励在遇到问题时使用 gdb 来调试项目。
如果遇到编译问题，运行 make clean 不会完全重置编译过程。 在重新运行 make 之前，您需要删除构建目录并再次运行 cmake..。
SUBMISSION
完成作业后，你可以将你的实现提交到 Grescope: https://www.gradescope.com/courses/424375/
只需要包含以下文件：
- src/include/container/hash/extendible_hash_table.h
- src/container/hash/extendible_hash_table.cpp
- src/include/buffer/lru_k_replacer.h
- src/buffer/lru_k_replacer.cpp
- src/include/buffer/buffer_pool_manager_instance.h
- src/buffer/buffer_pool_manager_instance.cpp
或者，在您的 build/ 目录中运行 make submit-p1 将在您的项目根目录下生成一个名为 project1-submission.zip 的 zip 存档，您可以将其提交到 Gradescope。 这相当于在项目根目录中运行以下 zip 命令：
$ zip project1-submission.zip \
src/include/container/hash/extendible_hash_table.h \
src/container/hash/extendible_hash_table.cpp \
src/include/buffer/lru_k_replacer.h \
src/buffer/lru_k_replacer.cpp \
src/include/buffer/buffer_pool_manager_instance.h \
src/buffer/buffer_pool_manager_instance.cpp
答案可多次提交。
Notes on Gradescope and Autograder
- 如果您在 Gradescope 上超时，很可能是因为您的代码中存在死锁，或者您的代码太慢并且没有在 60 秒内运行。 如果您的代码太慢，可能是因为您的
LRUKReplacer效率不够高。 - 如果您在提交前不删除日志，自动评分器将无法工作。
- 如果自动评分器无法正常工作，请确保您的格式化命令有效并且您提交的文件正确。
- leaderboard benchmark score 将通过对您的
buffer_pool_manager_instance实施进行压力测试来计算。