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

Practice

1. What is the main purpose of eviction policies in Redis?

easy

A. To encrypt Redis data

B. To configure the network settings of Redis

C. To backup data automatically

D. To decide how Redis frees memory when it is full

Solution

1. Step 1: Understand Redis memory management

   Redis uses eviction policies to manage memory when it reaches its limit.

2. Step 2: Identify the role of eviction policies

   Eviction policies decide which data to remove to free memory and keep Redis running smoothly.

3. Final Answer:

   To decide how Redis frees memory when it is full -> Option D

4. Quick Check:

   Eviction policies control memory freeing = A [OK]

Hint: Eviction policies manage memory freeing in Redis [OK]

Common Mistakes:

• Confusing eviction policies with backup or encryption
• Thinking eviction policies configure network
• Assuming eviction policies handle data encryption

2. Which command correctly sets the eviction policy to 'allkeys-lru' in Redis?

easy

A. CONFIG SET maxmemory-policy allkeys-lru

B. SET maxmemory-policy allkeys-lru

C. CONFIG GET maxmemory-policy allkeys-lru

D. EVICT POLICY allkeys-lru

Solution

1. Step 1: Recall the correct command format

   Redis uses CONFIG SET to change configuration settings.

2. Step 2: Match the correct syntax for eviction policy

   The correct syntax is CONFIG SET maxmemory-policy policy_name, so allkeys-lru fits here.

3. Final Answer:

   CONFIG SET maxmemory-policy allkeys-lru -> Option A

4. Quick Check:

   Use CONFIG SET for eviction policy = A [OK]

Hint: Use CONFIG SET maxmemory-policy to set eviction [OK]

Common Mistakes:

• Using SET instead of CONFIG SET
• Using CONFIG GET to set a value
• Using a non-existent EVICT POLICY command

3. Given Redis is set with eviction policy volatile-lru and maxmemory is reached, which keys are eligible for eviction?

medium

A. All keys regardless of expiration

B. Only keys with an expiration set

C. Only keys without expiration

D. No keys are evicted automatically

Solution

1. Step 1: Understand 'volatile-lru' policy meaning

   This policy evicts keys with expiration set using least recently used (LRU) order.

2. Step 2: Identify which keys can be evicted

   Only keys that have an expiration time are considered for eviction under 'volatile-lru'. Keys without expiration stay safe.

3. Final Answer:

   Only keys with an expiration set -> Option B

4. Quick Check:

   volatile-lru evicts expiring keys = B [OK]

Hint: volatile-lru evicts only keys with expiration [OK]

Common Mistakes:

• Thinking all keys are evicted
• Confusing volatile-lru with allkeys-lru
• Assuming no keys are evicted automatically

4. You set Redis eviction policy to noeviction but Redis still evicts keys when memory is full. What is the likely cause?

medium

A. The policy was not applied correctly or Redis was restarted without saving config

B. Redis always evicts keys regardless of policy

C. noeviction policy evicts keys randomly

D. Redis ignores eviction policies when maxmemory is set

Solution

1. Step 1: Understand 'noeviction' policy behavior

   This policy prevents Redis from evicting keys automatically when memory is full.

2. Step 2: Identify why eviction still happens

   If eviction occurs, likely the policy was not saved or applied properly, or Redis restarted without config persistence.

3. Final Answer:

   The policy was not applied correctly or Redis was restarted without saving config -> Option A

4. Quick Check:

   noeviction means no eviction unless misconfigured = C [OK]

Hint: Check config save and apply for noeviction policy [OK]

Common Mistakes:

• Believing Redis always evicts keys
• Thinking noeviction evicts randomly
• Assuming eviction policies are ignored when maxmemory is set

5. You want Redis to evict the least recently used keys regardless of expiration when memory is full. Which eviction policy should you choose?

hard

A. volatile-lru

B. noeviction

C. allkeys-lru

D. volatile-random

Solution

1. Step 1: Understand eviction policy options

   volatile-lru evicts only keys with expiration; allkeys-lru evicts any key using LRU.

2. Step 2: Match requirement to policy

   Since eviction should ignore expiration and evict least recently used keys, allkeys-lru fits best.

3. Final Answer:

   allkeys-lru -> Option C

4. Quick Check:

   Evict any key LRU = allkeys-lru = D [OK]

Hint: allkeys-lru evicts any key by least recent use [OK]

Common Mistakes:

• Choosing volatile-lru which only evicts expiring keys
• Selecting volatile-random which evicts randomly
• Picking noeviction which disables eviction