Time Complexity: Multi-key transactions for consistency
O(n)
0
0
Multi-key transactions for consistency in Redis - Time & Space Complexity
Understanding Time Complexity
When using multi-key transactions in Redis, it is important to understand how the time to complete the transaction changes as more keys are involved.
We want to know how the number of keys affects the work Redis does to keep data consistent.
Scenario Under Consideration
Analyze the time complexity of the following Redis transaction code.
MULTI
SET key1 value1
SET key2 value2
SET key3 value3
EXEC
This code starts a transaction, sets values for three keys, and then executes all commands atomically.
Identify Repeating Operations
Look for repeated actions inside the transaction.
- Primary operation: Setting a key-value pair with SET command.
- How many times: Once for each key involved in the transaction.
How Execution Grows With Input
As the number of keys increases, Redis performs more SET operations inside the transaction.
| Input Size (n) | Approx. Operations |
|---|---|
| 3 | 3 SET commands inside one transaction |
| 10 | 10 SET commands inside one transaction |
| 100 | 100 SET commands inside one transaction |
Pattern observation: The total work grows directly with the number of keys you update.
Final Time Complexity
Time Complexity: O(n)
This means the time to complete the transaction grows linearly with the number of keys involved.
Common Mistake
[X] Wrong: "Using MULTI/EXEC makes all key updates happen instantly, no matter how many keys."
[OK] Correct: Even though the commands run atomically, Redis still processes each key update one by one, so more keys mean more work and more time.
Interview Connect
Understanding how multi-key transactions scale helps you explain how Redis handles atomic updates and consistency in real applications.
Self-Check
What if we replaced multiple SET commands with a single Lua script that updates all keys? How would the time complexity change?