Заказанный магазин ключей-значений
Упорядоченное хранилище ключей-значений (OKVS) — это тип парадигмы хранения данных, который может поддерживать многомодельную базу данных . ОКВС — это упорядоченное отображение байтов в байты. Это более мощная парадигма, чем хранилище значений ключей , поскольку OKVS позволяет создавать абстракции более высокого уровня без необходимости полного сканирования. ОКВС будет хранить пары ключ-значение, отсортированные по ключевому лексикографическому порядку. Системы ОКВС предоставляют различный набор функций и компромиссы в производительности. Большинство из них поставляются в виде библиотек без сетевых интерфейсов для встраивания в другой процесс. Большинство ОКВС поддерживают гарантии ACID . Некоторые ОКВС представляют собой распределенные базы данных . Упорядоченное хранилище ключей-значений нашло свое применение во многих современных системах баз данных, включая системы баз данных NewSQL .
История
[ редактировать ]Происхождение упорядоченного хранилища ключей-значений связано с работой Кена Томпсона над dbm в 1979 году. Позже, в 1991 году, Berkeley DB была выпущена , в которой использовался бэкэнд B-Tree , который позволял ключам оставаться отсортированными. Говорят, что Berkeley DB была очень быстрой и нашла применение в различных коммерческих продуктах. Он был включен в стандартную библиотеку Python до версии 2.7. [1] В 2009 году был выпущен Токийский кабинет, который был заменен Киотским кабинетом , который поддерживает как транзакционные, так и заказанные ключи. В 2011 году LMDB был создан для замены Berkeley DB в OpenLDAP . Существует также LevelDB от Google , который был разветвлен Facebook в 2012 году как RocksDB . В 2014 году WiredTiger , преемник Berkeley DB, был приобретен MongoDB и с 2019 года является основным сервером базы данных MongoDB.
Другой заметной реализацией парадигмы ОКВС является София. [2] и расширение SQLite3 LSM. Еще одним заметным применением парадигмы OKVS является многомодельная система баз данных под названием ArangoDB. [3] на основе RocksDB.
Некоторые базы данных NewSQL поддерживаются упорядоченными хранилищами ключей и значений. JanusGraph , база данных графов свойств, имеет как серверную часть Berkeley DB, так и серверную часть FoundationDB .
Ключевые понятия
[ редактировать ]Лексикографическое кодирование
[ редактировать ]Существуют алгоритмы, которые кодируют основные типы данных (логические, строковые, числовые) и композицию этих типов данных внутри отсортированных контейнеров (кортеж, список, вектор), сохраняющих их естественный порядок. Можно работать с упорядоченным хранилищем ключей-значений без необходимости работать напрямую с байтами. В FoundationDB это называется уровнем кортежа. [4]
Запрос диапазона
[ редактировать ]Внутри ОКВС ключи упорядочены, поэтому можно выполнять запросы по диапазону. Запрос диапазона позволяет получить все ключи между двумя ключами, например, все выбранные ключи упорядочены.
Подпространства
[ редактировать ]Ключевой состав
[ редактировать ]Можно создавать ключевые пространства для построения абстракций более высокого уровня. Идея состоит в том, чтобы создать ключи, которые используют преимущества упорядоченного характера пространства ключей верхнего уровня. Воспользовавшись упорядоченностью пространства ключей, можно запрашивать диапазоны ключей, имеющих определенный шаблон.
Денормализация
[ редактировать ]Денормализация, например, повторение одного и того же фрагмента данных в нескольких подпространствах, является обычной практикой. Это позволяет создавать вторичное представление, также называемое индексами, что позволит ускорить запросы.
Абстракции более высокого уровня
[ редактировать ]Следующая абстракция или базы данных были построены на основе упорядоченных хранилищ ключей и значений:
- база данных таймсерий,
- База данных записей, [5] также известные как базы данных с хранилищем строк, они ведут себя аналогично тому, что называется RDBMS .
- Хранилища кортежей, также известные как Triple Store или Quad Store, а также Generic Tuple Store, [6] [7]
- База данных документов, [8] который имитирует API MongoDB,
- Полнотекстовый поиск [9]
- Географические информационные системы [10]
- Граф свойств [11]
- Версионные данные [12]
Вся эта абстракция может сосуществовать с одной и той же базой данных OKVS, и когда поддерживается ACID, операции выполняются с гарантиями, предлагаемыми системой транзакций.
Матрица функций
[ редактировать ]| ОКВС | Лицензия | Транзакции | Распределенный | В памяти | Несколько потоков | Несколько процессов |
|---|---|---|---|---|---|---|
| Беркли ДБ | АГПЛ | Да | Нет | Нет | да | да |
| ПроводнойТигр | лицензия GPL | Да | Нет | Да | да | нет |
| УровеньБД | Апач | Нет | Нет | Нет | нет | |
| Киото Кабинет | лицензия GPL | Да | Нет | Нет | нет | |
| РоксДБ | Апач | Да | Нет | Нет | да | нет |
| Расширение SQLite LSM | Общественное достояние | Да 1 | Нет | Да | да 2 | да 2 |
| ТиКВ | Апач | Да | Да | Нет | да | да |
| FoundationDB | Апач | Да | Да | Да | да | да |
- Транзакции расширения SQLite LSM могут быть вложенными.
- Расширение SQLite LSM поддерживает несколько читателей и только одну запись, которая не блокирует считыватели.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ «11.11. bsddb — Интерфейс к библиотеке Berkeley DB — Документация Python 2.7.17» . docs.python.org . Проверено 16 января 2020 г.
- ^ «София — современная транзакционная библиотека хранения ключей/значений/строк» . София.системы . Проверено 16 января 2020 г.
- ^ «Сравнение новых механизмов хранения RocksDB и MMFiles» . АрангоДБ . Проверено 16 января 2020 г.
- ^ «API Python — FoundationDB 6.2» . apple.github.io . Проверено 19 января 2020 г.
- ^ Ориентированное на записи хранилище, построенное на FoundationDB. , FoundationDB, 16 января 2020 г. , получено 17 января 2020 г.
- ^ «Общая база данных хранилища кортежей» . srfi.schemers.org . Проверено 17 января 2020 г.
- ^ «Общий магазин кортежей» . Гитхаб .
- ^ Модель данных документа в FoundationDB, реализующая проводной протокол MongoDB®: FoundationDB/fdb-document-layer , FoundationDB, 09 декабря 2019 г. , получено 17 января 2020 г.
- ^ meilisearch/MeiliSearch , MeiliSearch, 19 июня 2021 г. , получено 19 июня 2021 г.
- ^ «6.1. Структура индекса GeoMesa — Руководства по GeoMesa 1.3.1» . www.geomesa.org . Проверено 19 января 2020 г.
- ^ «Адаптер хранилища JanusGraph FoundationDB — Тед Уилмс, Expero Inc» . www.youtube.com . Проверено 17 января 2020 г.
- ^ «Молниеносный доклад: Entity Store: слой FoundationDB для версий… — Стивен Пиментел, — YouTube» . www.youtube.com . Проверено 17 января 2020 г.