Главная | Обратная связь

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

Основная идея алгоритмов сериализации транзакций, описываемых в этом разделе, состоит в том, что в базе данных допускается существование нескольких «версий» одного и того же объекта. Эти алгоритмы, главным образом, направлены на преодоление конфликтов транзакций категорий 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 и ω.

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

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

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

Рис. 13.8. Пример работы алгоритма 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. Таблица совместимости «версионных» блокировок

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