SCAN for safe key iteration in Redis - Time & Space Complexity

Time Complexity: SCAN for safe key iteration

O(n)

Understanding Time Complexity

When working with many keys in Redis, it's important to know how long it takes to look through them safely.

We want to understand how the time to scan keys grows as the number of keys increases.

Scenario Under Consideration

Analyze the time complexity of the following Redis SCAN command usage.

    local cursor = "0"
    repeat
      local result = redis.call('SCAN', cursor, 'COUNT', 100)
      cursor = result[1]
      local keys = result[2]
      -- process keys here
    until cursor == "0"
    

This code safely iterates over all keys in the database in small batches without blocking Redis.

Identify Repeating Operations

Look for repeated actions in the code.

• Primary operation: Calling SCAN repeatedly to get batches of keys.
• How many times: The number of calls depends on total keys divided by batch size.

How Execution Grows With Input

As the number of keys grows, the number of SCAN calls grows roughly in proportion.

Input Size (n)	Approx. Operations
10	About 1 call (small number of keys)
100	About 1 call (batch size covers all keys)
1000	About 10 calls (100 keys per call)

Pattern observation: The number of SCAN calls grows linearly with the number of keys divided by batch size.

Final Time Complexity

Time Complexity: O(n)

This means the time to scan all keys grows roughly in direct proportion to how many keys there are.

Common Mistake

[X] Wrong: "SCAN returns all keys in one call quickly."

[OK] Correct: SCAN returns keys in small batches to avoid blocking, so multiple calls are needed to get all keys.

Interview Connect

Understanding how SCAN works and its time behavior shows you can handle large data safely without slowing down the system.

Self-Check

What if we changed the COUNT value to a much larger number? How would the time complexity change?

Practice

1. What is the main advantage of using SCAN over KEYS in Redis for iterating keys?

easy

A. SCAN returns all keys at once for faster access.

B. SCAN only works with sorted sets.

C. SCAN deletes keys while iterating.

D. SCAN does not block Redis and returns keys in batches.

Solution

1. Step 1: Understand KEYS behavior

   KEYS returns all matching keys at once and blocks Redis during execution.

2. Step 2: Understand SCAN behavior

   SCAN returns keys in small batches without blocking Redis, allowing safe iteration.

3. Final Answer:

   SCAN does not block Redis and returns keys in batches. -> Option D

4. Quick Check:

   Safe iteration = SCAN non-blocking [OK]

Hint: Remember: SCAN is non-blocking, KEYS blocks [OK]

Common Mistakes:

• Thinking SCAN returns all keys at once
• Confusing SCAN with key deletion
• Assuming SCAN only works on sorted sets

2. Which of the following is the correct syntax to start a SCAN iteration from the beginning in Redis CLI?

easy

A. SCAN 1

B. SCAN 0

C. SCAN *

D. SCAN start

Solution

1. Step 1: Identify the starting cursor for SCAN

   The SCAN command requires a cursor argument; starting cursor is always 0.

2. Step 2: Check options for correct cursor

   SCAN 0 starts iteration from the beginning; other options are invalid.

3. Final Answer:

   SCAN 0 -> Option B

4. Quick Check:

   Start cursor = 0 [OK]

Hint: Always start SCAN with cursor 0 [OK]

Common Mistakes:

• Starting with cursor 1 instead of 0
• Using wildcard * as cursor
• Using invalid strings like 'start'

3. Given the following Redis commands executed sequentially, what will be the output of the last SCAN command?

SET user:1 Alice
SET user:2 Bob
SET admin:1 Carol
SCAN 0 MATCH user:*

medium

A. [cursor, ["user:1", "user:2"]]

B. [0, ["user:1", "user:2"]]

C. [cursor, ["user:1", "user:2", "admin:1"]]

D. [0, ["admin:1"]]

Solution

1. Step 1: Understand SCAN with MATCH

   The MATCH user:* filters keys starting with 'user:'. So keys 'user:1' and 'user:2' match; 'admin:1' does not.

2. Step 2: Understand SCAN output format

   SCAN returns a two-element array: a cursor (string) and a list of keys matching the pattern in this batch. Cursor is not necessarily 0 unless iteration is complete.

3. Final Answer:

   [cursor, ["user:1", "user:2"]] -> Option A

4. Quick Check:

   Filtered keys = user keys only [OK]

Hint: MATCH filters keys; cursor is a string, not always 0 [OK]

Common Mistakes:

• Expecting cursor 0 on first SCAN call
• Including keys not matching pattern
• Confusing cursor with count

4. You wrote this Redis command to iterate keys safely:

SCAN 0 MATCH user:*

But you notice it returns only a partial list of keys matching the pattern. What is the likely mistake?

medium

A. Not repeating SCAN with the returned cursor until it returns 0.

B. Using MATCH with an incorrect pattern.

C. Starting SCAN with cursor 1 instead of 0.

D. Using COUNT option with a value too high.

Solution

1. Step 1: Understand SCAN iteration process

   SCAN returns a cursor and a batch of keys; to get all keys, you must repeat SCAN with the new cursor until it returns 0.

2. Step 2: Identify the mistake

   Running SCAN 0 MATCH user:* only once returns partial keys; not looping causes incomplete results.

3. Final Answer:

   Not repeating SCAN with the returned cursor until it returns 0. -> Option A

4. Quick Check:

   Repeat SCAN until cursor 0 [OK]

Hint: Always loop SCAN calls until cursor returns 0 [OK]

Common Mistakes:

• Expecting all keys in one SCAN call
• Misusing MATCH pattern syntax
• Starting with wrong cursor

5. You want to safely iterate all keys starting with session: in Redis but avoid blocking the server. You also want to limit each batch to about 10 keys. Which command sequence correctly achieves this?

hard

A. Use SCAN 0 COUNT 10 without MATCH.

B. Run KEYS session:* once to get all keys.

C. Repeat SCAN cursor MATCH session:* COUNT 10 until cursor returns 0.

D. Use SCAN 0 MATCH session:* once without COUNT.

Solution

1. Step 1: Use SCAN with MATCH and COUNT

   To filter keys starting with 'session:' and limit batch size, use MATCH session:* and COUNT 10.

2. Step 2: Repeat SCAN calls until cursor is 0

   Iterate by passing the returned cursor each time until it returns 0 to get all keys safely without blocking.

3. Final Answer:

   Repeat SCAN cursor MATCH session:* COUNT 10 until cursor returns 0. -> Option C

4. Quick Check:

   Safe iteration + filter + batch size = Repeat SCAN cursor MATCH session:* COUNT 10 until cursor returns 0. [OK]

Hint: Combine MATCH and COUNT, loop until cursor 0 [OK]

Common Mistakes:

• Using KEYS which blocks Redis
• Not looping SCAN calls
• Omitting MATCH or COUNT when needed