В процессе изучения теории баз данных, а именно проблем параллелизма, как правило, упоминается такое понятие, как «тупиковая ситуация» и причины её появления, но не всегда поднимается вопрос о том, каким образом эта проблема решается. Именно этот вопрос рассматривается в данной статье. Раскрывается тема разрешения тупиковых ситуаций, возникающих при параллельной обработке кортежей, даются определения основным проблемам параллелизма, а также возможные методы их решения и выхода из тупиков.
Ключевые слова: базы данных, проблемы параллелизма, тупиковая ситуация
Для дальнейшего рассмотрения вопроса разберёмся, что есть параллельная обработка кортежей или параллелизм. Термин параллелизм означает возможность одновременной обработки в СУБД многих транзакций с доступом к одним и тем же данным, причем в одно и то же время. [1] Очевидно, что для корректного выполнения параллельной обработки необходимо иметь определенные методы управления, которые позволят избежать конфликтных ситуаций и проблем, рассмотренных далее в статье.
Итак, рассмотрим три проблемы, которые могут возникнуть при параллельном выполнении транзакций:
− Проблема потери результатов обновления;
− Проблема незафиксированной зависимости;
− Проблема несовместимого анализа.
Проблема потери результатов обновления возникает тогда, когда две транзакции записывают данные в один и тот же кортеж и фиксируют значения, как следствие –зафиксировано то обновление, которое было произведено последним. Остальные обновления — потеряны. Из рис. 1 видно, что транзакция B выполнила обновление кортежа после транзакции A, таким образом, обновление кортежа транзакцией А утеряно.
Проблема незафиксированной зависимости появляется, если с помощью некоторой транзакции осуществляется извлечение (а еще хуже — обновление) некоторого кортежа, который в данный момент обновляется другой транзакцией, но это обновление еще не закончено. Если обновление не завершено, существует вероятность, что оно не завершится никогда. [1]
В таких случаях кортеж выполняет возврат в своё предыдущее состояние, и транзакция, пытающая извлечь данные из него как бы считывает данные, которых «никогда» не существовало. Пример данной проблемы отображен на рис. 2: транзакция А становится зависимой от изменения, не выполненного в момент времени t2, а в момент t3 утрачивается результат обновления, поскольку происходит возврат транзакции B в исходное состояние в момент времени t1.
Рис. 1. Потеря результатов обновления в момент времени t4
Рис. 2. Проблема незафиксированной зависимости
Наконец третья проблема — проблема несовместимого анализа. Транзакция А дважды читает один и тот же кортеж. Между этими чтениями выполняется транзакция В, которая изменяет значения в кортеже.
Итак, были рассмотрены три основные проблемы, возникающих в процессе параллельного выполнения транзакций. Все эти проблемы разрешимы определённым стандартным методом — методом блокировки. Заметим, что это отнюдь не единственный метод разрешения такого рода проблем, но на практике использующийся чаще всех.
Основная идея этого метода заключается в том, что, в случае, когда для выполнения некоторой транзакции необходимо, чтобы некоторый объект не изменялся непредсказуемо и без ведома этой транзакции, такой объект блокируется. Предположим, что в системе поддерживается два типа блокировки: X-блокировка — без взаимного доступа (блокировка записи) и S-блокировка (блокировка чтения) со взаимным доступом. [1]
Теперь рассмотрим решение описанных ранее проблем при помощи данного метода.
Для решения проблемы потери результатов обновления рассмотрим рис. 3. Обе транзакции успешно накладывают S-блокировку и получают доступ для извлечения кортежа p. Для того чтобы осуществить обновление кортежа p, транзакция B пытается наложить на него X-блокировку. Эта блокировка отвергается, так как кортеж p уже заблокирован S-блокировкой, осуществленной транзакцией A. Транзакция B переходит в состояние ожидания до тех пор, пока транзакция В не освободит объект.
Рис. 3. Решение проблемы потери результатов обновления при помощи блокировок
Но решив одну проблему, блокировка приводит к появлению другой проблемы — тупиковой ситуации. Разберемся, как это происходит. Что, например, произойдет в случае, когда транзакция B начнет вносить изменения в кортеж p (рис. 3)? Перед обновлением кортежа, транзакции В необходимо наложить на него X-блокировку, но ей это не удастся, так как транзакция А прежде наложила на кортеж S-блокировку. Получается, что ни одна из транзакций не может продолжить своё выполнение, ожидая пока одна из них не закончит своё выполнение. Это явление и называется тупиковой ситуацией. К разрешению таких ситуаций мы вернемся чуть позже.
Аналогично, с помощью метода блокировок, решается и проблема незафиксированнойзависимости. Наложив S-блокировку, транзакция А не дает прав транзакции В на обновление кортежа, поэтому В ожидает, пока А произведёт фиксацию (рис. 4).
Рис. 4. Решение проблемы незафиксированной зависимости с помощью блокировок
Работа транзакции В была приостановлена до окончания (отката) транзакции А. После этого транзакция В продолжила работу в обычном режиме и работала с правильными данными. Конфликт разрешен за счет некоторого увеличения времени работы транзакции В (потрачено время на ожидание снятия блокировки транзакцией А).
Проблема несовместимого анализа также решается с помощью блокировок. Работа транзакции В приостановилась до окончания транзакции А. В результате транзакция А дважды корректно читает одни и те же данные. После окончания транзакции А транзакция В продолжила работу в обычном режиме. Проблема успешно разрешена (рис. 5).
Однако, данное решение проблемы приводит к возникновению тупиковой ситуации. К примеру, длинная транзакция выполняет некоторый анализ по всей таблице: подсчитывает общую сумму денег на счетах клиентов банка. Пусть на всех счетах находятся одинаковые суммы — 100 р. Короткая транзакция в этот момент выполняет перевод 50 р. с одного счета на другой так, что общая сумма по всем счетам не меняется.
Рис. 5. Решение проблемы несовместимого анализа с помощью блокировок
Итак, мы рассмотрели три проблемы, из которых в двух возникла тупиковая ситуация. Один из выходов в данной ситуации — поиск «жертвы» — транзакции, которая будет отменена первой. Тогда её блокировка снимается, и процесс выполнения продолжается. Отмененную транзакцию необходимо выполнять заново. Для обработки тупиков существует два основных подхода.
Подход 1. Транзакция сама решает, быть ли ей «жертвой». Задается время ожидания (или число попыток), в течение которого она пытается установить нужную блокировку. Если по истечении времени (попыток) блокировка не установилась, то транзакция откатывается. Достоинства подхода — простота использования. Недостатки — транзакции-«жертвы» выбираются случайным образом. Из-за одной простой транзакции может откатиться более «дорогая» транзакция, на выполнение которой уже потрачено много времени и ресурсов системы. Такой подход характерен для СУБД FoxPro, Clipper и т. п.
Подход 2. Система сама следит за возникновением ситуации тупика путем построения диаграммыожиданиятранзакций, т. е. перечне «транзакций, которые ожидают окончания других транзакций». Для обнаружения тупиковой ситуации следует обнаружить цикл в данной диаграмме. [1] Определив цикл в диаграмме, выбирается транзакция-жертва, которая откатывается для обеспечения возможности продолжения работы других транзакций. Критерий выбора транзакции-жертвы — её стоимость, в которую входят: время выполнения транзакции, число накопленных блокировок, приоритет и другие факторы. После выбора транзакции-жертвы выполняется ее откат, освобождаются её блокировки. Подход свойственен для Oracle, DB2, MS SQL Server и т. п.
Таким образом, в данной статье были рассмотрены основные проблемы параллельной обработки транзакций, методы их решения, а также причины появления тупиковых ситуаций и способы их разрешения.
Литература:
- Дейт К. Дж. Введение в системы баз данных, 6-е изд., «Вильямс» 2000. — 848 с.
