Решение проблем параллельной обработки транзакций и выход из тупиковых ситуаций в базах данных | Статья в журнале «Молодой ученый»

Авторы: ,

Рубрика: Информатика

Опубликовано в Молодой учёный №9 (143) март 2017 г.

Дата публикации: 03.03.2017

Статья просмотрена: 252 раза

Библиографическое описание:

Омельяненко М. В., Папинашвили В. Г. Решение проблем параллельной обработки транзакций и выход из тупиковых ситуаций в базах данных // Молодой ученый. — 2017. — №9. — С. 31-34. — URL https://moluch.ru/archive/143/40173/ (дата обращения: 15.08.2018).



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

Ключевые слова: базы данных, проблемы параллелизма, тупиковая ситуация

Для дальнейшего рассмотрения вопроса разберёмся, что есть параллельная обработка кортежей или параллелизм. Термин параллелизм означает возможность одновременной обработки в СУБД многих транзакций с доступом к одним и тем же данным, причем в одно и то же время. [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 и т. п.

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

Литература:

  1. Дейт К. Дж. Введение в системы баз данных, 6-е изд., «Вильямс» 2000. — 848 с.
Основные термины (генерируются автоматически): транзакция А, проблема, транзакция, тупиковая ситуация, транзакция В, обновление кортежа, незафиксированная зависимость, несовместимый анализ, помощь блокировок, момент времени.


Ключевые слова

базы данных, проблемы параллелизма, тупиковая ситуация

Похожие статьи

Восстановление и параллельность как аспекты управления...

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

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

Транзакции в базах данных | Статья в журнале «Молодой ученый»

Транзакции в базах данных. Автор: Папинашвили Виктор Геннадьевич.

Из этого следует, что в данном примере необходимо избегать такой ситуации, когда одно из обновлений будет

Восстановление незафиксированных транзакций сервер, разумеется, не гарантирует.

Алгоритм обработки транзакций для повышения эффективности...

По истечении отведенного времени транзакция должна быть принудительно завершена: откат.

Решение проблем параллельной обработки транзакций и выход из тупиковых ситуаций в базах данных.

Использование Big Data в управлении взаимоотношениями...

Либо противоположная ситуация, когда клиент совершает покупку в магазине, банк видит, что карта, по которой происходит транзакция, и

Цифровые дисплеи в магазинах отображают предложения, сменяющие друг друга каждую минуту, в зависимости от времени суток и...

Проблемы распределённых СУБД | Статья в журнале...

Основная проблема репликации данных заключается в том, что обновление любого

Но, если некоторый узел, содержащий копию данного объекта, в момент обновления может оказаться

Двухфазная фиксация транзакций требуется в любой среде, где отдельная транзакция может...

Основы разработки баз данных реального времени

Транзакция в реальном времени — это транзакция с дополнительными атрибутами

Рис. 1. Зависимость значимости транзакций от времени.

Зыль С. Н. Проектирование, разработка и анализ программного обеспечения систем реального времени — СПб.

Транзакционные издержки и управление портфелями ценных бумаг

Избыточный спрос на акции и цена, преобладающая на момент размещения приказа, может стать причиной ее роста.

Например, они могут разместить несколько мелких приказов в разные периоды времени для

Анализ привлечения капитала на рынке ценных бумаг России.

Технологии профилирования заёмщиков в банковской сфере...

С помощью передовых технологий интеллектуального анализа данных банк может достаточно точно оценить кредитоспособность потенциальных

Может включать в себя периодическое обновление профилей пользователей, сопоставление транзакций между группами лиц.

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Восстановление и параллельность как аспекты управления...

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

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

Транзакции в базах данных | Статья в журнале «Молодой ученый»

Транзакции в базах данных. Автор: Папинашвили Виктор Геннадьевич.

Из этого следует, что в данном примере необходимо избегать такой ситуации, когда одно из обновлений будет

Восстановление незафиксированных транзакций сервер, разумеется, не гарантирует.

Алгоритм обработки транзакций для повышения эффективности...

По истечении отведенного времени транзакция должна быть принудительно завершена: откат.

Решение проблем параллельной обработки транзакций и выход из тупиковых ситуаций в базах данных.

Использование Big Data в управлении взаимоотношениями...

Либо противоположная ситуация, когда клиент совершает покупку в магазине, банк видит, что карта, по которой происходит транзакция, и

Цифровые дисплеи в магазинах отображают предложения, сменяющие друг друга каждую минуту, в зависимости от времени суток и...

Проблемы распределённых СУБД | Статья в журнале...

Основная проблема репликации данных заключается в том, что обновление любого

Но, если некоторый узел, содержащий копию данного объекта, в момент обновления может оказаться

Двухфазная фиксация транзакций требуется в любой среде, где отдельная транзакция может...

Основы разработки баз данных реального времени

Транзакция в реальном времени — это транзакция с дополнительными атрибутами

Рис. 1. Зависимость значимости транзакций от времени.

Зыль С. Н. Проектирование, разработка и анализ программного обеспечения систем реального времени — СПб.

Транзакционные издержки и управление портфелями ценных бумаг

Избыточный спрос на акции и цена, преобладающая на момент размещения приказа, может стать причиной ее роста.

Например, они могут разместить несколько мелких приказов в разные периоды времени для

Анализ привлечения капитала на рынке ценных бумаг России.

Технологии профилирования заёмщиков в банковской сфере...

С помощью передовых технологий интеллектуального анализа данных банк может достаточно точно оценить кредитоспособность потенциальных

Может включать в себя периодическое обновление профилей пользователей, сопоставление транзакций между группами лиц.

Задать вопрос