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

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

Основная идея метода (у которого существует множество разновидностей) состоит в следующем: если транзакция T1 началась раньше транзакции T2, то система обеспечивает такой режим выполнения, как если бы T1 была целиком выполнена до начала T2. Для этого каждой транзакции T предписывается временная метка t, соответствующая времени начала T. При выполнении операции над объектом r транзакция T помечает его своей временной меткой и типом операции (чтение или изменение).

Перед выполнением операции над объектом r транзакция T2 выполняет следующие действия (алгоритм см. на Рис. 29):

• Проверяет, не закончилась ли транзакция T1, пометившая этот объект. Если T1 закончилась, T2 помечает объект r и выполняет свою операцию.

• Если транзакция T1 не завершилась, то T2 проверяет конфликтность операций. Если операции неконфликтны, при объекте r остается или проставляется временная метка с меньшим значением, и транзакция T2 выполняет свою операцию.

• Если операции T2 и T1 конфликтуют, то если t(T1) > t(T2) (т.е. транзакция T1 является более "молодой", чем T2), производится откат T1 и T2 продолжает работу.

• Если же t(T1) < t(T2) (T1 "старше" T2), то T2 получает новую временную метку и начинается заново.

Рис. 29. Алгоритм метода временных меток

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

Д/З 9. Для примера из Д/З 4 придумайте транзакцию с немедленно проверяемой целостностью и отложенной проверкой. Для транзакции из Д/З 1 с конфликтом пользователей проанализируйте 1,2,3 уровень изолированности пользователей (то есть более подробно распишите, какие возникают проблемы) и последствия появления кортежей-фантомов.

Подробнее о транзакциях см. [1].

Вопросы для самопроверки:

1. Чем различаются второй и третий уровни изолированности транзакций?

2. В каком из методов сериализации возможны тупики?

3. Какой из методов сериализации более выгоден в условиях редких конфликтов?