Time Complexity: EVALSHA for cached scripts
O(n)
0
0
EVALSHA for cached scripts in Redis - Time & Space Complexity
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?"