DISCARD to abort in Redis - Time & Space Complexity

Time Complexity: DISCARD to abort

O(n)

Understanding Time Complexity

When using Redis transactions, it's important to know how the time cost changes when you abort a transaction with DISCARD.

We want to understand how DISCARD affects the work Redis does as the transaction size grows.

Scenario Under Consideration

Analyze the time complexity of the following Redis transaction with DISCARD.

MULTI
SET key1 value1
SET key2 value2
... (more commands) ...
DISCARD
    

This code starts a transaction, queues several commands, then aborts all queued commands using DISCARD.

Identify Repeating Operations

Look for repeated actions inside the transaction before DISCARD.

• Primary operation: Queuing each command inside the transaction.
• How many times: Once per command queued before DISCARD.

How Execution Grows With Input

As you add more commands before DISCARD, Redis queues more commands.

Input Size (n)	Approx. Operations
10	Queue 10 commands, then DISCARD clears all
100	Queue 100 commands, then DISCARD clears all
1000	Queue 1000 commands, then DISCARD clears all

Pattern observation: The work to queue commands grows with the number of commands, but DISCARD clears all queued commands in a single step.

Final Time Complexity

Time Complexity: O(n)

This means the time to abort with DISCARD grows linearly with the number of commands queued in the transaction.

Common Mistake

[X] Wrong: "DISCARD instantly cancels the transaction with no extra work regardless of size."

[OK] Correct: Redis must clear all queued commands, so the time depends on how many commands were queued before DISCARD.

Interview Connect

Understanding how DISCARD works helps you reason about transaction costs and error handling in Redis, a useful skill for real-world database tasks.

Self-Check

"What if we replaced DISCARD with EXEC? How would the time complexity change?"

Practice

1. What does the DISCARD command do in a Redis transaction?

easy

A. It starts a new transaction.

B. It cancels all commands queued in the current transaction.

C. It saves the current database state to disk.

D. It executes all commands queued in the current transaction.

Solution

1. Step 1: Understand the role of DISCARD in Redis transactions

   DISCARD is used to cancel all commands queued after MULTI before EXEC is called.

2. Step 2: Compare DISCARD with other transaction commands

   Unlike EXEC which executes queued commands, DISCARD aborts them, so no changes happen.

3. Final Answer:

   It cancels all commands queued in the current transaction. -> Option B

4. Quick Check:

   DISCARD cancels queued commands = D [OK]

Hint: DISCARD always cancels queued commands without executing them [OK]

Common Mistakes:

• Confusing DISCARD with EXEC which executes commands
• Thinking DISCARD saves changes instead of aborting
• Assuming DISCARD starts a transaction

2. Which of the following is the correct syntax to abort a Redis transaction after MULTI?

easy

A. EXEC

B. ABORT

C. ROLLBACK

D. DISCARD

Solution

1. Step 1: Recall Redis transaction commands

   After MULTI, you can either execute with EXEC or abort with DISCARD.

2. Step 2: Identify the correct abort command

   DISCARD is the official command to abort queued commands; ABORT and ROLLBACK do not exist in Redis.

3. Final Answer:

   DISCARD -> Option D

4. Quick Check:

   Abort command after MULTI = DISCARD [OK]

Hint: Use DISCARD to abort, EXEC to execute queued commands [OK]

Common Mistakes:

• Using EXEC instead of DISCARD to abort
• Typing ABORT or ROLLBACK which are invalid Redis commands
• Confusing DISCARD with starting a transaction

3. Consider the following Redis commands executed in order:

MULTI
SET key1 value1
DISCARD
GET key1

What will be the output of the GET key1 command?

medium

A. nil

B. "value1"

C. Error: EXEC without MULTI

D. "key1"

Solution

1. Step 1: Analyze the transaction commands

   After MULTI, SET key1 value1 is queued but not executed yet.

2. Step 2: Effect of DISCARD on queued commands

   DISCARD aborts the transaction, so SET key1 value1 is never applied.

3. Step 3: Result of GET key1

   Since key1 was never set, GET key1 returns nil.

4. Final Answer:

   nil -> Option A

5. Quick Check:

   DISCARD aborts SET, so GET returns nil [OK]

Hint: DISCARD cancels queued SET, so key remains unset [OK]

Common Mistakes:

• Assuming SET runs immediately after MULTI
• Expecting EXEC to run automatically without calling it
• Confusing output with command names

4. You run the following Redis commands:

MULTI
SET key1 value1
DISCARD
EXEC

What will happen when you run EXEC after DISCARD?

medium

A. EXEC returns nil without error

B. EXEC runs and applies SET key1 value1

C. EXEC returns an error because no transaction is active

D. EXEC starts a new transaction

Solution

1. Step 1: Understand DISCARD effect on transaction state

   DISCARD aborts the transaction and clears the queue, ending the transaction state.

2. Step 2: Behavior of EXEC after DISCARD

   Since no transaction is active after DISCARD, calling EXEC causes an error because EXEC requires an active MULTI block.

3. Final Answer:

   EXEC returns an error because no transaction is active -> Option C

4. Quick Check:

   EXEC after DISCARD errors due to no active transaction [OK]

Hint: After DISCARD, no active transaction; EXEC causes error [OK]

Common Mistakes:

• Expecting EXEC to run queued commands after DISCARD
• Thinking EXEC silently returns nil after DISCARD
• Assuming EXEC starts a new transaction

5. You want to safely update multiple keys in Redis but abort if a condition fails. Which sequence correctly uses DISCARD to abort the transaction if the condition is false?

WATCH key1
MULTI
IF condition IS FALSE
DISCARD
ELSE
SET key1 newValue
SET key2 newValue2
EXEC
END

What is the correct way to use DISCARD here?

hard

A. Call DISCARD immediately after MULTI if condition is false, skipping EXEC.

B. Call DISCARD after EXEC to undo changes if condition is false.

C. Call DISCARD before WATCH to abort the transaction.

D. Call DISCARD after SET commands to cancel them.

Solution

1. Step 1: Understand transaction flow with WATCH and MULTI

   WATCH monitors keys, MULTI starts queuing commands, EXEC executes them.

2. Step 2: Use DISCARD to abort before EXEC if condition fails

   If the condition is false, DISCARD cancels queued commands before EXEC runs, preventing changes.

3. Step 3: Why other options are incorrect

   DISCARD after EXEC or after SET commands is invalid; DISCARD before WATCH does not abort a transaction.

4. Final Answer:

   Call DISCARD immediately after MULTI if condition is false, skipping EXEC. -> Option A

5. Quick Check:

   DISCARD aborts queued commands before EXEC [OK]

Hint: Use DISCARD before EXEC to abort if condition fails [OK]

Common Mistakes:

• Calling DISCARD after EXEC which is too late
• Trying to DISCARD before WATCH which does nothing
• Assuming DISCARD cancels commands after they run