sstable: sstable-local key kinds for overwritten/deleted points

[sumeerbhola]

We have various related problems caused by Pebble snapshots:

• P1. RANGEDELs that delete points in the same sstable, but the points were not deleted during the compaction because of an open snapshot. This results in expensive iteration. db: efficient skipping of points deleted by RANGEDEL in the same file #2424 discusses a possible solution using a block property collector for the range of seqnums in a block. It involves using a dynamic block property filter, based on the RANGEDELs at the current point iterator position, to skip blocks. A concern there is the code complexity of this dynamic application (we have significant code complexity in the other case of dynamic application -- range key masking).

• P2. When iterating over foreign sstables, we need to do (a) point collapsing to expose at most one point per user key, (b) apply RANGEDELs. The current PR for this *: Implement iterators and seqnum substitution for foreign SSTs #2455 involves a pointCollapsingSSTIter that wraps the actual sst iterator. SST iteration is very performance sensitive code and adding extra wrappers is non ideal: there is no clear end to the life of a foreign sst and we'd rather not force a rewrite of that sstable -- one of the goals of disaggregated storage is to scale compute and disk bandwidth resources as a function of the hot (from a write perspective) data and not the whole data. Also, application of RANGEDELs in this case suffers from the same issue as in P1.

The ideal solution for P2 would allow user-facing reads to utilize the existing SST iterators (with slight modifications) and with no loss of efficiency. And for P1 and P2 we would like to skip whole blocks of overwritten/deleted points. And avoiding key comparisons would be very useful in general.

We observe that:

• Reads:
  • All user-facing reads in CockroachDB use iterators over the DB, hence have a higher read seqnum than all sstables
  • Even for the internal-facing reads that use snapshots, the snapshots are shortlived enough that most L5 and L6 sstables will have all seqnums lower than the snapshot seqnum.
• Writes:
  • we have already done the key comparisons between points that share the same user key and between points and RANGEDELs on the compaction path (in compactionIter). The idea below uses those comparisons, by encoding them in the written sst, so they can be cheaply utilized when reading.

We ignore MERGE in the following discussion since I don't believe it is worth optimizing:

• For P2, we should disallow it from foreign ssts.
• For regular ssts, we don't need to optimize for it. They can be handled by the upstream iterators in the iterator tree (specifically pebble.Iterator).

We are left with the following point key kinds: SET, DEL, SINGLEDEL, SETWITHDEL. For each of these we introduce a corresponding *_LOCALLY_DELETED kind e.g. SET_LOCALLY_DELETED.

Reads:
The *_LOCALLY_DELETED kinds are only visible to the sst iterators and the sst iterators will convert them to the corresponding externally visible kind e.g. SET_LOCALLY_DELETED to SET, before exposing them (if they need to be exposed). Since all valid kinds have a uint8 value <= 22, we can do the check for *_LOCALLY_DELETED kind and the conversion cheaply by reserving the most significant bit in the InternalKeyKind uint8 for the *_LOCALLY_DELETED kinds. An (internally installed) block property collector collects whether all points in a block are *_LOCALLY_DELETED. There are two kinds of iteration modes over such a sstable:

• A. Hide the *_LOCALLY_DELETED keys: this is used when the read seqnum is > all the seqnums in the sst. This is the common case. Forward and reverse iteration simply skips over the *_LOCALLY_DELETED keys. There are no user-key comparisons needed to do such skipping/collapsing. And skipping uses the block property filter to skip whole blocks whenever possible. This is straightforward compared to a dynamic block property filter and there is no need to do key span comparisons for RANGEDEL application. This hiding is correct because of the level invariant: the sequence of seqnums for a user key in a sstable represents a contiguous subsequence of the seqnums for the userkey across the whole LSM, and is more recent than the seqnums in a sstable in a lower level.

• B. map *_LOCALLY_DELETED to the externally visible kind: Used by compactions and certain pebble.Iterator reads.

In general A is best-effort, since not all ssts will satisfy the conditions for A. Hence the normal iterator tree continues to have the ability to apply DELs, RANGEDELs etc. (which it anyway needs to do for merging across levels). One case where A is not best effort is iteration over foreign sstables, which by definition happens at a seqnum > that of the foreign sst.

Writes:
The *_LOCALLY_DELETED types are generated during compactions. compactionIter knows which points are locally deleted either because they are overwritten by a newer point, or by a RANGEDEL, but are being preserved because of snapshots.
Some care is needed here.

Simple case for a userkey: One point output per snapshot stripe (that has points for that userkey). Currently, the output point has the seqnum of the highest point in that snapshot stripe and key kind of this highest seqnum and the corresponding value. We change this to:

• The point output from the most recent stripe retains it's key kind.
• The output points from older stripes transition to the kind *_LOCALLY_DELETED.
• If writing to L6 and the most recent stripe output point is a DEL it is changed to a DEL_LOCALLY_DELETED (there are no levels below for which this DEL is useful).

General case: This occurs due to SETWITHDEL, SINGLEDEL. Various transformations can currently happen, that all apply within a snapshot stripe:

• SET => SETWITHDEL based on the next older key after the SET being a DEL or SINGLEDEL
• SINGLEDEL => DEL based on the next older key after the SINGLEDEL being a DEL or a SETWITHDEL.
• SINGLEDEL vanishing: by consuming the next older key that is a SET. The key exposed for that snapshot stripe may then be an older key in that stripe, or nothing may be exposed from that stripe.

Now that since iteration A will ignore the older keys, we need to do these transformations eagerly for the youngest candidate key for the userkey, since we cannot do this at read time. If the next older key is in the same snapshot stripe as the youngest candidate key (NB: if SINGLEDEL as the youngest candidate key vanishes, it passes the mantle of the youngest candidate key to the next key, which may be in the next older stripe), the same logic in compactionIter suffices. The difficulty arises when the next older key to the youngest candidate key is in an older snapshot stripe. We change the logic to apply this transformation even in that case. This should be straightforward since we do step to the next key when the current candidate is a SET (compactionIter.setNext) or a SINGLEDEL (compactionIter.singleDeleteNext), before outputting the current candidate (both call nextInStripe). The resulting key kind is what is output for the youngest key. In the case where this means the SINGLEDEL would vanish, we output SINGLEDEL_LOCALLY_DELETED.

[jbowens]

I like that this idea localizes complexity to the scope of an sstable. Instead of storing the obsolete bit in the key kind, could we store it in the new Pebblev3 table format's value handle? The obsolescence of a snapshot-pinned key is semantically similar to the obsolescence of an old MVCC key. It's also equally beneficial to store an obsolete SET's value out-of-band. If I recall correctly, there's an extra bit or two in the value handle byte that could be used. DELs are value-less today, but to implement #2340 they (or a new tombstone key kind) will need to carry the length of the deleted value provided by the user.

[jbowens]

Thinking about this more, I think we should consider focusing our attention on limiting the amount of obsolete data we accumulate (eg, #1810). In Cockroach at least, I expect most of the obsolete data is unnecessary since we only need to snapshot a range at a time. Even if we can efficiently skip over the garbage we accumulate, we're still suffering the unnecessary write bandwidth and CPU cost of building larger tables. If we reduce the frequency of snapshot-pinned data, I think #2463 becomes more attractive.

[sumeerbhola]

Thinking about this more, I think we should consider focusing our attention on limiting the amount of obsolete data we accumulate

I don't disagree. What attracts me to the approach here is that it also provides a guarantee of single non-locally-deleted InternalKey per userkey in a sst, and pre-application of same sst rangedels. This guarantee means we can do foreign sst iteration with a minor change to the sst iterators instead of less efficient wrappers.

[jbowens]

Makes sense. Doing #2463 or the like would also keep the sst iterators efficient, right? If we can make snapshot-pinned keys exceedingly rare, refusing to allow sstables with locally-deleted keys to be shared becomes much more palatable.

[sumeerbhola]

Doing #2463 or the like would also keep the sst iterators efficient, right?

Agreed.
I do have a vague fear of creating a dependency from snapshots to what compactions are allowed, resulting in some level becoming very large. Also, small LSMs (rare for production, except for new stores, but maybe more common for benchmarking) can have L5 or L6 as Lbase, so we could potentially delay compactions out from L0.

[sumeerbhola]

I was thinking again about #2463 vs this issue. #2463 does require narrower snapshots as a prerequisite and I still have my "vague fear" from my previous comment.

Another question is if/when we do stateless read replicas, we will have foreign ssts for all levels, for a range. They will come from the same other-LSM, so the L0-L4 will have been local for that other-LSM and we can just use these seqnums. A different scheme would be to use manufactured seqnums for all levels, which we can do when there is the "guarantee of single non-locally-deleted InternalKey per userkey in a sst".

This guarantee seems generally useful to have, since it allows us the flexibility of even sharing L4 ssts for rebalancing e.g. if we have 5GB ranges, then L6, L5, L4 have 4.5GB, 450MB, 45MB (and L4 has likely more than that since the adjusted level multipliers is < 10x). The L5/L6 sharing was partially pulled out of a hat -- it would be nice if we did not have to hard code this behavior because adding additional shared levels had a detrimental effect on compactions.

[jbowens]

All user-facing reads in CockroachDB use iterators over the DB, hence have a higher read seqnum than all sstables

nit: I think it's possible to race with an ingest during iterator construction, obtaining a LSM version that includes the file but a visible sequence number that excludes the file:

1. Ingest acquires sequence number S.
2. Ingest acquires manifest lock and installs its version that includes the ingested sstable T.
3. Iterator construction acquires read state containing T.
4. Iterator reads current visible sequence number, < S.
5. Ingest finishes applications and publishes S.

[sumeerbhola]

Currently there is no support for MERGE keys when writing strict sstables with the obsolete bit, since it is non-trivial, and we can exclude all CockroachDB keys up to SystemMax from disaggregated storage. This exclusion contains the timeseries data in CockroachDB, which is the only use of MERGE (and there is no plan to expand the use of MERGE).

@jbowens had the following idea if we later need to add support for MERGE: we could use add a PREMERGE key kind that holds the pre-merged operands and write both the PREMERGE (live) key and the individual MERGE (obsolete bit set) operands (including for the most recent operand). A sstable iterator would be required to return either only the contained PREMERGEs (if the iterator's seqnum is higher than the sstable's LargestSeqNum) or only the contained MERGEs (if not). PREMERGE would otherwise behave just like MERGE, (or the sstable iterator could transparently edit the kind to MERGE before surfacing).

[jbowens]

@sumeerbhola Is this good to close out now that this is active on cockroach master?

[sumeerbhola]

Yes, I'll close it.
I've created #2756 for the disaggregated storage integration.