# Improving Redis Cache Eviction with the LRU Algorithm

DevFeed: [Improving Redis Cache Eviction with the LRU Algorithm](<https://devfeed.tech/articles/random-notes-on-improving-the-redis-lru-algorithm-20600.md>)

Original publisher: [Read original article](<http://antirez.com/news/109>)

Published: 2016-07-29T08:04:12Z

Content type: article

Language: en

Sources: [Antirez](<https://devfeed.tech/sources/antirez.md>)

Topics: [Redis](<https://devfeed.tech/topics/redis.md>), [Caching](<https://devfeed.tech/topics/caching.md>), [Cache](<https://devfeed.tech/topics/cache.md>), [Algorithm](<https://devfeed.tech/topics/algorithm.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [cache](<https://devfeed.tech/tags/cache.md>), [caching](<https://devfeed.tech/tags/caching.md>), [redis](<https://devfeed.tech/tags/redis.md>)

## AI overview

The article explains how Redis cache eviction affects hit rates and why access patterns make eviction difficult. It introduces LRU, which evicts keys based on when they were last requested, as a practical approximation for retaining data likely to be accessed again.

## Source excerpt

Redis is often used for caching, in a setup where a fixed maximum memory to use is specified. When new data arrives, we need to make space by removing old data. The efficiency of Redis as a cache is related to how good decisions it makes about what data to evict: deleting data that is going to be needed soon is a poor strategy, while deleting data that is unlikely to be requested again is a good one. In other terms every cache has an hits/misses ratio, which is, in qualitative terms, just the percentage of read queries that the cache is able to serve. Accesses to the keys of a cache are not distributed evenly among the data set in most workloads. Often a small percentage of keys get a very large percentage of all the accesses. Moreover the access pattern often changes over time, which means that as time passes certain keys that were very requested may no longer be accessed often, and conversely, keys that once were not popular may turn into the most accessed keys. So in general what a cache should try to do is to retain the keys that have the highest probability of being accessed in the future. From the point of view of an eviction policy (the policy used to make space to allow new data to enter) this translates into the contrary: the key with the least probability of being accessed in the future should be removed from the data set. There is only one problem: Redis and other caches are not able to predict the future. The LRU algorithm === While caches can't predict the future, they can reason in the following way: keys that are likely to be requested again are keys that were recently requested often. Since usually access patterns don't change very suddenly, this is an effective strategy. However the notion of "recently requested often" is more insidious that it may look at a first glance (we'll return shortly on this). So this concept is simplified into an algorithm that is called LRU, which instead just tracks the *last time* a key was requested. Keys that are acce