参考

CMU 15-445 Project 2 (Spring 2023) | 关于 B+Tree 的十个问题

对crabbing lock、乐观锁做了详尽解释

Project2 B+Tree

In this programming project you will implement a B+Tree index in your database system.

Your implementation will support thread-safe search, insertion, deletion (including splitting and merging nodes包括分裂和合并结点), and an iterator to support in-order leaf scans.

它这里的B+树（以及wiki里的）跟王道考研讲得不大一样。王道考研的B+每个结点一个关键字对应一个child，但是这里的是B树的形式。

undefined

image-20230417181239196

Task1 B+Tree Pages

You must implement three Page classes to store the data of your B+Tree:

  1. B+Tree Page BPlusTreePage

    下面那两个的基类

  2. B+Tree Internal Page

    An Internal Page stores m ordered keys and m+1 child pointers (as page_ids) to other B+Tree Pages.These keys and pointers are internally represented as an array of key/page_id pairs.

    Because the number of pointers does not equal the number of keys, the first key is set to be invalid, and lookups should always start with the second key.

    At any time, each internal page should be at least half full.【min_size<= <=max_size】

    During deletion, two half-full pages can be merged, or keys and pointers can be redistributed to avoid merging. During insertion, one full page can be split into two, or keys and pointers can be redistributed to avoid splitting.

  3. B+Tree Leaf Page

    The Leaf Page stores m ordered keys and their m corresponding values. In your implementation, the value should always be the 64-bit record_id for where the actual tuples are stored; see the RID class, in src/include/common/rid.h.

    *Note:* Even though Leaf Pages and Internal Pages contain the same type of key, they may have different value types. Thus, the max_size can be different.

大概就是有一个基类结点，它有两个子类，一个表示b+树的leaf node，另一个表示b+树的internal node，每个结点都占据一个内存页。

也就是说，一个内存页中存储着一个结点类对象。每次我们都是读取一页到内存中，然后将它类型转换为TreeNodePage*，就可以访问其里面的存储数据的数组array_了。体会一下这个思想。

值得一提的是，LeafPage的成员变量中有个这样的成员：

1
2
3
private:
 // Flexible array member for page data.
 MappingType array_[0];

它就是柔性数组成员。

在C++中，Flexible Array Member（柔性数组成员）是一种用于定义具有可变大小的结构的技术。它通常用于在结构的末尾声明一个数组，该数组的大小是动态确定的，这允许你在使用该结构时更灵活地处理变长数据。

在你提供的代码片段中，MappingType array_[0]; 是一个柔性数组成员的例子。这里 array_ 后面有 [0]，这并不表示它们的大小是固定的0。相反，它们的大小是在运行时动态确定的，而 [0] 的写法是一种历史上的技巧，用于告诉编译器这是柔性数组成员。

例如，如果有一个结构定义如下：

1
2
3
4
struct MyStruct {
    // 其他成员...
    MappingType array_[0];
};

你可以根据需要为 array_ 分配任意数量的内存，例如：

1
2
3
4
5
6
7
int arraySize = 10;  // 你想要的数组大小
MyStruct* myObject = static_cast<MyStruct*>(operator new(sizeof(MyStruct) + arraySize * sizeof(MappingType)));

// 在这里你可以使用 myObject，并通过 myObject->array_ 访问柔性数组

// 记得在使用完毕后释放内存
operator delete(myObject);

在这个例子中，array_ 可以用于存储可变大小的数据，而结构体 MyStruct 的大小将动态地调整为 sizeof(MyStruct) + arraySize * sizeof(MappingType)。这样的设计通常在需要处理变长数据块的场景中比较有用。请注意，在C++17之后，你也可以使用 std::byte 类型来定义柔性数组成员。

拥有柔性数组成员的实例需要动态分配内存（或者像接下来的把一块内存空间interpret一下），柔性数组成员会占用其他成员没有占用的剩下的空间，也即：

1
2
3
4
5
6
7
8
+--------------------------+
| Other Members of MyClass |
| ...                      |
+--------------------------+
| array_ (flexible)        |
|                          |
|                          |
+--------------------------+

Task2a Insertion and Search + Task3 Iterator

The index should support only unique keys; if you try to reinsert an existing key into the index, it should not perform the insertion, and should return false. key必须unique

B+Tree pages should be split (or keys should be redistributed) if an insertion would violate the B+Tree’s invariants. 插入时需要分裂

If an insertion changes the page ID of the root, you must update the root_page_id in the B+Tree index’s header page. You can do this by accessing the header_page_id_ page, which is given to you in the constructor. Then, by using reinterpret_cast, you can interpret this page as a BPlusTreeHeaderPage (from src/include/storage/page/b_plus_tree_header_page.h) and update the root page ID from there. You also must implement GetRootPageId, which currently returns 0 by default.对root_page_id的一切访问，都需要通过header_page_id_。如果插入后改变了root的page ID，需要更新root_page_id。

We recommend that you use the page guard classes from Project 1 to help prevent synchronization problems. For this checkpoint, we recommend that you use FetchPageBasic (defined in src/include/storage/page/) when you access a page. 在当前task中，我们推荐你使用pro1实现的page guard，比如说这里如果要访问一页，就需要用 FetchPageBasic 。

You may optionally use the Context class (defined in src/include/storage/index/b_plus_tree.h) to track the pages that you’ve read or written (via the read_set_ and write_set_ fields) or to store other metadata that you need to pass into other functions recursively.你可以随意使用和修改 Context class，它大概就是一个存储共享信息的对象。

If you are using the Context class, here are some tips:如果你要用，要注意以下几点：

  • You might only need to use write_set_ when inserting or deleting. 当你在为B+树插入/删除结点时，需要用到write_set_。【为什么？这个set存储的是修改路径上的结点吗？然后如果要分裂/合并结点，只需什么while(pop且需要分裂/合并){分裂/合并}？？所以说这里的deque是栈结构？】

    也就是说，其实我们就可以不用递归了，而是将上下文存储在context->write_set_这个栈里面就行了？大概是这个意思吧

    It is possible that you don’t need to use read_set_, depending on your implementation.

    read可以用递归（比较简单）也可以不用，所以说具体看实现。

  • You might want to store the root page id in the context and acquire write guard of header page when modifying the B+Tree.你需要将root page id存储在context，并且在修改b+树（插入、删除）时获取header page的WritePageGurad。

  • To find a parent to the current node, look at the back of write_set_. It should contain all nodes along the access path.如果想要寻找当前node的父亲，可以看看write_set_.back，它包含了访问路径上所有结点的引用【所以确实是当成栈来用了】

  • You should use BUSTUB_ASSERT to help you find inconsistent data in your implementation. 需要使用 BUSTUB_ASSERT。

    For example, if you want to split a node (except root), you might want to ensure there is still at least one node in the write_set_. If you need to split root, you might want to check if header_page_ is std::nullopt.

    如果你想要分割一个根节点以外的node，那你必须保证write_set_中至少有一个结点；如果你想要分割根节点，那你必须保证header_page_非空。

  • To unlock the header page, simply set header_page_ to std::nullopt. To unlock other pages, pop from the write_set_ and drop.如果你想要不锁住header page，那就置其为空指针；如果想释放别的页，那就将它从 write_set_ pop出来就行。【这是因为我们要用到的page类型都是page guard，可以析构时unpin吗？】

感想

由于各种原因，lab2的战线还是拉得太长了。四月份完成了代码初版，中间修了几个bug勉强通过了insertion test，然后一直到十一月底的现在才再次捡起来。不得不说，回看当初的代码，还是能够很清晰地感受到自己这半年多来的成长的，令人感慨。

我先是花了一天的时间重构了下以前写的所有代码，然后再花了两天时间修bug终于通过了insertion test和sequence scale test，并且将b+树的代码修到了我满意的地步（指不像以前那样一坨重复代码和中文注释。。。）。

思路

这里简要介绍下B+树的插入实现及我觉得实现中需要注意的几个要点吧。

B+树的插入流程大概是这样的：

  1. 查找到key要插入的叶子结点（途中需要维护write_set，也即查找路径）

  2. 判断结点是否满

    1. 未满，直接插入即可。（我采取插入排序的方法）

    2. 已满，需要对结点进行分裂。

      推举出中间结点tmp_key，它和新结点page_id接下来将插入到父节点中。

  3. 持续进行分裂：

    需要注意具体的分裂方法，我认为其中internal page size == 3的情况尤为棘手。在具体实现中，我是这样分裂的：

    1. 推举出将要被插入到父节点的tmp_key

      该推举出的key将不会出现在分裂后的新旧结点中，而是会被加入到父节点中。默认为(m + 1) / 2【m为max size】。

      但是要尤其注意size为3的case，此时tmp_key为array_[2]，很有可能右边结点为空。所以我们需要做点特殊处理：

      1. 当要插入到该节点的insert_key > array_[(m + 1) / 2]时，我们推举(m + 1) / 2这个结点。
      2. 当insert_key < array_[m / 2]，我们转而推举m / 2（此时为array_[1]）。
      3. 当insert_key < array_[(m + 1) / 2]且insert_key > array_[m / 2]时，我们应该对此做出特殊处理，推举insert_key。在此为了代码实现方便，我们还需要调换insert_key和tmp_key的地位。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      special = false;
      middle = (m + 1) / 2;
      tmp_key = root->KeyAt(middle);
      insert_small_than_tmp_key = (comparator_(insert_key, tmp_key) < 0);
      if (insert_small_than_tmp_key) {
        middle = m / 2;
        tmp_key = root->KeyAt(middle);
        if (comparator_(insert_key, tmp_key) >= 0) {
          special = true;
          swap = insert_key;
          insert_key = tmp_key;
          tmp_key = swap;
        }
      }

    2. 分裂旧结点

      被推举出的tmp_key的value及其右部元素会变成新结点，左部依然留在旧结点，tmp_key会到父节点中去。也即如下图所示：

      ![未命名文件 (1)](./cmu15445/未命名文件 (1).png)

      依然是注意上面那个case3特殊情况，需要交换insert key和middle key：

      1
      2
      3
      4
      5
      6
      if (!special)
        new_page->SetValueAt(0, root->ValueAt(middle));
      else {
        new_page->SetValueAt(0, insert_val);
        insert_val = root->ValueAt(middle);
      }

    3. 持续进行推举和分裂，直到父节点不用分裂

      此时直接将insert key和insert value插入排序到父节点即可。

然后是Iterator的话，我感觉这也是设计得很不错，让我们亲手写了下c++的重载运算符，也是让我学到了很多c++知识。。。

遇到的问题

感觉问题其实不多，主要还是debug有点痛苦花了很长时间（）

cmake报错

切换内核前后报错。

Check for working C compiler: /usr/bin/cc - broken

感觉可能是内核切来切去，导致cmake cache发生了点小问题？总之我最后在5.11内核把build文件删了，重新执行cmake -DCMAKE_CXX_COMPILER=$(which g++) -DCMAKE_C_COMPILER=$(which gcc) ..就ok了。

page guard

用错了

image-20230505002652748

我发现在这里创建的root最后好像会被释放掉？

比如我看到新root的page为6，连接也做得好好的，最后出了函数就寄了：

image-20230505002731312

还有一个是发现新的leaf page好像不大对，其类型甚至是internal呃呃，我调下看看

尼玛，绷不住了是这里：

image-20230505011731797

原来写的

image-20230505011744924

改了之后test2马上ok，乐

作用域

还弄了个commit修:

image-20231130222702358

一点c++引用震撼

1
auto INDEXITERATOR_TYPE::operator*() -> const MappingType &

这个函数卡了我还挺久。。。里面逻辑很简单，不过难就难在怎么构造出一个const MappingType &。

如果这样：

1
2
3
4
5
6
INDEX_TEMPLATE_ARGUMENTS
auto INDEXITERATOR_TYPE::operator*() -> const MappingType & { 
    auto page = guard_.As<LeafPage>();
    return std::pair<KeyType, ValueType>(page->KeyAt(cnt_), page->ValueAt(cnt_));
    // or use make_pair. the same result
}

会说你临时对象不能作为引用。如果这样：

1
2
3
4
5
6
INDEX_TEMPLATE_ARGUMENTS
auto INDEXITERATOR_TYPE::operator*() -> const MappingType & { 
    auto page = guard_.As<LeafPage>();
    auto res = new MappingType(std::pair<KeyType, ValueType>(page->KeyAt(cnt_), page->ValueAt(cnt_)));
    return *res;
}

又会找不到机会delete导致内存泄漏。冥思苦想了半天不知道该怎么办，最后从网上看了别人怎么写的：

1
2
3
4
5
6
7
8
9
10
INDEX_TEMPLATE_ARGUMENTS
auto INDEXITERATOR_TYPE::operator*() -> const MappingType & { 
    auto page = guard_.As<LeafPage>();
    return page->PairAt(cnt_);
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::PairAt(int index) const -> const MappingType & {
  return array_[index];
}

我服了。

不过可能有更好的解决方法？可惜我c++水平不大够，所以暂时想不出来了。

Task4 Remove

感想

由于有了insert的沉淀，remove的实现便相较不大困难了，写完代码到通过内置的delete测试只花了一天的时间。

思路

  1. 找到需要操作的叶结点路径

  2. 判断叶子结点属于以下四种策略中的哪一种，执行对应策略（优先级从高到低）：

    1. 直接删除

      当删除后叶结点元素数仍在合法范围，并且路径上父节点没有target key，直接删除然后返回即可。

    2. 更新父节点路径

      当删除后叶结点元素数仍在合法范围，并且路径上父节点有target key，直接删除然后向上回溯更新父节点即可。

    3. 窃取兄弟元素

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      If do a steal, we should update related key in the parent, and update up till reaching the root.
         
        /*
          For that steal is more simple, we first check whether it can do a steal first.
          We steal the node whose size is biggest between the next and the prev node.
          If the prev size is bigger, we only update self key in parent.
          If the next size is bigger, we update both self key and next key n parent.
          After that, we trace back and update all the parent nodes which contains the
          target key.
        */

      当删除后叶结点元素数过少，并且左右兄弟元素充足，则从左右兄弟窃取一个。优先窃取元素最多者。

      1. 窃取左兄弟

        窃取左兄弟的最大元素

        需递归更新自身父节点路径上的对应值。

      2. 窃取右兄弟

        窃取右兄弟的最小元素

        需要递归更新自身和右兄弟父节点路径上的对应值。

      之后返回即可。

    4. 合并

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      /*
        Need to merge with one of the node. It is more simple to try to merge the left node
        first. So the strategy:
        1. Pick the prev node to merge. (If leaf is most left, pick next node)
        2. Update delete-key. (for prev, it's leaf[0]; for next, it's right key, and need
          to update self)
        3. Go up till reaching root. Do:
          1. delete delete-key.
          2. pick merging or stealing like above.
            1. if merge, update delete-key, go up;
            2. if steal, break to do update and has no need to go up.
        4. Remember to deal with edge case: root.
      */

      当删除后叶结点元素数过少，并且左右兄弟元素也都是最小值，那么需要与左右兄弟之一进行合并。优先合并左兄弟。合并都为大->小，也即target->左兄弟 或者 右兄弟->target。

      需要递归删除父节点路径上的merge from元素。

  3. 可以看到，1/2/3三种情况都可以实现简单地直接返回。4稍显复杂，由于递归删除，所以需要对每一个父节点都再次进行上面几种策略的判断，直到遇到情况123返回为止。

遇到的问题

一个比较sb的小bug……

image-20231204163052528

Task5 Concurrency

感想

这位可更是重量级，足足花了我三天的时间……不过感觉第一次处理这么一个复杂的并发情景，花的时间还是值得的。

最后的结果虽然很一般（指排行榜倒数水平。。。），但至少还是过了。就先这样吧。

image-20231204170030245

思路

我实现了crabbing lock+optimal lock。对于Insert和Remove，都是先在一开始获取header page和路径上父节点的读锁，然后在之后有可能向上更新时（比如说Insert的需要分裂、Remove的Update和Merge两种情况），丢弃所有读锁，然后获取header page和路径上父节点的写锁。

不过感觉我这个思路还是略有粗糙，因为相当一部分时间都得占用header page的写锁。但是我思考了一下细粒度方案，发现还是有点难实现。比如说，对于insert，细粒度化的方式也许就是一直持有header page的读锁，一直到需要分裂根节点时，才释放读锁获取写锁。但这样一来就会暴露一个危险的空窗期（而且感觉这个空窗期还不小），当你真的拿到写锁，这树的结构可能已经变得不知道什么样了。在这种情况下，你就需要再做一次回溯工作，也即获取从新root结点到旧root结点的路径，递归插入insert key和insert value，最后安全分裂根节点（因为此时已经安全持有了header page写锁）。感觉思路也是比较易懂，但是实现上还是太麻烦了，所以先暂且搁置吧。

遇到的问题

这种感觉大多还是在面向测试用例见招拆招……所以其实感觉没什么好说的。

bpm遗留

这个并发问题是这样的，我原来是先evict，然后再写回被替换的页面，写回过程中磁盘没加bpm锁。这就会出现这样一个情况：

一个page被进程A evict，进程A还没执行写回的时候这个page又被进程B捡回来了，因为还没写入所以磁盘空空如也。这时候pages_latch_这个细粒度锁不能防范这种情况，是因为此时这个page对应的container不是同一个，所以fid不同，细粒度锁不同导致寄。

解决方法是要么写的时候持有bpm锁，但是这太太慢了。另一个就是干脆直接在unpin的时候不带bpm锁顺便写回了。也即把写回从evict后移到unpin中立即写回：

1
2
3
4
if (pages_[fid].GetPinCount() == 0 && pages_[fid].IsDirty()) {
  pages_[fid].is_dirty_ = false;
  disk_manager_->WritePage(pages_[fid].GetPageId(), pages_[fid].GetData());
}

火焰图性能分析

FlameGraph

参考博客

看起来感觉大多性能损耗还是在bpm上，特别是LRU-K。也许是我的全局锁太暴力了。

out