结合了06 index locking & latching和论文A survey of B-Tree Locking Techniques
一个困扰很久的问题，闩保护的是数据结构，隔离的是线程；锁保护的是内容，隔离的是事务。在索引中，闩保护的是树的结构，举个例子：线程t1因为插入要对节点N1（存了123）进行分裂成N1（12）和N2（34），在分裂的过程中，按照原始的B+树，在生成N2但是还没有添加到父亲节点的中间状态，另一个线程t2要访问3就无从访问了——这就是闩要做的事，保护N1避免其他线程的访问直到N1分裂结束（避免分裂或合并的中间状态被其他线程看到）
索引主要有两种，有序索引（也就是树，有序存key）和哈希索引（只支持等值查询）
闩
要解决的问题：
- 当一个线程在读取缓冲池中的某个页面时，不能被另外一个线程修改。
- 当跟随指针(页面标识符)从一个页面到另一个时，例如从B-TREE索引中的一个父节点到一个子节点，
该指针必须不能被另外一个线程废止(invalidate) - 不仅父-子指针之间有"指针追踪"的问题，在相邻指针之间也存在。不同的线程可能根据升序或降序
进行索引扫描，这会引起死锁。 - 在B-TREE中执行插入操作时，一个子节点可能会因溢出而需要在父节点中进行插入。在极端情况下，
B-TREE的旧根节点会溢出，而不得不进行分拆，并使用一个新的根节点代替。从叶子节点往根节点
访问在单线程环境下不会出问题，但在多线程环境下有死锁的可能。
对于第一个问题，数据库实现了只读latch和读-写latch。
解决第二个问题的方法是使用"lock coupling"，即保留父节点的latch直到获取了子节点的latch。
如果子节点当前不在缓冲池中，因而需要相对缓慢的磁盘I/O，则在从磁盘读取子节点的过程中
应该释放父节点上的latch。这种情况下，可以通过获取缓冲池中所选页面对应的描述符结构的latch
来实现lock coupling。
另外，为了防止B-TREE在此期间的变化，该I/O应该重新遵循从根到叶子的遍历方式。这么做看起来会
比较昂贵，但是通常可以直接基于之前的搜索结果。例如，验证在将子节点页面读取到缓冲池中时
所有父页面上的LSN都没有变化。
第三个问题和第二个类似，只有两点不同。从积极的一面来说，异步read-ahead可以缓解该问题的发生。
由于B-TREE索引中的大规模read-ahead通常不能依赖于相邻指针，而必须依赖于叶子节点父节点中的指针
来预读，甚至是祖父节点。从消极的一面来说，要避免相反方向扫描的死锁，latch代码必须提供一种立即
失败模式。当在向前或向后遍历时发生了获取latch失败的情况，则必须释放所有叶子节点所对应页面的
latch。
第四个问题是最复杂的。它影响所有的更新，包括插入，删除，甚至记录的更新。
一个方法是在查找受影响的叶子节点时，将从根节点到叶子节点的遍历过程中碰到的所有节点都加上排他(exclusive) latch。这种方法显然的问题是会碰到并发上的瓶颈，尤其在根节点。
另一个方法是在从根到叶子的搜索过程中使用共享(shared) latch，当有需要的时候将共享latch升级成排他latch。
在能够允许升级并且没有死锁风险的情况下这种方法很好，但是实际上由于它可能会失败，因此在实现中不能只使用该方法。
第三个方法是在通常的共享和排他latch之外，使用"更新"("update")或"升级"("upgrade") latch。"更新" latch兼容共享latch，但是彼此之间不兼容，这导致对于多个更新来说B-TREE根节点还是一个瓶颈。
以上三个方法可以有个改进，就是当碰到一个更低层的未满节点，如果它能保证拆分操作不会传递到更高层的节点，则可以释放从根到父节点这条路径上的所有latch。另一方面，变长B-TREE记录和变长键值会使得决定需要多少空闲空间才能做出该保证变得很困难甚至不可能。有趣的是，该问题可以通过以下方法来解决：在释放父节点的latch之前，可以知道如果子节点因为该插入操作而需要拆分，则哪个键值会被添加到父节点中去。
第四个方法在为插入操作从根到叶子的遍历过程中主动拆分节点。该方法避免了第一个方法的瓶颈问题和第二个方法的升级失败问题。它的不利之处是在真正需要之前拆分，浪费了一些空间，更重要的是在变长记录和键值的情况下，可能不可能在任何情况下都能够主动拆分。
第五个方法是在初次根到叶子的搜索过程中使用共享latch，当一个节点需要拆分的时候中止该过程。然后启动一个新的过程，并且在到达需要拆分的节点时，获取一个排他latch然后拆分。该方法能够受益于之前讨论过的基于之前路径的快速搜索机制。（这也是下文中提到的Latch-Crabbing的改进）
另外还有一些Latch-free index，如Bw-Tree(下节会讲), Blink-tree
Blink-Tree的每个节点都有一个high fence key和一个右指针指向右邻居节点，如果high fence key和右指针都用了表示它的右邻居还有建立和父亲节点的指针，在查找的时候会比较查找的key和high fence key，如果search key比较大，会查找右邻居节点。 分裂节点分成两步：1创建high fence key和一个新的右邻居节点 2.把high fence key给父亲节点（建立父亲节点指向新节点的指针，去掉指向右邻居的指针）
CaS是闩的基础
Blocking OS mutex
用系统的排它锁，简单，扩展性差，每次lock/unlock都需要时间
Test-and-set SpinLock (TAS)
效率高，扩展性差，not cache friendly
会不断的test需要的object是不是空闲的，如果是就用；不是，继续test
Queue-based Spinlock (MCS)
对同一个对象的latch排成队列，按队列一个一个来就好了
读写锁
需要设立规则来防止饥饿，允许并发读，也是用的最多的
Latch Crabbing
为了提高并发（如读写都要从根节点开始，给根节点上完读锁，无论下一个operator要 写的是不是与前一个operator冲突都必须等待），提出了 Latch Crabbing/Coupling——一节点安全时可以释放起所有祖先节点的latch。
安全：对于插入，是未满；对于删除，是多于一半
改进的Latch Crabbing：对于Latch Crabbing来说仍要从根节点上上latch，然后往下找到安全节点根节点上的latch才能释放，仍然影响了并发；所以在这里考虑乐观的假设叶子节点是安全的，总是加读锁直到到需要的节点，如果的是安全的，加相应的锁；如果不安全就按原来的方法restart。
Index Locks
Lock保护的是内容，可以是不在内存中的内容，甚至可以不在数据库中的内容——所以锁不能内嵌
谓词锁
很少用了
但在快速可串行化MVCC那个论文中用到了，用在了验证阶段，事务txn1（T0开始，T1提交）提交的时候会会验证在T0到T1内提交的txn list对应的undo buffer中做出的修改是不是满足谓词，如果是abort and restart,如果不是，提交成功（比track the entire read set, and recheck，也就是记住原来读的，最后再读一遍看是不是发生了改变）。
Gap Locks, Key-Value Locks
Key-Range Locks
Key-Value Locks + Gap Locks
谓词锁的特殊形式，边界[ )必须都是已存在的key（需要定义特殊的key ∞）
删除一个key需要老key和它的邻居上锁，来保证事务回滚时还能重新插入 （？为什么）
record head里ghost bit对于插入删除都非常有用：如果插入的key是index中的ghost record，那么插入实际上就是update了，update ghost bit and content；删除也是直接update ghost bit就可以了，空间的回收可以放在后面；也可以用在key range locking中做边界。——优点：回滚不用重新分配空间（没有真删），删除的时候也只用一个key locking，不需要lock它的neighboring gaps了； 插入时也可以调高并发性，可以先插ghost record，再更新ghost record，和delete一样，只需要key lock
Hierarchical Locking
更大范围的Key-Range Locks，类似于表锁（意向锁），给一个更大范围上一个latch，可以减少上latch的量（在锁里可以减少访问锁管理器）
网友评论