Redis 缓存替换策略

本文分析 redis 的 8 种缓存替换（淘汰）策略

Redis 配置文件

# volatile-lru -> Evict using approximated LRU among the keys with an expire set.
# allkeys-lru -> Evict any key using approximated LRU.
# volatile-lfu -> Evict using approximated LFU among the keys with an expire set.
# allkeys-lfu -> Evict any key using approximated LFU.
# volatile-random -> Remove a random key among the ones with an expire set.
# allkeys-random -> Remove a random key, any key.
# volatile-ttl -> Remove the key with the nearest expire time (minor TTL)
# noeviction -> Don't evict anything, just return an error on write operations.
#
# LRU means Least Recently Used
# LFU means Least Frequently Used
#
# Both LRU, LFU and volatile-ttl are implemented using approximated
# randomized algorithms.
#
#
# The default is:
#
# maxmemory-policy noeviction

# LRU, LFU and minimal TTL algorithms are not precise algorithms but approximated
# algorithms (in order to save memory), so you can tune it for speed or
# accuracy. For default Redis will check five keys and pick the one that was
# used less recently, you can change the sample size using the following
# configuration directive.
#
# The default of 5 produces good enough results. 10 Approximates very closely
# true LRU but costs more CPU. 3 is faster but not very accurate.
#
# maxmemory-samples 5

redis 缓存替换策略分析

基础

LRU：Least Recently Used，最近最少（被）使用，选择最近使用的页面予以保留，反之予以淘汰。该算法赋予每个样本一个访问时间字段，用来记录一个上次被访问的时间戳 t，当必须淘汰一个样本时，选择样本中 t 值最小的予以淘汰。

LFU：Least Frequently Used，最不经常（被）使用，淘汰引用计数最小的样本。算法为每个key维护一个引用计数器，每当key被访问的时候，计数器增大；计数器越大，可以约等于访问越频繁。

分析

class 1, volatile  # 基于过期时间的淘汰策略
    volatile-lru  # 在设置了过期时间的key上，执行LRU策略
    volatile-lfu  # 在设置了过期时间的key上，执行LFU策略
    volatile-random  # 在设置了过期时间的key上，执行随机淘汰策略
    volatile-ttl  # 删除过期时间最近的key
class 2, allkey		# 简单过期策略
		allkeys-lru  # 使用近似LRU策略来淘汰key
		allkeys-lfu  # 使用近似LFU策略来淘汰key
		allkeys-random  # 随机淘汰任何key
class 3, no eviction  # 不淘汰策略
		noeviction  # 不淘汰任何key

redis默认使用noeviction策略，也即不淘汰任何的key。

默认情况下，Redis将检查5个key，并选择最近使用较少的1个key进行淘汰。默认值5会产生足够好的结果。10非常接近真实的LRU，但需要更多的CPU。3更快，但不是很准确。