Time Complexity: RDB vs AOF comparison
O(n)
0
0
RDB vs AOF comparison in Redis - Performance Comparison
Understanding Time Complexity
When saving data in Redis, two main methods are used: RDB and AOF. Each method takes time to save data, and this time changes as the data grows.
We want to understand how the time to save data grows with the amount of data for both methods.
Scenario Under Consideration
Analyze the time complexity of saving data using RDB snapshot and AOF append-only file.
# RDB snapshot
SAVE
# AOF append
APPENDONLY yes
# Commands are appended as they happen
SET key value
INCR counter
DEL key
RDB saves the whole dataset at once. AOF saves each command as it happens.
Identify Repeating Operations
Look at what repeats when saving data.
- Primary operation for RDB: Writing the entire dataset to disk in one go.
- How many times: Once per snapshot, but the work depends on dataset size.
- Primary operation for AOF: Appending each command to the file as it happens.
- How many times: Once per command, so many times as commands run.
How Execution Grows With Input
How does saving time grow as data grows?
| Input Size (n) | RDB Approx. Operations | AOF Approx. Operations |
|---|---|---|
| 10 keys | Write 10 keys at once | Append 10 commands one by one |
| 100 keys | Write 100 keys at once | Append 100 commands one by one |
| 1000 keys | Write 1000 keys at once | Append 1000 commands one by one |
RDB time grows with total data size because it writes all at once. AOF time grows with number of commands because it writes each command separately.
Final Time Complexity
Time Complexity: O(n) for both, but with different meanings.
RDB time grows linearly with dataset size when saving snapshots. AOF time grows linearly with number of commands appended.
Common Mistake
[X] Wrong: "RDB is always faster because it saves less often."
[OK] Correct: RDB writes the whole dataset at once, which can take longer if data is large. AOF writes smaller pieces more often, so total time depends on command volume.
Interview Connect
Understanding how Redis saves data helps you explain trade-offs in real systems. It shows you can think about how work grows with data, a key skill in many jobs.
Self-Check
"What if AOF was rewritten less often, batching commands? How would that affect time complexity?"