ARIES

Tags: [ database chinese note ]

ARIES Database Crash Recovery Algorithms

ARIES

Algorithms for Recovery and Isolation Exploiting Semantics

ARIES 恢复协议的main idea:

• Write Ahead Logging: Any change is recorded in log on stable storage before the database change is written to disk (STEAL + NO-FORCE)
• Repeating History During Redo: restart时，回溯操作并将数据库恢复到崩溃前的确切状态
• Logging Changes During Undo: 将Undo操作记录到日志中，以确保在重复失败的情况下不会重复操作

WAL Records

每个log record中包含一个log sequence number (LSN)

• Data page中有pageLSN: 该page的最新更新的LSN
• flushedLSN: 到目前为止已刷新的最大LSN
• 在第 i 页可以写入磁盘之前，我们必须至少将日志刷新到 $pageLSN_i <= flushedLSN$ 的位置

Normal Execution

Transaction Commit

• 事务提交时，先在log buffer(WAL文件)中写一个 COMMIT标识，再将所有log records刷到disk中，包括刚记录的 COMMIT标识
  • log刷新是对disk的顺序同步写入
• 当 COMMIT标识储存在disk上时，DBMS会向application返回一个事务已提交的确认
• 之后DBMS会在log buffer中写一个 TXN-END表示事务在系统中已经全部完成，不会再记录任何log record
  • TXN-END是internal bookkeeping，不需要立即刷到disk上

Transaction Abort

Abort是仅适用于一个事务的ARIES撤销操作的一种特殊情况

• 在log record中添加 prevLSN
  • prevLSN记录事务先前的 LSN，DBMS使用这些 prevLSN构造一个linked-list，更轻松地遍历log去查找records
• 引入Compensation Log Record(CLR, 与BEGIN, UPDATE等并列)
  • 描述为了撤销先前更新记录的操作而采取的操作
  • has all the fields of an update log record and the undoNext pointer (下一个要撤销的LSN)
  • CLR不需要撤销
• 要Abort事务的话
  • 先将 ABORT记录到memory的log buffer中
  • 然后它以相反的顺序撤销(undone)事务的update更，以从数据库中删除它们的影响
  • 对于每个撤销的update，DBMS在log中创建CLR并恢复旧值
  • 在所有abort txs的updates都被恢复后，DBMS最终写入 TXN-END的log record

Checkpointing

DBMS一般会定期获取checkpoints，将buffer pool中的dirty pages写入disk

used to minimize how much of the log it has to replay upon recovery

这里讨论两种blocking checkpoint methods(阻塞checkpoint的方法)，DBMS会在checkpoint过程中暂停transactions，确保DBMS在checkpoint期间不会错过对page的update

Blocking Checkpoint

DBMS将everything暂停，确保a consistent snapshot写入disk

• 暂停任何新txs的开始
• 等到所有active txs完成执行
• 刷新disk上的dirty page

另一种更好一点的Blocking Checkpoints

DBMS可以不必等到所有active txs完成执行 我们必须记录checkpoint开始的时候的内部系统状态

• 暂停任何新的txs的开始
• 在DBMS执行checkpoint的时候暂停txs

(记录checkpoint和checkpoint之间的)

引入几个两个Table:

Active Transaction Table (ATT)

ATT表示DBMS中active transactions的状态 在DBMS完成该事务的commit/abort的过程之后，将会删除这个事务的entry

对于每个transaction的entry，包含以下信息:

• $transactionID$: Unique tx identifier
• $status$: 当前tx的状态(mode)(Running, Committting Undo candidate)
• $lastLSN$: 事务写入的最新的LSN

Dirty Page Table (DPT)

DPT里面有关于在buffer pool中被uncommitted txs修改的pages的信息 每个dirty page都有$recLSN$->即首先导致page变脏的log record的LSN

然后这里是另一种更好的方法，允许tx在checkpoint期间继续执行，但是需要DBMS记录附加的信息，以此确定它可能错过了哪些updates

Fuzzy Checkpoints

DBMS允许其他txs继续运行

主要是用了额外的log records来track checkpoint boundaries:

• <CHECKPOINT-BEGIN>: Start of the checkpoint
• <CHECKPOINT-END>: When the checkpoint has completed. Contains ATT+DPT.

ARIES Recovery

ARIES Protocol由三阶段组成，当crash后重启，DBMS将执行以下阶段

1. Analysis: 读取WAL以识别buffer pool中的dirty page和crash时的active transaction
2. Redo: 从log中的适当点开始重复所有操作
3. Undo: Reverse crash前的未提交事务的操作

Analysis Phase

从通过databse的MasterRecord LSN找到最后一个checkpoint开始:

1. 从checkpoint向前扫描log
2. 如果DBMS找到一条TXN-END记录，则从ATT中删除其tx
3. 所有其他记录，将tx添加到状态为UNDO的ATT中，并在提交时将tx状态修改成COMMIT
4. 对于UPDATE的log record，如果page $P$不在DPT中，则将P添加到DPT并将P的recLSN设置为log record的LSN

这里的57:53开始有例子

Redo Phase

目标是重复history来重建crash时刻的状态，重新应用所有updates(甚至可能aborted txs)并redo CLRs

DBMS从DPT中包含最小$recLSN$的log record开始向前扫描，对于具有给定LSB的每个update log record或者是CLR来说，DBMS会re-apply the update，除非:

• Affected page is not in the DPT or
• Affected page is in DPT but the record’s LSN is greater than smallest $recLSN$ or
• Affected $pageLSN(on disk) >= LSN$

redo的话，DBMS会重新过一遍log record中的change，然后将affected page的pageLSN设置成该log record的LSN

当redo阶段结束之后，DBMS会为所有状态为COMMIT的tx写入TXN-ENDlog record，并将他们从ATT中删除

Undo Phase

在最后一个阶段，DBMS会reverse crash时处于active的所有txs，这些都是在analysis phase之后在ATT中具有UNDO状态的事务

DBMS使用lastLSN在reverse LSN顺序处理事务，从而加快遍历的速度，当它reverse tx的update时，DBMS会为每次修改将CLR entry写入log中。

一旦最后一个tx成功abort，DBMS就会flush log，然后准备开始处理新tx

---

related posts: