《ARIES/lM: An Efficient and High Concurrency index Management Method Using Write-Ahead Logging》是IBM发表的ARIES系列论文中的一篇，文章提出了一种针对B+树索引的并发控制和故障恢复算法，该算法以ARIES为基础，本文将介绍该算法中并发控制相关的内容，下一篇文章将介绍其中故障恢复相关内容并进行整体的分析，囿于个人水平，如有错误，敬请指正。

基本概念

索引数据结构

文章针对的索引按照B+树的方式进行组织，索引树提供单点检索(fetch)，范围检索(fetch next)，插入(insert)和删除(delete) 4项基本操作，同时索引更新可能导致树结构变更操作即SMOs(structure modification operations)。

索引并发控制和故障恢复面临的问题

索引的并发控制和故障恢复主要面临以下问题：

1. 如何最小化并发更新索引的影响，提高并发效率
2. 如何处理死锁问题
3. 如何支持不同粒度的锁，锁对象该如何选取
4. 如何解决phantom problem
5. 唯一索引被删除后，如何确保该事务提交前该索引不被其他事务添加
6. 如何让SMO和其他操作正确且高效地并行
7. 如何记录索引变更日志使得故障恢复更加高效
8. 当SMO操作部分成功时，故障恢复如何进行
9. 如何保证SMO成功后，即使进行SMO的事务回滚，SMO不会回滚
10. 事务回滚时如何检测SMO操作导致的数据移动，以保证回滚正确进行

ARIES/IM 能够很好的应对以上问题

并发控制逻辑

Lock逻辑

ARIES/IM 中主要使用data-only lock 逻辑，不同操作下的Lock操作如下表

表1 Lock逻辑

使用data-only lock，索引管理器在insert/delete时不需要对current key进行显式加锁，而由数据记录管理器对相应数据记录加的X lock。而在fetch/fetch next操作时，索引管理器对current key加S lock，数据记录管理器则不需要再对相应数据记录进行加S lock。因此相比于index-specific lock， data-only lock的锁开销和维护成本更小。该锁逻辑的执行以及作用会在后文相应位置说明。

Latch 逻辑

ARIES/IM 使用index page latch保证数据的物理一致性， 在遍历索引树时使用latch coupling逻辑，其加锁主要步骤为：

1. Step 1: 对索引树根节点加S latch, 令当前节点等于root
2. Step 2: 进行检索操作，确定目标子节点，并将当前节点设置为目标子节点，检测当前节点，若
3. （1）当前节点为叶节点且操作为fetch/fetch next，对当前节点加S latch；
4. （2）当前节点为页节点且操作为insert/delete，对当前节点加X latch；
5. （3）当前节点为非页节点，对当前节点加S latch，释放父节点的S latch, 重复Step 2

该逻辑保证任意时刻，一次索引树遍历最多只对两个节点持有锁（latch），同时加锁严格有序，可以避免死锁发生。SMO时的附加逻辑在后文介绍。

SMO

在ARIES/IM 中，SMO前必须先获取索引树的X latch，因此SMO操作是严格串行化的。 此外为了控制SMO和其他操作的并发，ARIES/IM 为每个节点引入了SM_BIT标志，SM_BIT为1时表明SMO 操作正在进行。因此索引树遍历的逻辑拓展为：

1. S latch root and note root’s page_LSN
2. Child := Root
3. Parent := NIL
4. Descend:
5. IF child is a leaf AND Op is (insert OR delete)
6. THEN
7. X latch child
8. ELSE
9. S latch child
10. Note child’s page LSN
11. IF child is a nonleaf page THEN
12. IF nonempty child &
13. ((input key <= highest key in child)
14. OR (input key > highest key in child) & SM-Bit=0))
15. THEN
16. IF parent <> NIL THEN unlatch parent
17. Parent := Child
18. Child := Page-Search (Child)
19. Go to Descend
20. ELSE
21. Unlatch parent & child
22. S latch tree for instant duration
23. /* Wait for unfinished SMO to finish */
24. Unwind recursion as far as necessary based on noted page_LSNs and go down again
25. ELSE
26. CASE Op
27. Fetch:  . . .  /* invoke fetch action routine */
28. Insert: . . .  /* invoke insert action routine */
29. Delete: . . .  /* invoke delete action routine */
30. END

条件nonempty child & ((input key <= highest key in child) OR (input key > highest key in child) & SM-Bit=0))表明若没有SMO或本次操作的目标key不受SMO的影响，加锁逻辑与前文latch coupling逻辑一致，因此该算法允许部分操作和SMO操作并行执行，而对于必须等待SMO的操作，先释放其已持有的锁，防止阻塞其他事务，同时请求索引树的S latch，并等待。当锁获取成功后，通过调用链上记录的page_lsns判断相应节点是否变更，以快速恢复到断点，并继续进行。若已经遍历到叶节点，则执行相应的操作。

Fetch

1. Find requested or next higher key (maybe on NextPage)
2. Unlatch parent
3. Request conditional S lock on found key
4. IF lock granted
5. THEN
6. Unlatch child & return found key
7. ELSE
8. Note LSN and key position and unlatch child
9. Request unconditional 1ock on key
10. Once lock granted backup & search if needed

该算法首先查询目标key或者下一个最小key（next higher key）然后对查找到的key（目标key或者next higher key）加S lock（若next higher key不存在，此时将对该索引树一个特定的key加锁，该key表征索引尾部边界）。之所以要对next higher key加commit-duration的S lock，是为了防止目标Key正被某个未提交的事务删除，或目标key被其他事务插入（回顾表1，insert/delete都需要对next higher key 加X lock）。若查找过程中出现跨页，获取下一个页的latch，同时前一个页的latch不能释放，否则前一个页可能会被插入数据。当锁获取失败时，记录page_lsn，和key的位置然后释放latch并等待lock，当lock获取成功后，根据page_lsn判断页是否被修改，然后执行相应操作。

Fetch next

Fetch next流程首先定位一个key，然后不断顺序遍历符合范围查找要求的key，每次返回一个符合要求的key时都需要记录相应的page_lsn。下一次查找时需要比较page_lsn，若page_lsn变更，说明页被修改，此时需要按照Fetch逻辑查找下一个结果，否则继续顺序遍历。同样的，fetch next每次找到一个key，都需要加S lock，以防止phantom problem。

Insert

1. IF SM_Bit | Delete-Bit = 1
2. THEN
3. Instant S latch tree, set Bits to 0
4. Unlatch parent
5. Find key > insert key & X lock it for instant duration
6. /* Next key may be on next page ‘/
7. /* Latch next page while holding latch on current page*/
8. /* Lock next key while holding latch on next page also*/
9. /* Unlatch next page after acquiring next key lock */
10. Insert key, 1og and update page-LSN
11. Release child latch

插入时，若目标key已经存在，且索引为唯一索引，则返回错误，并持有该key的S lock至事务提交，以保证RR；若不为唯一索引，则执行插入操作。

若目标key不存在，则insert操作将定位到next higher key或该索引的尾部边界key。此时将对该key加X lock，持有周期为instant-duration。此后，若索引为唯一索引，则必须检测目标key是否正在被删除。该目的通过判断Delete-Bit(见后文)实现，若Delete-Bit为1，则说明该页存在删除操作，此时需要等待获取索引树的S latch。

此外，插入操作可能面临需要SMO的情况，相应操作流程如下：

1. Fix needed neighboring pages in buffer pool

3. X latch tree and unlatch parent
4. IF key delete THEN do it as "delete"

6. RememberLSN of last log record of transaction
7. Perform SMO at leaf, set SMO-Bit = 1,
8. modify neighboring pages’ pointers,
9. log, and unlatch pages

11. Propagate SMO to higher levels setting SMO-Bit to 1
12. Write DummyCLR pointing to remembered LSN

14. Reset SM_Bit to 0 in affected pages (optional)

16. IF key insert THEN do it as "insert"
17. Release tree latch

首先获取相应的页，然后对索引树加X latch，同时释放父节点的latch。然后进行split操作，完成后执行insert操作。

Delete

1. IF SMO-Bit = 1 THEN
2. Instant S latch tree and set SMO-Bit to 0
3. Set Delete_Bit to 1

5. Unlatch parent
6. Find key > delete key & X lock it for commit duration

8. IF delete key is smallest/largest on page
9. THEN
10. S latch tree and set Delete-Bit to 0

12. Delete key, log and update page_LSN
13. Release child latch and tree latch, if held

删除操作开始时需要设置delete_bit标志位，以阻止insert的进行。删除操作还必须找到next higher key，并加X lock，且持有周期为commit-duration以防止phantom problem。此外若被删除的key是索引的边界，还需要对索引树加S latch，该操作是因为索引边界变更会影响故障恢复，具体逻辑将会在下一篇描述故障恢复逻辑时进行描述。如果删除的key是页的最后一个key，则需要SMO，进行一次merge操作，其逻辑见insert部分。

分析

整体而言，针对索引并发控制中面临的问题，ARIES/lM的解决方案如下

原文：http://mysql.taobao.org/monthly/2020/05/03/