lsm-tree-1.0.0.2: lsm-tree.cabal
cabal-version: 3.4
name: lsm-tree
version: 1.0.0.2
synopsis: Log-structured merge-trees
description:
This package contains an efficient implementation of on-disk key–value storage, implemented as a log-structured merge-tree, LSM-tree or LSMT.
An LSM-tree is a data structure for key–value mappings, similar to "Data.Map", but optimized for large tables with a high insertion volume.
It has support for:
* Basic key–value operations, such as lookup, insert, and delete.
* Range lookups, which efficiently retrieve the values for all keys in a given range.
* Monoidal upserts which combine the stored and new values.
* BLOB storage which associates a large auxiliary BLOB with a key.
* Durable on-disk persistence and rollback via named snapshots.
* Cheap table duplication where all duplicates can be independently accessed and modified.
* High-performance lookups on SSDs using I\/O batching and parallelism.
This package exports two modules:
* "Database.LSMTree.Simple"
This module exports a simplified API which picks sensible defaults for a number of configuration parameters.
It does not support upserts or BLOBs, due to their unintuitive interaction, see [Upsert and BLOB](#upsertandblob).
If you are looking at this package for the first time, it is strongly recommended that you start by reading this module.
* "Database.LSMTree"
This module exports the full API.
== Upsert and BLOB #upsertandblob#
The interaction between upserts and BLOBs is unintuitive.
A upsert updates the value associated with the key by combining the new and old values with a user-specified function.
However, any BLOB associated with the key is simply deleted.
== Portability #portability#
* This package only supports 64-bit, little-endian systems.
* On Windows, the package has only been tested with NTFS filesystems.
* On Linux, executables using this package, including test and benchmark suites, must be compiled with the [@-threaded@](https://downloads.haskell.org/ghc/latest/docs/users_guide/phases.html#ghc-flag-threaded) RTS option enabled.
== Concurrency #concurrency#
LSM-trees can be used concurrently, but with a few restrictions:
* Each session locks its session directory.
This means that a database cannot be accessed from different processes at the same time.
* Tables can be used concurrently and concurrent use of read operations such as lookups is deterministic.
However, concurrent use of write operations such as insert or delete with any other operation results in a race condition.
== Performance #performance#
The worst-case behaviour of the library is described using [big-O notation](http://en.wikipedia.org/wiki/Big_O_notation).
The documentation provides two measures of complexity:
* The time complexity of operations is described in terms of the number of disk I\/O operations and referred to as the disk I\/O complexity.
In practice, the time of the operations on LSM-trees is dominated by the number of disk I\/O actions.
* The space complexity of tables is described in terms of the in-memory size of an LSM-tree table.
Both the in-memory and on-disk size of an LSM-tree table scale linearly with the number of physical entries.
However, the in-memory size of an LSM-tree table is smaller than its on-disk size by a significant constant.
This is discussed in detail below, under [In-memory size of tables](#performance_size).
The complexities are described in terms of the following variables and constants:
* The variable \(n\) refers to the number of /physical/ table entries.
A /physical/ table entry is any key–operation pair, e.g., @Insert k v@ or @Delete k@, whereas a /logical/ table entry is determined by all physical entries with the same key.
If the variable \(n\) is used to describe the complexity of an operation that involves multiple tables, it refers to the sum of all table entries.
* The variable \(o\) refers to the number of open tables and cursors in the session.
* The variable \(s\) refers to the number of snapshots in the session.
* The variable \(b\) usually refers to the size of a batch of inputs\/outputs.
Its precise meaning is explained for each occurrence.
* The constant \(B\) refers to the size of the write buffer,
which is determined by the @TableConfig@ parameter @confWriteBufferAlloc@.
* The constant \(T\) refers to the size ratio of the table,
which is determined by the @TableConfig@ parameter @confSizeRatio@.
* The constant \(P\) refers to the average number of key–value pairs that fit in a page of memory.
=== Disk I\/O cost of operations #performance_time#
The following table summarises the worst-case cost of the operations on LSM-trees measured in the number of disk I\/O operations.
If the cost depends on the merge policy or merge schedule, then the table contains one entry for each relevant combination.
Otherwise, the merge policy and\/or merge schedule is listed as N\/A.
The merge policy and merge schedule are determined by the @TableConfig@ parameters @confMergePolicy@ and @confMergeSchedule@.
+----------+------------------------+-----------------+-----------------+------------------------------------------------+
| Resource | Operation | Merge policy | Merge schedule | Worst-case disk I\/O complexity |
+==========+========================+=================+=================+================================================+
| Session | Open | N\/A | N\/A | \(O(1)\) |
+----------+------------------------+-----------------+-----------------+------------------------------------------------+
| | Close | @LazyLevelling@ | N\/A | \(O(o \: T \: \log_T \frac{n}{B})\) |
+----------+------------------------+-----------------+-----------------+------------------------------------------------+
| Table | New | N\/A | N\/A | \(O(1)\) |
+----------+------------------------+-----------------+-----------------+------------------------------------------------+
| | Close | @LazyLevelling@ | N\/A | \(O(T \: \log_T \frac{n}{B})\) |
+----------+------------------------+-----------------+-----------------+------------------------------------------------+
| | Lookup | @LazyLevelling@ | N\/A | \(O(T \: \log_T \frac{n}{B})\) |
+----------+------------------------+-----------------+-----------------+------------------------------------------------+
| | Range Lookup | N\/A | N\/A | \(O(T \: \log_T \frac{n}{B} + \frac{b}{P})\)* |
+----------+------------------------+-----------------+-----------------+------------------------------------------------+
| | Insert\/Delete\/Update | @LazyLevelling@ | @Incremental@ | \(O(\frac{1}{P} \: \log_T \frac{n}{B})\) |
+----------+------------------------+-----------------+-----------------+------------------------------------------------+
| | | @LazyLevelling@ | @OneShot@ | \(O(\frac{n}{P})\) |
+----------+------------------------+-----------------+-----------------+------------------------------------------------+
| | Duplicate | N\/A | N\/A | \(O(0)\) |
+----------+------------------------+-----------------+-----------------+------------------------------------------------+
| | Union | N\/A | N\/A | \(O(\frac{n}{P})\) |
+----------+------------------------+-----------------+-----------------+------------------------------------------------+
| Snapshot | Save | @LazyLevelling@ | N\/A | \(O(T \: \log_T \frac{n}{B})\) |
+----------+------------------------+-----------------+-----------------+------------------------------------------------+
| | Open | N\/A | N\/A | \(O(\frac{n}{P})\) |
+----------+------------------------+-----------------+-----------------+------------------------------------------------+
| | Delete | @LazyLevelling@ | N\/A | \(O(T \: \log_T \frac{n}{B})\) |
+----------+------------------------+-----------------+-----------------+------------------------------------------------+
| | List | N\/A | N\/A | \(O(s)\) |
+----------+------------------------+-----------------+-----------------+------------------------------------------------+
| Cursor | New | @LazyLevelling@ | N\/A | \(O(T \: \log_T \frac{n}{B})\) |
+----------+------------------------+-----------------+-----------------+------------------------------------------------+
| | Close | @LazyLevelling@ | N\/A | \(O(T \: \log_T \frac{n}{B})\) |
+----------+------------------------+-----------------+-----------------+------------------------------------------------+
| | Next | N\/A | N\/A | \(O(\frac{1}{P})\) |
+----------+------------------------+-----------------+-----------------+------------------------------------------------+
(*The variable \(b\) refers to the number of entries retrieved by the range lookup.)
=== Table Size #performance_size#
The in-memory and the on-disk size of an LSM-tree scale /linearly/ with the number of physical entries.
However, the in-memory size is smaller by a significant factor.
Let us look at a table that uses the default configuration and has 100 million entries with 34 byte keys and 60 byte values.
The total size of 100 million key–value pairs is approximately 8.75GiB.
Hence, the on-disk size would be at least 8.75GiB, not counting the overhead for metadata.
The in-memory size would be approximately 265.39MiB:
* The write buffer would store at most 20,000 entries, which is approximately 2.86MiB.
* The fence-pointer indexes would store approximately 2.29 million keys, which is approximately 9.30MiB.
* The Bloom filters would use 15.78 bits per entry, which is approximately 188.11MiB.
For a discussion of how the sizes of these components are determined by the table configuration, see [Fine-tuning Table Configuration](#fine_tuning).
The total size of an LSM-tree must not exceed \(2^{41}\) physical entries.
Violation of this condition /is/ checked and will throw a 'TableTooLargeError'.
=== Fine-tuning Table Configuration #fine_tuning#
[@confMergePolicy@]
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@]
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@]
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.
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@]
The /merge schedule/ balances the performance of lookups and updates against the smooth performance 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.
[@confBloomFilterAlloc@]
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.
[@confFencePointerIndex@]
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@]
The /disk cache policy/ determines if lookup operations use the OS page cache.
Caching may improve the performance of lookups and updates if database access follows certain patterns.
[@confMergeBatchSize@]
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.
==== Fine-tuning: Merge Policy, Size Ratio, and Write Buffer Size #fine_tuning_data_layout#
The configuration parameters @confMergePolicy@, @confSizeRatio@, and @confWriteBufferAlloc@ affect how the table organises its data.
To understand what effect these parameters have, one must have a basic understanding of how an LSM-tree stores its data.
The physical entries in an LSM-tree are key–operation pairs, which pair a key with an operation such as an @Insert@ with a value or a @Delete@.
These key–operation pairs are organised into /runs/, which are sequences of key–operation pairs sorted by their key.
Runs are organised into /levels/, which are unordered sequences or runs.
Levels are organised hierarchically.
Level 0 is kept in memory, and is referred to as the /write buffer/.
All subsequent levels are stored on disk, with each run stored in its own file.
The following shows an example LSM-tree layout, with each run as a boxed sequence of keys and each level as a row.
\[
\begin{array}{l:l}
\text{Level}
&
\text{Data}
\\
0
&
\fbox{\(\texttt{4}\,\_\)}
\\
1
&
\fbox{\(\texttt{1}\,\texttt{3}\)}
\quad
\fbox{\(\texttt{2}\,\texttt{7}\)}
\\
2
&
\fbox{\(\texttt{0}\,\texttt{2}\,\texttt{3}\,\texttt{4}\,\texttt{5}\,\texttt{6}\,\texttt{8}\,\texttt{9}\)}
\end{array}
\]
The data in an LSM-tree is /partially sorted/: only the key–operation pairs within each run are sorted and deduplicated.
As a rule of thumb, keeping more of the data sorted means lookup operations are faster but update operations are slower.
The configuration parameters @confMergePolicy@, @confSizeRatio@, and @confWriteBufferAlloc@ directly affect a table's data layout.
The parameter @confWriteBufferAlloc@ determines the capacity of the write buffer.
[@AllocNumEntries maxEntries@]:
The write buffer can contain at most @maxEntries@ entries.
The constant \(B\) refers to the value of @maxEntries@.
Irrespective of this parameter, the write buffer size cannot exceed 4GiB.
The parameter @confSizeRatio@ determines the ratio between the capacities of successive levels.
The constant \(T\) refers to the value of @confSizeRatio@.
For instance, if \(B = 2\) and \(T = 2\), then
\[
\begin{array}{l:l}
\text{Level} & \text{Capacity}
\\
0 & B \cdot T^0 = 2
\\
1 & B \cdot T^1 = 4
\\
2 & B \cdot T^2 = 8
\\
\ell & B \cdot T^\ell
\end{array}
\]
The merge policy @confMergePolicy@ determines the number of runs per level.
In a /tiering/ LSM-tree, each level contains \(T\) runs.
In a /levelling/ LSM-tree, each level contains one single run.
The /lazy levelling/ policy uses levelling only for the last level and uses tiering for all preceding levels.
The previous example used lazy levelling.
The following examples illustrate the different merge policies using the same data, assuming \(B = 2\) and \(T = 2\).
\[
\begin{array}{l:l:l:l}
\text{Level}
&
\text{Tiering}
&
\text{Levelling}
&
\text{Lazy Levelling}
\\
0
&
\fbox{\(\texttt{4}\,\_\)}
&
\fbox{\(\texttt{4}\,\_\)}
&
\fbox{\(\texttt{4}\,\_\)}
\\
1
&
\fbox{\(\texttt{1}\,\texttt{3}\)}
\quad
\fbox{\(\texttt{2}\,\texttt{7}\)}
&
\fbox{\(\texttt{1}\,\texttt{2}\,\texttt{3}\,\texttt{7}\)}
&
\fbox{\(\texttt{1}\,\texttt{3}\)}
\quad
\fbox{\(\texttt{2}\,\texttt{7}\)}
\\
2
&
\fbox{\(\texttt{4}\,\texttt{5}\,\texttt{7}\,\texttt{8}\)}
\quad
\fbox{\(\texttt{0}\,\texttt{2}\,\texttt{3}\,\texttt{9}\)}
&
\fbox{\(\texttt{0}\,\texttt{2}\,\texttt{3}\,\texttt{4}\,\texttt{5}\,\texttt{6}\,\texttt{8}\,\texttt{9}\)}
&
\fbox{\(\texttt{0}\,\texttt{2}\,\texttt{3}\,\texttt{4}\,\texttt{5}\,\texttt{6}\,\texttt{8}\,\texttt{9}\)}
\end{array}
\]
Tiering favours the performance of updates.
Levelling favours the performance of lookups.
Lazy levelling strikes a middle ground between tiering and levelling.
It favours the performance of lookup operations for the oldest data and enables more deduplication,
without the impact that full levelling has on update operations.
==== Fine-tuning: Merge Schedule #fine_tuning_merge_schedule#
The configuration parameter @confMergeSchedule@ affects the worst-case performance of lookup and update operations and the structure of runs.
Regardless of the merge schedule, the amortised disk I\/O complexity of lookups and updates is /logarithmic/ in the size of the table.
When the write buffer fills up, its contents are flushed to disk as a run and added to level 1.
When some level fills up, its contents are flushed down to the next level.
Eventually, as data is flushed down, runs must be merged.
This package supports two schedules for merging:
* Using the @OneShot@ merge schedule, runs must always be kept fully sorted and deduplicated.
However, flushing a run down to the next level may cause the next level to fill up,
in which case it too must be flushed and merged futher down.
In the worst case, this can cascade down the entire table.
Consequently, the worst-case disk I\/O complexity of updates is /linear/ in the size of the table.
This is unacceptable for real-time systems and other use cases where unresponsiveness is unacceptable.
* Using the @Incremental@ merge schedule, runs can be /partially merged/, which allows the merging work to be spead out evenly across all update operations.
This aligns the worst-case and average-case disk I\/O complexity of updates—both are /logarithmic/ in the size of the table.
The cost is a small constant overhead for both lookup and update operations.
The merge schedule does not affect the performance of table unions.
The amortised disk I\/O complexity of one-shot unions is /linear/ in the size of the tables.
Instead, there are separate operations for incremental and oneshot unions.
For incremental unions, it is up to the user to spread the merging work out evenly over time.
==== Fine-tuning: Bloom Filter Size #fine_tuning_bloom_filter_size#
The configuration parameter @confBloomFilterAlloc@ affects the size of the Bloom filters,
which balances the performance of lookups against the in-memory size of the table.
Tables maintain a [Bloom filter](https://en.wikipedia.org/wiki/Bloom_filter) in memory for each run on disk.
These Bloom filters are probablilistic datastructures that are used to track which keys are present in their corresponding run.
Querying a Bloom filter returns either \"maybe\" meaning the key is possibly in the run or \"no\" meaning the key is definitely not in the run.
When a query returns \"maybe\" while the key is /not/ in the run, this is referred to as a /false positive/.
While the database executes a lookup operation, any Bloom filter query that returns a false positive causes the database to unnecessarily read a page from disk.
The probabliliy of these spurious reads follow a [binomial distribution](https://en.wikipedia.org/wiki/Binomial_distribution) \(\text{Binomial}(r,\text{FPR})\)
where \(r\) refers to the number of runs and \(\text{FPR}\) refers to the false-positive rate of the Bloom filters.
Hence, the expected number of spurious reads for each lookup operation is \(r\cdot\text{FPR}\).
The number of runs \(r\) is proportional to the number of physical entries in the table. Its exact value depends on the merge policy of the table:
[@LazyLevelling@]
\(r = T (\log_T\frac{n}{B} - 1) + 1\).
The false-positive rate scales exponentially with size of the Bloom filters in bits per entry.
+---------------------------+----------------------+
| False-positive rate (FPR) | Bits per entry (BPE) |
+===========================+======================+
| \(1\text{ in }10\) | \(\approx 4.77 \) |
+---------------------------+----------------------+
| \(1\text{ in }100\) | \(\approx 9.85 \) |
+---------------------------+----------------------+
| \(1\text{ in }1{,}000\) | \(\approx 15.78 \) |
+---------------------------+----------------------+
| \(1\text{ in }10{,}000\) | \(\approx 22.57 \) |
+---------------------------+----------------------+
| \(1\text{ in }100{,}000\) | \(\approx 30.22 \) |
+---------------------------+----------------------+
The configuration parameter @confBloomFilterAlloc@ can be specified in two ways:
[@AllocFixed bitsPerEntry@]
Allocate the requested number of bits per entry in the table.
The value must strictly positive, but fractional values are permitted.
The recommended range is \([2, 24]\).
[@AllocRequestFPR falsePositiveRate@]
Allocate the required number of bits per entry to get the requested false-positive rate.
The value must be in the range \((0, 1)\).
The recommended range is \([1\mathrm{e}{ -5 },1\mathrm{e}{ -2 }]\).
The total in-memory size of all Bloom filters scales /linearly/ with the number of physical entries in the table and is determined by the number of physical entries multiplied by the number of bits per physical entry, i.e, \(n\cdot\text{BPE}\).
Let us consider a table with 100 million physical entries which uses the default table configuration for every parameter other than the Bloom filter size.
+---------------------------+----------------------+------------------------------------------------------------------+
| False-positive rate (FPR) | Bloom filter size | Expected spurious reads per lookup |
+===========================+======================+==================================================================+
| \(1\text{ in }10\) | \( 56.86\text{MiB}\) | \( 2.56\text{ spurious reads every lookup }\) |
+---------------------------+----------------------+------------------------------------------------------------------+
| \(1\text{ in }100\) | \(117.42\text{MiB}\) | \( 1 \text{ spurious read every } 3.91\text{ lookups }\) |
+---------------------------+----------------------+------------------------------------------------------------------+
| \(1\text{ in }1{,}000\) | \(188.11\text{MiB}\) | \( 1 \text{ spurious read every } 39.10\text{ lookups }\) |
+---------------------------+----------------------+------------------------------------------------------------------+
| \(1\text{ in }10{,}000\) | \(269.06\text{MiB}\) | \( 1 \text{ spurious read every } 391.01\text{ lookups }\) |
+---------------------------+----------------------+------------------------------------------------------------------+
| \(1\text{ in }100{,}000\) | \(360.25\text{MiB}\) | \( 1 \text{ spurious read every } 3910.19\text{ lookups }\) |
+---------------------------+----------------------+------------------------------------------------------------------+
==== Fine-tuning: Fence-Pointer Index Type #fine_tuning_fence_pointer_index_type#
The configuration parameter @confFencePointerIndex@ affects the type and size of the fence-pointer indexes.
Tables maintain a fence-pointer index in memory for each run on disk.
These fence-pointer indexes store the keys at the boundaries of each page of memory to ensure that each lookup has to read at most one page of memory from each run.
Tables support two types of fence-pointer indexes:
[@OrdinaryIndex@]
Ordinary indexes are designed for any use case.
Ordinary indexes store one serialised key per page of memory.
The average total in-memory size of all indexes is \(K \cdot \frac{n}{P}\) bits,
where \(K\) refers to the average size of a serialised key in bits.
[@CompactIndex@]
Compact indexes are designed for the use case where the keys in the table are uniformly distributed, such as when using hashes.
Compact indexes store the 64 most significant bits of the minimum serialised key of each page of memory.
This requires that serialised keys are /at least/ 64 bits in size.
Compact indexes store 1 additional bit per page of memory to resolve collisions, 1 additional bit per page of memory to mark entries that are larger than one page, and a negligible amount of memory for tie breakers.
The average total in-memory size of all indexes is \(66 \cdot \frac{n}{P}\) bits.
==== Fine-tuning: Disk Cache Policy #fine_tuning_disk_cache_policy#
The configuration parameter @confDiskCachePolicy@ determines how the database uses the OS page cache.
This may improve performance if the database's /access pattern/ has good /temporal locality/ or good /spatial locality/.
The database's access pattern refers to the pattern by which entries are accessed by lookup operations.
An access pattern has good temporal locality if it is likely to access entries that were recently accessed or updated.
An access pattern has good spatial locality if it is likely to access entries that have nearby keys.
* Use the @DiskCacheAll@ policy if the database's access pattern has either good spatial locality or both good spatial and temporal locality.
* Use the @DiskCacheLevelOneTo l@ policy if the database's access pattern has good temporal locality for updates only.
The variable @l@ determines the number of levels that are cached.
For a description of levels, see [Merge Policy, Size Ratio, and Write Buffer Size](#fine_tuning_data_layout).
With this setting, the database can be expected to cache up to \(\frac{k}{P}\) pages of memory,
where \(k\) refers to the number of entries that fit in levels \([1,l]\) and is defined as \(\sum_{i=1}^{l}BT^{i}\).
* Use the @DiskCacheNone@ policy if the database's access pattern has does not have good spatial or temporal locality.
For instance, if the access pattern is uniformly random.
==== Fine-tuning: Merge Batch Size #fine_tuning_merge_batch_size#
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.
== References
The implementation of LSM-trees in this package draws inspiration from:
* Chris Okasaki.
1998.
\"Purely Functional Data Structures\"
[doi:10.1017/CBO9780511530104](https://doi.org/10.1017/CBO9780511530104)
* Niv Dayan, Manos Athanassoulis, and Stratos Idreos.
2017.
\"Monkey: Optimal Navigable Key-Value Store.\"
[doi:10.1145/3035918.3064054](https://doi.org/10.1145/3035918.3064054)
* Subhadeep Sarkar, Dimitris Staratzis, Ziehen Zhu, and Manos Athanassoulis.
2021.
\"Constructing and analyzing the LSM compaction design space.\"
[doi:10.14778/3476249.3476274](https://doi.org/10.14778/3476249.3476274)
license: Apache-2.0
license-files:
LICENSE
NOTICE
author:
Duncan Coutts, Joris Dral, Matthias Heinzel, Wolfgang Jeltsch, Wen Kokke, and Alex Washburn
maintainer: oso@intersectmbo.org
copyright: (c) 2023-2025 Cardano Development Foundation
category: Database
build-type: Simple
tested-with: GHC ==9.2 || ==9.4 || ==9.6 || ==9.8 || ==9.10 || ==9.12
extra-doc-files: CHANGELOG.md
data-dir: test/golden-file-data/
source-repository head
type: git
location: https://github.com/IntersectMBO/lsm-tree
subdir: lsm-tree
source-repository this
type: git
location: https://github.com/IntersectMBO/lsm-tree
subdir: lsm-tree
tag: lsm-tree-1.0.0.2
common warnings
ghc-options:
-Wall -Wcompat -Wincomplete-uni-patterns
-Wincomplete-record-updates -Wpartial-fields -Widentities
-Wredundant-constraints -Wmissing-export-lists
-Wno-unticked-promoted-constructors -Wunused-packages
ghc-options: -Werror=missing-deriving-strategies
common wno-x-partial
if impl(ghc >=9.8)
-- No errors for x-partial functions. We might remove this in the future if
-- we decide to refactor code that uses partial functions.
ghc-options: -Wno-x-partial
common language
default-language: GHC2021
default-extensions:
DeriveAnyClass
DerivingStrategies
DerivingVia
ExplicitNamespaces
GADTs
LambdaCase
OverloadedRecordDot
RecordWildCards
RoleAnnotations
ViewPatterns
library
import: language, warnings, wno-x-partial
hs-source-dirs: src
exposed-modules:
Database.LSMTree
Database.LSMTree.Simple
build-depends:
, base >=4.16 && <4.23
, blockio ^>=0.1
, contra-tracer ^>=0.1 || ^>=0.2
, deepseq ^>=1.4 || ^>=1.5
, fs-api ^>=0.4
, io-classes ^>=1.6 || ^>=1.7 || ^>=1.8.0.1 || ^>=1.9 || ^>=1.10
, io-classes:strict-mvar
, lsm-tree:control
, lsm-tree:core
, primitive ^>=0.9
, random ^>=1.0 || ^>=1.1 || ^>=1.2 || ^>=1.3
, text ^>=2.1.1
, vector ^>=0.13
library core
import: language, warnings, wno-x-partial
visibility: private
hs-source-dirs: src-core
exposed-modules:
Database.LSMTree.Internal.Arena
Database.LSMTree.Internal.Assertions
Database.LSMTree.Internal.BitMath
Database.LSMTree.Internal.BlobFile
Database.LSMTree.Internal.BlobRef
Database.LSMTree.Internal.BloomFilter
Database.LSMTree.Internal.ByteString
Database.LSMTree.Internal.ChecksumHandle
Database.LSMTree.Internal.Chunk
Database.LSMTree.Internal.Config
Database.LSMTree.Internal.Config.Override
Database.LSMTree.Internal.CRC32C
Database.LSMTree.Internal.Cursor
Database.LSMTree.Internal.Entry
Database.LSMTree.Internal.IncomingRun
Database.LSMTree.Internal.Index
Database.LSMTree.Internal.Index.Compact
Database.LSMTree.Internal.Index.CompactAcc
Database.LSMTree.Internal.Index.Ordinary
Database.LSMTree.Internal.Index.OrdinaryAcc
Database.LSMTree.Internal.Lookup
Database.LSMTree.Internal.Map.Range
Database.LSMTree.Internal.Merge
Database.LSMTree.Internal.MergeSchedule
Database.LSMTree.Internal.MergingRun
Database.LSMTree.Internal.MergingTree
Database.LSMTree.Internal.MergingTree.Lookup
Database.LSMTree.Internal.Page
Database.LSMTree.Internal.PageAcc
Database.LSMTree.Internal.PageAcc1
Database.LSMTree.Internal.Paths
Database.LSMTree.Internal.Primitive
Database.LSMTree.Internal.Range
Database.LSMTree.Internal.RawBytes
Database.LSMTree.Internal.RawOverflowPage
Database.LSMTree.Internal.RawPage
Database.LSMTree.Internal.Readers
Database.LSMTree.Internal.Run
Database.LSMTree.Internal.RunAcc
Database.LSMTree.Internal.RunBuilder
Database.LSMTree.Internal.RunNumber
Database.LSMTree.Internal.RunReader
Database.LSMTree.Internal.Serialise
Database.LSMTree.Internal.Serialise.Class
Database.LSMTree.Internal.Snapshot
Database.LSMTree.Internal.Snapshot.Codec
Database.LSMTree.Internal.Types
Database.LSMTree.Internal.UniqCounter
Database.LSMTree.Internal.Unsafe
Database.LSMTree.Internal.Unsliced
Database.LSMTree.Internal.Vector
Database.LSMTree.Internal.Vector.Growing
Database.LSMTree.Internal.WriteBuffer
Database.LSMTree.Internal.WriteBufferBlobs
Database.LSMTree.Internal.WriteBufferReader
Database.LSMTree.Internal.WriteBufferWriter
build-depends:
, base >=4.16 && <4.23
, bitvec ^>=1.1
, blockio ^>=0.1
, bloomfilter-blocked ^>=0.1
, bytestring ^>=0.11.4.0 || ^>=0.12.1.0
, cborg ^>=0.2.10.0
, containers ^>=0.6 || ^>=0.7 || ^>=0.8
, contra-tracer ^>=0.1 || ^>=0.2
, crc32c ^>=0.2.1
, deepseq ^>=1.4 || ^>=1.5
, filepath ^>=1.4 || ^>=1.5
, fs-api ^>=0.4
, io-classes ^>=1.6 || ^>=1.7 || ^>=1.8.0.1 || ^>=1.9 || ^>=1.10
, io-classes:strict-mvar
, lsm-tree:control
, lsm-tree:kmerge
, primitive ^>=0.9
, serialise ^>=0.2
, text ^>=2.1.1
, utf8-string ^>=1.0
, vector ^>=0.13
, vector-algorithms ^>=0.9
if impl(ghc >=9.4)
other-modules: Database.LSMTree.Internal.StrictArray
build-depends: data-elevator ^>=0.1.0.2 || ^>=0.2
cpp-options: -DHAVE_STRICT_ARRAY
library extras
import: language, warnings
visibility: private
hs-source-dirs: src-extras
exposed-modules:
Database.LSMTree.Extras
Database.LSMTree.Extras.Generators
Database.LSMTree.Extras.Index
Database.LSMTree.Extras.MergingRunData
Database.LSMTree.Extras.MergingTreeData
Database.LSMTree.Extras.NoThunks
Database.LSMTree.Extras.Orphans
Database.LSMTree.Extras.Random
Database.LSMTree.Extras.ReferenceImpl
Database.LSMTree.Extras.RunData
Database.LSMTree.Extras.UTxO
build-depends:
, base >=4.16 && <4.23
, bitvec
, blockio
, bytestring
, containers
, contra-tracer
, deepseq
, fs-api
, fs-sim
, io-classes:strict-mvar
, io-classes:strict-stm
, lsm-tree
, lsm-tree:control
, lsm-tree:core
, lsm-tree:kmerge
, lsm-tree:prototypes
, nonempty-containers
, nothunks
, primitive
, QuickCheck
, quickcheck-instances
, random
, vector
, wide-word
test-suite lsm-tree-test
import: language, warnings, wno-x-partial
type: exitcode-stdio-1.0
hs-source-dirs: test
main-is: Main.hs
other-modules:
Database.LSMTree.Class
Database.LSMTree.Class.Common
Database.LSMTree.Model
Database.LSMTree.Model.IO
Database.LSMTree.Model.Session
Database.LSMTree.Model.Table
Paths_lsm_tree
Test.Database.LSMTree
Test.Database.LSMTree.Class
Test.Database.LSMTree.Generators
Test.Database.LSMTree.Internal
Test.Database.LSMTree.Internal.Arena
Test.Database.LSMTree.Internal.BlobFile.FS
Test.Database.LSMTree.Internal.BloomFilter
Test.Database.LSMTree.Internal.Chunk
Test.Database.LSMTree.Internal.CRC32C
Test.Database.LSMTree.Internal.Entry
Test.Database.LSMTree.Internal.Index.Compact
Test.Database.LSMTree.Internal.Index.Ordinary
Test.Database.LSMTree.Internal.Lookup
Test.Database.LSMTree.Internal.Merge
Test.Database.LSMTree.Internal.MergingRun
Test.Database.LSMTree.Internal.MergingTree
Test.Database.LSMTree.Internal.PageAcc
Test.Database.LSMTree.Internal.PageAcc1
Test.Database.LSMTree.Internal.RawBytes
Test.Database.LSMTree.Internal.RawOverflowPage
Test.Database.LSMTree.Internal.RawPage
Test.Database.LSMTree.Internal.Readers
Test.Database.LSMTree.Internal.Run
Test.Database.LSMTree.Internal.RunAcc
Test.Database.LSMTree.Internal.RunBloomFilterAlloc
Test.Database.LSMTree.Internal.RunBuilder
Test.Database.LSMTree.Internal.RunReader
Test.Database.LSMTree.Internal.Serialise
Test.Database.LSMTree.Internal.Serialise.Class
Test.Database.LSMTree.Internal.Snapshot.Codec
Test.Database.LSMTree.Internal.Snapshot.Codec.Golden
Test.Database.LSMTree.Internal.Snapshot.FS
Test.Database.LSMTree.Internal.Unsliced
Test.Database.LSMTree.Internal.Vector
Test.Database.LSMTree.Internal.Vector.Growing
Test.Database.LSMTree.Internal.WriteBufferBlobs.FS
Test.Database.LSMTree.Internal.WriteBufferReader.FS
Test.Database.LSMTree.Model.Table
Test.Database.LSMTree.Resolve
Test.Database.LSMTree.StateMachine
Test.Database.LSMTree.StateMachine.DL
Test.Database.LSMTree.StateMachine.Op
Test.Database.LSMTree.Tracer.Golden
Test.Database.LSMTree.UnitTests
Test.FS
Test.Util.Arbitrary
Test.Util.FS
Test.Util.FS.Error
Test.Util.Orphans
Test.Util.PrettyProxy
Test.Util.QC
Test.Util.QLS
Test.Util.RawPage
Test.Util.TypeFamilyWrappers
autogen-modules: Paths_lsm_tree
build-depends:
, ansi-terminal
, barbies
, base <5
, bitvec
, blockio
, blockio:sim
, bloomfilter-blocked
, bytestring
, cborg
, constraints
, containers
, contra-tracer
, crc32c
, cryptohash-sha256
, deepseq
, directory
, filepath
, fs-api
, fs-sim
, io-classes
, io-classes:strict-mvar
, io-classes:strict-stm
, io-sim <1.10
, lsm-tree
, lsm-tree:control
, lsm-tree:core
, lsm-tree:extras
, lsm-tree:prototypes
, mtl
, nothunks
, primitive
, QuickCheck
, quickcheck-classes
, quickcheck-dynamic
, quickcheck-instances
, quickcheck-lockstep >=0.8
, random
, safe-wild-cards
, semialign
, split
, tasty <1.5.3.0
, tasty-golden
, tasty-hunit
, tasty-quickcheck
, temporary
, text
, these
, transformers
, vector
, vector-algorithms
, wide-word
ghc-options: -threaded
benchmark lsm-tree-micro-bench
import: language, warnings, wno-x-partial
type: exitcode-stdio-1.0
hs-source-dirs: bench/micro
main-is: Main.hs
other-modules:
Bench.Database.LSMTree
Bench.Database.LSMTree.Internal.BloomFilter
Bench.Database.LSMTree.Internal.Index
Bench.Database.LSMTree.Internal.Index.Compact
Bench.Database.LSMTree.Internal.Lookup
Bench.Database.LSMTree.Internal.Merge
Bench.Database.LSMTree.Internal.RawPage
Bench.Database.LSMTree.Internal.Serialise
Bench.Database.LSMTree.Internal.WriteBuffer
build-depends:
, base <5
, blockio
, bloomfilter-blocked
, bytestring
, containers
, contra-tracer
, criterion
, deepseq
, directory
, fs-api
, lsm-tree
, lsm-tree:control
, lsm-tree:core
, lsm-tree:extras
, QuickCheck
, random
, temporary
, vector
ghc-options: -rtsopts -with-rtsopts=-T -threaded
benchmark lsm-tree-bench-bloomfilter
import: language, warnings, wno-x-partial
type: exitcode-stdio-1.0
hs-source-dirs: bench/macro
main-is: lsm-tree-bench-bloomfilter.hs
build-depends:
, base <5
, bloomfilter-blocked
, lsm-tree:core
, lsm-tree:extras
, random
, time
, vector
, wide-word
ghc-options: -rtsopts -with-rtsopts=-T -threaded
benchmark lsm-tree-bench-lookups
import: language, warnings, wno-x-partial
type: exitcode-stdio-1.0
hs-source-dirs: bench/macro
main-is: lsm-tree-bench-lookups.hs
build-depends:
, base <5
, blockio
, bloomfilter-blocked
, deepseq
, fs-api
, io-classes
, lsm-tree:control
, lsm-tree:core
, lsm-tree:extras
, primitive
, random
, time
, vector
, vector-algorithms
ghc-options: -rtsopts -with-rtsopts=-T -threaded
library mcg
import: language, warnings, wno-x-partial
visibility: private
hs-source-dirs: src-mcg
exposed-modules: MCG
build-depends:
, base <5
, primes
benchmark unions-bench
import: language, warnings, wno-x-partial
type: exitcode-stdio-1.0
hs-source-dirs: bench-unions
main-is: Main.hs
other-modules: Bench.Unions
build-depends:
, async
, base
, bytestring
, clock
, containers
, directory
, lsm-tree
, lsm-tree:extras
, mtl
, optparse-applicative
, primitive
, random
, vector
ghc-options: -rtsopts -with-rtsopts=-T -threaded
flag measure-batch-latency
description:
Measure the latency for individual batches of updates and lookups
default: False
manual: True
common measure-batch-latency
if flag(measure-batch-latency)
cpp-options: -DMEASURE_BATCH_LATENCY
benchmark utxo-bench
import: language, warnings, wno-x-partial, measure-batch-latency
type: exitcode-stdio-1.0
hs-source-dirs: bench/macro
main-is: utxo-bench.hs
build-depends:
, async
, base <5
, blockio
, bytestring
, clock
, containers
, contra-tracer
, deepseq
, fs-api
, lsm-tree
, lsm-tree:extras
, lsm-tree:mcg
, optparse-applicative
, pretty-show
, primitive
, random
, transformers
, vector
ghc-options: -rtsopts -with-rtsopts=-T -threaded
flag rocksdb
description: Build components that rely on RocksDB (only on Linux)
default: True
manual: False
benchmark utxo-rocksdb-bench
import: language, warnings, wno-x-partial
type: exitcode-stdio-1.0
hs-source-dirs: bench/macro
main-is: utxo-rocksdb-bench.hs
if !(os(linux) && flag(rocksdb))
buildable: False
build-depends:
, base <5
, binary
, bytestring
, clock
, containers
, cryptohash-sha256
, deepseq
, directory
, lsm-tree:mcg
, lsm-tree:rocksdb
, optparse-applicative
, split
ghc-options: -rtsopts -with-rtsopts=-T -threaded
library rocksdb
import: language, warnings
visibility: private
hs-source-dirs: src-rocksdb
exposed-modules: RocksDB
other-modules: RocksDB.FFI
if !(os(linux) && flag(rocksdb))
buildable: False
-- Ubuntu 22.04 doesn't have pkgconfig files for rocksdb
extra-libraries: rocksdb
build-depends:
, base <5
, bytestring
, indexed-traversable
library kmerge
import: language, warnings, wno-x-partial
visibility: private
hs-source-dirs: src-kmerge
exposed-modules:
KMerge.Heap
KMerge.LoserTree
build-depends:
, base <5
, indexed-traversable ^>=0.1
, primitive ^>=0.9
test-suite kmerge-test
import: language, warnings, wno-x-partial
type: exitcode-stdio-1.0
hs-source-dirs: test
main-is: kmerge-test.hs
build-depends:
, base >=4.16 && <4.23
, deepseq
, heaps
, lsm-tree:kmerge
, primitive
, splitmix
, tasty
, tasty-bench
, tasty-hunit
, tasty-quickcheck
, vector
benchmark kmerge-bench
import: language, warnings, wno-x-partial
type: exitcode-stdio-1.0
hs-source-dirs: test
main-is: kmerge-test.hs
cpp-options: -DKMERGE_BENCHMARKS
build-depends:
, base >=4.16 && <4.23
, deepseq
, heaps
, lsm-tree:kmerge
, primitive
, splitmix
, tasty
, tasty-bench
, tasty-hunit
, tasty-quickcheck
, vector
test-suite map-range-test
import: language, warnings, wno-x-partial
type: exitcode-stdio-1.0
hs-source-dirs: test
main-is: map-range-test.hs
build-depends:
, base >=4.16 && <4.23
, bytestring
, containers
, lsm-tree:core
, QuickCheck
, tasty
, tasty-hunit
, tasty-quickcheck
library prototypes
import: language, warnings, wno-x-partial
visibility: private
hs-source-dirs: src-prototypes
exposed-modules:
FormatPage
ScheduledMerges
build-depends:
, base <5
, binary
, bytestring
, containers
, contra-tracer
, primitive
, QuickCheck
, transformers
test-suite prototypes-test
import: language, warnings, wno-x-partial
type: exitcode-stdio-1.0
hs-source-dirs: test-prototypes
main-is: Main.hs
other-modules:
Test.FormatPage
Test.ScheduledMerges
Test.ScheduledMerges.RunSizes
Test.ScheduledMergesDL
Test.ScheduledMergesQLS
build-depends:
, base <5
, bytestring
, constraints
, containers
, contra-tracer
, lsm-tree:prototypes
, mtl
, primitive
, QuickCheck
, quickcheck-dynamic
, quickcheck-lockstep >=0.8
, tasty
, tasty-hunit
, tasty-quickcheck
library control
import: language, warnings
visibility: private
hs-source-dirs: src-control
exposed-modules:
Control.ActionRegistry
Control.Concurrent.Class.MonadSTM.RWVar
Control.RefCount
build-depends:
, base >=4.16 && <4.23
, deepseq ^>=1.4 || ^>=1.5
, io-classes ^>=1.6 || ^>=1.7 || ^>=1.8.0.1 || ^>=1.9 || ^>=1.10
, io-classes:strict-stm
, primitive ^>=0.9
test-suite control-test
import: language, warnings
type: exitcode-stdio-1.0
hs-source-dirs: test-control
main-is: Main.hs
other-modules:
Test.Control.ActionRegistry
Test.Control.Concurrent.Class.MonadSTM.RWVar
Test.Control.RefCount
build-depends:
, base <5
, io-classes
, io-sim
, lsm-tree:control
, primitive
, QuickCheck
, tasty
, tasty-quickcheck
-- It's not really a test suite, but if we make it an executable then its
-- dependencies will be included for dependency resolution when building the
-- main library. As a test-suite, it's more accurately represented as an
-- internal component.
test-suite demo
import: language, warnings
type: exitcode-stdio-1.0
hs-source-dirs: app
main-is: Main.hs
other-modules: Database.LSMTree.Demo
build-depends:
, base <5
, blockio
, blockio:sim
, contra-tracer
, directory
, fs-api
, fs-sim
, io-classes
, io-sim
, lsm-tree
, primitive
, vector
ghc-options: -threaded