数据库内核月报 － 2020 / 05

《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逻辑，其加锁主要步骤为：

Step 1: 对索引树根节点加S latch, 令当前节点等于root
Step 2: 进行检索操作，确定目标子节点，并将当前节点设置为目标子节点，检测当前节点，若
				（1）当前节点为叶节点且操作为fetch/fetch next，对当前节点加S latch；
				（2）当前节点为页节点且操作为insert/delete，对当前节点加X latch；
				（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 操作正在进行。因此索引树遍历的逻辑拓展为：

S latch root and note root’s page_LSN
Child := Root
Parent := NIL
Descend:
IF child is a leaf AND Op is (insert OR delete) 
THEN
  X latch child
ELSE 
  S latch child
Note child’s page LSN
IF child is a nonleaf page THEN
	IF nonempty child & 
		((input key <= highest key in child) 
			OR (input key > highest key in child) & SM-Bit=0))
  THEN
			IF parent <> NIL THEN unlatch parent
			Parent := Child
			Child := Page-Search (Child)
			Go to Descend
	ELSE 
			Unlatch parent & child
			S latch tree for instant duration
					/* Wait for unfinished SMO to finish */ 
			Unwind recursion as far as necessary based on noted page_LSNs and go down again
ELSE 
	CASE Op 
			Fetch:  . . .  /* invoke fetch action routine */
			Insert: . . .  /* invoke insert action routine */
			Delete: . . .  /* invoke delete action routine */
	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

Find requested or next higher key (maybe on NextPage) 
Unlatch parent 
Request conditional S lock on found key 
IF lock granted 
THEN 
	Unlatch child & return found key 
ELSE 
	Note LSN and key position and unlatch child 
	Request unconditional 1ock on key 
  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

IF SM_Bit | Delete-Bit = 1 
THEN
	Instant S latch tree, set Bits to 0
Unlatch parent
Find key > insert key & X lock it for instant duration
	/* Next key may be on next page ‘/
	/* Latch next page while holding latch on current page*/
	/* Lock next key while holding latch on next page also*/
	/* Unlatch next page after acquiring next key lock */
Insert key, 1og and update page-LSN
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的情况，相应操作流程如下：

Fix needed neighboring pages in buffer pool

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

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

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

Reset SM_Bit to 0 in affected pages (optional)

IF key insert THEN do it as "insert"
Release tree latch

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

Delete

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

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

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

Delete key, log and update page_LSN 
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的解决方案如下