Script loading and caching in Redis - Time & Space Complexity

Time Complexity: Script loading and caching

O(n)

Understanding Time Complexity

When using Redis scripts, it is important to understand how loading and caching affect performance.

We want to know how the time to run scripts changes as we add more scripts or run them multiple times.

Scenario Under Consideration

Analyze the time complexity of loading and running a Redis Lua script with caching.

    -- Load script and get SHA1 hash
    local sha = redis.sha1hex(script)
    
    -- Check if script is cached
    if redis.call('SCRIPT', 'EXISTS', sha)[1] == 0 then
      redis.call('SCRIPT', 'LOAD', script)
    end
    
    -- Run the script by SHA
    redis.call('EVALSHA', sha, keys_count, unpack(keys_and_args))
    

This code loads a Lua script into Redis if not already cached, then runs it by its hash.

Identify Repeating Operations

Look for repeated checks or calls that affect performance.

• Primary operation: Checking if the script SHA exists and loading it if missing.
• How many times: Once per unique script; running the script by SHA can happen many times without reloading.

How Execution Grows With Input

As the number of unique scripts grows, the initial load cost grows linearly.

Number of Unique Scripts (n)	Approx. Load Checks and Loads
10	10 checks, up to 10 loads
100	100 checks, up to 100 loads
1000	1000 checks, up to 1000 loads

Once loaded, running scripts by SHA is fast and does not grow with n.

Final Time Complexity

Time Complexity: O(n)

This means the time to load scripts grows linearly with the number of unique scripts, but running cached scripts is fast.

Common Mistake

[X] Wrong: "Running a cached script takes as long as loading it every time."

[OK] Correct: Once a script is cached, running it by SHA is quick and does not repeat the loading cost.

Interview Connect

Understanding how caching scripts affects performance shows you can reason about efficiency in real systems.

Self-Check

What if we skipped the existence check and always loaded the script before running? How would the time complexity change?

Practice

1. What does the SCRIPT LOAD command do in Redis?

easy

A. It executes a Lua script immediately without caching.

B. It lists all cached Lua scripts in Redis.

C. It deletes a cached Lua script by its SHA1 hash.

D. It loads a Lua script into Redis and returns its SHA1 hash.

Solution

1. Step 1: Understand SCRIPT LOAD purpose

   The SCRIPT LOAD command stores a Lua script in Redis and returns a unique SHA1 hash for it.

2. Step 2: Differentiate from other commands

   Unlike EVAL, SCRIPT LOAD does not execute the script but prepares it for later use.

3. Final Answer:

   It loads a Lua script into Redis and returns its SHA1 hash. -> Option D

4. Quick Check:

   SCRIPT LOAD returns SHA1 hash [OK]

Hint: SCRIPT LOAD stores script and returns SHA1 hash [OK]

Common Mistakes:

• Confusing SCRIPT LOAD with EVAL which runs scripts immediately
• Thinking SCRIPT LOAD deletes scripts
• Assuming SCRIPT LOAD lists scripts

2. Which of the following is the correct syntax to load a Lua script into Redis and get its SHA1 hash?

easy

A. EVALSHA "return redis.call('PING')" 0

B. SCRIPT LOAD "return redis.call('PING')"

C. SCRIPT EXECUTE "return redis.call('PING')"

D. LOAD SCRIPT "return redis.call('PING')"

Solution

1. Step 1: Identify correct command syntax

   The correct command to load a script is SCRIPT LOAD followed by the Lua script as a string.

2. Step 2: Eliminate incorrect options

   EVALSHA runs a cached script by SHA, SCRIPT EXECUTE and LOAD SCRIPT are invalid Redis commands.

3. Final Answer:

   SCRIPT LOAD "return redis.call('PING')" -> Option B

4. Quick Check:

   SCRIPT LOAD syntax is SCRIPT LOAD "script" [OK]

Hint: SCRIPT LOAD "script" loads script and returns SHA1 [OK]

Common Mistakes:

• Using EVALSHA instead of SCRIPT LOAD to load script
• Using non-existent commands like SCRIPT EXECUTE
• Incorrect command order or missing quotes

3. Given the following commands executed in Redis:

SCRIPT LOAD "return ARGV[1]"
EVALSHA <sha1> 0 Hello

What will be the output of the EVALSHA command?

medium

A. 0

B. An error because the script is not cached

C. "Hello"

D. The SHA1 hash string

Solution

1. Step 1: Understand SCRIPT LOAD and EVALSHA interaction

   SCRIPT LOAD stores the script and returns its SHA1 hash. EVALSHA runs the cached script using that SHA1.

2. Step 2: Analyze the script and arguments

   The script returns ARGV[1], and EVALSHA is called with argument "Hello" as ARGV[1]. So output is "Hello".

3. Final Answer:

   "Hello" -> Option C

4. Quick Check:

   EVALSHA runs cached script returning ARGV[1] = "Hello" [OK]

Hint: EVALSHA runs cached script with ARGV arguments [OK]

Common Mistakes:

• Confusing SCRIPT LOAD output with EVALSHA output
• Forgetting to pass correct number of keys (0 here)
• Expecting SHA1 hash as output of EVALSHA

4. You run the following Redis commands:

SCRIPT LOAD "return redis.call('GET', KEYS[1])"
EVALSHA <sha1> 1 mykey

But you get an error: NOSCRIPT No matching script. Please use EVAL. What is the most likely cause?

medium

A. The SHA1 hash used in EVALSHA is incorrect or from a different script.

B. The KEYS argument count is wrong; it should be 0 instead of 1.

C. SCRIPT LOAD does not cache scripts, so EVALSHA fails.

D. Redis does not support EVALSHA for GET commands.

Solution

1. Step 1: Understand NOSCRIPT error meaning

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

2. Step 2: Identify common causes

   Most often, the SHA1 hash passed to EVALSHA is wrong or from a different script than loaded.

3. Final Answer:

   The SHA1 hash used in EVALSHA is incorrect or from a different script. -> Option A

4. Quick Check:

   NOSCRIPT error means SHA1 mismatch [OK]

Hint: NOSCRIPT means SHA1 hash mismatch or missing script [OK]

Common Mistakes:

• Assuming KEYS count is always zero
• Thinking SCRIPT LOAD does not cache scripts
• Believing Redis disallows EVALSHA for certain commands

5. You want to optimize Redis script execution by caching a Lua script that increments a key's value by a given amount. Which sequence of commands correctly loads and runs this script multiple times efficiently?

hard

A. Use SCRIPT LOAD to get SHA1, then call EVALSHA with the SHA1 and arguments for each increment.

B. Use EVAL with the full script every time you want to increment the key.

C. Use SCRIPT FLUSH before every increment to clear cached scripts, then EVALSHA.

D. Use SCRIPT LOAD once, then call EVAL with the full script every time.

Solution

1. Step 1: Understand caching for efficiency

   Loading the script once with SCRIPT LOAD caches it and returns SHA1 for reuse.

2. Step 2: Use EVALSHA for repeated execution

   Calling EVALSHA with the SHA1 runs the cached script efficiently without sending full script each time.

3. Step 3: Eliminate inefficient options

   Using EVAL every time sends full script, SCRIPT FLUSH clears cache unnecessarily.

4. Final Answer:

   Use SCRIPT LOAD to get SHA1, then call EVALSHA with the SHA1 and arguments for each increment. -> Option A

5. Quick Check:

   Cache script once, run with EVALSHA repeatedly [OK]

Hint: Load once with SCRIPT LOAD, run many times with EVALSHA [OK]

Common Mistakes:

• Using EVAL repeatedly instead of EVALSHA
• Flushing scripts unnecessarily with SCRIPT FLUSH
• Reloading script before every execution