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?"

Practice

1. What is the main purpose of the AOF rewrite process in Redis?

easy

A. To delete all keys from the database

B. To backup the Redis database to a remote server

C. To increase the memory usage of Redis

D. To clean and compact the Append Only File to save disk space

Solution

1. Step 1: Understand the role of AOF in Redis

   The Append Only File (AOF) logs every write operation to Redis for durability.

2. Step 2: Identify what rewrite does

   The rewrite process compacts the AOF by removing redundant commands, saving disk space and improving startup speed.

3. Final Answer:

   To clean and compact the Append Only File to save disk space -> Option D

4. Quick Check:

   AOF rewrite = compacts file to save space [OK]

Hint: AOF rewrite compacts file to save space [OK]

Common Mistakes:

• Confusing AOF rewrite with backup process
• Thinking it increases memory usage
• Believing it deletes data

2. Which Redis command starts the AOF rewrite process without stopping the server?

easy

A. SAVE

B. BGSAVE

C. BGREWRITEAOF

D. FLUSHALL

Solution

1. Step 1: Recall commands related to persistence

   SAVE and BGSAVE are for RDB snapshots, FLUSHALL deletes keys.

2. Step 2: Identify the command for AOF rewrite

   BGREWRITEAOF triggers background AOF rewrite without stopping Redis.

3. Final Answer:

   BGREWRITEAOF -> Option C

4. Quick Check:

   BGREWRITEAOF = background AOF rewrite [OK]

Hint: BGREWRITEAOF rewrites AOF in background [OK]

Common Mistakes:

• Using SAVE which blocks Redis
• Confusing BGSAVE (RDB snapshot) with AOF rewrite
• Using FLUSHALL which clears data

3. Given the following Redis commands sequence:

SET key1 value1
APPEND key1 _extra
BGREWRITEAOF

What is the expected effect on the AOF file after BGREWRITEAOF completes?

medium

A. The AOF file will contain only the latest state of key1 with value 'value1_extra'

B. The AOF file will be empty

C. The AOF file will contain all commands including SET and APPEND separately

D. The AOF file will be deleted

Solution

1. Step 1: Understand the commands effect

   SET key1 value1 sets key1, APPEND adds '_extra' to its value.

2. Step 2: Understand BGREWRITEAOF effect

   BGREWRITEAOF rewrites AOF to contain minimal commands to recreate current state, so it will store SET key1 value1_extra.

3. Final Answer:

   The AOF file will contain only the latest state of key1 with value 'value1_extra' -> Option A

4. Quick Check:

   BGREWRITEAOF compacts commands to current state [OK]

Hint: Rewrite saves only final key states in AOF [OK]

Common Mistakes:

• Thinking all commands remain in AOF
• Assuming AOF is emptied
• Believing AOF is deleted

4. You run BGREWRITEAOF but notice the AOF file size does not reduce. What could be a likely cause?

medium

A. The rewrite process failed due to insufficient disk space

B. The AOF file was already compact and minimal

C. Redis server was stopped during rewrite

D. The command BGSAVE was used instead

Solution

1. Step 1: Consider reasons for no size reduction

   If AOF is already compact, rewriting won't reduce size.

2. Step 2: Evaluate other options

   Failure due to disk space would cause errors; server stop would abort rewrite; BGSAVE does RDB snapshot, not AOF rewrite.

3. Final Answer:

   The AOF file was already compact and minimal -> Option B

4. Quick Check:

   No size change means AOF already minimal [OK]

Hint: No size change means AOF already compact [OK]

Common Mistakes:

• Assuming rewrite always reduces size
• Confusing BGSAVE with BGREWRITEAOF
• Ignoring disk space errors

5. Which of the following best explains why the AOF rewrite process improves Redis startup speed?

hard

A. Because the rewritten AOF file contains fewer commands, Redis loads data faster

B. Because the rewrite process compresses the AOF file using gzip

C. Because the rewrite process deletes all expired keys before startup

D. Because the rewrite process moves the AOF file to a faster disk

Solution

1. Step 1: Understand what affects Redis startup speed

   Redis loads data by replaying commands in the AOF file; fewer commands mean faster loading.

2. Step 2: Analyze options

   Rewrite does not compress with gzip, delete expired keys at startup, or move files to faster disks.

3. Final Answer:

   Because the rewritten AOF file contains fewer commands, Redis loads data faster -> Option A

4. Quick Check:

   Fewer commands in AOF = faster startup [OK]

Hint: Fewer commands in AOF speed up Redis startup [OK]

Common Mistakes:

• Thinking rewrite compresses with gzip
• Believing expired keys are deleted by rewrite
• Assuming file is moved to faster disk