Некоторое время назад мне потребовалось использовать функциональность mongodb в виде подключаемой динамической библиотеки в нативном C/C++ приложении. Причины были просты:
Попытка использовать mongodb в виде динамической библиотеки в моем случае натолкнулась на следующие барьеры:
Упорный поиск в интернете свободных и похожих по функциональности альтернатив не принес существенных результатов, что и подвигло меня взять в руки шашку и реализовать открытый продукт, схожий в базовой функциональности с mongodb, который можно было бы использовать в качестве библиотеки как в открытых так и в закрытых C/C++ приложениях, а также в приложениях на платформе node.js. Пытаться реализовать подобный проект с нуля и в сжатые сроки было бы весьма самонадеянно. Нужна была хорошо зарекомендовавшая себя основа под подходящей лицензией. Поэтому неудивительно, что этой основой стал LGPL продукт широко известного в узких кругах японца Микио Хирабаяши (Mikio Hirabayashi) под названием Tokyo Cabinet. Не мудрствуя лукаво проект получил имя EJDB как производное от embedded json database.
Какая требовалась функциональность от этой библиотеки:
Что было использовано из tokyocabinet:
В этом списке в скобках приведены ссылки на элементы api tokyocabinet. Далее, я буду приводить ссылки на api tokyocabinet кратко, как например под tchdb подразумеваем api хеш таблицы tokyocabinet или саму хеш базу в зависимости от контекста.
Физически EJDB это:
JSON объекты в EJDB представлены в формате BSON (Binary JSON). Для работы с BSON используется несколько модифицированная версия BSON API из C драйвера mongodb (ссылка). Замечу, что BSON, по моему мнению, очень эффективный формат для представления любых иерархических данных со строковыми ключами и типизированными значениями как с точки зрения удобства навигации так и производительности, и отлично может подойти для внутреннего представления данных в обычных С/C++ программах.
Записи в коллекции EJDB хранятся в табличной базе tctdb. Коротко, база tctcdb является хеш-таблицей, где значение каждой записи это словарь в котором ключ(c1..cN) это имя колонки в таблице, и соответствующие им данные (v1..vN) . Каждая запись в табличной базе может иметь свой набор колонок. Данные разных записей принадлежащие к колонкам с одинаковым именами могут быть проиндексированы в B+ дереве tcbdb ссылаясь на первичные ключи основной хеш таблицы. Что проиллюстрировано на рисунке:
BSON объекты в коллекции EJDB представлены в очень простом виде:
Где в качестве первичных ключей используются уникальные двенадцатибайтные идентификаторы UUID для JSON объектов. Объекты сериализованные в BSON формат хранятся в колонке с кратким и звучным именем $. Подобная модель допускает возможность связи произвольной мета информации с записями коллекции, путем добавления новых колонок, например списков доступа (ACL) на уровне записей, или данных статистики доступа к записям, но оставим это для следующих релизов.
Алгоритм выборки записей без использования индексов очень простой: последовательно выбираем из коллекции записи и для каждой записи берем BSON данные объекта из $ колонки и определяем соответствие объекта запросу. Несмотря на наивную простоту этот способ выбора записей по запросу весьма быстр для коллекций в пределах миллиона записей на современном железе.
Запросы к коллекциям формируются в JSON формате, в основе своей они очень похожи или идентичны запросам mongodb.
В запросах указываются условия на возможные значения ключей искомых JSON объектов, ключи определяются их именами, поскольку структура JSON может быть иерархической, для идентификации ключа используются иерархические имена. Например для JSON объекта:
условие на соответствие имени wife в запросе, определяется как:
Для краткости, иерархический путь до ключа в JSON объекте иногда будем упоминать как имя ключа или английским термином fieldpath.
Приведу несколько кратких примеров, о том какие запросы поддерживаются:
Как и в табличной базе tctdb, для значений ключей в BSON объектов с одинаковыми именами ключей можно создать B+ tree индекс на значения ключей.
Как и в табличной базе tctdb, для значений ключей в BSON объектов с одинаковыми именами ключей можно создать B+ tree индекс на значения ключей.
При выполнении запроса осуществляется поиск подходящего индекса, который может ускорить операцию поиска. Алгоритм выбора эмпирический, однако с большей долей вероятности будет выбран индекс с наибольшей селективность или индекс поля по которому осуществляется сортировка результатов запроса. Как и в mongodb для запроса используется только один индекс.
Поиск по элементам массивов в JSON объектов или на вхождении терма в строку можно оптимизировать с помощью инвертированного индекса, основанного на B+ деревьях.
Например для объекта:
можно создать инвертированный индекс как на поле tags или строку textbuffer.
На языке C это будет выглядеть следующим образом:
Эти индексы будут использоваться например в таких запросах:
В многопоточной среде, в работе коллекциям EJDB используются read-write блокировки на уровне коллекции в отличие от mongodb где, как мне известно, глобальная read-write блокировка работает на всю базу. Также поддерживается модель выполнения транзакций на уровне коллекций.
Надеюсь этот краткий обзор был интересным, а сама библиотека EJDB будет полезной.
- Приложение необходимо распространять как единое целое, не инсталлируя сетевой сервер mongodb как отдельный продукт.
- В приложении нет необходимости взаимодействия с СУБД через сетевые интерфейсы и сокеты, когда, как работа с библиотекой в едином адресном пространстве программы гораздо быстрее.
Попытка использовать mongodb в виде динамической библиотеки в моем случае натолкнулась на следующие барьеры:
- На сегодняшний день не существует сборки mongodb как подключаемой динамической библиотеки.
- И самое главное: mongodb распространяется под лицензией AGPL, что не позволяет использовать код этой системы в приватном софте. Хотя с 10gen можно и договориться.
Упорный поиск в интернете свободных и похожих по функциональности альтернатив не принес существенных результатов, что и подвигло меня взять в руки шашку и реализовать открытый продукт, схожий в базовой функциональности с mongodb, который можно было бы использовать в качестве библиотеки как в открытых так и в закрытых C/C++ приложениях, а также в приложениях на платформе node.js. Пытаться реализовать подобный проект с нуля и в сжатые сроки было бы весьма самонадеянно. Нужна была хорошо зарекомендовавшая себя основа под подходящей лицензией. Поэтому неудивительно, что этой основой стал LGPL продукт широко известного в узких кругах японца Микио Хирабаяши (Mikio Hirabayashi) под названием Tokyo Cabinet. Не мудрствуя лукаво проект получил имя EJDB как производное от embedded json database.
Какая требовалась функциональность от этой библиотеки:
- Хранение коллекций JSON объектов
- Mongodb-like запросы относительно коллекций
- Поддержка транзакций на уровне коллекций
- Связка с NodeJS
Что было использовано из tokyocabinet:
- B+ деревья (tcbdb.h)
- Хеш таблицы (tchdb.h)
- Табличная база (tctdb.h)
- Структуры данных и утилиты (tcutil.h)
В этом списке в скобках приведены ссылки на элементы api tokyocabinet. Далее, я буду приводить ссылки на api tokyocabinet кратко, как например под tchdb подразумеваем api хеш таблицы tokyocabinet или саму хеш базу в зависимости от контекста.
Структура данных EJDB
Физически EJDB это:
- Мета-файл в котором хранится информация об доступных коллекциях. Это табличная база tctdb.
- Для каждой коллекции:
- Мета-файл с данными об индексах коллекции и настройках коллекции (tctdb)
- Файл c данными JSON объектов коллекции (tctdb)
- Набор B-Tree индексов для полей JSON объектов (tcbdb)
JSON объекты в EJDB представлены в формате BSON (Binary JSON). Для работы с BSON используется несколько модифицированная версия BSON API из C драйвера mongodb (ссылка). Замечу, что BSON, по моему мнению, очень эффективный формат для представления любых иерархических данных со строковыми ключами и типизированными значениями как с точки зрения удобства навигации так и производительности, и отлично может подойти для внутреннего представления данных в обычных С/C++ программах.
Записи в коллекции EJDB хранятся в табличной базе tctdb. Коротко, база tctcdb является хеш-таблицей, где значение каждой записи это словарь в котором ключ
BSON объекты в коллекции EJDB представлены в очень простом виде:
Где в качестве первичных ключей используются уникальные двенадцатибайтные идентификаторы UUID для JSON объектов. Объекты сериализованные в BSON формат хранятся в колонке с кратким и звучным именем $. Подобная модель допускает возможность связи произвольной мета информации с записями коллекции, путем добавления новых колонок, например списков доступа (ACL) на уровне записей, или данных статистики доступа к записям, но оставим это для следующих релизов.
Запросы
Алгоритм выборки записей без использования индексов очень простой: последовательно выбираем из коллекции записи и для каждой записи берем BSON данные объекта из $ колонки и определяем соответствие объекта запросу. Несмотря на наивную простоту этот способ выбора записей по запросу весьма быстр для коллекций в пределах миллиона записей на современном железе.
Запросы к коллекциям формируются в JSON формате, в основе своей они очень похожи или идентичны запросам mongodb.
В запросах указываются условия на возможные значения ключей искомых JSON объектов, ключи определяются их именами, поскольку структура JSON может быть иерархической, для идентификации ключа используются иерархические имена. Например для JSON объекта:
условие на соответствие имени wife в запросе, определяется как:
{"family.wife.name" : "Sally"} Для краткости, иерархический путь до ключа в JSON объекте иногда будем упоминать как имя ключа или английским термином fieldpath.
Приведу несколько кратких примеров, о том какие запросы поддерживаются:
- Неравенства для численных типов:
{"age" : {"$gt" : 18}} - Принадлежность промежутку значений
{"age" : {"$bt" : [18, 30]}} - Принадлежность элементов массива к множеству:
{"tags" : {"$in" : ["one", "two", "three"]} - Сравнение на наличие слова в строке или в массиве:
{"words" : {"$strand" : ["one", "two"]}}В данном примере это означает, что строковое поле «words» должно содержать слова «one» и «two». О значении '$stror' можно догадаться. - Сравнение без учета регистра:
{"name" : {"$icase" : "петров"}} - А также операции модификации данных: $set установить поле объекта, а с помошью $inc инкриминировать значение числового поля.
Индексы
Как и в табличной базе tctdb, для значений ключей в BSON объектов с одинаковыми именами ключей можно создать B+ tree индекс на значения ключей.
Как и в табличной базе tctdb, для значений ключей в BSON объектов с одинаковыми именами ключей можно создать B+ tree индекс на значения ключей.
При выполнении запроса осуществляется поиск подходящего индекса, который может ускорить операцию поиска. Алгоритм выбора эмпирический, однако с большей долей вероятности будет выбран индекс с наибольшей селективность или индекс поля по которому осуществляется сортировка результатов запроса. Как и в mongodb для запроса используется только один индекс.
Поиск по элементам массивов в JSON объектов или на вхождении терма в строку можно оптимизировать с помощью инвертированного индекса, основанного на B+ деревьях.
Например для объекта:
можно создать инвертированный индекс как на поле tags или строку textbuffer.
На языке C это будет выглядеть следующим образом:
Эти индексы будут использоваться например в таких запросах:
- Поиск объектов массив tags которых содержит строковые элементы: tag2 или tag3:
{"tags" : {"$in" : ["tag2", "tag3"]}} - Поиск объектов строка textgbuffer которых содержит слова word3 и word4:
{"textbuffer" : {"$strand" : ["word3", "word4"] }}
Конкурентный доступ к данным
В многопоточной среде, в работе коллекциям EJDB используются read-write блокировки на уровне коллекции в отличие от mongodb где, как мне известно, глобальная read-write блокировка работает на всю базу. Также поддерживается модель выполнения транзакций на уровне коллекций.
Надеюсь этот краткий обзор был интересным, а сама библиотека EJDB будет полезной.
- Домашняя страница проекта: http://ejdb.org
- Проект на GitHub