Redis LRU 实现原理
Redis 的 LRU（Least Recently Used，最近最少使用）是一种缓存淘汰策略，用于在内存不足时根据数据的访问情况选择要淘汰的键。Redis 的 LRU 实现并不是完全精确的，而是基于采样算法，以在性能和准确性之间取得平衡。
Redis 内存淘汰策略简介
Redis 提供多种内存淘汰策略，其中 LRU 是最常用的一种。
常见策略包括：
noeviction：不淘汰数据，超出内存限制时直接返回错误。
allkeys-lru：在所有键中，使用 LRU 策略淘汰最近最少使用的键。
volatile-lru：仅在设置了过期时间的键中，使用 LRU 策略淘汰最近最少使用的键。
allkeys-random：随机淘汰键。
volatile-random：仅在设置了过期时间的键中随机淘汰。
volatile-ttl：仅在设置了过期时间的键中，淘汰剩余存活时间最短的键。
Redis LRU 的实现步骤
Redis 的 LRU 实现基于以下关键点：
1. 每个键都存储了一个最近使用时间戳
Redis 在每个键的元数据中，记录了一个最近访问时间。
这个时间戳是从 Redis 服务器启动到当前时间的秒数（或更精确的毫秒数）。
2. 采用采样算法
Redis 的 LRU 并不是对所有键进行排序，而是通过随机抽样的方式进行。
当需要淘汰键时，从 Redis 数据库中随机采样一部分键，然后在这部分键中选择最近最少使用的键淘汰。
默认的采样数量是 5 个，可以通过配置参数
maxmemory-samples调整。
3. 过程描述
以下是 LRU 策略的简化过程：
Redis 检测内存是否超过了配置的最大限制（
maxmemory）。如果超过限制，则根据配置的淘汰策略选择键。
对于
allkeys-lru策略，Redis 从所有键中随机选择maxmemory-samples个键。对于
volatile-lru策略，只从有过期时间的键中随机选择。
比较这
maxmemory-samples个键的最近使用时间，淘汰最近最少使用的键。如果内存仍然超标，重复此过程直到内存回到限制以下。
4. 配置选项
Redis LRU 的相关配置项包括：
maxmemory：设置 Redis 最大内存使用限制。maxmemory-policy：选择内存淘汰策略（如allkeys-lru）。maxmemory-samples：设置采样键的数量，默认值为 5。
为什么是采样而不是精确实现
性能考虑
如果对所有键进行排序，操作的时间复杂度为 O(N)，在键数量较多时会造成严重的性能瓶颈。
采样算法的复杂度为 O(maxmemory-samples)，可以在性能和准确性之间取得平衡。
准确性不需要完全精确
LRU 本质是一个启发式策略，完全精确的 LRU 在大多数场景中并没有必要。
通过增加采样数量（如从 5 增加到 10 或 15），可以显著提高准确性。
Redis 内部实现的核心结构
1. 时间戳的存储
每个键的最近使用时间保存在
redisObject结构的lru字段中。这个字段记录了键的最近访问时间，单位为 Redis 启动以来的时钟周期数。
2. 淘汰过程代码简述
以下是 Redis 淘汰键时 LRU 策略的伪代码：
void evictKey() {
// 从所有键中随机抽取 maxmemory-samples 个键
sample_keys = getRandomKeys(maxmemory_samples);
// 找到最近最少使用的键
key_to_evict = findLeastRecentlyUsed(sample_keys);
// 删除选定的键
deleteKey(key_to_evict);
}3. 采样数的影响
当
maxmemory-samples较小时，采样结果的随机性较大，准确性较低。当
maxmemory-samples较大时，结果更接近真实的 LRU，但会消耗更多的 CPU。
优势与局限
优势
性能优先：通过采样避免了全局排序，大幅提高了效率。
灵活性：支持多种淘汰策略（如 LRU、随机、TTL 等），满足不同场景需求。
可调优：通过调整
maxmemory-samples，开发者可以在性能和准确性之间找到合适的平衡。
局限
非精确 LRU：采样策略导致 Redis 的 LRU 实现并不完全精确。
极端情况失效：如果键分布不均匀，采样可能选不到真正需要淘汰的键。
总结
Redis 的 LRU 策略通过以下方式实现：
每个键记录最近访问时间。
使用随机采样法选择键，避免对所有键排序的性能开销。
淘汰采样中最近最少使用的键。
这种基于采样的实现平衡了性能和准确性，适用于大多数高性能场景。
通过调整采样数量和策略，可以进一步优化 Redis 的 LRU 行为，满足具体业务需求。
