5. Index Concurrency Control

5.1. concurrency（并发）

A concurrency control protocol 的正确性标准在于：

• logical correctness：线程必须能够完整正确的看到其应该看到的数据
• physical correctness：数据内部是否完整合理，比如一个数据结构指针不会指向非法的内存地址

5.2. Lock & Latches

• Lock：

  是一个高层，逻辑上的原语，其在事务之间保护数据库的内容。

  • 保护数据库中的逻辑内容

    • 逻辑内容可以是 tuple、tuple set、table、db

  • 一个 txn(transaction 的简写)会全程持有 lock

  • 在查询执行时，数据库可以将 lock 暴露给用户

  • lock 需要能够回滚变化，比如说，如果一个被 lock 锁上的 tuple 被修改了，这次修改可以回滚

• Latch(有时又叫 mutex)：

  是一个底层保护原语，在线程之间，其用来保护 DBMS 内部数据结构的关键区域(比如，数据结构，内存区域)

  • latch 只有在操作执行的时候才会持有

  • latch 并不需要能够回滚数据，因为 latch 所尝试进行的操作本质上是原子性操作

  • 存在两种 latch mode

    • READ：多个线程可以同时读，也就是线程可以持有read latch，即使是其他线程也持有read latch

• WRITE：对于write latch，当一个 thread 持有时，其他 thread 就不能持有

5.2.1. Latch 的实现

• Blocking OS Mutex

• Test-and-Set Spin Latch

• Reader-Writer Latches

CMU15445 Lecture 9 Index Concurrency Control - 抿了抿嘴丶 - 博客园 (cnblogs.com)

• 其实正式的读写线程调度取决于上下文和使用策略。不能一昧的读优先，因为这样可能造成写进程 starvation。

5.2.2. Hash Table Latching

• 区别是 latches 的粒度，后者更小。

  • 前者方便，但减少并行性：因为无法让两个线程同时操作不同的 slot
  • 后者并行性更高。付出的代价更高：因为扫描每个 slot 都要获取 latch

• 在 hash table 中，由于线程都是从上往下（同方向）扫描，因此不用考虑死锁的问题

  • 即来自另一个方向的线程在我争抢该处写锁前就将内容修改，无法保证数据一致性，即前一条线程刚修改完，但我之前刚通过读锁读了数据，修改的数据是在原来的数据上进行的，此时，如果不重新读，事务会出现问题，所以就需要做更多考虑了，如果都是从上往下的，那就无须考虑这点

5.2.3. B+ Tree Latching

• 这里的情况更复杂。比如有一条线程可能正在遍历 B+Tree，接着在它到达叶子结点之前，另一条线程对 B+Tree 进行了修改，这引起了节点间的拆分与合并。使得 B+Tree 中节点的位置可能会有所移动，我所查找的数据可能就并不在原来的位置上了，甚至在最糟糕的情况下，指针指向了内存中的一个无效内存地址，导致 segmentation fault，并且程序崩溃。

• 如何处理？

• 即 latch crabbing 或者 latch doubling
  • 一种允许多条线程在同一时间访问 B+ Tree 的技术
  • 在任何时候，当我们在一个节点中时，我们必须在该节点上挂一个 latch，不管是写模式还是读模式的 latch 都可以。
  • 接着，在我们跳到我们的孩子节点之前，我们要拿到我们孩子节点上的 latch，以及我们想要到达的下一个节点的 latch。
  • 然后，当我们落到那个孩子节点上时，我们要对它里面的内容进行测试。如果我们判断出来移到到该孩子节点是安全的话，那么，对我们来说将父节点上的 latch 释放掉是 ok 的。
    • 如何判断安全？
      • 如果我们要进行一次修改，我们所在的节点无须进行拆分或合并操作，也不用去管在它下面所发生的事情

• 例子

• A -> B：不安全，不释放 A latch
• B -> D：安全，因为 D 已满（相反，如果是 insert 操作，则 D 不满才是安全的），不管 D 下面发生了什么，都不会影响到 B 和 A，可以释放 B 和 A 的 latches
• D -> H：安全，释放 D 的 latch，删除完后，释放 H

基本上来讲，在 B+Tree 中，当线程往下进行遍历时，线程会通过一个 stack 来保存它一路上所持有的 latch

在某个时间点，当我在一个安全的节点处时，我就可以释放掉该节点之前所有节点上的 latch

• 注意：释放时：想尽量快的先释放更上层的 latch，因为这样可以尽快减小 latch 对其他线程的影响。但是由于是栈结构，所以还是 FILO

5.2.4. 乐观和悲观

• 但是这样的锁机制存在着一个问题：每个线程访问 B+树时都需要在根节点获得 write latch。但是 W latch 是独占的，会造成并发性的性能瓶颈。
• 因此会有乐观锁：
  • 乐观地假设我不会去进行任何拆分操作，向下访问 B+Tree 的时候，我所采用的是 read latch，而不是 write latch。然后，我在对叶子节点进行处理时，会使用 write latch。
  • 如果我判断出我并不需要进行拆分的话，that’s good. 如果我在进行拆分或合并操作时犯错了，那么，我直接终止操作，并在根节点处重启该操作，在向下遍历的时候获取 write latch
  • 这样可以有效避免，非拆分合并操作占用非叶子结点 W latch 造成性能瓶颈的情况：因为非拆分合并操作不会造成非叶子结点的变化

5.3. Observation

• 目前所有的遍历都是从上到下。如果有从左到右的遍历呢？

• 如果是 Write 操作，可能会存在死锁问题

• 解决方法：中断其中之一