A nightly reconciliation job walks the keyspace of a live store whose entries are split across several nodes; what must that job tolerate to be correct?
answer
- evidence, not truth
- one walk per node
- no instant the union describes
- absence never proves non-existence
- confirm across two passes before deleting
basics
~20 sOne walk per node, assembled at different times: the result may repeat entries, may miss entries written while it ran, and describes no single instant. Every action must be idempotent, and a difference needs a second pass before anything destructive.
solid answer
~50 sTreat the result as evidence, not as truth. A walk is per node, so the job runs several walks and unions lists gathered at different times; within each walk, entries present throughout come back at least once, some come back twice, and entries that arrived or left mid-walk may be absent. Where the store can move entries between nodes while serving, an entry can also slip from a node you have finished to one you have not reached, or the reverse. So: deduplicate by key, make every per-entry action idempotent, never treat absence as proof an entry does not exist, and gate destructive actions behind agreement across two consecutive runs plus a minimum age on the entry. Throttle the batches, since the total work still tracks the distinct-key count. And finish by recording what the pass actually claims: converging, not complete.
go deeper
Recall that a walk over a split keyspace is one walk per node, and that what comes back is a best-effort list rather than a complete one.
Explain the mechanics you must handle: repeats, mid-walk arrivals, per-node guarantees that do not compose, and the pacing the job needs.
Demonstrate the production judgment: split the two questions, re-read before acting, confirm differences across runs, require a minimum entry age, and state what the pass may claim.
Ask whether the job should exist. A recurring whole-keyspace reconciliation is a standing tax and a standing risk; recording keys on the write path removes both.
Reconciling a volatile tier against the system of record is one of the few jobs that genuinely has to look at a whole keyspace. It is also where every weakness of traversal shows up at once, because the job does something with what it finds. ## What the job is really doing It is answering two different questions that people run together: - **Is everything that should be here, here?** That question is answered from the system of record, by iterating rows and addressing the store by key. It never needs a walk. - **Is anything here that should not be?** Only that question needs a traversal, because the keys you are hunting are the ones nobody remembers creating. Separating them is the first move a strong answer makes, and it halves the exposure to everything below. ## One walk per node When the keyspace is split, there is no single traversal. The job opens a walk against each node that holds part of the keyspace and unions the results. How keys got assigned to those nodes is not this job's business — what matters is the consequence: - The union is assembled at **several different times**, so it describes no instant even in principle. - The three-part guarantee holds **per node** and does not compose: at-least-once per node is not at-least-once globally the moment entries can move. - Where the store can **relocate entries between nodes while serving**, an entry can move from a node already walked to one not yet reached, and be missed, or the reverse, and be seen twice. - A node that is unreachable for part of the run leaves a hole. The job must know which nodes it actually covered, and say so. ## The four hazards, and the handling for each 1. **Repeats.** Deduplicate by key as you go, and make per-entry work idempotent so a survivor of the deduplication is harmless. Never attach a counter increment or an external call that must happen once per entry. 2. **Misses.** An entry written mid-walk may not appear. Absence is therefore never evidence of non-existence, and a job that deletes rows elsewhere because the walk did not see an entry is deleting on a guess. 3. **Staleness.** A key handed back at the top of the run may have been removed, overwritten or given an entry lifetime by the time you act on it. Re-read the entry immediately before acting, and accept that even that read is a moment old. 4. **Cost.** The total work still tracks the distinct-key count, and the job competes with live traffic for whichever node it is on. Cap the batch size, pace the loop, and prefer a window when the tier is least busy; where the deployment allows reading a copy that is not taking traffic, run the traversal there and accept the extra staleness that copy carries. ## Acting on a difference safely The dangerous step is the one that removes something. Two rules make it survivable, and they compose: - **Confirm across runs.** Act only on differences that two consecutive passes both saw. A mid-walk arrival that looked like an orphan on Monday is an ordinary entry on Tuesday. - **Require an age.** Ignore anything younger than the longest plausible write-to-commit gap in the producing service, so the job cannot race a caller that is halfway through creating the entry and its row. The same caution applies in reverse: do not write a row into the system of record because a walk found an entry the record lacks. The store is not the authority, and the entry may be exactly the debris the pass exists to clear. ## What the pass may claim when it finishes It may claim that it examined some entries and repaired or reported the differences it confirmed, over the nodes it reached. It may not claim a count, a clean bill of health, or `the keyspace now matches the record`. A reconciliation over a live keyspace is a converging process, and its value comes from running often enough that the residue stays small — not from any single run being complete. If the job's output is load-bearing enough that converging is not good enough, the right fix is upstream: record the keys on the write path, so the inventory does not have to be discovered at all.
- Why is walking the store the wrong way to check that everything which should exist does exist?Because that question is anchored in the system of record, not in the store. Iterate the rows and address the store by key: it is exact, it is resumable, its cost tracks the rows you care about rather than the whole distinct-key count, and it is unaffected by repeats and mid-walk arrivals. Reserve the traversal for finding entries nobody has a record of.
- The job sees an entry with no matching row. Can it delete the entry straight away?No. The entry may have been created a millisecond ago by a caller whose row is still in flight, and the walk gives no evidence about timing. Require the difference to survive two consecutive passes and require the entry to be older than the producing service's longest write-to-commit gap, then act.
- What does the job have to record about which nodes it covered?Which nodes it walked to completion, which it could not reach, and when each walk started and finished. Without that, a hole caused by an unreachable node is indistinguishable from a clean result, and the next pass cannot tell whether a difference is new or simply unobserved last time.
saying these in an interview costs you the question
- Treats the union of per-node walks as one consistent inventory.
- Deletes an entry the first time a pass finds no matching row.
- Assumes one traversal covers a keyspace split across nodes.
- Believes deduplicating keys makes the result exact.
- Runs the walk at full speed against the node taking live traffic.
- Writes a record row because a walk found an entry without one.