Posts

写在前面 在这篇文章中我们先抛开SQL在bustub的中的历程，直接快进到最后开始执行的阶段，这篇文章只关注设计上的细节。 至于如何理顺这些细节在[[CMU15-445 Project3 - Query Execution]]文章中会有详细的介绍，这里就不再赘述。😃 架构总览 上图中catalog其实不是特别准确，按照我的理解应该是下面这种情况👇。通过一个table_id双向映射表的名字和实体table。 接下来就按照从上到下的顺序依次介绍各个部分的结构。 Catalog 下面这个图是是整个catalog关于table的。👇这里引出了TableInfo. Catalog中不仅仅包含table的信息还储存了index的信息。这里引出了IndexInfo,但是后边用的不是很多。 接下来看TableInfo的组成。（TableInfo的定义就在Catalog.h文件中） TableInfo name_:就是表的名字 table_: 是一个每个节点都是tablepage的双向链表 oid_: 顾名思义就是表的id Schema_：其实到现在我都没有很弄懂这个是干什么的东西，但是chat给出了答案。 什么是Schema 按照我的理解应该是一个类似于表头的包含各种配置信息的一个抽象集合。现在就看看源码。👇 在bustub中schema的信息似乎没有包含很多，就是对每一个列的数据类型约束进行了记录。以及对所有的列进行一个汇总，方便获取到每一个列。 ==Column== 实际上每个列的实现实体是Column，在这个实体中包含列名，数据类型，长度等基本信息。 ⚠️值得注意的是column对于varchar单独做了处理🙂,变长数组终究还是不一样啊。 TableHeap 实质上就是配合TablePage里面的信息构成的双向链表，我觉得这个设计真的非常的巧妙。只用了基本的pre_page_id 和next_page_id这两个变量就把双向链表给建立起来而且耦合度非常的低。 first_page_id_: 就是第一个pageid bufferpool：所有的page都需要从bufferpool中去取。 TablePage的结构 ok看到这里有疑问了？ 那么多的信息都存在那里， 这继承的加上初始化的也不够啊。 答案在这里👇 通过偏移量直接在page的剩余空间里去定义各种变量。 ==通过InsertTuple（）函数了解详细结构== 直接看源代码： if (tuple.size_ + 32 > BUSTUB_PAGE_SIZE) { // larger than one page size txn->SetState(TransactionState::ABORTED); return false; } auto cur_page = static_cast<TablePage *>(buffer_pool_manager_->FetchPage(first_page_id_)); if (cur_page == nullptr) { txn->SetState(TransactionState::ABORTED); return false; } 这主要是判断一些前置条件的合法性 为什么要用tuple的大小+32进行比较呢？ 文末给出答案 在第一页中进行插入，如果没有足够的空间就开一个新页然后插进去 ⚠️需要注意的是，在离开第一页的时候仍然要持有写锁，因为还要写next_page_id变量. 💡跟随代码跳转到TablePage::InserTuple(). ...

事务 ==Transaction== 在英文中事务用transaction表示，一般约定俗成的缩写为txn，所以在数据库的源代码中看到txn的话多半就是事务。 ==事务诞生的背景== 我们假设一个银行的场景，转账这一操作在外界看来是单一的操作，但是在数据库内部涉及到很多的操作，假如转账操作发生了失败，那么数据的不一致是不能被接受的。所以这一连串的操作可以被归为逻辑上的一个操作集。要么整体都成功要么都失败。 事务的概念 在chatgpt上问事务的概念他会这样子进行回答。 这也正是事务的关键。 我们回归课本，看课本上给出的定义 事务的隔离性级别 我个人觉得对于隔离性的的理解是非常重要的，在后续的算子的实现当中几乎都要考虑事务的隔离等级，根据不同的隔离等级去进行不同的操作。（我个人现在比较迷茫的是怎么能比较周全的考虑不同隔离等级所带来的影响。：）。看来是时候找个大佬请教一下了。🙃

Join Operation， 连表 在查询过程中经常会涉及到连表的操作。那么为什么总是需要连表呢？ ==为什么需要连表？== 在存储的时候为了避免数据的冗杂，将表进行规范化，导致表的割裂。 在查询的时候需要获取完整的信息，所以将表进行重新的组装。 连表的算法 Fetching Title#i6kq

做这个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👀，眼瞪的比黑猫警长还大。 最后附上通过截图。 ...