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?"

Practice

1. Why do Lua scripts in Redis ensure atomicity?

easy

A. Because they run as a single, uninterruptible operation

B. Because they use multiple threads simultaneously

C. Because they store data in separate databases

D. Because they execute commands randomly

Solution

1. Step 1: Understand Lua script execution in Redis

   Lua scripts run all commands inside them as one single operation without interruption.

2. Step 2: Connect atomicity to uninterrupted execution

   This uninterrupted execution means no other commands can interfere, ensuring atomicity.

3. Final Answer:

   Because they run as a single, uninterruptible operation -> Option A

4. Quick Check:

   Atomicity = single uninterruptible operation [OK]

Hint: Atomicity means no interruptions during script run [OK]

Common Mistakes:

• Thinking Lua scripts run in multiple threads
• Believing Lua scripts split commands across databases
• Assuming commands execute randomly

2. Which of the following is the correct way to start a Lua script in Redis?

easy

A. EVAL 'return redis.call("GET", "key")' 1 key

B. RUN 'return redis.call("GET", "key")' 1 key

C. EXECUTE 'return redis.call("GET", "key")' 1 key

D. SCRIPT 'return redis.call("GET", "key")' 1 key

Solution

1. Step 1: Identify Redis command to run Lua scripts

   Redis uses the EVAL command to run Lua scripts.

2. Step 2: Check syntax correctness

   EVAL 'script' number_of_keys keys... is the correct syntax.

3. Final Answer:

   EVAL 'return redis.call("GET", "key")' 1 key -> Option A

4. Quick Check:

   Use EVAL to run Lua scripts [OK]

Hint: Lua scripts start with EVAL command in Redis [OK]

Common Mistakes:

• Using RUN instead of EVAL
• Using EXECUTE or SCRIPT commands incorrectly
• Missing the number of keys argument

3. What will be the output of this Lua script run in Redis?

EVAL "return redis.call('INCR', KEYS[1])" 1 counter

Assuming the key 'counter' has value 5 before running.

medium

A. nil

B. 5

C. Error

D. 6

Solution

1. Step 1: Understand the INCR command effect

   INCR increases the integer value stored at the key by 1 and returns the new value.

2. Step 2: Apply INCR to current value 5

   Incrementing 5 by 1 results in 6, which is returned by the script.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   INCR(5) = 6 [OK]

Hint: INCR returns incremented value, not original [OK]

Common Mistakes:

• Thinking INCR returns old value
• Expecting nil if key exists
• Assuming script causes error

4. You wrote this Lua script for Redis:

EVAL "redis.call('SET', KEYS[1], ARGV[1])" 1 mykey newvalue

But it does not return any value. What is the problem?

medium

A. Lua scripts cannot use redis.call

B. Wrong number of keys argument

C. Missing 'return' before redis.call

D. Incorrect key name format

Solution

1. Step 1: Check Lua script return statement

   Lua scripts must return a value explicitly to get output from EVAL.

2. Step 2: Identify missing return

   The script calls redis.call but does not return its result, so output is nil.

3. Final Answer:

   Missing 'return' before redis.call -> Option C

4. Quick Check:

   Lua scripts need 'return' for output [OK]

Hint: Always use 'return' to get Lua script output [OK]

Common Mistakes:

• Assuming redis.call auto-returns value
• Incorrect keys count causing error
• Believing redis.call is disallowed

5. You want to increment two counters atomically in Redis using Lua. Which script ensures both increments happen together without interference?

EVAL "redis.call('INCR', KEYS[1]); redis.call('INCR', KEYS[2]); return {redis.call('GET', KEYS[1]), redis.call('GET', KEYS[2])}" 2 counter1 counter2

hard

A. This script is not atomic because it uses multiple redis.call commands

B. This script is atomic because Lua scripts run without interruption

C. This script is atomic only if wrapped in MULTI/EXEC

D. This script is not atomic because it returns multiple values

Solution

1. Step 1: Understand Lua script atomicity in Redis

   All commands inside a Lua script run as one atomic operation, no matter how many redis.call commands are used.

2. Step 2: Confirm script increments both counters atomically

   Both INCR commands run together without interruption, ensuring atomicity.

3. Final Answer:

   This script is atomic because Lua scripts run without interruption -> Option B

4. Quick Check:

   Multiple redis.call in Lua script = atomic [OK]

Hint: Multiple commands in Lua script run atomically [OK]

Common Mistakes:

• Thinking multiple redis.call break atomicity
• Believing MULTI/EXEC needed inside Lua
• Assuming returning multiple values breaks atomicity