CMU-15445-Index Concurrency Control

Concurrency Control

A concurrency control protocol is the method that the DBMS uses to ensure “correct” results for concurrent operations on a shared object.

分别有Logical Correctness与Physical Correctness.

本文主要侧重于Physical Correctness

Latches

Locks(Transactions)

• 保护数据库的逻辑内容（从其他的事务中）
• 在事务的持续时间内持有
• 能够rollback
• higher-level

Latches(Workers)

• 保护DBMS内部数据结构（从其他的工人中）（例如thread）
• 在操作持续时间内持有
• 不需要rollback
• low-level

Latch Modes

Read Mode

• 不同的线程可以同时读取相同的对象
• 一个线程可以获取读latch如果另一个线程在读模式也有它

Write Mode

• 只有一个线程可以访问对象
• 一个线程不能获取写latch如果另一个线程在任何模式也有它

Latch Implementation goals

• 内存占用小
• 快速的执行路径当没有线程竞争latch的时候
• 当等待时间过长时取消对thread的调度
• 每一个latch没必要执行他们自己的队列去记录等待中的thread

latch Implementation

Test and Set Spin Latch

• 非常高效(在数据库中十分低效)
• 不可扩展、不支持缓存、不支持OS
• Example：std::atomic<T>

Blocking OS Mutex

• 使用很简单
• 不可扩展
• It appears as a single latch to the DBMS even though it contains two internal latches. If the DBMS fails to acquire the user-space latch, then it goes down into the kernel and tries to acquire a more expensive mutex. If the DBMS fails to acquire this second mutex, then the thread notifies the OS that it is blocked on the mutex and then it is de-scheduled.
• Example：std::mutex->pthread_mutex->futex(fast user-space mutex by Linux)
• OS mutex is generally a bad idea inside of DBMSs as it is managed by OS and has large overhead

Reader-Writer Latches

• 允许并发读取。必须管理读/写队列来避免starvation，比spin Latches有更大的存储开销因为额外的元数据
• 可以在spinlocks的顶层实现
• Example：std::shared_mutex->pthread_rwlock

Hash Table Latching

很方便去支持并发访问

• 所有的线程在同一个方向移动且一次只访问一个page/slot
• 死锁是不可能的

为了重新调整table的大小，在整个表上执行一个global write latch

Page Latches

• 每一个page都有它自己的reader-writer latch保护它全部的内容
• 线程在他们访问一个page前需要获取read或者write latch
• 虽然只能由一个latch去访问一个page，但是访问page里面的multiple slots很快

Slot Latches

• 每一个slot有它自己的latch
• 两个线程可以在同一个Page里访问不同的slots
• 可以用一个单模式latch去降低元数据与系统开销

B+Tree Concurrency Control

我们想允许多线程去访问与更新一个B+树在同一时刻

我们需要预防以下两种问题：

• 多线程尝试修改一个节点的内容在同一时刻
• 一个线程正在遍历树当另一个正在分解/融合节点

Latch Crabbing/Coupling

允许多线程在同一时间访问/修改树的协议如下

• get latch for parent
• get latch for child
• release latch for parent if “safe”

safe的节点是不会分解或者融合的节点（当更新的时候）

• Not full（在插入的时候）
• More than half-full（在删除的时候）

Find

• 获取R latch on child
• unlatch parent
• 重复直到我们找到叶子节点

Insert/Delete

一步一步遍历

• 一旦child被latched，检查是否safe。如果安全，释放所有latches在ancestors上

Better Latching Algorithm

Search

和之前的一样

Insert/Delete

• set latches as if for search，到叶子，然后set W latch在叶子上
• 如果叶子不安全，释放所有的latches，然后用先前的策略和写latches重新启动线程

这种方法在只有叶子节点被修改的情况下十分高效。

Leaf Node Scans

This means that a thread can only acquire a latch from a node that is below its current node. If the desired latch is unavailable, the thread must wait until it becomes available. Given this, there can never be deadlocks.

the only way programmers can deal with this problem is through coding discipline.

个人想法是可以想一个启发式算法，通过工作量来衡量wait的时间。时间一过就只好kill ourselves。