Posts

做这个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。主要就是在于你如何去解释它的组成部分。 ...

数值类型 整数类型 整数就是没有小数部分的数字。之前使用过的 i32 类型，表示有符号的 32 位整数（ i 是英文单词 integer 的首字母，与之相反的是 u，代表无符号 unsigned 类型）。下表显示了 Rust 中的内置的整数类型： 整型溢出 在使用编程的过程中难免会发生数的范围超过了类型范围这时候就会发生溢出的现象。 有趣的是：在debug模式下编译器会检测有没有发生整形溢出的现象，如果有发生整数溢出的现象编译就会发生panic. 但是在release模式下，编译器不会进行整数溢出的的检测。当发生整数溢出的时候会按照补码循环溢出进行处理。简单来讲就是取余。 要显式的处理可能的溢出，可以使用标准库提供的类型。 使用warpping_*的方法在所有模式下都按照补码循环溢出的规则进行处理 使用check_*方法发生溢出的时候返回None值。 使用overflowing_*方法返回该值和是否溢出的一个bool值 使用saturating_*的方法返回最大值或者最小值 下面是一个演示warpping_*的一个示例代码 fn main() { let a : u8 = 255; let b = a.wrapping_add(20); println!("{}", b); // 19 } 最后这个输出结果也没有出乎意料。 浮点类型 浮点类型是带有小数点的数字。在Rust中浮点数类型也有两种表示f32,f64. 分别表示32位和64位。在现代CPU中32位的运算速度几乎和64位是一样的。所以默认是f64. 浮点数陷阱 浮点数在其底层表示上有很大的特殊性，这就导致了如果在使用的时候不够谨慎就会造成危险。主要有以下两个原因。 浮点数是一种近似的表达。由于所有的生活中的数字我们都是用十进制进行标识但是计算机用二进制在底层进行表示，所以我们很难非常准确的表示十进制的小数。 浮点数在某一些事情上是反直觉的。例如很多人都觉得浮点数是可以进行比较的对吧。但是实际上如果我们编写如下的代码会发生什么呢？ fn main(){ assert!(0.1+0.2==0.3); } 程序将会panic，因为二进制精度 的问题，0.1+0.2将会在N位之后与0.3发生偏差。 为了避免掉入陷阱当中，我们需要注意以下两点。 避免在浮点数上测试相等性 当结果在数学上存在未定义的时候我们需要格外的小心 但是如果非要进行比较呢？ 可以考虑用这种方式 (0.1_f64 + 0.2 - 0.3).abs() < 0.00001 ，具体小于多少，取决于你对精度的需求。 ...

一些关于为什么要学rust的想法 其实在大一的时候我就有了解过rust语言，当时甚至还看了一周b站的视频，在我最近准备再看rust的时候发现我大一装的环境还在，我甚至自己都不记得有这件事了。 rust语言据说有非常好的内存管理机制和安全措施，以及极高的执行效率，所以近些年被用作开发底层非常的多，而我对这方面也是非常的感兴趣，也算是兴趣驱动吧。希望能有助于提高一下自己的编程能力，让自己也多了解一下rust语言。