3. 37. Сериализация транзакций на основе временных меток и поддержки версий объектов баз данных.

Метод временных меток.

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

Основная идея метода состоит в следующем: если транзакция Т1 началась раньше транзакции Т2, то система обеспечивает такой режим выполнения, как если бы Т1 была целиком выполнена да начала Т2.

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

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

Одним из наиболее старых и простых версионных алгоритмов является версионный вариант алгоритма временных меток (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 является отсутствие задержек и откатов при выполнении операций чтения, а основным недостатком – возможность возникновение каскадных откатов транзакций при выполнении операций записи. Кроме того, в базе данных может накапливаться произвольное число версий одного и того же объекта, и определение того, какие версии больше не требуются, является серьезной технической проблемой.