Реферат: Объектно-ориентированная СУБД (прототип)

Операция	Семантика (все операции работают с текущим каналом)
IBS	Чтение байта из канала
OBS	Запись байта в канал
GOTO	Переход по адресу в канале
@GOTO	Переход по смещению в канале
UPSIZE	Выделить доп. память в конце канала и встать на ее начало
DEFRAG	Сделать виртуальную память непрерывной на уровне нижнего канала (т.е. однофрагментной)

Начало виртуальной памяти соответствует нулевому значению TEKADR. Доступ осуществляется через операции позиционирования (GOTO и @GOTO), чтения байта (IBS) и записи байта (OBS). Остальные функции, реализуются через них (например, чтение длинного слова). К памяти может быть применена функция UPSIZE с аргументом, содер­жащим необходимое количество байт для выделения. Память может гаранти­ро­ванно вы­деляться до заполнения всей выделенной длины. При исчерпании выделенной длины, делается запрос к нижестоящему уровню о выделении дополнительной памяти. Если та­кой запрос применяется к каналу ниже 5-го, соответствующего дисковому файлу, файл увеличивается в размере, если его выделен­ная длина исчерпана. Если увеличение раз­мера файла невозможно из-за нехватки дискового пространства, то, в случае невоз­можности выделения памяти за счет упаковки, возбуждается ситуация NOMEMORY. При попытке доступа за пределы определенной вирту­альной памяти (например, чтение после расположения данных), возни­кает ситуация OUTDATA.

3.4 Система управления кэшированием объектов

Самостоятельное кэширование данных – неотъемлемая черта любой СУБД. Кэш состоит из двух частей: очереди кэшируемых объектов и памяти для кэшируемых объектов. Память для кэшируемых объектов – это оперативная память, в которую объект загружается. В этой памяти могут располагаться только те объекты, идентификаторы которых находятся в очереди кэшируемых объектов. Удаляемый из очереди объект выгружается в дисковую память. В данной дипломной работе все создаваемые объекты являются стабильными (Persistent), т.е. они обязательно сохраняются на диске и могут быть использованы после открытия базы данных для использования.

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

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

Наиболее популярны следующие пять алгоритмов замещения:

1.   Случайное замещение (СЗ): с равной вероятностью может быть замещен любой объект,

2.   Раньше пришел – раньше ушел (РПРУ, или FIFO): замещается объект дольше всех находившийся в оперативной памяти,

3.   Замещение наиболее давно использовавшегося объекта (НДИ),

4.   Алгоритм рабочего комплекта (РК): хранятся в памяти только те объекты, к которым было обращение в течении времени t, назад от текущего момента,

5.   Лестничный алгоритм (ЛЕСТН): в списке объектов при обращении к объекту он ме­ня­ется местами с объектом, находящемся ближе к голове списка. При обращении к от­сутствующему в ОП объекту объект, находящийся в последней позиции вытесняет­ся.

Для алгоритма замещения желательно, чтобы он обладал двумя отчасти противоречивыми свойствами: с одной стороны, он должен сохранять в ОП объекты к которым обращения происходят наиболее часто, с другой – быстро обновлять содер­жимое ОП при смене множества рабочих объектов.

Например, алгоритм РПРУ эффективен только в отношении быстрого обновления ОП, он не выделяет в списке объектов объекты, обращения к которым происходят чаще, чем к остальным. Алгоритм НДИ также позволяет быстро обновлять содержимое ОП. Однако последовательность одиночных обращений достаточной длины к объектам, находящимся во ВП, вытеснит из ОП все объекты, к которым, в среднем, обращения происходят чаще всего.

 В [1] описывается класс многоуровневых алгоритмов замещения c, которые поз­воляют решить эту проблему. Они зависят от конечного числа параметров и при адап­тивном подборе этих параметров соединяют свойство быстрого обновления части ОП со свойством сохранения в ОП тех объектов, которые наиболее часто запра­ши­ва­ются.

В дипломной работе решено использовать алгоритм замещения из класса c, при следующих параметрах: лимит времени нахождения объекта в ОП отсутствует, размеры подсписков на всех уровнях одинаковы, параметр l=1 (это соответствует алгоритму замещения НДИ для объектов всех подсписков; если i – положение объекта в подсписке, и i £ l, то при обращении к нему применяется алгоритм РПРУ, иначе НДИ).

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

Для определения подмножества объектов кэша, подлежащих вытеснению, можно применить алгоритм решения задачи о рюкзаке. Если бы все объекты имели одинаковую длину, без этого можно было бы обойтись. Хотя алгоритм решения задачи о рюкзаке NP-сложен, решение можно компактно записать в виде рекурсивного алгоритма, нахо­дя­ще­го решение за счет применения принципа динамического программирования Беллмана. Такой способ наиболее эффективен, когда размер кэша составляет 32 объекта, посколь­ку множество выбранных объектов можно представить битовыми полями в длинном слове. При большем размере кэша возрастают потери памяти и быстродействия, и во­зникает вопрос о месте расположения данных промежуточных вызовов. Рекурсивный вызов в среде ДССП требует малых затрат ресурсов, а время расчета окупается за счет времени обмена с внешней памятью, работа с которой много медленнее, чем с оператив­ной.

3.5 Система управления журнализацией и восстановлением

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

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

Для журнализации избран подход, примененный в СУБД Postgres, разработанной в университете г.Беркли, Калифорния под руководством М.Стоунбрейкера, как наиболее простой в реализации и предоставляющий полезные возможности, недоступные в базах данных с обычным типом журнализации (см. [23]). В этой системе, во-первых, не ведется обычная журнализация изменений базы данных, и мгновенно обеспечивается корректное состояние базы данных после перевызова системы с утратой состояния оперативной памяти. Во-вторых, система управления памятью поддерживает истори­ческие данные. Запросы могут содержать временные характеристики интересующих объектов. Реализационно эти два аспекта связаны.

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

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

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

1.   Канал объекта в кэше

2.   Канал объекта на диске

3.   Канал данных объекта в кэше

4.   Канал истории изменений объекта на диске

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

3.6 Принципы реализации механизма согласованного управления

Область действия операции

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

Областью действия операции на объекте являются:

Данные состояния объекта, входные параметры операции, системные объекты, а также все объекты, обладающие определенным поведением, если это поведение является объектом, над которым выполняется операция.

Воздействие операции

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

Множество запросов QS(opi(O)) определяется рекурсивно как QS(opi(O)) = LocalQS(opi(O)) È GlobalQS(opi(O)), где

·     LocalQS = Æ, если нет собственных ivj из O "запрошенных" операцией opi. {O}, иначе.

·     GlobalQS =

opi , посылает сообщение к Os.

Аналогично определяются можества создания модификации и удаления операции opi на объекте O.

Множество замен определяется как объединение множеств создания, модифи­ка­ции и удаления. Конфликт операций – выполнение одного из следующих условий:

1.   US(opi(O)) Ç US(opj(O')) ¹ Æ

2.   QS(opi(O)) Ç US(opj(O')) ¹ Æ

3.   US(opi(O)) Ç QS(opj(O')) ¹ Æ

Пользовательские транзакции можно рассматривать как операции над специ­альным объектом базы данных.

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

Объектно-ориентированное расписание

Для увеличения производительности СУБД, некоторые операции могут взаимодействовать друг с другом в базе данных. Некоторые из этих операций могут выполняться на одном объекте. Совместное выполнение многих операций (псевдо­параллельность) может приводить к произвольному чередованию операций (или их шагов). Порядок чередования называется объектно-ориентированным расписанием. Так как "пользовательские транзакции" являются только операциями на специальном объекте, ОО-расписание можно определить на этом объекте как пару (S,<расп), где S – множество всех шагов (как локальных, так и глобальных), а <расп – частичный порядок на множестве шагов в S. Глобальные шаги в S – это результат обращения операций к другим объектам, и шаги основанные на результате этих обращений также  включаются в расписание.

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

В работе [19] утверждается, что расписание Sch для T на специальном объекте является корректным объектно-ориентированным расписанием, если:

1.   Расписание состоит только из шагов операций, порожденных воздействием T, и каждый из этих шагов выполняется точно раз в Sch.

2.   В расписании сохраняется отношение порядка выполнения шагов операций для всех транзакций.

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

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

Этот критерий корректности заменяет собой критерий сериализуемости в ООБД.

Эквивалентность расписаний

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

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

Влияние наличия позднего связывания на  составление расписания операций в ООБД

Если объекты, которые доступны различным транзакциям, заранее известны, задача механизма согласованного управления относительно проста. Априорная инфор­мация облегчает статичное определение конфликтующих операций; следовательно, стра­тегия управления чередованием операций может быть сформулирована. Однако, позд­нее связывание (late binding), характерная черта объектно-ориентированных систем, приводит к трудности предварительного определения объектов доступа. При отсутствии такого знания, одним из выходов является блокировка некоторых транзакций до тех пор, пока вид объектов доступа не станет известен. Однако, для продолжительных (long-duration) транзакций (например, запись звука в мультимедийной БД) , такая блокировка может привести к слишком большому времени ожидания.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8