{-# OPTIONS_GHC -Wno-redundant-constraints #-}
{-# OPTIONS_GHC -Wno-unused-top-binds #-}
+
-- | On disk key-value tables, implemented as Log Structured Merge (LSM) trees.
+
-- This module is the API for \"normal\" tables, as opposed to monoidal tables.
+
-- * Normal key\/value operations: lookup, insert, delete.
+
-- * Range lookups by key or key prefix
+
-- * Support for BLOBs: large auxilliary values associated with a key
+
-- * On-disk durability is _only_ via named snapshots: ordinary operations
+
-- are otherwise not retained.
+
-- * Opening tables from previous named snapshots
+
-- * Full persistent data structure by cheap table duplication: all duplicate
+
-- tables can be both accessed and modified.
-- This module is intended to be imported qualified.
-------------------------------------------------------------------------------}
-
-- | A handle to a table.
+
-- | 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 handle is the object/reference by which an in-use LSM table
-
-- will be operated upon. In our API it identifies a single mutable instance of
+
-- parts. A table handle 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 multiple-handles feature allows for there to may be many
-- such instances in use at once.
type TableHandle :: (Type -> Type) -> Type -> Type -> Type -> Type
, thConfig :: !TableConfig
-
-- | Table configuration parameters, like tuning parameters.
+
-- | Table configuration parameters, including LSM tree tuning parameters.
-- Some config options are fixed (for now):
-- * Merge policy: Tiering
-- For more information about compatibility, see 'Session'.
deriving instance Eq TableConfig
-
-- | Create a new table referenced by a table handle.
+
-- | Create a new empty table, returning a fresh table handle.
+
-- NOTE: table handles hold open resources (such as open files) and should be
+
-- closed using 'close' as soon as they are no longer used.
-
-- NOTE: close table handles using 'close' as soon as they are
+
-- | 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 'open' via that
+
-- name. Names are strings and the management of the names is up to the user of
+
-- The names correspond to disk files, which imposes some constraints on length
+
-- and what characters can be used.
-- Snapshotting does not close the table handle.
-
-- Taking a snapshot should be relatively cheap, but it is not so cheap that one
-
-- can use one after every operation. It is relatively cheap because of a reason
-
-- similar to the reason why 'duplicate' is cheap. On-disk and in-memory data is
-
-- immutable, which means we can write (the relatively small) in-memory parts to
-
-- disk, and create hard links for existing files.
+
-- 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.
, SomeSerialisationConstraint k
-
-- | Open a table through a snapshot, returning a new table handle.
+
-- | Open a table from a named snapshot, returning a new table handle.
-- NOTE: close table handles using 'close' as soon as they are
+
--TODO: we're missing an operation to delete a snapshot that is no longer
+
-- required. This is necessary for management of disk space.
{-------------------------------------------------------------------------------
Mutiple writable table handles
-------------------------------------------------------------------------------}
-
-- | Create a cheap, independent duplicate of a table handle. This returns a new
+
-- | Create an independent duplicate of a table handle. This returns a new
-- A table handle and its duplicate are logically independent: changes to one
-- are not visible to the other.
-
-- Duplication is cheap because on-disk and in-memory data is immutable, which
-
-- means we can /share/ data instead of copying it. Duplication has small
-
-- computation, storage and memory overheads.
+
-- This operation enables /fully persistent/ use of tables by duplicating the
+
-- table prior to a batch of mutating operations. The duplicate retains the
+
-- the original table value, and can still be modified independently.
+
-- This is persistence in the sense 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
+
-- NOTE: duplication create a new table handle, which should be closed when no
-
-- NOTE: close table handles using 'close' as soon as they are
=> TableHandle m k v blob
