Redis过期键删除策略及原理

通过EXPIRE命令或者PEXPIRE命令，客户端可以以秒或者毫秒精度对库中的键设置生存时间（Time To Live，TTL）

SETNX可以在设置一个字符串键的同时设置过期时间。

TTL/ PTTL key 返回当前键的剩余时间

这也就是常用的，分布式锁的基本实现方式。

首先是明确：过期时间，存储在redisDB结构的expires字典里。这个字典称之为过期字典。

字典的键是一个指针，指向键空间里的某个键对象。

字典的值是一个long的整数，保存过期时间的毫米级unix时间戳。

    惰性删除+定期删除

    键过期后并不会立即删除，而是等到使用它时，先判断该键是否已经过期，如果过期则删除

    对内存不友好，对CPU友好

    redis每隔一段时间随机检测一部分数据（并不是全部）是否过期，如果已过期则删除

    redis.conf中的hz参数用来配置每秒执行几次定期删除，默认值是10，即100ms/次

    redis.conf中的maxmemory-samples参数用来指定每次检测几条数据，默认5

    对CPU不友好，对内存友好

    redis.conf中的maxmemory参数配置了redis的最大内存，maxmemory-policy配置了内存淘汰策略，当redis内存达到最大后，会根据内存淘汰策略淘汰部分数据。

    redis提供了8种内存淘汰策略：

        no-eviction：当内存达到最大后，新数据不能写入，会报错

        allkeys-lru：当内存达到最大后，淘汰最近最少使用的数据（最常用的策略）

        allkeys-random：当内存达到最大后，随机淘汰

        allkeys-lfu：当内存达到最大后，淘汰最少使用的数据

        volatitle-lru：当内存达到最大后，从设置了过期键的数据中，淘汰最近最少使用的数据

        volatitle-random：当内存达到最大后，从设置了过期键的数据中，随机淘汰

        volatitle-lfu：当内存达到最大后，从设置了过期键的数据中，淘汰最少使用的数据

        volatitle-ttl：当内存达到最大后，淘汰最早过期的数据

    标准的LRU算法需要维护一个链表，当某个数据被使用时就把它放到链表头部，这样就保证了链表是按照使用时间排序的，当需要淘汰数据时，就从链表尾部删除部分数据。

    标准LRU算法要进行大量的计算，redis采取了近似LRU算法的 *** 作。

    redis给每个键维护了一个24bit的属性字段，用来记录最后一次使用的时间戳。redis根据maxmemory-samples随机抽取一部分数据，将最旧的数据淘汰，指到内存降下来。后来redis又引入了淘汰池，淘汰池内的数据量等于maxmemory-samples，每次淘汰时将随机抽取的数据和淘汰池中的数据合并，淘汰最旧的数据，然后将剩余最旧的数据维护到淘汰池中，等待下次循环。

    为什么需要LFU算法？

    现在假设这种场景：redis中有两个键A和B，其使用频率如上面所示，当到达$时，因为A的使用时间比B晚，按照LRU算法会淘汰B，但是从使用频率上看，B明显比A使用的更频发，应该淘汰A。

    为了解决上面的问题，Redis引入了LFU算法，淘汰最少使用的数据。原理如下：

    LFU给每个数据维护了一个计数器，每次使用都会使计数器增加，淘汰使用次数最少的键。但是这样又有新的问题：

    ①新的key如果计数器为0，可能就会一直被淘汰

            redis解决方案：redis给每个新的键的计数器一个初始值

    ②某个键可能前一段时间被频繁使用，但是一段时间后使用频率就会下降。

            redis解决方案：如果某个键一段时间不使用，计数器会减小

  

Sorted Set，和set相比，增加权重参数score(浮点数)有序排列。Redis唯一可 根据成员访问 ，又可以 根据分值排序 ，访问元素结构。

场景：在线用户列表，各种礼物排行榜 ，d幕消息（可以理解为 按消息维度的消息排行榜 ）等信息，适合使用Redis中的SortedSet结构进行存储。

概要：原理（ziplist，skiplist，例子， *** 作）、  红黑树比较、    score相同，怎么排序

底层ziplist   或  HashMap和跳跃表(SkipList) 有序集合 

元素数 <128个 ，所有成员长度 <64字节 。都可通过zset-max-ziplist-entries和zset-max-ziplist-value来修改。

紧凑 压缩 列表节点 来保存，第一个节点存 member ，第二个存score， 按score从小到大排序

底层是 zset（1字典，跳跃表） 和一个。

    1） HashMap： 放 成员 到 score映射     O(1) ，共享相同元素member和score，因此不会浪费额外的内存

    2） 跳跃表： 放所有成员，依据HashMap的score,查找效率高，链表增加跳跃功能，O(logN)

插入或查找：O（1）获得节点分值，遍历跳跃表，根据分值到合适位置

新链表，包含原来一半，沿新查。 遇大节点，回原查。 7比较，19比较，比26小，回原链），比22要大，23比26小，23不存在

再增加，第三层链表： 查快 。 插/删重新进行调整，退化O(n)。

解决办法： 不要求 上下 相邻 链表间，节点个数 严格对应 ，如，一个节点随机出 层数3 ，那么就把它链入到第1层到第3层这三层链表中。

插入， 不影响 其它节点 层数 。只 修改 插入节点 前后指针 ，降低插入复杂度。 插入性能 明显优于 平衡树

查： 若干层稀疏链表，先查高层， 逐层降低 ，最终降到第1层。跳一些节点，加快速度。实际 按key(score)排序

基本 *** 作

1、 内存： 占更 小 ，更新 更节约、更灵活

2、ZRANGE或ZREVRANGE *** 作，跳表作为链表 遍历 ，和平衡树一样

3、简单： 易于实现，调试。

4、插入/删除，不需调整很多

（1）AVL 树 查询效率 严格 O(logN) ，插入需 多次旋转 ，导致插入 效率较低 ，才有更实用 红黑树 。

（2）红黑树 并发环境不方便， 更新 数据时， Skip更新较少，锁的也少 ，而红黑树有 平衡的过程 （涉及到较多节点）， 锁住更多节点，降低并发性 。

（3）SkipList 优势 实现简单 ，红黑树2天，SkipList2个小时实现。

用字典排序，“ABCDEFG”，首字母相同，比较后面的

https://www.jianshu.com/p/cc379427ef9d

https://blog.csdn.net/liyuxing6639801/article/details/105252293

---