storage: MVCC range deletion tombstones

[erikgrinaker]

We currently expose two main MVCC methods for deleting key spans, i.e. [key0, key1):

• MVCCDeleteRange: iterates over visible keys and writes an MVCC tombstone for each one, in O(n).
• Writer.ClearMVCCRangeAndIntents: removes all MVCC keys and versions via Pebble.DeleteRange, without any MVCC record, in <O(n).

However, for reasons outlined in #69380, we need a MVCC-compliant mechanism to delete a key span in < O(n). By this, we mean a mechanism that leaves an MVCC record of the range deletion and allows readers to read before it using an appropriate timestamp. To satisfy this, we will implement MVCC range tombstones, written either in MVCCDeleteRange() or as a separate method.

• Primitives (data structures, mutation, iteration)
• MVCC stats (both for garbage below and the tombstones themselves, with full-range fast path)
• Conflict handling (WriteTooOld, collisions, uncertainty, etc)
• Scans and gets (point tombstone synthesis, GC threshold)
• MVCC iterator validity/error checking
• Benchmarks

For more details, see the (currently internal) design document and tech note.

Epic CRDB-2624

Jira issue: CRDB-10062

[erikgrinaker]

May be implemented in Pebble as generalized range key support: cockroachdb/pebble#1339

[erikgrinaker]

I've been protoyping MVCC range tombstones based on Pebble range keys. I'm converging on the following approach, would appreciate a quick look by @sumeerbhola and @jbowens.

Data structure

Pebble range keys will use regular user keys as the start and end keys, and MVCC timestamps as suffix. This allows easy integration with point keys. To allow multiple range key kinds, the value will be a Protobuf union type, currently only with a range tombstone kind:

message MVCCRangeValue {
  option (gogoproto.onlyone) = true;

  MVCCRangeTombstone tombstone = 1;
}

message MVCCRangeTombstone {
  // NB: can't be roachpb.Key due to import cycle.
  bytes start_key = 1;
  bytes end_key   = 2;
}

The tombstone value includes the start and end keys to disambiguate individual range tombstones from constituent Pebble range key fragments. This also allows individual range tombstones to be identified across ranges, although we may want to clamp the returned bounds to the request bounds where appropriate. It also serves as a performance optimization, to avoid the need to decode every fragment for comparison during forwards and backwards iteration. However, these values will be duplicated for each range key fragment, so there will be some storage overhead.

One disadvantage of the key/suffix scheme is that range values of different kinds (e.g. range tombstones and range intents) cannot be iterated over separately. Since the amount of range tombstones is expected to be small, this will likely not present a problem. However, this will prevent differentiated range key masking by value kind, although this is not expected to be a problem for the currently anticipated range types (tombstones and intents).

In the MVCC API, range tombstones will be represented by a new MVCCRangeKey type:

type MVCCRangeKey struct {
	StartKey  roachpb.Key
	EndKey    roachpb.Key
	Timestamp hlc.Timestamp
}

MVCCDeleteRangeUsingTombstone

Range tombstones are written via storage.MVCCDeleteRangeUsingTombstone:

func MVCCDeleteRangeUsingTombstone(
	ctx context.Context,
	rw ReadWriter,
	ms *enginepb.MVCCStats,
	key, endKey roachpb.Key,
	timestamp hlc.Timestamp,
	maxIntents int64,
) error

This will scan for any separated intents in the span, returning a WriteIntentError, and then write the Pebble range key. It is not transactional, and thus cannot be atomic across ranges. Integration with MVCC statistics is currently unspecified.

It relies on the following lower-level Engine method:

type Engine interface {
	DeleteMVCCRange(MVCCRangeKey) error
}

MVCCIterator

Most MVCC read logic is built on top of MVCCIterator. To retain compatibility with current callers, this will expose range tombstones as synthesized point tombstones above/below existing point keys. This will not require any API changes, and will allow e.g. MVCCScan and MVCCGet to automatically handle range tombstones.

This will be implemented by a new storage.pebblePointSynthesizingIterator, which sits between storage.pebbleIterator and pebble.Iterator. Currently it will only synthesize point tombstones, but it could be extended to support e.g. ranged intents and other range key types. It will iterate across point keys, decode any range keys above/below them, and emit synthesized point keys in the appropriate order.

As a performance optimization, callers can request masking of point keys below range keys via IterOptions.RangeTombstoneMaskingAt. This gives a timestamp (typically the caller's read timestamp) below which any range keys will mask point keys and prevent them from being emitted. This cannot be used when the MVCC caller has requested tombstones to be emitted, since we must synthesize point tombstones for the point keys that would be masked.

Callers who need special handling of range tombstones (e.g. exports or rangefeeds) can disable tombstone synthesis by setting IterOptions.DisableRangeTombstoneSynthesis and access range tombstones via MVCCRangeTombstoneIterator (see below).

MVCCRangeTombstoneIterator

MVCCRangeTombstoneIterator iterates over MVCC range tombstones and emits them as MVCCRangeKey. A minimal interface would be e.g.:

type MVCCRangeTombstoneIterator interface {
	Close()
	Next()
	SeekGE(MVCCKey)
	UnsafeKey() MVCCRangeKey
	Valid() (bool, error)
}

This is exposed via a new method on Engine, which can either take the existing IterOptions or, more likely, a new option struct:

type Engine interface {
  NewMVCCRangeTombstoneIterator(opts IterOptions) MVCCRangeTombstoneIterator
}

[aliher1911]

In the MVCC API, range tombstones will be represented by a new MVCCRangeKey type:

Should this be the case for any MVCCRangeValue, not only for the one containing MVCCRangeTombstone?

[erikgrinaker]

In the MVCC API, range tombstones will be represented by a new MVCCRangeKey type:

Should this be the case for any MVCCRangeValue, not only for the one containing MVCCRangeTombstone?

Probably not. Range tombstones can, because the key/timespan fully describes the tombstone, but this won't be the case for e.g. ranged intents that will have lots of metadata.

[erikgrinaker]

expose range tombstones as synthesized point tombstones above/below existing point keys. This will not require any API changes, and will allow e.g. MVCCScan and MVCCGet to automatically handle range tombstones.

One caveat is uncertainty restarts and other conflict handling, which must explicitly check for range tombstones at a non-existing point key. But these exceptions can likely be layered on top of the point tombstone synthesis, or achieved via synthesis settings.

[sumeerbhola]

One disadvantage of the key/suffix scheme is that range values of different kinds (e.g. range tombstones and range intents) cannot be iterated over separately.

Range keys provide two benefits:

• simple handling of CockroachDB range splits/merges/rebalancing.
• in some cases, the benefit of native interleaving support from Pebble.

Both benefits apply to range tombstones since they are physically part of the same key space as point values. Intents, on the other hand, are already in a separate part of the key space for points, and it probably makes sense to continue that for future range intents. In which case interleaving (when needed) will need to be explicit in CockroachDB (like we do now with intentInterleavingIter). So I don't think this is an actual weakness.

This will be implemented by a new storage.pebblePointSynthesizingIterator, which sits between storage.pebbleIterator and pebble.Iterator.

storage.pebbleIterator implements MVCCIterator and EngineIterator. The latter is often used for lock table iteration for which one doesn't need synthesizing of points for range keys. Is the idea here to define a common interface that both pebble.Iterator and storage.pebblePointSynthesizingIterator implement?

This cannot be used when the MVCC caller has requested tombstones to be emitted, since we must synthesize point tombstones for the point keys that would be masked.

I'm thinking about the case where the caller wants masking, and sees a set of points P (post-masking).

• It still wants synthesized point tombstones that are more recent than P to do the uncertainty check.
• If it was scanning a range R, I don't think it cares about the fact that there are range tombstones within the uncertainty interval in R-P, since either way there is no value there. If this is correct, I think we don't need to worry about "One caveat is uncertainty restarts and other conflict handling, which must explicitly check for range tombstones at a non-existing point key."

[erikgrinaker]

Both benefits apply to range tombstones since they are physically part of the same key space as point values. Intents, on the other hand, are already in a separate part of the key space for points, and it probably makes sense to continue that for future range intents. In which case interleaving (when needed) will need to be explicit in CockroachDB (like we do now with intentInterleavingIter). So I don't think this is an actual weakness.

Indeed, as I mentioned later in that paragraph I don't see this being a problem for the anticipated range key types. But I though it would be worth calling it out anyway, if we should ever come up with some other range key type across the normal user key space.

storage.pebbleIterator implements MVCCIterator and EngineIterator. The latter is often used for lock table iteration for which one doesn't need synthesizing of points for range keys. Is the idea here to define a common interface that both pebble.Iterator and storage.pebblePointSynthesizingIterator implement?

Right, didn't consider EngineIterator. I was hoping to avoid another interface here. It's possible for callers to disable range tombstone synthesis, and in that case we'll set up the pebble.Iterator with IterKeyTypePointsOnly instead of IterKeyTypePointsAndRanges. That should make the synthesis and range key logic basically a noop. Perhaps that will be sufficient?

Either way, I think the main point here is the concept of synthesizing point tombstones below MVCCIterator for easy integration and compatibility with existing callers. I'll look into the specifics of how to implement that, which will also depend on benchmarks.

• If it was scanning a range R, I don't think it cares about the fact that there are range tombstones within the uncertainty interval in R-P, since either way there is no value there. If this is correct, I think we don't need to worry about "One caveat is uncertainty restarts and other conflict handling, which must explicitly check for range tombstones at a non-existing point key."

For non-tombstone reads, you're right. But if the caller has requested reads with tombstones, we need to determine whether the range tombstone across the empty span is visible or not. And for writes, we need to conflict with point writes at the same timestamp at least -- we may also need logic to order the range tombstone write and point write with respect to each other, but it's possible that locking and the timestamp cache takes care of this already (I'll have to give it some thought). In any case, I think it should be sufficient to layer this on top in the few cases that it's needed.

[sumeerbhola]

For non-tombstone reads, you're right. But if the caller has requested reads with tombstones, we need to determine whether the range tombstone across the empty span is visible or not. And for writes ...

It may be worthwhile enumerating the various cases in a doc so we can poke at it and revise. For instance

• I see that we may need something to be visible for writes, but I am not exactly clear how that should be made visible -- the write is writing specific points so if we knew those keys we could also synthesize point keys.
• For reads, I don't know the full list of cases where scan or get options is setting Tombstones=true. Rangefeeds and txn refreshes do, but they shouldn't care about uncertainty.

[erikgrinaker]

It may be worthwhile enumerating the various cases in a doc so we can poke at it and revise.

Yeah, I think that's a good idea. I'll write up either an RFC or a tech note to nail down the final MVCC range tombstone implementation and document it. I'm going to put a pin in these scan details for now and revisit.

the write is writing specific points so if we knew those keys we could also synthesize point keys

I was thinking the same thing. This would also handle an MVCCGet of a missing key.

I don't know the full list of cases where scan or get options is setting Tombstones=true

Doesn't seem to be that many. It's mostly rangefeeds and txn refreshes, as you point out, as well as testing. Exports and GC scans also care about range tombstones, but these have specialized APIs and will read the range tombstones separately.

The tombstone value includes the start and end keys to disambiguate individual range tombstones from constituent Pebble range key fragments. This also allows individual range tombstones to be identified across ranges, although we may want to clamp the returned bounds to the request bounds where appropriate. It also serves as a performance optimization, to avoid the need to decode every fragment for comparison during forwards and backwards iteration.

This would've been somewhat helpful for scans, but as we've touched on previously, I don't think we can/should think of a range tombstones as a single logical entity with fixed start/end bounds. The main reason is that mutations are non-atomic. For example, a range delete across multiple ranges may succeed on some ranges but fail on others. Similarly, range GC happens for different ranges at different times, so a tombstone spanning ranges would have "holes" in it. And splits/merges would require tombstone rewrites.

This is somewhat retreading old ground, but I'm reaching the same conclusion again: let's drop stored start/end bounds, but defragment during iteration for convenience.

[erikgrinaker]

MVCC range tombstones are now functional, except for garbage collection which is tracked separately in #70414. For details, see tech note in #83762.

There is a large amount of optimization and test work remaining, but this is tracked separately. See CRDB-2624 for details (internal).