libroach: timebound iterator metadata doesn't consider intents

[danhhz]

Note: I haven't confirmed this behavior in practice, it's currently theoretical from reading code. Holding off on the severity label until it's confirmed. The fix will need to be backported into 2.0

When computing which timestamps are present in an sstable for the time bound iterator performance optimization, all keys without a timestamp are ignored, which includes intents. This means that certain (probably unlikely) compactions will result in a situation where a time bounded iterator reading from [t1,t2] will miss an intent at t2.

cockroach/c-deps/libroach/timebound.cc

Lines 38 to 53 in 8b684ff

	rocksdb::Status AddUserKey(const rocksdb::Slice& user_key, const rocksdb::Slice& value,
	rocksdb::EntryType type, rocksdb::SequenceNumber seq,
	uint64_t file_size) override {
	rocksdb::Slice unused;
	rocksdb::Slice ts;
	if (SplitKey(user_key, &unused, &ts) && !ts.empty()) {
	ts.remove_prefix(1); // The NUL prefix.
	if (ts_max_.empty() || ts.compare(ts_max_) > 0) {
	ts_max_.assign(ts.data(), ts.size());
	}
	if (ts_min_.empty() || ts.compare(ts_min_) < 0) {
	ts_min_.assign(ts.data(), ts.size());
	}
	}
	return rocksdb::Status::OK();
	}

Backup uses timebounded iterators and does a read at a certain timestamp until all intents below that timestamp have been resolved one way or another. This bug means that backup could incorrectly proceed with an unresolved intent. If this intent is later rolled back, the backup would contain a value that was never committed.

CDC will have similar correctness issues.

Several fixes are possible with various performance tradeoffs. An partial list:

• Include intents in the time bound metadata. This requires unmarshalling every mvcc metadata proto in the sst and is probably too expensive, especially for inline values like timeseries.
• Disable time bound metadata for any sstable containing intents. This will cause the time bound iterator to always look in the file, so will be correct but a performance pessimization.
• Some combination of the two based on how many intents are in the file or where in the keyspace it is.

[benesch]

Backup uses timebounded iterators and does a read at a certain timestamp until all intents below that timestamp have been resolved one way or another. This bug means that backup could incorrectly proceed with an unresolved intent. If this intent is later rolled back, the backup would contain a value that was never committed.

I don't think this exact scenario is possible. If the time bound iterator accidentally excludes a lingering intent from an aborted transaction, it's no problem, as the backup wasn't supposed to contain that intent anyway. The problem, as far as I can see, arises when the iterator excludes a lingering intent from a committed transaction; that intent needed to be promoted to a write, but the backup will not include that write.

[nvanbenschoten]

When an intent is laid down, we write two keys: the MVCCMetadata key at ts=0 that indicates that an intent exists and the provisional value at ts=value_ts that holds the intent's value. When we commit an intent, we actually just delete the MVCCMetadata key, effectively "revealing" the provisional value as committed.

I think the issue here is that if an intent's MVCCMetadata key is split in a different sst from its provisional value key, it's possible that a timebound iterator scans only over the sst with the provisional value key. In that case, the value will look committed even though it's not! I think the hazard arises when the intent is either aborted or pushed before being committed. If this happens, the backup would contain a value that was never committed or was committed at a later timestamp.

[benesch]

Gah! My understanding was still subtly wrong. Thanks for the clarification, @nvanbenschoten.

There's now two other solutions, though I'm not sure how well supported by RocksDB they are. One is to simply disallow splitting a metadata key from its actual values. The other is to only look at the last key in an SST. If it's a metadata key, then we need to look in and see if there's an intent. Only in that case do we need to erase the timestamp bounds on the SST.

[benesch]

Also, no wonder we haven't seen this in practice.

[benesch]

I'm upgrading this to S-1 to hopefully get more visibility. I think this needs to get fixed for v2.1. We haven't seen this in practice, but that's the nature of this bug: you would never notice when it happened.

@petermattis putting this on your radar. Is there anyone who can take a look at this?

[petermattis]

One is to simply disallow splitting a metadata key from its actual values.

This isn't possible as far as I'm aware.

The other is to only look at the last key in an SST. If it's a metadata key, then we need to look in and see if there's an intent.

Are you thinking this would be done at compaction time?

Is there anyone who can take a look at this?

Hrmm, the number of folks familiar with the C++ code is too small.

[benesch]

Are you thinking this would be done at compaction time?

Yeah, at SST build time. I'm hoping there's some way to do this with the table properties collector interface.

[danhhz]

Yeah every time you see an intent, copy the serialized proto to a field in the table prop collector. Every time you see a non intent, clear it. Then when the finalize method is called, if the field is non empty, deserialize the proto and process the timestamp

[petermattis]

I can take a crack at doing this, but may require some assistance in setting up a test scenario which fails. Sounds like what we want is a situation where there are two sstables where the first contains the MVCC metadata key and the second contains the provisional key. I'm thinking I can create that scenario using ingested sstables. Then I perform a backup and the sstable which contains the provisional key should be included in the backup incorrectly, right?

[benesch]

I can take a crack at doing this

🎉

Sounds like what we want is a situation where there are two sstables where the first contains the MVCC metadata key and the second contains the provisional key. I'm thinking I can create that scenario using ingested sstables. Then I perform a backup and the sstable which contains the provisional key should be included in the backup incorrectly, right?

Yes, that's my understanding. The SST with the metadata key (SST_m) will need to have time bounds that are older than the SST with the provisional key. Then the backup needs to be incremental on top of a full backup that occurred after the timestamp of any key in SST_m. I think. Getting such a full backup is going to be tricky. I think it'll be easier if you just create an MVCCIncrementalIterator over a store with the desired SSTs and make sure that you don't see the provisional key.

[danhhz]

Backups never include provisional keys, they retry until it's resolved one way or the other. I think the high-level issue here is that the timebound iterator would incorrectly skip the sstable, and the backup wouldn't know it had to wait for it to be resolved.

[danhhz]

Oh, I misunderstood what you meant by provisional key. What @benesch said.

[petermattis]

Yes, that's my understanding. The SST with the metadata key (SSTm) will need to have time bounds that are older than the SST with the provisional key. Then the backup needs to be incremental on top of a full backup that occurred after the timestamp of any key in SSTm. I think. Getting such a full backup is going to be tricky. I think it'll be easier if you just create an MVCCIncrementalIterator over a store with the desired SSTs and make sure that you don't see the provisional key.

So perhaps I should do this fully within storage/engine? Can one of you point me to the backup code which uses MVCCIncrementalIterator? Is this the code in ccl/storageccl/export.go?

[danhhz]

Yeah, I think it's fine (and much simpler) to test at the storage/engine level. You found it:

cockroach/pkg/ccl/storageccl/export.go

Lines 164 to 200 in 62c976d

	iter := engineccl.NewMVCCIncrementalIterator(batch, engineccl.IterOptions{
	StartTime: args.StartTime,
	EndTime: h.Timestamp,
	UpperBound: args.EndKey,
	})
	defer iter.Close()
	for iter.Seek(engine.MakeMVCCMetadataKey(args.Key)); ; iterFn(iter) {
	ok, err := iter.Valid()
	if err != nil {
	// The error may be a WriteIntentError. In which case, returning it will
	// cause this command to be retried.
	return result.Result{}, err
	}
	if !ok || iter.UnsafeKey().Key.Compare(args.EndKey) >= 0 {
	break
	}
	// Skip tombstone (len=0) records when startTime is zero
	// (non-incremental) and we're not exporting all versions.
	if skipTombstones && args.StartTime.IsEmpty() && len(iter.UnsafeValue()) == 0 {
	continue
	}
	if debugLog {
	// Calling log.V is more expensive than you'd think. Keep it out of
	// the hot path.
	v := roachpb.Value{RawBytes: iter.UnsafeValue()}
	log.Infof(ctx, "Export %s %s", iter.UnsafeKey(), v.PrettyPrint())
	}
	if err := rows.Count(iter.UnsafeKey().Key); err != nil {
	return result.Result{}, errors.Wrapf(err, "decoding %s", iter.UnsafeKey())
	}
	if err := sst.Add(engine.MVCCKeyValue{Key: iter.UnsafeKey(), Value: iter.UnsafeValue()}); err != nil {
	return result.Result{}, errors.Wrapf(err, "adding key %s", iter.UnsafeKey())
	}
	}

[a-robinson]

Not sure it's workable

That's quite the understatement.

[danhhz]

I think it's fair to say this was re-closed by the workaround merged in #32909