EVALSHA for cached scripts in Redis - Time & Space Complexity

Time Complexity: EVALSHA for cached scripts

O(n)

Understanding Time Complexity

When using EVALSHA in Redis, we want to know how the time to run a cached script changes as the input grows.

We ask: How does the script execution time scale with the number of keys or arguments?

Scenario Under Consideration

Analyze the time complexity of this Redis EVALSHA usage.

# Assume script is already loaded and SHA1 hash is known
EVALSHA sha1hash numkeys key1 key2 ... arg1 arg2 ...

# Example:
EVALSHA abc123 2 user:1 user:2 100 200

# The script processes the keys and arguments passed.

This code runs a cached Lua script by its SHA1 hash, passing keys and arguments for processing.

Identify Repeating Operations

Look for repeated work inside the script triggered by EVALSHA.

• Primary operation: The Lua script processes each key and argument, often looping over them.
• How many times: Once per key or argument inside the script, depending on script logic.

How Execution Grows With Input

As the number of keys or arguments increases, the script does more work.

Input Size (n keys)	Approx. Operations
10	10 operations (one per key)
100	100 operations
1000	1000 operations

Pattern observation: The work grows roughly in direct proportion to the number of keys or arguments.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the cached script grows linearly with the number of keys or arguments it processes.

Common Mistake

[X] Wrong: "EVALSHA always runs instantly no matter how many keys or arguments it has."

[OK] Correct: The script still does work for each key or argument, so more inputs mean more time.

Interview Connect

Understanding how cached scripts scale helps you explain performance in real Redis use cases confidently.

Self-Check

"What if the script uses nested loops over keys and arguments? How would the time complexity change?"

Practice

1. What does the Redis command EVALSHA primarily do?

easy

A. Uploads a new Lua script to Redis cache

B. Deletes a script from the cache by its SHA1 hash

C. Lists all cached scripts by their SHA1 hashes

D. Runs a cached Lua script using its SHA1 hash

Solution

1. Step 1: Understand the purpose of EVALSHA

   EVALSHA runs a Lua script already stored in Redis cache using its SHA1 hash instead of sending the full script text.

2. Step 2: Compare with other script commands

   Other commands like SCRIPT LOAD upload scripts, SCRIPT FLUSH deletes scripts, but EVALSHA executes cached scripts.

3. Final Answer:

   Runs a cached Lua script using its SHA1 hash -> Option D

4. Quick Check:

   EVALSHA = run cached script [OK]

Hint: EVALSHA runs scripts by hash, not by full text [OK]

Common Mistakes:

• Confusing EVALSHA with SCRIPT LOAD
• Thinking EVALSHA deletes scripts
• Assuming EVALSHA lists scripts

2. Which of the following is the correct syntax for using EVALSHA in Redis?

easy

A. EVALSHA <numkeys> <sha1> [key1 key2 ...] [arg1 arg2 ...]

B. EVALSHA <sha1> <numkeys> [key1 key2 ...] [arg1 arg2 ...]

C. EVALSHA <sha1> [key1 key2 ...] <numkeys> [arg1 arg2 ...]

D. EVALSHA <script> <numkeys> [key1 key2 ...] [arg1 arg2 ...]

Solution

1. Step 1: Recall EVALSHA syntax

   The correct syntax is: EVALSHA followed by the SHA1 hash, then the number of keys, then the keys, then the arguments.

2. Step 2: Check option formats

   EVALSHA <sha1> <numkeys> [key1 key2 ...] [arg1 arg2 ...] matches the correct order. Options A, B, and C have wrong order or use script text instead of SHA1.

3. Final Answer:

   EVALSHA <sha1> <numkeys> [key1 key2 ...] [arg1 arg2 ...] -> Option B

4. Quick Check:

   Syntax = EVALSHA sha1 numkeys keys args [OK]

Hint: SHA1 hash comes first, then number of keys [OK]

Common Mistakes:

• Putting script text instead of SHA1 hash
• Mixing order of numkeys and keys
• Omitting number of keys

3. Given the following Redis commands executed in order:

127.0.0.1:6379> SCRIPT LOAD "return {KEYS[1],ARGV[1]}"
"a1b2c3d4e5f6g7h8i9j0"
127.0.0.1:6379> EVALSHA a1b2c3d4e5f6g7h8i9j0 1 mykey myarg

What will be the output of the EVALSHA command?

medium

A. ["mykey", "myarg"]

B. ["myarg", "mykey"]

C. Error: NOSCRIPT No matching script

D. ["a1b2c3d4e5f6g7h8i9j0", "myarg"]

Solution

1. Step 1: Understand SCRIPT LOAD output

   SCRIPT LOAD returns the SHA1 hash of the script, here "a1b2c3d4e5f6g7h8i9j0".

2. Step 2: Analyze EVALSHA call

   EVALSHA runs the cached script with 1 key: "mykey" and 1 argument: "myarg". The script returns {KEYS[1], ARGV[1]} so output is ["mykey", "myarg"].

3. Final Answer:

   ["mykey", "myarg"] -> Option A

4. Quick Check:

   Return keys[1], argv[1] = [mykey, myarg] [OK]

Hint: SCRIPT LOAD returns SHA1; EVALSHA uses keys then args [OK]

Common Mistakes:

• Confusing keys and args order
• Expecting error without loading script
• Using script text instead of SHA1

4. You run the command EVALSHA deadbeef 2 key1 key2 arg1 but get the error NOSCRIPT No matching script. What is the most likely cause?

medium

A. The number of keys argument should be 1, not 2

B. You provided too many keys for the script

C. The SHA1 hash 'deadbeef' is not loaded in Redis script cache

D. The script syntax is invalid

Solution

1. Step 1: Understand NOSCRIPT error meaning

   This error means Redis does not have a cached script matching the given SHA1 hash.

2. Step 2: Check command usage

   Since the hash 'deadbeef' is not loaded, Redis cannot run the script. Number of keys or syntax errors cause different errors.

3. Final Answer:

   The SHA1 hash 'deadbeef' is not loaded in Redis script cache -> Option C

4. Quick Check:

   NOSCRIPT = missing cached script [OK]

Hint: NOSCRIPT means script hash not cached yet [OK]

Common Mistakes:

• Assuming wrong number of keys causes NOSCRIPT
• Thinking syntax error causes NOSCRIPT
• Ignoring that script must be loaded first

5. You want to optimize a Redis Lua script execution by caching it. Which sequence correctly uses SCRIPT LOAD and EVALSHA to run the script multiple times with different keys and arguments?

hard

A. Load script once with SCRIPT LOAD, save SHA1, then call EVALSHA with SHA1, numkeys, keys, args each time

B. Call EVALSHA with script text each time, no need to load script

C. Use SCRIPT FLUSH before every EVALSHA to clear cache

D. Call EVALSHA with SHA1 but always set numkeys to 0

Solution

1. Step 1: Understand caching workflow

   First, SCRIPT LOAD uploads the script and returns its SHA1 hash. This hash is saved for reuse.

2. Step 2: Use EVALSHA for repeated execution

   Use EVALSHA with the saved SHA1, specifying number of keys, keys, and arguments to run the script efficiently multiple times.

3. Final Answer:

   Load script once with SCRIPT LOAD, save SHA1, then call EVALSHA with SHA1, numkeys, keys, args each time -> Option A

4. Quick Check:

   Load once, run many times with EVALSHA [OK]

Hint: Load script once, then run with EVALSHA and SHA1 [OK]

Common Mistakes:

• Calling EVALSHA with script text instead of SHA1
• Flushing scripts before every run
• Setting numkeys incorrectly