With scheduled merges, each update (e.g., insert) on a table contributes to the progression of ongoing merges in the levels structure. This ensures that merges are finished in time before a new merge has to be started. The points in the evolution of the levels structure where new merges are started are known: a flush of a full write buffer will create a new run on the first level, and after sufficient flushes (e.g., 4) we will start at least one new merge on the second level. This may cascade down to lower levels depending on how full the levels are. As such, we have a well-defined measure to determine when merges should be finished: it only depends on the maximum size of the write buffer!

The simplest solution to making sure merges are done in time is to step them to completion immediately when started. This does not, however, spread out work over time nicely. Instead, we schedule merge work based on how many updates are made on the table, taking care to ensure that the merge is finished just in time before the next flush comes around, and not too early.

The progression is tracked using nominal credits. Each individual update contributes a single credit to each level, since each level contains precisely one ongoing merge. Contributing a credit does not, however, translate directly to performing one unit of merging work:

• The amount of work to do for one credit is adjusted depending on the actual size of the merge we are doing. Last-level merges, for example, can have larger inputs, and therefore we have to do a little more work for each credit. Or input runs involved in a merge can be less than maximal size for the level, and so there may be less merging work to do. As such, we scale NominalCredits to MergeCredits, and then supply the MergeCredits to the MergingRun.
• Supplying MergeCredits to a MergingRun does not necessarily directly translate into performing merging work. Merge credits are accumulated until they go over a threshold, after which a batch of merge work will be performed. Configuring this threshold should allow a good balance between spreading out I/O and achieving good (concurrent) performance.

Merging runs can be shared across tables, which means that multiple threads can contribute to the same merge concurrently. Incoming runs however are not shared between tables. As such the tracking of NominalCredits does not need to use any concurrency precautions.