AOF rewrite process in Redis - Time & Space Complexity

Time Complexity: AOF rewrite process

O(n)

Understanding Time Complexity

We want to understand how the time needed for Redis to rewrite its Append Only File (AOF) changes as the data grows.

How does the rewrite process scale when more data is stored?

Scenario Under Consideration

Analyze the time complexity of the AOF rewrite process in Redis.

// Pseudocode for AOF rewrite process
start AOF rewrite
for each key in database {
  get key type
  get key value
  write command to new AOF file
}
finish AOF rewrite

This code loops over all keys in the database, reads their data, and writes commands to a new AOF file to compact the data.

Identify Repeating Operations

Look for repeated actions in the rewrite process.

• Primary operation: Looping over every key in the database.
• How many times: Once for each key stored in Redis.

How Execution Grows With Input

The time to rewrite grows as the number of keys grows, because each key must be processed once.

Input Size (n)	Approx. Operations
10	About 10 key reads and writes
100	About 100 key reads and writes
1000	About 1000 key reads and writes

Pattern observation: The work grows directly with the number of keys; doubling keys roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the rewrite time grows in a straight line with the number of keys stored.

Common Mistake

[X] Wrong: "The rewrite time stays the same no matter how many keys there are."

[OK] Correct: Because Redis must process every key to write it to the new file, more keys mean more work and longer rewrite time.

Interview Connect

Understanding how Redis handles data persistence and its costs helps you explain real-world database behavior clearly and confidently.

Self-Check

"What if Redis only rewrote keys that changed since the last rewrite? How would the time complexity change?"