> For the complete documentation index, see [llms.txt](https://wandersofb.gitbook.io/blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wandersofb.gitbook.io/blog/cmu15445/note/index-concurrency-control.md).

# Index Concurrency Control

此节考虑多线程情况下的锁的使用。

### Locks vs. Latches

二者都是锁的概念

|          | 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  |

简单来说，Latches 是针对下层的线程的概念用于保护数据结构，它有读写之分，分别用于不同的临界情况。而 Lockes 是对于上层的事务的概念用于保护数据内容，针对事务的分享、更新等。

### Latch Modes

* Read Mode
  1. Multiple threads can read the same object at the same time.
  2. A thread can acquire the read latch if another thread has it in read mode.
* Write Mode
  1. Only one thread can access the object.
  2. A thread cannot acquire a write latch if another thread has it in any mode.

关于读写锁就不多说了。

### Latch Implementations

我们自己来实现一下读写锁。

#### Blocking OS Mutex

说的就是 `std::mutex`，但其实用 OS 提供的锁并不好，它是会启用 OS 的线程调度，那样就太昂贵了且不可扩展。所以基本不会用。

#### Test-and-Set Spin Latch (TAS)

自己实现 spin latches 是一个更好的替代品相较于 OS mutex。简单来说就是第一个进入 spin 的线程通过，其他进入 spin 的都会陷入 while 循环中或者交给 OS 重新调度。但是这样不可扩展，对 cache 不友好，

#### Reader-Writer Latches

* Allows for concurrent readers
* Must manage read/write queues to avoid starvation
* Can be implemented on top of spin latches

### Hash Table Latching

给 hash table 上锁很简单，因为 hash table 都是单向的，直接上锁，到下一个的时候，解除上一个即可。 不过上锁有两种方式。

* Approach #1: Page Latches
  1. Each page has its own reader-writer latch that protects its entire contents.
  2. Threads acquire either a read or write latch before they access a page.
* Approach #2: Slot Latches
  1. Each slot has its own latch.
  2. Can use a single-mode latch to reduce meta-data and computational overhead.

当然也可能实现 lock-free 代码，这就不细说了，太难了。

### B+ Tree Concurrency Control

重头戏来了，我们希望有多个线程能够在 B+ Tree 上在同一时间读取和更新数据。有两个难点。

* 多个线程在同一时间修改 node 的内容。
* 一个线程遍历 tree 同时另一个线程 split/merge node。

#### Latch Crabbing/Coupling

**Basic Idea**:

* Get latch for parent
* Get latch for child
* Release latch for parent if “safe”

A **safe node** is one that will not split or merge when updated.

* Not full (on insertion)
* More than half-full (on deletion)

两种操作： **Find**: Start at root and go down; repeatedly,

* Acquire R latch on child
* Then unlatch parent

**Insert/Delete**: Start at root and go down, obtaining W latches as needed. Once child is latched, check if it is safe:

* If child is safe, release all latches on ancestors

#### Better Latching Algorithm

**Search**: Same as before. **Insert/Delete**:

* Set latches as if for search, get to leaf, and set W latch on leaf.
* If leaf is not safe, release all latches, and restart thread using previous insert/delete protocol with write latches.

乐观锁其实相较于朴素锁，就是假设 split/merge 的操作并不多，每次我都优先获取 read 锁，当到达 leaf node 看是否 split/merge，如果不，则获取写锁，更新，如果是，则重新来一遍朴素锁的过程。

#### Leaf Node Scans

通常做范围查询时，会在 leaf node 进行横向扫描，这个时候如果出现两个不同方向的 scan 时，就会 deadlock。解决办法是如果一个锁要等等待时，就不等待直接 abort，重现操作。