`ConsistencyCheck` can report incorrect unique keys at boundaries

[alecgrieser]

Looking at the ConsistencyCheck logic, there appears to be a problem with the way it is merging results that means that it will incorrectly report unique keys. The problem is in the way the merge works:

foundationdb/fdbserver/workloads/ConsistencyCheckUrgent.actor.cpp

Lines 399 to 430 in 0f64383

	while (currentI < current.data.size() || referenceI < reference.data.size()) {
	if (currentI >= current.data.size()) {
	referenceUniqueKey = reference.data[referenceI].key;
	referenceUniques++;
	referenceI++;
	} else if (referenceI >= reference.data.size()) {
	currentUniqueKey = current.data[currentI].key;
	currentUniques++;
	currentI++;
	} else {
	KeyValueRef currentKV = current.data[currentI];
	KeyValueRef referenceKV = reference.data[referenceI];
	if (currentKV.key == referenceKV.key) {
	if (currentKV.value == referenceKV.value)
	matchingKVPairs++;
	else {
	valueMismatchKey = currentKV.key;
	valueMismatches++;
	}
	currentI++;
	referenceI++;
	} else if (currentKV.key < referenceKV.key) {
	currentUniqueKey = currentKV.key;
	currentUniques++;
	currentI++;
	} else {
	referenceUniqueKey = referenceKV.key;
	referenceUniques++;
	referenceI++;
	}
	}
	}

It issues a GetRange request to multiple servers, and then it iterates over each response to see if there are keys that are missing and/or different. But each range response is only a partial view value of the total range. That means that once we've consumed all of the keys from one side, we can only mark the rest of the keys from the other siee as absent if the exhausted range response's more flag is false. For example, suppose there are two servers 1 and 2 and there are 10 keys, and each request returns 5 keys. The keys are:

key_01 -> both
key_02 -> both
key_03 -> both
key_04 -> only server 1
key_05 -> only server 1
key_06 -> both
key_07 -> both
key_08 -> both
key_09 -> both
key_10 -> only server 1

So, from server 1, it will read key_01, key_02, key_03, key_04, and key_05. From server 2, it will read: key_01, key_02, key_03, key_06, and key_07. This will then get reported as key_01, key_02, and key_03all being present (correctly). Thenkey_04andkey_05will be reported as unique to server 1 (correctly). Butkey_06andkey_07` will get reported as unique to server 2 (incorrectly). Instead, we should note that as server 2 has more data, we need to do another read. The current code is also ambiguous now as to whether we'll resume based on the end of the server 1 or server 2 read, but the correct logic should always resume from the minimum key (based on server 1 here).

In the second round, server 1 should read key_06, key_07, key_08, key_09, and key_10. Then server 2 will return key_06, key_07, key_08, and key_09 with a more of false. Because we're all done reading from server 2, we can still confidently mark key_10 as unique.

[alecgrieser]

I've validated that this is the case on the 7.3 branch. Todo is check the 7.4 and main branches. It would also appear that we have a few different places in the code where a very similar loop has been copied and pasted, and they all make the same mistake.