2008 г.

Базы данных. Вводный курс

Сергей Кузнецов

13.3.4. Методы сериализации транзакций на основе поддержки версий объектов базы данных

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

Алгоритмы управления транзакциями, основанные на поддержке версий, достаточно широко распространены в области SQL-ориентированных СУБД. В частности, подобные алгоритмы используются в СУБД Oracle и PostgreSQL. В дальнейшем в этом подразделе будем называть алгоритмы этой категории версионными алгоритмами.

Версионный вариант алгоритма временных меток

Одним из наиболее старых и простых версионных алгоритмов является версионный вариант алгоритма временных меток (Multiversion Timestamp Ordering, MVTO). Как и в простом методе временных меток, описанном в предыдущем подразделе, в алгоритме MVTO порядок выполнения операций одновременно выполняемых транзакций задается порядком временных меток, которые получают транзакции во время старта. Временные метки также используются для идентификации версий данных при чтении и модификации – каждая версия получает временную метку той транзакции, которая ее записала. Алгоритм MVTO не только следит за порядком выполнения операций транзакций, но также отвечает за трансформацию операций над объектами базы данных в операции над версиями этих объектов, т.е. каждая операция над объектом базы данных o преобразуется в соответствующую операцию над некоторой версией объекта o.

При описании алгоритма будем использовать следующие обозначения. Как и раньше, временную метку, полученную транзакцией T_i в начале ее работы, будем обозначать как t(T_i). Операция чтения объекта базы данных o, выполняемая в транзакции T_i, будет обозначаться как R_i(o). Для обозначения того, что транзакция T_i читает версию объекта базы данных o, созданную транзакцией T_k, будем использовать запись R_i(o_k). Для обозначения того, что транзакция T_i записывает версию элемента данных o, будем использовать запись W_i(o_i).

Алгоритм MVTO работает следующим образом.

Любая операция R_i(o) преобразуется в операцию R_i(o_k), где o_k – это версия объекта o, помеченная наибольшей временной меткой t(T_k), такой что t(T_k) t(T_i). Другими словами, транзакции T_i для чтения дается версия объекта o, созданная транзакцией T_k, которая не моложе T_i, но старше любой другой транзакции T_n, создававшей свою версию объекта o.
При обработке операции W_i(o) выполняются следующие действия:
- если к этому времени некоторой незафиксированной транзакцией T_n уже выполнена некоторая операция R_n(o_k), такая что t(T_k) t(T_i) < t(T_n), то операция W_i(o) не выполняется, а транзакция T_i откатывается;
- в противном случае W_i(o) преобразуется в W_i(o_i), т.е. образуется еще одна версия объекта o.
При откате любой транзакции уничтожаются все созданные ею версии объектов базы данных и откатываются все транзакции, прочитавшие хотя бы одну из этих версий. Тем самым, откаты транзакций могут быть «каскадными».
Выполнение операции фиксации транзакции T_i (COMMIT) откладывается до того момента, когда завершатся все транзакции, записавшие версии данных, прочитанные T_i. Легко видеть, что без соблюдения этого требования не соблюдалось бы свойство долговечности (durability) транзакций, поскольку при откате некоторых транзакций потребовалось бы откатывать и ранее зафиксированные транзакции.

Преимущества алгоритма MVTO лучше всего иллюстрируются поведением транзакций T₁ и T₂ (см. рис. 13.8). При использовании блокировок между ними возник бы синхронизационный тупик, а при использовании обычного метода временных меток одна из транзакций подверглась бы откату. Однако при применении версий такие неприятности не возникают из-за того, что первая транзакция читает «старые» версии объектов o и ω.

Рис. 13.8. Пример работы алгоритма MVTO

Транзакция T₃ ожидает фиксации транзакции T₂ перед своим собственным завершением (на рис. 13.8 это показано пунктирной линией). Это происходит потому, что транзакция T₃ прочитала версию o₂ объекта o, образованную еще не зафиксированной транзакцией.

Транзакция T₄ пытается создать версию ω₄ объекта ω после того, как еще не зафиксированная транзакция T₅ (начавшаяся позже) уже прочитала более раннюю версию ω₄. Поэтому транзакция T₅ не сможет «увидеть» изменения объекта ω, произведенные транзакцией T₄. Следовательно, сериализация транзакций в порядке получения ими временных меток становится невозможной, и приходится произвести откат транзакции T₄.

Итак, основными преимуществами алгоритма MVTO является отсутствие задержек и откатов при выполнении операций чтения, а основным недостатком – возможность возникновение каскадных откатов транзакций при выполнении операций записи. Кроме того, в базе данных может накапливаться произвольное число версий одного и того же объекта, и определение того, какие версии больше не требуются, является серьезной технической проблемой.

Версионный вариант двухфазного протокола синхронизационных блокировок

При описании двухверсионного варианта протокола 2PL (Two-Version Two-Phase Locking Protocol, 2V2PL) будем называть текущими версиями объектов базы данных версии, созданные зафиксированными транзакциями с наиболее поздним временем фиксации; незафиксированными версиями – версии, созданные еще незавершившимися транзакциями. При следовании протоколу 2V2PL в каждый момент времени существует не более одной незафиксированной версии каждого объекта базы данных.

Операции любой транзакции T_i над объектом базы данных o обрабатываются следующим образом:

операция R_i(o) немедленно выполняется над текущей версией объекта o;
операция W_i(o), приводящая к созданию новой версии объекта o, выполняется только после завершения (фиксации или отката) транзакции, создавшей незафиксированную версию объекта o;
выполнение операции COMMIT откладывается до тех пор, пока не завершатся все транзакции T_k, прочитавшие текущие версии объектов базы данных, которые должны замениться незафиксированными версиями этих объектов, созданными транзакцией T_i.

Для реализации такого поведения используются три типа блокировок:

RL (Read Lock) – в этом режиме блокируется любой объект базы данных o перед выполнением операции чтения его текущей версии; удержание этой блокировки до конца транзакции гарантирует, что при повторном чтении объекта o будет прочитана та же версия этого объекта;
WL (Write Lock) – в этом режиме блокируется любой объект базы данных o перед выполнением операции, приводящей к созданию новой (незафиксированной) версии этого объекта; удержание этой блокировки до конца транзакции гарантирует, что в любой момент времени будет существовать не более одной незафиксированной версии любого объекта базы данных;
CL (Commit Lock) – блокировка устанавливается во время выполнения операции COMMIT транзакции и затрагивает любой объект базы данных, новую версию которого создала данная транзакция; удовлетворение этой блокировки для данной транзакции гарантирует, что завершились все транзакции, читавшие текущие версии объектов, новые версии которых были созданы при выполнении данной транзакции, и, следовательно, их можно заменить.

В таб. 13.3 показаны правила совместимости этих блокировок.

Таблица 9.3. Таблица совместимости «версионных» блокировок

RL(o) WL(o) CL(o)

RL(o) да да нет

WL(o) да нет нет

CL(o) нет нет нет

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

Версионно-блокировочный протокол сериализации транзакций для поддержки только читающих транзакций

В заключение обсудим гибридный протокол, поддерживающий эффективное выполнение транзакций, не изменяющих состояние базы данных (Multiversion Protocol for Read-Only Transactions, ROMV). При применении этого протокола при образовании каждой транзакции явно указывается ее тип – только читающая (read-only) или изменяющая (update) транзакция. В только читающих транзакциях допускается использование только операций чтения объектов базы данных, а в изменяющих транзакциях – операций и чтения, и записи.

Изменяющие транзакции выполняются в соответствии с обычным протоколом 2PL, т.е. перед выполнением операции чтения или записи объекта базы данных o этот объект должен быть заблокирован в режиме S или X соответственно, и блокировки объектов удерживаются до конца изменяющей транзакции. Каждая операции записи объекта o создает его новую версию, которая при завершении транзакции помечается временной меткой, соответствующей моменту фиксации этой транзакции.

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

Основным плюсом протокола ROMV по сравнению с ранее описанным протоколом 2V2PL является принципиальное отсутствие синхронизационных задержек при выполнении операций чтения только читающих транзакций. Если сравнивать ROMV с MVTO, то он выигрывает в принципиальном отсутствии откатов только читающих транзакций. Конечно, при работе изменяющих транзакций возможно возникновение синхронизационных тупиков и откатов, и здесь требуется использовать обычные методы распознавания и разрушения тупиков.

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

13.4. Заключение

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

В лекции описаны два основных подхода к сериализации транзакций – на основе синхронизационных блокировок и временных меток. У каждого из этих подходов имеются свои достоинства и недостатки, но на практике существенно больше распространен метод синхронизационных блокировок. В заключение лекции были рассмотрены расширения этих подходов с применением версий объектов базы данных. Соответствующие алгоритмы и протоколы позволяют уменьшить число потенциальных конфликтов транзакций, но для их поддержки требуются дополнительные расходы внешней памяти и усложнение общей архитектуры СУБД.

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