Алгоритмы восстановления и изоляции, использующие семантику - Algorithms for Recovery and Isolation Exploiting Semantics

В Информатика, Алгоритмы восстановления и изоляции, использующие семантику, или же ОВЕН это восстановление алгоритм предназначен для работы с без силы, украсть подход к базе данных; он используется IBM DB2, Microsoft SQL Server и многие другие системы баз данных.[1] Сотрудник IBM Доктор К. Мохан является основным изобретателем семейства алгоритмов ARIES.[2]

В основе ОВЕНА лежат три основных принципа

  • Ведение журнала с упреждающей записью: Любое изменение объекта сначала записывается в бревно, и журнал должен быть записан в стабильное хранилище, прежде чем изменения объекта будут записаны на диск.
  • Повторение истории во время Redo: При перезапуске после сбоя, ОВЕН отслеживает действия базы данных до сбоя и возвращает систему в то состояние, в котором она находилась до сбоя. Затем он отменяет транзакции, все еще активные во время сбоя.
  • Ведение журнала изменений во время отмены: Изменения, внесенные в базу данных при отмене транзакций, регистрируются, чтобы гарантировать, что такое действие не повторится в случае повторных перезапусков.

логирование

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

Обычно результирующий файл журнала сохраняется в так называемом «стабильном хранилище», то есть на носителе, который, как предполагается, выдерживает сбои и отказы оборудования. Для сбора необходимой информации для регистрации два структуры данных должны поддерживаться: таблица грязных страниц (DPT) и таблица транзакций (TT).

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

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

Каждая транзакция неявно начинается с записи первого типа «Обновление» для данного идентификатора транзакции и фиксируется записью «Конец журнала» (EOL) для транзакции.

Во время восстановления или отмены действий прерванной транзакции записывается специальный вид записи журнала, Compensation Log Record (CLR), для записи того, что действие уже было отменено. CLR имеют форму (порядковый номер, идентификатор транзакции, идентификатор страницы, повтор, предыдущий порядковый номер, следующий порядковый номер отмены). Поле «Повторить» содержит применение поля «Отменить» для отмененного действия, а поле «Отменить» опущено, поскольку CLR никогда не возвращается.

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

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

Анализ

На этапе анализа мы восстанавливаем DPT и TT в том виде, в котором они были на момент аварии.

Мы просматриваем файл журнала (с начала или с последней контрольной точки) и добавляем все транзакции, для которых мы встречаем записи Begin Transaction, в TT. Всякий раз, когда обнаруживается запись End Log, соответствующая транзакция удаляется. Конечно, также сохраняется последний порядковый номер для каждой транзакции.

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

Повторить

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

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

Отменить

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

Для этого мы пробегаем назад по журналу для каждой транзакции в TT (эти прогоны, конечно, можно объединить в один), используя поля Предыдущий порядковый номер в записях. Для каждой записи мы отменяем изменения (используя информацию в поле «Отменить») и записываем запись журнала компенсации в файл журнала. Если мы сталкиваемся с записью начала транзакции, мы пишем запись в конце журнала для этой транзакции.

Записи журнала компенсации позволяют восстанавливать систему во время сбоя, произошедшего на этапе восстановления. Это не так уж редко, как можно было бы подумать, поскольку фаза восстановления может занять довольно много времени. CLR считываются во время фазы анализа и переделываются во время фазы повтора.

Контрольно-пропускные пункты

Чтобы избежать повторного сканирования всего файла журнала на этапе анализа, рекомендуется регулярно сохранять DPT и TT в файл журнала, образуя контрольную точку. Вместо того, чтобы проходить через весь файл, просто нужно бегать назад, пока не будет найдена контрольная точка. С этого момента можно восстановить DPT и TT такими, какими они были во время сбоя, путем повторного чтения файла журнала. Затем можно продолжить, как обычно, с помощью Redo и Undo.

Наивный способ контрольно-пропускной пункт включает блокировку всей базы данных, чтобы избежать изменений DPT и TT во время создания контрольной точки. Нечеткое ведение журнала позволяет обойти это, записывая две записи журнала. Здесь начинается один нечеткий журнал записи, а после подготовки данных контрольной точки - фактическая контрольная точка. Между двумя записями могут быть созданы другие записи журнала. Во время восстановления необходимо найти обе записи, чтобы получить действительную контрольную точку.

Рекомендации

  1. ^ Mohan, C .; Хадерле, Дональд; Линдси, Брюс; Пирахеш, Хамид; Шварц, Питер (март 1992 г.). «ОВЕН: метод восстановления транзакций, поддерживающий блокировку с высокой степенью детализации и частичный откат с использованием ведения журнала с упреждающей записью». Транзакции ACM в системах баз данных. 17 (1): 94–162. Дои:10.1145/128765.128770.
  2. ^ "Повторение истории за пределами ОВЕНА" (PDF). К. Мохан, Труды 25-й Международной конференции по очень большим базам данных, Эдинбург, Великобритания, сентябрь 1999 г.

внешняя ссылка