Project #2 - B+Tree-526互联

项目要求: https://15445.courses.cs.cmu.edu/fall2022/project2/

CHECKPOINT #1

Task #1 - B+Tree Pages

实现三个 page class 来存储 B+Tree 的数据。

src/include/storage/page/b_plus_tree_page.h

src/storage/page/b_plus_tree_page.cpp

父类，只包含两个子类共享的信息。

Variable Name	Size	Description
page_type_	4	Page Type (internal or leaf)
lsn_	4	Log sequence number (Used in Project 4)
size_	4	Number of Key & Value pairs in page
max_size_	4	Max number of Key & Value pairs in page
parent_page_id_	4	Parent Page Id
page_id_	4	Self Page Id

B+Tree Internal Page

src/include/storage/page/b_plus_tree_internal_page.h

src/storage/page/b_plus_tree_internal_page.cpp

一个 Internal page 并不存储任何真实的数据，而是存储一个有序的 m 个 key 和 m+1 个 child pointers（又称page_id）。由于 pointer 的数量不等于 key 的数量，第一个 key 被设置为无效，查找方法应该总是从第二个 key 开始。在任何时候，每个 Internal Page 至少有一半是满的。在删除过程中，两个半满的 page 可以 merge 成一个合法的 page，或者可以 redistribute 以避免 merge，而在插入过程中，一个满的 page 可以被 split 成两个。

B+Tree Leaf Page

src/include/storage/page/b_plus_tree_leaf_page.h

src/storage/page/b_plus_tree_leaf_page.cpp

Leaf page 存储了一个有序的 m 个 key 和 m 个 value。在你的实现中，value 只应该是 64 位的 record_id（用来定位 tuple 实际存储的位置），见 src/include/common/rid.h 中定义的 RID 类。Leaf Page 在 key/value pairs 的数量上有与 Internal pages 相同的限制，并且应该遵循相同的 merge、redistrihute、split 操作。

Important：即使 leaf pages 和 internal pages 包含相同类型的 key，它们可能有不同类型的值，因此 leaf pages 和 internal pages 的 max_size 可能不同。

Important：每个 B+Tree 的 leaf pages/internal pages 都对应于由 buffer pool 获取的内存页的内容 (i.e., the data_ part)。因此，每当你试图读或写一个 leaf pages/internal pages 时，你需要首先使用其唯一的 page_id 从 buffer pool 中获取该页，然后 reinterpret cast 为一个 leaf pages/internal pages，并在任何写或读的操作后 unpin the page。

Task #2 - B+Tree Data Structure

src/include/index/b_plus_tree.h

src/storage/index/b_plus_tree.cpp

你的 B+Tree Index 应该只支持 unique keys。也就是说，当你试图在 Index 中插入一个 key 重复的 key-value pair 时，它不应该执行插入并返回 false。如果删除导致某些页面低于占用阈值，你的 B+Tree Index 也必须正确执行 merge 或 redistribute（在教科书中称为 "coalescing"）。

对于 Checkpoint #1，你的 B+Tree Index只需要支持插入 Insert()，点搜索 GetValue()，和删除 Delete()。如果插入触发了 split 条件（插入后的 key/value pairs 的数量等于 leaf node 的 max_size，插入前的 children 的数量等于 internal node 的 max_size），应该正确执行 split。由于任何写操作都可能导致 B+Tree Index 中root_page_id 的改变，你需要更新 header page（src/include/storage/page/header_page.h）中的 root_page_id，这是为了确保索引在磁盘上是持久的。在 BPlusTree 类中，我们已经为你实现了一个名为 UpdateRootPageId 的函数；你所需要做的就是在 B+Tree 索引的 root_page_id 发生变化时调用这个函数。

Your B+Tree implementation must hide the details of the key/value type and associated comparator, like this:

template <typename KeyType,
          typename ValueType,
          typename KeyComparator>
class BPlusTree{
   // ---
};

These classes are already implemented for you:

KeyType: The type of each key in the index. This will only be GenericKey, the actual size of GenericKey is specified and instantiated with a template argument and depends on the data type of indexed attribute.
ValueType: The type of each value in the index. This will only be 64-bit RID.
KeyComparator: The class used to compare whether two KeyType instances are less/greater-than each other. These will be included in the KeyType implementation files.

CHECKPOINT #2

Task #3 - Index Iterator

src/include/storage/index/index_iterator.h

src/index/storage/index_iterator.cpp

要建立一个通用的 index iterator 来有效地检索所有的 leaf pages。基本的想法是将它们组织成一个单一的链表，然后按照特定的方向遍历存储在 B+Tree leaf pages 中的所有 key/value pairs。你的 index iterator 应该遵循 C++17 中定义的 Iterator 的功能，包括使用一组 operators 来迭代一系列元素和 for-each 循环（ increment, dereference, equal and not-equal operators）。注意，为了支持你的 index 的 for-each 循环功能，你的 B+Tree 应该正确实现 begin() 和 end()。

你必须在 IndexIterator 类中实现以下函数。

isEnd(): Return whether this iterator is pointing at the last key/value pair.
operator++(): Move to the next key/value pair.
operator*(): Return the key/value pair this iterator is currently pointing at.
operator==(): Return whether two iterators are equal.
operator!=(): Return whether two iterators are not equal.

Task #4 - Concurrent Index

在这一部分，你需要更新你原来的单线程 B+Tree index，使其能够支持并发操作。我们将使用课堂上和课本中描述的 latch crabbing 技术。线程遍历 index，将在 B+Tree pages 上获取然后释放 latches。一个线程只会在 child page 被认为是 "safe" 时，才会释放在其 parent page 上的 latch。请注意，根据线程正在执行的操作的不同，"safe" 的定义不同：

Search: 从 root page 开始，一旦获取到 child 的 read (R) latch 然后释放其 parent 的 latch
Insert: 从 root page 开始，获取 child 的 write (W) latch。锁住 child 后检查它是否 safe (not full)，若 safe 则释放祖先上的所有锁。
Delete: 从 root page 开始，获取 child 的 write (W) latch。锁住 child 后检查它是否 safe (至少 half-full，但对 root page，有不同的标准)，若 safe 则释放祖先上的所有锁。

Important：此处只描述了 latch crabbing 背后的基础概念，在实现前，请参考 lecture and textbook Chapter 15.10。

Requirements and Hints

不允许使用全局范围的 latch 来保护数据结构，换言之，不能 lock 整个 index 然后在操作完成后 unlock the latch。我们将通过语法和手工检查来确保你以正确的方式进行 latch crabbing。
我们提供了读写锁的实现 (src/include/common/rwlatch.h)，且已经在 page 头文件 (src/include/storage/page/page.h) 中添加了获取和释放 latch 的辅助函数。
我们不会在 B+Tree index 中添加任何强制性接口，你可以在你的实现中添加任何函数，只要保持所有原来的公共接口不动，达到测试目的就行。
不要使用 malloc/new 来为 tree 分配大块内存。如果你需要为 tree 创建一个新结点 or 需要一块 buffer 来完成一些操作，你需要使用 buffer pool。
对于本节 task，你必须使用传入的名为transaction的指针参数 (src/include/concurrency/transaction.h)。它提供了一些方法来存储你在遍历 B+Tree 时要求获取 latch 的 page，也提供了一些方法来存储你在 remove 操作中删除的 page。我们的建议是仔细研究 B+Tree 中的 FindLeafPage 方法，你可以修改你以前的实现（注意，你可能需要改变这个方法的返回值），然后使用这个特定的方法中加入 latch crabbing 的逻辑。
buffer pool manager 中 FetchPage() 的返回值是一个指向 page 实例 (src/include/storage/page/page.h) 的 pointer。你可以获取一个 Page 的 latch，但不能获取一个 B+Tree node (无论是 internal node 还是 leaf node) 的 latch。

Common Pitfalls

在本项目中，将测试 thread-safe scan (只测试没有并发的 iterator 操作)，一个正确的实现会要求 leaf page 在无法获取它 sibling 的 latch 时抛出 std::exception，以避免死锁。
仔细思考 buffer pool manager 类的 UnpinPage(page_id, is_dirty) 和 page 类的 UnLock() 方法之间的关系，必须在 unpin page 之前释放它的 latch。
如果你正确地实现了并发的 B+Tree index，那么每个线程都会从root 到 bottom 获取 latch。当你释放 latch 时，请确保也遵循同样的顺序（也是从 root 到 bottom）。
其中一种情况是，当插入和删除时，成员变量 root_page_id(src/include/storage/index/b_plus_tree.h) 也将被更新。你有责任保护这个共享变量不被并发更新（提示：在B+Tree index 中添加一个抽象层，你可以使用 std::mutex 来保护这个变量）。

INSTRUCTIONS

本地测试

$ cd build
$ make b_plus_tree_insert_test -j$(nproc)
$ ./test/b_plus_tree_insert_test

本项目还提供了 B+Tree 的可视化版本，具体看官网。

SUBMISSION

$ cd build
$ make format
$ make check-lint
$ make check-clang-tidy-p2
$ make submit-p2