Тема_9 (1122360), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Базы данных93УправлениМетоды сериализации транзакций (58)Синхронизационные тупики, их распознавание и разрушение (12)Разрушение тупиков (5)Естественно, такое насильственное устранениетупиковых ситуаций является нарушениемпринципа изолированности пользователей,которого невозможно избежатьЗаметим, что в централизованных системахстоимость построения графа ожиданиясравнительно невелика, но она становитсяслишком большой в распределенных СУБД, вкоторых транзакции могут выполняться в разныхузлах сетиПоэтому в таких системах обычно используютсядругие методы сериализации транзакций03.12.2009С.Д.Кузнецов. Базы данных94УправлениМетоды сериализации транзакций (59)Метод временных меток (1)Альтернативный метод сериализации транзакций, хорошоработающий в условиях редкого возникновения конфликтовтранзакций и не требующий построения графа ожиданиятранзакций, основан на использовании временных метокОсновная идея метода временных меток (TimestampOrdering, TO), у которого существует множестворазновидностей, состоит в следующем: если транзакция T1 началась раньше транзакции T2, тосистема обеспечивает такой сериальный план, как если бытранзакция T1 была целиком выполнена до начала T2.Для этого каждой транзакции T предписывается временнаяметка t(T), соответствующая времени начала выполнениятранзакции TПри выполнении операции над объектом o транзакция Tпомечает его своими идентификатором, временной меткой итипом операции (чтение или изменение)03.12.2009С.Д.Кузнецов.

Базы данных95УправлениМетоды сериализации транзакций (60)Метод временных меток (2)Перед выполнением операции над объектом o транзакция T2выполняет следующие действия:Проверяет, помечен ли объект o какой-либо транзакцией T1oЕсли не помечен, то помечает этот объект своей временной меткой и типомоперации и выполняет операцию•Иначе транзакция T2 проверяет, не завершилась ли транзакция T1,пометившая этот объектoЕсли транзакция T1 закончилась, то T2 помечает объект o и выполняет своюоперацию•Конец действийКонец действий.Если транзакция T1 не завершилась, то T2 проверяет конфликтностьоперацийoЕсли операции неконфликтны, то при объекте o•••03.12.2009запоминается идентификатор транзакции T2,остается или проставляется временная метка с меньшим значением, итранзакция T2 выполняет свою операциюС.Д.Кузнецов.

Базы данных96УправлениМетоды сериализации транзакций (61)Метод временных меток (3)Если операции транзакций T2 и T1конфликтуют, то если t(T1) > t(T2) (т.е.транзакция T1 является более «молодой», чемT2),ooто производится откат T1 и всех других транзакций,идентификаторы которых сохранены при объекте o,иT2 выполняет свою операциюЕсли же t(T1) < t(T2) (T1 «старше» T2),ooто производится откат T2;T2 получает новую временную метку и начинаетсязаново03.12.2009С.Д.Кузнецов. Базы данных97УправлениМетоды сериализации транзакций (62)Метод временных меток (4)К недостаткам метода TO относятся потенциально болеечастые откаты транзакций, чем в случае использованиясинхронизационных захватовЭто связано с тем, что конфликтность транзакцийопределяется более грубоКроме того, в распределенных системах не очень простовырабатывать глобальные временные метки с отношениемполного порядка это отдельная большая наукаНо в распределенных системах эти недостатки окупаютсятем, что не нужно распознавать тупики, а построение графаожидания в распределенных системах стоит очень дорого03.12.2009С.Д.Кузнецов.

Базы данных98УправлениМетоды сериализации транзакций (63)Версионные методы (1)Основная идея версионных алгоритмов сериализации транзакцийсостоит в том, что в базе данных допускается существованиенескольких «версий» одного и того же объектаЭти алгоритмы, главным образом, направлены на преодолениеконфликтов транзакций категорий R/W и W/R, позволяя выполнятьоперации чтения наднекоторой предыдущей версией объекта базы данныхВ результате операции чтения выполняются без задержек итупиков, свойственных механизмам синхронизационныхблокировок, а также без некоторых откатов, возможных приприменении метода временных метокАлгоритмы управления транзакциями, основанные на поддержкеверсий, достаточно широко распространены в области SQLориентированных СУБДВ частности, подобные алгоритмы используются в СУБД Oracle иPostgreSQL03.12.2009С.Д.Кузнецов.

Базы данных99УправлениМетоды сериализации транзакций (64)Версионные методы (2)Версионный вариант алгоритма временных меток (1)Одним из наиболее старых и простых версионных алгоритмовявляется версионный вариант алгоритма временных меток(Multiversion Timestamp Ordering, MVTO)Как и в простом методе временных меток, описанном впредыдущем подразделе, в алгоритме MVTO порядок выполненияопераций одновременно выполняемых транзакций задаетсяпорядком временных меток, которые получают транзакции вовремя стартаВременные метки также используются для идентификации версийданных при чтении и модификации – каждая версия получаетвременную метку той транзакции, которая ее записалаАлгоритм MVTO не только следит за порядком выполненияопераций транзакций, но также отвечает за трансформациюопераций над объектами базы данных в операции над версиямиэтих объектов,т.е.

каждая операция над объектом базы данных o преобразуется всоответствующую операцию над некоторой версией объекта o03.12.2009С.Д.Кузнецов. Базы данных100УправлениМетоды сериализации транзакций (65)Версионные методы (3)Версионный вариант алгоритма временных меток (2)При описании алгоритма будем использоватьследующие обозначенияКак и раньше, временную метку, полученнуютранзакцией Ti в начале ее работы, будем обозначатькак t(Ti)Операция чтения объекта базы данных o, выполняемаяв транзакции Ti, будет обозначаться как Ri(o)Для обозначения того, что транзакция Ti читает версиюобъекта базы данных o, созданную транзакцией Tk,будем использовать запись Ri(ok)Для обозначения того, что транзакция Ti записываетверсию элемента данных o, будем использовать записьWi(oi)Алгоритм MVTO работает следующим образом03.12.2009С.Д.Кузнецов.

Базы данных101УправлениМетоды сериализации транзакций (66)Версионные методы (4)Версионный вариант алгоритма временных меток (3)Любая операция Ri(o) преобразуется в операцию Ri(ok), гдеok – это версия объекта o, помеченная наибольшейвременной меткой t(Tk), такой что t(Tk)≤ t(Ti) Другими словами, транзакции Ti для чтения дается версияобъекта o, созданная транзакцией Tk, которая не моложе Ti,но старше любой другой транзакции Tn, создававшей своюверсию объекта oПри обработке операции Wi(o) выполняются следующиедействия: если к этому времени некоторой незафиксированнойтранзакцией Tn уже выполнена некоторая операция Rn(ok),такая что t(Tk) ≤ t(Ti) < t(Tn), тоooоперация Wi(o) не выполняется, атранзакция Ti откатывается;в противном случае Wi(o) преобразуется в Wi(oi),oт.е.

образуется еще одна версия объекта o03.12.2009С.Д.Кузнецов. Базы данных102УправлениМетоды сериализации транзакций (67)Версионные методы (5)Версионный вариант алгоритма временных меток (4)При откате любой транзакции уничтожаются все созданныеею версии объектов базы данных и откатываются всетранзакции, прочитавшие хотя бы одну из этих версий Тем самым, откаты транзакций могут быть «каскадными».Выполнение операции фиксации транзакции Ti (COMMIT)откладывается до того момента, когда завершатся всетранзакции, записавшие версии данных, прочитанные TiБез соблюдения этого требования не соблюдалось бысвойство долговечности (durability) транзакций, посколькупри откате некоторых транзакций потребовалось быоткатывать и ранее зафиксированные транзакции03.12.2009С.Д.Кузнецов. Базы данных103УправлениМетоды сериализации транзакций (68)Версионные методы (6)Версионный вариант алгоритма временных меток (5)Преимуществаалгоритма MVTOлучше всегоиллюстрируютсяповедениемтранзакций T1 и T2При использованииблокировок междуними возник бысинхронизационныйтупик, а прииспользованииобычного методавременных меток одна из транзакций подверглась бы откатуОднако при применении версий такие неприятности не возникаютиз-за того, что первая транзакция читает «старые» версии объектовoиω03.12.2009С.Д.Кузнецов.

Базы данных104УправлениМетоды сериализации транзакций (70)Версионные методы (7)Версионный вариант алгоритма временных меток (6)Транзакция T3ожидаетфиксациитранзакции T2перед своимсобственнымзавершениемэто показанопунктирнойлиниейЭто происходит потому, что транзакция T3прочитала версию o2 объекта o, образованнуюеще не зафиксированной транзакцией03.12.2009С.Д.Кузнецов. Базы данных105УправлениМетоды сериализации транзакций (71)Версионные методы (8)Версионный вариант алгоритма временных меток (7)Транзакция T4пытаетсясоздать версиюω4 объекта ωпосле того, какеще незафиксированнаятранзакция T5начавшаяся позжеуже прочиталаболее раннююверсию ω4Поэтомутранзакция T5не сможет «увидеть» изменения объекта ω, произведенныетранзакцией T4.

Следовательно, сериализация транзакций впорядке получения ими временных меток становится невозможной,и приходится произвести откат транзакции T403.12.2009С.Д.Кузнецов. Базы данных106УправлениМетоды сериализации транзакций (72)Версионные методы (9)Версионный вариант алгоритма временных меток (8)Итак, основными преимуществами алгоритмаMVTO являетсяа основным недостатком –отсутствие задержек и откатов при выполненииопераций чтения,возможность возникновение каскадных откатовтранзакций при выполнении операций записиКроме того, в базе данных может накапливатьсяпроизвольное число версий одного и того жеобъекта, иопределение того, какие версии больше не требуются,является серьезной технической проблемой03.12.2009С.Д.Кузнецов.

Базы данных107УправлениМетоды сериализации транзакций (73)Версионные методы (10)Версионный вариант двухфазного протокола синхронизационных блокировок (1)При описании двухверсионного вариантапротокола 2PLбудем называтьTwo-Version Two-Phase Locking Protocol, 2V2PLтекущими версиями объектов базы данных версии,созданные зафиксированными транзакциями снаиболее поздним временем фиксациинезафиксированными версиями – версии, созданныееще незавершившимися транзакциямиПри следовании протоколу 2V2PL в каждыймомент времени существует не более однойнезафиксированной версии каждого объектабазы данных03.12.2009С.Д.Кузнецов.

Базы данных108УправлениМетоды сериализации транзакций (74)Версионные методы (11)Версионный вариант двухфазного протокола синхронизационных блокировок (2)Операции любой транзакции Ti над объектом базы данных oобрабатываются следующим образом: операция Ri(o) немедленно выполняется над текущейверсией объекта o; операция Wi(o), приводящая к созданию новой версииобъекта o, выполняется только после завершенияoфиксации или откататранзакции, создавшей незафиксированную версию объектаo;выполнение операции COMMIT откладывается до тех пор,пока не завершатся все транзакции Tk, прочитавшие текущиеверсии объектов базы данных, которые должны заменитьсянезафиксированными версиями этих объектов, созданнымитранзакцией Ti03.12.2009С.Д.Кузнецов.

Характеристики

Список файлов лекций