storage, kv: do best-effort GC of old versions during storage compactions

[sumeerbhola]

GC of old versions requires reading each of the versions and creating point deletes to the storage layer to individually delete them (we may start using range tombstones in #51230). Since this is costly, we do GC periodically, when the "score", which includes the fraction of the bytes in a replica that are dead, is high enough. The lack of incremental GC means that individual keys can accumulate a lot of garbage, which can affect read performance.
It would be better if most of the GC work happened as a side-effect of storage level compactions which take as input a subset of sstables in the LSM. Periodic GC would still be used to cleanup versions that did not get cleaned up incrementally in compactions.

In #42514, we attempted to prototype GC in compactions.

There are some challenges to achieving this in the higher-level context of CockroachDB:

• MVCCStats maintenance: MVCCStats include information about non-live bytes and GC in compactions will make these inaccurate. We could do one of the following:

  • completely overhaul the MVCCStats machinery
  • keep the periodic scan that computes new MVCCStats, and a compaction-GC-timestamp-threshold, and replicate both through Raft (suggested by @ajwerner). The timestamp threshold allows compactions to GC all non-live versions that have timestamp lower than the threshold. Since this is a non-incremental scheme we are still subject to too much garbage accumulation for individual keys, so this may be ok as a first step, but not necessarily as the final solution.

• We expect all replicas to have identical replicated state in the store: Replica consistency checking is important for discovering bugs, and sometimes mitigating the impact of bugs that may accidentally creep into production deployments. GC in compactions will make the replicas diverge. The previous compaction-GC-timestamp-threshold approach fixes this, in that the read for consistency checking can hide all non-live data below the timestamp threshold. Alternatively, consistency checking could hide all non-live versions altogether.

• Correctly identifying which values (SET) in the compaction have not been deleted (DEL) in sstables not involved in the compaction. See the discussion thread at [WIP] storage/engine: attempt to do best-effort GC in compactions (fa… #42514 (review) for details. There are two (not fleshed out) approaches:

  • make different MVCC versions be overlapping in the file key space. This ensures that if one sees, for example, a@30#100.SET, a@20#90.SET, a@10#80.SET in the compaction input, there isn't a a@20#95.DEL lurking in another sstable that is not part of this compaction. The cons of this approach are (a) the possibility of higher write amplification, and (b) very big sstables (if there are too many versions of a key -- though we should be able to GC most of them, even if there is an old protected timestamp, so this may not be an issue).
  • pass down a promise (structured as a range) that no such a key with timestamp <= 20 exists in a higher sstable (suggested by @nvanbenschoten). This idea needs more refinement, since propagation of the promise would require the key range of the promise to be included in the sstable key range (like range tombstones), which may itself cause unnecessarily wide compactions and higher write amplification. And if the file key range caused by the promise is considered in the read path, we may unnecessarily read an sstable where there is no relevant data, which would increase read amplification.

Jira issue: CRDB-2843

Epic CRDB-2566

[sumeerbhola]

Somewhat related is the issue of efficiently supporting row-level TTLs, discussed here #20239 (comment)
Compactions doing discard of data that is expired due to TTL is easier from a correctness perspective, since the state of the row (key-value pair) is sufficient to make that expiry decision -- it does not need knowledge of the state of other rows.

[sumeerbhola]

In the context of the design for cockroachdb/pebble#1339, @nvanbenschoten @erikgrinaker brought up:

We could use these range keys in CockroachDB to store information about GC actions over an MVCC key span, and then expose them in Pebble compaction filters, such that we could push much of the GC mechanics down to Pebble compactions.

My interpretation of this is:

• Use the support we are building for range keys to introduce an "MVCC-aware RANGEDEL". An MVCC-RANGEDEL [k1,k2)@v would be telling Pebble that all points and ranges with prefix overlapping [k1,k2) and version < v can be discarded, and must immediately be hidden from all iteration.
• Unlike regular range keys, where Pebble only provides masking iteration, and otherwise does not interpet the range key, this is a case where Pebble knows the semantics of the operation. Also, there would not be any Unset operation on MVCC-RANGEDEL, and it would be elided when falling down to L6.
• For range keys we have not decided yet whether to require the invariant that two overlapping key prefixes with @v1#s1 and @v2#s2 satisfy v1 < v2 => s1 <= s2. That is, versions would not violate the LSM invariant. For MVCC-RANGEDEL we would need to require this.
• Having this operation would not avoid the need to scan the range and recompute MVCC stats, so GC would continue to be periodic at a low frequency. However, it does allow for efficient deletion since regular RANGEDELs can only be used over a swathe of keys only if there aren't more recent versions.

[erikgrinaker]

My interpretation, without much familiarity with Pebble internals, was that instead of introducing an "MVCC-aware RANGEDEL" that Pebble has to know the semantics of, we instead expose a mechanism where users (CRDB) can hook into the compaction process via compaction filters and provide a custom GC policy.

We could then drop a user-defined range key across the span we want to GC (to Pebble this would just be an arbitrary range key), and the compaction filter would reference this range key during compactions to make versions below it eligible for compaction-time GC.

As for stats, I'd imagine that CRDB would update its MVCC stats when it drops this custom range key. From CRDB's point of view, the logical data is removed, and it's just pending compaction in Pebble. This is no different than other write amplification in Pebble, which will be reduced on compaction.

I may be misrepresenting @nvanbenschoten's idea here, but that was my understanding at least.

[nvb]

@erikgrinaker's comment is closer to what we had discussed. Pebble does not need to guarantee that GC-able versions are immediately hidden from all iteration after the ranged key has been written because those versions are not visible by higher levels anyway. By definition, for a KV version to be GC-able, it must be shadowed by another version that itself is below the GC threshold. And because we don't allow MVCC scans at timestamps below the GC threshold, the GC-able version will never be visible to an MVCC scan.

So the idea was to treat this ranged key as a form of metadata that is exposed to a user-defined compaction filter but otherwise ignored. It was essentially the same idea that you mentioned above:

pass down a promise (structured as a range) that no such a key with timestamp <= 20 exists in a higher sstable