skip to content

On a single-node store still serving production traffic, how do you find which key prefixes hold the memory?

level: middleimportance: must knowfreq 64%

answer

  1. bounded batches, not one shot
  2. pause between batches
  3. size estimate per key
  4. sum bytes and count per prefix
  5. watch caller-observed latency

basics

~20 s

Walk the keyspace with an incremental cursor traversal in bounded batches, pausing between them, take a size estimate for each entry, and accumulate bytes and counts per prefix. Never ask for the whole keyspace in one operation.

solid answer

~50 s

You run a paced attribution walk. An **incremental cursor traversal** returns a bounded batch of keys and a cursor to continue from; you weigh each key in the batch, add its estimate to a running per-prefix sum and count, then sleep briefly before asking for the next batch. Asking for the whole keyspace in a single operation is not an option on a live tier — that contract is its own subject, and it is the reason the traversal exists. The pause, not the batch size, is what actually bounds the cost: on a server that executes one operation at a time every batch is time taken from serving, and where the server is multi-threaded you still pay for whatever value transfers the sizing needs. Watch caller-observed latency while it runs and tune the pause against it. Treat the result as an estimate taken over a window, not a census.

code

pseudocode · 20 lines
pseudocode
start_cursor = cursor_origin()
cursor       = start_cursor
batch_size   = 200          # keep any single operation short
pause_ms     = 50           # and bound the rate at which you repeat it
totals       = {}           # prefix -> { bytes, count }

while true:
    cursor, entries = traverse(cursor, batch_size)

    for key in entries:
        bytes = estimate_size(key)      # server figure where offered,
                                        # otherwise measure the fetched value
        p = prefix_of(key)              # or "__unattributed__"
        totals[p].bytes += bytes
        totals[p].count += 1

    if cursor == start_cursor:                 # the walk has come back round
        break

    pause(pause_ms)                     # the rate limiter, not the batch size

go deeper

for a junior

Remember the one rule that matters here: you never ask a live tier for its whole keyspace at once. Walking it in bounded batches is the supported way.

for a middle

Describe the loop end to end — cursor, bounded batch, size estimate, per-prefix sum and count, pause — and say why the pause rather than the batch size bounds the cost.

for a senior

Show the control loop: tune the pause against caller-observed latency, decide whether to run against a node that serves no traffic, and state the window the result covers.

for a principal

Decide whether this runs on demand during incidents or on a schedule that produces a trend, and who owns the dials so the procedure is not reinvented under pressure.

## What you are doing, and why it is delicate The goal is attribution: turning "the tier is holding a lot of memory" into "this prefix holds this many bytes across this many entries". Nothing in the store produces that, so you have to visit the entries yourself. The awkward part is that the only process able to visit them is the one that is also answering production traffic, so the measurement competes with the thing it is measuring. ## The procedure 1. **Decide the grouping.** Which segment of the key names the owner — the first colon-delimited segment, usually. Keys matching nothing go to an explicit remainder bucket. 2. **Traverse incrementally.** Ask for a bounded batch of keys and a cursor; continue from the cursor. One operation that returns the entire keyspace is forbidden on a serving tier. 3. **Weigh each key.** Take the server's size estimate where it offers one, otherwise measure the value you fetched. 4. **Accumulate.** A running sum of bytes and a count of entries, per prefix. Not a maximum — a sum. 5. **Pause between batches**, then repeat until the walk comes back round. 6. **Report** the per-prefix rollup, the unattributed remainder, and the gap between your summed estimates and the server's own total. ## Pacing is the whole safety mechanism A bounded batch keeps any *single* operation short. It does nothing about the *rate*, and a tight loop of short operations is still a sustained extra workload. The dials are the batch size and the pause, and both are chosen against the tier's spare capacity rather than copied from a default: - On a server that executes **one operation at a time**, every batch is time on the one thread that also serves callers. The pause is directly the share of that thread you are borrowing. - Where the server is **multi-threaded**, batches interleave with serving instead of blocking it, but the sizing work and any value transfers still consume connections, network and the caller's own memory. - Either way, the honest control loop is: run the walk, watch **caller-observed** latency, and only lengthen the batch or shorten the pause while that stays inside its budget. Server-recorded execution time will look fine long after callers have started queueing. A walk that takes two hours and costs nothing is a better measurement than one that takes four minutes and shows up in a latency graph. ## Getting a size for each entry This is the step where stores in this class genuinely differ, and an answer that assumes one behaviour is describing one product: | What the server offers | What the walk does | What it costs | |---|---|---| | An estimated size per entry | Ask for it per key | One cheap operation per key | | Only the value's length | Ask, and note that overhead is excluded | One cheap operation per key | | Nothing | Fetch the value and measure it | A transfer per key, plus your own footprint | | No enumeration at all | No walk exists; instrument the callers instead | Shipped code, not an operator action | If sizing requires transferring values, do not weigh every key. Weigh a sampled fraction per prefix and scale by the sampling rate, and label the output an estimate. ## Reading the result honestly The keyspace changed while you walked it: entries were written, deadlines passed, and entries may have been removed under pressure. The rollup is therefore a picture taken over a window rather than at an instant. What a cursor does and does not guarantee across concurrent mutation is its own subject, and you should say plainly that you rely on it rather than restating it. For attribution the practical consequence is small and worth stating anyway: report the wall-clock window the walk covered, and do not quote the result to more precision than the window deserves. ## How the deployment shape changes it - **A primary with a following copy:** run the walk against the copy if it serves no traffic, and the cost lands where nobody is waiting. Remember it lags the primary slightly. - **A partitioned keyspace:** one walk per node, merged. A cluster-wide rollup that silently came from one node is wrong in a way nobody will notice. - **A managed instance:** you may have no host access at all, but a paced walk needs only a connection, which is exactly why it is usually the route that survives. - **A tier too hot for even a paced walk:** move the analysis off the serving path entirely and work from a copy.

  • How do you choose the batch size and the pause?
    From the tier's spare capacity, not from a default. Watch caller-observed latency while the walk runs and only grow the batch or shrink the pause while that stays inside its budget. On a server that executes one operation at a time, each batch is time taken directly from serving, so the pause is the borrowed share made explicit.
  • The server will not report an entry's size. What now?
    Either fetch each value and measure it, paying a transfer per key and inflating your own footprint, or sample: weigh a fraction of the keys per prefix and scale by the sampling rate, labelling the output an estimate. Sizing from the value also misses whatever the entry costs beyond its bytes, so the totals are comparable to each other but not to the server's own.
  • Why not just run the walk faster out of hours?
    Often you can, and it is the right first move. But a volatile tier's composition at three in the morning is not the composition at peak, and some tiers have no quiet hour at all. Pace it anyway so the same procedure is safe when you need it during the day.

saying these in an interview costs you the question

  • Asks for the whole keyspace in one operation to save time
  • Runs the walk at full speed because each batch looks cheap
  • Fetches every value to weigh it without counting the transfers
  • Quotes the rollup as an exact census rather than a window
  • Tunes the walk against server-recorded execution time only
  • Confuses a largest-entries list with a per-prefix rollup