Протоколы управления транзакциями в СУБД реального времени

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

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

Формально различие между типами директивных сроков можно описать при помощи функции полезности транзакции в зависимости от времени завершения. На рисунке 4.9.1 показан вид этой функции для всех трех типов систем.

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

Рисунок 4.9.1 – Функция полезности для систем с мягкими, крепкими и жесткими директивными сроками

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

Способы вычисления этих величин сильно отличаются для разных типов СУБД реального времени. Так, например, в системах с крепкими директивными сроками среднее время опоздания транзакций не играет никакой роли, в то время как в системах с мягкими директивными сроками этот параметр довольно полезен [79].

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

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

В течение последних 10 лет для систем реального времени был предложен ряд специфических протоколов с улучшенными характеристиками для систем реального времени. Среди них есть как модификации классических пессимистических и оптимистических протоколов [79], так совершенно новые, созданные специально для систем реального времени, протоколы [79].

Пессимистический подход

Наиболее известными пессимистическими протоколами для баз данных в системах реального времени являются модификации «двухфазового протокола блокирования» (2PL). Рассмотрим вкратце некоторые из них:

1 2PL-HP (High Priority)

Основная идея этого протокола [79] – разрешать все конфликты в пользу транзакций с большим приоритетом. Когда транзакция Т запрашивает блокировку на какой-то элемент данных d, возможно три варианта ситуаций:

· если d свободен, то Т получает на него блокировку;

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

· иначе Т становится в очередь на эту блокировку.

Заметим, что такой протокол гарантирует отсутствие тупиков.

2 2PL-WP (Wait Promote)

Эта модификация 2PL основана на идее наследования приоритета [79]. Когда транзакция Т с большим приоритетом запрашивает блокировку на какой-то ресурс d, который в данный момент заблокирован другой транзакцией с меньшим приоритетом, то Т встает в очередь (как в 2PL). Однако транзакции, удерживающей блокировку на d, повышают приоритет до уровня приоритета Т. В результате эта транзакция может быть выполнена быстрее (поскольку ей меньше придется простаивать дожидаясь других ресурсов) и, следовательно, приближается момент получения блокировки на d транзакцией Т.

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

Пример работы этих двух протоколов изображен на рисунке 4.9.2.

Рисунок 4.9.2 – Пессимистические протоколы 2PL-HP, 2PL-WP

Оптимистический подход

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

Рассмотрим два примера оптимистических протоколов для систем реального времени:

1 OPT-SACRIFICE

Этот протокол [79] является адаптированным к СУБД реального времени вариантом протокола OCC-FV (Optimistic Concurrency Control with Forward Validation). Согласно OPT-SACRIFICE транзакция Т₀, достигшая фазы проверки, обрывается, если хотя бы одна из конфликтующих с ней транзакций имеет больший приоритет. Иначе же Т₀ благополучно завершается, а все конфликтующие с ней транзакции завершаются анормально. Таким образом, проверяемая транзакция, которая уже почти завершилась, приносит себя в жертву ради еще работающей транзакции Т₁ с большим приоритетом.

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

2 OPT-WAIT

Этот протокол [79] также принадлежит к классу «вперед смотрящих» протоколов. Согласно ему, транзакция Т, достигнув фазы проверки и обнаружив множество конфликтующих с ней транзакций Т´, ведет себя следующим образом:

· если приоритет T выше, чем у всех конфликтующих с ней транзакций Т_iÎТ´, то T завершается нормально, а все Т_i завершаются анормально;

· иначе Т не обрывается немедленно, а ждет завершения тех Т_i из Т´, чей приоритет выше ее собственного:

· в случае если более высокоприоритетная транзакция из Т´ завершается нормально, то Т обрывается;

· если же ни одна из более высокоприоритетных транзакций из Т´ не завершится нормально, то Т_i завершается нормально сама.

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

Пример работы двух оптимистических протоколов изображен на рисунке 4.9.3.

Рисунок 4.9.3 – Оптимистические протоколы OPT-SACRIFICE,

OPT-WAIT

Сравнение подходов

Традиционно протоколы управления транзакциями различаются по двум критериям: время обнаружения конфликтов и способ их обнаружения. Согласно этим критериям пессимистические и оптимистические протоколы представляют собой две крайности.

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

Оба способа разрешения конфликтов имеют свои недостатки. Блокирование приводит к консервированию ресурсов, а рестарты вызывают их растрату.

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

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

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

Сравнительный анализ этих двух подходов для модели простых транзакций в системах управления базами данных реального времени с мягкими и крепкими директивными сроками, с ограниченным числом ресурсов и неограниченным, показывает, что в большинстве ситуаций оптимистический подход превосходит пессимистический [79]. Однако в связи с огромным количеством систем реального времени со специфическими требованиями не существует лучшего протокола для всех случаев, и бывают ситуации, когда пессимистический протокол показывает лучшие результаты.