Eviction policies (LRU, LFU, random) in Redis - Step-by-Step Execution

Concept Flow - Eviction policies (LRU, LFU, random)

Cache Full?

Yes↓

Select Eviction Policy

↓

LRU

↓

Evict Key

↓

Add New Key

When the cache is full, Redis chooses a key to remove based on the selected eviction policy (LRU, LFU, or Random) before adding a new key.

Execution Sample

Redis

SET key1 val1
SET key2 val2
... (cache full)
GET key1
SET key3 val3

Simulates adding keys until cache is full, accessing keys to update usage, then adding a new key causing eviction.

Execution Table

Step	Action	Cache State	Eviction Policy	Evicted Key	Reason
1	SET key1 val1	{key1}	LRU	None	Cache not full
2	SET key2 val2	{key1, key2}	LRU	None	Cache not full
3	GET key1	{key1 (recent), key2}	LRU	None	Access updates usage
4	SET key3 val3	{key1, key3}	LRU	key2	Cache full, evict least recently used key2
5	SET key4 val4	{key3, key4}	LFU	key1	Cache full, evict least frequently used key1
6	SET key5 val5	{key4, key5}	Random	key3	Cache full, evict random key3

💡 Eviction occurs only when cache is full; keys are evicted based on policy before adding new keys.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6
Cache Keys	{}	{key1}	{key1, key2}	{key1 (recent), key2}	{key1, key3}	{key3, key4}	{key4, key5}
Eviction Policy	LRU	LRU	LRU	LRU	LFU	Random	Random
Evicted Key	None	None	None	None	key2	key1	key3

Key Moments - 3 Insights

Why does 'key2' get evicted at step 4 instead of 'key1'?

Because at step 3, 'key1' was accessed making it the most recently used, so 'key2' is the least recently used and gets evicted as shown in execution_table row 4.

How does the LFU policy decide which key to evict at step 5?

LFU evicts the key with the lowest usage count. Since 'key1' was used less frequently than 'key4', it is evicted as shown in execution_table row 5.

What happens when the Random policy is used at step 6?

A random key is chosen to be evicted without considering usage. Here, 'key3' was randomly selected and evicted as shown in execution_table row 6.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. Which key was evicted and why?

A key2 because it was least recently used

B key1 because it was least recently used

C key3 because it was least frequently used

D No key was evicted

💡 Hint

Check the 'Evicted Key' and 'Reason' columns at step 4 in execution_table.

According to variable_tracker, what is the cache state after step 5?

A {key4, key5}

B {key1, key3}

C {key3, key4}

D {key1, key4}

💡 Hint

Look at the 'Cache Keys' row under 'After 5' in variable_tracker.

If the eviction policy at step 6 was LRU instead of Random, which key would likely be evicted?

A key5

B key3

C key4

D key1

💡 Hint

Refer to the usage order in execution_table and variable_tracker before step 6.

Concept Snapshot

Eviction policies remove keys when cache is full.
LRU evicts least recently used key.
LFU evicts least frequently used key.
Random evicts any key randomly.
Policy choice affects cache behavior and performance.

Full Transcript

This visual execution shows how Redis eviction policies work when the cache is full. First, keys are added until the cache reaches capacity. When a new key is added beyond capacity, Redis evicts one key based on the selected policy. LRU removes the least recently used key, LFU removes the least frequently used key, and Random removes a random key. The execution table tracks each step, showing cache state, eviction decisions, and reasons. The variable tracker records how cache keys and eviction policy change over time. Key moments clarify common confusions about eviction choices. The quiz tests understanding by referencing specific steps and states. This helps beginners see exactly how eviction policies affect cache contents step-by-step.

Practice

1. Which Redis eviction policy removes the least recently used keys first when memory is full?

easy

A. LRU (Least Recently Used)

B. LFU (Least Frequently Used)

C. Random

D. No eviction

Solution

1. Step 1: Understand eviction policies in Redis

   Redis uses eviction policies to free memory when it is full by removing keys based on certain rules.

2. Step 2: Identify the policy that removes least recently used keys

   LRU stands for Least Recently Used, which means it removes keys that have not been accessed for the longest time.

3. Final Answer:

   LRU (Least Recently Used) -> Option A

4. Quick Check:

   Eviction policy removing least recently used keys = LRU [OK]

Hint: LRU = removes oldest unused keys first [OK]

Common Mistakes:

• Confusing LRU with LFU
• Thinking random eviction is based on usage
• Assuming no eviction means keys are removed

2. Which of the following is the correct Redis configuration directive to set the eviction policy to LFU?

easy

A. maxmemory-policy allkeys-lfu

B. maxmemory-policy random-eviction

C. maxmemory-policy volatile-lru

D. maxmemory-policy noeviction

Solution

1. Step 1: Recall Redis maxmemory-policy options

   Redis uses the 'maxmemory-policy' directive to set eviction behavior, with options like 'allkeys-lfu' for LFU eviction.

2. Step 2: Identify the correct syntax for LFU eviction

   The correct directive for LFU eviction on all keys is 'maxmemory-policy allkeys-lfu'.

3. Final Answer:

   maxmemory-policy allkeys-lfu -> Option A

4. Quick Check:

   LFU eviction config = maxmemory-policy allkeys-lfu [OK]

Hint: LFU config uses 'allkeys-lfu' in maxmemory-policy [OK]

Common Mistakes:

• Using 'random-eviction' instead of LFU
• Confusing 'volatile-lru' with LFU
• Missing 'maxmemory-policy' keyword

3. Given Redis is configured with the maxmemory-policy allkeys-lru and memory is full, what happens when a new key is added?

medium

A. A random key is evicted to make space

B. The least frequently used key is evicted to make space

C. The least recently used key is evicted to make space

D. The new key is rejected and not added

Solution

1. Step 1: Understand the 'allkeys-lru' eviction policy

   This policy evicts the least recently used key among all keys when memory is full.

2. Step 2: Predict behavior when adding a new key

   When memory is full, Redis removes the least recently used key to free space for the new key.

3. Final Answer:

   The least recently used key is evicted to make space -> Option C

4. Quick Check:

   allkeys-lru evicts least recently used key [OK]

Hint: allkeys-lru evicts oldest used key on full memory [OK]

Common Mistakes:

• Confusing LRU with LFU eviction
• Thinking random eviction applies here
• Assuming new keys are rejected automatically

4. You configured Redis with maxmemory-policy volatile-lfu but notice keys without expiration are never evicted. What is the likely cause?

medium

A. LFU policy does not work with volatile keys

B. Only keys with expiration are considered for eviction in volatile-lfu

C. Redis randomly evicts keys regardless of policy

D. Keys without expiration are evicted first

Solution

1. Step 1: Understand volatile-lfu eviction policy

   Volatile policies only evict keys that have an expiration set (TTL).

2. Step 2: Analyze why keys without expiration remain

   Since keys without expiration are not eligible, they are never evicted under volatile-lfu.

3. Final Answer:

   Only keys with expiration are considered for eviction in volatile-lfu -> Option B

4. Quick Check:

   Volatile policies evict only expiring keys [OK]

Hint: Volatile policies evict only keys with expiration [OK]

Common Mistakes:

• Assuming LFU ignores expiration
• Thinking random eviction applies here
• Believing keys without expiration are evicted first

5. You want Redis to evict keys randomly but only among keys with expiration set. Which eviction policy should you configure?

hard

A. volatile-lru

B. allkeys-random

C. allkeys-lfu

D. volatile-random

Solution

1. Step 1: Understand eviction policy prefixes

   'allkeys-' applies to all keys; 'volatile-' applies only to keys with expiration.

2. Step 2: Identify random eviction among volatile keys

   'volatile-random' evicts keys randomly but only among keys with expiration set.

3. Final Answer:

   volatile-random -> Option D

4. Quick Check:

   Random eviction on expiring keys = volatile-random [OK]

Hint: Volatile-random evicts random expiring keys only [OK]

Common Mistakes:

• Choosing allkeys-random which evicts all keys
• Confusing LFU or LRU with random eviction
• Selecting volatile-lru which is not random