Механизм теневых страниц

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 18:47, 31 мая 2016.

Механизм теневых страниц по существу является усовершенствованием техники теневого копирования. При определенных обстоятельствах для механизма теневых страниц может потребоваться меньше обращений к диску, чем для метода на основе журнала.[1] Есть, однако, недостатки механизма теневых страниц, которые ограничивают его использование. Например, трудно расширить механизм теневых страниц, чтобы позволить нескольким транзакциям выполняться одновременно.

Как это работает?

Рисунок 1. Пример таблицы страниц.

База данных разбивается на некоторое количество блоков фиксированной длины, которые называются страницами. Термин страниц заимствован из операционных систем, так как мы используем схему подкачки для управления памятью. Предположим, что есть страниц, пронумерованных от до . (На практике, может быть в сотнями тысяч.) Эти страницы не нужно хранить в определенном порядке на диске. Тем не менее, должен быть способ найти -ую страницу базы данных для любого . Мы используем таблицы страниц, как показано на Рисунке 1, для этих целей. Таблица страниц имеет записей — по одной на каждую страницу. Каждая запись содержит указатель на страницу на диске. Первая запись содержит указатель на первую страницу базы данных, вторая — на вторую, и так далее. В примере на рисунке 1 показано, что логический порядок страниц базы данных не обязательно соответствует физическому порядку, в котором страницы помещаются на диске.

Ключевая идея

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

Алгоритм

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

  1. Если -я страница (то есть страница, на которой расположена ) уже не в оперативной памяти, тогда система выдаёт .
  2. Если эта запись впервые выполняется на -й странице во время этой транзакции, то система изменяет текущую таблицу страниц следующим образом:
    • Находит неиспользуемую страницу на диске. Обычно, СУБД имеет доступ к списку неиспользуемых (свободных) страниц.
    • Удаляет страницу, найденную на предыдущем шаге, из списка свободных страниц, затем копирует содержимое -й страницы на страницу, найденную на предыдущем шаге.
    • Изменяет текущую таблицу страниц таким образом, что -я запись указывает на страницу, найденную на шаге 2a.
  3. Присваивает значение объекту на буферной странице.
Рисунок 2. Теневая и текущая страницы таблиц.

На рисунке 2 показаны теневая и текущая таблицы страниц для транзакции, выполняющей запись на четвертой странице базы данных, состоящей из 10 страниц.

Аналогия с веб-страницами

Предположим, вам нужно отредактировать веб-страницу на вашем сайте (page.html), чтобы внести серьезные изменения в дизайн и содержание.[2] Естественно, вы обеспокоены тем, что если люди посетят страницу в то время, как вы работаете с ней, то они увидят кривую разметку.

Решение заключается в том, чтобы сделать копию веб-страницы с новым именем (например, page2.html), и редактировать этот новый файл. В этом случае можно не беспокоиться о качестве отдаваемой страницы, внести все изменения и проверить, как выглядит обновленная страница.

Когда вы полностью закончили с правками, вы переименовываете файлы таким образом, чтобы первый файл получил имя page.old.html, а отредактированный файл - page.html.

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

Цель такого подхода заключается в сохранении исходной страницы на случай возникновения ошибок при обновлении.

Применение к восстановлению

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

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

Преимущества[3]

  • Отсутствие накладных расходов на запись логов.
  • Отсутствие алгоритма отмены/повтора операций.
  • Более быстрое восстановление.

Недостатки

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

Ссылки

  1. http://database-management-system-course.blogspot.ru/2015/05/concurrency-controlshadow-paging.html
  2. https://www.quora.com/What-is-shadow-paging-in-dbms
  3. http://dbms-ii.blogspot.ru/2010/03/shadow-paging.html