Transaction execution model in Redis - Time & Space Complexity

Time Complexity: Transaction execution model

O(n)

Understanding Time Complexity

When using Redis transactions, it is important to understand how the time to execute commands grows as more commands are added.

We want to know how the total work changes when the number of commands in a transaction increases.

Scenario Under Consideration

Analyze the time complexity of the following Redis transaction commands.

MULTI
SET key1 value1
INCR counter
GET key1
EXEC
    

This code starts a transaction, queues three commands, and then executes them all at once.

Identify Repeating Operations

Look for repeated actions inside the transaction.

• Primary operation: Executing each queued command in the transaction.
• How many times: Once for each command queued before EXEC.

How Execution Grows With Input

As you add more commands to the transaction, the total work grows with the number of commands.

Input Size (n)	Approx. Operations
10	10 commands executed
100	100 commands executed
1000	1000 commands executed

Pattern observation: The total execution time grows directly with the number of commands queued.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the transaction grows linearly with the number of commands inside it.

Common Mistake

[X] Wrong: "All commands inside a transaction run instantly together, so time does not grow with more commands."

[OK] Correct: Each command still needs to be executed one by one during EXEC, so more commands mean more work and more time.

Interview Connect

Understanding how Redis transactions scale helps you design efficient data operations and shows you can reason about performance in real systems.

Self-Check

"What if the transaction included commands that themselves take longer to run, like scanning many keys? How would that affect the time complexity?"

Practice

1. What is the purpose of the MULTI command in Redis transactions?

easy

A. To discard all queued commands in a transaction

B. To immediately execute all queued commands

C. To start a transaction and queue commands for atomic execution

D. To check the status of the current transaction

Solution

1. Step 1: Understand the role of MULTI

   The MULTI command starts a transaction and queues subsequent commands instead of executing them immediately.

2. Step 2: Differentiate MULTI from other commands

   EXEC runs the queued commands, DISCARD cancels them, and no command checks status directly.

3. Final Answer:

   To start a transaction and queue commands for atomic execution -> Option C

4. Quick Check:

   MULTI = start transaction [OK]

Hint: MULTI always starts queuing commands, not executing them [OK]

Common Mistakes:

• Confusing MULTI with EXEC
• Thinking MULTI executes commands immediately
• Assuming MULTI discards commands

2. Which of the following is the correct sequence to execute a Redis transaction?

easy

A. EXEC, MULTI, commands

B. commands, MULTI, EXEC

C. commands, EXEC, MULTI

D. MULTI, commands, EXEC

Solution

1. Step 1: Recall the transaction command order

   First, MULTI starts the transaction, then commands are queued, and finally EXEC runs them.

2. Step 2: Verify the sequence

   Only MULTI, commands, EXEC follows the correct order: MULTI, then commands, then EXEC.

3. Final Answer:

   MULTI, commands, EXEC -> Option D

4. Quick Check:

   Order = MULTI -> commands -> EXEC [OK]

Hint: MULTI starts, EXEC ends transaction execution [OK]

Common Mistakes:

• Starting with EXEC instead of MULTI
• Running commands before MULTI
• Mixing order of commands and EXEC

3. Consider the following Redis transaction commands:

MULTI
SET key1 value1
INCR counter
EXEC

What will be the result of the EXEC command if counter does not exist before the transaction?

medium

A. ["OK", "(error) counter is not an integer"]

B. ["OK", 1]

C. Syntax error

D. Transaction discarded

Solution

1. Step 1: Analyze commands in the transaction

   SET key1 value1 sets a string key, and INCR counter increments the counter key. If counter does not exist, Redis treats it as 0 before incrementing.

2. Step 2: Understand Redis transaction behavior

   Redis queues commands and executes them atomically. Since counter is missing, INCR will create it with value 1. Both commands succeed.

3. Final Answer:

   ["OK", 1] -> Option B

4. Quick Check:

   INCR missing key = 1 [OK]

Hint: INCR creates missing keys with value 1 [OK]

Common Mistakes:

• Expecting error if key is missing
• Thinking transaction rolls back on error
• Confusing syntax error with runtime error

4. You run this Redis transaction:

MULTI
SET key1 value1
INCR key1
EXEC

What is the expected outcome and why?

medium

A. EXEC returns an error for INCR because key1 is not an integer

B. Both commands succeed; key1 becomes 'value1' then incremented

C. Transaction is discarded due to type error

D. Only SET executes; INCR is ignored

Solution

1. Step 1: Examine commands and data types

   SET key1 value1 sets key1 to a string. INCR key1 expects an integer but key1 is a string.

2. Step 2: Understand Redis transaction error handling

   Redis queues commands and executes all on EXEC. It does not rollback on errors. INCR fails with a type error, but SET succeeds.

3. Final Answer:

   EXEC returns an error for INCR because key1 is not an integer -> Option A

4. Quick Check:

   Type error in transaction = error on EXEC [OK]

Hint: Redis transactions don't rollback on command errors [OK]

Common Mistakes:

• Assuming transaction rolls back on error
• Expecting INCR to convert string automatically
• Thinking only first command runs

5. You want to increment a counter only if a key lock does not exist, using Redis transactions. Which sequence correctly ensures atomicity?

hard

A. WATCH lock
MULTI
INCR counter
EXEC

B. MULTI
SET lock 1
INCR counter
EXEC

C. MULTI
INCR counter
GET lock
EXEC

D. MULTI
GET lock
INCR counter
EXEC

Solution

1. Step 1: Understand the need for atomic check and increment

   You must check if lock exists and increment counter only if it does not, atomically.

2. Step 2: Use WATCH to monitor lock

   WATCH lock watches the key for changes. If lock changes before EXEC, the transaction aborts, ensuring atomicity.

3. Step 3: MULTI queues commands and EXEC runs them if lock unchanged

   This sequence ensures the increment happens only if lock was not modified.

4. Final Answer:

   WATCH lock MULTI INCR counter EXEC -> Option A

5. Quick Check:

   WATCH + MULTI = atomic check and update [OK]

Hint: Use WATCH before MULTI to ensure atomic conditional updates [OK]

Common Mistakes:

• Not using WATCH for conditional logic
• Checking key inside MULTI without WATCH
• Assuming MULTI alone ensures atomic condition