An incremental merge of multiple runs.

The credits and debt concept we use here comes from amortised analysis of data structures (see the Bankers Method from Okasaki). Though here we use it not as an analysis method but within the code itself for tracking the state of the scheduled (i.e. incremental) merge.

There are two notions of credits (and corresponding debt) in this LSM implementation: nominal credits and merge credits. The merging run deals exclusively with merge credits. See IncomingRun for nominal credits.

A single merge credit corresponds with a merge step performed. Merge steps are measured by the number of entries in the input runs that are consumed. We measure the merge in terms of inputs, not outputs, because the number of inputs is known beforehand, whereas the number of outputs is not. The total merge debt is therefore defined to be the sum of the number of entries across the input runs to the merge. Once the merge credits spent equals the merge debt then the merge is (or rather must be) complete.

In both the prototype and implementation we accumulate unspent credits until they reach a threshold at which point we do a batch of merging work. We track both credits spent and credits as yet unspent.

In the prototype, the credits spent equals the merge steps performed. The same holds in the real implementation, but making it so is more complicated. When we spend credits on merging work, the number of steps we perform is not guaranteed to be the same as the credits supplied. For example we may ask to do 100 credits of merging work, but the merge code (for perfectly sensible efficiency reasons) will decide to do 102 units of merging work. The rule is that we may do (slightly) more work than the credits supplied but not less. To account for this we spend more credits, corresponding to the excess merging work performed. We spend them by borrowing them from the unspent credits, which may leave the unspent credits with a negative balance.

Furthermore, the real implementation has to cope with concurrency: multiple threads sharing the same MergingRun and calling supplyCredits concurrently. The credit accounting thus needs to define the state of the credits while merging work is in progress by some thread. The approach we take is to define spent credit to include credits that are in the process of being spent, leaving unspent credit as credits that are available for a thread to spend on merging work.

Thus we track three things:

• spent credits (SpentCredits): credits supplied that have been or are in the process of being spent on performing merging steps;
• unspent credits (UnspentCredits): credits supplied that are not yet spent and are thus available to spend; and
• merge debt (MergeDebt): the sum of the sizes of the input runs, and thus the total merge credits that have to be spent for the merge to be complete.

And define a derived measure:

• supplied credits: the sum of the spent and unspent credits. This is therefore also the sum of all the credits that have been (successfully) supplied to a merging run via supplyCredits.

The supplied credits increases monotonically, even in the presence of (a)synchronous exceptions.

We guarantee that the supplied credits never exceeds the total debt.

When the supplied credits equals the merge debt then we may not have actually completed the merge (since that requires spending the credits) but we have the potential to complete the merge whenever needed without supplying any more credits.

The credits spent and the steps performed (or in the process of being performed) will typically be equal. They are not guaranteed to be equal in the presence of exceptions (synchronous or asynchronous). In this case we offer a weaker guarantee: : a merge may progress more steps than the number of credits that were spent. If an exception happens at some point during merging work, we will "unspend" all the credits we intended to spend, but we will not revert all merging steps that we already successfully performed before the exception. Thus we may do more merging steps than the credits we accounted as spent. This makes the implementation simple, and merges will still finish in time. It would be bad if we did not put back credits, because then a merge might not finish in time, which will mess up the shape of the levels tree.

Merging runs can be shared across tables, which means that multiple threads can contribute to the same merge concurrently. The design to contribute credits to the same merging run is largely lock-free. It ensures consistency of the unspent credits and the merge state, while allowing threads to progress without waiting on other threads.

The entry point for merging is supplyCredits. This may be called by concurrent threads that share the same merging run. No locks are held initially.

The credits to supply can be specified as either an absolute or relative value. That is, we can ask that the number of supplied credits be set to a value N, or we can specify an additional N credits. increasing so in the absolute case, there is no change if the requested new supplied credit value is less than the current value. Supplying credits from the levels (via incoming runs) uses absolute credits, while supplying credits from merging trees using relative credits.

The main lock we will discuss is the mergeState StrictMVar, and we will refer to it as the merge lock.

We get the easy things out of the way first: the mergeKnownCompleted variable is purely an optimisation. It starts out as MergeMaybeCompleted and is only ever modified once to MergeKnownCompleted. It is modified with the merge lock held, but read without the lock. It does not matter if a thread reads a stale value of MergeMaybeCompleted. We can analyse the remainder of the algorithm as if we were always in the MergeMaybeCompleted state.

Variable access and locks:

• CreditsVar contains the pair of the current SpentCredits and UnspentCredits. Is only operated upon using transactions (atomic CAS), and most of these transactions are done without the merge lock held. The two constituent components can increase and decrease, but the total supplied credits (sum of spent and unspent) can only increase.
• MergeState contains the state of the merge itself. It is protected by the merge lock.

First, we do a moderately complex transaction atomicDepositAndSpendCredits, which does the following:

• Deposit credits to the unspent pot, while guaranteeing that the total supplied credits does not exceed the total debt for the merging run.
• Compute any leftover credits (that would have exceeded the total debt).
• Compute the credits to spend on performing merge steps, depending on which of three cases we are in:

1. we have supplied enough credits to complete the merge;
2. not case 1, but enough unspent credits have accumulated to do a batch of merge work;
3. not case 1 or 2, not enough credits to do any merge work.

• Update the spent and unspent pots
• Return the credits to spend now and any leftover credits.

If there are now credits to spend, then we attempt to perform that number of merging steps. While doing the merging work, the (more expensive) merge lock is taken to ensure that the merging work itself is performed only sequentially.

Note that it is not guaranteed that the merge gets completed, even if the credits supplied has reached the total debt. It may be interrupted during the merge (by an async exception). This does not matter because the merge will be completed in expectCompleted. Completing early is an optimisation.

If an exception occurs during the merge then the credits that were in the process of being spent are transferred back from the spent to the unspent pot using atomicSpendCredits (with a negative amount). It is this case that implies that the spent credits may not increase monotonically, even though the supplied credits do increase monotonically.

Once performing merge steps is done, if it turns out that excess merge steps were performed then we must do a further accounting transaction: atomicSpendCredits to spend the excess credits. This is done without respect to the balance of the unspent credits, which may result in the unspent credit balance becoming negative. This is ok, and will result in more credits having to be supplied next time before reaching the credit batch threshold. The unspent credits can not be negative by the time the merge is complete because the performing of merge steps cannot do excess steps when it reaches the end of the merge.