Aione's blog

一起快乐摸鱼吧🐳

  1. 1. ARIES 中的数据结构
  2. 2. Updates
  3. 3. Total or Partial Rollbacks
  4. 4. Checkpoints
  5. 5. Analysis Pass
  6. 6. Redo Pass
  7. 7. Undo Pass
  8. 8. Checkpoints During Restart
  9. 9. 原文

大概是 ARIES 论文的阅读笔记。

ARIES 中的数据结构

老生常谈的东西了,包含以下几样:

  • LSN: log 的唯一标识符。
  • Type: 用来区分 log 的类型。
  • TxnID
  • PrevLsn: 同事务的上一条 log,在 undo 中可以减少我们寻找下一条需要被 undo 的log 所需的时间。
  • pageId
  • pageLSN: 可以加速 redo, 在没有 dpt 辅助的情况下,如果此时我们不存在 pageLSN,那么找到 redo start 的唯一方法就是,从 checkpoint 向后扫描 log, 根据 log 找出在 checkpoint 后未结束的事务,然后从 checkpoint 向前扫描, 找到这些事务对页发生修改的最早的 lsn。这样还有一个问题,当我们进行 redo 的时候,可能会发生重复 redo 破坏数据的一致性。
  • UndoNextLSN: 在 CLR log 中,用于指定下一条需要被 undo 的 log。
  • transcation table: 在 checkpoint 当中被用到,表中每个条目维护一个 tid, lastlsn,undoNextLsn, 用这个表我们可以找到每个事务最后一条 log 所在位置,方便进行 undo。
  • dirty page table: 脏页表,每个条目记录第一次使该页不同于硬盘上的页的 lsn。
    该表可以让我们在恢复的时候更加方便的找到 redo start。

Updates

更新记录的基本操作如下

1
2
3
4
5
6
7
8
9
10
lockManager.Lock(oid)
bufferPoll.Get(pageId)
bufferPool.Pin(page)
page.Xlock()
defer page.XUnlock()
defer buffPool.Unpin(page)

logManager.LogUdate()
page.doChange()
bufferPool.setPageLSN(page)

这么做是为了保证日志的顺序和对页更新的顺序一致,如果顺序不一致,在 redo 的时候不一定能保证事务的一致性,比如写入覆盖这个问题。同时,注意修改 pageLsn 一定在 page 被修改过后,这是由于,考虑如下情况

1
2
3
4
write update log
chaneg page lsn
checkpoint
crash

那么恢复的时候会认为该页的最后一条记录已经反应到磁盘上了,但实际上我们只修改了 pagelsn,具体内容对修改并没有反映到磁盘上。

在对记录更新对时候,有一种特殊情况:插入,由于在插入数据之前我们并不知道它的 oid, 所以无法对其进行 lock,只有在我们获取了该页的 latch 并且知道插入位置之后才能获取到 lcok,但是在这种情况下可能会产生死锁。而且这种死锁不能被 lockmanager 所探测到。

解决的方法如下,当我们向 lockmanager 发送一个立即返回的 condition lock 请求,此处的 condition 可以为 page.freeSpace() > tuple.Size() && dstSlot.free() 如果接受,那么按正常操作继续。如果没有,释放 latch,获取一个正常的 lock,该lock返回之后获取 latch,并检查该 slot 是否可用,如果不可用,则重复上述步骤(感觉自己理解还是有问题,原文如下)

T o avoid waiting for a lock while holding a latch, which could lead to an undetected deadlock, the lock is requested conditionally, and if it is not granted, then the latch is released and the lock is requested unconditionally. Once the unconditionally requested lock is granted, the page is latched again, and any previously verified conditions are rechecked. This rechecking is required beacuse, after the page was unlatched, the conditions could have changed. The page_LSN, on relatching, if any changeds could have possibly occurred. If the conditions are still found to be satisfied for performing the update, it is performed as described above. Ohterwise, corrective actions are taken. If the conditionally requested lock is granted immediately, then the update can proceed as before.

Total or Partial Rollbacks

基本操作如下

1
2
3
4
5
6
7
8
9
10
11
log := txnManager.UndoNextLsn(tid)

lockManager.Lock(log.oid)
bufferPoll.Get(log.pageId)
bufferPool.Pin(log.page)
page.Xlock()
defer page.XUnlock()
defer buffPool.Unpin(page)

page.doUpdate()
logManager.LogClr()

rollback 部分比较简单,不过这里 writelog 的时间点和前面有所不同,只有在操作被 undo 之后才会写 clr log,同时 clr log 里的 undoNextLSN 非常重要,当我们 total rollback 但中途 crash 的时候,我们可以利用 txnTable 里的 lastLsn,直接找到对应下一条该重做的 log,提升了恢复速度。

为什么要在 undo 之后写 log,主要原因和上面差不多,如果提前写 log,就会存在虚空 undo 的情况,导致少撤销一条操作。

Checkpoints

ARIES 采取了 fuzzy checkpoint 技术,fuzzy checkpoint 也就是说,当我们进行 checkpoint 操作的时候不需要 stw,我们只是记录一些元信息,方便更快的恢复,不过这也需要和 bufferpoolmanager 进行配合,需要 bpm 定时向硬盘写入 pagebuffer,减少恢复所需的工作量。

fuzzy checkpoint 的基本操作如下,当系统进行 checkpoint 操作的时候,首先向日志写入 checkpoint_start, 然后写入 dirty page table, txn table,之后标注 checkpoint_end, 最后将 master-record 指向的记录改为当前 checkpoint_start 所在位置。

Analysis Pass

这阶段的目的是完善 dpt 和 txnTable, 当我们 crash 的时候,checkpoint 之后的操作也需要进行 redo 和 undo,而这部分的信息并没有包含在 checkpoint 的两张表内,我们需要借助当前 pass 进行补全。

当前 pass 会产生 txnTable, dpt, redoLsn 三个数据结构,用于接下来两个 pass 的操作。 redoLsn 是在 dpt 里最小的 reclsn,如果 dpt 为空,也就是说没有修改发生,那么我们就没必要进行 redo。

当前 pass 如何构造 dpt, txnTable

  • dpt: 对遇到的每条记录,如果所做修改的的页没有在 dpt 中出现,dpt.append(lsn, lsn)
  • txnTable: 对遇到的每条记录,如果指明了某个事务结束,则从 txnTable 中移除,否则更新 txntable 的状态,即更新 txnTable 对应条目的 undoNextLsn, lastLsn, state

Redo Pass

redo 只需要从 redoLsn 开始向后重做就好了,不过要检查几个要素,要被 redo 的页是否在 dpt 中,当前 lsn 是否大于等于该页的 recLsn,该页的 pageLsn 是否小于该 log 的lsn。

当我们 redo 的时候,有可能会从 checkpoint 前某个点开始 redo,这样就会造成部分页已经被写入了硬盘并且日后也未被修改,所以 checkpoint 的时候不在 dpt 当中,不需要被修改。

关于 pageLsn,如果 pageLsn 大于当前 lsn,即证明该条记录所做的操作已经落盘,不需要进行重做,而且我们的 recLsn 需要更新,更新为比 pageLsn 大一点的记录。由于 pageLsn 只在 redo 的时候需要,这么做也是可以的。

redo 部分可以发挥并行优势,因为我们的 redo 是面向 page 的,也就是说对于 dpt 的所有 page,我们都可以进行并行操作,只要事先/或者流水线 准备好对应 page 的 log queue,依次执行即可。

Undo Pass

因为之前的 redo pass, 当前要做的只是把 crash 时刻没有完成的事务撤销而已。undo 部分的操作和前面 rollback 基本一致,不同的是这里取得 undoNextLsn 是从 txnTable。

Checkpoints During Restart

Analysis Pass 在完成这个 pass 之后,我们将现在的 dpt/txnTable 写入到硬盘上,这样下次恢复的时候就可以跳过 Analysis pass.

Redo Pass 每次 bufferpool 向磁盘写入修改过后的页的时候,就更新该页的记录为当前 log 的下一条记录,由于 redo 是从前往后,所以同样保证了 wal 的性质。并且,在这种情况下,我们下次重启的时候就可以少一些 redo。其他记录 checkpoint 相关的记录保持不变。

Undo Pass 在启动 undo pass 的时候,将 dpt 更新为现在 bufferpoll 的 dpt,很容易理解,在下次进行重启操作的时候只要由于前面两个 pass 的操作,可以减少工作量。

原文

ARIES : A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging

Author : Aione
本文使用 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议
Link to this article : https://aione.space/2020/05/26/aries/

This article was last updated on days ago, and the information described in the article may have changed.