The session directory does not exist.

The session directory is locked by another active session.

The session directory is corrupted, e.g., it misses required files or contains unexpected files.

The session is closed.

The table is closed.

The table data is corrupted.

The table contains a run that has more than \(2^{40}\) physical entries.

A table union was constructed with two tables that are not compatible.

The named snapshot already exists.

The named snapshot does not exist.

The named snapshot is corrupted.

The named snapshot is not compatible with the expected type.

A BlobRef used with retrieveBlobs was invalid.

BlobRefs are obtained from lookups in a Table, but they may be invalidated by subsequent changes in that Table. In general the reliable way to retrieve blobs is not to change the Table before retrieving the blobs. To allow later retrievals, duplicate the table before making modifications and keep the table open until all blob retrievals are complete.

The cursor is closed.

The file is corrupted.

A session provides context that is shared across multiple tables.

Sessions are needed to support sharing between multiple table instances. Sharing occurs when tables are duplicated using duplicate, or when tables are combined using union. Sharing is not fully preserved by snapshots: existing runs are shared, but ongoing merges are not. As such, restoring of snapshots (using open) is expensive, but snapshotting (using snapshot) is relatively cheap.

The "monoidal" table types support a union operation, which has the constraint that the two input tables must be from the same Session.

Each session places files for table data under a given directory. It is not permitted to open multiple sessions for the same directory at once. Instead a session should be opened once and shared for all uses of tables. This restriction implies that tables cannot be shared between OS processes. The restriction is enforced using file locks.

Sessions support both related and unrelated tables. Related tables are created using duplicate, while unrelated tables can be created using new. It is possible to have multiple unrelated tables with different configuration and key and value types in the same session. Similarly, a session can have both "normal" and "monoidal" tables. For unrelated tables (that are not involved in a union) one has a choice between using multiple sessions or a shared session. Using multiple sessions requires using separate directories, while a shared session will place all files under one directory.

(Asynchronous) exception-safe, bracketed opening and closing of a session.

If possible, it is recommended to use this function instead of openSession and closeSession.

Create either a new empty table session or open an existing table session, given the path to the session directory.

A new empty table session is created if the given directory is entirely empty. Otherwise it is intended to open an existing table session.

Sessions should be closed using closeSession when no longer needed. Consider using withSession instead.

Exceptions:

• Throws an exception if the directory does not exist (regardless of whether it is empty or not).
• This can throw exceptions if the directory does not have the expected file layout for a table session
• It will throw an exception if the session is already open (in the current process or another OS process)

Close the table session. closeSession is idempotent. All subsequent operations on the session or the tables within it will throw an exception.

This also closes any open tables and cursors in the session. It would typically be good practice however to close all tables first rather than relying on this for cleanup.

Closing a table session allows the session to be opened again elsewhere, for example in a different process. Note that the session will be closed automatically if the process is terminated (in particular the session file lock will be released).

A handle to an on-disk key/value table.

An LSMT table is an individual key value mapping with in-memory and on-disk parts. A table is the object/reference by which an in-use LSM table will be operated upon. In this API it identifies a single mutable instance of an LSM table. The duplicate tables feature allows for there to may be many such instances in use at once.

Table configuration parameters, including LSM tree tuning parameters.

Some config options are fixed (for now):

• Merge policy: Tiering
• Size ratio: 4

A reasonable default TableConfig.

This uses a write buffer with up to 20,000 elements and a generous amount of memory for Bloom filters (FPR of 2%).

Allocation method for the write buffer.

A count of entries, for example the number of entries in a run.

This number is limited by the machine's word size. On 32-bit systems, the maximum number we can represent is 2^31 which is roughly 2 billion. This should be a sufficiently large limit that we never reach it in practice. By extension for 64-bit and higher-bit systems this limit is also sufficiently large.

Allocation method for bloom filters.

NOTE: a physical database entry is a key/operation pair that exists in a file, i.e., a run. Multiple physical entries that have the same key constitute a logical database entry.

Configure the type of fence pointer index.

The policy for caching data from disk in memory (using the OS page cache).

Caching data in memory can improve performance if the access pattern has good access locality or if the overall data size fits within memory. On the other hand, caching is determental to performance and wastes memory if the access pattern has poor spatial or temporal locality.

This implementation is designed to have good performance using a cacheless policy, where main memory is used only to cache Bloom filters and indexes, but none of the key/value data itself. Nevertheless, some use cases will be faster if some or all of the key/value data is also cached in memory. This implementation does not do any custom caching of key/value data, relying simply on the OS page cache. Thus caching is done in units of 4kb disk pages (as opposed to individual key/value pairs for example).

A configuration option that determines how merges are stepped to completion. This does not affect the amount of work that is done by merges, only how the work is spread out over time.

The default MergeSchedule.

>>> defaultMergeSchedule
Incremental

(Asynchronous) exception-safe, bracketed opening and closing of a table.

If possible, it is recommended to use this function instead of new and close.

Create a new empty table, returning a fresh table.

NOTE: tables hold open resources (such as open files) and should be closed using close as soon as they are no longer used.

Close a table. close is idempotent. All operations on a closed handle will throw an exception.

Any on-disk files and in-memory data that are no longer referenced after closing the table are lost forever. Use Snapshots to ensure data is not lost.

Perform a batch of lookups.

Lookups can be performed concurrently from multiple Haskell threads.

Result of a single point lookup.

Perform a range lookup.

Range lookups can be performed concurrently from multiple Haskell threads.

A range of keys.

A result for one point in a cursor read or range query.

A read-only view into a table.

A cursor allows reading from a table sequentially (according to serialised key ordering) in an incremental fashion. For example, this allows doing a table scan in small chunks. Once a cursor has been created, updates to the referenced table don't affect the cursor.

(Asynchronous) exception-safe, bracketed opening and closing of a cursor.

If possible, it is recommended to use this function instead of newCursor and closeCursor.

A variant of withCursor that allows initialising the cursor at an offset within the table such that the first entry the cursor returns will be the one with the lowest key that is greater than or equal to the given key. In other words, it uses an inclusive lower bound.

NOTE: The ordering of the serialised keys will be used, which can lead to unexpected results if the SerialiseKey instance is not order-preserving!

Create a new cursor to read from a given table. Future updates to the table will not be reflected in the cursor. The cursor starts at the beginning, i.e. the minimum key of the table.

Consider using withCursor instead.

NOTE: cursors hold open resources (such as open files) and should be closed using close as soon as they are no longer used.

A variant of newCursor that allows initialising the cursor at an offset within the table such that the first entry the cursor returns will be the one with the lowest key that is greater than or equal to the given key. In other words, it uses an inclusive lower bound.

NOTE: The ordering of the serialised keys will be used, which can lead to unexpected results if the SerialiseKey instance is not order-preserving!

Close a cursor. closeCursor is idempotent. All operations on a closed cursor will throw an exception.

Read the next n entries from the cursor. The resulting vector is shorter than n if the end of the table has been reached. The cursor state is updated, so the next read will continue where this one ended.

The cursor gets locked for the duration of the call, preventing concurrent reads.

NOTE: entries are returned in order of the serialised keys, which might not agree with Ord k. See SerialiseKey for more information.

Perform a batch of inserts.

Inserts can be performed concurrently from multiple Haskell threads.

Perform a batch of deletes.

Deletes can be performed concurrently from multiple Haskell threads.

Perform a batch of monoidal upserts.

Monoidal upserts can be performed concurrently from multiple Haskell threads.

Perform a mixed batch of inserts, deletes and monoidal upserts.

If there are duplicate keys in the same batch, then keys nearer to the front of the vector take precedence.

Updates can be performed concurrently from multiple Haskell threads.

Monoidal tables support insert, delete and monoidal upsert operations.

An update is a term that groups all types of table-manipulating operations, like inserts, deletes and mupserts.

Create snapshot name.

The given string must satsify isValidSnapshotName.

Throws the following exceptions:

InvalidSnapshotNameError

If the given string is not a valid snapshot name.

Check if a String would be a valid snapshot name.

Snapshot names consist of lowercase characters, digits, dashes -, and underscores _, and must be between 1 and 64 characters long. >>> isValidSnapshotName "main" True

>>> isValidSnapshotName "temporary-123-test_"
True

>>> isValidSnapshotName "UPPER"
False
>>> isValidSnapshotName "dir/dot.exe"
False
>>> isValidSnapshotName ".."
False
>>> isValidSnapshotName "\\"
False
>>> isValidSnapshotName ""
False
>>> isValidSnapshotName (replicate 100 'a')
False

Snapshot names must be valid directory on both POSIX and Windows. This rules out the following reserved file and directory names on Windows:

>>> isValidSnapshotName "con"
False
>>> isValidSnapshotName "prn"
False
>>> isValidSnapshotName "aux"
False
>>> isValidSnapshotName "nul"
False
>>> isValidSnapshotName "com1" -- "com2", "com3", etc.
False
>>> isValidSnapshotName "lpt1" -- "lpt2", "lpt3", etc.
False

See, e.g., the VBA docs for the "Bad file name or number" error.

Custom, user-supplied text that is included in the metadata.

The main use case for a SnapshotLabel is for the user to supply textual information about the key/value/blob type for the table that corresponds to the snapshot. This information is used to dynamically check that a snapshot is opened at the correct key/value/blob type.

Make the current value of a table durable on-disk by taking a snapshot and giving the snapshot a name. This is the only mechanism to make a table durable -- ordinary insert/delete operations are otherwise not preserved.

Snapshots have names and the table may be opened later using openSnapshot via that name. Names are strings and the management of the names is up to the user of the library.

The names correspond to disk files, which imposes some constraints on length and what characters can be used.

Snapshotting does not close the table.

Taking a snapshot is relatively cheap, but it is not so cheap that one can use it after every operation. In the implementation, it must at least flush the write buffer to disk.

Concurrency:

• It is safe to concurrently make snapshots from any table, provided that the snapshot names are distinct (otherwise this would be a race).

Open a table from a named snapshot, returning a new table.

NOTE: close tables using close as soon as they are unused.

Exceptions:

• Opening a non-existent snapshot is an error.
• Opening a snapshot but expecting the wrong type of table is an error. e.g., the following will fail:

example session = do
  t <- new @IO @Int @Int @Int session _
  createSnapshot "intTable" t
  openSnapshot @IO @Bool @Bool @Bool session "intTable"

Override configuration options in TableConfig that can be changed dynamically.

Some parts of the TableConfig are considered fixed after a table is created. That is, these options should (i) should stay the same over the lifetime of a table, and (ii) these options should not be changed when a snapshot is created or loaded. Other options can be changed dynamically without sacrificing correctness.

This type has Semigroup and Monoid instances for composing override options.

Delete a named snapshot.

NOTE: has similar behaviour to removeDirectory.

Exceptions:

• Deleting a snapshot that doesn't exist is an error.

List snapshots by name.

Create a logically independent duplicate of a table. This returns a new table.

A table and its duplicate are logically independent: changes to one are not visible to the other. However, in-memory and on-disk data are shared internally.

This operation enables fully persistent use of tables by duplicating the table prior to a batch of mutating operations. The duplicate retains the original table value, and can still be modified independently.

This is persistence in the sense of persistent data structures (not of on-disk persistence). The usual definition of a persistent data structure is one in which each operation preserves the previous version of the structure when the structure is modified. Full persistence is if every version can be both accessed and modified. This API does not directly fit the definition because the update operations do mutate the table value, however full persistence can be emulated by duplicating the table prior to a mutating operation.

Duplication itself is cheap. In particular it requires no disk I/O, and requires little additional memory. Just as with normal persistent data structures, making use of multiple tables will have corresponding costs in terms of memory and disk space. Initially the two tables will share everything (both in memory and on disk) but as more and more update operations are performed on each, the sharing will decrease. Ultimately the memory and disk cost will be the same as if each table were entirely independent.

NOTE: duplication create a new table, which should be closed when no longer needed.

Union two full tables, creating a new table.

A good mental model of this operation is unionWith (<>) on Map k v.

Multiple tables of the same type but with different configuration parameters can live in the same session. However, union only works for tables that have the same key/value types and configuration parameters.

NOTE: unioning tables creates a new table, but does not close the tables that were used as inputs.

Like union, but for n tables.

A good mental model of this operation is unionsWith (<>) on Map k v.

The current upper bound on the number of UnionCredits that have to be supplied before a union is completed.

The union debt is the number of merging steps that need to be performed /at most/ until the delayed work of performing a union is completed. This includes the cost of completing merges that were part of the union's input tables.

Return the current union debt. This debt can be reduced until it is paid off using supplyUnionCredits.

Credits are used to pay off UnionDebt, completing a union in the process.

A union credit corresponds to a single merging step being performed.

Supply union credits to reduce union debt.

Supplying union credits leads to union merging work being performed in batches. This reduces the union debt returned by remainingUnionDebt. Union debt will be reduced by at least the number of supplied union credits. It is therefore advisable to query remainingUnionDebt every once in a while to see what the current debt is.

This function returns any surplus of union credits as leftover credits when a union has finished. In particular, if the returned number of credits is non-negative, then the union is finished.

Serialisation of keys.

Instances should satisfy the following:

Identity

deserialiseKey (serialiseKey x) == x

Identity up to slicing

deserialiseKey (packSlice prefix (serialiseKey x) suffix) == x

Instances may satisfy the following:

Ordering-preserving

x `compare` y == serialiseKey x `compare` serialiseKey y

Raw bytes are lexicographically ordered, so in particular this means that values should be serialised into big-endian formats. This constraint mainly exists for range queries, where the range is specified in terms of unserialised values, but the internal implementation works on the serialised representation.

Serialisation of values and blobs.

Instances should satisfy the following:

Identity

deserialiseValue (serialiseValue x) == x

Identity up to slicing

deserialiseValue (packSlice prefix (serialiseValue x) suffix) == x

A class to specify how to resolve/merge values when using monoidal updates (Mupsert). This is required for merging entries during compaction and also for doing lookups, resolving multiple entries of the same key on the fly. The class has some laws, which should be tested (e.g. with QuickCheck).

It is okay to assume that the input bytes can be deserialised using deserialiseValue, as they are produced by either serialiseValue or resolveValue itself, which are required to produce deserialisable output.

Prerequisites:

• [Valid Output] The result of resolution should always be deserialisable. See resolveValueValidOutput.
• [Associativity] Resolving values should be associative. See resolveValueAssociativity.

Future opportunities for optimisations:

• Include a function that determines whether it is safe to remove an Update from the last level of an LSM tree.
• Include a function v -> RawBytes -> RawBytes, which can then be used when inserting into the write buffer. Currently, using resolveDeserialised means that the inserted value is serialised and (if there is another value with the same key in the write buffer) immediately deserialised again.

TODO: The laws depend on SerialiseValue, should we make it a superclass? TODO: should we additionally require Totality (for any input RawBytes, resolution should successfully provide a result)? This could reduce the risk of encountering errors during a run merge.

A helper function to implement resolveValue by operating on the deserialised representation. Note that especially for simple types it should be possible to provide a more efficient implementation by directly operating on the RawBytes.

This function could potentially be used to provide a default implementation for resolveValue, but it's probably best to be explicit about instances.

To satisfy the prerequisites of ResolveValue, the function provided to resolveDeserialised should itself satisfy some properties:

• [Associativity] The provided function should be associative.
• [Totality] The provided function should be total.

Test the Valid Output law for the ResolveValue class

Test the Associativity law for the ResolveValue class

Utility class for grouping io-classes constraints.