Rework of SRFI-167.
Ordered Key-Value Store (OKVS) is a type of data storage paradigm that can support multi-model database. An OKVS is an ordered mapping of bytes to bytes. It is a more powerful paradigm than a key-value store because OKVS allow to build higher level abstractions without the need to do 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 database systems.
The generics from (okvs) extends the legacy Ordered Key-Value Store interface inherited from Ken Thomson’s DBM, then sleepy cats’ BerkeleyDB, and nowadays FoundationDB, and TiKV to make the implementation of efficient extensions easier thanks to the ability to estimate within a range the count of keys, and the count of bytes.
There is several existing databases that expose an interface similar to okvs, and even more that use an Ordered Key-Value Store (OKVS) as their backing storage.
While okvs interface is lower-level than the mainstream SQL, it also has the advantage of having less moving pieces, and stems from a well-known datastructure, part of every software engineering curriculum, namely binary trees, it makes okvs a good teaching material that has immediate useful applications, including building your own SQL database. Last but not least, okvs pin the current practice of building databases on top of a similar tool.
okvs is used to build many datastructures, called extensions.
Extensions of okvs are counter, bag, set, and multi-mapping. Higher level extensions include Entity-Attribute-Value possibly supported by datalog, Generic Tuple Store (nstore) inspired from Resource Description Framework that can match the query capabilities of SPARQL, and RDF-star, or the Versioned Generic Tuple Store (vnstore), that ease the implementation of bitemporal databases. Also, it is possible to implement a property graph database, ranked set, leaderboard, priority queue. It is possible to implement efficient geometric queries with the help of xz-ordered curves. Vector database indices such as Hierarchical Navigable Small World are also available.
(make-okvs)Return a handle over an ordered key-value store.
(okvs? object)Returns #true if object is an ordered key-value store object returned by make-okvs. Otherwise, returns #false.
(okvs-error? okvs object)Returns #true if object is an error produced by okvs. Otherwise, returns #false.
(okvs-transaction? okvs object)Returns #true if object is a transaction object produced by call-with-okvs-transaction or call-with-okvs-transaction-read-only.
(okvs-handle? okvs object)Returns #true if object satisfy one of the following predicate:
okvs-transaction?okvs-cursor?(call-with-okvs-transaction okvs proc success failure)Describe the extent of the transaction within PROC in case of success success is called with returned values, when an object is raised failure is invoked with the raised objects. Otherwise, If a continuation escape PROC the behavior is unspecified.
(okvs-query handle key [other [offset [limit]]])If only handle, and key are provided, returns the value associated with key, or #false if key is not paired with an object.
If other is provided, returns a generator producing all pairs present in the okvs associated with handle between key, and other in lexicographic order. If key is smaller than other, the generator produce keys in ascending order, if key is bigger than other produce keys in descending order.
(okvs-set! handle key value)Set, or update the object associated with key to value inside the okvs associated with handle.
The modification is only visible to other transactions when the current transaction returns successfully.
(okvs-clear! handle key [other])Clear the pairing, if any, that key has with an object inside the okvs associated with handle.
The modification is only visible to other transactions when the current transaction returns successfully.
(okvs-close okvs)Close the database okvs.
(okvs-empty? handle)Returns #true if the database associated with a handle that is empty. Otherwise, returns #false.
(call-with-okvs-transaction-read-only okvs proc success failure)(okvs-key-max-size handle)Returns the maximum size of a key for the database associated with HANDLE.
(okvs-value-max-size handle)Returns the maximum size of a value of the database associated with HANDLE.
(okvs-cursor? okvs object)Returns #true if object is a cursor object produced by call-with-okvs-cursor.
(make-okvs-parameter default)Returns a procedure that is a parameter bound during the extent of transactions. transaction parameters follow the protocol:
When a transaction parameter is called with one argument that satisfies okvs-transaction?, it returns the current value associated within the ongoing transaction, that is default at the beginning of the transaction, and until the transaction parameter is reset.
When a transaction parameter is called with two arguments, the first must satisfy the predicate okvs-transaction?, the second argument can be anything; that will reset the object associated with the transaction parameter within the ongoing transaction. An immediate call with the same transaction object as only argument.
Calling a transaction parameter outside a transaction is an error.
(okvs-parameterize ((okvs-parameter object) ...) body ...)Binds okvs-parameter ... to object ... while evaluating body ...
(okvs-begin-hook okvs)Returns the SRFI-172 hooks associated with okvs. The begin hook’s procedures are called, when a transaction is started, at the beginning of the transaction, inside the transaction.
(okvs-pre-commit-hook okvs)Returns the SRFI-172 hooks associated with okvs. The pre-commit hook’s procedures are called, at the end of a transaction, before call-with-okvs-transaction or call-with-okvs-transaction-read-only returns, inside the transaction.
(okvs-post-commit-hook okvs)Returns the SRFI-172 hooks associated with okvs. The post-commit hook’s procedures are called, at the end of a transaction, before call-with-okvs-transaction or call-with-okvs-transaction-read-only returns, outside the transaction, after the transaction has succeed to commit.
(okvs-rollback-hook okvs)Returns the SRFI-172 hooks associated with okvs. The rollback hook’s procedures are called, at the end of a transaction, before call-with-okvs-transaction or call-with-okvs-transaction-read-only exit, outside the transaction, after the transaction has failed to commit.
(okvs-approximate-key-count handle [key other])Returns an approximate count of keys inside the okvs associated with handle.
(okvs-approximate-byte-count handle [key other])Returns an approximate count of bytes inside the okvs associated with handle.
(call-with-okvs-cursor handle key proc)(okvs-next cursor)Try to move cursor to the next pairing. If there is a lexicographically a bigger key in the okvs, returns #true. Otherwise, returns #false. It means the cursor is at the end of the key space, and okvs-key or okvs-value will return #false.
(okvs-previous cursor)Try to move cursor to the previous pairing. If there is a lexicographically a smaller key in the okvs, returns #true. Otherwise, returns #false. It means the cursor is at the beginning of the key space, and okvs-key or okvs-value will return #false.
(okvs-key cursor)Returns the key associated with cursor. Returns #false when cursor is at the beginning, or the end of the key space, or when the cursor is not set.
(okvs-value cursor)Returns the value associated with cursor. Returns #false when cursor is at the beginning, or the end of the key space, or when the cursor is not set.