redis lru实现原理是什么？

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