高级数据库七：索引的锁和闩

约定不等于承诺〃 2022-06-05 12:26 150阅读 0赞

# 索引的锁和闩(Locking & Latching) #

## 索引的锁和闩 ##

### 索引作用 ###

一种能够加快数据检索速度的数据结构，但是会占用额外的读写维护操作和存储空间。

### 索引实现 ###

B树系列、哈希表等等。

这些别的地方说的比较多，我就不多提了。

### 索引锁 ###

对于之前疏文章中提到的那些并发控制、多版本控制等，我们知道了如何使用锁来保护数据库的数据。但是对于索引，我们需要用别的方式和方法来对待它。

尽管索引的物理结构会发生改变，但是只要索引在逻辑层次上保持一致，就能够被使用者和开发者所接受。

举个简单的例子，我们读取数据的时候，并不关心它存储的位置或者索引指向的位置是哪里，我们只需要能够读取到正确的数据即可，就算因为插入了多个其他的数据，导致索引结构的改变，我们还是可以得到正确的数据。

### 锁和闩 ###

锁

*  高层次，抽象
 *  保护索引的逻辑内容不受其他txns的影响，从逻辑层面保护索引。
 *  以txn为单位被保持。
 *  需要能够回滚更改。

插销

*  低层次，具体
 *  保护索引内部数据结构的关键部分不受其他线程影响，从物理层面保护索引。
 *  以operation为单位被保持。
 *  不需要能够回滚更改（或者说是不能通过回滚修改，因为底层不知道操作了啥，底层只知道有操作，知道操作的具体内容是高层的事情）。

![图1][1]

在没有锁的情况下，事务就不通过锁去访问修改数据库，而是直接通过latches进行并发控制。  
在没有闩的情况下，我们可以使用类似shadow paging等技术使得指针可以对数据进行原子操作，比如compare\_and\_swap（用于对特定内存地址进行值确认，如果确认成功则用新值覆盖，否则不做操作），但是我们也要通过locks来进行事务的并发控制。

因此没有一个数据库可以同时缺少这两种锁。

## 闩的实现 ##

### Blocking OS Mutex ###

简单易懂；  
不可扩展，速度慢，每次分配和取消锁需要大概25纳秒。

每次mutex分配锁和取消锁都不能直接操作，而是需要调用操作系统的内核函数，这就导致非常缓慢了。每次没有获得锁，则可以直接通过内核函数表明，该线程需要锁，则有schedule的内核函数会在锁空闲的时候再次请求锁。

std::mutex m; //pthread_mutex_t  futex
    ⋮
    m.lock();
    // Do something special... m.unlock();

### Test-and-Set Spinlock ###

快速，单个指令实现加锁减锁；  
不可扩展；  
对缓存不友好，假设我们有三个CPU，我们需要一直去访问一块内存地址，并将内存地址放到CPU内部的缓存中，但是因为我们每次都要请求可能变化的新值，所以我们不可能将之存储下来继续用。

typedef std::atomic<bool> atomic_flag //std::atomic<T>
    std::atomic_flag latch;
    ⋮
    while (latch.test_and_set(…)) { // 请求锁，如果没有得到，则循环；得到结束循环
    // 让位? 放弃? 重试?
    // 因为在上一种方法，我们通过内核函数进行规划，所以它会自动请求锁
    // 而这里则需要我们自己去考虑如何去做
    }

### Queue-based Spinlock(Mellor-Crummey and Scott) ###

比Mutex更快，更好的缓存系统。

对于CPU1，访问最基础的latch，占有并锁，基础Lacth指向新产生的CPU1 Latch

![图2][2]

对于CPU2，访问最基础的latch，发现已经被占有了，就产生了类似上面的步骤

![图3][3]

依次占有

![图4][4]

### Reader-Writer Locks ###

这种方式不能说比上一种方式好。

允许并发读  
需要管理读/写队列以避免饥饿  
可以在自旋锁之上实现

一个latch中包含两种锁，一把读锁，一把写锁，并且有四个计数器，表示有多少线程在占用读/写锁，有多少线程在等待读/写锁。

![图5][5]

两个线程先占有了读锁，则直接分配读取权限；再来了一个线程请求写锁，则因为读锁已经被分配所以只能等到写锁。

![图6][6]

若再来一个请求读锁的线程，则因为有线程在等待写锁，所以只能等待读锁。

![图7][7]

具体的实现和设计与实现者需要这种latch的目的有关，可能会有更加细微的差别。而且这四种锁也并不是包含了所有的锁。

## Latch Crabbing ##

在B+树上，如果一个子节点被认为是安全的，线程可以释放父节点上的latch  
安全的指的是：更新时不会拆分或合并的任何节点。

1.  未满（插入时）
2.  超过半满（删除时）

### 操作 ###

查找：自上而下，从根开始重复如下操作

1.  获得子节点的读锁
2.  如果子节点是安全的，则释放父亲结点的锁

插入/删除：从根开始，然后向下，根据需要获得写锁。

1.  一旦孩子被锁定，检查是否安全：
2.  如果孩子是安全的，释放祖先的所有锁

具体的图示在参考文献里的PPT中有写。

## 索引锁 ##

需要一种方法来保护索引的逻辑内容免受其他TXT的影响，以避免幻读。

与索引闩的差异：

1.  锁在整个txn持续时间。
2.  只在叶节点分配。
3.  没有在索引数据结构中进行物理层面的存储。

## 锁的实现 ##

### Predicate Locks ###

这种锁的设计非常简单易懂，但是没有人实现了这种锁

*  SELECT查询的WHERE子句中的关键词的共享锁。
 *  在任何UPDATE，INSERT或DELETE查询的WHERE子句中对关键词进行独占锁定。

![图8][8]

在查询语句中，我们发现了关键词`name = "Biggie"`，则我们对该表中所有`name = "Biggie"`的数据加了一把锁。

在插入语句中，我们发现了关键词`name = "Biggie" and balance = 100`，并且和上一个关键词有重复的部分，所以这个锁就是上一个锁的子集，并且不能在上一个锁结束前使用。

### Key-Value Locks ###

只能锁单个键值的锁。  
需要“虚拟键”来表示不存在的值。

![图9][9]

如，14到16之间没有值，则需要用虚拟的值来填充；但是有可能值的差距特别大，则需要非常多的空间去存储这些虚拟的值。

### Gap Locks ###

解决了上一种锁需要虚拟键来填充的问题。

每个txn获取要访问的单个键上的键值锁定。 然后在它与下一个键的间隙上获得一个间隙锁定。

这种间隙是开区间。

![图10][10]

### Key-Range Locks ###

将上面两种锁合起来就成了这种锁。

锁定键空间范围的锁。

*  每个范围是从关系中出现的一个键到出现的下一个键。
 *  定义锁定模式，以便冲突表将捕获可用操作。

![图11][11]

### Hierarchical Locking ###

允许txn使用不同的锁定模式来保持更宽的键范围锁定，从而减少锁管理器的访问次数。

![图12][12]

## 参考文献 ##

*  [Lecture \#06 – Index Locking & Latching][Lecture _06 _ Index Locking _ Latching]

[1]: https://drive.google.com/uc?export=view&id=1wSt-1huqWH9Y2E6_C1lFy8aiDQGQ0FqR
[2]: https://drive.google.com/uc?export=view&id=1OL7cH2Sj7F1Cl-FfANtY-HH1jti2dMEB
[3]: https://drive.google.com/uc?export=view&id=1VYsE2iGQhzZtp-l5UvLfFCWux9kCKdjl
[4]: https://drive.google.com/uc?export=view&id=1gBaOFSj-_imvZ48vvtZwn1K_0u98jM_v
[5]: https://drive.google.com/uc?export=view&id=10XJvcIROTcgfo1yxguQwfjEoirqjztoO
[6]: https://drive.google.com/uc?export=view&id=1V4Umdz3fPUKgv0B-F6Uj3ro-1lzDqFTA
[7]: https://drive.google.com/uc?export=view&id=1ATk0NeBAOiVs6ndUFyydgZPMnAGCwF9c
[8]: https://drive.google.com/uc?export=view&id=14rQU6rHkmxLf7UvIzsqkMu4t7U-2tST1
[9]: https://drive.google.com/uc?export=view&id=1p8DmfJaPFDQ4ln9A9uuQpcoHMBbWDHkN
[10]: https://drive.google.com/uc?export=view&id=1H3rSxPcrA5B8NhwrTuHJtPq7xRqPAXfb
[11]: https://drive.google.com/uc?export=view&id=1ONIufurlZSe9iTDuVD_e-ZA6g39ttOgi
[12]: https://drive.google.com/uc?export=view&id=1_cYd288A-D0wKXSA0_QkLlXU5rN3bajP
[Lecture _06 _ Index Locking _ Latching]: http://15721.courses.cs.cmu.edu/spring2017/slides/06-latching.pdf