автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Низкоуровневая поддержка нестандартных моделей транзакций в системе хранения

р\ Ь и»

1 п ЛПР 1595

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

Домбровасаа Генриэтта Ромуальдовна

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

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 1995

Работа выполнена в Санкт-Петербургской государственной университете.

Научный руководитель: кандидат физико-математических наук,

Официальные оппоненты:

• доктор технических наук С.Д. Кузнецов

• кандидат физико-математических наук Ф.А. Новиков

Ведущая организация — Институт проблем информатики Российской академии наук

Защита диссертации состоится « » 199 Эг. в

час. З-С? мин. на заседания диссертационного совета К 063.57.54 по присуждению ученой степени кандидата физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904 Санкт-Петербург, Старый Петергоф, Библиотечная пл. 2.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского университета по адресу:

199034, Санкт-Петербург, Университетская набережная, 7/9.

Новиков Борис Асенович

Автореферат разослан

Ученый секретарь диссертационного совета

Б.К. Мартыпенко

Общая характеристика работы

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

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

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

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

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

блокировок, метод проверки корректности доступа транзакций к буферам, разработка структуры п способа ведения дерева активных транзакций как основного инструмента поддержки нестандартных моделей транзакций на уровне управления буферами; предложенная модификация алгоритма ARIES/NT для поддержки откатов и восстановлений, дающая возможность использовать его не только в системах с вложенными транзакциями, но и в условиях поддержки системой других нетрадиционных моделей транзакций.

Практическая ценность. Практическая ценность работы определяется использованием ее результатов в проекте "СИНТЕЗ", ориентированном на создание интеродерабельноя среды неоднородных информационных ресурсов.

Апробация работы. Основные результаты диссертации докладывались на рабочих семинарах по проекту "СИНТЕЗ" в 1990 и 1993 годах, на семинарах лаборатории исследования операций, а также на рабочем семинаре "Перспективы развития систем баз данных и информационных систем" в мае 1993 года и на международном симпозиуме "Advances in Databases and Information Systems" (Москва, май 1994 г.). По теме диссертации опубликованы работы (1]-[7].

Структура в объем работы. Диссертация состоит из 6 глав, в том числе введения и заключения. Объем диссертации составляет 71 машинописный лист, Список литературы содержит 48 наименований.

Содержание работы

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

Обсуждаются причины, по которым применение классических

транзакций в таких современных приложенных, как САПР, и в распределенных СУБД приводит к появлению нежелательных ограничений. Для преодоления этих ограничении были предложены новые модели транзакций, не обладающие набором ACID свойств: во-первых, различные варианты вложенных транзакций, политранзакцип и другие, применяемые в распределенных системах [АА92, LEB92], и, во-вторых, различные тппы долгожпвущпх траязакппй, например, саги [GMS87].

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

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

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

Далее рассматриваются конкретизации модели вложенных транзакций: многоуровневые транзакции и модель DOM, позволяющая специфицировать различные подтипы вложенных транзакций, в частности, отложенные и отсоединенные

В качестве примеров моделей, конкретизирующих саги, обсуждаются расщепляемые транзакции, контракты и система ACTA. В последней разделе главы приводятся примеры описания некоторых классов транзакций в языке СИНТЕЗ.

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

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

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

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

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

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

По завершении логической операции записи буфер помечается как "грязный", т.е. требующий последующего переноса иа диск. В одном из буферов, зарезервированных для записей журнала, формируются записи типов undo и redo. Эти записи немедленно, не дожидаясь конца транзакции, записываются в журнал. После этого удаляется строка пз таблицы захватов. Еслп по завершения операции записи буфер помечен на запись более чем одной транзакцией (признак изменения больше 1), то он переносится на диск немедленно после занесения записи в журнал, иначе это делается по концу транзакции.

Далее описывается алгоритм выполнение операции чтения страницы в буфер и применяемая стратегия замещения.

В четвертой главе рассматриваются средства поддержки нестандартных моделей транзакций. При наличии вложенности любая транзакция имеет доступ ко всем записям, считанным ее непосредственными предшественниками, и по ее завершении все измененные заппси передаются родительской транзакции. При этом фактической записи на диск не происходит, если только этого не требуют параллельно выполняемые транзакции. Задачу контроля корректности доступа решает ведение в памяти дерев а активных транзакций (ДАТ) |5, 7], в узлах которого записывается код транзакции, и ссылки на родителя, старшего брата и первого потомка.

Структура ДАТ обеспечивает эффективный поиск всех предков данной транзакции, определение по коду транзакции се места в дереве транзакций п проверку завершенности всех порожденных пра завершении транзакции.

При проверке корректности обращения к буферу вложенной транзакции сначала необходимо пайти ее место в дереве активных тран-

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

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

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

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

В главе 5 описывается алгоритм ARIES [MHL+92], предназначенный для обеспечения откатов транзакций о восстановления системы после отказов. Этот алгоритм соблюдает WAL (write ahead logging) протокол заполнения журнала, требующий, чтобы все изменения БД прежде, чем будут перенесены на постоянный носитель, записываются в журнал.

При использовании алгоритма ARIES в журнал заносятся записи нескольких типов, отражающие наиболее важные действия с базой данных: undo - запись откатов, содержит информацию, позволяющую вернуть запись в то состояние; в котором она была до начала транзакции; redo - запись накатов, содержит информацию, позволяющую воспроиз-

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

В процессе нормального функционирования СУБД при каждом обновлении записи для нее формируются записи журнала типа undo и redo. Кроме того, периодически выполняется процедура взятия контрольной точки, которая сохраняет в журнале состояние всей системы. ' При плановом откате все произведенные обновления откатываются по журналу.

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

Алгоритм ARIES/NT [RM89] предназначен для осуществления откатов и восстановлений в система с поддержкой вложенных транзакций. В исходном алгоритме рассматривается только вложенность, возникающая в результате распределенности транзакций, при этом транзакции верхнего уровня обрабатываются в соответствии с двухфазный протоколом завершения (2РС).

Все записи журнала, относящиеся к одной транзакции, связаны в обратную цепочку (BW-chaiu). Основным изменением по сравнению с базовым алгоритмом является введение нового типа записей журнала: c-conmitted. Записи этого типа заносятся в журнал в случае завершения порожденной транзакции, причем они добавляются В обратную

цепочку родительской транзакции.

При обновлении записей базы данных никаких изменений по сравнению с базовым методом не происходит, модификации касаются только записей о конце транзакций. При завершении вложенной транзакции, & журнал заносится запись типа c-coanitted, входящая в обратную цепочку ее родительской транзакции. При завершении транзакция верхнего уровня (TL-транзакции) на первом этапе в журнал заносится запись топа prepare п все записи журнала, входящие в эту цепочку, переносятся на постоянный носитель. На второй фазе завершения формируется запись журнала типа end, которая может быть перенесена на постоянный носитель либо сразу же, либо впоследствии, в зависимости от используемого типа двухфазного протокола завершения. После завершения транзакции снимаются все блокировки.

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

Наиболее существенным отличием процедуры отката от уже описанной является необходимость поддерживать сшгсок известных цепочек. Также требуют отдельной обработки записи типа c-committed и prepare.

Восстановление после аварийного завершения также состоит иэ трех фаз: анализа, наката а отката.

На этапе анализа восстанавливается таблица транзакций, таблица страниц и адрес записи журнала, с которой будет начинаться восстановление системы. Отличие от базового алгоритма состоит в особой обработке записей типа prepare, c-comnitted и end. Фаза наката не

отличается от описанной выше. На фазе отката производите! откат транзакций, находившихся в состоянии active. Что касается транзакций в состояли prepared, то вопрос об их откате пли восстановлении решается после восстановления взаимодействия с уравляющей системой. Таким образом, сначала определяется множество BWC-деревьев записей журнала, которые должны быть обработаны, и затем производится последовательный откат в обратном хронологическом порядке.

Система управления буферами поддерживает в полном объеме алгоритм ARIES/NT, при этом в отдельных случаях он может быть упрощен, в частности, нет необходимости поддерживать дополнительные структуры в памяти, требуемые базовым алгоритмом.

Алгоритм ARIES/NT был первоначально разработан только для поддержки классических вложенных транзакций. В такой модели npL аварийном завершения транзакции верхнего уровня все ее подтран-заклпи подлежат откату и, следовательно, не требуют восстановления всей иерархия зависимостей внутри дерева вложенных транзакций. Однако для других моделей транзакций невозможность восстановление этих зависимостей после сбоя системы оказывается существенным ограничением.

В рассматриваемой системе управления буферами роль таблицы транзакций играет дерево активных транзакций. Для того, чтобы его можно было восстановить в процессе рестарта, вводится новый тип записи журнала ne*rtrans. Такая запись формируется при старте под-транзакции и включает идентификатор новой транзакция, ее тип, и идентификатор родительской транзакции. Благодаря наличию в журнале записей типа neirtrana имеется возможность восстановить состояние ДАТ на момент аварийного завершения.

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

журнал просматриваете* последовательно вперед от контрольной точки на предмет войска записей типа nevtrans, на юс основе восстанавливается ДАТ в том воде, в каком оно находилось на момент аварийного завершения. Таблица захватов восстанавливается исходя из анализа фактически произведенных к моменту аварийного завершения системы обновлений. После завершения фазы анализа система становится доступной для выполнения новых пользовательских транзакций.

На фазе нажата записи типа redo считываются в буфера и все обновления воспроизводятся последовательно в прямом направлении. Незавершенные транзакции аннулируются на фазе отката.

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

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

При этом, например, модель ConTVact предполагает возможность продолжать работу от точки прерывания, для чего необходимо иметь восстановленное ДАТ. В открытых вложенных транзакциях, поддерживаемых, в частности, в модели DOM, в случае аварийного завершения может возникнуть необходимость откатить не только незавершенную транзакцию, но и те завершенные транзакш/п, которые использовал я ее промежуточные результаты. Предлагаемая модификация ал-

горитма ARIES лает возможность осуществлять подобные алгоритмы восстановления.

Основные результаты

В диссертационной работе получены следующие основные результаты:

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

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

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

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

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

Библиография

[AA92] D. Agrawal and A. EI Abbadi. A Non-Restrictive Concurrency Control for Object Oriented Databases. In Extending Data Base ' Technology. Pwc. Int. Con/., EDBT-92, vol. 580 of Lect Notes in Comp. Set., p. 469-481, Vienna, Austria, March 1992.

(GMS87J H. Garcia-Molina and K. Salem. SAGAS. In Proc. of ACM SIGMOD Conf., p. 249-259, San Francisco, Calif., May 1987.

(LBB92) Y. Lea, A.K. Elmagarmid, and N. Boudriga. Specification and of transactions for advanced database applications. Inf. 5y.it., 17(2):171-183,1992.

jMHL+92) C. Mohan, D. Haderle, B. Lindsay, H. Pirahcsh, and P. Schwartz. ARIES: A transaction recovery method supporting fine-granularity locking with partial rollbacks using write-ahead logging. ACM Traru. on Database Systems, 17(1):94-162,1992.

[Mos85J J.E.B Moss. Nested Transactions: An Approach to Reliable Distributed Computing. PhD thesis, MIT Press, Cambridge, MA, 1985.

(RM89) K. Rothermel and C. Mohan. ARIES/NT: A recovery method based on write-ahead logging for nested transactions. In Proc. IS conf. VLDB, p. 337-346,1989.

14

Работы автора по теме диссертации

[1] Домбровская Г.Р., Нестерешсо Ю.А., Новиков Б.А. Исследование и разработка методов и средств хранения данных (знаний) для си-стел» управления « машин баз данных (знаний). (заключительный отчет). Л.: ЛГУ, 1990. Гос. per. 01890086701, 92 с.

[2] Домбровская Г.Р., Нестерешсо Ю.А., Новиков Б.А. Система ин- ' теграции неоднородных баз данных. Внутренние структуры данных, поддержка объектов концептуального уровняв структурах хранения данных. Справочный материал. 2700560.00016-01 90 06. ИПИ АН СССР. Москва, 1990. 62 с.

[3} Домбровская Г.Р., Капризкина И.Ю., Нестеренко Ю.А., Новиков Б.А. Исследование « разработка методов и средств хранения данных (знаний) для систем интеграции неоднородных информационных ресурсов, (заключительный отчет). - СПб.: СТОГУ, 1992. 65 с.

[4} H. Dombrowsba, Г. Kaprizkiaa, В. Novikov. Representation and analysis of the SYNTHESIS data structures in tke itorage system.// Труды рабочего семинара "Перспективы развития систем баз данных и информ. систем", М.:ЙПИРАН, 1993. С. 60-68.

(5) Домбровская Г.Р. Поддержка вложенных транзакций на уровне системы хранения в проекте СИНТЕЗ. ТрудьЗ рабочего семинара "Перспективы развития систем баз данных и ияформ. систем", М.:ИПИРАН, 1993. С. 81-85.

[6] Домбровскал Г.Р., Капризкпва, И.Ю., Новиков Б.А. Представление сложных объектов в системах баз данных нового поколения. // Исслед. операций и стат. моделирование. Вып. 6/ Под ред. И.В. Романовского. - СПб.: Изд-во С.-Петербург, ун.-та. 1994. С. 95-110.

[7] Н. Dombrowska. Low-level support and logging for flexible, transactions.//Proceedings of the International Workshop on Advances in Databases and Information Systems. M.: IPIAN, 1994., P. 49-53.