What are Redis expiration strategies and memory eviction mechanisms? How to choose the right strategy? - 面试题

Redis expiration strategy and memory eviction mechanism are core components of Redis memory management, crucial for ensuring Redis stability and performance.

1. Expiration Strategy

Redis has three expiration strategies: Timed Expiration, Lazy Expiration, and Periodic Expiration.

Timed Expiration

Working Principle: When setting a key's expiration time, create a timer. When the expiration time is reached, immediately delete the key.

Advantages:

Memory friendly: Expired keys are deleted in time, not occupying memory
Ensures expired keys don't occupy memory

Disadvantages:

CPU unfriendly: If there are many expired keys, need to create many timers, consuming CPU resources
Affects performance: Timer creation and deletion consume system resources

Redis Implementation: Redis doesn't use timed expiration strategy because it consumes too much CPU.

Lazy Expiration

Working Principle: When a key expires, it's not immediately deleted. Instead, it's checked whether it's expired when accessing the key, and deleted if expired.

Advantages:

CPU friendly: Only checks expiration when accessing the key, doesn't consume extra CPU resources
Good performance: Won't affect system performance due to expired key deletion

Disadvantages:

Memory unfriendly: If expired keys are never accessed, they will continue to occupy memory
May cause memory leaks: Many expired keys not accessed will occupy large amounts of memory

Redis Implementation: Redis uses lazy expiration strategy, checking if a key is expired when executing commands.

c
// Lazy expiration implementation in Redis source code
int expireIfNeeded(redisDb *db, robj *key) {
    // Get key's expiration time
    mstime_t when = getExpire(db, key);
    
    // If key has no expiration time set, return directly
    if (when < 0) return 0;
    
    // If key hasn't expired yet, return directly
    if (mstime() < when) return 0;
    
    // Key has expired, delete key
    server.stat_expiredkeys++;
    propagateExpire(db, key, server.lazyfree_lazy_expire);
    notifyKeyspaceEvent(NOTIFY_EXPIRED, "expired", key, db->id);
    return dbDelete(db, key);
}

Periodic Expiration

Working Principle: Every period of time, randomly select some keys to check if they're expired, and delete if expired.

Advantages:

Balances CPU and memory: By limiting deletion operation frequency, balances CPU and memory usage
Avoids memory leaks: Periodically deletes expired keys, avoiding memory leaks

Disadvantages:

Complex implementation: Need to reasonably set deletion frequency and quantity
May miss: Random selection may miss some expired keys

Redis Implementation: Redis uses periodic expiration strategy, executed periodically in the serverCron function.

c
// Periodic expiration implementation in Redis source code
void activeExpireCycle(int type) {
    // Get current time
    long long start = ustime();
    
    // Iterate through all databases
    for (int j = 0; j < server.dbnum; j++) {
        // Randomly select some keys to check if expired
        for (int i = 0; i < num; i++) {
            // Randomly select a key
            dictEntry *de = dictGetRandomKey(db->dict);
            
            // Check if key is expired
            if (expireIfNeeded(db, de->key)) {
                // Key has expired, delete
                expired++;
            }
        }
    }
}

Redis Expiration Strategy

Redis uses a combination of Lazy Expiration + Periodic Expiration strategies:

Lazy Expiration: Check if key is expired when accessing it, delete if expired
Periodic Expiration: Every period of time, randomly select some keys to check if expired, delete if expired

This combination strategy balances CPU and memory usage, ensuring expired keys are deleted in time without affecting system performance due to massive deletion operations.

2. Memory Eviction Mechanism

When Redis memory usage reaches the maximum memory limit, Redis triggers the memory eviction mechanism, deleting some keys to free memory.

Memory Eviction Policies

Redis provides 8 memory eviction policies:

1. noeviction (No Eviction)

Description: When memory usage reaches maximum limit, don't evict any keys, new write operations return errors.

Use Case: Scenarios with high data integrity requirements, not allowing data loss.

Configuration:

bash
maxmemory-policy noeviction

2. allkeys-lru (All keys use LRU)

Description: Evict least recently used keys from all keys.

Use Case: Need to evict all keys, using LRU algorithm.

Configuration:

bash
maxmemory-policy allkeys-lru

3. allkeys-lfu (All keys use LFU)

Description: Evict least frequently used keys from all keys.

Use Case: Need to evict all keys, using LFU algorithm.

Configuration:

bash
maxmemory-policy allkeys-lfu

4. allkeys-random (All keys random eviction)

Description: Randomly evict keys from all keys.

Use Case: Don't need to consider access frequency, randomly evict keys.

Configuration:

bash
maxmemory-policy allkeys-random

5. volatile-lru (Keys with expiration time use LRU)

Description: Evict least recently used keys from keys with expiration time set.

Use Case: Only evict keys with expiration time set, using LRU algorithm.

Configuration:

bash
maxmemory-policy volatile-lru

6. volatile-lfu (Keys with expiration time use LFU)

Description: Evict least frequently used keys from keys with expiration time set.

Use Case: Only evict keys with expiration time set, using LFU algorithm.

Configuration:

bash
maxmemory-policy volatile-lfu

7. volatile-random (Keys with expiration time random eviction)

Description: Randomly evict keys from keys with expiration time set.

Use Case: Only evict keys with expiration time set, random eviction.

Configuration:

bash
maxmemory-policy volatile-random

8. volatile-ttl (Evict keys about to expire)

Description: Evict keys about to expire from keys with expiration time set.

Use Case: Prioritize evicting keys about to expire.

Configuration:

bash
maxmemory-policy volatile-ttl

LRU Algorithm Implementation

Redis uses an approximate LRU algorithm, not an exact LRU algorithm.

Why use approximate LRU?

Exact LRU algorithm needs to maintain a linked list, updating the list every time a key is accessed, consuming large amounts of CPU resources
Approximate LRU algorithm only needs to record the key's last access time, doesn't need to maintain a linked list, better performance

Redis's Approximate LRU Implementation: Redis records the last access time for each key. When needing to evict keys, randomly select some keys and evict the one with the earliest access time.

c
// Approximate LRU implementation in Redis source code
unsigned int LRU_GetLRU(redisObject *obj) {
    unsigned int lru = obj->lru;
    if (lru >= LRU_CLOCK()) {
        lru = (lru & 0x7FFFFFFF);
    } else {
        lru = LRU_CLOCK() & 0x7FFFFFFF;
    }
    return lru;
}

LFU Algorithm Implementation

Redis 4.0 introduced the LFU algorithm for evicting least frequently used keys.

LFU Algorithm Implementation: Redis records access frequency for each key. When needing to evict keys, evict the key with the lowest access frequency.

c
// LFU implementation in Redis source code
void LFU_DecrAndReturn(robj *obj) {
    unsigned long ldt = obj->lru >> 8;
    unsigned long counter = LFUGetCounterIncrAndReturn(obj->lru);
    
    if (counter) {
        counter--;
        obj->lru = (ldt << 8) | counter;
    }
}

Memory Eviction Policy Selection

Selection Recommendations:

If all keys have expiration time set: Use volatile-lru or volatile-lfu
If only some keys have expiration time set: Use allkeys-lru or allkeys-lfu
If data integrity requirements are high: Use noeviction
If access frequency doesn't need to be considered: Use allkeys-random or volatile-random

3. Monitor Memory Usage

You can use the INFO memory command to view Redis memory usage:

bash
# View memory usage
INFO memory

# View memory usage details
used_memory:1024000
used_memory_human:1.00M
used_memory_rss:2048000
used_memory_rss_human:2.00M
used_memory_peak:2048000
used_memory_peak_human:2.00M
maxmemory:1073741824
maxmemory_human:1.00G

Summary

Redis expiration strategy and memory eviction mechanism are core components of Redis memory management. Expiration strategies include Timed Expiration, Lazy Expiration, and Periodic Expiration. Redis uses a combination of Lazy Expiration + Periodic Expiration strategies. Memory eviction mechanism includes 8 policies, and you can choose the appropriate policy based on actual scenarios. In practical applications, you need to choose appropriate expiration strategies and memory eviction policies based on business requirements and performance requirements.