Eviction policies overview in Redis - Time & Space Complexity

Time Complexity: Eviction policies overview

O(n)

Understanding Time Complexity

When Redis runs out of memory, it removes some data to make space. This process is called eviction.

We want to understand how the time it takes to evict keys changes as the data size grows.

Scenario Under Consideration

Analyze the time complexity of eviction when Redis uses the allkeys-lru policy.

    // Redis eviction with allkeys-lru
    while (memory_used > max_memory) {
      key = find_least_recently_used_key();
      delete_key(key);
      update_memory_usage();
    }
    

This code removes the least recently used keys until enough memory is freed.

Identify Repeating Operations

Look for repeated actions that affect performance.

• Primary operation: Finding and deleting keys one by one.
• How many times: Repeated until memory is below the limit, depends on how much memory needs freeing.

How Execution Grows With Input

As the number of keys grows, finding the least recently used key takes more effort.

Input Size (n keys)	Approx. Operations
10	Few steps to find and delete keys
100	More steps, but still manageable
1000	More searching needed, time grows

Pattern observation: The time to find keys grows roughly with the number of keys.

Final Time Complexity

Time Complexity: O(n)

This means the time to evict keys grows linearly with the number of keys stored.

Common Mistake

[X] Wrong: "Eviction always happens instantly no matter how many keys there are."

[OK] Correct: Finding which keys to remove takes more time as the database grows, so eviction can slow down with more data.

Interview Connect

Understanding eviction time helps you explain how Redis manages memory efficiently and what happens under heavy load.

Self-Check

"What if Redis used a random eviction policy instead of LRU? How would the time complexity change?"