CMU15-445-Project #2 - B+ Tree Index Checkpoint 2

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的吉祥物也是个螃蟹吧。。

螃蟹锁

因为其加锁和解锁的过程以及逻辑特别像螃蟹的行走的方式，因此而得名螃蟹锁。

读模式

在读模式的时候最为形象，当获取到父节点的读锁之后，尝试着获取目标子节点的读锁，当获取到锁之后立马释放父节点的锁
image.png|600
在上图中，一个线程获取A页的锁之后会尝试着获取目标子节点B的锁，当获取B的锁之后就会释放A的锁。如此循环往复，就像螃蟹在走。

写模式

写模式的时候只是锁释放的条件不一样，读模式的时候当获取的下一个页的锁的时候就可以立马释放当前页的锁，但是写模式涉及到插入和删除，可能整个路径上的页都会受影响。
image.png|600
如上图所示，当获取到B页的锁的时候不能释放A页的锁，因为B有可能会发生合并，于是继续向下获取锁，获取到C页的锁之后发现C页是处于安全状态的。所以可以释放C页之上的所有锁。⚠️注意：并不包括C本身。

安全状态

安全状态的这个概念只存在于写模式的时候。需要注意的是：在删除和插入的时候页处于安全状态的条件并不一样。

image.png|600

在插入的时候：该页不是满的-----》就算发生分裂的情况，到此页也就结束了。
在删除的时候：大于半数---------》就算删除之后发生合并或者重新分配到此页就结束了。

螃蟹锁的优势在哪里？

⚠️这里的优势是相较于一把大锁而言。

虽然B+树可以做的很高很大，但是无论如何都只有一个入口。如果每次都是一把大锁，那不管什么操作都会先获取根节点并且锁住，那直接就编程单线程的了。

所以整个的瓶颈就是根节点上锁的时间太长了。影响了并发。所以螃蟹锁的优势就在于：

能够显著的减少根结点上锁的时间，让更多的线程进入B+树进行操作

更优的螃蟹锁执行策略

当前释放的策略仍然拥有很大的优化空间。在原来的策略上写模式的时候会对根节点上写锁，知道找到一个安全节点之后才会释放，这就占用了很长时间，导致效率降低。这种不分青红皂白的直接给各个节点上写锁的行为称之为悲观锁。顾名思义，悲观锁表示这种策略对多线程的执行非常的悲观，觉得每个页都会被修改，必须都上锁才安心。但是事实上在实际的应用过程中触发分裂或者合并并不是很频繁。

所以就诞生了一种更优的加锁策略乐观锁，在写模式的时候就大胆的假设从根节点到最后的叶子节点都是安全的，给路径的页都上读锁，最后的叶子节点才上写锁。如果在这个过程中发现了某个节点跟假设的不一样，不是安全的，那么之前的所有锁都释放，再重新按照悲观锁的方式进行操作。

这样做的好处是，在相较于悲观锁乐观锁在一定程度上能改善根节点总是上写锁导致并发时读取效率的降低。

但是我本人还没有实现乐观锁，修改FindLeafPage()或者添加FindLeafPageHelper()应该都是可以的。