14.6. Способность к упорядочению

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

1. Отдельные транзакции считаются верными, если при их выполнении база данных переходит из одного непротиворечивого состояния в другое непротиворечивое со­стояние в смысле, изложенном в главе 13.

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

3. Чередующееся выполнение транзакций, следовательно, является верным, если оно эквивалентно некоторому последовательному выполнению, т.е. если оно подле­жит упорядочению.

Возвращаясь к приведенным выше примерам (рис. 14.1-14.4), можно отметить:

данная проблема в каждом случае заключалась в том, что чередующееся выполнение транзакций не было упорядочено, т.е. не было эквивалентно выполнению либо снача­ла транзакции А, а затем транзакции В, либо сначала транзакции В, а затем транзак­ции А. Основное значение предложенной выше схемы блокировки заключается в принудительном упорядочении. На рис. 14.7 и 14.8 чередующееся выполнение экви­валентно выполнению сначала транзакции В, а затем транзакции А. На рис. 14.6 и 14.9 показана тупиковая ситуация, в которой можно было бы отменить и, возможно, повторно запустить одну из двух транзакций. Если транзакция А отменяется, чере­дующееся выполнение вновь становится эквивалентным выполнению сначала тран­закции В, а затем транзакции А.

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

Стоит подчеркнуть, что при выполнении двух различных последовательных гра­фиков запуска, содержащих одинаковый набор транзакций, можно получить совер­шенно различные результаты. Поэтому выполнение двух различных чередующихся графиков запуска с одинаковыми транзакциями может также привести к различным результатам, которые могут быть восприняты как верные. Например, предположим, что транзакция А означает действие "сложить 1 с х”, а транзакция В — "удвоить х" (где х— это некоторый объект базы данных). Предположим также, что начальное значением равно 10. Тогда при последовательном выполнении сначала транзакции А, а затем транзакции В будет получен результат х=22, а при последовательном выпол­нении сначала транзакции В, а затем транзакции А — х=21. Оба результата одинаково верные, а любой график запуска, эквивалентный выполнению либо сначала транзак­ции А, а затем транзакции В, либо сначала транзакции В, а затем транзакции А, также является верным (это еще будет обсуждаться в упражнениях к данной главе).

Концепция способности к упорядочению была впервые предложена (хотя и под другим названием) Есвараном (Eswaran) в [14.5]. В этой работе также доказана важ­ная теорема двухфазной блокировки(///), которая кратко может быть сформулирована следующим образом:

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

/// Двухфазная блокировка не имеет ничего общего с двухфазной фиксацией.///

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

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

2. После снятия блокировки транзакция не должна накладывать никаких других бло­кировок.

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

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

Понятие способности к упорядочению существенно облегчает понимание этой до­вольно запутанной области знаний. В дополнение к сказанному следует добавить не­сколько комментариев. Пусть Е является чередующимся графиком запуска, включающим некоторый набор транзакций Т1, Т2, ... Тп. Если Е является графиком, до­пускающим возможность упорядочения, то существует некоторый последовательный график запуска S, содержащий такой набор транзакций T1, T2, ... Тп, что график Е эк­вивалентен графику S. В таком случае S называется упорядочением Е. Как уже было показано ранее, S необязательно является уникальным, т.е. некоторый график запуска Е может иметь несколько упорядочений.

Пусть Ti и Тj — некоторые транзакции множества транзакций T1, Т2, ... Тп. Не те­ряя общности изложения, предположим, что в упорядочении S транзакция Ti предше­ствует Тj. Следовательно, для чередующегося графика запуска Е это значит, что тран­закция Ti выполняется перед транзакцией Тj. Иначе говоря, неформальная, но очень полезная характеристика упорядочения может быть выражена следующим образом. Если А и В являются любыми двумя транзакциями некоторого графика запуска, до­пускающего возможность упорядочения, то либо А логически предшествует В, либо В логически предшествует А, т.е. либо В использует результаты выполнения тран­закции А, либо А использует результаты выполнения транзакции В. (Если тран­закция А приводит к обновлению кортежей р, q, ... r и транзакция В использует эти кортежи в качестве входных данных, то используются либо все обновленные с помо­щью А кортежи, либо полностью не обновленные кортежи до выполнения транзакции А, но никак не их смесь.) Наоборот, график запуска является неверным и не подлежит упорядочению, если результат выполнения транзакций не соответствует либо сначала выполнению транзакции А, а затем транзакции В, либо сначала выполнению транзак­ции В, а затем транзакции А.

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