apple / apple/foundationdb

`ConsistencyCheck` can report incorrect unique keys at boundaries

Open
#13,311 1 comment 0 reactions 1 assignee Claimed by @alecgrieser View on GitHub
Dominant language
C++
Stars
16.7k
Forks
1.6k
Avg merge
1d 20h
Merged PRs (30d)
126

Description

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: https://github.com/apple/foundationdb/blob/0f6438317625d6bd6cd230ef9853199a1d57ad36/fdbserver/workloads/ConsistencyCheckUrgent.actor.cpp#L399-L430

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_03` all being present (correctly). Then `key_04` and `key_05` will be reported as unique to server 1 (correctly). But `key_06` and `key_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.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.