Система хранения безсхемных данных

Термины

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

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

Клетка -

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

Описание модулей

Storage

Block layer

Блок удаляется, когда удаляется последний элемент в нём. Если блок находится в конце файла, размер файла уменьшается на размер этого блока. Если блок не в конце файла, блок остаётся пустым (заполненным нулями), его клетка в block_header отмечается специальным полем, блок добавляется в список пустых блоков в памяти и при следующем запросе на создание блока, с уровня storage, этот блок будет выделен для создания.

Можно сделать также трансляцию "виртуальных" дескрипторов блоков в номер блока в файле хранилища. Таким образом: - Дескриптор клетки будет состоять из "виртуального" дескриптора блока и "виртуального" дескриптора клетки. - Внутри block_header: Клетки с мета-информацией о блоке будут хранить соответствие "виртуальных" дескрипторов блока к местам в файле. - Внутри block_meta: Клетки с мета-информацией о клетке будут хранить соответствие "виртуальных" дескрипторов клетки к отступам внутри соответствующего блока. - Блоки можно свободно перемещать по файлу хранилища, борясь с растущим размером файла из-за пустых блоков.

Заголовочные блоки (block_header)

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

Подробная информация о доступе к блокам через через виртуальные дескрипторы блоков в разделе cell_block

Блоки данных для клеток фиксированного размера (block_data_fix)

Блоки данных для клеток не фиксированного размера (block_data_dyn)

Блоки мета-информации данных (block_meta)

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

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

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

Cell layer

Клетки мета-информации блоков

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

Тестирование

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

Пока библиотека не подключена, тестирование может проводиться вручную с подменой подключаемых к библиотеке "storage" файлов-драйверов с функцией main.