ARIES(Algorithm for Recovery and Isolation Exploiting Semantics)
ARIES的性质： WAL协议的算法
1. 数据结构
如图1，在ARIES中主要有三大模块：buffer pool manager，transaction system和log system。ARIES支持灵活的buffer pool管理策略，例如可以使用steal+no-force的page管理策略。
1.1 日志条目
| name | description |
|---|---|
| LSN | 日志条目的编号，log sequence number |
| Type | 日志类型 |
| TRX-ID | 写当前日志条目的事务id |
| PrevLSN | 当前事务上一条日志LSN，与CLR的UndbNxtLSN共同串联起rollback的日志链 |
| PageID | 日志条目的更新page目标 |
| UndoNxtLSN | CLR独有，表示当前某条日志的回滚完成，下一条目标回滚日志LSN，与PrevLSN共同形成rollback日志链 |
1.2 page
| name | description |
|---|---|
| page_LSN | 最新更新当前page的日志LSN |
1.3 DPT(dirty page table)
DPT由多条dirty page entry组成，每条entry的主要字段：
| name | description |
|---|---|
| page_id | 当前条目对应的page的id |
| RecLSN | 当一个非脏的page被pined去修改时，buffer pool manager记录日志LSN |
RecLSN表明自此日志开始，当前page有可能被修改且没有flush到stable storage。在recover过程中，RecvLSN可以减少对潜在dirty page的检查。
1.4 ATT(Active Transaction Table)
由多条事务条目组成，每条条目的主要字段有：
| name | description |
|---|---|
| trx-id | 当前条目对应事务的id |
| state | 事务状态：prepared（in-doubt），unprepared |
| LastLSN | 当前事务最新写的日志LSN |
| UndoNxtLSN | 当前事务回滚时，下一条要处理的日志LSN |
2.系统常规运行
- 事务在常规运行过程中，当修改page时，不断地向日志系统中写日志条目，一般的update日志为undo-redo log，包含了当前操作的redo信息（page-oriented信息）和undo信息（logical undo信息）【ARIES采用page-oriented redo log和logical undo log，page-oriented log可以隔离各个事务的history repeatition，响应了ARIES的I（isolation），而使用logical undo可以使数据库系统提供更好的并发性能】；更新ATT的LastLSN和UndoNxtLSN；如果是更新非脏页，更新DPT并设置其条目的RecvLSN；更新修改的page的page_lsn。
- 事务常规回滚时，写CLR（compensation log record）。CLR是read-only的日志，记录了目标日志的undo操作。【核心问题：CLR是undo log，那他是logical undo log还是page-orientd undo log? 上文阐述了ARIES采用logical undo log的策略，但是CLR并不是logical undo log，而是page-oriented undo log。不过虽然CLR的实际内容是page-oriented，但是其语义却是logical undo log。因为其是由上文提到的普通update日志的logical undo信息生成的，这也是ARIES最精妙的地方。】CLR使用UndoNxtLSN字段和其他日志的PrevLSN共同形成了事务回滚的日志链，使得在重复的系统故障中，DB的recovery是幂等的。同时，CLR可以描述undo行为，而undo行为可以是logical undo，因此ARIES支持logical undo。
- 在系统运行过程中，buffer pool manager周期性flush dirty pages。ARIES对buffer pool的page管理策略没有限制，支持steal+no-force的管理策略。
- 在系统运行过程中，系统周期性做checkpoint。ARIES支持fuzzy checkpoint，fuzzy checkpoint是异步的checkpoint，在其异步输出时可以不阻塞其他事物的处理。Fuzzy checkpoint格式：
<begin_chkpt>
......
<end_chkpt, ATT, DPT, others>
当<end_chkpt>写入后，系统中写入master_record，用以记录最新的checkpoint的<begin_chkpt>。在写DPT信息时，为了避免对事务造成场阻塞，可以少量地对DPT内容进行加锁写入。正确性不会影响，由recovery的analysis pass保证。
3. Recovery
如图展示了ARIES的recovery总体框架图。
ARIES的recovery过程有三个阶段：Analysis Pass、Redo Pass和Undo Pass
3.1 Analysis Pass
Analysis阶段以master record作为输入，找到最新的成功begin_chkpt LSN，并输出RedoLSN、ATT和DPT。RedoLSN用于指示Redo阶段开始redo行为的日志LSN。
Analysis Pass由begin_chkpt LSN开始分析到日志文件末尾。APT和DPT由checkpoint信息初始化，并在序列分析所有的日志信息时，如果更新的page不在DPT，则将该page添加到DPT中；如果有新事务（<begin>），则将该事物添加到ATT中；如果事务结束（<end>），则将事务从ATT中移除。对于普通的日志条目，根据其信息更新ATT和DPT。最终，RedoLSN = min(LSN(<begin_chkpt>), min(ATT_ENTRY[RecLSN]))
RESTART_ANALYSIS(Master_Addr, Trans_table, Dirty_pages, RedoLSN) ;
lnlitiallze the tables Trans_Table and Dirty_Pages to empty;
Master_Rec := Read_Disk(Master_Addr) ;
Open_Log_Scan (Master_Rec.ChkptLSN) ; /*open log scan at Begin_Chkpt record */
LogRec := Next_ Logo; /* read in the Begin_Chkpt record */
LogRec := Next_ Logo; /* read log record followlng Begln_Chkpt */
WHILE NOT(End_of_Log) DO;
IF trans related record & LogRec.TransID not in Trans Table THEN /* not chkpt/OSflle_return*/
Insert (LogRec.TransID, 'U' , LogRec.LSN, LogRec. PrevLSN) into TransTable; /* log record */
SELECT (LogRec.Type)
WHEN( 'update' I 'compensation') DO;
Trans_Table[LogRec.TransID].LastLSN := LogRec.LSN;
IF LogRec.Type = 'update' THEN
IF LogRec is undoable THEN Trans_Table[logRec.TransID].UndoNxtLSN := LogRec.LSN;
ELSE Trans_Table[LogRec.TransID].UndoNxtLSN := LogRec.UndoNxtLSN;
/* next record to undo is the one pointed to by this CLR */
IF LogRec is redoable & LogRec.pageID NOT IN Dirty_Pages THEN
insert(LogRec.PageID, LogRec.LSN) into Dirty_Pages;
END; /* WHEN( 'update'I 'compensation') */
WHEN( 'Begln_Chkpt') ; /* found an Incomplete checkpoint's Begln_Chkpt record ignore It */
WHEN( 'End_Chkpt') DO;
FOR each entry in LogRec.TransTable DO;
IF Trans ID NOT IN Trans_Table THEN DO;
insert entry (TransID, State, LastLSN, UndoNxtLSN) In TransTable;
END;
END; /* FOR */
FOR each entry in LogRec.DirtyPagLst DO;
IF PagelD NOT IN Dirty_Pages THEN insert entry (PageID, RecLSN) In Dirty_Pages;
ELSE set RecLSN of Dirty_Pages entry to RecLSN In Dirty_PagLst;
END; /* FOR */
END; /* WHEN( 'End Chkpt') */
WHEN( 'prepare' | 'rollback') DO;
IF LogRec.Type = 'prepare' THEN Trans_Table[LogRec.TransID].State := 'P' ;
ELSE TransTable[LogRec.TransID].State := 'U';
Trans_Table[LogRec.TransID].Last LSN := LogRec.LSN;
END; /* WHEN( 'prepare'I 'roll back') */
WHEN('end')
delete Trans_Table entry for which TransID = LogRec.TransID;
WHEN( 'OSfile_return')
delete from Dirty_Pages all pages of returned file;
END; /* SELECT */
LogRec := Next_ Log();
END; /*WHILE */
FOR EACH TransTable entry with (State = 'U') & (Undo Nxt LSN = O) DO; /* rolled back trans */
write end record and remove entry from Trans_Table; /* with missing end record */
END; /* FOR */
RedoLSN := minimum(Dirty_Pages.RecLSN) ; /* return start position for redo */
RETURN;
3.2 Redo Pass
Redo阶段以Analysis阶段输出的DPT和RedoLSN为输入，从stable storage中加载所有可能的dirty page，并从日志文件的RedoLSN开始，序列处理每条日志。如果当前日志是可redo的，日志目标更新page在DPT中，且LSN > Page_LSN && LSN > Dirty_Pages[LogRec.PageID].RecLSN，则将该日志在page上进行redo，同时更新page的Page_LSN为当前Log_LSN。
因此，DPT entry的RecLSN可以减少recovery过程中要校验的page数量。
Redo Pass是无锁的，因为ARIES中日志是page-oriented redo log和page-oriented undo log（CLR，由logical undo语义产生）。每个page的操作都是隔离的。因此，可以进行并行的redo。
RESTART-REDO(RedoLSN, Di rty_Pages);
Open_Log_Scan(RedoLSN); /* open log scan and position at restart pt */
LojRec := Next_ Logo; /* read log record a: restart redo point */
WHILE NOT(End_of_Log) DO; /* look at all records till end of log */
IF LogRec.Type = ( 'update' | 'compensation') &
LogRec is redoable &
LogRec.PageID IN Dirty-Pages &
LogRec.LSN >= Dirty_Pages[LogRec.PageID].RecLSN
THEN DO; /* a redoable page update.updated page mg-t not have made It to */
/* disk before sys failure.need to access cage and check Its LSN */
Page := fix&l atch(LogRec.PageID, 'X');
IF Page.LSN < LogRec.LSN THEN DO /* update not or cage.need to redo It */
Redo_Update(Page, LogRec); /*redo update */
Pag.LSN := LogRec.LSN;
END; /* redid update */
ELSE Dirty_Pages[LogRec. PageID].RecLSN := Page.LSN+1; /* update already on page */
/*update dirty page list with correct info, trans will happen if this */
/* page was written to disk after the checkpt but before sys failure */
unfix&unlatch (Page);
END; /* LSN on page has to be checked */
LogRec: = Next_ Log (); /* read next log record */
END; /* reading till end of log */
RETURN;
3.3 Undo Pass
从日志文件的最后日志开始反时间序分析。每个事务的待undo的log已经通过CLR的UndoNxtLSN和non-CLR的PrevLSN形成了undo日志链，在recovery过程中，下一条待undo的日志就是所有ATT中事务undo日志链的最新日志记录（UndoLSN := maximum(UndoNxtLSN) from Trans_Table entries with State = 'u';）。当一条日志是可undone的时，则将该日志undo，并向日志文件中补写当前被undone日志的CLR并更新ATT事务的UndoNxtLSN；如果是当前事务的首日志，则向日志文件中写当前事务的<end>日志并从ATT中删除；否则更新ATT事务的UndoNxtLSN。
Undo Pass也是无锁的，这是由于所有的更改在语意级都是绝对互斥的，一个还没commit的Tx如果可以进行某种“更改”并生成其伴随的Undo/Redo log，那么绝对不会有其他Tx可以更改同一个Object，从而生成冲突的Undo/Redo log, 换句话说，所有的Redo/Undo/CLR都在高层语意上是无冲突的，不同的Tx也许回改同一个页面，但是它们绝对不会更改同一个Row(如果数据库支持行锁)或者可以更改同一个Row，但是绝不会更改同一个Field(如果数据库支持field级锁)；无锁的Rollback是避免死锁的关键, 这样就不会发生Rollback和另外一个Rollback相互死锁的尴尬，此时需要Rollback一个Rollback, 这也是很多数据库设计力图避免的问题(引用知乎分析)
由于每个独立的事物都有自己的undo日志链，因此可以在事物级并行地进行undo【但是如何保证并行时仍然是反时间序？】
RESTART_UNDO(Trans-Table);
WHILE EXISTS (Trans with State = 'U' in Trans_Table) DO;
UndoLSN := maximum(UndoNxtLSN) from Trans_Table entries with State = 'u';
/* pick up UndoNxtLSN of unprepared trans with maximum UndoNxtLSN */
LogRec := Log-Read (UndoLSN); /* read log record to be undone or a CLR */
SELECT(LogRec.Type)
WHEN('update') DO;
IF LogRec is undoable THEN DO; /*record needs undoing (not redo-only record) */
Page := flx&latch(LogRec.PageID, 'X');
Undo_Update(Page, LogRec);
Log_Write('compensation' , LogRec.TransID, Trans_Table[LogRec.TransID].LastLSN,
LogRec.PageID, LogRec.PrevLSN, . . . ,LgLSN, Data); /* write CLR */
Page.LSN := LgLSN; /*store LSN of CLR in page */
Trans_Table[LogRec.TransID].LastLSN := LgLSN; /*store LSN of CLR in table */
unfix&unlatch(Page);
END; /* undoable record case */
ELSE; /* record cannot be undone - ignore it */
Trans_Table[LogRec.TransID].UndoNxtLSN := LogRec.PrevLSN; /* next record to process is the one preceding this record in its backward chain */
IF LogRec.PrevLSN = 0 THEN DO; /* have undone completely-write end */
Log_Wrlte( 'end' ,LogRec.TransID, Trans_Table[LogRec.Transit].LastLSN, . . .) ;
delete Trans_Table entry where TransID.LogRec.TransID; /* delete trans from table */
END ; /* trans fully undone */
END; /* WHEN('update') */
WHEN( 'compensation')
Trans_Table[LogRec.TransID].UndoNxtLSN := LogRec.UndoNxtLSN; /* pick up addr of next record to examine */
WHEN( 'rollback' | 'prepare')
Trans_Table[LogRec.TransID].UndoNxtLSN := LogRec.PrevLSN; /* pick up addr of next record to examine */
END; /* SELECT */
END; /* WHILE */
RETURN ;
ARIES的特性
- 支持小于page粒度的并发控制和多粒度锁机制
- 支持灵活的buffer pool管理策略（可以采用steal+no-force的最高灵活度策略）
- 低page存储负载（每个page只需要存储一个page_LSN字段）
- redo/undo的幂等操作不依赖对数据进行限制（通过CLR）
- Logical Undo（ARIES采用page-oriented redo log和logical undo log语义，CLR是由logical undo log语义生成的page-oriented undo log）
- 支持operation log和novel lock model
- 兼容redo-only和undo-only日志
- 支持partial/total事务回滚
- 支持数据对象跨page存储
- 支持动态的从OS获取/移除文件（操作视为redo-only）
- Nest top action（通过调整CLR的UndoNxtLSN字段，如果使用redo-only log，则该日志不可回滚，不符合语义）
- 高效的checkpoint（fuzzy checkpoint技术以及recovery过程中的checkpoint可以减少recovery时间）
- 对同一page的并发事务处理/回滚（只需要latch page）
- 事务回滚不需要获取锁（只需要latch page，锁正确性由高层语义保证，partial rollback后可以释放相关锁，同时避免了rollback中死锁的产生）
- 即使多次recovery，日志数量亦有限（redo pass不产生log，undo产生CLR，常规处理中事务写的每条日志至多产生一条CLR）
- 支持recovery并行（Analysis Pass预获取dirty pages list并执行并行IO，并行redo【page】，并行undo【transaction】，支持deferred recovey）
- fuzzy image copying技术
- 支持恢复失败事务
- recovey只需要一次逆向日志遍历
- CLR为redo-only，只需要redo信息（因此CLR的空间占用是事务普通日志的一半，普通日志为redo-undo log）
- 支持分布式事务
- partial rollback后，可以及时释放相关锁，亦简化了死锁检测逻辑（因为CLR不会被undone且non-CLR日志之多被undone一次）
感想
- ARIES最精妙在于CLR的使用，由logical undo语义产生page-oriented的CLR undo log。
- 通过page-oriented redo log和CLR实现了各个page之间的隔离性，可以并行redo。
- Undo pass的并行感觉效率不高，因为需要保证并行时任然维持反时间序列的正确性。（ARIES文中提到了有page级的undo pass并行，待进行阅读理解。）
- Analysis pass可以减少redo pass中的IO数量，提升并行效率
- 通过日志的时间序和page的日志隔离性，使得整个recovery的过程是无锁的。
