skip to content

In Redis, what actually happens when you run the KEYS command with a glob pattern against a production database with millions of keys, and what should you use instead?

level: juniorimportance: must knowfreq 70%

answer

  1. KEYS = O(total keys), one shot
  2. commands run serially → everyone waits
  3. pattern narrows the reply, not the scan
  4. huge single reply = memory + network spike
  5. SCAN cursor batches; redis-cli --scan

basics

~20 s

KEYS visits every key in the database in a single command, O(N), and Redis executes commands one at a time — so every other client waits until it finishes, potentially seconds. Use SCAN, which iterates the same keyspace in small cursor-based batches.

solid answer

~50 s

`KEYS pattern` is **O(N) in the number of keys in the database**, not in the number of matches: Redis walks the entire top-level dictionary and glob-matches every key name. Because Redis executes commands serially, that walk is not interleaved with anything — a 10-million-key database can stall the whole instance for hundreds of milliseconds to seconds. Every other client sees that as latency; replication and health probes are delayed too, which in a Sentinel or Cluster setup can even trigger a spurious failover. There is a second cost: the whole match list is materialised into one reply, so a large result also spikes memory and network. The replacement is `SCAN`: `SCAN <cursor> [MATCH pattern] [COUNT n]` returns a batch plus the next cursor, so the O(N) work is split across many short commands that interleave with normal traffic. You trade guarantees for it — SCAN may return duplicates and gives no point-in-time snapshot. `redis-cli --scan --pattern 'x:*'` runs that loop for you.

code

text · 14 lines
text
# BAD: one O(N) command, blocks the whole instance
redis-cli KEYS 'session:*'

# GOOD: cursor loop, many short commands
redis-cli --scan --pattern 'session:*'

# The same loop by hand
127.0.0.1:6379> SCAN 0 MATCH session:* COUNT 100
1) "3072"            # next cursor
2) 1) "session:a1"
   2) "session:b7"
127.0.0.1:6379> SCAN 3072 MATCH session:* COUNT 100
1) "0"               # cursor 0 => iteration complete
2) 1) "session:c9"

go deeper

for a junior

Say it plainly: KEYS looks at every key, Redis runs one command at a time, so it freezes the server; use SCAN or redis-cli --scan instead.

for a middle

Add the complexity statement (O(number of keys in the DB), not matches), note that MATCH does not reduce the traversal, and describe the SCAN cursor loop and its termination condition.

for a senior

Talk about blast radius — client-wide latency, replication stream stalled, health probes timing out into a spurious failover — plus the reply-size/memory cost, and the safe operational recipe (SCAN with a moderate COUNT, batched idempotent actions).

for a principal

Frame scanning as an operational escape hatch and argue for designs that remove the need: maintained index sets or sorted sets, per-tenant logical databases droppable with FLUSHDB ASYNC, TTL-driven expiry, and guardrails such as disabling KEYS via ACL/rename-command on production instances.

## What KEYS does `KEYS <pattern>` walks the entire top-level hash table of the currently selected database, glob-matches every key **name** against the pattern, and returns all matches in one array reply. Its documented complexity is **O(N) where N is the number of keys in the database** — not the number of keys that match. Adding a narrower pattern reduces the size of the reply, never the amount of scanning. ## Why this is worse in Redis than in a typical database Redis processes client commands serially: one command runs to completion before the next one starts. There is no per-command concurrency to hide a slow command behind. So a `KEYS` that takes 1.5 seconds does not cost 1.5 seconds to *one* client — it adds up to 1.5 seconds of latency to *every* client connected to that instance, plus everything queued behind them. As a rough order of magnitude, plain key-name matching runs on the order of a few million keys per second, so a 10M-key instance is comfortably in "seconds of full stop" territory. ## The second cost: the reply itself All matching key names are assembled into the client output buffer before anything is sent. A million keys averaging 40 bytes is a ~40 MB reply that must be allocated inside the server, copied, and pushed over the network. On an instance already near `maxmemory` that allocation alone can push it into eviction or an out-of-memory condition, and slow consumers can be disconnected by `client-output-buffer-limit`. ## Collateral damage while the loop is blocked While the event loop is inside `KEYS`, Redis is not doing anything else: it is not feeding the replication stream, not answering `PING` from Sentinel or from cluster peers, not accepting connections. That is how a "harmless read-only debug command" turns into an incident — application timeouts, retry storms, and in Sentinel/Cluster deployments, a health-check timeout that promotes a replica while the master is perfectly healthy but busy. ## The alternative: SCAN `SCAN` is a cursor-based iterator over the same keyspace: `SCAN 0` returns `(next-cursor, batch-of-keys)`, and you call it again with the returned cursor until the cursor comes back as `0`. Each individual call does a small, bounded amount of work (roughly `COUNT` buckets, default 10), so the total O(N) cost is chopped into many short commands with other clients' traffic interleaved between them. Total work is still O(N) — you have not made it cheaper, you have made it **non-blocking in practice**. What you give up: `SCAN` provides no snapshot. The same key can be returned more than once, keys created or deleted during the iteration may or may not appear, and a key returned may already be gone by the time you act on it. For the usual jobs — bulk delete, re-index, audit — that is fine, because those actions are idempotent. ## Related traps in the same family `KEYS` is the most famous member of a family of single-shot O(N) commands: `SMEMBERS`/`HGETALL`/`LRANGE 0 -1` on a collection with millions of elements, `FLUSHALL` (synchronous) on a big database, `DEL` of one enormous collection. The mitigation shape is always the same: iterate in batches (`SSCAN`/`HSCAN`/`ZSCAN`), or use the asynchronous variants (`UNLINK`, `FLUSHALL ASYNC`). ## Better still: design so you never scan Scanning is a recovery tool, not an access path. If you routinely need "all keys for tenant 42", maintain the index yourself: `SADD tenant:42:keys <key>` when you create the key, and read the set directly — O(1) lookup instead of O(N) traversal. Sorted sets serve the same role for ordered/time-ranged lookups. Segregating a disposable dataset into its own logical database (so it can be dropped with `FLUSHDB ASYNC`) or giving keys TTLs are the other two ways the question disappears. ## When KEYS is defensible A developer laptop, a test fixture, a keyspace of a few thousand keys, or a dedicated offline replica nobody serves traffic from. Even there it is worth using `SCAN` out of habit, because the code that ships to production is usually the code that was written on the laptop. ## What an interviewer is listening for Three things: the complexity is O(total keys), the consequence is a server-wide stall because commands run one at a time, and the replacement is cursor-based `SCAN`. A bonus point for noticing that `MATCH`/pattern narrowing does not reduce the traversal cost.

  • Is running KEYS on a read replica a safe workaround?
    No. The replica has its own single execution thread, so KEYS blocks it exactly the same way — any read traffic served from that replica stalls. It also delays the replica's processing of the replication stream, so replication lag grows during the command and health probes to that node can time out. It is only acceptable on a node that serves nobody and is not part of a failover set.
  • Does adding a very selective MATCH pattern make KEYS cheap?
    No. Redis still walks every key in the database and applies the glob to each name; the pattern only decides which names make it into the reply. It reduces reply size, memory for the reply, and network, but the traversal cost — the part that blocks the server — is unchanged. The same is true of MATCH on SCAN.
  • If SCAN is also O(N) in total, what have you actually gained?
    You have converted one long command into many short ones. Total CPU work is similar, but no single command holds the execution thread for long, so other clients' latency stays flat and replication keeps flowing. You also cap reply size per call. The cost is weaker semantics: duplicates are possible and there is no snapshot.

KEYS is walking into a library and reading every spine before answering; SCAN is reading one shelf, answering the phone, then the next shelf.

saying these in an interview costs you the question

  • "KEYS is fine, Redis is in-memory so it's instant" — memory speed does not make an O(N) walk of 10M keys free.
  • "KEYS is O(1) because keys live in a hash table" — hash lookup is O(1); enumerating and pattern-matching everything is not.
  • "A narrow pattern like user:1234:* makes KEYS cheap" — filtering happens after visiting every key.
  • "SCAN takes a lock / gives me a consistent snapshot" — SCAN takes no lock and gives no snapshot; duplicates are expected.
  • "I'll just stop when SCAN returns an empty batch" — empty batches are normal mid-iteration; only cursor 0 means done.

context

resolving links…