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

- Received: 2019/4/13
- Draft #1 published: 2019/4/18
- Draft #2 published: 2019/4/26
- Draft #3 published: 2019/6/2
- Draft #4 published: 2019/6/11
- Draft #5 published: 2019/7/29
- Draft #6 published: 2019/9/18
- Draft #7 published: 2019/10/29
- Finalized: 2019/11/8

# 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:

- `okvs` is a handle to the data storage
- `transaction` is a handle to a currently running transaction

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.