Latch

	Locks	Latches
Separate	User transactions	Threads
Protect	Database contents	In-memory Data Structures
During	Entire Transactions	Critical Sections
Modes	Shared, Exclusive, Update, Intention	Read, Write
DeadLock	Detection & Resolution	Avoidance
… by …	Waits-for, Timeout, Aborts	Coding Discipline
kept in …	Lock Manager	Protected Data Structure

Latch Implementation

Approach #1: Blocking OS Mutex

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

Approach #2: Test-and-Set Spin Latch(TAS)

std::atomic_flag latch;
...
while(latch.test_and_set(...)){
  //Retry?Yield?Abort
}

Approach #3: Read-Writer Latch

正常的读写锁逻辑

Hashing table latching

不会发生死锁，因为扫描顺序都是从hash table的头到尾。

Approach #1: Page Latches

在每一个page上，使用一个read/write latch。

Approach #2: Slot Latches

使用粒度更小的latch，即你可以在每个slot上使用latch。

B+ Tree Concurrency Control

Two problems needs to be protected：

多个线程尝试去同时修改一个节点中的内容
一个线程在遍历树的时候，另一个线程在分割/合并节点

Approach #1: Latch Crabbing/Coupling

这种技术允许多条线程在同一时间访问B+ tree。

safe node是指当插入时不是满的，当删除时节点中的key数大于容量的一半。

Find操作：从根节点开始往下走，需要子节点上的read latch，之后解开父节点的锁。
Insert/Delete操作：从根节点开始往下走，使节点获得write latch，一旦子节点被锁上了，检查它是否安全，如果安全就解开所有祖宗节点的latch。（尽可能先释放更靠近root的节点）

Approach #2: Better Latching Algorithm

由于之前的方法并发操作效率很低，我们使用一个优化的方法来实现线程同步。我们假设叶子节点是安全的，DBMS使用read latch去接近叶子节点（去除父节点的latch和latch crabbing中find case的操作一致），并且验证它是否是安全的。如果叶子节点不是安全的，那我们使用上面的latch crabbing方法（用的是write latch）。在现实的数据库系统中，需要做拆分和合并的概率很小。

Leaf Node Scan

叶节点扫描需要去考虑死锁的问题。

case 1: 读遇上读

两个叶子节点交换锁。

case 2: 读遇上写

读线程restart，这样可以避免死锁，不过这可能会导致饥饿。

Delayed Parent Updates

当一个节点溢出的时候，我们必须更新至少三个节点：

该叶节点必须被拆分
要创建一个新的叶节点
修改父节点使其容纳新的key

延迟更新父节点是一种对于这种情况的优化技术。当插入新的值时，只会更新子节点而不更新父节点，但是会在一个全局变量中表明父节点需要更改的内容，当下一次获取到该父节点的write latch时再更新该父节点。（这样方便还有个原因是因为一开始更新操作之前的节点使用的都是read latch）