Project

做这个p3首先需要明晰整个bustub的架构[[Bustub执行器架构简单分析]],在这个文章中进行了很详细的分析。

CHECKPOINT-2 Task #3 - Index Iterator 简单来说就是实现一个迭代器 将所有的叶子节点视为一个链表，要求实现给出的函数。在当前的迭代器中保存所在的pageId和当前的起始位置，然后通过leafpage中的next_page_id来获取下一个叶子节点。 总体上来说难度不是很大，没有什么好说的，就是还是注意要加锁，其中的某一个函数在实现的时候需要考虑跨页的情况，这时候就要考虑加锁和去锁的情况了。 Task #4 - Concurrent Index 这就是要完实现一个多线程的b+树，加锁的实现方式和原理在[[B+ Tree Index#b+ tree latches]]中有比较详细的介绍，这里我简单的解释一下。 这是整个项目的重点也是难点，考察对b+树整个结构和每个操作涉及到的点，当然可以像之前的项目一样一把大锁报平安，但是对于b+树来说这样会使的性能约等于单线程，每次都需要从根节点进入整个树，但是一把大锁就意味着每次整个树中都只能存在一个线程在操作。。。 所以我们需要更细粒度的锁，于是螃蟹锁🦀应运而生。 ：）rust的吉祥物也是个螃蟹吧。。 ==螃蟹锁== 因为其加锁和解锁的过程以及逻辑特别像螃蟹的行走的方式，因此而得名螃蟹锁。 读模式 在读模式的时候最为形象，当获取到父节点的读锁之后，尝试着获取目标子节点的读锁，当获取到锁之后立马释放父节点的锁 在上图中，一个线程获取A页的锁之后会尝试着获取目标子节点B的锁，当获取B的锁之后就会释放A的锁。如此循环往复，就像螃蟹在走。 写模式 写模式的时候只是锁释放的条件不一样，读模式的时候当获取的下一个页的锁的时候就可以立马释放当前页的锁，但是写模式涉及到插入和删除，可能整个路径上的页都会受影响。 如上图所示，当获取到B页的锁的时候不能释放A页的锁，因为B有可能会发生合并，于是继续向下获取锁，获取到C页的锁之后发现C页是处于安全状态的。所以可以释放C页之上的所有锁。⚠️注意：并不包括C本身。 安全状态 安全状态的这个概念只存在于写模式的时候。需要注意的是：在删除和插入的时候页处于安全状态的条件并不一样。 在插入的时候：该页不是满的—–》就算发生分裂的情况，到此页也就结束了。 在删除的时候：大于半数———》就算删除之后发生合并或者重新分配到此页就结束了。 螃蟹锁的优势在哪里？ ⚠️这里的优势是相较于一把大锁而言。 虽然B+树可以做的很高很大，但是无论如何都只有一个入口。如果每次都是一把大锁，那不管什么操作都会先获取根节点并且锁住，那直接就编程单线程的了。 所以整个的瓶颈就是根节点上锁的时间太长了。影响了并发。所以螃蟹锁的优势就在于： 能够显著的减少根结点上锁的时间，让更多的线程进入B+树进行操作 更优的螃蟹锁执行策略 当前释放的策略仍然拥有很大的优化空间。在原来的策略上写模式的时候会对根节点上写锁，知道找到一个安全节点之后才会释放，这就占用了很长时间，导致效率降低。这种不分青红皂白的直接给各个节点上写锁的行为称之为悲观锁。顾名思义，悲观锁表示这种策略对多线程的执行非常的悲观，觉得每个页都会被修改，必须都上锁才安心。但是事实上在实际的应用过程中触发分裂或者合并并不是很频繁。 所以就诞生了一种更优的加锁策略乐观锁，在写模式的时候就大胆的假设从根节点到最后的叶子节点都是安全的，给路径的页都上读锁，最后的叶子节点才上写锁。如果在这个过程中发现了某个节点跟假设的不一样，不是安全的，那么之前的所有锁都释放，再重新按照悲观锁的方式进行操作。 这样做的好处是，在相较于悲观锁乐观锁在一定程度上能改善根节点总是上写锁导致并发时读取效率的降低。 但是我本人还没有实现乐观锁，修改FindLeafPage()或者添加FindLeafPageHelper()应该都是可以的。 具体实现 ==GetValue（）== 如上如所示，当获取到下一个读锁的时候就释放父节点的读锁，然后接着循环这样的操作 这样子像螃蟹走路的方式，也是这种加锁策略的由来。 ==Insert（）== 还有一个图我懒得画了，page4也是不安全的，所以page2、3、4.在这里都不能释放。 找到一个安全的节点之后如何安全有便捷的释放所有父节点链的锁呢？ ==Remove（）== 移除和上图大同小异啦，就是判断安全的条件不一样啦。注意一下就好了 Transaction、事务 这里就用到了我在checkpoint1中提到的这个东西[[CMU15-445 Project2-B+ Tree Index Checkpoint 1#^d53eec|对Transaction的详细介绍]],可以翻看前文。 它可以跟踪记录某个线程上的锁，并且是按照顺序的。从上到下。便于进行统筹操作。 由于越往上page越密集，竞争越激烈，在释放锁的时候可以优先释放处于顶部的锁，也算是一个小优化🤣。 Summary 整个checkpoint2想较于checkpoint1来说我觉得需要注意的事情更多。特别是对根节点的加锁时机的把握，很重要的。难度我觉得是有提升的。 写完这个让我体会最深的是，代码写完整个工作完成百分之20，跑起来并且过本地测试勉强算完成一半，线上测试是真难啊啊啊，每次卡玩都回来一点一点看log👀，眼瞪的比黑猫警长还大。 最后附上通过截图。 ...

一些工具 BusTub B+Tree PrinterCMU官方在线的B+树的生成工具。我主要用来细节实现的时候进行参考。 JavaScript B+ TreeB+树插入和删除的动态演示。 Graphviz Online可视化自己的树。在debug的时候会用到。将生成的dot文件转换成svg图片。 Log In | Gradescope在线评测网站,邀请码：PXWVR5， Project #2 - B+Tree | CMU 15-445/645 :: Intro to Database Systems (Fall 2022)最重要的当然还是课程网站了 课程的视频，还有对应的教材还是推荐看一下的上面有很多实现细节的。非常值得参考。 如何Debug自己的🌳 大致上可以分为两种方式 可视化的用自带的printer将树生成dot文件然后复制到上面的可视化网站。 由于本项目采用的是cmake构建的，所以可以很方便的在测试文件中打上断点。进行调试。 ==可视化调试== 在终端中执行以下命令，构建和执行printer。 ➜ build git:(main) make b_plus_tree_printer -j2 // 构建printer ➜ build git:(main) ./bin/b_plus_tree_printer // 执行printer 执行完之后就会有以下提示： 按照这个提示就可以生成dot文件，然后复制到上述的网站进行可视化。（当你看到自己的树呈现出来的时候还是非常有成就感的😁） ==非可视化== 可以很方便的直接打断点，然后在vscode中的cmake插件中选择调试进行debug。 官方还提供了一种大打log的方式进行debug，我是不太习惯这种方式所以没有进行很深入的研究。感兴趣的可以自己进行了解😗。 两种debug的方式是相辅相成的，在你过不了本地样例的时候好好的用非可视化的方式进行debug，线上样例过不了大部分原因是细节处理上出问题了。用可视化的方式会更加的直观。 请不要公开代码，尊重Andy劳动成果 概览 Project2是实现B+树索引，整个project大致被分为了两个部分 checkpoint1：实现一个单线程的b+树。 checkpoint2：实现一个多线程的b+树。 实验代码中给出的自由发挥的空间非常的大，只给出了Getvalue(),Insert(),Remove()这三个函数的接口，剩下的所有的实现都非常的自由，整个实验实现的过程就像一个黑盒一样，只在乎输入和输出。 本实验需要完成b+ index部分，b+树中的页（page）都需要从上一个实验中实现的buffer pool中取。 Checkpoint-1 Task #1 - B+Tree Pages 需要完成以下三个page，主要都是一些getter和setter的函数，重在理解各部分的组成。 B+Tree Parent Page B+Tree Internal Page B+Tree Leaf Page 其中parentPage是internal page和leaf page的父类。我更倾向于把这几个page类型理解为 从buffer pool中取回来的Page的不同解释形式。Page还是那个Page。主要就是在于你如何去解释它的组成部分。 ...

环境搭建 按照P0的指导中进行环境的搭建，由于我本人现在时WIN平台，课程没有提供一键配置环境的脚本，所以我选择云服务器进行环境的构建，很稳。 但是我的云服务器配置只有2核2G在编译的时候会爆内存。这里还有个故事，在爆内存之后我已经意识到这个问题，我给阿里云客服提了个工单试图能白嫖一些配置，客服还是很有水平的，直接就分析出来我是内存爆了导致的，但是直接建议我加钱升级配置，不告诉我设置swap分区，有点不厚道了。 话说回来，设置完swap分区之后就没有再出现过爆内存的现象。用VScode的远程开发，体验还是很不错的。 Overview p1主要是内存管理部分的内容，这门课程的课本和录制视频还是很有必要看一下的。 主要的任务是以下三个部分： 可扩展的哈希表 LRU-K的淘汰策略的视线 Buffer Pool的一个实例 在开始梳理项目之前我想要先解释清楚一下三个任务之间的关系，以及各个部分的负责。 frame更像是一个载体，而page是其中的内容。打个比方来说，一个仓库（buffer pool）只有100辆货车（frame），而货物（page）成千上万种，每次都是仓库告诉货车需要什么货物然后由货车带着货物来到仓库，而可扩展的哈希表就是登记货车和货物的对应关系。因为只有100辆货车，当每辆车都是满的时候（没有闲置的车辆free_list不为空）就需要根据task2的LRU-K算法挑选出一个符合要求的货车清空后去装载指定的货物。 而task3就是负责整个的管理和交互。 大概解释了一下，可能比方不是很恰当，做的时候一定要多看文档和注释，因为漏看注释给我带来了极大的痛苦。 Task #1 -ExtendibleHashTable 相关函数 Find(K,V): 查询一个Key是否存在，如果存在则将其V指针指向相关的值，返回true，否则返回false Insert(K,V): 插入一个（K，V），如果插入失败需要进行一下步骤的重试： 插入失败肯定是桶满了，但是桶满了分为两种不同的情况。 一种是global深度和桶的local深度不相同的时候，需要对桶进行重新的分配。 当两个深度相同的时候说明桶是真的满了，需要对哈希表进行扩展 Remove(K): 在哈希表中移除对应的（K，V）对，但是需要进行哈希表缩小的操作。 IndexOf(K): 当前global深度下的映射规则。 项目架构 首先要清楚这个是自己动手实现一个可扩展哈希表用于保存frame和page的映射关系的。我觉得首先要明白frame和page之间的关系。不清楚的可以回看上文的解释。 Bucket 存储桶 在可可以扩展的哈希表种引入和Bucket的概念，用于解决哈希冲突的问题，每一个Bucket的大小都是固定的，当一个Bucket满了的时候就需要进行哈希表的扩展。 Bucket的组成 depth_：表示本地深度的一个标识，用于识别当前的深度是否和全局深度相同。要特别注意这个变量。 list_：发生哈希冲突时保存多个（K，V）映射的双向链表。 size：为了保证效率，list的长度不能无限延伸，所以达到一定长度的时候要进行哈希表的扩展。 可扩展的哈希表结构 Bucket_size:用于限制每个bucket的list的长度 dir_:用于哈西运算后保存映射关系。 global_depth_:全局深度，在插入的时候根据全局深度和局部深度来确定这个桶是否要进行重新的分配。 num_buckets:用于统计现在一共有多少bucket。 ReHash的过程详解 1.hash的规则是什么样的 template <typename K, typename V> auto ExtendibleHashTable<K, V>::IndexOf(const K &key) -> size_t { int mask = (1 << global_depth_) - 1; return std::hash<K>()(key) & mask; } 上述函数就是该哈希表的映射规则，总的来说就是取hash函数值的低global_depth位 假如现在global_depth_的值为3。 那么 1 << global_depth_的值就是8转换为二进制就是 1000 。mask=8-1=7，转换为二进制就是 111. mask 的作用就是取一个位数和global_depth_一样的全1的二进制数，为了取低global_depth_位做铺垫。 现在假如key的值进行完hash之后是 10110100011010 和 mask进行进行 & 的操作之后就变成了 010 （低3位） ...

CMU15-445 作为 CMU 数据库的入门课，这门课由数据库领域的大牛 Andy Pavlo 讲授（“这个世界上我只在乎两件事，一是我的老婆，二就是数据库”）。 这是一门质量极高，资源极齐全的 Database 入门课，这门课的 Faculty 和背后的 CMU Database Group 将课程对应的基础设施 (Autograder, Discord) 和课程资料 (Lectures, Notes, Homework) 完全开源，让每一个愿意学习数据库的同学都可以享受到几乎等同于 CMU 本校学生的课程体验。 亮点在于这门课程实现了一个关系型数据库的Demo–bustub，并对组成部分进行修改，最后达到完成整个数据库的目的，非常的有意思。 近年来由于CMU15-445这门课的热度大增，无论是找工作还是保研的简历上都少不了这个课程。到了可以说是人手一个的地步（还有MIT6.824），但是最后的排行榜上真正完成4个项目并且有成绩的不过100余人。在这种背景下也催生出了很多卖课的机构和个人。还有种种乱象。暂且按下不表，进入主题。 前言 先附上 课程链接我原本是想要完成最新的课程即2023fall的，但是2023fall的P0直接就把我劝退了，相较于2022fall的P0我认为难度上升了不止一点。但是其他的Project的实现差别并不是太大，所以我选择了较为容易下手的2022fall的课程进行学习。 Project0-C++ Primer 还是先放上项目Project#0-C++primer链接 概述 这是一个相当于先导课程的项目，旨在培养和检验学生的现代C++编程能力 ，BusTub大量使用C++17，当你上手之后可能就会发现和你印象中的C++不一样。 在CMU如果你没能满分通过P0，那么你会被要求退课。 所需前置知识 我认为需要的前置知识主要包括C++11的新特性 这是在2023fall课程的一个可能是助教写的一个小demo包含了几个例子能够帮助你快速的上手c++11的新特性。 熟悉字典树能够理解字典树原理能够完成一个字典树的小demoLeetCode.208实现前缀字典树 可以先把这个做了，了解一下什么是字典树。 上图就是一个字典树的简单示意图 文件结构 在文件中作为字典树的架子文件中包含了三个类。 TrieNode TrieNodeWithValue Trie Task#1 字典树 先完成一个单线程版本的字典树，后期再考虑并发。 TrieNode TrieNode定义了一个Trie树的一个节点。 一个包含关键字的char类型`key_char_。 一个bool类型is_node的标志来标记这个节点是否是值节点 包含一个存储类型为 char to unique_ptr<TrieNode>映射的哈希表 需要注意的点： C++中智能指针std::unique_ptr的特性所带来的： The InsertChildNode and GetChildNode both return a pointer to unique_ptr 这个独享类型的智能指针也不支持被复制，所以要么使用std::move()把所有权交出去，要么就用get()函数把裸指针交出去。 the move constructor TrieNode(TrieNode &&other_trie_node) is used to transfer old TrieNode’s unique pointers to a new TrieNode。因为是unique_ptr所以在传递的时候不能对指针进行复制。（解决方法就是使用move()函数）。 ...