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

基本概念

概念解释
data-only lock将对索引键加锁实现为对相应数据记录加锁的锁方式，区别于index-specific lock
lock 和 latch的区别lock用于保护数据库内容，是常说的表锁/行锁中的锁概念，latch用于保护内存数据结构等临界资源，与mutex, rwlock是一类概念
commit duration 和instant durationlock的持有周期，commit duration 在commit后释放锁，instant duration 在相应操作完成后释放锁
索引节点和索引页针对B+树，本文混用两个概念，不做特别区分

索引数据结构

文章针对的索引按照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逻辑

 Next KeyCurrent Key
fetch & fetch next S for commit duration
insertX for instant duration 
deleteX for commit duration 

使用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的解决方案如下

问题解决方案
1 如何最小化并发更新索引的影响，提高并发效率使用latch coupling逻辑，使得同一时间持有的latch不超过两个
2 如何处理死锁问题使用latch coupling逻辑，严格有序地加锁
3 如何支持不同粒度的锁，锁对象该如何选取data-only lock，将对索引加锁实现为对相应数据记录加锁。锁的实际粒度等于数据记录中锁的粒度
4 如何解决phantom probleminsert/delete操作都对next higher key加X lock
5 唯一索引被删除后，如何确保该事务提交前该索引不被其他事务添加对next higher key 加X lock，且持有周期为commit-duration
6 如何让SMO和其他操作正确且高效地并行引入SM_BIT和tree latch，同时串行化SMO