索引并发控制

1.简介¶

在数据库中的锁分为两类：

CAS是一个原子操作，用于将旧值与指针对应的值进行对比，若相同则将指针的值替换成新值。

function cas(p: pointer to int, old: int, new: int) is
    if *p ≠ old
        return false

    *p ← new

    return true

CAS的原子性是由硬件提供的，Intel对LOCK原语的说明如下：

确保对内存的读-改-写操作原子执行。在Pentium及Pentium之前的处理器中，带有lock前缀的指令在执行期间会锁住总线，使得其他处理器暂时无法通过总线访问内存。很显然，这会带来昂贵的开销。从Pentium 4，Intel Xeon及P6处理器开始，intel在原有总线锁的基础上做了一个很有意义的优化：如果要访问的内存区域（area of memory）在lock前缀指令执行期间已经在处理器内部的缓存中被锁定（即包含该内存区域的缓存行当前处于独占或以修改状态），并且该内存区域被完全包含在单个缓存行（cache line）中，那么处理器将直接执行该指令。由于在指令执行期间该缓存行会一直被锁定，其它处理器无法读/写该指令要访问的内存区域，因此能保证指令执行的原子性。这个操作过程叫做缓存锁定（cache locking），缓存锁定将大大降低lock前缀指令的执行开销，但是当多处理器之间的竞争程度很高或者指令访问的内存地址未对齐时，仍然会锁住总线。
禁止该指令与之前和之后的读和写指令重排序。
把写缓冲区中的所有数据刷新到内存中。

上面的第1点保证了CAS操作是一个原子操作，第2点和第3点所具有的内存屏障效果，保证了CAS同时具有volatile读和volatile写的内存语义。

由于CAS需要同步缓存，因此频繁的利用CAS进行自旋是cache unfriendly的，CPU的开销较大。

TAS是一个原子操作，将内存的值设置为1，并返回旧值。 TAS常用于自旋锁(spin lock)，伪代码如下

lock = 0 //shared state
while(test_and_set(lock)==0){ //try lock
       //do nothing   
}
// 臨界區代碼
lock = 0   //release

TAS底层还是使用CAS操作实现的，不断的设置锁标志位的过程会一直修改共享变量的值（写回），会引发缓冲一致性流量发风暴，是cache unfriendly的。

Mutex是互斥锁的一种，当线程尝试获取锁但获取不到时就会被阻塞，直到得到锁。

Mutex的底层使用的是Futex(fast userspace mutex)，其实就是用户空间中的一个数据结构。

最开始的时候线程会尝试使用CAS进行锁的获取，若获取失败则会使用内核层面的Mutex。此时，线程会被放进等待队列中，并由调度器调度。

Mutex的缺点是由于需要内核进行调度，因此开销较大。

读写锁是粒度更小的互斥锁，可以更好的支持并发。

本质是为读锁和写锁都维护一个队列，用于调度获取读写锁的线程。

其中读锁是可以被共享的，因为多个线程同时读一个数据是安全的，但写锁和读锁之间需要做到隔离。

哈希表的并发控制是十分简单的，所有线程获取数据的方向都是一致的，因此不会引发死锁。

当需要对整个表进行操作如Resize时，只需要加上一个Table级的Latch即可。

唯一需要考虑的是读写数据时锁的粒度：

B+树需要考虑的问题在于Merge和Redistribute这两种操作，这会一路影响到到向上递归的最后一个会发生Merge或Redistribute的父节点。

主要有两种思路：

悲观锁（latch crabbing）：每个节点都拥有一个latch，向下递归并获取子节点的锁后（此时已经有了自身所在节点的latch），会观察子节点的状况是否安全。安全指的是子节点不处于半满或全满的状态，则此时子节点如果发生了变化也不会影响父节点，因此释放父节点的锁；否则直到找到一个安全的子节点为止，一直持有一条链路的锁。
乐观锁：一个节点处于半满和全满的状况是非常少的，因此假设节点不会发生Merge和Redistribute，最后再做校验。实现方式是读写锁，对于读操作来说需要获取读锁；对于写操作来说，一开始Inner Node仍然获取读锁，只在Leaf Node获取写锁。如果判断对于该写操作会导致叶节点发生Merge或Redistribute操作，则放弃本次操作并从根节点开始使用latch crabbing算法。

对于叶节点的顺序扫描来说，主要需要考虑死锁问题。

一种常见的手段是若无法获取锁则直接放弃本次的操作并重来，但最好的方式是使所有线程沿着一个方向进行扫描。