关于后端:谈谈-Redis-的过期策略

能为有价值的工作而致力，就是生存给予你最宝贵的礼物。

在日常开发中，咱们应用 Redis 存储 key 时通常会设置一个过期工夫，然而 Redis 是怎么删除过期的 key，而且 Redis 是单线程的，删除 key 会不会造成阻塞。要搞清楚这些，就要理解 Redis 的过期策略和内存淘汰机制。

Redis 采纳的是定期删除 + 懈怠删除策略。

Redis 会将每个设置了过期工夫的 key 放入到一个独立的字典中，默认每 100ms 进行一次过期扫描：

随机抽取 20 个 key
删除这 20 个 key 中过期的 key
如果过期的 key 比例超过 1/4，就反复步骤 1，持续删除。

为什不扫描所有的 key？

Redis 是单线程，全副扫描岂不是卡死了。而且为了避免每次扫描过期的 key 比例都超过 1/4，导致不停循环卡死线程，Redis 为每次扫描增加了下限工夫，默认是 25ms。

如果客户端将超时工夫设置的比拟短，比方 10ms，那么就会呈现大量的链接因为超时而敞开，业务端就会呈现很多异样。而且这时你还无奈从 Redis 的 slowlog 中看到慢查问记录，因为慢查问指的是逻辑处理过程慢，不蕴含等待时间。

如果在同一时间呈现大面积 key 过期，Redis 循环屡次扫描过期词典，直到过期的 key 比例小于 1/4。这会导致卡顿，而且在高并发的状况下，可能会导致缓存雪崩。

为什么 Redis 为每次扫描添的下限工夫是 25ms，还会呈现下面的状况？

因为 Redis 是单线程，每个申请解决都须要排队，而且因为 Redis 每次扫描都是 25ms，也就是每个申请最多 25ms，100 个申请就是 2500ms。

如果有大批量的 key 过期，要给过期工夫设置一个随机范畴，而不宜全副在同一时间过期，扩散过期解决的压力。

从库不会进行过期扫描，从库对过期的解决是被动的。主库在 key 到期时，会在 AOF 文件里减少一条 del 指令，同步到所有的从库，从库通过执行这条 del 指令来删除过期的 key。

因为指令同步是异步进行的，所以主库过期的 key 的 del 指令没有及时同步到从库的话，会呈现主从数据的不统一，主库没有的数据在从库里还存在。

Redis 为什么要懈怠删除 (lazy free)？

删除指令 del 会间接开释对象的内存，大部分状况下，这个指令十分快，没有显著提早。不过如果删除的 key 是一个十分大的对象，比方一个蕴含了千万元素的 hash，又或者在应用 FLUSHDB 和 FLUSHALL 删除蕴含大量键的数据库时，那么删除操作就会导致单线程卡顿。

redis 4.0 引入了 lazyfree 的机制，它能够将删除键或数据库的操作放在后盾线程里执行，从而尽可能地防止服务器阻塞。

unlink 指令，它能对删除操作进行懒解决，丢给后盾线程来异步回收内存。

> unlink key  
OK

flushdb 和 flushall 指令，用来清空数据库，这也是极其迟缓的操作。Redis 4.0 同样给这两个指令也带来了异步化，在指令前面减少 async 参数就能够将整棵大树连根拔起，扔给后盾线程缓缓焚烧。

> flushall async  
OK

主线程将对象的援用从「大树」中摘除后，会将这个 key 的内存回收操作包装成一个工作，塞进异步工作队列，后盾线程会从这个异步队列中取工作。工作队列被主线程和异步线程同时操作，所以必须是一个线程平安的队列。

不是所有的 unlink 操作都会延后解决，如果对应 key 所占用的内存很小，延后解决就没有必要了，这时候 Redis 会将对应的 key 内存立刻回收，跟 del 指令一样。

Redis 回收内存除了 del 指令和 flush 之外，还会存在于在 key 的过期、LRU 淘汰、rename 指令以及从库全量同步时承受完 rdb 文件后会立刻进行的 flush 操作。

Redis4.0 为这些删除点也带来了异步删除机制，关上这些点须要额定的配置选项。

slave-lazy-flush 从库承受完 rdb 文件后的 flush 操作
lazyfree-lazy-eviction 内存达到 maxmemory 时进行淘汰
lazyfree-lazy-expire key 过期删除
lazyfree-lazy-server-del rename 指令删除 destKey

Redis 的内存占用会越来越高。Redis 为了限度最大应用内存，提供了 redis.conf 中的
配置参数 maxmemory。当内存超出 maxmemory，Redis 提供了几种内存淘汰机制让用户抉择，配置 maxmemory-policy：

noeviction： 当内存超出 maxmemory，写入申请会报错，然而删除和读申请能够持续。（应用这个策略，疯了吧）
allkeys-lru： 当内存超出 maxmemory，在所有的 key 中，移除起码应用的 key。只把 Redis 既当缓存是应用这种策略。（举荐）。
allkeys-random： 当内存超出 maxmemory，在所有的 key 中，随机移除某个 key。（应该没人用吧）
volatile-lru： 当内存超出 maxmemory，在设置了过期工夫 key 的字典中，移除起码应用的 key。把 Redis 既当缓存，又做长久化的时候应用这种策略。
volatile-random： 当内存超出 maxmemory，在设置了过期工夫 key 的字典中，随机移除某个 key。
volatile-ttl： 当内存超出 maxmemory，在设置了过期工夫 key 的字典中，优先移除 ttl 小的。

实现 LRU 算法除了须要 key/value 字典外，还须要附加一个链表，链表中的元素依照肯定的程序进行排列。当空间满的时候，会踢掉链表尾部的元素。当字典的某个元素被拜访时，它在链表中的地位会被挪动到表头。所以链表的元素排列程序就是元素最近被拜访的工夫程序。

应用 Python 的 OrderedDict(双向链表 + 字典) 来实现一个简略的 LRU 算法：

from collections import OrderedDict

class LRUDict(OrderedDict):
    def __init__(self, capacity):
        self.capacity = capacity
        self.items = OrderedDict()

    def __setitem__(self, key, value):
        old_value = self.items.get(key)
        if old_value is not None:
            self.items.pop(key)
            self.items[key] = value
        elif len(self.items) < self.capacity:
            self.items[key] = value
        else:
            self.items.popitem(last=True)
            self.items[key] = value

    def __getitem__(self, key):
        value = self.items.get(key)
        if value is not None:
            self.items.pop(key)
            self.items[key] = value
        return value

    def __repr__(self):
        return repr(self.items)


d = LRUDict(10)

for i in range(15):
    d[i] = i
print d

Redis 应用的并不是齐全 LRU 算法。不应用 LRU 算法，是为了节俭内存，Redis 采纳的是随机 LRU 算法，Redis 为每一个 key 减少了一个 24 bit 的字段，用来记录这个 key 最初一次被拜访的工夫戳。

留神 Redis 的 LRU 淘汰策略是懈怠解决，也就是不会被动执行淘汰策略，当 Redis 执行写操作时，发现内存超出 maxmemory，就会执行 LRU 淘汰算法。这个算法就是随机采样出 5(默认值) 个 key，而后移除最旧的 key，如果移除后内存还是超出 maxmemory，那就持续随机采样淘汰，直到内存低于 maxmemory 为止。

如何采样就是看 maxmemory-policy 的配置，如果是 allkeys 就是从所有的 key 字典中随机，如果是 volatile 就从带过期工夫的 key 字典中随机。每次采样多少个 key 看的是 maxmemory_samples 的配置，默认为 5。

Redis 4.0 里引入了一个新的淘汰策略 —— LFU（Least Frequently Used）模式，作者认为它比 LRU 更加优良。

LFU 示意按最近的拜访频率进行淘汰，它比 LRU 更加精准地示意了一个 key 被拜访的热度。

如果一个 key 长时间不被拜访，只是刚刚偶尔被用户拜访了一下，那么在应用 LRU 算法下它是不容易被淘汰的，因为 LRU 算法认为以后这个 key 是很热的。而 LFU 是须要追踪最近一段时间的拜访频率，如果某个 key 只是偶尔被拜访一次是不足以变得很热的，它须要在近期一段时间内被拜访很屡次才有机会被认为很热。

Redis 对象的热度

Redis 的所有对象构造头中都有一个 24bit 的字段，这个字段用来记录对象的热度。

// redis 的对象头
typedef struct redisObject {
    unsigned type:4; // 对象类型如 zset/set/hash 等等
    unsigned encoding:4; // 对象编码如 ziplist/intset/skiplist 等等
    unsigned lru:24; // 对象的「热度」int refcount; // 援用计数
    void *ptr; // 对象的 body
} robj;

LRU 模式

在 LRU 模式下，lru 字段存储的是 Redis 时钟 server.lruclock，Redis 时钟是一个 24bit 的整数，默认是 Unix 工夫戳对 2^24 取模的后果，大概 97 天清零一次。当某个 key 被拜访一次，它的对象头的 lru 字段值就会被更新为 server.lruclock。

LFU 模式

在 LFU 模式下，lru 字段 24 个 bit 用来存储两个值，别离是 ldt(last decrement time) 和 logc(logistic counter)。

logc 是 8 个 bit，用来存储拜访频次，因为 8 个 bit 能示意的最大整数值为 255，存储频次必定远远不够，所以这 8 个 bit 存储的是频次的对数值，并且这个值还会随工夫衰减。如果它的值比拟小，那么就很容易被回收。为了确保新创建的对象不被回收，新对象的这 8 个 bit 会初始化为一个大于零的值，默认是 LFU_INIT_VAL=5。

ldt 是 16 个位，用来存储上一次 logc 的更新工夫，因为只有 16 位，所以精度不可能很高。它取的是分钟工夫戳对 2^16 进行取模，大概每隔 45 天就会折返。

同 LRU 模式一样，咱们也能够应用这个逻辑计算出对象的闲暇工夫，只不过精度是分钟级别的。图中的 server.unixtime 是以后 redis 记录的零碎工夫戳，和 server.lruclock 一样，它也是每毫秒更新一次。

定期删除策略

从库的过期策略

懈怠删除策略

unlink

flush

异步队列

更多异步删除点

内存淘汰机制

LRU 算法

近似 LRU 算法

LFU