SRFI 167: Ordered Key Value Store
Amirouche Boubekki
This SRFI is currently in final status. Here is an
explanation of each status that a SRFI can hold. To provide
input on this SRFI, please send email to srfi-167@nospamsrfi.schemers.org. To
subscribe to the list, follow these
instructions. You can access previous messages via the
mailing list archive.
engine-pack.
Add clarifications.)Both SRFI 167 and SRFI 168 contain infelicities. [For more details, see this message.] Both SRFIs are being perfected outside the SRFI process. In the meantime, it is preferable to use these SRFIs as inspiration rather than an interface that will stand the tests of time.
This library describes an interface for an ordered key-value store that is suitable for implementing a storage engine for the generic tuple-store SRFI. It maps cleanly to existing ordered key-value databases that may or may not provide transactions.
Ordered key-value stores offer a powerful set of simple and elegant primitives to build database abstractions. The SRFI 168: Generic Tuple Store is an example of such abstraction. Others are possible. A standard interface for such databases will allow more people to experiment with databases in Scheme.
While it has not been Scheme's forte to power databases, the recent appearance of several ordered key-value stores make the idea of building databases with Scheme more applicable as the performance concerns are solved by lower-level languages.
The author argues that getting started with data management systems with ordered key-value stores is easier to the mind and also reflects the modern industrial practice that builds (distributed) databases systems possibly with SQL support on top of ordered key-value stores. Otherwise said, this SRFI should offer grounds for apprentices to learn about data storage. It will also offer a better story (the best?) for data durability in Scheme implementations.
This SRFI does not overlap with existing SRFIs and complements SRFI 168: Generic Tuple Store.
The SRFI is composed of two library modules. The first is the
engine library and the second is the
okvs library.
engineTo allow the user of an okvs abstraction (also
known as a layer) to swap implementations easily, it must be
written in terms of the procedures specified in this section.
The engine is a simple record of okvs
procedures that must be passed to the constructor of layers. It must
be shared between okvs implementations.
(make-engine open close in-transaction ref set delete range-remove range prefix-range hook-on-transaction-begin hook-on-transaction-commit pack unpack)Return an engine record instance.
(engine? obj)Return #t if OBJ is an engine record
instance. Otherwise, it returns #f.
(engine-open engine okvs [config])Call the procedure okvs-open.
(engine-close engine okvs [config])Call the procedure okvs-close.
(engine-in-transaction engine okvs proc [failure [success [make-state [config]]]])Call the procedure okvs-in-transaction.
(engine-ref engine okvs key)Call the procedure okvs-ref.
(engine-set! engine okvs key value)Call the procedure okvs-set!.
(engine-delete! engine okvs key)Call the procedure okvs-delete!
(engine-range-remove! engine okvs start-key start-include? end-key end-include?)Call the procedure okvs-range-remove!
(engine-range engine okvs start-key start-include? end-key end-include? [config])Call the procedure okvs-range.
(engine-prefix-range engine okvs prefix [config])Call the procedure okvs-prefix-range.
(engine-hook-on-transaction-begin engine okvs)Call the procedure okvs-hook-on-transaction-begin.
(engine-hook-on-transaction-commit engine okvs)Call the procedure okvs-hook-on-transaction-commit.
(engine-pack engine . key)Call a packing procedure that allows to encode some scheme types into bytevectors preserving their natural order. The supported Scheme types are implementation dependent.
(engine-unpack engine bytevector)Call an unpacking procedure that will decode a bytevector encoded with the above pack procedure into a Scheme object.
A okvs is a mapping that may or may not support transactions. Keys are lexicographically ordered bytevectors. Values are bytevectors.
The following specification defines two disjoint types:
okvs is a handle to the data storagetransaction is a handle to a currently running
transactionIn the following, CONFIG is always an optional
parameter that is an association list. Some configuration
options are specified to ease portability. If an
implementation doesn't recognize an option, it is an
error. Default values are implementation dependent. It is an
error if this argument is not an association list.
(okvs-open home [config])Return an okvs object.
HOME describes the the location of the database. It can be
an address or a directory.
CONFIG might contain the following options:
| key | description |
|---|---|
'cache |
an integer describing cache size in bytes. |
'create? |
create the database if it does not exist. |
'memory? |
whether to keep data only in memory. |
'wal? |
whether to enable write-ahead-log. |
'read-only? |
whether to open the database in read-only mode. |
(okvs? obj)Return #t if OBJ is a okvs,
and #f otherwise.
(okvs-close okvs [config])Close OKVS. CONFIG is optional. In the
case where it is provided, it must be an association list. It is
implementation dependent.
(make-default-state)Return a SRFI
125: Intermediate hash table
with a comparator returned by the
SRFI
128: Comparators procedure
(make-default-comparator).
(okvs-transaction? obj)Return #t if OBJ is a okvs transaction,
and #f otherwise.
(okvs-transaction-state transaction)Return the state associated with TRANSACTION. See
okvs-in-transaction for a description of what is
the transaction state.
(okvs-in-transaction okvs proc [failure [success [make-state [config]]]])Start a transaction against OKVS and pass the
transaction object as argument to PROC. When
PROC returns, the transaction is committed and
okvs-in-transaction passes whatever PROC
returned to the SUCCESS procedure. If PROC
raises an exception, the transaction is rolled back and FAILURE
is called with the exception condition. By default FAILURE
is raise and SUCCESS is values.
The transaction must be associated with a newly created state
object as returned by MAKE-STATE. The default value
of MAKE-STATE is make-default-state. The
transaction state can be retrieved during the transaction
using the procedure okvs-transaction-state.
No CONFIG options are specified. An
implementation may or may not support some implementation
specific options.
(okvs-ref okvs-or-transaction key)Return the bytevector associated with KEY
bytevector using OKVS-OR-TRANSACTION. If there is no such
key, return #f.
OKVS-OR-TRANSACTION can be an okvs object or an okvs-transaction.
In the case where OKVS-OR-TRANSACTION is an okvs object,
the implementation should execute the operation, preferably
without starting a transaction. If the underlying engine doesn't
allow one to execute operations without a transaction, the operation should
handle starting and committing the transaction.
(okvs-set! okvs-or-transaction key value)Associate KEY bytevector with VALUE
bytevector using OKVS-OR-TRANSACTION.
OKVS-OR-TRANSACTION can be an okvs object or an okvs-transaction.
In the case where OKVS-OR-TRANSACTION is an okvs object,
the implementation should execute the operation, preferably
without starting a transaction. If the underlying engine doesn't
allow one to execute operations without a transaction, the operation should
handle starting and committing the transaction.
(okvs-delete! okvs-or-transaction key)Delete the pair associated with KEY bytevector
using OKVS-OR-TRANSACTION.
OKVS-OR-TRANSACTION can be an okvs object or an okvs-transaction.
In the case where OKVS-OR-TRANSACTION is an okvs object,
the implementation should execute the operation, preferably
without starting a transaction. If the underlying engine doesn't
allow one to execute operations without a transaction, the operation should
handle starting and committing the transaction.
(okvs-range-remove! okvs-or-transaction start-key start-include? end-key end-include?)Remove all pairs in the specified range.
OKVS-OR-TRANSACTION can be an okvs object or an okvs-transaction.
In the case where OKVS-OR-TRANSACTION is an okvs object,
the implementation should execute the operation, preferably
without starting a transaction. If the underlying engine doesn't
allow one to execute operations without a transaction, the operation should
handle starting and committing the transaction.
(okvs-range okvs-or-transaction start-key start-include? end-key end-include? [config])Return a SRFI 158 generator of key-value pairs where keys
are between START-KEY bytevector and END-KEY,
possibly including the boundaries depending on START-INCLUDE?
and END-INCLUDE?. The stream must be lexicographically
ordered. CONFIG is optional.
OKVS-OR-TRANSACTION can be an okvs object or an okvs-transaction.
In the case where OKVS-OR-TRANSACTION is an okvs object,
the implementation should execute the operation, preferably
without starting a transaction. If the underlying engine doesn't
allow one to execute operations without a transaction, the operation should
handle starting and committing the transaction.
CONFIG might contain the following options:
| key | description |
|---|---|
'reverse? |
whether key-value pairs will be returned in reverse lexicographical order beginning at the end of the range. It must be "applied" before the other options. |
'offset |
specify how many keys must be skipped. It must be
applied after reverse? but before limit. |
'limit |
indicates the maximum number of key-value pairs to return. It must be applied last. |
(okvs-prefix-range okvs-or-transaction prefix [config])Return a SRFI 158 generator of key-value pairs where the keys
start with PREFIX bytevector. The stream must be
lexicographically ordered. PREFIX can be the empty
bytevector, in which case the all the pairs are included.
OKVS-OR-TRANSACTION can be an okvs object or an okvs-transaction.
In the case where OKVS-OR-TRANSACTION is an okvs object,
the implementation should execute the operation, preferably
without starting a transaction. If the underlying engine doesn't
allow one to execute operations without a transaction, the operation should
handle starting and committing the transaction.
CONFIG might contain the following options:
| key | description |
|---|---|
'reverse? |
whether key-value pairs will be returned in reverse lexicographical order beginning at the end of the range. It must be "applied" before the other options. |
'offset |
specify how many keys must be skipped. It must be
applied after reverse? but before limit. |
'limit |
indicates the maximum number of key-value pairs to return. It must be applied last. |
(make-default-engine)Return an engine record for the current okvs
implementation.
SRFI 173 hooks
are procedures that are executed at specific times during the
life of an okvs. They allow one to sneak into transaction life
cycles to validate mutations, keep indices synchronized, or
carry out other operations.
(okvs-hook-on-transaction-begin okvs)This procedure returns the hook object associated with the start of a transaction.
The hook is run after the transaction is started inside
okvs-in-transaction. It takes the transaction
object as its first and only argument.
(okvs-hook-on-transaction-commit okvs)This procedure returns the hook object associated with the commit of a transaction.
The hook is run before the transaction is committed inside
okvs-in-transaction. It takes the transaction
object as its first and only argument.
The sample implementation relies on scheme mappings (SRFI 146), generators (SRFI 158) and hooks (SRFI 173).
Credit goes to the authors of WiredTiger and FoundationDB for their work on their respective database engines. The author would like to thank Arthur A. Gleckler and Marc Nieper-Wißkirchen for getting together SRFI 146 and Shiro Kawai, John Cowan, and Thomas Gilray for their work on SRFI 158.
Copyright (C) Amirouche Boubekki (2019).
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.