Классика баз данных - статьи
       

MVSG-планировщики


Последний рассматриваемый нами класс многоверсионных алгоритмов планирования обобщает широко известную моноверсионную технику SGT (Serialization Graph Testing). Планировщики, основанные на SGT, работают по следующему принципу.

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

  1. Если это первая операция транзакции ti, поступившая планировщику, то создается новый узел в графе сериализации.
  2. В граф добавляются дуги вида (tj, ti) для каждой запланированной ранее операции qj(x) (i ≠ j), конфликтующей с pi(x). Теперь возможны два варианта:

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

Остановимся подробнее на пункте 2a. Что означает то, что в графе появился цикл? Это означает, что полученное расписание больше не будет сериализуемым. Это утверждение становится очевидным, если заметить, что дуга из ti в tj фиксирует порядок следования транзакций в эквивалентном последовательном расписании. Т.е. результат нашего расписания должен быть таким же, как и последовательное выполнения сначала всех действий транзакции ti, а затем tj. Поскольку транзакция не может следовать раньше самой себя, граф с циклами не будет иметь соответствующего последовательного расписания.

Теперь мы можем перейти к более общему многоверсионному случаю. Cоответственно, будем рассматривать многоверсионный граф конфликтов (MVSG).

Содержание  Назад  Вперед