skip to content

The Redis SCAN command returns a cursor you pass back on the next call. What consistency guarantees does a complete SCAN iteration give you about the elements returned, and why can the same key come back twice?

level: middleimportance: must knowfreq 55%

answer

  1. at-least-once, never at-most-once
  2. cursor = reverse binary bucket index
  3. rehash/shrink → duplicates, no misses
  4. added/removed mid-iteration = undefined
  5. stop only at cursor 0, not empty batch

basics

~20 s

Guarantee: any element present from the start to the end of the full iteration is returned at least once. Elements added or removed mid-iteration may or may not appear, and duplicates are possible because the hash table can rehash while you iterate. No snapshot, no server-side state.

solid answer

~50 s

SCAN gives an **at-least-once, non-snapshot** iteration. Precisely: an element present in the collection for the whole duration of a complete iteration is returned at least once; an element added or removed during the iteration may or may not be returned; and the same element may be returned multiple times. The client must dedupe if that matters. The cursor is not an offset — it is a position in the hash-table bucket array encoded with **reverse binary iteration** (increment from the high-order bit, carrying rightwards). Redis's dictionary grows and shrinks by rehashing into a power-of-two table, and that ordering guarantees no element can hide in a bucket you already passed when the table resizes. The price of that guarantee is duplicates: when the table shrinks, buckets merge, so already-visited elements can land in a bucket you have not visited yet. The cursor carries no server state, so iterations can be paused, resumed, or run concurrently. Iteration ends only when the returned cursor is `0`.

code

text · 10 lines
text
127.0.0.1:6379> SCAN 0 MATCH user:* COUNT 10
1) "17"
2) (empty array)      # normal: those buckets held no matches
127.0.0.1:6379> SCAN 17 MATCH user:* COUNT 10
1) "25"
2) 1) "user:8812"
...
127.0.0.1:6379> SCAN 9 MATCH user:* COUNT 10
1) "0"                # ONLY this ends the iteration
2) 1) "user:41"

go deeper

for a junior

Recall the contract in one line: everything that stayed the whole time comes back at least once, duplicates can happen, and you keep calling until the cursor is 0.

for a middle

Explain that the cursor encodes a hash-table bucket position and that resizing/rehashing is what forces at-least-once semantics; describe how a client loop should dedupe and terminate.

for a senior

Reason about consequences in production: idempotent per-key actions, TOCTOU handling for keys that vanish, why SCAN cannot back an exact count, per-node cursors in Cluster, and how a migration must also cover keys written after the scan started.

for a principal

Position SCAN as a deliberate CAP-style trade — statelessness and bounded latency bought with weakened iteration semantics — and specify the surrounding design (dual-write during migration, reconciliation pass, or a maintained index) so correctness never depends on the scan being complete.

## The problem SCAN has to solve Redis must let you walk a collection that other clients are mutating, without blocking the server for the duration and without keeping per-client iteration state on the server (which would leak on disconnect and cost memory). Those constraints rule out both a snapshot cursor and an offset-based paginator. ## Why an offset would not work The keyspace, and a large hash or set, are stored in a hash table: an array of buckets whose size is a power of two. When the table gets too full, Redis creates a new table of double the size and **rehashes** entries into it incrementally (both tables are live during the migration); when it becomes too sparse it shrinks the same way. An element's bucket index therefore changes over time. A naive "resume at bucket 137" cursor would silently miss elements that moved from a not-yet-visited bucket to an already-visited one during a resize. ## Reverse binary iteration SCAN's cursor is a bucket index that is advanced by adding one to the **most significant** bit and carrying towards the least significant bit — the mirror image of normal counting. The useful property of this order is how it interacts with power-of-two resizes. When the table doubles, an element from old bucket `b` ends up in either `b` or `b + oldsize`; when it halves, buckets `b` and `b + newsize` merge into `b`. Under reverse-binary order, the buckets you have already visited always map, after any resize, onto positions the algorithm treats as already visited — so nothing that stayed in the collection can slip behind the cursor unseen. (While a rehash is in progress Redis scans the corresponding bucket in both tables, which is why the guarantee holds mid-resize too.) ## The three guarantees, stated exactly 1. **Full-iteration guarantee**: an element that is present in the collection from the moment the iteration starts until the moment it ends is returned **at least once**. 2. **No guarantee for churn**: elements added or removed during the iteration may or may not be returned. Nothing is promised either way. 3. **Duplicates are possible**: the same element may be returned by several calls. This is not a bug and clients must tolerate it. There is deliberately **no** snapshot, no isolation from concurrent writers, and no ordering guarantee. ## Where duplicates actually come from Two sources. First, a shrinking table merges two old buckets into one: if you had already visited one of them, its elements can be reported again from the merged bucket. Second, while an incremental rehash is running, a bucket index is scanned in both the old and the new table, and the ordering may cause an element to be seen from both sides. Growth-heavy workloads produce fewer duplicates than shrink-heavy ones; a fast-churning keyspace produces more. ## The cursor is stateless Nothing about your iteration lives on the server. That has practical consequences: you can pause for an hour and resume, you can hand the cursor to a different connection or process, any number of clients can iterate concurrently, and a disconnect leaks nothing. There are no timeouts to worry about. The flip side is that the server cannot help you — it cannot tell you the progress percentage, and a cursor is only meaningful for the collection it came from (and, in Cluster, for the node it came from, since each master holds a different slice of the keyspace). ## Termination The iteration is complete **only** when a call returns cursor `0`. An empty batch mid-iteration is completely normal — SCAN visited some buckets, none of them had a matching element, and it returned early to keep the command short. Code that stops on an empty batch is one of the most common SCAN bugs. A complete iteration is guaranteed to terminate in a bounded number of calls provided the collection is not growing without bound. ## Writing correct client code - **Dedupe** if the action is not idempotent — counting, billing, sending an email. A client-side hash set of seen keys works for moderate sizes; a probabilistic filter for huge ones. - **Prefer idempotent actions**: `UNLINK`, `EXPIRE`, an upsert into a search index. Then duplicates cost only a little extra work. - **Handle time-of-check/time-of-use**: a returned key may already be deleted, may have been recreated with a different type, or may have gained a TTL. Handle nil replies and `WRONGTYPE` rather than assuming. - **Never use SCAN to compute exact counts** of a mutating collection. Use `DBSIZE`, `SCARD`, `HLEN`, `ZCARD` for exact cardinality of one structure. - **Do not assume completeness for correctness-critical work.** "Every key that existed the whole time is seen at least once" is exactly the guarantee — a key created after you started may be missed, so a migration must also handle newly-written keys through the write path itself. ## What interviewers are listening for The phrase "at least once, with possible duplicates, and no snapshot", awareness that resizing/rehashing is *why*, and the operational conclusion: make the per-element action idempotent, dedupe when it is not, and stop only on cursor 0.

  • Can you pause an iteration for an hour and resume with the same cursor?
    Yes — the cursor is a plain integer and the server keeps no iteration state, so there is nothing to expire or leak. You may even resume from a different connection or process. What you lose is coverage: keys created during the pause may or may not be returned, and the longer the gap, the more rehashing has happened and the more duplicates you may see.
  • You need an exact count of keys matching a prefix. Is a full SCAN good enough?
    No, for two reasons: duplicates would inflate the count unless you dedupe, and keys created or deleted during the iteration are simply undefined, so the number describes no single moment in time. If you need an exact, meaningful count, maintain a counter or an index set at write time, or accept an approximate figure and say so.
  • Why does SCAN return duplicates at all — could the design avoid them?
    Duplicates are the price paid for the no-miss guarantee under a hash table that resizes while you iterate. When the table shrinks, two buckets merge, so elements you already saw can reappear in a bucket ahead of the cursor. Avoiding that would require server-side iteration state or a snapshot, both of which Redis deliberately refuses in order to keep SCAN stateless and non-blocking.

Like counting a crowd that keeps reshuffling: you are promised you never miss anyone who stayed the whole time, but you may count some people twice.

saying these in an interview costs you the question

  • "SCAN gives me a consistent snapshot of the keyspace" — it explicitly does not.
  • "The cursor is an offset / page number I can compute progress from" — it is a reverse-binary bucket index, not a position in a list.
  • "An empty result means the iteration is over" — only cursor 0 ends it.
  • "Redis remembers my cursor, so I must close the iteration" — there is no server-side state to close.
  • "Duplicates mean something is broken / my Redis is corrupted" — duplicates are a documented, expected outcome of rehashing.

context

resolving links…