apple / apple/foundationdb

DD finishMove*: serverKeys is not re-verified across the waitForShardReady wait, relying on an unstated keyServers co-write invariant

Open
#13,941 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
16.7k
Forks
1.6k
Avg merge
1d 20h
Merged PRs (30d)
126

Description

### Summary

`finishMoveKeys` / `finishMoveShards` re-verify `keyServers` after the `waitForShardReady`
wait, but nothing re-verifies `serverKeys`. That leaves a window in which a transaction
that revoked a destination server's ownership in `serverKeys` — without also updating
`keyServers` — would be invisible, and the finish-move commit would resurrect it.

No such writer exists today, so **this is not a live data-loss bug**. It is an unstated,
unenforced invariant that the current code silently depends on. Raised by @spraza during
review of the release-7.4 backport
(https://github.com/apple/foundationdb/pull/13642#discussion), and worth recording against
`main` because that is where a future one-sided writer would first appear.

### Background

#13364 restructured both finish-move functions so the `waitForShardReady` wait happens
outside any transaction:

```
txn1: read keyServers / serverTags (/ dataMove) -> read version V1, then tr.reset()
wait: waitForShardReady, up to SERVER_READY_QUORUM_TIMEOUT (15s)
txn2: re-verify, then commit -> read version V2, commit version C
```

`tr.reset()` discards txn1's read conflict ranges. Only some of what they covered is
replaced:

| what | window | covered by |
|---|---|---|
| `keyServers` | (V1, V2] | txn2 re-reads at V2 and `destUnchanged()` compares by value |
| `keyServers` | (V2, C] | txn2's own `krmGetRanges` is a non-snapshot read |
| `serverKeys` | (V2, C] | `krmSetRangeCoalescing`'s explicit `addReadConflictRange` calls |
| `serverKeys` | **(V1, V2]** | **nothing** |

Worth noting where the pre-#13364 `serverKeys` coverage came from, because it is not
obvious: `finishMoveKeys` never *reads* `serverKeys` at all. It came from
`krmSetRangeCoalescing`, which probes with `Snapshot::True` and then calls
`addReadConflictRange` itself (`fdbclient/KeyRangeMap.cpp:272-277`). Its second range starts
at `lastLessOrEqual(range.end)`, which in a uniform map is the boundary at or below
`range.begin`, so it spanned the whole range. Running in the same transaction at V1, that
covered (V1, C].

### Why it is currently safe

Every writer that changes a server's ownership in `serverKeys` also writes the
corresponding `keyServers` entry for the same range in the same transaction, so the V2
re-read sees it and `destUnchanged()` catches it. Audited: `startMoveKeys` /
`removeOldDestinations`, both `finishMove*`, `cleanUpSingleShardDataMove`,
`cleanUpDataMoveCore`, both branches of `removeKeysFromFailedServer`, `prepareBlobRestore`,
`seedShardServers`.

Two further mitigations: `checkMoveKeysLock` runs inside txn2, so a *different* DD
generation cannot slip a write into (V1, V2] without txn2 failing `movekeys_conflict` — the
exposed surface is intra-generation writers only; and
`auditLocationMetadataPreCheck`/`PostCheck` cross-validate the two maps.

### The obvious fix does not work

Adding a read conflict range on `serverKeys` in txn2 looks like the answer:

```cpp
for (const UID& ssid : dest) {
tr.addReadConflictRange(KeyRangeRef(serverKeysKey(ssid, currentKeys.begin),
serverKeysKey(ssid, currentKeys.end)));
}
```

Read conflict ranges are evaluated from the transaction's read version to its commit
version. txn2's read version is V2, so this protects (V2, C] — the window
`krmSetRangeCoalescing` already covers — and cannot see (V1, V2]. A one-sided writer
committing at V1 < V < V2 is *inside* txn2's snapshot: the `keyServers` re-read shows
nothing, `destUnchanged()` passes, and the ownership is resurrected. Adding it would make
the invariant look resolver-enforced when it is not.

(It does incidentally close interior gaps in the fragmented case, where
`krmSetRangeCoalescing`'s second conflict range starts at an interior boundary — a smaller,
separate improvement.)

Also considered and rejected: `tr.setVersion(V1)` on txn2 would restore the exact
pre-#13364 coverage with no extra reads, but V1 is up to `SERVER_READY_QUORUM_TIMEOUT` (15s)
stale against a ~5s `MAX_READ_TRANSACTION_LIFE_VERSIONS`, so the reads would throw
`transaction_too_old`.

### What does work

A semantic check in txn2, which needs no txn1 snapshot: `startMoveKeys` has already set
`serverKeys[dest][range]`, so txn2 can simply confirm the destination team is *still*
assigned. After `destUnchanged()` passes, issue `|dest|` parallel `krmGetRanges` over
`serverKeysPrefixFor(ssid)` and require every sub-range to decode as `assigned`; retry
through `retryAfterPostWaitChange()` otherwise.

Two deliberate choices:

- Check `assigned` only, not the `dataMoveId` stamp. `destUnchanged()` already enforces the
stamp on the `keyServers` side, and old-format entries decode to `anonymousShardId`, so
comparing it here would add false-retry surface for no extra coverage.
- `serverKeysTrueEmptyRange` decodes as `assigned == true`, so `AssignEmptyRange` moves do
not trip the check.

Cost is `|dest|` extra `krmGetRanges` inside txn2 — issued in parallel, so roughly one extra
round trip — plus the read conflict ranges they add, which will raise txn2's `not_committed`
rate somewhat.

### Also worth doing regardless

State the invariant where it is discoverable. The `serverKeysRange` declaration
(`fdbclient/include/fdbclient/SystemData.h:195`) currently says nothing about it, and
neither does the `tr.reset()` site in either finish-move function.

### Status

I have this implemented locally against `main` (branch
`movekeys-serverkeys-conflict-window`) but it is **not yet built or Joshua'd**, so no PR
yet. Filing the issue first so the reasoning is recorded — particularly the fact that the
intuitive `addReadConflictRange` fix is in the wrong transaction, which cost some time to
work out.

Note there is no test that can fail without this check, since no current writer violates the
invariant. Joshua can only show it does not regress anything, never that it fixes something.
That is the main argument for landing it on `main` and letting it bake rather than rushing it
into a release branch.

Contributor guide

Open the contributing guide

Research direction

Start with finishMoveKeys and finishMoveShards around the tr.reset() and waitForShardReady flow, then read serverKeysRange in fdbclient/include/fdbclient/SystemData.h:195 and the listed serverKeys writers. Review the local implementation's semantic verification approach, build it, and run Joshua; done means the invariant is documented and the post-wait ownership check works without regressions.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
databases, distributed-systems
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.