storage: bug in single delete optimization for separated intents

[sumeerbhola]

The SINGLEDEL optimization for separated intents is used for removing the intent when possible. It is important since

• A combination of SET=>SINGLEDEL (SET followed by/happens before SINGLEDEL) will result in both disappearing from Pebble when they meet in a compaction. In contrast SET=>DEL will cause the SET to disappear, but the DEL will typically fall all the way to L6 before being elided.
• Unlike interleaved intents, where we reused the same key for intents (<key>@0), separated intents use a different key for each txn. This is done to allow for lock contention reduction in the future. With interleaved intents we had <key>@0.SET=><key>@0.DEL=><key>@0.SET=><key>@0.DEL, so even if the latest DEL had to fall all the way to L6, the older DELs would vanish because of the newer SET (this is potentially important for keys with high write rates). With separated intents and high write rates, where each set and delete pair will be a different key, the SINGLEDEL optimization is important for not resulting in more garbage relative to interleaved intents.

The optimization is performed by tracking a TxnDidNotUpdateMeta bool in the intent's MVCCMetadata proto, which defaults to false for legacy code, and starts as true for non-legacy code. If the MVCCMetadata is updated using another SET, this value transitions to false. When resolving the intent we use SINGLEDEL if this value is true, else DEL. There are two correctness assumptions made here:

• [A1] The MVCCMetadata for a txn is never deleted and recreated during the lifetime of a transaction. This is important since the history of TxnDidNotUpdateMeta would be lost if it were deleted and recreated.
• [A2] CockroachDB range drops (due to the range being moved to another node) are done using a RANGEDEL across the whole range and not using individual DELs for the data to be removed. So we can get a sequence of: SET=>RANGEDEL=>SET=>SINGLEDEL if the range is removed before the intent is resolved, then added back, and then the intent is resolved. If the RANGEDEL were replaced by a DEL, we would have the bug described below.

Assumption [A1] is violated, by intent resolution for a non-finalized txn which has (a) rolled back savepoints that cause the intent to be removed, (b) the txn epoch has been incremented and the intent is from an older epoch.
Due to this violation we can see sequences like SET=>SET=>DEL=>SET=>SINGLEDEL.
To understand why this causes a problem, note that compactions only see a continuous subsequence of the sequence of operations on a key — they can be missing operations newer and older. A compaction can see the DEL=>SET and the SET will consume the DEL. The reasoning being that it is either (a) the current latest SET in the LSM in which case the DEL is no longer relevant, or (b) something later has deleted the whole key, in which the DEL is also no longer needed. The SINGLEDEL violates (b). The result of this compaction will cause the LSM to have SET=>SET=>SET=>SINGLEDEL. And if this SET and SINGLEDEL later meet in a compaction, both will vanish. Now all the deleted SETs from before will reappear incorrectly.

List of things we need to do to fix this:

• Pebble unit test to demonstrate above expected behavior @sumeerbhola db: add test demonstrating current SINGLEDEL behavior pebble#1252
• CockroachDB unit test that reproduces bug storage: add randomized test to trigger intent single deletion bug #69902
• CockroachDB randomized unit test that reproduces bug under all possible intent resolution scenarios @sumeerbhola
• Confirmation that roachtest failures seen in roachtest: tpccbench/nodes=9/cpu=4/multi-region failed [replica inconsistency] #69414 are due to SINGLEDEL, and narrow down what is causing inappropriate use of SINGLEDEL: confirmed based on no failure when reducing the scope of the SINGLEDEL optimization. Workload and code inspection suggested the bug is because of txn epoch being bumped up.
• CockroachDB workaround to narrow use of SINGLEDEL optimization storage: narrow down use of SingleDel to avoid anomalies #69923
• CockroachDB correctness when migrating from 21.1 to 21.2 storage: override MVCCMetadata.TxnDidNotUpdateMeta in mixed version c… #70267
• Range movement or any other range related operations may also trigger this bug -- see storage: bug in single delete optimization for separated intents #69891 (comment)
  • Add KV test that stresses range movement while having unresolved intents, and see if intentInterleavingIter operating over the whole global key space finds any inconsistency.
  • Fix the code to use range delete instead of delete for 21.2 beta if the Pebble change is not a release blocker.
• Pebble change to make SINGLEDEL semantics robust to sequences like SET=>DEL=>SET=>SINGLEDEL and SET=>SINGLEDEL=>SET=>SINGLEDEL.
  • Create issue with solution sketch and correctness proof db: more deterministic SingleDelete semantics for Set pebble#1255
  • Code changes @nicktrav

[tbg]

Isn't [A2] also violated? The code that deletes the replica data is here

cockroach/pkg/kv/kvserver/replica_destroy.go

Lines 137 to 151 in 3357d2e

	func (r *Replica) destroyRaftMuLocked(ctx context.Context, nextReplicaID roachpb.ReplicaID) error {
	startTime := timeutil.Now()
	ms := r.GetMVCCStats()
	batch := r.Engine().NewUnindexedBatch(true /* writeOnly */)
	defer batch.Close()
	clearRangeIDLocalOnly := !r.IsInitialized()
	if err := r.preDestroyRaftMuLocked(
	ctx,
	r.Engine(),
	batch,
	nextReplicaID,
	clearRangeIDLocalOnly,
	false, /* mustUseClearRange */
	); err != nil {

and note how it passes false for mustUseClearRange, which translates into calling into this method:

cockroach/pkg/storage/engine.go

Lines 1003 to 1007 in 6e34358

	// ClearRangeWithHeuristic clears the keys from start (inclusive) to end
	// (exclusive). Depending on the number of keys, it will either use ClearRawRange
	// or clear individual keys. It works with EngineKeys, so don't expect it to
	// find and clear separated intents if [start, end) refers to MVCC key space.
	func ClearRangeWithHeuristic(reader Reader, writer Writer, start, end roachpb.Key) error {

The other caller of destroyRaftMuLocked (during splits) similarly passes false (so nobody passes true anywhere):

cockroach/pkg/kv/kvserver/store_split.go

Lines 101 to 102 in 793b4c8

	const mustUseClearRange = false
	if err := clearRangeData(&split.RightDesc, readWriter, readWriter, rangeIDLocalOnly, mustUseClearRange); err != nil {

This is easy to fix of course - we need to pass true in both places - but possibly at the expense of subjecting pebble to a higher frequency of rangedels.

[sumeerbhola]

• Are we deleting any range local or global data when splitting a range? If not we may be ok there since those are the only keys with intents.
• Passing true for those cases would also require a change to 21.1, which is troublesome. I had been thinking of the range tombstone we place here

  cockroach/pkg/kv/kvserver/store_snapshot.go

  Lines 166 to 170 in 91311cf

  	if err := msstw.currSST.ClearRawRange(
  	msstw.keyRanges[msstw.currRange].Start.Key, msstw.keyRanges[msstw.currRange].End.Key); err != nil {
  	msstw.currSST.Close()
  	return errors.Wrap(err, "failed to clear range on sst file writer")
  	}

  which I had been assuming happens whenever we add a range. Is that a correct assumption?

[tbg]

Are we deleting any range local or global data when splitting a range? If not we may be ok there since those are the only keys with intents.

The snippet I linked is a special code path, where a split realizes that the right-hand side it is about to create has already been rebalanced away (and so it becomes another instance of replicaGC).

Passing true for those cases would also require a change to 21.1, which is troublesome.

Wouldn't this be taken care of by the same strategy we discussed for avoiding the original anomaly? We make sure that SingleDel isn't used in the first place until 21.1 is out of the picture, by overriding TxnDidNotUpdateMeta to false until a 21.2 cluster version gate is active.

I had been thinking of the range tombstone we place here

Yeah, maybe we are technically OK here? Let's say replicaGC can really make a random intent show up again (as it can). This technically doesn't really matter until this intent shows up in a Replica. For a replica to exist again, a snapshot has to apply, and from the looks of it a snapshot will put a blanket rangedel over the entire keyspace of the replica, which nukes the intent anyway. So yeah, anomaly might be benign, but I still wouldn't take my chances with it, who knows what fallout unexpected KVs in "unassigned" keyspace have.

[sumeerbhola]

Wouldn't this be taken care of by the same strategy we discussed for avoiding the original anomaly? We make sure that SingleDel isn't used in the first place until 21.1 is out of the picture, by overriding TxnDidNotUpdateMeta to false until a 21.2 cluster version gate is active.
...
who knows what fallout unexpected KVs in "unassigned" keyspace have.

Agreed about using the same strategy. But we would need to fix this for the 21.2 beta which will then need to use mustUseClearRange=true, even in a cluster with only 21.2 beta nodes, since we are deeming the Pebble-level fix as a GA blocker and not a release blocker.
And I agree that there can be unexpected fallout. One example is that the intentInterleavingIter enters an error state if it finds an intent without a provisional value. We should not really be scanning a range that is no longer local, but this would still make me nervous.

I've added this to the list of things to do, and it includes having a unit test that creates conditions like range movement while there are live intents. Can we get someone from KV to write such a test -- this is likely to be generally useful and will really increase our confidence in the code?

[sumeerbhola]

Documenting the current plan for the work item:
CockroachDB correctness when migrating from 21.1 to 21.2

• We are fixing the intent resolution code path in 21.2-beta to use SingleDelete more conservatively. The 21.2-GA will likely include Pebble changes to make the current usage of SingleDelete correct.
• There is a problem if someone upgrades from 21.1 to 21.2-beta or 21.2-GA, described next.
• Problem: 21.1 nodes will not write separated intents while they are the leaseholder for a range. However they can become the leaseholder for a range after a separated intent was written (in a mixed version cluster). Hence they can resolve separated intents. The logic in 21.1 for using SingleDelete when resolving intents is similarly buggy, and the Pebble code included in 21.1 will not make this buggy usage correct.
• Solution (by @tbg): Change code in 21.2 to never set txnDidNotUpdateMeta=true when writing separated intents, until the cluster version is at the latest version defined in clusterversion when the buggy code was fixed in 21.2. So 21.1 code will never use SingleDelete when resolving these separated intents (since the only separated intents being written are by 21.2 nodes).