В компьютерной науке алгоритмы восстановления и изоляции, эксплуатирующие семантику , или ARIES , представляют собой алгоритм восстановления, разработанный для работы с подходом к базе данных без применения силы и кражи; он используется в IBM Db2 , Microsoft SQL Server и многих других системах баз данных . [1] Доктор наук , научный сотрудник IBM, является основным изобретателем семейства алгоритмов ARIES. [2]
В основе ОВНА лежат три основных принципа:
Алгоритм ARIES основан на регистрации всех операций с базой данных с возрастающими порядковыми номерами. Обычно полученный файл журнала хранится на так называемом «стабильном хранилище», то есть на носителе данных, который, как предполагается, выдерживает сбои и отказы оборудования.
Чтобы собрать необходимую информацию для журналов, необходимо поддерживать две структуры данных : таблицу грязных страниц (DPT) и таблицу транзакций (TT).
Таблица грязных страниц хранит записи всех страниц, которые были изменены и еще не записаны на диск, и первый порядковый номер, который привел к тому, что эта страница стала грязной. Таблица транзакций содержит все текущие запущенные транзакции и порядковый номер последней записи журнала, которую они создали.
Мы создаем записи журнала в форме (Порядковый номер, Идентификатор транзакции, Идентификатор страницы, Повторить, Отменить, Предыдущий порядковый номер). Поля Повторить и Отменить содержат информацию об изменениях, которые эта запись журнала сохраняет, и о том, как их отменить. Предыдущий порядковый номер — это ссылка на предыдущую запись журнала, которая была создана для этой транзакции. В случае прерванной транзакции можно просмотреть файл журнала в обратном порядке, используя Предыдущие порядковые номера, отменяя все действия, выполненные в рамках конкретной транзакции.
Каждая транзакция неявно начинается с первой записи типа «Обновление» для данного идентификатора транзакции и фиксируется записью «Конец журнала» (EOL) для транзакции.
Во время восстановления или отмены действий прерванной транзакции записывается специальный тип записи журнала, запись журнала компенсации (CLR), чтобы зафиксировать, что действие уже было отменено. CLR имеют форму (порядковый номер, идентификатор транзакции, идентификатор страницы, повтор, предыдущий порядковый номер, следующий порядковый номер отмены). Поле повтора содержит применение поля отмены отмененного действия, а поле отмены опущено, поскольку CLR никогда не отменяется.
Восстановление работает в три фазы. Первая фаза, Анализ, вычисляет всю необходимую информацию из файла журнала. Фаза Повтора восстанавливает базу данных до точного состояния на момент сбоя, включая все изменения незафиксированных транзакций, которые выполнялись в тот момент времени. Затем фаза Отмены отменяет все незафиксированные изменения, оставляя базу данных в согласованном состоянии.
На этапе анализа мы восстанавливаем DPT и TT такими, какими они были на момент сбоя.
Мы просматриваем файл журнала (с начала или последней контрольной точки) и добавляем все транзакции, для которых мы встречаем записи Begin Transaction в TT. Всякий раз, когда находится запись End Log, соответствующая транзакция удаляется. Последний порядковый номер для каждой транзакции также сохраняется.
В течение того же запуска мы также заполняем таблицу грязных страниц, добавляя новую запись всякий раз, когда сталкиваемся со страницей, которая была изменена и еще не находится в DPT. Однако это вычисляет только надмножество всех грязных страниц на момент сбоя, поскольку мы не проверяем фактический файл базы данных, была ли страница записана обратно в хранилище.
Из DPT мы можем вычислить минимальный порядковый номер грязной страницы. Оттуда мы должны начать повторять действия до сбоя, если они еще не были сохранены.
Просматривая файл журнала, мы проверяем для каждой записи, существует ли измененная страница P в записи в DPT. Если ее нет, то нам не нужно беспокоиться о повторной записи, так как данные сохраняются на диске. Если страница P существует в таблице DPT, то мы смотрим, меньше ли порядковый номер в DPT порядкового номера записи журнала (т. е. является ли изменение в журнале более новым, чем последняя сохраненная версия). Если это не так, то мы не повторяем запись, так как изменение уже есть. Если это так, мы извлекаем страницу из хранилища базы данных и сравниваем порядковый номер, сохраненный на странице, с порядковым номером в записи журнала. Если первый меньше второго, страницу необходимо записать на диск. Эта проверка необходима, так как восстановленный DPT является лишь консервативным надмножеством страниц, которые действительно нуждаются в повторном применении изменений. Наконец, когда все вышеуказанные проверки завершены и не пройдены, мы повторно применяем действие повтора и сохраняем новый номер последовательности на странице. Это также важно для восстановления после сбоя во время фазы повтора, поскольку повтор не применяется дважды к одной и той же странице.
После фазы Redo база данных отражает точное состояние на момент сбоя. Однако изменения незафиксированных транзакций должны быть отменены, чтобы восстановить базу данных до согласованного состояния.
Для этого мы проходим в обратном направлении по журналу для каждой транзакции в TT (конечно, эти прогоны можно объединить в один), используя поля Previous Sequence Number в записях. Для каждой записи мы отменяем изменения (используя информацию в поле Undo) и записываем запись журнала компенсации в файл журнала. Если мы сталкиваемся с записью Begin Transaction, мы записываем запись End Log для этой транзакции.
Записи журнала компенсации позволяют восстановиться во время сбоя, который происходит на этапе восстановления. Это не так уж и редко, как можно подумать, поскольку этап восстановления может занять довольно много времени. CLR считываются на этапе анализа и переделываются на этапе повтора.
Чтобы избежать повторного сканирования всего файла журнала во время фазы анализа, рекомендуется регулярно сохранять DPT и TT в файл журнала, формируя контрольную точку. Вместо того, чтобы проходить по всему файлу, необходимо просто пройти назад, пока не будет найдена контрольная точка. С этой точки можно восстановить DPT и TT такими, какими они были на момент сбоя, снова прочитав файл журнала вперед. Затем можно продолжить как обычно с помощью Redo и Undo.
Наивный способ создания контрольной точки заключается в блокировке всей базы данных, чтобы избежать изменений в DPT и TT во время создания контрольной точки. Нечеткое журналирование обходит это, записывая две записи журнала. Одна запись Fuzzy Log Starts Here и, после подготовки данных контрольной точки, фактическая контрольная точка. Между двумя записями могут быть созданы другие записи журнала. Во время восстановления необходимо найти обе записи, чтобы получить допустимую контрольную точку.