Identifiers for LSM tables

Configuration options for individual LSM tables.

Similar to Data.Map.unionWith.

A call to union itself is not expensive, as the input tables are not immediately merged. Instead, it creates a representation of an in-progress merge that can be performed incrementally (somewhat similar to a thunk).

The more merge work remains, the more expensive are lookups on the table.

Credits for keeping track of merge progress. These credits correspond directly to merge steps performed.

We also call these "physical" credits (since they correspond to steps done), and as opposed to "nominal" credits in NominalCredit and NominalDebt.

Debt for keeping track of the total merge work to do.

Return the current union debt. This debt can be reduced until it is paid off using supplyUnionCredits.

Supply union credits to reduce union debt.

Supplying union credits leads to union merging work being performed in batches. This reduces the union debt returned by remainingUnionDebt. Union debt will be reduced by at least the number of supplied union credits. It is therefore advisable to query remainingUnionDebt every once in a while to see what the current debt is.

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

A "merging tree" is a mutable representation of an incremental tree-shaped nested merge. This allows to represent union merges of entire tables, each of which itself first need to be merged to become a single run.

Trees have to support arbitrarily deep nesting, since each input to union might already contain an in-progress merging tree (which then becomes shared between multiple tables).

See Note [Table Unions].

A merge that is waiting for its inputs to complete.

The inputs can themselves be MergingTrees (with its STRef) to allow sharing existing unions.

This is much like an IncomingRun, and are created from them, but contain only the essential information needed in a PendingLevelMerge.

A "merging run" is a mutable representation of an incremental merge. It is also a unit of sharing between duplicated tables.

The merge policy for a LSM level can be either tiering or levelling. In this design we use levelling for the last level, and tiering for all other levels. The first level always uses tiering however, even if it's also the last level. So MergePolicyForLevel and LevelMergeType are orthogonal, all combinations are possible.

Merges can exist in different parts of the LSM, each with different options for the exact merge operation performed.

Different types of merges created as part of the merging tree.

Union merges follow the semantics of Data.Map.unionWith (<>). Since the input runs are semantically treated like Data.Maps, deletes are ignored and inserts act like mupserts, so they need to be merged monoidally using resolveValue.

Trees can only exist on the union level, which is the last. Therefore, node merges can always drop deletes.

Different types of merges created as part of a regular (non-union) level.

A last level merge behaves differently from a mid-level merge: last level merges can actually remove delete entries, whereas mid-level merges must preserve them. This is orthogonal to the MergePolicyForLevel.

Nominal credit is the credit supplied to each level as we insert update entries, one credit per update entry inserted.

Nominal credit must be supplied up to the NominalDebt to ensure the merge is complete.

Nominal credits are a similar order of magnitude to physical credits (see Credit) but not the same, and we have to scale linearly to convert between them. Physical credits are the actual number of inputs to the merge, which may be somewhat more or somewhat less than the number of update entries we will insert before we need the merge to be complete.

The nominal debt for a merging run is the worst case (minimum) number of update entries we expect to insert before we expect the merge to be complete.

We require that an equal amount of nominal credit is supplied before we can expect a merge to be complete.

We scale linearly to convert nominal credits to physical credits, such that the nominal debt and physical debt are both considered "100%", and so that both debts are paid off at exactly the same time.

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

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

The current upper bound on the number of UnionCredits that have to be supplied before a union is completed.

The union debt is the number of merging steps that need to be performed /at most/ until the delayed work of performing a union is completed. This includes the cost of completing merges that were part of the union's input tables.

Compute the maximum size of a run for a given level.

The size of a tiering run at each level is allowed to be bufferSize*sizeRatio^(level-1) < size <= bufferSize*sizeRatio^level.

>>> levelNumberToMaxRunSize LevelTiering (LSMConfig 2 4) <$> [0, 1, 2, 3, 4]
[0,2,8,32,128]

The size of a levelling run at each level is allowed to be bufferSize*sizeRatio^level < size <= bufferSize*sizeRatio^(level+1). A levelling run can take take up a whole level, so the maximum size of a run is sizeRatio tmes larger than the maximum size of a tiering run on the same level.

>>> levelNumberToMaxRunSize LevelLevelling (LSMConfig 2 4) <$> [0, 1, 2, 3, 4]
[0,8,32,128,512]

Compute the appropriate level for the size of the given run.

See levelNumberToMaxRunSize for the bounds on (tiering or levelling) run sizes at each level.

>>> runSizeToLevelNumber LevelTiering (LSMConfig 2 4) <$> [0,2,8,32,128]
[0,1,2,3,4]

>>> runSizeToLevelNumber LevelLevelling (LSMConfig 2 4) <$> [0,8,32,128,512]
[0,1,2,3,4]

Check wheter a run of the given size fits in the given level.

See levelNumberToMaxRunSize for the bounds on (tiering or levelling) run sizes at each level.

>>> runSizeFitsInLevel LevelTiering (LSMConfig 2 4) 3 <$> [8,9,16,32,33]
[False,True,True,True,False]

>>> runSizeFitsInLevel LevelLevelling (LSMConfig 2 4) 2 <$> [8,9,16,32,33]
[False,True,True,True,False]

Check wheter a run of the given size is too small for the given level.

See levelNumberToMaxRunSize for the bounds on (tiering or levelling) run sizes at each level.

>>> runSizeTooSmallForLevel LevelTiering (LSMConfig 2 4) 3 <$> [8,9]
[True,False]

>>> runSizeTooSmallForLevel LevelLevelling (LSMConfig 2 4) 2 <$> [8,9]
[True,False]

Check wheter a run of the given size is too large for the given level.

See levelNumberToMaxRunSize for the bounds on (tiering or levelling) run sizes at each level.

>>> runSizeTooLargeForLevel LevelTiering (LSMConfig 2 4) 2 <$> [8,9]
[False,True]

>>> runSizeTooLargeForLevel LevelLevelling (LSMConfig 2 4) 1 <$> [8,9]
[False,True]