Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Ordered Key-Value Store
open-in-new
<h2 id="history">History</h2> <p>The origin of Ordered Key-Value Store stems from the work of <a href="/facts/Ken_Thompson/KQtrw9YM">Ken Thompson</a> on <a href="/facts/DBM_(computing)/CgBHvMEz">dbm</a> in 1979. Later in 1991, <a href="/facts/Berkeley_DB/lWwNrclz">Berkeley DB</a> was released that featured a <a href="/facts/B-tree/IHE2l8GR">B-Tree</a> 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.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> In 2009, Tokyo Cabinet was released that was superseded by <a href="/facts/Kyoto_Cabinet/hp55qvsz">Kyoto Cabinet</a> that support both transaction and ordered keys. In 2011, <a href="/facts/Lightning_Memory-Mapped_Database/ELYDjKj1">LMDB</a> was created to replace Berkeley DB in <a href="/facts/OpenLDAP/Uy8pfH3P">OpenLDAP</a>. There is also Google's <a href="/facts/LevelDB/ffG5drbg">LevelDB</a> that was forked by Facebook in 2012 as <a href="/facts/RocksDB/SveC2lEp">RocksDB</a>. In 2014, <a href="/facts/WiredTiger/PeVM5Tcl">WiredTiger</a>, successor of Berkeley DB was acquired by <a href="/facts/MongoDB/9myQKGoY">MongoDB</a> and is since 2019 the primary backend of MongoDB database. </p><p>Other notable implementation of the OKVS paradigm are Sophia<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> and SQLite3 LSM extension. Another notable use of OKVS paradigm is the multi-model database system called <a href="/facts/ArangoDB/72NoJrPM">ArangoDB</a><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> based on RocksDB. </p><p>Some <a href="/facts/NewSQL/6Hvrzn0R">NewSQL</a> databases are supported by Ordered Key-Value Stores. <a href="/facts/JanusGraph/cBufGvdp">JanusGraph</a>, a property graph database, has both a Berkeley DB backend and <a href="/facts/FoundationDB/FTr6n5Hy">FoundationDB</a> backend. </p> <h2 id="key-concepts">Key concepts</h2> <h3>Lexicographic encoding</h3> <p>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.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> </p> <h3>Range query</h3> <p>Inside an OKVS, keys are ordered, and because of that it is possible to do range queries. A range query retrieves all keys between two specified keys, ensuring that the fetched keys are returned in a sorted order. </p> <h3>Subspaces</h3> <h3>Key composition</h3> <p>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. </p> <h3>Denormalization</h3> <p>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. </p> <h2 id="higher-level-abstractions">Higher level abstractions</h2> <p>The following abstraction or databases were built on top Ordered Key-Value Stores: </p> <ul><li>Timeseries database,</li> <li>Record Database,<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> also known as Row store databases, they behave similarly to what is dubbed <a href="/facts/Relational_database/pEKGmJLy">RDBMS</a>,</li> <li>Tuple Stores, also known as <a href="/facts/Triplestore/k0e2ua9S">Triple Store</a> or Quad Store but also Generic Tuple Store,<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a><a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a></li> <li>Document database,<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> that mimics MongoDB API,</li> <li>Full-text search<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a></li> <li>Geographic Information Systems<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a></li> <li>Property Graph<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a></li> <li>Versioned Data<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a></li> <li>Vector space database for Approximate Nearest Neighbor<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a></li></ul> <p>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. </p> <h2 id="feature-matrix">Feature matrix</h2> Comparison of several Ordered Key-Value Stores<table><tbody><tr><th>OKVS</th><th>License</th><th>Transactions</th><th>Distributed</th><th>In-memory</th><th>Multiple threads</th><th>Multiple processes</th><th>Nested Transactions</th></tr><tr><td><a href="/facts/Berkeley_DB/lWwNrclz">Berkeley DB</a></td><td>AGPL</td><td>Yes</td><td>No</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td></tr><tr><td><a href="/facts/FoundationDB/FTr6n5Hy">FoundationDB</a></td><td>Apache</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td><td>No</td></tr><tr><td><a href="/facts/DBM_(computing)/CgBHvMEz">GDBM</a></td><td>GPL</td><td>?</td><td>?</td><td>?</td><td>?</td><td>?</td><td>?</td></tr><tr><td><a href="/facts/Kyoto_Cabinet/hp55qvsz">Kyoto Cabinet</a></td><td>GPL</td><td>Yes</td><td>No</td><td>No</td><td>?</td><td>No</td><td>No</td></tr><tr><td><a href="/facts/LevelDB/ffG5drbg">LevelDB</a></td><td>Apache</td><td>No</td><td>No</td><td>No</td><td>?</td><td>No</td><td>No</td></tr><tr><td><a href="/facts/Lightning_Memory-Mapped_Database/ELYDjKj1">LMDB</a></td><td>OpenLDAP</td><td>Yes</td><td>No</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td></tr><tr><td><a href="/facts/RocksDB/SveC2lEp">RocksDB</a></td><td>Apache</td><td>Yes</td><td>No</td><td>No</td><td>Yes</td><td>No</td><td>No</td></tr><tr><td><a href="/facts/SQLite/1PwYzIft">SQLite</a> (LSM extension)</td><td>Public domain</td><td>Yes</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td></tr><tr><td><a href="/facts/TiKV/8mLVvEfR">TiKV</a></td><td>Apache</td><td>Yes</td><td>Yes</td><td>No</td><td>Yes</td><td>Yes</td><td>No</td></tr><tr><td><a href="/facts/Tkrzw/hp55qvsz">Tkrzw</a></td><td>Apache</td><td>Yes</td><td>No</td><td>?</td><td>Yes</td><td>No</td><td>?</td></tr><tr><td><a href="/facts/Tokyo_Cabinet/hp55qvsz">Tokyo Cabinet</a></td><td>LGPL</td><td>Some</td><td>No</td><td>?</td><td>Yes</td><td>?</td><td>?</td></tr><tr><td><a href="/facts/WiredTiger/PeVM5Tcl">WiredTiger</a></td><td>GPL</td><td>Yes</td><td>No</td><td>Yes</td><td>Yes</td><td>No</td><td>No</td></tr></tbody></table> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Key%25E2%2580%2593value_database/Yee8EIGE">Key–value database</a></li> <li><a href="/facts/Wide-column_store/qL6MGfhr">Wide-column store</a></li> <li><a href="/facts/Multi-model_database/cQHomRjT">Multi-model database</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>"11.11. bsddb — Interface to Berkeley DB library — Python 2.7.17 documentation". docs.python.org. Retrieved 2020-01-16. <a href="https://docs.python.org/2/library/bsddb.html" target="_blank">https://docs.python.org/2/library/bsddb.html</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>"sophia - modern transactional key-value/row storage library". sophia.systems. Retrieved 2020-01-16. <a href="http://sophia.systems/" target="_blank">http://sophia.systems/</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>"Comparing new RocksDB and MMFiles storage engines". ArangoDB. Retrieved 2020-01-16. <a href="https://www.arangodb.com/why-arangodb/rocksdb-storage-engine/" target="_blank">https://www.arangodb.com/why-arangodb/rocksdb-storage-engine/</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>"Python API — FoundationDB 6.2". apple.github.io. Retrieved 2020-01-19. <a href="https://apple.github.io/foundationdb/api-python.html#api-python-tuple-layer" target="_blank">https://apple.github.io/foundationdb/api-python.html#api-python-tuple-layer</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>A record-oriented store built on FoundationDB., FoundationDB, 2020-01-16, retrieved 2020-01-17 <a href="https://github.com/FoundationDB/fdb-record-layer" target="_blank">https://github.com/FoundationDB/fdb-record-layer</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>"Generic Tuple Store Database". srfi.schemers.org. Retrieved 2020-01-17. <a href="https://srfi.schemers.org/srfi-168/" target="_blank">https://srfi.schemers.org/srfi-168/</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>"Generic Tuple Store". GitHub. <a href="https://github.com/amirouche/hoply/" target="_blank">https://github.com/amirouche/hoply/</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>A document data model on FoundationDB, implementing MongoDB® wire protocol: FoundationDB/fdb-document-layer, FoundationDB, 2019-12-09, retrieved 2020-01-17 <a href="https://github.com/FoundationDB/fdb-document-layer" target="_blank">https://github.com/FoundationDB/fdb-document-layer</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>meilisearch/MeiliSearch, MeiliSearch, 2021-06-19, retrieved 2021-06-19 <a href="https://github.com/meilisearch/MeiliSearch" target="_blank">https://github.com/meilisearch/MeiliSearch</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>"6.1. GeoMesa Index Structure — GeoMesa 1.3.1 Manuals". www.geomesa.org. Retrieved 2020-01-19. <a href="https://www.geomesa.org/documentation/1.3.1/user/datastores/index_structure.html" target="_blank">https://www.geomesa.org/documentation/1.3.1/user/datastores/index_structure.html</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>"The JanusGraph FoundationDB Storage Adapter - Ted Wilmes, Expero Inc". www.youtube.com. Retrieved 2020-01-17. <a href="https://www.youtube.com/watch?v=rQM_ZPZy8Ck" target="_blank">https://www.youtube.com/watch?v=rQM_ZPZy8Ck</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>"Lightning Talk: Entity Store: A FoundationDB Layer for Versioned... - Stephen Pimentel, - YouTube". www.youtube.com. Retrieved 2020-01-17. <a href="https://www.youtube.com/embed/16uU_Aaxp9Y?autoplay=1&feature=oembed&wmode=opaque" target="_blank">https://www.youtube.com/embed/16uU_Aaxp9Y?autoplay=1&feature=oembed&wmode=opaque</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>meilisearch/arroy, Meilisearch, 2024-08-05, retrieved 2024-08-06 <a href="https://github.com/meilisearch/arroy" target="_blank">https://github.com/meilisearch/arroy</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> </ol>