并发b+树协议.

• 协议介绍:

    下降方法 {
        获取根节点并锁住根节点(读锁)     
        while (true) {
            if (此节点是叶子节点) {
                if (插入方法调用) {
                    //这里为什么不用锁升级而要这么做,后面会解释.
                    解锁此节点(读锁)
                    此节点加锁(写锁)
                    更新此节点的内容.
                }
                返回此节点(此时此节点加锁,读调用加读锁,插入调用加写锁)
            }           
            int rightPos;
            while (需要右移) {
                获取右节点位置
                此节点解锁(读锁)
                获取右节点并加锁(读锁)
                此节点等于右节点
            }
            
            获取下降位置
            此节点解锁
            获取下一层节点并加锁
        }
    }

   读方法 {
        调用下降方法,获取叶子节点(已加读锁)
        while (true) {
            if (需要右移) {
                获取右节点位置
                此节点解锁(读锁)
                获取右节点并加锁(读锁)
                此节点等于右节点
                continue;
            }
            
            检索叶子节点,查找是否有符合的key.
            解锁此节点.
            返回value;
        }
    }

    插入方法 {
        调用下降方法,获取叶子节点(已加写锁)
        
        while (需要右移) {
            获取右节点位置
            此节点解锁(写锁)
            获取右节点并加锁(写锁)
            此节点等于右节点
        }
        
        if (节点满) {
            调用分裂方法
        } else {
            插入key和value在此节点中.
            此节点解锁(写锁).
        }
    }

    分裂方法 {
        while (此节点满) {
            if (此节点为根节点) {
                创建一个新的根节点(不用加锁)
                分裂当前节点产生一个新节点(不用加锁)
                key等于新节点的最小键值,value等于新节点的位置.
            } else {
                分裂当前节点产生一个新节点,且把key和value插入相应节点(不用加锁)
                key等于新节点的最小键值,value等于新节点的位置.
                获取父节点并加锁(写锁,且需要右移,右移与插入方法中的写法一致)
            }
            
            解锁当前节点(写锁)
            当前节点等于父节点
        }
        把key和value插入当前节点
        解锁当前节点(写锁)
    }

• 协议证明:

  • 不会死锁

    • 死锁的必要条件

      • 互斥：每个资源要么已经分配给了一个进程，要么就是可用的。
      • 占有和等待：已经得到了某个资源的进程可以再请求新的资源。
      • 不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显示地释放。
      • 环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

    • 从下降方法可以看到,下降方法在获取下一个节点的锁的时候会先释放当前节点的锁,也就是说不满足死锁的必要条件的第二条,所以下降方法不会发生死锁.
      这里解释一下下降方法里为什么不用锁升级,因为可能会有两个线程插入数据同时下降到同一个叶子节点,这时两个线程都锁升级就会发生死锁.

    • 在需要右移的时候也是先放弃当前节点的锁,再获取右节点的锁,所以右移也不会发生死锁.

    • 在分裂方法里会同时持有两个锁,但是其加锁顺序是获得当前节点的锁,再请求父节点的锁,所以不会构成环路,不满足死锁的必要条件的第四条,所以分裂方法也不会死锁.

    • 综上,该协议不会发生死锁,不需要进行死锁检验.

  • 在并发读写时保证一致性.

    • 首先考虑插入时叶子节点未满.
      此时通过下降函数和右移找到那个叶子节点,此时那个叶子节点被加写锁,叶子节点插入完成后,才解除写锁.
      此时有其他线程要读到这个叶子节点必须等待解除写锁,所以其他线程看到的叶子节点是完整的.

    • 再考虑插入时叶子节点满

      • 不考虑中途断电
        此时调用分裂函数,获得该节点的写锁,再生成另一个新节点,把该节点的一般数据分给新节点,写入磁盘.再把该节点写入磁盘,然后获得父节点的写锁,把新节点的位置写入父节点.这样递归上去,直至节点不满.可以发现,在获取节点的锁的时候,整个b+树会处在一致的状态.

      • 中途断电
        如果在把新节点写入磁盘后断电,这时原节点还没有更新到磁盘,所以处于一致状态.
        如果在把原节点写入磁盘后断电,这时因为父节点未写入新节点的位置.但是因为原节点的右指针指向新节点,所以新节点可以被访问到,所以处于一致的状态.

在这里提一下,我实现这个b+树的时候,b+树的节点储存在一个有日志的存储模块,节点写入前会记录在日志,重新启动时会重写日志的内容,所以每个节点要么完全写入了磁盘,要么完全没写入磁盘,
也就是说这个协议不用关注节点本身结构是否会被破坏,只关注节点之间的关系是否会影响b+树的一致性.