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?