Time Complexity: WATCH for optimistic locking
O(n)
0
0
WATCH for optimistic locking in Redis - Time & Space Complexity
Understanding Time Complexity
When using WATCH in Redis, we want to see how the time to complete a transaction changes as we watch more keys.
We ask: How does watching keys affect the work Redis does before committing changes?
Scenario Under Consideration
Analyze the time complexity of this Redis transaction using WATCH.
WATCH key1 key2 key3
MULTI
INCR key1
INCR key2
EXEC
This code watches three keys for changes, then starts a transaction to increment two keys, and finally tries to execute the transaction.
Identify Repeating Operations
Look for repeated checks or loops inside the transaction process.
- Primary operation: Redis checks each watched key for changes before EXEC.
- How many times: Once per EXEC call, checking all watched keys.
How Execution Grows With Input
As the number of watched keys grows, Redis must check more keys before running the transaction.
| Input Size (number of watched keys) | Approx. Operations |
|---|---|
| 3 | 3 key checks |
| 10 | 10 key checks |
| 100 | 100 key checks |
Pattern observation: The work grows directly with the number of watched keys.
Final Time Complexity
Time Complexity: O(n)
This means the time to check keys grows linearly with how many keys you watch.
Common Mistake
[X] Wrong: "Watching more keys does not affect performance because Redis is fast."
[OK] Correct: Even though Redis is fast, it still checks every watched key before executing, so more keys mean more work.
Interview Connect
Understanding how WATCH scales helps you explain transaction costs clearly and shows you know how Redis handles concurrency.
Self-Check
What if we replaced WATCH with a Lua script for atomic updates? How would the time complexity change?