perf: separate latest and old MVCC versions for faster reads

[sumeerbhola]

This issue is different from #847 since this one is specifically about how Pebble is used in CockroachDB to store MVCC data. When there are many MVCC versions for a key, reads slow down because (a) the block cache is less effective since most of each block is data that is not needed, (b) when doing scans one needs to seek from one versioned key to another to skip iterating over all the versions.

A prerequisite to doing something here is Pebble gaining some understanding of MVCC timestamps. That prerequisite is also the case for compaction-time GC cockroachdb/cockroach#57260. One can also argue that compaction-time GC may make separating the latest and old MVCC versions less important.

If we ignore provisional values, a rough approach would be to put “live” and “dead” versions of data into separate files. This should not be hard when the multiple versions are in the same sstable -- when generating that sstable instead of writing one sstable we would write a pair, the “live” and “dead” sstable. These will have overlapping keys and will participate in compactions as a pair. A read at the “current time” can ignore the "dead" sstable. But what is “current time” given that we don’t have TrueTime like spanner? One possibility is to track the newest timestamp in the “live” sstable -- if the txn timestamp is newer than this newest timestamp there is no possibility that it will need anything from the “dead” sstable. This should work for sstables in lower levels which have most of the data.
The above approach will need adjustment to handle provisional values and intents.

[sumeerbhola]

There is some historical discussion in cockroachdb/cockroach#17229 (comment) which explicitly changes the key for older versions. That approach has a more explicit performance tradeoff since one needs to rewrite the existing key-value pair, which makes it less tenable.

[jbowens]

@sumeerbhola — I had a shower thought regarding differentiating between provisional and finalized keys. It's complicated and hopefully could be simplified. Food for thought:

At the beginning of a compaction, Pebble needs to decide which keys are final and which might be provisional. It takes the smallest-largest key range of the compaction and queries a CockroachDB-provided callback ClosedTimestamp([start, end]) for the current closed timestamp ct for that key range. This value ct guarantees that every key within the range [start, end] with timestamp <ct, is either committed or shadowed by a tombstone somewhere in the LSM.

But those tombstones may be somewhere above the compaction, meaning the compaction may still contain provisional keys at timestamps <ct. To differentiate those keys, we introduce coordination from all batches that remove or revise provisional values.

history-rewrite ranges

When a batch is going to alter history by deleting or modifying provisional values, the caller flips a bit on the batch indicating so. The min and max MVCC timestamps written by the batch form the batch's 'history-rewrite range'. Every sstable and memtable has a 'history-rewrite range' that encodes a start and end MVCC timestamp. When the batch commits, its 'history-rewrite range' is merged with the memtable's, widening the range to encompass the existing range and the new batch's range.

When a memtable is flushed, the outputted sstables inherit the memtable's history-rewrite range. Some of the sstables may not contain any of the history-rewriting keys, but they still inherit the whole range. [Maybe this could be relaxed to be the intersection of the sstable's MVCC key range and the memtable's history-rewrite range?]

When sstables are merged in a compaction, the compaction decides an output's history-rewrite range by merging the history-rewrite ranges of the compaction inputs' that overlap with it. This isn't necessarily all the inputs to the compaction, just the inputs that might have contributed keys to the individual output file. The ranges are merged by widening the range to encompass all the inputted history-rewrite ranges. When a compaction outputs a table to L6, it elides the history-rewrite range property.

compaction closed ranges

Now, when a compaction starts it needs to decide which keys are final and which are provisional. It takes the input sstable boundaries of all its inputs and fragments them. For each fragment's bounds, it calls ClosedTimestamp([start, end]). It associates with the fragment the range [0,ClosedTimestamp], representing the assumption that all its input keys that fall within the fragment and have timestamps in the range [0,@ClosedTimestamp] are final:

    [   input sstable k   [a-c]     ]
               [              input sstable l   [b-d]              ]

        i0              i1                          i2
    [          |                     |                             ]
    |  [0,t6]  |      [0,t9]         |          [0,t9]             |
    a          b                     c                             d

Now, it ascends the LSM level-by-level looking at files and memtables that overlap the compaction's keyspace. It uses these overlapping files' ranges to reduce which timestamp ranges are considered closed. For every overlapping higher-levelled file or memtable, it subtracts out the file or memtable's history-range for overlapping input ranges. This yields a range, or sequence of ranges, in which keys are known to be finalized within each of these intervals of the compaction.

L0 table o [                                            ] (rewrite [t12,t10])
L1 table n [                ]                             (rewrite [t8,t10])
L2 table m                                  [ ]           (rewrite [t5,t5])

L3 compaction:
    [   input sstable k   [a-c]     ]
               [              input sstable l   [b-d]              ]

        i0              i1                          i2
    [          |                     |                             ]
    |  [0,t6]  |      [0,t7]         |        [0,t4],[t6,t9]       |
    a          b                     c                             d

The compaction can consider final any keys that fall within interval i0 and have timestamps within [0, t₆], and so on.

minimum closed timestamps

A long-running transaction in one part of the keyspace doesn't prevent keys from being considered closed in another part... until the long-running transaction gets aborted. When the history-rewriting batch is written to the memtable with the range [t_{long ago}, t_recent], it prevents any keys overlapping the memtable and within that wide time range from being considered closed, even if they were considered closed in earlier compactions.

In the above example, a history-rewriting batch in a disjoint part of the keyspace could commit a rewrite batch with a rewrite range of [t₁,t₉]. If i₀, i₁, or i₂ overlap the memtable, they're forced to only consider keys within [0,t₁) to be closed.

To avoid this, every sstable also has a 'minimum closed timestamp' property. This represents a floor on the file's closed timestamp. It guarantees any of the file's keys with timestamps less than the minimum closed timestamp are closed.

The value is derived from the compaction input intervals. When an sstable is outputted, its key range overlaps some set of the fragmented compaction input intervals. The minimum closed timestamp holds the minimum upper bound t such that [0, t] is contained within all the overlapping input intervals' closed timestamp ranges. In the above example, an output that spans i₀ and i₁ would have a minimum closed timestamp of min(t₆,t₈) = t₆.

When computing closed ranges for a compaction, each compaction input interval is assigned a minimum closed timestamp equal to the minimum of all the overlapping input sstables' minimum closed timestamps.

    [   input sstable k   [a-c]     ]                                mct t3
               [              input sstable l   [b-d]              ] mct t7

        i0              i1                          i2
    [          |                     |                             ]
    | mct = t3 |     mct = t3        |             mct = t7        |
    a          b                     c                             d

When traversing the LSM and subtracting out overlapping files' history-rewrite ranges, the interval's minimum closed timestamp prevents the removal of the range below the minimum closed timestamp.:

L0 table o [                                            ] (rewrite [t12,t10])
L1 table n [                ]                             (rewrite [t8,t10])
L2 table m                                  [ ]           (rewrite [t5,t5])

L3 compaction:
    [   input sstable k   [a-c]     ]                                mct t3
               [              input sstable l   [b-d]              ] mct t7

        i0              i1                          i2
    [          |                     |                             ]
    | mct = t3 |     mct = t3        |             mct = t7        |
    |  [0,t6]  |      [0,t7]         |              [0,t9]         |
    a          b                     c                             d

In the above example, interval i₂'s minimum closed timestamp of t₇ prevents the L2 table m's rewrite range of [t₅,t₅] from reducing the size of its closed timestamp range.

The minimum closed timestamp serves as a compact way of carrying forward knowledge of keys' finality from compaction to compaction.

[sumeerbhola]

Thanks for the writeup @jbowens

Another idea, that came up in the discussion in cockroachdb/cockroach#72121 (comment)

Consides sstables with separate sections for keys and values. The simplest way to do this is to write

'0' + k0 => 0
'0' + k1 => 1
...
'1' + 0 => v0
'1' + 1 => v1
...

which ensures that the normal sstable sorting takes care of the ordering. It does require buffering the values in-memory (as compressed ssblocks) since they can't be written out immediately. Alternatively, one could reverse the order and put values before keys, in case the buffering required for keys is less.

The downside of this scheme is that reading a particular ki=>vi requires loading 2 ssblocks. So instead of doing this for all keys, say we did this for only older versions of keys in the sstable. Something like:

'0' + k0@10 => v0
'0' + k0@9 => index 0
'0' + k0@8 => index 1
'0' + k1@50 => v1
'0' + k1@40 => index 2
...
'1' + 0 => <value>
'1' + 1 => <value>
'1' + 2 => <value>

All the keys are visible as usual and the values can be lazily loaded if there is indirection. If we get unlucky and k0@10 has been deleted at a higher level, say because the transaction was aborted, there is no correctness issue since we can load the value for k0@9. Assuming such aborts (or pushes causing rewrites) are rare, we will mostly not need to do this. Scans will typically want to step from k0@10 to k1@50, and won't need to pay the expense of reading the older values of k0. And even if the key lengths are not significantly smaller than value lengths, we will get prefix compression on the different versions of the same key.

[jbowens]

@sumeerbhola Nice, that's cool.

I'd briefly entertained storing values out of band when thinking about range keys because of the duplication incurred from fragmentation. I didn't entertain it for long since range keys are rare. It makes a lot of sense in this case.

And even if the key lengths are not significantly smaller than value lengths, we will get prefix compression on the different versions of the same key.

Now I'm wondering whether you could make use of the prefix compression to avoid the extra key comparisons too. Something like the caller calls NextPrefix(prefixLength int) passing len(mvccKey.Key) if they read a non-provisional key at Iterator.Key(), and the iterator at the top of the heap can skip over any keys read for which shared > prefixLength.

[sumeerbhola]

@jbowens nice idea for avoiding the key comparison -- it seems very doable.

Adding an offline comment by @nvanbenschoten on how queue-like workloads could benefit from this:

It’s interesting to consider what a unoptimized queue-like workload would look like in this scheme. Because the latest version for most keys would be a deletion tombstone, the “key” section would consist almost exclusively of keys -> tombstone and shadowed keys -> indirect_value_ptr. So we would never need to load the values of the deleted queue entries and the cost of a scan would be independent of the value size of the deleted queue entries. I don’t have a mental model for the cost of a scan of tombstones (one that collects no live versions), but I imagine that this would provide a sizable speedup, especially for a workload that generates large queue entries.

[sumeerbhola]

@jbowens pointed out that this organization may also help during GC of older versions.

We do two scans for GC

• Using gcIterator where we are looking at both the keys and values, in order to identify what can be GC'd. Reading the values from the value section will be slower in this case. However, it seems we don't typically need the value -- the only place we actually use the value is if it is an intent. We should be able to change the code to not load MVCC values.
• Performing the GC: MVCCGarbageCollect only needs the key and the size of the value (for updating MVCCStats). So the key section should store the value size when there is an indirection, so that we can avoid loading the value.

A different issue: not all keys with a non-empty suffix are true CockroachDB MVCC keys. Lock table keys are the exception, where the ordering on the suffix is random (contains the txn UUID). One easy way to accommodate this would be for the Pebble DB Options to allow specification of key span exclusion(s) for where this separation of versions is not applicable -- we would use it to exclude [LockTableSingleKeyStart, LockTableSingleKeyEnd).

[jbowens]

For the case where there's a lot of garbage like the naive queue implementation, could we use a block property collector, my favorite new Pebble feature?

We could write a block property collector that records the prefix cardinality of a block/index-block/sstable. If a block/index-block/sstable has cardinality 1, a NextPrefix call could skip the rest of the block/index-block/sstable at the top of the mergingIter heap.

[jbowens]

If we did compaction-time GC, does the encoding of a key still need to be stable once it's committed? I'm imagining modifying committed MVCC keys to set a bit indicating that they are committed.

This could be done through a new special range key that associates a key span (always of whole prefixes) with both a closed timestamp and a GC threshold timestamp. These range keys descend the LSM and respect the LSM invariant with respect to keys older than their closed timestamp. In a compaction with one of these range keys, a user-defined merger is invoked for every point key within the range key's span.

type Options struct {
    // ...
    RangeKeyMerger func() RangeKeyMerger
 }

type RangeKeyMerger interface {
    InitRangeKey(rangeValue) error
    MergePointKey(key, value []byte) (newKey, newValue []byte, drop bool)
}

• If the point key's timestamp is greater than the range key's closed timestamp, the point key is output unmodified.
• If the point key's timestamp is less than the range key's GC threshold timestamp and the merger has already seen another key with the same prefix, it returns (nil, nil, true /* drop */) to drop the value.
• If the point key's timestamp is less than the range key's closed timestamp, it returns the key with the closed bit (or unchanged if it's already set).

MVCCStats would be updated when these range keys are written. The range keys would be elided out of L6.

With this scheme:

• A 'mvcc garbage' block property collector can examine keys and determine when a block is all committed garbage. It can set the block's annotation to the highest timestamp of any of the keys. A read at a timestamp t can use a block property filterer that skips over any blocks with garbage timestamps < t.
• Garbage compaction happens at compaction-time, through these range keys.

One obstacle that immediately comes to mind is that the above scheme changes a key's encoding once it's merged with one of these range keys. That would be a problem with today's GC scheme, but performing compaction-time GC sidesteps that. I'm probably unaware of other problems with unstable mvcc keys.

[jbowens]

I've been thinking about this issue in the context of MVCCDeleteRange. A span that includes a MVCCDeleteRange will suffer a performance cliff, because an iterator seeking into the deleted span needs to construct a range-key iterator stack and perform extra key comparisons during interleaving.

If a MVCCDeleteRange falls into L6, we could output it and the point keys it covers into a garbage-only L7. Iterators reading at recent timestamps could skip the entire file. This particular case is easier than the general garbage case, since there are no provisional MVCCDeleteRanges.

[erikgrinaker]

there are no provisional MVCCDeleteRanges

It's possible that these will exist in the future (along with ranged intents), if SQL wants to start making use of them. But there are no short-term plans for this.

Also, Pebble can't know whether a range key is an MVCCDeleteRange or some other ranged key type, so CRDB will have to inform Pebble about these semantics. Although I suppose any kind of MVCC range key would imply that points below it are garbage.

We discussed something related over in cockroachdb/cockroach#57260 (comment), where CRDB can lay down a new kind of range key during GC that it can use in compaction filters to do MVCC GC during Pebble compactions.

[jbowens]

Also, Pebble can't know whether a range key is an MVCCDeleteRange or some other ranged key type, so CRDB will have to inform Pebble about these semantics.

Yeah, I think we should do this regardless when we introduce any other ranged key type, so that we can explicitly avoid applying range-key masking using non-MVCCDeleteRange range keys.

[sumeerbhola]

The remaining work is to produce a tech note describing the design.

[jbowens]

Something that didn't click for me until I was talking with @itsbilal just now: The setHasSameKeyPrefix can also be used in the progressive restore case when restoring from backup sstables with revision history. During those restores, we need to ignore all the keys in the backup sstable that are not the first key with the prefix. When transforming backup sstables' blocks for sstables created with TableFormatv3, we can just skip any keys with the bit set.

[sumeerbhola]

During those restores, we need to ignore all the keys in the backup sstable that are not the first key with the prefix.

Are we restoring to a point in time, so it could be an arbitrary version, and not necessarily the most recent one? The optimization does seem worthwhile.

[jbowens]

Yeah, I think it's possible to restore to a particular point-in-time that might be behind the most recent version of a key. I suppose at transform time, we could use the block properties (do we write these to backups today?) to determine whether the restore timestamp is higher than all the keys within the block.

I think it'll be relatively uncommon to need to restore to a non-most-recent version, because only the full backup will be restored "lazily" and require transformation.