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.
home.