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

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

Result of a single point lookup.

A range of keys.

A handle-like reference to an on-disk blob. The blob can be retrieved based on the reference.

Blob comes from the acronym Binary Large OBject (BLOB) and in many database implementations refers to binary data that is larger than usual values and is handled specially. In our context we will allow optionally a blob associated with each value in the table.

Though blob references are handle-like, they do not keep files open. As such, when a blob reference is returned by a lookup, modifying the corresponding table, cursor, or session may cause the blob reference to be invalidated (i.e.., the blob has gone missing because the blob file was removed). These operations include:

• Updates (e.g., inserts, deletes, mupserts)
• Closing tables
• Closing cursors
• Closing sessions

An invalidated blob reference will throw an exception when used to look up a blob. Note that operations such as snapshotting, duplication and cursor reads do not invalidate blob references. These operations do not modify the logical contents or state of a table.

Blob reference validity

as long as the table or cursor that the blob reference originated from is not updated or closed, the blob reference will be valid.

Exception: currently the snapshot operation also invalidates BlobRefs, but it should not do. See https://github.com/IntersectMBO/lsm-tree/issues/392

TODO: get rid of the m parameter?

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.

Create snapshot name.

The given string must satsify isValidSnapshotName.

Throws the following exceptions:

InvalidSnapshotNameError

If the given string is not a valid snapshot name.

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.

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.

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.

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

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

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

Newtype wrapper for values, so that Mupserts behave like Inserts.

If there is no intent to use Mupserts, then the user still has to define a ResolveValue instance for their values, unless they use this newtype, which provides a sensible default instance.

Utility class for grouping io-classes constraints.