lsm-tree-0.1.0.0: Log-structured merge-trees
Safe HaskellSafe-Inferred
LanguageGHC2021

Database.LSMTree.Internal.Config

Synopsis

Documentation

Table configuration

data TableConfig Source #

Table configuration parameters, including LSM tree tuning parameters.

Some config options are fixed (for now):

  • Merge policy: Tiering
  • Size ratio: 4

Constructors

TableConfig 

Fields

defaultTableConfig :: TableConfig Source #

A reasonable default TableConfig.

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

Table configuration override

data TableConfigOverride Source #

Override configuration options in TableConfig that can be changed dynamically.

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

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

Merge policy

data MergePolicy Source #

Constructors

MergePolicyLazyLevelling

Use tiering on intermediate levels, and levelling on the last level. This makes it easier for delete operations to disappear on the last level.

Size ratio

Write buffer allocation

data WriteBufferAlloc Source #

Allocation method for the write buffer.

Constructors

AllocNumEntries !NumEntries

Total number of key/value pairs that can be present in the write buffer before flushing the write buffer to disk.

NOTE: if the sizes of values vary greatly, this can lead to wonky runs on disk, and therefore unpredictable performance.

Bloom filter allocation

data BloomFilterAlloc Source #

Allocation method for bloom filters.

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

Constructors

AllocFixed

Allocate a fixed number of bits per physical entry in each bloom filter.

Fields

  • !Word64

    Bits per physical entry.

AllocRequestFPR

Allocate as many bits as required per physical entry to get the requested false-positive rate. Do this for each bloom filter.

Fields

Fence pointer index

data FencePointerIndexType Source #

Configure the type of fence pointer index.

Constructors

CompactIndex

Use a compact fence pointer index.

Compact indexes are designed to work with keys that are large (for example, 32 bytes long) cryptographic hashes.

When using a compact index, it is vital that the serialiseKey function satisfies the following law:

Minimal size
size (serialiseKey x) >= 8

Use serialiseKeyMinimalSize to test this law.

OrdinaryIndex

Use an ordinary fence pointer index

Ordinary indexes do not have any constraints on keys other than that their serialised forms may not be 64 KiB or more in size.

Disk cache policy

data DiskCachePolicy Source #

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

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

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

Constructors

DiskCacheAll

Use the OS page cache to cache any/all key/value data in the table.

Use this policy if the expected access pattern for the table has a good spatial or temporal locality.

DiskCacheLevelsAtOrBelow !Int

Use the OS page cache to cache data in all LSMT levels at or below a given level number. For example, use 1 to cache the first level. (The write buffer is considered to be level 0.)

Use this policy if the expected access pattern for the table has good temporal locality for recently inserted keys.

DiskCacheNone

Do not cache any key/value data in any level (except the write buffer).

Use this policy if expected access pattern for the table has poor spatial or temporal locality, such as uniform random access.

diskCachePolicyForLevel :: DiskCachePolicy -> RunLevelNo -> RunDataCaching Source #

Interpret the DiskCachePolicy for a level: should we cache data in runs at this level.

Merge schedule

data MergeSchedule Source #

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

Constructors

OneShot

Complete merges immediately when started.

The OneShot option will make the merging algorithm perform big batches of work in one go, so intermittent slow-downs can be expected. For use cases where unresponsiveness is unacceptable, e.g. in real-time systems, use Incremental instead.

Incremental

Schedule merges for incremental construction, and step the merge when updates are performed on a table.

The Incremental option spreads out merging work over time. More specifically, updates to a table can cause a small batch of merge work to be performed. The scheduling of these batches is designed such that merges are fully completed in time for when new merges are started on the same level.

defaultMergeSchedule :: MergeSchedule Source #

The default MergeSchedule.

>>> defaultMergeSchedule
Incremental