Разрушение тупиков

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

Выбрать «жертву» не так уж легко, поскольку для этого могут использоваться различные, зачастую противоречивые критерии. С одной стороны, было бы разумно жертвовать наиболее «богатой» транзакцией, т.е. той транзакцией, которая удерживает наиболее число блокировок объектов. В этом случае после принудительно завершения такой транзакции освободилось бы наибольшее число объектов, что с большой вероятностью привело бы к исчезновению тупиковой ситуации. Но, с другой стороны, «богатая» транзакция, скорее всего, выполнялась дольше других транзакций. На ее выполнение уже затрачено большое количество системных ресурсов и, вероятно, она скоро завершится самостоятельно. Поэтому этот выбор может оказаться в системном отношении не самым удачным.

Рис. 13.7.Применение алгоритма редукции к графу ожидания транзакций

Можно пожертвовать самой «молодой» транзакцией, которая существует в системе в течение наименьшего времени. Такую транзакцию менее всего жалко, поскольку она еще не успела израсходовать много системных ресурсов. Но, с другой стороны, такая транзакция не могла и накопить много блокировок, и поэтому ее насильственное завершение вряд ли поможет устранить тупиковую ситуацию. Так стоит ли ею жертвовать?

Можно выбрать транзакцию-жертву случайным образом из всех транзакций, попавших в тупик. Возможно, что в среднем этот подход привел бы к хорошим результатам. Но, к сожалению, в нем не учитывается возможная приоритетность транзакций. Было бы не слишком хорошо, например, жертвовать транзакцией, запущенной от имени руководителя организации.

Поэтому обычно при выборе транзакции-жертвы используется многофакторная оценка ее стоимости, в которую с разными весами входят время выполнения, число накопленных блокировок, приоритет и т.д. В качестве «жертвы» выбирает транзакция, для которой эта оценка выдает наиболее подходящий результат.

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

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

Заметим, что в централизованных системах стоимость построения графа ожидания сравнительно невелика, но она становится слишком большой в распределенных СУБД, в которых транзакции могут выполняться в разных узлах сети. Поэтому в таких системах обычно используются другие методы сериализации транзакций.

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

Альтернативный метод сериализации транзакций, хорошо работающий в условиях редкого возникновения конфликтов транзакций и не требующий построения графа ожидания транзакций, основан на использовании временных меток. Основная идея метода временных меток (Timestamp Ordering, TO), у которого существует множество разновидностей, состоит в следующем: если транзакцияT₁началась раньше транзакцииT₂, то система обеспечивает такой сериальный план, как если бы транзакцияT₁была целиком выполнена до началаT₂.

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

Перед выполнением операции над объектом oтранзакцияT₂выполняет следующие действия:

• Проверяет, помечен ли объект oкакой-либо транзакциейT₁. Если не помечен, то помечает этот объект своей временной меткой и типом операции и выполняет операцию. Конец действий.

• Иначе транзакция T₂проверяет, не завершилась ли транзакцияT₁, пометившая этот объект. Если транзакцияT₁закончилась, тоT₂помечает объектoи выполняет свою операцию. Конец действий.

• Если транзакция T₁не завершилась, тоT₂проверяет конфликтность операций. Если операции неконфликтны, то при объектеoзапоминается идентификатор транзакцииT₂, остается или проставляется временная метка с меньшим значением, и транзакцияT₂выполняет свою операцию.

• Если операции транзакций T₂иT₁конфликтуют, то еслиt(T₁) > t(T₂)(т.е. транзакцияT₁является более «молодой», чемT₂), то производится откатT₁и всех других транзакций, идентификаторы которых сохранены при объектеo, иT₂выполняет свою операцию.

• Если же t(T₁) < t(T₂)(T₁«старше»T₂), то производится откатT₂;T₂получает новую временную метку и начинается заново.

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

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