Базы данных. Вводный курс
Метод временных меток
Альтернативный метод сериализации транзакций, хорошо работающий в условиях редкого возникновения конфликтов транзакций и не требующий построения графа ожидания транзакций, основан на использовании временных меток. Основная идея метода временных меток (Timestamp Ordering, TO), у которого существует множество разновидностей, состоит в следующем: если транзакция T1
началась раньше транзакции T2, то система обеспечивает такой сериальный план, как если бы транзакция T1
была целиком выполнена до начала T2.
Для этого каждой транзакции T
предписывается временная метка t(T), соответствующая времени начала выполнения транзакции T. При выполнении операции над объектом o
транзакция T
помечает его своими идентификатором, временной меткой и типом операции (чтение или изменение).
Перед выполнением операции над объектом o
транзакция T2
выполняет следующие действия:
- Проверяет, помечен ли объект o
какой-либо транзакцией T1. Если не помечен, то помечает этот объект своей временной меткой и типом операции и выполняет операцию. Конец действий.
- Иначе транзакция T2
проверяет, не завершилась ли транзакция T1, пометившая этот объект. Если транзакция T1
закончилась, то T2
помечает объект o
и выполняет свою операцию. Конец действий.
- Если транзакция T1
не завершилась, то T2
проверяет конфликтность операций. Если операции неконфликтны, то при объекте o
запоминается идентификатор транзакции T2, остается или проставляется временная метка с меньшим значением, и транзакция T2
выполняет свою операцию.
- Если операции транзакций T2
и T1
конфликтуют, то если t(T1) > t(T2)
(т.е. транзакция T1
является более «молодой», чем T2), то производится откат T1
и всех других транзакций, идентификаторы которых сохранены при объекте o, и T2
выполняет свою операцию.
- Если же t(T1) < t(T2)
(T1
«старше» T2), то производится откат T2; T2
получает новую временную метку и начинается заново.
К недостаткам метода TO относятся потенциально более частые откаты транзакций, чем в случае использования синхронизационных захватов. Это связано с тем, что конфликтность транзакций определяется более грубо. Кроме того, в распределенных системах не очень просто вырабатывать глобальные временные метки с отношением полного порядка (это отдельная большая наука).
Но в распределенных системах эти недостатки окупаются тем, что не нужно распознавать тупики, а как мы уже отмечали, построение графа ожидания в распределенных системах стоит очень дорого.
