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


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


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

Но в распределенных системах эти недостатки окупаются тем, что не нужно распознавать тупики, а как мы уже отмечали, построение графа ожидания в распределенных системах стоит очень дорого.




Начало  Назад  Вперед



Книжный магазин