mridul's blog

Key Eviction Strategies in Redis and DiceDB

Author: @MridulDhiman11

Overview

When working with high-performance applications, caching plays a crucial role in reducing latency by storing frequently accessed data in memory. However, memory is a finite resource, so eviction strategies are essential to ensure that the cache does not overflow. This article explores the various eviction strategies in Redis and DiceDB and their implementation details, particularly focusing on the approximated LRU and LFU algorithms.

In-memory caches like Redis and DiceDB often act as intermediaries to speed up access to data stored in slower databases or servers. Because caches store data that already exists on disk, evicting data from memory is generally safe. Here are the key eviction strategies employed:

Each strategy comes with its strengths and trade-offs, but LRU and LFU are the most commonly used due to their ability to prioritize frequently accessed data.

The Challenge of Theoretical LRU

A true LRU implementation requires maintaining an exact order of access for each key in memory, typically using a data structure like a doubly-linked list. This allows the system to identify and remove the least recently used key efficiently when eviction is necessary. However, this approach is memory-intensive as it adds overhead to track access recency for every key.

Redis’s Approximated LRU

Redis addresses the memory overhead challenge by using an approximated LRU algorithm. Instead of tracking every single key's usage, Redis samples a subset of keys to determine which one to evict. Here’s how it works:

  1. Sampling: Redis takes a random sample of keys from the dataset.
  2. Eviction Decision: Within the sample, the least recently used key is selected for eviction.
  3. Repetition: The sampling and eviction process repeats until enough keys have been evicted to free up memory.

This sampling-based approach significantly reduces memory usage while maintaining an eviction policy that approximates true LRU behavior.

Sampling Threshold

Redis can be configured to control the sample size and the threshold for eviction, which can influence performance and accuracy. The larger the sample size, the closer the behavior approximates true LRU, but at the cost of higher computational effort.

Approximated LFU with the Morris Counter

Similar to LRU, implementing a true LFU algorithm can be resource-intensive. Redis and DiceDB tackle this challenge by using a probabilistic counting technique known as the Morris Counter. This counter estimates access frequency with a small memory footprint by storing the frequency in a single byte (8 bits) instead of a typical 32-bit integer.

How the Morris Counter Works

The Morris Counter encodes frequency using a logarithmic scale, where the counter increments probabilistically:

Here’s a Go function that demonstrates the logarithmic counter incrementation in DiceDB:

func incrementLogCounter(counter uint8) uint8 {
    if counter == 255 {
        return 255
    }
    randomFactor := rand.Float32()
    approxFactor := 1.0 / (float32(counter)*10 + 1)
    if approxFactor > randomFactor {
        counter++
    }
    return counter
}

This implementation ensures that frequently accessed items increase their count more slowly over time, adapting to changes in access patterns and preventing runaway counts for popular items.

Implementation of LRU eviction in DiceDB

import "sort"

type PoolItem struct {
	key string;
        lastAccessedAt uint8;
}

type EvictionPool struct {
	pool []*PoolItem
}

type ByIdleTime []*PoolItem;

func (x ByIdleTime) Len() {
return len(x);
}

func (a ByIdleTime) Swap(i, j int) {
a[j], a[i] = a[i], a[j]
}

func (a ByIdleTime) Less(i, j bool) bool {
// element with longer idle time removed before the element with shorter idle time
	return GetIdleTime(a[i].lastAccessedAt) > GetIdleTime(a[j].lastAccessedAt)
}


var maxPoolSize int = 16

func (pq *EvictionPool) Push(key string, lastAccessedAt uint8) { 
     if(len(pq.pool) < maxPoolSize)  {
          pq.pool = append(pq.pool, &PoolItem{key: key, lastAccessedAt lastAccessedAt})
         sort.Sort(ByIdleTime(pq.pool));
     } else if(lastAccessedAt > pq.pool[0].lastAccessedAt) {
        pq.pool = pq.pool[1:] // evict the 1st element from priority queue
     }
}

func (pq *EvictionPool) Pop() *PoolItem {
if len(pq.pool) == 0 {
return nil
}
item := pq.pool[0];
pq.pool = pq.pool[1:]
return item;
}

This implementation involves the use of a priority queue to manage the eviction pool.

Eviction Pool Creation: The pool is populated with keys based on sample size and sorted in decreasing order of their idle time and if the pool becomes full while being populated, the least recently used item(i.e. the first item) with the most idle time is evicted.

Eviction Process : Keys are popped from the pool and removed from the hash table on the basis of LRU strategy, where the item with maximum idle time is evicted to free the memory and make room for new keys.

This method provides flexibility and ensures efficient memory use while adapting to different data access patterns.

Conclusion

Redis and DiceDB employ sophisticated approximated algorithms to manage memory efficiently without the need for full-scale data structures that track every key. By using sampling for LRU and probabilistic counters for LFU, they strike a balance between memory usage and eviction accuracy. These strategies make them robust choices for high-performance caching, capable of scaling to meet modern data demands without overwhelming memory resources.

References

https://redis.io/docs/latest/develop/reference/eviction/ https://github.com/DiceDB/dice/blob/master/internal/store/eviction.go https://github.com/DiceDB/dice/blob/master/internal/store/evictionpool.go