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

XML-ориентированная СУБД Sedna [1-3], разрабатываемая в Институте системного программирования РАН, призвана решать задачи хранения большого объема XML-данных (до 1Гб и более) и эффективного управления этими данными, включая задачи поиска, изменения и трансформации данных. В рамках этого проекта предложен ряд оригинальных решений, включая метод представления XML-данных во внешней памяти (доложен на одном из семинаров Московской секции ACM SIGMOD) и управление памятью СУБД, что является темой данного доклада.

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

• Указатели должны существовать в адресном пространстве большого размера, достаточного для идентификации всех сущностей базы данных (XML-документы и служебная информация), плюс должен оставаться резерв на будущее. Таким образом, следует ориентироваться на адресное пространство размером не менее терабайта;
• В силу того, что переход по указателю от одного элемента данных к другому является очень частой операцией, необходимо реализовать разыменование указателя максимально эффективно;
• Особенность внутреннего представления данных такова, что, несмотря на локальность расположения данных (например, интересующие нас данные располагаются в нескольких страницах), переключения между страницами данных (то есть смена страницы, с которой производится работа в данный момент) происходят очень часто. Соответственно, минимизация накладных расходов, связанных с переключением страниц, является важнейшим требованием;
• В случае использования различного представления указателя в оперативной и внешней памяти необходимо минимизировать накладные расходы, связанные с “подменой” указателей (pointer swizzling) при перемещении страницы из внешней памяти в оперативную и обратно, а в идеале полностью исключить эти накладные расходы.

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

Метод организации адресного пространства, используемый в XML-ориентированная СУБД Sedna, является надстройкой над механизмом виртуальной памяти ОС. Несмотря на закрытость ядра современных ОС для пользовательских программ, существуют средства, которые позволяют программисту реализовать базовые механизмы виртуальной памяти самостоятельно [4]. Именно эти средства используются для реализации метода слоистой организации адресного пространства, который используется в XML-ориентированной СУБД Sedna. Основная идея метода заключается в эмуляции расширенного адресного пространства над виртуальным адресным пространством, предоставляемым ОС. При этом расширенное адресное пространство представляет собой набор слоев, каждый из которых отображается на виртуальное адресное пространство ОС. Указатель в слоистом адресном пространстве состоит из двух частей: номер слоя и смещение относительно начало слоя, которое, по сути, является обычным указателем адресного пространства ОС.

Основные преимущества рассматриваемого метода слоистой организации адресного пространства СУБД состоят в следующем:

• Эмуляция 64-х разрядного адресного пространства на стандартной 32-х разрядной архитектуре;
• Операция разыменования указателя в слоистом адресном пространстве производится почти так же быстро, как операция разыменования обычного C/C++ указателя;
• Полностью отсутствует необходимость в “подмене” указателей, так как представления указателя в оперативной и внешней памяти совпадают.

Данный метод организации адресного пространства может быть реализован на любой современной операционной системе. В частности, в докладе рассматриваются реализационные аспекты данного метода для операционных систем Windows 2000/XP и Linux.

Литература:

1. Grinev, M., Fomichev, A., Kuznetsov, S., Antipin, K., Boldakov, A., Lizorkin, D., Novak, L., Rekouts, M., Pleshachkov, P.: Sedna: A Native XML DBMS, http://www.ispras.ru/~grinev/mypapers/sedna.pdf
2. Fomichev, A., Grinev, M., Kuznetsov, S.: Descriptive Schema Driven XML Storage, http://www.ispras.ru/~grinev/mypapers/sedna-storage.ps
3. Максим Гринев, Сергей Кузнецов, Андрей Фомичев. Особенности СУБД Sedna. XML-СУБД Sedna: технические особенности и варианты использования //Открытые системы. - №8. - 2004.
4. Wilson, P., Kakkad, S.: Pointer Swizzling at Page Fault Time: Efficiently and Compatibly Supporting Huge Address Spaces on Standard Hardware, Proceedings of Workshop on Object Orientation and Operating Systems, Paris, France, 1992.