Ordered Key-Value Store
   HOME

TheInfoList



OR:

An Ordered Key-Value Store (OKVS) is a type of data storage paradigm that can support
multi-model database In the field of database design, a multi-model database is a database management system designed to support multiple data models against a single, integrated backend. In contrast, most database management systems are organized around a single data ...
. An OKVS is an ordered mapping of bytes to bytes. It is a more powerful paradigm than Key-Value Store because OKVS allow to build higher level abstractions without the need to do full scans. An OKVS will keep the key-value pairs sorted by the key lexicographic order. OKVS systems provides different set of features and performance trade-offs. Most of them are shipped as a library without network interfaces, in order to be embedded in another process. Most OKVS support ACID guarantees. Some OKVS are distributed databases. Ordered Key-Value Store found their way into many modern database systems including
NewSQL NewSQL is a class of relational database management systems that seek to provide the scalability of NoSQL systems for online transaction processing (OLTP) workloads while maintaining the ACID guarantees of a traditional database system. Many e ...
database systems.


History

The origin of Ordered Key-Value Store stems from the work of Ken Thompson on
dbm DBM or dbm may refer to: Science and technology * dBm, a unit for power measurement * DBM (computing), family of key-value database engines including dbm, ndbm, gdbm, and Berkeley DB * Database Manager (DBM), a component of 1987's ''Extended Edi ...
in 1979. Later in 1991, Berkeley DB was released that featured a B-Tree backend that allowed the keys to stay sorted. Berkeley DB was said to be very fast and made its way into various commercial product. It was included in Python standard library until 2.7. In 2009, Tokyo Cabinet was released that was superseded by Kyoto Cabinet that support both transaction and ordered keys. In 2011, LMDB was created to replace Berkeley DB in
OpenLDAP OpenLDAP is a free, open-source implementation of the Lightweight Directory Access Protocol (LDAP) developed by the OpenLDAP Project. It is released under its own BSD-style license called the OpenLDAP Public License. LDAP is a platform-independe ...
. There is also Google's LevelDB that was forked by Facebook in 2012 as
RocksDB RocksDB is a high performance embedded database for Key-value database, key-value data. It is a fork of Google's LevelDB optimized to exploit many multi-core processor, CPU cores, and make efficient use of fast storage, such as solid-state drives ...
. In 2014,
WiredTiger WiredTiger is a NoSQL, Open Source extensible platform for data management. It is released under version 2 or 3 of the GNU General Public License. WiredTiger uses MultiVersion Concurrency Control ( MVCC) architecture. MongoDB acquired WiredTiger I ...
, successor of Berkeley DB was acquired by
MongoDB MongoDB is a source-available cross-platform document-oriented database program. Classified as a NoSQL database program, MongoDB uses JSON-like documents with optional schemas. MongoDB is developed by MongoDB Inc. and licensed under the Serve ...
and is since 2019 the primary backend of MongoDB database. Other notable implementation of the OKVS paradigm are Sophia and SQLite3 LSM extension. Another notable use of OKVS paradigm is the multi-model database system called
ArangoDB ArangoDB is a free and open-source native graph database system developed by ArangoDB Inc. ArangoDB is a multi-model database system since it supports three data models (graphs, JSON documents, key/value) with one database core and a unified q ...
based on RocksDB. Some
NewSQL NewSQL is a class of relational database management systems that seek to provide the scalability of NoSQL systems for online transaction processing (OLTP) workloads while maintaining the ACID guarantees of a traditional database system. Many e ...
databases are supported by Ordered Key-Value Stores.
JanusGraph JanusGraph is an open source, distributed graph database under The Linux Foundation. JanusGraph is available under the Apache License 2.0. The project is supported by IBM, Google, Hortonworks and Grakn Labs. JanusGraph supports various storage ...
, a property graph database, has both a Berkeley DB backend and FoundationDB backend.


Key concepts


Lexicographic encoding

There are algorithms that encode basic data types (boolean, string, number) and composition of those data types inside sorted containers (tuple, list, vector) that preserve their natural ordering. It is possible to work with an Ordered Key-Value Store without having to work directly with bytes. In FoundationDB, it is called the tuple layer.


Range query

Inside an OKVS, keys are ordered, and because of that it is possible to do range queries. A range query allow to retrieve all keys between two keys such as all keys that are fetched are ordered.


Subspaces


Key composition

One can construct key spaces to build higher level abstractions. The idea is to construct keys, that takes advantage of the ordered nature of the top level key space. When taking advantage of the ordered nature of the key space, one can query ranges of keys that have particular pattern.


Denormalization

Denormalization, as in, repeating the same piece of data in multiple subspace is common practice. It allows to create secondary representation, also called indices, that will allow to speed up queries.


Higher level abstractions

The following abstraction or databases were built on top Ordered Key-Value Stores: * Timeseries database, * Record Database, also known as Row store databases, they behave similarly to what is dubbed
RDBMS A relational database is a (most commonly digital) database based on the relational model of data, as proposed by E. F. Codd in 1970. A system used to maintain relational databases is a relational database management system (RDBMS). Many relation ...
, * Tuple Stores, also known as Triple Store or Quad Store but also Generic Tuple Store, * Document database, that mimics MongoDB API, * Full-text search *Geographic Information Systems *Property Graph *Versioned Data *Vector space database for Approximate Nearest Neighbor All those abstraction can co-exist with the same OKVS database and when ACID is supported, the operations happens with the guarantees offered by the transaction system.


Feature matrix

# SQLite LSM extension's transactions can be nested # SQLite LSM extension support multiple readers, and only a single writer that do not block readers


See also

*
Key–value_database A key–value database, or key–value store, is a data storage paradigm designed for storing, retrieving, and managing associative arrays, and a data structure more commonly known today as a ''dictionary'' or ''hash table''. Dictionaries contai ...
*
Wide Column Store A wide-column store (or extensible record store) is a type of NoSQL database.Wide Column Stores
*
Multi-model database In the field of database design, a multi-model database is a database management system designed to support multiple data models against a single, integrated backend. In contrast, most database management systems are organized around a single data ...


References

{{Database models Types of databases Database theory Databases Associative arrays Data management Data analysis NoSQL Structured storage Transaction processing