Оптимистические технологии управления транзакциями

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

Перед завершением выполнения транзакции выполняется проверка с целью определения, имел ли место конфликт. Если конфликт найден, то транзакция отменяется и перезапускается.

Оптимистический протокол управления параллельностью включает три фазы:

1 Фаза чтения. Она охватывает транзакцию от ее начала и вплоть до момента фиксации результатов. Транзакция считывает значения всех необходимых элементов и помещает из в локальные переменные. Любые обновления применяются только к локальной копии данных, но не к информации в основной БД.

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

3 Фаза записи. Эта фаза выполняется для транзакций, обновляющих данные. Она заключается в перенесении изменений локальных переменных в основную БД.

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

Часто множества элементов, с которыми работают транзакции, можно рассматривать как иерархические структуры. Два основных типа иерархических структур:

1 Узлы В-деревьев.

2 Большинство элементов данных могут рассматриваться как составные части большего элемента. В связи с этим в БД можно выделить четыре уровня иерархии: а) БД в целом, б) отношение БД, в) блок, на который разбита база при хранении файла г) кортеж.

Существует два вида политики при обеспечении параллельного доступа к иерархическим структурам

1 При блокировании элемента не происходит блокирования ни каких других элементов. Эта политика присуща иерархическим структурам первого типа.

2 При блокировании элемента блокируются все его потомки. Характерна для структур второго типа.

Простой протокол для иерархических структур

Автор: Administrator
Будем рассматривать простую модель транзакций, учитывающую операторы Lock и Unlock.   При этом реализуется первый вид политики блокирования иерархических структур. Для таких транзакций используется следующий протокол. /*Протокол – ограничения на шаги транзакции */. 1 Никакой элемент не должен блокироваться раньше, чем будет заблокирован его родитель. Исключение составляет только корень дерева. 2 Ни один элемент не блокируется дважды одной и то же транзакцией. При этом транзакция, следующая этому протоколу, не обязана быть двухфазной. Рассмотрим пример. При использовании политики первого вида и простого протокола возможны следующие действия. Заблокировать элемент А. Затем заблокировать элемент В, являющийся потомком А. Если описываемая ситуация характеризует вставку новой записи в В-дерево, то необходимо проверить есть ли в блоке В свободное место для нового элемента. Если такое В позволяет вставку без реструктуризации дерева, то возможно разблокировать элемент А. При этом появляется возможность блокировать А и потомков А, но не В. /*Преимущество политики */. Можно доказать, что если транзакции плана следуют простому протоколу для иерархической структуры, то план сериализуем. Предположим, что Ti и Tj – транзакции, блокирующие один и тот же элемент. /* Естественно в разное время. */. Обозначим черезFIRST(T) – первый элемент, который блокируется транзакцией Т. Если элементы First(Ti) и First(Tj) не зависимы, то есть ни один из них не является потомком другого, то протокол гарантирует, чтоTi и Tj не будут блокировать элемент совместно, а следовательно в графе не нужно строить соответствующей дуги. Рассмотрим ситуацию, когда first(Ti) – предок first(Tj). Если Ti блокируетfirst(Tj) прежде, чем это выполняет Tj, то строится дуга Ti? Tj. Иначе строится дуга Tj? Ti. Такой граф не будет иметь циклов. Каждая транзакция имеет границу из по нижним заблокированным узлам, а протокол гарантирует, что границы транзакций не пересекаются. Если граница Ti начинает пересекаться с границей Tj, то это происходит по элементам, которые блокируются обеими транзакциями, но это не приводит к конфликтам, так как такие элементы транзакция Ti всегда блокирует первой. Пример.   Lock A       Lock B       Lock D       Unlock B         Lock B     Lock C           Lock E   Unlock D           Lock F   Unlock A           Lock G   Unlock C           Unlock E     Lock E         Unlock F     Unlock B         Unlock G     Unlock E   /*Обратите внимание на следование транзакций протоколу для иерархической структуры, Т1 – не двухфазная. Граф строим по изложенной выше методике, граф не имеет циклов, учитывая firstвсех транзакций. */
Протокол блокирования поддеревьев

Автор: Administrator

Рассмотрим второй вид политики блокирования иерархических структур.   В этом случае рассматриваемая структура имеет вид База данных-> отношения -> блоки -> Записи. Преимущество такой политики состоит в том, что вместо блокирования многих маленьких элементов данных (кортежей, например), можно заблокировать один большой (отношение, например). Это экономит время на блокирование и разблокирование. Проблема, с которой может столкнуться такая модель. Пусть Т1 блокирует элемент Е. Это приведет к блокированию элементов F иG. Если затем транзакции T2 потребуется блокировать элемент B. Это возможно, так как он не блокирован. Установка такой блокировки потребует блокирования элементов D, E, F, G. В результате появился конфликт. Поэтому в протокол блокирования поддеревьев вводится новое понятие “Предупреждение” (warning). Теперь, если транзакция устанавливает блокировку на элемент, то должны установить предупреждения на всех потомков узла. Установка предупреждения на элемент А, предотвращает блокирование этого элемента другими транзакциями, но позволяет им установить предупреждение на тот же элемент для установки блокировок на тех потомков А, на которые еще не было установлено ни блокировок, ни предупреждений. Матрица совместимости предупреждений и блокировок.   W L W Y N L N N Протокол блокирования поддеревьев накладывает на транзакции следующие ограничения: 1 Начинаться транзакция должна с блокирования или установки предупреждения на корень дерева. 2 Не должно осуществляться блокирования элемента или установки предупреждения на элемент без установки предупреждения на всех предков элемента. 3 Не должно происходить снятия блокировки или предупреждения с элемента, если он имеет хотя бы одного потомка, на которого установлена блокировка или предупреждение. 4 Все транзакции должны следовать двухфазному протоколу в следующем прочтении: «Все блокировки и предупреждения транзакции должны предшествовать разблокированию» Пример плана, транзакции которого следуют протоколу блокирования поддеревьев. Т1: (1) warn A; (4) warn B; (6) Lock D; (8) Unlock D; (10) Unlock B; (14) Unlock A T2: (2) warn A; (5) Lock C; (7) Unlock C; (9) Unlock A T3: (3) warn A; (11) Lock B; (12) warn C; (13) Lock F; (15) Unlock B; (16) Unlock B; (17) Unlock C; (18) Unlock A;