Алгоритм восстановления. Фаза Undo.
Наконец Фаза 3 — Undo. После исполнения первых двух фаз, таблица незавершённых транзакций TT может быть не пуста. Эти транзакции не успели сделать коммит. Значит они должны откатиться, чтобы сохранить свойство атомарности.
Во время Undo транзакции должны откатиться в обратном хронологическом порядке относительно порядка, в котором они записывались. Для этого пока в TT есть записи Undo-фаза использует следующий алгоритм:
1. Выбирается запись с самым большим LSN.
2. Если запись update — эта запись откатывается при помощи CRL записи в WAL. Той самой записи, которая обычно записывается в WAL при роллбеках. Фактически ARIES подменяется неуспешные транзакции на успешные, которые просто сделали роллбек. В TT добавляется новая CLR запись для дальнейшего анализа.
3. Если эта запись CLR -> вместо неё добавляется её значение undoNextLSN. Если этого значения нет, запись удаляется из TT.
Посмотрим на примере выше. WAL всё ещё выглядит следующим образом:
30. [-, 1, X, "u", k+=2, k-=2]
31. [-, 2, Y, "u", n-=3, n+=3]
32. [30, 1, X, "u", k+=9, k-=9]
33. [31, 2, Y, "c"]
-- RESTART
Undo фаза смотрим в TT. Видит там запись
1, 32 и начинает её откатывать при помощи clr записи. После отката новое состояние WAL будет:
30. [-, 1, X, "u", k+=2, k-=2]
31. [-, 2, Y, "u", n-=3, n+=3]
32. [30, 1, X, "u", k+=9, k-=9]
33. [31, 2, Y, "c"]
34. [32, 1, X, "clr", k-=9, 30]
А TT обновится до
1, 34
Добавление новой CLR записи в WAL следует такому же write-ahead протоколу, как и добавление обычных записей. Другими словами, эта запись не может попасть на диск, пока она не будет сохранена в журнал WAL.
При откате 32 записи видно, что эта транзакция связана с записью 30 (поле prevLSN). Это значение копируется в undoNextLSN CLR записи. Таким же образом undoData копируется в redoTheUndoData.
Пусть в этот момент происходит ещё 1 рестарт. ARIES же обещает, что всё будет работать и при рестартах. Посмотрим!
30. [-, 1, X, "u", k+=2, k-=2]
31. [-, 2, Y, "u", n-=3, n+=3]
32. [30, 1, X, "u", k+=9, k-=9]
33. [31, 2, Y, "c"]
34. [32, 1, X, "clr", k-=9, 30]
-- RESTART 2
Снова запустим анализ. После анализа первых 4 записей (30-33) состояние TT и DPT такое же, как было и раньше в конце первого рестарта.
DPT:
X, 30
Y, 31
TT:
1, 32
Но анализ ещё не завершен, ведь есть запись под номером 34. После обработки этой записи DPT не изменится, а вот TT поменяется на
1, 34
Как видите это ровно такое же состояние, в котором был TT во время undo фазы предыдущего рестарта. ARIES пришёл ровно в тоже самое состояние, что и раньше.
Redo фаза снова обновит состояние буферов страниц. Останется только завершить процесс восстановления в undo фазе. Снова смотрим на запись с самым большим LSN — это запись 34. Пункт 3 алгоритма говорит, что если запись является CLR, значение в TT должно обновиться на undoNextLSN. Новое состояние TT:
1, 30
Снова ищем самый большой LSN по TT. Находим 30. Запись update, поэтому надо откатить при помощи CLR. У записи нет prevLSN, значит это последняя CLR запись. Теперь состояние WAL будет:
30. [-, 1, X, "u", k+=2, k-=2]
31. [-, 2, Y, "u", n-=3, n+=3]
32. [30, 1, X, "u", k+=9, k-=9]
33. [31, 2, Y, "c"]
34. [32, 1, X, "clr", k-=9, 30]
35. [34, 1, X, "clr", k-=3, -]
А в TT получится:
1, 35
Остался последний шаг — вытаскиваем самый больше LSN из TT — 35. Это CLR, значит значение в TT для транзакции 1 в соответствии с пунктом 3 нужно обновить на undoNextLSN, но там "-". Это значит, мы произвели полный откат транзакции и запись можно удалить. Наконец-то в TT больше нет записей. Состояние базы данных успешно восстановлено.