Аномалии параллельных транзакций: потерянное обновление, зависимость от нефиксированных результатов, несогласованная обработка

Управление параллельностью – это процесс организации одновременного выполнения в БД различных операций, гарантирующий исключение их взаимного влияния друг на друга.

Почему необходимо управлять параллельностью?

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

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

1 Проблема потерянного обновления. Эта проблема проявляется в том, что результаты успешно завершенной операции обновления одной транзакции перекрываются результатами выполнения другой транзакции.

время	T1	T2	значение элемента f
t1		begin tran
t2	begin tran	read f
t3	read f	f:=f+100
t4	f:=f-10	write f
t5	write f	commit
t6	Commit

В данном случае элемент – значение поля некоторого кортежа.

Транзакции Т1 и Т2 начинаются практически одновременно и считывают одинаковое значение элемента f. Одна добавляет к значению элемента 100 и записывает результат, а вторая вычитает 10 и также записывает результат. Таким образом значение элемента равно 90. Если бы транзакции выполнялись последовательно, то значение поля было бы равно 190. То есть явное влияние транзакций друг на друга. Избежать такой проблемы можно, если запретить Т1 читать элемент f до тех пор, пока Т2 не запишет его значения.

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

время	Т1	Т2	значение элемента f
t1		begin tran
t2		read f
t3		f:=f+100
t4	begin tran	write f
t5	read f	... {т.е Т1 читает после записи Т2}
t6	f:=f-10	rollback
t7	write f
t8	commit

Если бы транзакции выполнялись бы последовательно, то значение элемента f было бы равно 90. Подобную проблему можно устранить, если запретить Т1 читать значение элемента f до того, как Т2 будет зафиксирована или отменена.

3 Проблема несогласованной обработки (неповторяемого чтения). Эта проблема возникает, когда одна транзакция только считывает элементы, но вторая в это время изменяет их значения. (T1переводит деньги с f1 на f3, а Т2 считает общую сумму на счетах f1, f2, f3)

время	Т1	Т2	f1	f2	f3	sum
t1		begin tran
t2	begin tran	sum:=0
t3	read f1	read f1
t4	f1:=f1-10	sum:=sum+f1
t5	write f1	read f2	90 /*уТ1 100*/
t6	read f3	sum:=sum+f2
t7	f3:=f3+10
t8	write f3
t9	commit	read f3
t10		sum:=sum+f3
t11		Commit

Таким образом, сумма получилась не верной, не смотря на то, что перевод осуществлялся между теми же счетами, по которым считалась сумма. В данном случае БД осталась в корректном состоянии, но пользователь получил некорректные данные.

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

53.Понятие плана параллельного выполнения транзакций. Последовательные, непоследовательные и неупорядоченные планы.

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

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

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

Непоследовательный плана – это план в котором чередуются операции из некоторого набора одновременно выполняемых транзакций. Непоследовательный плана является корректным, если он приводит к получению тех же результатов, которые получаются при использовании некоторого последовательного плана. Такой план называется упорядоченным. /*Все три проблемы параллельного доступа были обусловлены неупорядоченностью плана выполнения транзакций. */

Пример. Перевод денежных средств между счетами А, В, С. Две транзакции.

T1: read (A); A:=A-10; write(A); read(B); B:=B+10; write (B);

T2: read (B); B:=B-20; write(B); read(C); C:=C+20; write (C);

Корректность работы заключается в сохранении постоянного значения суммой А+В+С.

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

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

54.Конфликтное упорядочивание планов и упорядочивание планов по просмотру.

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

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

1 Вершин, соответствующих каждой их транзакций плана.

2 Направленных ребер Ti -> Tj, где транзакция Tj считывает элемент, записанный транзакцией Ti.

3 Направленных ребер, Ti -> Tj, где транзакция Tj записывает элемент после того, как он был считан транзакцией Tj. /*До записи или вообще не записывает */

Если граф предшествования содержит циклы, то он не является конфликтно упорядоченным.

Пример конфликтно упорядочиваемого плана и неупорядочиваемого

T1	T2		T3	T4
begin tran			begin tran
read X			read X
write X			X=X+100
	begin tran		write X
	read X			begin tran
	write X			read X
read Y				X=X*1.1
write Y				write X
commit				read Y
	read Y			Y=Y*1.1
	write Y			write Y
	commit			commit
			read Y
			Y=Y-100
			write Y
			commit

Граф для Т1 и Т2 – без циклов Т3 и Т4 – с циклом

План является упорядоченным по просмотру, если он эквивалентен по просмотру некоторому последовательному плану.

Два плана S1 и S2, состоящих из одних и тех же операций, входящих в транзакции T1, T2, … Tn, являются эквивалентными по просмотру, если выполняются следующие условия:

1 Если транзакция Ti прочла исходное значение элемента в плане S1, то эта же транзакция Ti должна прочесть исходное значение элемента и в плане S2.

2 Если в плане S1 транзакция Ti считывает значение элемента, записанного транзакцией Tj, то и в плане S2 Ti должна читать элемент, записанный Tj.

3 Если в плане S1 последняя операция записи элемента была выполнена транзакцией Ti, то эта же транзакция должна выполнять последнюю запись элемента и в плане S2.

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

T1	T2	T3
begin tran
read X
	begin tran
	write X
	commit
write X
commit
		begin tran
		write X
		commit

Этот план не вызовет никаких аномалий, так транзакция Т3 последней записывает элемент Х, не основываясь на его чтении. Поэтому не важно как другие транзакции ранее записывают значение этого элемента. Это и есть слепая запись.

/*Проверка упорядоченности по просмотру является очень сложной задачей. */

На практике СУБД не проверяют планы на упорядоченность. В большинстве случаев это не только трудоемко, но и нецелесообразно, так как на параллельность выполнения влияет операционная система.

Вместо этого в СУБД используются специальные протоколы, гарантирующие упорядоченность планов.

Протокол – это набор правил, которым должны следовать транзакции, что бы между ними не возникали конфликты.