Title

SRFI 167: Ordered Key Value Store

Author

Amirouche Boubekki

Status

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.

Abstract

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.

Rationale

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.

Specification

The SRFI is composed of two library modules. The first is the engine library and the second is the okvs library.

engine

To 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 okvs . 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.

Okvs and Transaction

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:

In 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 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
'limit indicates the maximum number of key-value pairs to return.
'reverse? whether key-value pairs will be returned in reverse lexicographical order beginning at the end of the range.
'offset specify how many keys must be skipped.

Hooks

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.

(make-default-engine)

Return an engine record for the current okvs implementation.

Implementation

The sample implementation relies on scheme mappings (SRFI 146), generators (SRFI 158) and hooks (SRFI 173).

Acknowledgements

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

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.


Editor: Arthur A. Gleckler