(import (okvs2))
Rework of SRFI-167.
Change log
- 2023-10-06: initial publication at hyper.dev;
- 2024-01-12: various changes published at https://amirouche.dev:
- rename library from
(okvs) to
(okvs2);
- small editing improvements;
- in
okvs-query replace generator with a list;
- rename the okvs parameter concept back to okvs variable;
- rename
okvs-clear! to okvs-remove!
Issues
- Missing implementation that can be durable and
bigger-than-memory;
- Describe intended behavior with a formal language;
Abstract
Ordered Key-Value Store (OKVS) is a data storage paradigm that can
support a multi-model database. An OKVS is an ordered mapping of bytes
to bytes. It makes different trade-offs compared to key-value store
paradigm to allow to build higher level abstractions more efficiently.
An OKVS will keep the key-value pairs sorted by the key lexicographic
order. OKVS systems provide 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 databases.
The procedures from (okvs2) extend the legacy Ordered
Key-Value Store interface inherited from Ken Thomson’s DBM, then sleepy
cats’ BerkeleyDB, and nowadays LMDB, 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.
Rationale
There are several databases that expose an interface similar to
(okvs2), and even more that use an Ordered Key-Value Store
as their backing storage.
While (okvs2) interface is lower-level than the defacto
industry standard for data durability SQL, it also has the advantage of
having less moving pieces, and stems from a well-known data-structure,
part of every software engineering curriculum, namely binary trees, it
makes (okvs2) a good teaching material that has immediate
useful applications, including building your own SQL database. Last but
not least, (okvs2) pin the current practice of building
databases on top of a similar tool.
(okvs2) is used to build many low to high-level
data-structures, called extensions, and can support a versatile
multi-model database.
Extensions of (okvs2) are counter, bag, set, multi-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, and full-text search.
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 possible.
Reference
Minimal
(make-okvs filepath)
Return a handle over an ordered key-value store stored at
filepath.
(okvs? object)
Returns #true if object is an ordered
key-value store object as returned by make-okvs. Otherwise,
returns #false.
(okvs-error? okvs object)
Returns #true if object is an error
produced by (okvs2). Otherwise, returns
#false.
(okvs-in-transaction okvs proc [failure [success]])
Begin a transaction against the database, and execute
PROC. PROC is called with first and only
argument an object that satisfy okvs-transaction?. In case
of error, rollback the transaction and execute FAILURE with
the error object as argument. The default value of FAILURE
re-raise the error with raise. Otherwise, executes
SUCCESS with the returned values of PROC. The
default value of SUCCESS is the procedure
values.
When the transaction begin, okvs-in-transaction must
call the procedures associated with okvs-begin-hook.
Just before the transaction commit, okvs-in-transaction
must call the procedures associated with
okvs-pre-commit-hook.
Just after the transaction commit is a success,
okvs-in-transaction must call the procedures associated
with okvs-post-commit-hook.
Just before calling FAILURE,
okvs-in-transaction must call the procedures associated
with okvs-rollback-hook.
okvs-in-transaction describes the extent of the atomic
property, the A in ACID, of changes against
the underlying database. A transaction will apply all database
operations in PROC or none: all or nothing. When
okvs-in-transaction returns successfully, the changes will
be visible for future transactions, and implement durability, D in ACID.
In case of error, changes will not be visible to other transactions in
all cases. Regarding isolation, each transactions do their change as if
those were done on separate copy of the database; when a transaction is
commited its changes are visible for all future transactions, but not
those that are still in progress.
TODO: what about read-write and write-write conflicts? https://en.wikipedia.org/wiki/Write%E2%80%93write_conflict
TODO: keep it unspecified?
(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?
(okvs-query transaction key [other [offset [limit]]])
Rationale: (okvs2) dropped okvs-ref, and
the (okvs2) range procedures to focus attention of the
users on this procedure that has a name that is explicit about the
intended use. That has the drawback that there is most of necessarily a
dispatch based on the comparison of KEY and
OTHER. That is a performance vs. developper experience
trade-offs which advantage is making its use more obvious, while
reducing the apparent (okvs2) surface while covering the
same use-cases.
If only transaction, 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 list of all pairs
present in the database associated with transaction between
key, and other in lexicographic order. If
key is smaller than other, the list is
produced with keys in ascending order, if key is bigger
than other produce the keys are in descending order.
In any case, the biggest bytevector, key or
other is excluded from the list.
(okvs-set! transaction key value)
Set, or update the database related to transaction with
the association key and value.
The modification is only visible to other transactions when the
current transaction returns successfully.
(okvs-remove! transaction key [other])
Clear the database related to transaction with the
association, if any, that key is part of. If
other is provided, it can be bigger or smaller than
key, the database associations are cleared between
key, and other. The biggest bytevector is
excluded from that operation.
The modification is only visible to other transactions when the
current transaction returns successfully.
(okvs-close okvs)
Close the database.
Base
(okvs-empty? okvs)
Returns #true if the database associated with a
handle that is empty. Otherwise, returns
#false.
(okvs-in-transaction-read-only okvs proc [success [failure]])
(okvs-key-max-size okvs)
Returns the maximum size of a key for the related database.
(okvs-key-value-max-size okvs)
Returns the maximum size of an association of the related
database.
(okvs-cursor? okvs object)
Returns #true if object is a cursor object
produced by call-with-okvs-cursor.
(okvs-cursor-transaction cursor)
(make-okvs-variable default)
Returns a procedure that is a variable bound during the extent of
transactions. Transaction variables protocol is the following:
When a transaction variable is called with one argument that
satisfies okvs-transaction?, it returns the current value
associated within the transaction, that is default at the
beginning of the transaction, and until the transaction variable is
reset for that transaction;
When a transaction variable is called with two arguments, the
first must satisfy the predicate okvs-transaction?, the
second argument can be any scheme object; that will reset the object
associated with the transaction variable within the
transaction.
Calling a transaction variable outside a transaction is an error that
satisfy okvs-error?.
(okvs-variable ((okvs-variables objects) ...) body ...)
Binds okvs-variables to thei respective
objects while evaluating body.
(okvs-begin-hook okvs)
Returns the SRFI-172 hooks. 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. The pre-commit hook’s procedures are
called within the transaction, at the end of the transaction.
(okvs-post-commit-hook okvs)
Returns the SRFI-172 hooks. The post-commit hook’s procedures are
called outside the transaction, after the transaction was commit before
a call to the success procedure.
(okvs-rollback-hook okvs)
Returns the SRFI-172 hooks. The rollback hook’s procedures are called
outside the transaction, after the transaction was commit before a call
to the failure procedure.
(okvs-approximate-key-count transaction [key other])
Returns an approximate count of keys inside the okvs associated with
transaction.
(okvs-approximate-byte-count transaction [key other])
Returns an approximate count of bytes inside the okvs associated with
transaction.
(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 database, 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.
The cursor is marked as moving forward.
(okvs-previous cursor)
Try to move cursor to the previous pairing. If there is
a lexicographically a smaller key in the database, 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.
The cursor is marked as moving backward.
(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.
