Database · 理论基础 · ARIES/IM (一)

Database · 理论基础 · ARIES/IM (一)

《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 duration lock的持有周期,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 Key Current Key
fetch & fetch next   S for commit duration
insert X for instant duration  
delete X 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逻辑,其加锁主要步骤为:

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

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