Why Lua scripts enable atomicity in Redis - Performance Analysis

Time Complexity: Why Lua scripts enable atomicity

O(n)

Understanding Time Complexity

When using Lua scripts in Redis, it's important to understand how the time to run the script changes as the script does more work.

We want to see how the script's execution time grows when it processes more data or commands.

Scenario Under Consideration

Analyze the time complexity of this Lua script in Redis.

local count = redis.call('LLEN', KEYS[1])
for i = 1, count do
  local item = redis.call('LPOP', KEYS[1])
  redis.call('RPUSH', KEYS[2], item)
end
return count
    

This script moves all items from one list to another, one by one, inside a single atomic operation.

Identify Repeating Operations

Look for repeated actions inside the script.

• Primary operation: Loop that pops an item from one list and pushes it to another.
• How many times: Once for each item in the source list.

How Execution Grows With Input

The script does one pop and one push for every item in the list.

Input Size (n)	Approx. Operations
10	20 (10 pops + 10 pushes)
100	200 (100 pops + 100 pushes)
1000	2000 (1000 pops + 1000 pushes)

Pattern observation: The number of operations grows directly with the number of items.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the script grows in a straight line as the list gets longer.

Common Mistake

[X] Wrong: "Lua scripts run instantly no matter how much work they do."

[OK] Correct: The script still does work for each item, so more items mean more time needed.

Interview Connect

Understanding how Lua scripts run helps you explain why atomic operations can still take longer with more data, showing you grasp both correctness and performance.

Self-Check

"What if the script used a Redis command that processes all items at once instead of looping? How would the time complexity change?"