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

РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ПРОБЛЕМ КИБЕРНЕТИКИ

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

ГОНОМАРЕНКО Вера Николаевна

ИССЛЕДОВАНИЕ ПРИНЦИПОВ УПРАВЛЕНИЯ нтот ПАМЯТЬЮ И ТРАНЗАКЦИЯМИ В РЕЛЯЦИОННОЙ СУЩ И РАЗРАБОТКА ПОДСИСТЕМЫ УПРАВЛЕНИЯ ПАМЯТЬЮ И СИНХРОНИЗАЦИЕЙ В РЕЛЯЦИОННОЙ СУБД

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1992 -

Работа выполнена в Институте проблем кибернетики АН России.

Научный руководитель -кандидат фиаико-математических наук, старший научный сотрудник С. Д. Кувнецов.

Официальные оппоненты: доктор фиакко-матемагических науч А А. Калининенко, кандидат физико-математических наук М. Р. Когаловский.

Ведущая организация - Институт прикладной математики им. У. Е Келдыш АН России.

Защита диссертации состоится " Р^.ЧЧЯ^1 1992 г. в Ц " н часов на заседании специализированного совета НООЗ. 78.01 по присуждению ученой степени кандидата фиаико-математических наук в Институте проблем кибернетики АН России по адресу: 11731?, Шсква, ух Вавилова, 37.

С диссертацией можно ознакомиться в библиотеке Института проблем кибернетики АН России.

Автореферат разослан " 1992 г.

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

РОССИЙСКАЯ

rocvpj.-p:- • ь::НКАЯ зййл-'.очекА

..''J-"-;:L.J ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ'

... V "«i „'..I,!!

Актуальность теки.

В конце 70-х поело появления ряда фундаментальных работ по теории реляционной модели данных и реализации в исследовательской лаборатории фирмы IBM экспериментальной реляционной СУБД System R начала нарастать популярность этого подхода к управлению данными. Реляционный подход к управлению базами' данных обладает рядом премущэств: простота и теоретичэасая обоснованность, ненавигационный доступ к данным и т.д. Основным недостатком реляционных систем долгое время считалась их недостаточная эффективность. По мере отработки алгоритмов и структур данных и развития техники оптимизации запросов стало вовможным появление коммерческих реляционных СУБД, которые в настоящее время доминируют на мировом рынке.

Следует отметить особую роль языка реляционных баа данных SQL, который был разработан в рамках проекта System R, а в настоящее время стандартизован и поддерживается во всех современных СУБД.

Реляционная модель данных обладает рядом ограничений, среди которых основными являются обязательность атомарности значений атрибутов отношений, недостаточный уровень семантики, несоответствие непроцедурных языков запросов природе традиционных языков программирования. Ведется ряд работ, направленных на преодоление этих ограничений. В теоретическом плане это семантические и объектно-ориентированные модели данных. Ка практике имеется ряд постреляционных эспериыентальных и даже коммерчески доступных СУБД.

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

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

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

Цель диссертационной работы.

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

Целью диссертационной работы являлось

- исследование принципов построения такой системы,

- анализ и выработка алгоритмов и структур данных,

- реализация системы в среде кластерной операционной системы (КЛОС) И В среде ОС UNIX.

Научная новизна. I Основными новыми результатами являются следующие:

- применение принципов КЛОС при выработке внутренней I структуры ПУДТ;

I - расширение интерфейса ПУДТ мощними "макро"-операциями; | - введение двух уровней синхроиизации транзакций: логичес-j кого, основанного на испольаооании предикатных синхронизационных захватов, и физического, основанного на вахватах страниц;

- введение двух уровней журнализации: ведение .логического , журнала с аалисями уровня интерфейса ПУДТ и микрожурнала о еа-

писями о постраничных изменениях;

. - з -

- введение понятия* микрооперации для управления буфером оперативной памяти;

- применение индексной структуры в виде В-дерева для описания внешней памяти, занимаемой отношениями базы данных;

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

Апробация работы.

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

- на 5-й Всесоюзной конференции по бавам данных и знаний (Львов, 1991);

- на научных семинарах отдела системного программирования (под рук. чл. -кор. АН России Иванникова а П. ) Института проблем кибернетики АН России (1088-1991).

Практическая ценность.

Работа начиналась в рамках проекта КЛОС и была исходно ориентирована на то, чтобы обеспечить основу реляционной СУЩ в . среде этой операционной системы. В настоящее время ПУДТ перенесена в среду ОС UNIX. О использованием ПУДТ ведется работа по созданияю свободно распространяемого SQL-сервера. Если учесть повсеместную потребность в SQL-сервере, работаюздэм в UNIX-среде, а также высокую стоимость коммерчески доступных систем, моего оценить практическую важность диссертационной работы.

Публикации.

Основные результаты опубликованы в 3 работах, список которых помешэн в конце реферата.

Структура диссертации.

Работа состоит из введения, пяти глав, заключения и списка литературы.

- А -

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе приводится обвор научной литературы, относящейся к тематике диссертации.

Структурная организация современных СУЩ является весьма сложной. Она должна поддерживать выполнение всех функций, которыми обладает развитые СУБД, а именно компиляции вапросов, управление транзакциями, обеспечение целостности БД, управление хранимыми данными, восстановление поело сбоев и т.д. Структура каждой СУЩ так или иначе отражает поставленные при ее разработка цеди и выбранные решения. Проводится аналитический обаор структурных компонент таких известных реляционных СУЩ, как System R И DBS.

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

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

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

- б -

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

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

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

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

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

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

- в -

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

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

В обычном режиме работы ПУДТ состоит из шести постоянно присутствующих в подсистеме кластеров: Администратора, Синхронизатора, Логического Журнала, Ыикрожурнала, Буфера и Сортировщика. Количество кластеров-Транзакций в подсистеме соответствует числу одновременно выполняющихся транзакций в подсистеме.

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

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

В интерфейс описываемой подсистемы входят операции сканирования отношения. Имеется три споссСа сканирования отношения. Отношение можно сканировать последовательно в порядке, предопределенном ПУДТ. Можно сканировать отношение в порядке, задаваемом лхАш сус^ствудош индексом на уток отношении. Наконец, можно сканировать отношение в порядке, еада£веюм суп^ствующим на этом отношении фильтром.

С открытии сканаи можно выполнять следующие,операции:

. - 7 -найти следующий ко^тея, выбрать из текущего,

запомнить текущую позицию сканирования,

сделать запомненную позицию текудай,

удалить кортеж, задаваемый текудей позицией сканирова-

ния,

- модифицировать кортеж, задаваемый текущей позицией сканирования,

- закрыть сканирование.

В лабор "макро"-операций входят следующие операции:

- отфильтровать отношение,

- удалить кортежи, удовлетворяющие условию,

- модифицировать кортежи, удовлетворяющие условию,

- вставить в отношение набор кортежей другого отношения, удовлетворяющих условию,

- породить отсортированный фильтр в соответствии с заданным условием.

Операция вставки кортежей в отношение:

- вставить кортеж.

Сортировка и теоретико-множественные операции над отсортированными временными объектами:

- отсортировать временный объект.

Допускаются теоретико-множественные операции над отсортированными временными объектами: объединение, пересечение и раа-ность. Для отсортированных временных отношений допускается операция эквисоединения, т.е. соединение с предикатом равенства.

Операции, связанные с изменением схемы БД:

- создать постояное или врешнное отношение,

- создать фильтр,

- создать индекс,

- уничтожить временный объект,

- уничтожить постоянное отношение,

- уничтожить индекс.

Операция изменения схемы отношения:

- добавить полл к судаствуюшрму отношению.

- 8 -

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

- утановить контрольную точку,

- откатить транзакцию до указанной контрольной точки.

Операция вавервения транзакции:

- вавершть транзакции.

Интерфейс подсистемы реализуется в кластере-транзакции.

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

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

БД, с которой манипулирует ПУДТ, располагается в одном или нескольких сегментах - файлах внешней памяти со страничной организацией.

Все файлы-сегменты одной ВД должны быть размещены в одном справочнике (его имя является именем БД) и иметь в нем стандартные предопределенные имена (номера сегментов).

Различается три типа сегшнтов: ссгшнты журналов, рабочий сегмент и восстанавливаемые сегмента Для каждого типа сегментов ПУДТ поддерживает разные структуры хранения.

Основная часть БД - постоянные отнесения и индексы - хранится в восстанавливаешь сегментах. При атом каждое отношнне располагается в одном сегменте, в этом же сегиэнте находится ого описатель и eco индексы, определенные» на данном отношении.

Рабочий пстмонт БД используется для размеарния временных объемов транзакции (ьременных отношений и фильтров). При сортировке используется буфера из пула ПУДТ и рабочая внесшая память, в качестве кот с pal} используется память того же рабочего сегмента.

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

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

Организация В-дерева описателей страниц очень близка к организации индексов. Для работы с этими структурами используется общий набор программ.

Каждое отношение идентифицируется Ыс1'ом своего кортеш -описателя в отношении-каталоге. Схема отношения каталога предопределена и фиксирована, и поэтому ато служебное отношение не нуждается в наличии описателя. Отношение-каталог тем самым не имеет идентификатора и потому к нему невозможен доступ черев интерфейс 'ПУДТ.

В-деревья индексов включают страницы двух типов: промежуточные и листовые. В промежуточных страницах находятся значения ключей и ссылки на страницы непосредственно подчиненного уровня. Листовые значения содержат значения ключей и для каждого значения - список и<1'ов кортежей, упорядоченный по возрастанию значений ИсГов. Листовые страницы связаны в однонаправленный список, соответствующий возрастанию ключа

Ключи индексов могут бьггь простыми (соответствовать одному полю отношения) и составными (соответствовать нескольким полян отношения в их заданной последовательности). Для всех допусти-

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

Страница данных предназначена для хранения кортежей отношения. Кортеж располагается только в одной странице. Уникальный идентификатор кортежа - и<1 - состоит из номера страницы в сегменте и идентификатора кортежа внутри страницы (Мс1 идентифицирует кортеж в пределах данного сегмента1). Внутренний идентификатор кортежа (в пределах страницы) есть номер указателя на кортеж; этот указатель хранится в той же странице. Т1с1 кортежа не может меняться, пока этот кортеж существует.

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

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

Структура стргишц, содержащих фильтры, очень проста: это просто линейный список иа'ов.

ПУДГ поддсфливаот пул буферов - сегментов в смысле КЛОС (в среде СО 1ШХ также непельаук.тоя рагделменш сегменты).

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

Управлением пулсм буферов ПУДГ ведает специальный компонент ПУДТ - кластор-Буфер.

С точки зрения синхр.жкзгаш кластер-Буфор поддиржиьает некоторую разновидность двухфазного протокола захватов на уров-

ве страниц данных.

Кластерная операционная система дает возможность реаливо-вать кластер-Буфер таким оврагом, что он удовлетворяет запросы на страницу от всех кластеров-Транзакций, ранее ео захвативших (конечно, при вопросе о разделяемой памяти имеются п виду только захваты на чтение). Аналогичные возможности обеспечиваются механизмом управления разделяемой памятью ОС UNIX.

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

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

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

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

Чтобы не накладывать какие-либо ограничения на порядок

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

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

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

Четвертая глава посвящена синхронизации транзакций верхнего уровня, логической синхронизации транзакций. Особенностью основанного на двухфазном протоколе синхронизационных захватов механизма синхронизации является то, что захватываются не физические объекты базы Данных, а логические условия - предикаты. Сама ндоя предикатных захватов не является новой, но'Несмотря на очевидные преимущества, предикатные захваты мало где исполь-вуются по причине сложности реализации. В ПУДГ удалось добиться эффективной реализации этого механизма с поддержанием аппарата распознавания и разрушения тупиков.

В данной системе синхронизация транзакций происходит на уровне ПУДГ, в которой ничего но известно про предикаты исходных аш1росое. На этом уровне в роли "языка запросов" выступает набор операций интерфейса ПУДТ, а в атом интерфейсе допускаются только очень простые предикаты, представленные в виде логических формул, в которых через конъюнкцию соединены прсстие условия на пеля отношения.

Логической синхронизацией управляет в подсистеме кластер-Синхронизатор. Захваты объектов в ПУДГ могут выполняться в двух режимах: совместном (на чтение) и монопольном (на обновление).

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

• - 13 -

вахвата. Элементарный захват является конъюнкцией диапазонов значений атрибутов отношения. Общий захват является дизъюнкцией элементарных захватов.

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

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

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

Описываются примитивы кластера-Синхронизатора.

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

- 14 -

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

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

Приводятся примитиву кластеров логического журнала и микрожурнала. Описываются структуры отракиц отих журналов.

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

)

- 16 -ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

1. На основе применения принципов и методологии кластерной операционной системы (КЛОС), следуя идеям объектно-ориентированного подхода в программировании, выработана структура подсистемы управления данными и транзакциями (ПУДТ), предназначенной для реализации SQL-ориентированной СУБД. Подсистема состоит из статически определенного набора функционально-ориентированных активных кластеров, взаимодействующих путем обмена сообщениями.

2. Базирование на простых механизмах обмена сообщениями и использовании разделяемых сегментов оперативной памяти, ограниченные требования к внешней среде и использование для программирования стандартного варианта языка Си позволили достичь высокого уровня мобильности ПУДТ. Задуманная как машнно-незави- ' симая система в среде КЛОС, ПУДТ легко и естественно была перенесена в среду ОС UNIX, причем в UNIX-реализации используются только те средства ядра ОС UNIX, которые присутствуют во всех современных вариантах этой ОС.

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

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

4. Для обеспечения сериалиэацни транзакций на должном уровне их изолированности в ПУДТ применен двухфазный протокол синхронизационных предикатных захватов с обнаружением и разрушением возможных синхронизационных тупиков. Для увеличения се-пени асинхрокности транзакций при синхронизации доступа к стра-

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

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

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

7. Применение индексной структуры в виде В-дерева для описания внешней памяти, занимаемой отношениями базы данных.

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

9. Подсистема управления данными и транзакциями была реализована ъ опытном варианте в первой версии КЛОС на ГСЭВЫ "Электроника В£". Цгш; ресурсы этой ГОРЛ позволили использовать ее только для отладки и проверки правильности основных решений. В дальнейшем ПУДТ вместе с КЛОС была перенесена на более

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

10. Перенос ПУДТ в среду 00 UNIX System V был также произведен на рабочей станции "Веста". В настоящее время произведен еще один перенос ПУДГ на ЭШ типа VAX, работающую под управлением ОС ULTRIX (разработанный на фирме DEC аналог UNIX BSD 4.3). Это продемонстрировало мобильнбсть ПУДГ в разнородной UNIX-среде.

11. В настоящее время с использованием ПУДТ реализуется проект свободно распространяемого SQL-сервера, предназначенного для использования в локальных сетях UNIX-машин. При работе в среде ОС UNIX для доступа к ПУДТ используется механизм гнезд (sockets). Это позволяет использовать ПУДГ как в локальном варианте (когда прикладные программы и ПУДТ работают в одной компьютере), так и в удаленном режиме (когда прикладные программы обращаются к компьютеру-серверу череа средства локальной сети). Для прикладных систем, естественно, обеспечивается прозрачность доступа.

* ft А

Особую признательность автор выражает научному руководителю С. Д. Кузнецову за постоянную помощь в работе и написании диссертации и а П. Иванникову за внимание и поддержку проекта

Я разработке проекта ПУДГ, выработке основных алгоритмов, протоколов и структур данных участвовали И. Б. Бурдонов, С. Д. Кузнецов, П.Е Лэгвин, С.Е Шпекторов, Е& К&ин. В практическом написании программ принимали участие Н. Е Игнатьева и С. Е Шпекторон. Всем им автор приносит свою искреннюю благодарность.

Автор таюю искренне благодарит А. С. Косачева, Г. В. Копи-това и Е. Г. Березина за консультации по операционной системе КЛОС и приятную совместную работу.

- 18 -

ПУБЛИКАЦИИ ТО МАТЕРИАЛАМ РАБОТЫ

1. И. Е Бурдонов, Е а Игнатьева, С. Д. Кузнецов, Е Е Пономаре нко, С. Е Шпекторов. Функции и организация подсистемы управления памятью и синхронизацией реляционной СУБД. В сб. "Вопросы кибернетики. Программное обеспечение высокопроизводительных систем". ЬЬ иад-во НСК АН СССР. - 1991. - с. 71-97.

2. С. Д. Кузнецов, ЕЕ Пономаренко. Модульная мобильная система управления данными и транзакциями. Труды 5-ой Всесоюзной конференции по базам данных и знаний. - Львов, 23-27 сект. 1991, УИиМ, 1991, N 7, с. 37-45.

3. ЕЕ Игнатьева, С.Д. Кузнецов, ЕЕ Пономаренко. Реализация подсистемы управления данными м транзакциями в ОС КЛОС. В сб. "Вопросы кибернетики. Программное обеспечение высокопроизводительных систем", к иад-во НСК АН СССР. В печати.