Why is asking a serving in-memory store for every key matching a prefix in one operation not a harmless query?

An in-memory store of this class addresses a value by its key and by nothing else. There is no schema, no catalogue and no table of contents, so the question `which keys are in there?` is not a lookup at all — it is a traversal of the entire address space wearing the costume of a single call. ## What the single-operation form actually asks for Asking the store to return every key matching a pattern, in one operation, asks it to do three things at once: examine every key it holds, keep the ones that match, and hand the whole result back as one reply. Each is a cost the caller rarely pictures. - **The work follows the distinct-key count, not the match count.** There is no index over key names to consult; the pattern is tested against each key in turn. A prefix that matches forty entries out of sixty million still costs sixty million comparisons. - **The reply is assembled whole.** Every matching key string is built into one response before the first byte is useful to anyone. A million matches means a large allocation on the server, the same again on the client, and a long push through one connection. - **It is all or nothing.** There is no partial result and no resume point. A client that gives up and disconnects does not stop the server — the traversal it started runs to completion regardless, and the caller has paid the cost without getting the answer. ## Who pays while it runs This is where the class genuinely varies, and asserting one shape as the model is the classic mistake. - Where **the store executes one operation at a time**, the traversal runs to completion before any other caller is served. Every waiting request pays the full duration, so a traversal that takes four seconds is a four-second outage for everyone on that node. - Where **the store executes operations on several worker threads**, the same traversal occupies a worker, the allocator and the network path. It narrows the tier rather than stopping it — which is better, not harmless, because a large enough reply still saturates the connection and the memory budget. Either way it is an unbounded operation on a component whose whole value is a bounded answer measured in microseconds. ## The incremental alternative A cursor traversal replaces one unbounded operation with many bounded ones. The caller asks for a batch; the store returns a few keys plus an opaque cursor marking where it stopped; the caller hands that cursor back for the next batch, and repeats until the cursor comes back at its terminal value. Between batches, other callers are served normally. | | whole-keyspace listing | cursor traversal | |---|---|---| | work per call | the whole keyspace | a bounded batch | | other callers | wait, or compete, for the whole run | served between batches | | resumable | no | yes, from the cursor | | result | one complete list, at a price | at-least-once, repeats possible | | a picture of one instant | no | no | Two details matter when you write the loop: 1. **The batch size is a hint, not a promise.** Where the store applies the pattern filter after reading a batch, a call can legitimately come back with no keys at all and still not be finished. The walk is over when the cursor returns to its terminal value, never because a batch came back empty. 2. **The walk is not a snapshot.** Entries present throughout the walk come back at least once, an entry may come back more than once, and entries that arrived or left mid-walk may or may not appear. ## What the incremental form does not buy back - It is **not universally available**. Some stores in this class expose no incremental traversal at all; the only way to reach an entry is to already know its key. - 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. - It is still **proportional to the whole keyspace** in total work. It spreads the cost across many small calls; it does not remove it. A walk every minute over sixty million keys is a permanent background tax on the tier. ## The verdict a strong answer ends on An incremental walk is the right way to run a traversal you genuinely need: a one-off audit, a best-effort repair pass, a migration sweep. It is the wrong answer to `how do I find every entry for this customer` on a request path. When a code path needs that list routinely, stop asking the store to find things nobody asked it to index — maintain your own lookup, or derive the set from the system of record and address the store by key.