Семейство алгоритмов ARIES

К сожалению, ситуация с литературой по системам баз данных в нашей стране такова, что многие важные работы не только не переведены на русский язык, но зачастую не существует даже их русскоязычных обзоров. Такая ситуация сложилась и с алгоритмами ARIES, служащими для восстановления систем, поддерживающих понятие транзакции, — несмотря на массу англоязычных публикаций про алгоритмы этого семейства и его признание, на русском языке прочитать о нем практически нечего.

Семейство ARIES, содержащее алгоритмы восстановления систем, где поддерживается понятие транзакции, крайне популярно. Данные алгоритмы используются в целом ряде программных продуктов ведущих производителей, включая СУБД IBM DB2, Starburst и Lotus Domino/Notes, а также СУБД O2, Microsoft SQL Server, а также файловую систему NTFS. Чем вызвана такая популярность? Дело в том, что алгоритмы семейства оказались чрезвычайно гибкими: не фиксируя особенностей реализации, любой из них предлагает разработчику массу вариантов для достижения тех или иных преимуществ.

Каждый из алгоритмов представляет собой собрание множества небольших подалгоритмов, которые сравнительно легко понять и реализовать. К тому же, алгоритмы семейства отличаются сильной «ветвистостью»: в них рассматриваются различные способы реализации того или иного эффекта — в зависимости от выбранных способов журнализации, буферизации, структур данных и т.д. Вероятно, именно вследствие этого оригинальное название Algorithm for Recovery and Isolation Exploiting Semantics довольно быстро претерпело небольшие изменения — первую букву названия стали расшифровывать как Algorithms.

Краткая история ARIES

В середине 80-х годов в исследовательском центре корпорации IBM Almaden Research Center стартовал проект Starburst. Его целью было создание расширяемой реляционной СУБД. Группа исследователей решила сосредоточить свое внимание на устройстве системы управления транзакциями и пересмотрела ряд предположений и выводов, к которым пришли разработчики знаменитой СУБД System R. Эта деятельность позволила выявить сильные и слабые места в конструкции существовавших систем. Так, выяснилось, что разработчики System R, хотя и убедились в том, что при восстановлении базы данных упреждающая журнализация работает лучше механизма теневых страниц, но не преуспели в разработке методов журнализации и восстановления, в которых поддерживались бы блокировки небольших объектов (например, кортежей) без блокировки более крупного объекта. Скажем, в иерархической СУБД IMS можно было производить блокировки самых различных объектов, однако захват происходил не на логическом, а на физическом уровне: блокировка закрывала доступ к конкретным сегментам памяти. Это приводило к тому, что реорганизация кортежей в странице должна была происходить в режиме, запрещающем операции над страницей. Создатели ARIES решили объединить лучшие разработки IBM в области управления транзакциями, журнализацией и восстановлением в единый алгоритм.

Следующий этап развития ARIES включал внедрение алгоритмов в индустрию и разработку расширений. Наиболее интересное из расширений, по-видимому, — ARIES for Semi-Structured Data. Это расширение было выполнено в рамках проекта Dominotes по разработке способа восстановления на основе журнализации для Lotus Domino/Notes [1]. Выяснилось, что несмотря на существенные особенности модели квазиструктурированных данных ARIES удалось сравнительно легко адаптировать и внедрить в уже существовавший продукт. Алгоритмы ARIES/KVL и ARIES/IM ориентированы на детальную разработку способов управления индексами и в различной степени реализованы в СУБД DB2 [2].

Разработкой алгоритма занималась группа исследователей, но вдохновителем и идеологом ARIES стал Си Мохан. В 1999 году за работу над ARIES он получил награду 10 Years Award; доклад, сделанный им по этому поводу, опубликован в виде статьи [3]. Работы над ARIES привели также к формированию Института технологий баз данных — особого структурного подразделения в составе корпорации IBM, что стало отражением более четкого осознания проблем, стоящих перед сообществом баз данных.

Сегодня ссылки на ARIES можно найти в самых известных учебниках по системам баз данных. Семейство алгоритмов изучают во многих американских университетах. В ряде из них разработаны специальные программные системы для демонстрации свойств ARIES; примером может служить система Mars, разработанная в университете Корнелла.

Обратимся к описанию ARIES, ограничившись рассмотрением лишь основного алгоритма, на базе которого созданы все расширения. Будем говорить об ARIES в контексте баз данных, хотя этим область его применения не ограничивается.

Журнализация и теневые страницы

ARIES предусматривает запись в журнал данных о всех действиях производимых транзакциями, способных изменить состояние базы данных. Используется широко известный метод упреждающей журнализации (write ahead log, WAL), предполагающий, что записи о некоторой операции над базой данных попадают на жесткий диск раньше, чем в базу вносятся изменения, произведенные этой операцией.

Альтернативной техникой восстановления в случае сбоев является механизм теневых страниц. Основное отличие этого метода состоит в том, что в WAL изменения, внесенные в страницу базы данных, записываются в то же место, где располагалась предыдущая версия данных, а при использовании теневых страниц измененная версия страницы данных записывается на другое место диска. В случае сбоя можно восстановить базу данных на основе старой («теневой») версии страницы и журнала. Как видно, идея, стоящая за теневым механизмом, проста и легко поддается реализации, однако по ряду причин техника восстановления на основе теневых страниц, несмотря на всю свою простоту, считается хуже [4].

Структура записей журнала

Поскольку в ARIES на журнал возлагается вся ответственность за восстановление данных, записи журнала достаточно сложны, содержат массу информации и в зависимости от журнализуемого действия имеют различную структуру. Скажем, запись, помещаемая при обычной работе транзакции, несколько отличается от так называемой компенсационной записи (compensation log record, CLR), помещаемой в случае частичного или полного отката транзакции.

Перечислим некоторые поля записи журнала, используемые при описании алгоритмов ARIES.

• LSN (Log Sequence Number) — номер записи. Для простоты можно считать, что это значение постоянно увеличивается, благодаря чему номера не используются повторно. Удобно также считать, что сам журнал представляет собой бесконечно увеличивающийся файл (конечно, на практике обычно используется группа файлов). В качестве LSN часто используют адрес первого байта записи журнала; в таком случае хранить LSN в виде отдельного поля не обязательно.
• Type — тип действия, которое описывает запись. В этом поле могут встретиться такие значения, как compensation (откат некоторого шага транзакции), update или commit. Тип действия не обязательно связан с работой транзакций; например, записи могут относиться к работе менеджера буферизации.
• TransID — идентификатор транзакции, к которой относится запись.
• PrevLSN — номер предыдущей записи, которая добавлена журнализуемой транзакцией. В первой записи, созданной транзакцией, это значение полагается равным нулю. Таким образом, все записи, которые описывают изменения, вносимые данной транзакцией, оказываются связанными в список. При необходимости отката это позволяет пройти от конца транзакции к началу, по шагам отменяя все совершенные ею действия.
• PageID — идентификатор изменяемой страницы данных. Присутствует только в записях, описывающих действия по изменению данных.
• UndoNxtLSN — номер следующей записи, требующей обработки при откате. Присутствует только в CLR-записях. Существенная особенность ARIES состоит в том, что CLR-записи, фиксирующие откаты транзакций, сами не допускают отката. Именно по этой причине такие записи содержат поле UndoNxtLSN, которое позволяет при откате обойти CLR, проследовав к той записи, на которую оно указывает. Обычно данное поле содержит номер записи, расположенной в списке записей, описывающем действия данной транзакции, перед той записью, откат которой фиксирует CLR. Поскольку обычно требуется отменить не собственно откат, а несколько действий транзакции (может быть, даже все), то тем самым устраняется потребность в лишней работе. В самом деле, зачем отменять откат, восстанавливая некоторое действие, если тут же будет отменено и само это действие?

Рис. 1. Пример использования указателей UndoNxtLSN

Предположим, сначала некоторая транзакция совершила несколько действий, а затем вследствие каких-то причин начала откат. Ее действия будут последовательно откатываться в обратном порядке относительно их совершения. Каждому действию будет соответствовать своя CLR-запись. На рис. 1 показаны ссылки UndoNxtLSN компенсационных записей, созданных при откате второго и третьего действий. Таким образом, поле UndoNxtLSN последней такой записи содержит LSN следующего действия транзакции, которое нужно будет обработать при откате.

• Data. В зависимости от типа записи это поле содержит информацию, необходимую при восстановлении или откате. Обычно это самое длинное поле записи журнала, содержащее информацию непосредственно из базы данных (в частности, это может быть образ объекта до и после его изменения).

Объясним теперь, как в ARIES отслеживаются состояния страниц базы данных. Говоря о состоянии страницы, главным образом, интересуются, попали ли в нее изменения, описанные в журнале. Чтобы выяснить это, в каждую страницу помещается номер записи, которая описывает последнее изменение, внесенное в данную страницу; будем называть его page_LSN. Сравнивая его со значениями номеров записей журнала, можно выяснить, были ли внесены описываемые данной записью изменения в страницу или нет. Вся эта информация необходима во время восстановления после сбоя. ARIES очень детально описывает процесс восстановления, что, возможно, и стало главным фактором его популярности.

Дополнительные структуры данных

Таблица транзакций содержит информацию о всех незавершенных транзакциях, существующих в данный момент в системе. Данная таблица используется также при установке контрольных точек и восстановлении. Элемент таблицы содержит идентификатор транзакции и номер последней записи, помещенной в журнал этой транзакцией (LastLSN). Кроме того, элемент таблицы содержит указатель UndoNxtLSN, а также поле, описывающее статус транзакции. Статус prepared означает, что транзакция готова зафиксировать все требуемые изменения и ждет подтверждения от инициатора распределенной транзакции, составной частью которой она являлась, чтобы завершить работу. В то же время такая транзакция должна сохранять ряд блокировок, чтобы быстро откатиться в случае неудачного завершения распределенной транзакции. unprepared характеризует состояние, когда транзакция находится в процессе работы и еще не готова к завершению.

Как можно использовать эту информацию? В случае сбоя транзакцию, находившуюся в этот момент в состоянии unprepared, во время восстановления, скорее всего, придется откатить. Но если транзакция находилась в состоянии prepared, то может оказаться так, что она должна быть восстановлена и завершена. Это происходит, если инициатор транзакции все еще ждет от нашей базы данных завершения ее части распределенной транзакции.

В поле UndoNxtLSN элемента таблицы транзакций содержится номер следующей записи журнала, которую необходимо обработать при откате. В случае, когда последняя запись не является CLR-записью, это значение совпадает с LastLSN. В противном случае это значение будет браться из одноименного поля CLR-записи.

Важное достоинство ARIES состоит в том, что алгоритм не накладывает никаких ограничений на политику, используемую менеджером буферизации кроме требования поддержки упреждающей журнализации. Вся необходимая для восстановления информация собирается на основе данных из журнала. Но если конкретная политика буферизации неизвестна, во время восстановления потребуется некоторая дополнительная информация о состоянии страниц базы данных. Эта информация содержится в таблице «грязных» страниц.

Страницу буферного пула называют «грязной», если она содержит изменения, еще не внесенные в тот вариант страницы, который расположен во внешней памяти. Чтобы отслеживать такие страницы, менеджер буферизации и поддерживает таблицу грязных страниц. Каждый элемент этой таблицы содержит пару значений: идентификатор страницы и номер записи, используемый при восстановлении (RecLSN). Зная значение RecLSN, можно установить, с какого номера записи нужно просматривать журнал, чтобы восстановить страницу с данным идентификатором. (Таблицу «грязных» страниц можно реализовать с использованием хеширования.)

Параллельная природа ARIES

ARIES спроектирован для оптимальной работы в параллельной среде как в нормальном режиме, так и в режиме восстановления. Применительно к нормальному режиму это означает, прежде всего, наличие развитой системы управления транзакциями.

В условиях одновременной работы множества транзакций необходимо позаботиться о том, чтобы данные оставались согласованными, а для этого нужно особое внимание уделить совместно доступным объектам баз данных. В большинстве СУБД в качестве средства контроля согласованности данных используются блокировки (lock). В ARIES наряду с ними используется также механизм легких семафоров (latch). Блокировки применяются для контроля логической согласованности данных, в то время как легкие семафоры служат средством контроля физической согласованности. Установка легкого семафора — гораздо более дешевая операция, чем установка блокировки. Также легкие семафоры обычно удерживаются на гораздо меньших промежутках времени, нежели блокировки. Еще одно важное различие этих двух механизмов в том, что система обнаружения тупиков не получает информацию о работе легких семафоров; их можно использовать лишь в том случае, когда имеется абсолютная уверенность, что они не станут причиной возникновения тупика.

Для максимально возможного распараллеливания во время восстановления ARIES позволяет восстанавливать каждую страницу базы данных в отдельности. Это свойство обеспечивается наличием на каждой странице поля PageLSN, содержащего номер записи журнала, которая описывает последнее изменение, внесенное в эту страницу. Таким образом, при восстановлении можно сразу определить, какие действия над этой страницей следует повторены. Поскольку ARIES на одной из первых стадий восстановления повторяет все действия, произведенные над базой данных к моменту сбоя, нужно просто применить к данной странице все изменения, для которых номера записей в журнале больше, чем PageLSN.

Контрольные точки

Различают три вида сбоев:

• сбой транзакции, при котором по каким-то причинам транзакция не может завершиться, и ее требуется откатить;
• мягкий сбой системы, при котором теряется содержимое буферов основной памяти, и требуется восстановить базу данных на основе журнальной информации;
• жесткий сбой, при котором теряются один или несколько жестких дисков.

Остановимся на восстановлении после мягких сбоев.

Как и в большинстве случаев, восстановление в ARIES основывается на механизме контрольных точек, что позволяет уменьшить объем журнала, который нужно будет обработать при восстановлении. Во многих СУБД при установке контрольной точки существенно изменялся режим работы системы. Скажем, в System R для этого временно прекращалась инициация новых транзакций; система дожидалась завершения работы всех операций всех транзакций и выталкивала буферы основной памяти на диск. Это очень дорогой способ создания контрольных точек, ведь система становится недоступной для пользователей. В ARIES контрольные точки устанавливаются асинхронно, не приостанавливая работу СУБД. Более того, установка контрольной точки не требует сброса буферов памяти.

С точки зрения ARIES, контрольная точка — это всего лишь множество специфических записей журнала. Создание контрольной точки начинается с добавления в журнал записи begin_chkpt, а завершается добавлением записи end_chkpt, содержащей копии таблицы транзакций, таблицы «грязных» страниц, а также некоторую дополнительную информацию. Для простоты будем полагать, что все эти сведения содержатся в одной записи. После того, как запись end_chkpt добавлена в журнал, номер первой записи (begin_chkpt) заносится в специальное место, называемое главной записью (master record). Обычно контрольные точки устанавливаются в процессе нормальной работы, но возможны случаи, когда так поступают и во время восстановления. К этому прибегают, если ожидаются сбои во время работы собственно системы восстановления.

Схема восстановления

Процесс восстановления в разных системах выглядит схожим образом. Сначала проходит анализ, во время которого из журнала собираются сведения, необходимые для восстановления. Прежде всего, при этом определяют те транзакции, действия которых необходимо повторить, и те, действия которых нужно отменить. После этого следуют стадии повторения и отмены. Обычно во время повторения в базу данных вносятся все изменения, которые были сделаны транзакциями, успевшими завершиться к моменту сбоя. Соответственно отмена заключается в том, чтобы отменить действия, совершенные транзакциями, нуждающимися в откате. В ARIES есть некоторое отступление от этой схемы — на стадии повторения алгоритм повторяет все действия, которые были отражены в журнале к моменту сбоя. Иными словами, после этой стадии база данных находится в том же состоянии, в каком она была во время сбоя, а уже после этого происходит откат всех незавершенных транзакций.

Другие возможности ARIES

Остановимся на ряде других интересных свойств ARIES. Наверное, самое изящное и простое в исполнении свойство — это поддержка вложенных заключительных действий (nested top actions, NTA).

Иногда требуется зафиксировать некоторые изменения, произведенные транзакцией над базой данных, вне зависимости от того, каким образом транзакция завершится. Такие изменения не будут отменены даже в случае отката всей транзакции. Для подобных действий требуется соблюдение свойства атомарности. В качестве примера рассмотрим транзакцию, в ходе которой требуется произвести расширение некоего файла. После расширения другие транзакции также могут добавлять данные в новую область файла, причем это может происходить еще до завершения первой транзакции. В случае отката изначальной транзакции нельзя отменять действия по расширению файла, поскольку это может привести к потере данных. При этом для самого расширения требуется поддержка свойства атомарности: в случае сбоя во время выполнения действий по расширению файла должна иметься возможность восстановить этот файл базы данных в первоначальном виде. Традиционно такого рода действия совершались путем запуска независимых транзакций, называемых заключительными действиями. При этом транзакция-инициатор ожидала завершения порожденной транзакции, перед тем как продолжить работу. Однако это связано с некоторыми неудобствами; главное из них — уязвимость этого механизма по отношению к тупикам, вовлекающим в себя как первую, так и вторую транзакции.

В ARIES используется концепция вложенных заключительных действий, позволяющая в подобных случаях обойтись без запуска независимых транзакций. Вложенное заключительное действие представляет собой последовательность действий транзакции, которая по завершению уже не подлежит отмене даже в случае отката объемлющей транзакции.

Технически организация NTA проходит в три этапа. На первом этапе запоминается номер последней журнальной записи текущей транзакции; на втором — записывается информация, необходимая для повторения и отката NTA; на третьем — записывается фиктивная компенсационная запись (dummy CLR), поле UndoNxtLSN которой указывает на запись журнала, заполненную на первом этапе. В результате, при откате этой транзакции все действия NTA будут пропущены. При этом в случае сбоя, произошедшего до окончания NTA, все действия вложенного заключительного действия будут отменены в ходе восстановления. (Описание процесса создания NTA предполагает, что все действия типа создания файла и внесения соответствующей системной информации фиксируются во внешней памяти до того, как в журнал попадает фиктивная компенсационная запись.)

Рис. 2. Схема работы NTA

Рис. 2 иллюстрирует схему работы NTA для записей журнала, созданных одной транзакцией. Записи, номера которых помечены штрихом, являются компенсационными (скажем, если 1 — запись журнала, то 1? будет для нее компенсационной). Записи 3, 4 и 5 на рисунке образуют NTA. Компенсационная запись 6? не имеет пары; это объясняется тем, что ее единственное назначение — фиксировать изменения, внесенные NTA. Далее показано, какие действия будут отменены при откате транзакции после сбоя, произошедшего после завершения NTA. Все шаги, совершенные NTA, не будут отменены, поскольку поле UndoNXT фиктивной компенсационной записи 6? указывает на запись 2.

ARIES весьма детально описывает методы работы и организации транзакций, не теряя при этом своего главного свойства — гибкости. Существует масса его разновидностей для поддержки различных типов транзакций. В качестве примера можно привести ARIES/NT (ARIES for Nested Transactions), расширение ARIES для поддержки вложенных транзакций. С его помощью можно реализовать систему, поддерживающую сложные транзакции, составной частью которых могут быть другие транзакции. При этом откат предка транзакции ведет к откату потомка, но не наоборот. Одним из отличий этого алгоритма от базового является то, что действия транзакции описываются в журнале не списком записей, а деревом записей. Это влечет за собой не только изменение структуры журнала, но и всего процесса восстановления. Также по-иному выглядит работа распределенных транзакций. (Подробнее этот алгоритм рассматривается в [5].)

Блокировки кортежей и распределение памяти

Одна из целей, которую перед собой ставили разработчики ARIES, — создание алгоритма, поддерживающего блокировки небольших объектов баз данных, таких как кортеж. Этим свойством обладали некоторые дореляционные системы, однако их основным недостатком являлось выполнение блокировок на физическом уровне. В ARIES блокировки вообще и блокировки кортежей в частности предлагается реализовывать на логическом уровне. Это означает, что при блокировке кортежа блокируется не область памяти, а некий идентификатор, который может выглядеть как (page#, slot#), где page# адресует определенную страницу базы данных, а slot# определяет место на странице, указывающее на сам кортеж.

Подобная система скрывает реальное расположение кортежей на странице. Во-первых, при таком устройстве блокировок можно производить реорганизацию данных на странице, не приостанавливая работы транзакций на ней. Во-вторых, отход от физического уровня позволяет гораздо проще организовать хранение и изменение кортежей переменной длины.

В любой СУБД, помимо собственно данных должна храниться некоторая служебная информация, помогающая ускорить процесс поиска и добавления кортежей. Если говорить о системе управления внешней памятью, то, наверное, для нее более всего нужны сведения о размере свободной памяти в страницах базы данных. Обычно каждый файл с кортежами одного или нескольких отношений содержит также несколько страниц с такой информацией — так называемых страниц учета свободной памяти (free space inventory pages, FSIP). Каждая такая страница содержит информацию, касающуюся многих страниц данных или индексов. При вставке кортежа FSIP используют для того, чтобы определить станицу данных, в которой для этого достаточно места. FSIP содержат лишь приблизительную информацию о размере свободной памяти в странице (например: в странице занято не меньше чем 30% места, 40% места и т.д.). Поэтому совсем не каждое внесение или удаление какой-либо информации в базу данных требует изменения FSIP. Для ускорения процесса восстановления все изменения FSIP должны журналироваться. Но эти журнальные записи должны обладать тем свойством, что их нельзя откатить — при откате транзакции, действия по изменению FSIP не всегда будут обратными по отношению к тем, что были произведены при прямом ее выполнении.

Отличительные свойства базового алгоритма ARIES

Подытожим обзор ARIES перечислением отличительных свойств базового алгоритма, благодаря которым он стал столь популярным.

• Поддерживаются покортежные блокировки.
• Действия, производимые во время отката транзакции, не обязательно должны быть обратными по отношению к действиям, которые были совершены при ее прямом выполнении.
• Восстановление каждой страницы базы данных может вестись независимо от других страниц. Это свойство особенно полезно при восстановлении после жесткого сбоя, когда приходится обрабатывать сразу очень много данных.
• При необходимости можно восстанавливать работу транзакций, которые не успели завершиться к моменту сбоя. Эта возможность обусловлена тем, что ARIES во время восстановления повторяет все действия транзакций, в отличие от большинства прочих систем, которые используют выборочное повторение.
• Поддерживается разделенный запуск, когда после сбоя сначала восстанавливается наиболее важная информация, к которой сразу предоставляется доступ, а восстановление прочих частей системы на время откладывается.
• Поддерживается операционная журнализация, при которой в журнале запоминаются операции (например, «прибавить к атрибуту A кортежа T число 5»), а не образы кортежей до и после внесения изменений.
• Возможны частичные откаты транзакций к заранее установленным точкам сохранения. Если во время работы транзакции требуется установить точку сохранения, то запись об этом добавляется к списку, описывающему действия транзакции. Соответственно, при откате к точке сохранения, отменяются все действия транзакции до тех пор, пока не будет достигнут маркер с именем этой точки.
• Компенсационные записи не нуждаются в откате, что позволяет избежать журнализации заведомо избыточной информации. Кроме того, можно не писать в журнал информацию, необходимую для их отката.
• Еще до завершения отката транзакции ARIES позволяет снять блокировки всех объектов, над которыми уже произведены все необходимые действия. Это может быть важно в том случае, если выполняется откат длинной транзакции или если требуется избавиться от тупика путем частичного отката одной из транзакций-участниц.
• Механизм NTA позволяет вкладывать в транзакцию действия, результат которых не будет отменен даже в случае отката транзакции.

Литература

Сергей Кузнецов (kuzloc@ispras.ru) — сотрудник ИСП РАН, Петр Чардин (cps@rc.ru) — студент факультета ВМиК МГУ.

Восстановление по ARIES

Псевдокод, иллюстрирующий процесс восстановления.

restart (masteraddr) {
restartanalysis (masteraddr, transtable,
 dirtypages, redoLSN);
restartredo (redoLSN, transtable, dirtypages);
Инициализировать системную таблицу «грязных»
 страниц данными из таблицы
dirtypages, созданной на двух первых этапах;
Удалить из этой таблицы все записи,
 соответствующие тем страницам, которые
были сброшены на диск;
restartundo (transtable);
Восстановить блокировки для транзакций,
 находившихся в состоянии prepared;
checkpoint ();
}

На стадии анализа из записей последней контрольной точки воссоздаются таблицы транзакций и грязных страниц. Еще одно значение, получаемое на этой стадии, — redoLSN, номер записи журнала, начиная с которой будут повторяться действия над базой данных во время следующего этапа восстановления. Единственный тип записей, которые добавляются в журнал на стадии анализа, — это записи о завершении откатов транзакций, которые уже завершили откат к моменту сбоя, но не успели зафиксировать этот факт в журнале.

Далее на стадии повторения просматривается журнал, и в таблицы, загруженные из записей контрольной точки, вносятся изменения. В конце этой стадии таблицы транзакций и «грязных» страниц фактически приходят в то состояние, в котором они находились на момент сбоя. После этого redoLSN вычисляется как минимум из номеров RecLSN, содержащихся в таблице «грязных» страниц.

Вообще говоря, не обязательно требуется оформлять стадию анализа в качестве отдельного прохода. Поскольку в ARIES на стадии повторения в любом случае вносятся все недостающие изменения вне зависимости от того, придется ли их потом откатывать или нет, информация, собранная во время анализа, может потребоваться лишь на этапе отмены. Поэтому стадии повторения и анализа можно совместить.

Затем системная таблица «грязных» страниц инициализируется тем вариантом таблицы, который получился в результате проделанной работы. Далее из нее удаляются записи о страницах, которые уже попали во внешнюю память. Начиная с этого момента, таблица «грязных» страниц поддерживается менеджером буферизации в автоматическом режиме. И лишь после этого происходит откат.

На этой стадии откатываются те транзакции, которые в существенной степени не успели завершиться к моменту сбоя. Откат происходит за один просмотр журнала. Номер следующей записи журнала, подлежащей откату, вычисляется как максимум из всех номеров записей, которые были созданы откатываемыми транзакциями: откат действий этих транзакций происходит в обратном хронологическом порядке.

В описанной схеме восстановление происходит в автономном режиме; пользователям СУБД придется дожидаться окончания процесса. Вполне естественно желание сократить промежуток времени после сбоя, в течение которого система недоступна. Для этого можно разделить все объекты базы данных на два класса в соответствии с их важностью. Объекты первого класса восстанавливаются в первую очередь, чтобы позволить СУБД как можно скорее инициировать новые транзакции для работы над ними; восстановление же объектов второго класса можно отложить. Такой подход поддерживается во многих алгоритмах восстановления.