A session stores context that is shared by multiple tables.

Each session is associated with one session directory where the files containing table data are stored. Each session locks its session directory. There can only be one active session for each session directory at a time. If a database is must be accessed from multiple parts of a program, one session should be opened and shared between those parts of the program. Session directories cannot be shared between OS processes.

A session may contain multiple tables, which may each have a different configuration and different key, value, and BLOB types. Furthermore, sessions may contain both simple and full-featured tables.

Run an action with access to a session opened from a session directory.

If the session directory is empty, a new session is created using the given salt. Otherwise, the session directory is restored as an existing session ignoring the given salt.

If there are no open tables or cursors when the session terminates, then the disk I/O complexity of this operation is \(O(1)\). Otherwise, closeTable is called for each open table and closeCursor is called for each open cursor. Consequently, the worst-case disk I/O complexity of this operation depends on the merge policy of the open tables in the session. The following assumes all tables in the session have the same merge policy:

LazyLevelling

\(O(o \: T \log_T \frac{n}{B})\).

The variable \(o\) refers to the number of open tables and cursors in the session.

This function is exception-safe for both synchronous and asynchronous exceptions.

It is recommended to use this function instead of openSession and closeSession.

Throws the following exceptions:

SessionDirDoesNotExistError

If the session directory does not exist.

SessionDirLockedError

If the session directory is locked by another process.

SessionDirCorruptedError

If the session directory is malformed.

Variant of withOpenSession that is specialised to IO using the real filesystem.

Run an action with access to a new session.

The session directory must be empty.

If there are no open tables or cursors when the session terminates, then the disk I/O complexity of this operation is \(O(1)\). Otherwise, closeTable is called for each open table and closeCursor is called for each open cursor. Consequently, the worst-case disk I/O complexity of this operation depends on the merge policy of the open tables in the session. The following assumes all tables in the session have the same merge policy:

LazyLevelling

\(O(o \: T \log_T \frac{n}{B})\).

The variable \(o\) refers to the number of open tables and cursors in the session.

This function is exception-safe for both synchronous and asynchronous exceptions.

It is recommended to use this function instead of newSession and closeSession.

Throws the following exceptions:

SessionDirDoesNotExistError

If the session directory does not exist.

SessionDirLockedError

If the session directory is locked by another process.

SessionDirCorruptedError

If the session directory is malformed.

Run an action with access to a restored session.

The session directory must be non-empty: a session must have previously been opened and closed in this directory.

If there are no open tables or cursors when the session terminates, then the disk I/O complexity of this operation is \(O(1)\). Otherwise, closeTable is called for each open table and closeCursor is called for each open cursor. Consequently, the worst-case disk I/O complexity of this operation depends on the merge policy of the open tables in the session. The following assumes all tables in the session have the same merge policy:

LazyLevelling

\(O(o \: T \log_T \frac{n}{B})\).

The variable \(o\) refers to the number of open tables and cursors in the session.

This function is exception-safe for both synchronous and asynchronous exceptions.

It is recommended to use this function instead of restoreSession and closeSession.

Throws the following exceptions:

SessionDirDoesNotExistError

If the session directory does not exist.

SessionDirLockedError

If the session directory is locked by another process.

SessionDirCorruptedError

If the session directory is malformed.

Open a session from a session directory.

If the session directory is empty, a new session is created using the given salt. Otherwise, the session directory is restored as an existing session ignoring the given salt.

The worst-case disk I/O complexity of this operation is \(O(1)\).

Warning: Sessions hold open resources and must be closed using closeSession.

Throws the following exceptions:

SessionDirDoesNotExistError

If the session directory does not exist.

SessionDirLockedError

If the session directory is locked by another process.

SessionDirCorruptedError

If the session directory is malformed.

Create a new session.

The session directory must be empty.

The worst-case disk I/O complexity of this operation is \(O(1)\).

Warning: Sessions hold open resources and must be closed using closeSession.

Throws the following exceptions:

SessionDirDoesNotExistError

If the session directory does not exist.

SessionDirLockedError

If the session directory is locked by another process.

SessionDirCorruptedError

If the session directory is malformed.

Restore a session from a session directory.

The session directory must be non-empty: a session must have previously been opened (and closed) in this directory.

The worst-case disk I/O complexity of this operation is \(O(1)\).

Warning: Sessions hold open resources and must be closed using closeSession.

Throws the following exceptions:

SessionDirDoesNotExistError

If the session directory does not exist.

SessionDirLockedError

If the session directory is locked by another process.

SessionDirCorruptedError

If the session directory is malformed.

Close a session.

If there are no open tables or cursors in the session, then the disk I/O complexity of this operation is \(O(1)\). Otherwise, closeTable is called for each open table and closeCursor is called for each open cursor. Consequently, the worst-case disk I/O complexity of this operation depends on the merge policy of the tables in the session. The following assumes all tables in the session have the same merge policy:

LazyLevelling

\(O(o \: T \log_T \frac{n}{B})\).

The variable \(o\) refers to the number of open tables and cursors in the session.

Closing is idempotent, i.e., closing a closed session does nothing. All other operations on a closed session will throw an exception.

A table is a handle to an individual LSM-tree key/value store with both in-memory and on-disk parts.

Warning: Tables are ephemeral. Once you close a table, its data is lost forever. To persist tables, use snapshots.

Run an action with access to an empty table.

The worst-case disk I/O complexity of this operation depends on the merge policy of the table:

LazyLevelling

\(O(T \log_T \frac{n}{B})\).

This function is exception-safe for both synchronous and asynchronous exceptions.

It is recommended to use this function instead of newTable and closeTable.

Throws the following exceptions:

SessionClosedError

If the session is closed.

Variant of withTable that accepts table configuration.

Create an empty table.

The worst-case disk I/O complexity of this operation is \(O(1)\).

Warning: Tables hold open resources and must be closed using closeTable.

Throws the following exceptions:

SessionClosedError

If the session is closed.

Variant of newTable that accepts table configuration.

Close a table.

The worst-case disk I/O complexity of this operation depends on the merge policy of the table:

LazyLevelling

\(O(T \log_T \frac{n}{B})\).

Closing is idempotent, i.e., closing a closed table does nothing. All other operations on a closed table will throw an exception.

Warning: Tables are ephemeral. Once you close a table, its data is lost forever. To persist tables, use snapshots.

Check if the key is a member of the table.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" Nothing
  LSMT.insert table 1 "World" Nothing
  print =<< LSMT.member table 0
:}
True

The worst-case disk I/O complexity of this operation depends on the merge policy of the table:

LazyLevelling

\(O(T \log_T \frac{n}{B})\).

Membership tests can be performed concurrently from multiple Haskell threads.

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

TableCorruptedError

If the table data is corrupted.

Variant of member for batch membership tests. The batch of keys corresponds in-order to the batch of results.

The worst-case disk I/O complexity of this operation depends on the merge policy of the table:

LazyLevelling

\(O(b \: T \log_T \frac{n}{B})\).

The variable \(b\) refers to the length of the input vector.

The following property holds in the absence of races:

members table keys = traverse (member table) keys

Get the field of type v from a LookupResult v b, if any.

Get the field of type b from a LookupResult v b, if any.

The following property holds:

isJust (getBlob result) <= isJust (getValue result)

Look up the value associated with a key.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" Nothing
  LSMT.insert table 1 "World" Nothing
  print =<< LSMT.lookup table 0
:}
Found (Value "Hello")

If the key is not associated with any value, lookup returns NotFound.

>>> :{
runExample $ \session table -> do
  LSMT.lookup table 0
:}
NotFound

If the key has an associated BLOB, the result contains a BlobRef. The full BLOB can be retrieved by passing that BlobRef to retrieveBlob.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" (Just "World")
  print
    =<< traverse (LSMT.retrieveBlob session)
    =<< LSMT.lookup table 0
:}
FoundWithBlob (Value "Hello") (Blob "World")

The worst-case disk I/O complexity of this operation depends on the merge policy of the table:

LazyLevelling

\(O(T \log_T \frac{n}{B})\).

Lookups can be performed concurrently from multiple Haskell threads.

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

TableCorruptedError

If the table data is corrupted.

Variant of lookup for batch lookups. The batch of keys corresponds in-order to the batch of results.

The worst-case disk I/O complexity of this operation depends on the merge policy of the table:

LazyLevelling

\(O(b \: T \log_T \frac{n}{B})\).

The variable \(b\) refers to the length of the input vector.

The following property holds in the absence of races:

lookups table keys = traverse (lookup table) keys

Get the field of type k from an Entry k v b.

Get the field of type v from an Entry k v b.

Get the field of type b from an Entry k v b, if any.

Look up a batch of values associated with keys in the given range.

The worst-case disk I/O complexity of this operation is \(O(T \log_T \frac{n}{B} + \frac{b}{P})\), where the variable \(b\) refers to the length of the output vector.

Range lookups can be performed concurrently from multiple Haskell threads.

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

TableCorruptedError

If the table data is corrupted.

Insert associates the given value and BLOB with the given key in the table.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" Nothing
  LSMT.insert table 1 "World" Nothing
  print =<< LSMT.lookup table 0
:}
Found (Value "Hello")

Insert may optionally associate a BLOB value with the given key.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" (Just "World")
  print
    =<< traverse (retrieveBlob session)
    =<< LSMT.lookup table 0
:}
FoundWithBlob (Value "Hello") (Blob "World")

Insert overwrites any value and BLOB previously associated with the given key, even if the given BLOB is Nothing.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" (Just "World")
  LSMT.insert table 0 "Goodbye" Nothing
  print
    =<< traverse (retrieveBlob session)
    =<< LSMT.lookup table 0
:}
Found (Value "Goodbye")

The worst-case disk I/O complexity of this operation depends on the merge policy and the merge schedule of the table:

LazyLevelling/Incremental

\(O(\frac{1}{P} \: \log_T \frac{n}{B})\).

LazyLevelling/OneShot

\(O(\frac{n}{P})\).

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

Variant of insert for batch insertions.

The worst-case disk I/O complexity of this operation depends on the merge policy and the merge schedule of the table:

LazyLevelling/Incremental

\(O(b \: \frac{1}{P} \: \log_T \frac{n}{B})\).

LazyLevelling/OneShot

\(O(\frac{b}{P} \log_T \frac{b}{B} + \frac{n}{P})\).

The variable \(b\) refers to the length of the input vector.

The following property holds in the absence of races:

inserts table entries = traverse_ (uncurry $ insert table) entries

If the given key is not a member of the table, upsert associates the given value with the given key in the table. Otherwise, upsert updates the value associated with the given key by combining it with the given value using resolve.

>>> :{
runExample $ \session table -> do
  LSMT.upsert table 0 "Hello"
  LSMT.upsert table 0 "Goodbye"
  print =<< LSMT.lookup table 0
:}
Found (Value "Goodbye Hello")

Warning: Upsert deletes any BLOB previously associated with the given key.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" (Just "World")
  LSMT.upsert table 0 "Goodbye"
  print
    =<< traverse (LSMT.retrieveBlob session)
    =<< LSMT.lookup table 0
:}
Found (Value "Goodbye Hello")

The worst-case disk I/O complexity of this operation depends on the merge policy and the merge schedule of the table:

LazyLevelling/Incremental

\(O(\frac{1}{P} \: \log_T \frac{n}{B})\).

LazyLevelling/OneShot

\(O(\frac{n}{P})\).

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

The following property holds in the absence of races:

upsert table k v = do
  r <- lookup table k
  let v' = maybe v (resolve v) (getValue r)
  insert table k v' Nothing

Variant of upsert for batch insertions.

The worst-case disk I/O complexity of this operation depends on the merge policy and the merge schedule of the table:

LazyLevelling/Incremental

\(O(b \: \frac{1}{P} \: \log_T \frac{n}{B})\).

LazyLevelling/OneShot

\(O(\frac{b}{P} \log_T \frac{b}{B} + \frac{n}{P})\).

The variable \(b\) refers to the length of the input vector.

The following property holds in the absence of races:

upserts table entries = traverse_ (uncurry $ upsert table) entries

Delete a key from the table.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" Nothing
  LSMT.delete table 0
  print =<< LSMT.lookup table 0
:}
NotFound

If the key is not a member of the table, the table is left unchanged.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" Nothing
  LSMT.delete table 1
  print =<< LSMT.lookup table 0
:}
Found (Value "Hello")

The worst-case disk I/O complexity of this operation depends on the merge policy and the merge schedule of the table:

LazyLevelling/Incremental

\(O(\frac{1}{P} \: \log_T \frac{n}{B})\).

LazyLevelling/OneShot

\(O(\frac{n}{P})\).

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

Variant of delete for batch deletions.

The worst-case disk I/O complexity of this operation depends on the merge policy and the merge schedule of the table:

LazyLevelling/Incremental

\(O(b \: \frac{1}{P} \: \log_T \frac{n}{B})\).

LazyLevelling/OneShot

\(O(\frac{b}{P} \log_T \frac{b}{B} + \frac{n}{P})\).

The variable \(b\) refers to the length of the input vector.

The following property holds in the absence of races:

deletes table keys = traverse_ (delete table) keys

Update generalises insert, delete, and upsert.

The worst-case disk I/O complexity of this operation depends on the merge policy and the merge schedule of the table:

LazyLevelling/Incremental

\(O(\frac{1}{P} \: \log_T \frac{n}{B})\).

LazyLevelling/OneShot

\(O(\frac{n}{P})\).

The following properties hold:

update table k (Insert v mb) = insert table k v mb

update table k Delete = delete table k

update table k (Upsert v) = upsert table k v

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

Variant of update for batch updates.

The worst-case disk I/O complexity of this operation depends on the merge policy and the merge schedule of the table:

LazyLevelling/Incremental

\(O(b \: \frac{1}{P} \: \log_T \frac{n}{B})\).

LazyLevelling/OneShot

\(O(\frac{b}{P} \log_T \frac{b}{B} + \frac{n}{P})\).

The variable \(b\) refers to the length of the input vector.

The following property holds in the absence of races:

updates table entries = traverse_ (uncurry $ update table) entries

Run an action with access to the duplicate of a table.

The duplicate is an independent copy of the given table. Subsequent updates to the original table do not affect the duplicate, and vice versa.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" Nothing
  LSMT.withDuplicate table $ \table' -> do
    print =<< LSMT.lookup table' 0
    LSMT.insert table' 0 "Goodbye" Nothing
    print =<< LSMT.lookup table' 0
  LSMT.lookup table 0
  print =<< LSMT.lookup table 0
:}
Found (Value "Hello")
Found (Value "Goodbye")
Found (Value "Hello")

The worst-case disk I/O complexity of this operation depends on the merge policy of the table:

LazyLevelling

\(O(T \log_T \frac{n}{B})\).

This function is exception-safe for both synchronous and asynchronous exceptions.

It is recommended to use this function instead of duplicate and closeTable.

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

Duplicate a table.

The duplicate is an independent copy of the given table. Subsequent updates to the original table do not affect the duplicate, and vice versa.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" Nothing
  bracket (LSMT.duplicate table) LSMT.closeTable $ \table' -> do
    print =<< LSMT.lookup table' 0
    LSMT.insert table' 0 "Goodbye" Nothing
    print =<< LSMT.lookup table' 0
  LSMT.lookup table 0
  print =<< LSMT.lookup table 0
:}
Found (Value "Hello")
Found (Value "Goodbye")
Found (Value "Hello")

The worst-case disk I/O complexity of this operation is \(O(0)\).

Warning: The duplicate must be independently closed using closeTable.

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

Run an action with access to a table that contains the union of the entries of the given tables.

>>> :{
runExample $ \session table1 -> do
  LSMT.insert table1 0 "Hello" Nothing
  LSMT.withTable session $ \table2 -> do
    LSMT.insert table2 0 "World" Nothing
    LSMT.insert table2 1 "Goodbye" Nothing
    LSMT.withUnion table1 table2 $ \table3 -> do
      print =<< LSMT.lookup table3 0
      print =<< LSMT.lookup table3 1
    print =<< LSMT.lookup table1 0
    print =<< LSMT.lookup table2 0
:}
Found (Value "Hello World")
Found (Value "Goodbye")
Found (Value "Hello")
Found (Value "World")

The worst-case disk I/O complexity of this operation is \(O(\frac{n}{P})\).

This function is exception-safe for both synchronous and asynchronous exceptions.

It is recommended to use this function instead of union and closeTable.

Warning: Both input tables must be from the same Session.

Warning: This is a relatively expensive operation that may take some time to complete. See withIncrementalUnion for an incremental alternative.

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

TableUnionNotCompatibleError

If both tables are not from the same Session.

Variant of withUnions that takes any number of tables.

Create a table that contains the union of the entries of the given tables.

If the given key is a member of a single input table, then the same key and value occur in the output table. Otherwise, the values for duplicate keys are combined using resolve from left to right. If the resolve function behaves like const, then this computes a left-biased union.

>>> :{
runExample $ \session table1 -> do
  LSMT.insert table1 0 "Hello" Nothing
  LSMT.withTable session $ \table2 -> do
    LSMT.insert table2 0 "World" Nothing
    LSMT.insert table2 1 "Goodbye" Nothing
    bracket (LSMT.union table1 table2) LSMT.closeTable $ \table3 -> do
      print =<< LSMT.lookup table3 0
      print =<< LSMT.lookup table3 1
    print =<< LSMT.lookup table1 0
    print =<< LSMT.lookup table2 0
:}
Found (Value "Hello World")
Found (Value "Goodbye")
Found (Value "Hello")
Found (Value "World")

The worst-case disk I/O complexity of this operation is \(O(\frac{n}{P})\).

Warning: The new table must be independently closed using closeTable.

Warning: Both input tables must be from the same Session.

Warning: This is a relatively expensive operation that may take some time to complete. See incrementalUnion for an incremental alternative.

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

TableUnionNotCompatibleError

If both tables are not from the same Session.

Variant of union that takes any number of tables.

Run an action with access to a table that incrementally computes the union of the given tables.

>>> :{
runExample $ \session table1 -> do
  LSMT.insert table1 0 "Hello" Nothing
  LSMT.withTable session $ \table2 -> do
    LSMT.insert table2 0 "World" Nothing
    LSMT.insert table2 1 "Goodbye" Nothing
    LSMT.withIncrementalUnion table1 table2 $ \table3 -> do
      print =<< LSMT.lookup table3 0
      print =<< LSMT.lookup table3 1
    print =<< LSMT.lookup table1 0
    print =<< LSMT.lookup table2 0
:}
Found (Value "Hello World")
Found (Value "Goodbye")
Found (Value "Hello")
Found (Value "World")

The worst-case disk I/O complexity of this operation depends on the merge policy of the table:

LazyLevelling

\(O(T \log_T \frac{n}{B})\).

This function is exception-safe for both synchronous and asynchronous exceptions.

It is recommended to use this function instead of incrementalUnion and closeTable.

The created table has a union debt which represents the amount of computation that remains. See remainingUnionDebt. The union debt can be paid off by supplying union credit which performs an amount of computation proportional to the amount of union credit. See supplyUnionCredits. While a table has unresolved union debt, operations may become more expensive by a factor that scales with the number of unresolved unions.

Warning: Both input tables must be from the same Session.

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

TableUnionNotCompatibleError

If both tables are not from the same Session.

Variant of withIncrementalUnion that takes any number of tables.

The worst-case disk I/O complexity of this operation depends on the merge policy of the table:

LazyLevelling

\(O(T \log_T \frac{n}{B} + b)\).

The variable \(b\) refers to the number of input tables.

Create a table that incrementally computes the union of the given tables.

>>> :{
runExample $ \session table1 -> do
  LSMT.insert table1 0 "Hello" Nothing
  LSMT.withTable session $ \table2 -> do
    LSMT.insert table2 0 "World" Nothing
    LSMT.insert table2 1 "Goodbye" Nothing
    bracket (LSMT.incrementalUnion table1 table2) LSMT.closeTable $ \table3 -> do
      print =<< LSMT.lookup table3 0
      print =<< LSMT.lookup table3 1
    print =<< LSMT.lookup table1 0
    print =<< LSMT.lookup table2 0
:}
Found (Value "Hello World")
Found (Value "Goodbye")
Found (Value "Hello")
Found (Value "World")

The worst-case disk I/O complexity of this operation is \(O(1)\).

The created table has a union debt which represents the amount of computation that remains. See remainingUnionDebt. The union debt can be paid off by supplying union credit which performs an amount of computation proportional to the amount of union credit. See supplyUnionCredits. While a table has unresolved union debt, operations may become more expensive by a factor that scales with the number of unresolved unions.

Warning: The new table must be independently closed using closeTable.

Warning: Both input tables must be from the same Session.

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

TableUnionNotCompatibleError

If both tables are not from the same Session.

Variant of incrementalUnion for any number of tables.

The worst-case disk I/O complexity of this operation is \(O(b)\), where the variable \(b\) refers to the number of input tables.

Get an upper bound for the amount of remaining union debt. This includes the union debt of any table that was part of the union's input.

>>> :{
runExample $ \session table1 -> do
  LSMT.insert table1 0 "Hello" Nothing
  LSMT.withTable session $ \table2 -> do
    LSMT.insert table2 0 "World" Nothing
    LSMT.insert table2 1 "Goodbye" Nothing
    bracket (LSMT.incrementalUnion table1 table2) LSMT.closeTable $ \table3 -> do
      putStrLn . ("UnionDebt: "<>) . show =<< LSMT.remainingUnionDebt table3
:}
UnionDebt: 4

The worst-case disk I/O complexity of this operation is \(O(0)\).

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

Supply the given amount of union credits.

This reduces the union debt by at least the number of supplied union credits. It is therefore advisable to query remainingUnionDebt every once in a while to get an upper bound on the current debt.

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 positive, then the union is finished.

>>> :{
runExample $ \session table1 -> do
  LSMT.insert table1 0 "Hello" Nothing
  LSMT.withTable session $ \table2 -> do
    LSMT.insert table2 0 "World" Nothing
    LSMT.insert table2 1 "Goodbye" Nothing
    bracket (LSMT.incrementalUnion table1 table2) LSMT.closeTable $ \table3 -> do
      putStrLn . ("UnionDebt: "<>) . show =<< LSMT.remainingUnionDebt table3
      putStrLn . ("Leftovers: "<>) . show =<< LSMT.supplyUnionCredits table3 2
      putStrLn . ("UnionDebt: "<>) . show =<< LSMT.remainingUnionDebt table3
      putStrLn . ("Leftovers: "<>) . show =<< LSMT.supplyUnionCredits table3 4
:}
UnionDebt: 4
Leftovers: 0
UnionDebt: 2
Leftovers: 3

NOTE: The remainingUnionDebt functions gets an upper bound for the amount of remaning union debt. In the example above, the second call to remainingUnionDebt reports 2, but the union debt is 1. Therefore, the second call to supplyUnionCredits returns more leftovers than expected.

The worst-case disk I/O complexity of this operation is \(O(\frac{b}{P})\), where the variable \(b\) refers to the amount of credits supplied.

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

A blob reference is a reference to an on-disk blob.

Warning: A blob reference is not stable. Any operation that modifies the table, cursor, or session that corresponds to a blob reference may cause it to be invalidated.

The word "blob" in this type comes from the acronym Binary Large Object.

Retrieve the blob value from a blob reference.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" (Just "World")
  print
    =<< traverse (LSMT.retrieveBlob session)
    =<< LSMT.lookup table 0
:}
FoundWithBlob (Value "Hello") (Blob "World")

The worst-case disk I/O complexity of this operation is \(O(1)\).

Warning: A blob reference is not stable. Any operation that modifies the table, cursor, or session that corresponds to a blob reference may cause it to be invalidated.

Throws the following exceptions:

SessionClosedError

If the session is closed.

BlobRefInvalidError

If the blob reference has been invalidated.

Variant of retrieveBlob for batch retrieval. The batch of blob references corresponds in-order to the batch of results.

The worst-case disk I/O complexity of this operation is \(O(b)\), where the variable \(b\) refers to the length of the input vector.

The following property holds in the absence of races:

retrieveBlobs session blobRefs = traverse (retrieveBlob session) blobRefs

A cursor is a stable read-only iterator for a table.

A cursor iterates over the entries in a table following the order of the serialised keys. After the cursor is created, updates to the referenced table do not affect the cursor.

The name of this type references database cursors, not, e.g., text editor cursors.

Run an action with access to a cursor.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" Nothing
  LSMT.insert table 1 "World" Nothing
  LSMT.withCursor table $ \cursor -> do
    traverse_ print
      =<< LSMT.take 32 cursor
:}
Entry (Key 0) (Value "Hello")
Entry (Key 1) (Value "World")

The worst-case disk I/O complexity of this operation depends on the merge policy of the table:

LazyLevelling

\(O(T \log_T \frac{n}{B})\).

This function is exception-safe for both synchronous and asynchronous exceptions.

It is recommended to use this function instead of newCursor and closeCursor.

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

Variant of withCursor that starts at a given key.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" Nothing
  LSMT.insert table 1 "World" Nothing
  LSMT.withCursorAtOffset table 1 $ \cursor -> do
    traverse_ print
      =<< LSMT.take 32 cursor
:}
Entry (Key 1) (Value "World")

Create a cursor for the given table.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" Nothing
  LSMT.insert table 1 "World" Nothing
  bracket (LSMT.newCursor table) LSMT.closeCursor $ \cursor -> do
    traverse_ print
      =<< LSMT.take 32 cursor
:}
Entry (Key 0) (Value "Hello")
Entry (Key 1) (Value "World")

The worst-case disk I/O complexity of this operation depends on the merge policy of the table:

LazyLevelling

\(O(T \log_T \frac{n}{B})\).

Warning: Cursors hold open resources and must be closed using closeCursor.

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

Variant of newCursor that starts at a given key.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" Nothing
  LSMT.insert table 1 "World" Nothing
  bracket (LSMT.newCursorAtOffset table 1) LSMT.closeCursor $ \cursor -> do
    traverse_ print
      =<< LSMT.take 32 cursor
:}
Entry (Key 1) (Value "World")

Close a cursor.

The worst-case disk I/O complexity of this operation depends on the merge policy of the table:

LazyLevelling

\(O(T \log_T \frac{n}{B})\).

Closing is idempotent, i.e., closing a closed cursor does nothing. All other operations on a closed cursor will throw an exception.

Read the next table entry from the cursor.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" Nothing
  LSMT.insert table 1 "World" Nothing
  LSMT.withCursor table $ \cursor -> do
    print =<< LSMT.next cursor
    print =<< LSMT.next cursor
    print =<< LSMT.next cursor
:}
Just (Entry (Key 0) (Value "Hello"))
Just (Entry (Key 1) (Value "World"))
Nothing

The worst-case disk I/O complexity of this operation is \(O(\frac{1}{P})\).

Throws the following exceptions:

SessionClosedError

If the session is closed.

CursorClosedError

If the cursor is closed.

Read the next batch of table entries from the cursor.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" Nothing
  LSMT.insert table 1 "World" Nothing
  LSMT.withCursor table $ \cursor -> do
    traverse_ print
      =<< LSMT.take 32 cursor
:}
Entry (Key 0) (Value "Hello")
Entry (Key 1) (Value "World")

The worst-case disk I/O complexity of this operation is \(O(\frac{b}{P})\), where the variable \(b\) refers to the length of the output vector, which is at most equal to the given number. In practice, the length of the output vector is only less than the given number once the cursor reaches the end of the table.

The following property holds:

take n cursor = catMaybes <$> replicateM n (next cursor)

Throws the following exceptions:

SessionClosedError

If the session is closed.

CursorClosedError

If the cursor is closed.

Variant of take that accepts an additional predicate to determine whether or not to continue reading.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" Nothing
  LSMT.insert table 1 "World" Nothing
  LSMT.withCursor table $ \cursor -> do
    traverse_ print
      =<< LSMT.takeWhile 32 (<1) cursor
:}
Entry (Key 0) (Value "Hello")

The worst-case disk I/O complexity of this operation is \(O(\frac{b}{P})\), where the variable \(b\) refers to the length of the output vector, which is at most equal to the given number. In practice, the length of the output vector is only less than the given number when the predicate returns false or the cursor reaches the end of the table.

The following properties hold:

takeWhile n (const True) cursor = take n cursor

takeWhile n (const False) cursor = pure empty

Throws the following exceptions:

SessionClosedError

If the session is closed.

CursorClosedError

If the cursor is closed.

Save the current state of the table to disk as a snapshot under the given snapshot name. This is the only mechanism that persists a table. Each snapshot must have a unique name, which may be used to restore the table from that snapshot using openTableFromSnapshot. Saving a snapshot does not close the table.

Saving a snapshot is relatively cheap when compared to opening a snapshot. However, it is not so cheap that one should use it after every operation.

>>> :{
runExample $ \session table -> do
  LSMT.insert table 0 "Hello" Nothing
  LSMT.insert table 1 "World" Nothing
  LSMT.saveSnapshot "example" "Key Value Blob" table
:}

The worst-case disk I/O complexity of this operation depends on the merge policy of the table:

LazyLevelling

\(O(T \log_T \frac{n}{B})\).

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

SnapshotExistsError

If a snapshot with the same name already exists.

Run an action with access to a table from a snapshot.

>>> :{
runExample $ \session table -> do
  -- Save snapshot
  LSMT.insert table 0 "Hello" Nothing
  LSMT.insert table 1 "World" Nothing
  LSMT.saveSnapshot "example" "Key Value Blob" table
  -- Open snapshot
  LSMT.withTableFromSnapshot @_ @Key @Value @Blob session "example" "Key Value Blob" $ \table' -> do
      LSMT.withCursor table' $ \cursor ->
        traverse_ print
          =<< LSMT.take 32 cursor
:}
Entry (Key 0) (Value "Hello")
Entry (Key 1) (Value "World")

The worst-case disk I/O complexity of this operation is \(O(\frac{n}{P})\).

This function is exception-safe for both synchronous and asynchronous exceptions.

It is recommended to use this function instead of openTableFromSnapshot and closeTable.

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

SnapshotDoesNotExistError

If no snapshot with the given name exists.

SnapshotCorruptedError

If the snapshot data is corrupted.

SnapshotNotCompatibleError

If the snapshot has a different label or is a different table type.

Variant of withTableFromSnapshot that accepts table configuration overrides.

Open a table from a named snapshot.

>>> :{
runExample $ \session table -> do
  -- Save snapshot
  LSMT.insert table 0 "Hello" Nothing
  LSMT.insert table 1 "World" Nothing
  LSMT.saveSnapshot "example" "Key Value Blob" table
  -- Open snapshot
  bracket
    (LSMT.openTableFromSnapshot @_ @Key @Value @Blob session "example" "Key Value Blob")
    LSMT.closeTable $ \table' -> do
      LSMT.withCursor table' $ \cursor ->
        traverse_ print
          =<< LSMT.take 32 cursor
:}
Entry (Key 0) (Value "Hello")
Entry (Key 1) (Value "World")

The worst-case disk I/O complexity of this operation is \(O(\frac{n}{P})\).

Warning: The new table must be independently closed using closeTable.

Throws the following exceptions:

SessionClosedError

If the session is closed.

TableClosedError

If the table is closed.

SnapshotDoesNotExistError

If no snapshot with the given name exists.

SnapshotCorruptedError

If the snapshot data is corrupted.

SnapshotNotCompatibleError

If the snapshot has a different label or is a different table type.

Variant of openTableFromSnapshot that accepts table configuration overrides.

Check if the named snapshot exists.

>>> :{
runExample $ \session table -> do
  -- Save snapshot
  LSMT.insert table 0 "Hello" Nothing
  LSMT.insert table 1 "World" Nothing
  LSMT.saveSnapshot "example" "Key Value Blob" table
  -- Check snapshots
  print =<< doesSnapshotExist session "example"
  print =<< doesSnapshotExist session "this_snapshot_does_not_exist"
:}
True
False

The worst-case disk I/O complexity of this operation is \(O(1)\).

Throws the following exceptions:

SessionClosedError

If the session is closed.

Delete the named snapshot.

>>> :{
runExample $ \session table -> do
  -- Save snapshot
  LSMT.insert table 0 "Hello" Nothing
  LSMT.insert table 1 "World" Nothing
  LSMT.saveSnapshot "example" "Key Value Blob" table
  -- Delete snapshot
  LSMT.deleteSnapshot session "example"
:}

The worst-case disk I/O complexity of this operation depends on the merge policy of the table:

LazyLevelling

\(O(T \log_T \frac{n}{B})\).

Throws the following exceptions:

SessionClosedError

If the session is closed.

SnapshotDoesNotExistError

If no snapshot with the given name exists.

List the names of all snapshots.

>>> :{
runExample $ \session table -> do
  -- Save snapshot
  LSMT.insert table 0 "Hello" Nothing
  LSMT.insert table 1 "World" Nothing
  LSMT.saveSnapshot "example" "Key Value Blob" table
  -- List snapshots
  traverse_ print
    =<< listSnapshots session
:}
"example"

The worst-case disk I/O complexity of this operation is \(O(s)\), where \(s\) refers to the number of snapshots in the session.

Throws the following exceptions:

SessionClosedError

If the session is closed.

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

The session salt is used to secure the hash operations in the Bloom filters.

The value of the salt must be kept secret. Otherwise, there are no restrictions on the value.

A collection of configuration parameters for tables, which can be used to tune the performance of the table. To construct a TableConfig, modify the defaultTableConfig, which defines reasonable defaults for all parameters.

For a detailed discussion of fine-tuning the table configuration, see Fine-tuning Table Configuration.

confMergePolicy :: MergePolicy

The merge policy balances the performance of lookups against the performance of updates. Levelling favours lookups. Tiering favours updates. Lazy levelling strikes a middle ground between levelling and tiering, and moderately favours updates. This parameter is explicitly referenced in the documentation of those operations it affects.

confSizeRatio :: SizeRatio

The size ratio pushes the effects of the merge policy to the extreme. If the size ratio is higher, levelling favours lookups more, and tiering and lazy levelling favour updates more. This parameter is referred to as \(T\) in the disk I/O cost of operations.

confWriteBufferAlloc :: WriteBufferAlloc

The write buffer capacity balances the performance of lookups and updates against the in-memory size of the database. If the write buffer is larger, it takes up more memory, but lookups and updates are more efficient. This parameter is referred to as \(B\) in the disk I/O cost of operations. Irrespective of this parameter, the write buffer size cannot exceed 4GiB.

confMergeSchedule :: MergeSchedule

The merge schedule balances the performance of lookups and updates against the consistency of updates. With the one-shot merge schedule, lookups and updates are more efficient overall, but some updates may take much longer than others. With the incremental merge schedule, lookups and updates are less efficient overall, but each update does a similar amount of work. This parameter is explicitly referenced in the documentation of those operations it affects. The merge schedule does not affect the way that table unions are computed. However, any table union must complete all outstanding incremental updates.

confBloomFilterAlloc :: BloomFilterAlloc

The Bloom filter size balances the performance of lookups against the in-memory size of the database. If the Bloom filters are larger, they take up more memory, but lookup operations are more efficient.

confFencePointerIndex :: FencePointerIndexType

The fence-pointer index type supports two types of indexes. The ordinary indexes are designed to work with any key. The compact indexes are optimised for the case where the keys in the database are uniformly distributed, e.g., when the keys are hashes.

confDiskCachePolicy :: DiskCachePolicy

The disk cache policy supports caching lookup operations using the OS page cache. Caching may improve the performance of lookups and updates if database access follows certain patterns.

confMergeBatchSize :: MergeBatchSize

The merge batch size balances the maximum latency of individual update operations, versus the latency of a sequence of update operations. Bigger batches improves overall performance but some updates will take a lot longer than others. The default is to use a large batch size.

The defaultTableConfig defines reasonable defaults for all TableConfig parameters.

>>> confMergePolicy defaultTableConfig
LazyLevelling
>>> confMergeSchedule defaultTableConfig
Incremental
>>> confSizeRatio defaultTableConfig
Four
>>> confWriteBufferAlloc defaultTableConfig
AllocNumEntries 20000
>>> confBloomFilterAlloc defaultTableConfig
AllocRequestFPR 1.0e-3
>>> confFencePointerIndex defaultTableConfig
OrdinaryIndex
>>> confDiskCachePolicy defaultTableConfig
DiskCacheAll
>>> confMergeBatchSize defaultTableConfig
MergeBatchSize 20000

The merge policy balances the performance of lookups against the performance of updates. Levelling favours lookups. Tiering favours updates. Lazy levelling strikes a middle ground between levelling and tiering, and moderately favours updates. This parameter is explicitly referenced in the documentation of those operations it affects.

NOTE: This package only supports lazy levelling.

For a detailed discussion of the merge policy, see Fine-tuning: Merge Policy, Size Ratio, and Write Buffer Size.

The merge schedule balances the performance of lookups and updates against the consistency of updates. The merge schedule does not affect the performance of table unions. With the one-shot merge schedule, lookups and updates are more efficient overall, but some updates may take much longer than others. With the incremental merge schedule, lookups and updates are less efficient overall, but each update does a similar amount of work. This parameter is explicitly referenced in the documentation of those operations it affects.

For a detailed discussion of the effect of the merge schedule, see Fine-tuning: Merge Schedule.

The size ratio pushes the effects of the merge policy to the extreme. If the size ratio is higher, levelling favours lookups more, and tiering and lazy levelling favour updates more. This parameter is referred to as \(T\) in the disk I/O cost of operations.

NOTE: This package only supports a size ratio of four.

For a detailed discussion of the size ratio, see Fine-tuning: Merge Policy, Size Ratio, and Write Buffer Size.

The write buffer capacity balances the performance of lookups and updates against the in-memory size of the table. If the write buffer is larger, it takes up more memory, but lookups and updates are more efficient. Irrespective of this parameter, the write buffer size cannot exceed 4GiB.

For a detailed discussion of the size ratio, see Fine-tuning: Merge Policy, Size Ratio, and Write Buffer Size.

The Bloom filter size balances the performance of lookups against the in-memory size of the table. If the Bloom filters are larger, they take up more memory, but lookup operations are more efficient.

For a detailed discussion of the Bloom filter size, see Fine-tuning: Bloom Filter Size.

The fence-pointer index type supports two types of indexes. The ordinary indexes are designed to work with any key. The compact indexes are optimised for the case where the keys in the database are uniformly distributed, e.g., when the keys are hashes.

For a detailed discussion the fence-pointer index types, see Fine-tuning: Fence-Pointer Index Type.

The disk cache policy determines if lookup operations use the OS page cache. Caching may improve the performance of lookups if database access follows certain patterns.

For a detailed discussion the disk cache policy, see Fine-tuning: Disk Cache Policy.

The merge batch size is a micro-tuning parameter, and in most cases you do need to think about it and can leave it at its default.

When using the Incremental merge schedule, merging is done in batches. This is a trade-off: larger batches tends to mean better overall performance but the downside is that while most updates (inserts, deletes, upserts) are fast, some are slower (when a batch of merging work has to be done).

If you care most about the maximum latency of updates, then use a small batch size. If you don't care about latency of individual operations, just the latency of the overall sequence of operations then use a large batch size. The default is to use a large batch size, the same size as the write buffer itself. The minimum batch size is 1. The maximum batch size is the size of the write buffer confWriteBufferAlloc.

Note that the actual batch size is the minimum of this configuration parameter and the size of the batch of operations performed (e.g. inserts). So if you consistently use large batches, you can use a batch size of 1 and the merge batch size will always be determined by the operation batch size.

A further reason why it may be preferable to use minimal batch sizes is to get good parallel work balance, when using parallelism.

The TableConfigOverride can be used to override the TableConfig when opening a table from a snapshot.

No override of the TableConfig. You can use this as a default value and record update to override some parameters, while being future-proof to new parameters, e.g.

noTableConfigOverride { overrideDiskCachePolicy = DiskCacheNone }

A range of keys.

Union credits are passed to supplyUnionCredits to perform some amount of computation to incrementally complete a union.

Union debt represents the amount of computation that must be performed before an incremental union is completed. This includes the cost of completing incremental unions that were part of a union's input.

Warning: The UnionDebt returned by remainingUnionDebt is an upper bound on the remaining union debt, not the exact union debt.

Raw bytes.

This type imposes no alignment constraint and provides no guarantee of whether the memory is pinned or unpinned.

Serialisation of keys.

Instances should satisfy the following laws:

Identity

deserialiseKey (serialiseKey x) == x

Identity up to slicing

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

Order-preserving serialisation of keys.

Table data is sorted by serialised keys. Range lookups and cursors return entries in this order. If serialisation does not preserve the ordering of unserialised keys, then range lookups and cursors return entries out of order.

If the SerialiseKey instance for a type preserves the ordering, then it can safely be given an instance of SerialiseKeyOrderPreserving. These should satisfy the following law:

Order-preserving

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

Serialised keys are lexicographically ordered. To satisfy the Order-preserving law, keys should be serialised into a big-endian format.

Serialisation of values and blobs.

Instances should satisfy the following laws:

Identity

deserialiseValue (serialiseValue x) == x

Identity up to slicing

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