What does an incremental cursor walk over a live keyspace actually guarantee about the entries it returns, and what does it not?
answer
- a position, not a moment
- three parts, and one is silence
- at least once for what stayed
- repeats are normal, not a bug
- idempotent work only
basics
~20 sA cursor walk returns every entry present throughout it at least once, may return one twice, and may or may not return entries that arrived or left mid-walk. It is not a snapshot, so no exact count rests on it.
solid answer
~50 sThe guarantee has three parts, and the third is the one people forget. Any entry that was present for the entire duration of the walk comes back **at least once**; the same entry **may come back more than once**; and an entry that was written or removed while the walk was running **may or may not** appear. Nothing in it says the batches describe the keyspace at any single instant. So you can build a best-effort audit or a repair pass whose work on each returned entry is idempotent, and you cannot build an exact distinct-key count, a consistent inventory as of a moment, or a proof that no entry violates some rule — a violating entry may simply never have been handed to you. Where the keyspace is split across nodes the walk is one walk per node, which weakens it further.
go deeper
Remember the shape: bounded batches plus a cursor you hand back, and a result that is a good list rather than an exact one.
State all three parts of the guarantee without prompting, including the silence about entries that arrived or left, and derive the idempotence requirement from the repeat clause.
Show what you refuse to build on it — exact counts, correctness proofs, once-per-entry effects — and say what you do instead when the answer has to be exact.
Treat it as a contract question: which guarantees a component owes its callers, and why buying a snapshot here costs precisely what the walk was introduced to save.
A cursor traversal is the safe way to look at a keyspace on a store that is still serving traffic: the caller asks for a bounded batch, the store returns some keys and an opaque cursor, and the caller hands the cursor back for the next batch until it comes home at its terminal value. Everything useful about it, and everything dangerous, follows from one fact — the cursor marks a position, not a moment. ## The promise, in three parts 1. **At least once for what stayed.** Any entry that was present from the first batch to the last comes back at least one time. 2. **Possibly more than once.** The same key may appear in two different batches. This is normal and not a defect in the caller. 3. **No promise at all for what moved.** An entry created after the walk began, or removed before it ended, may appear or may not. Either outcome is correct behaviour. What is absent is as important: there is no ordering promise, no count promise, and no instant the batches collectively describe. ## Why the promise is that weak The store is answering ordinary traffic between your batches, so the structure being walked changes under you. The cursor marks a position in a table that can grow or shrink while the walk is in flight. A store that wanted a snapshot instead would have to hold a consistent view of the keyspace for the whole duration — which means either blocking writers or copying, and both cost exactly what the incremental walk was introduced to avoid. So the iteration order is chosen so that a resize cannot lose an entry that stayed put, and repeats are accepted as the price. The weak guarantee is not sloppiness; it is the deal that makes the walk cheap enough to run on a live tier. ## What you may build on it - A **best-effort repair or audit pass**, where the work done on each returned entry is idempotent — re-applying it to the same entry twice changes nothing. - A **background sweep** that converges over repeated runs rather than being correct in one: anything it missed this time is a candidate for next time. - A **sample or an estimate** you are willing to label as such, for a report nobody will act on destructively. - A **migration sweep** that copies or rewrites entries, provided the copy is idempotent and the source of truth is elsewhere. - A **trigger for a second, exact check**: treat every key the walk hands back as a candidate to be verified against the system of record rather than as a finding. ## What you may not build on it | you want | why the walk cannot give it | |---|---| | an exact distinct-key count | repeats inflate it, missed arrivals deflate it, and you cannot tell which happened | | a consistent inventory as of a moment | no instant exists that the batches describe | | a proof that no entry breaks a rule | a violating entry may never have been returned | | a once-per-entry side effect | a repeat runs the effect twice; billing, emitting or incrementing per returned entry is wrong | | a deletion you can call complete | writers are live, so `nothing matched on the last pass` is not `nothing matches` | ## Batches, cursors and knowing when to stop The batch size is a hint. Where the store applies a pattern filter after reading a batch, a call can return no keys at all and still not be finished, so an empty batch is never the termination condition — the walk is over when the cursor comes back at its terminal value. Hold the cursor as opaque: it encodes an internal position, not a key or an offset, and arithmetic on it is meaningless. It is resumable across process restarts, but the longer you hold it the more of the keyspace has churned underneath, which widens the third part of the guarantee rather than breaking it. ## More than one node, and stores with no walk at all Where the keyspace is split across nodes, a walk is **one walk per node**, and the union is a list assembled at several different times — the three-part guarantee holds per node and does not compose into anything stronger. And the walk is not universal: some stores in this class expose no incremental traversal at all, so a design that depends on walking is a design that cannot move to them. If what you need is an exact, stable set of keys, the honest answer is that no walk of a live keyspace will ever give it to you: keep your own lookup, or derive the set from the system of record and address the store by key.
- Why can a walk return the same key twice, and what must the caller do about it?The structure being walked changes under a live cursor, and the iteration order is chosen so that a resize cannot lose an entry that stayed put — repeats are the accepted price. The caller must make per-entry work idempotent, or deduplicate keys as it goes, and must never attach a once-per-entry side effect such as a counter increment or a charge.
- A batch comes back empty. Is the walk finished?No. Where the store filters a batch after reading it, a call can legitimately return nothing and still be mid-walk. The only termination condition is the cursor returning to its terminal value; treating an empty batch as the end silently truncates the traversal and makes it look like the keyspace is smaller than it is.
- You need an exact count of entries under a prefix. What do you do?Not a walk. Either count on the write path — maintain the number as the entries are created and removed — or derive it from the system of record. Counting by traversal is wrong twice over: repeats inflate it, entries arriving mid-walk are a coin flip, and there is no instant the total belongs to.
Counting the books in a library while readers browse. Walk the shelves aisle by aisle and you will certainly see every book that stayed shelved the whole time; you may count one twice if a reader carries it into an aisle you have not reached yet; and a book brought in or taken out during your walk may or may not be counted at all. What you come away with is a good list, not a stocktake — fine for spotting damaged spines, useless for telling the insurer how many books you own.
saying these in an interview costs you the question
- Treats the walk as a consistent snapshot of the keyspace.
- Reports a repeated key as a bug in the client or a stale cursor.
- Stops the walk when a batch comes back empty.
- Counts entries by walking and calls the total exact.
- Does non-idempotent work per returned entry, such as charging or incrementing.
- Concludes an entry does not exist because the walk never returned it.