Redis 引发的思考：能用就行

最近从 Redis 的设计中，想到一些解决问题的思维方式。那就是如果想从正面完美地解决某个问题不容易实现，不如从另一个角度出发，”不完美”地解决问题。

比如下面的 Redis 开发者在解决下面的问题时：

炫杉：菜鸟瞎分析，大佬勿喷。

跳表层数的确定

完美层数的问题

众所周知，跳表的层数在下一层与上一层节点数量为2:1时会达到最佳的效果。但是如果按照这个来设计，跳表中节点的变更可能会引发类似『平衡树』的连锁反应。怎么样用最简单的实现去接近这个预期呢？

Redis 的解法

在Redis的跳表实现中，每个新插入的节点的层数是通过一个随机过程确定的。这个随机过程通常遵循一种“抛硬币”的策略，即每次“抛硬币”正面朝上就增加一层，直到出现反面为止，或者达到跳表定义的最大层数。这个概率通常设为1/2，意味着平均来看，每两个节点就会有一个节点具有更高的层数。

下面是Redis跳表层级选择的伪代码：

int zslRandomLevel(void) {
    int level = 1;
    while ((rand()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

在这段代码中：

ZSKIPLIST_P 是概率值，通常设置为 0.25，意味着每个节点有 1/4 的概率增加一个层级。

rand()&0xFFFF 产生一个随机数，并且通过位运算保留低16位，使得随机数范围在 0 到 65535 之间。

(ZSKIPLIST_P * 0xFFFF) 计算得到的阈值，如果随机数小于这个阈值，层数就增加。
ZSKIPLIST_MAXLEVEL 是跳表的最大层数限制，通常设置为 32 或其他适当的值。

这种随机化的层数分配策略使得跳表的高层链表中的节点数量逐渐减少，从而使得搜索时能够快速跳过大量低层节点，达到快速查找的目的。同时，由于层数的选择是随机的，这也保证了跳表结构在长期运行过程中不会倾向于某种特定的形态，从而保持操作的效率。

一个新创建的跳表的头节点的层数是由 ZSKIPLIST_MAXLEVEL 定义的。这不意味着所有的层都会被立即使用，而是这些层都是可用的，以便在插入新节点时如果随机过程决定一个节点应该有更多的层，这些层就已经准备好了。

在Redis的源代码中，ZSKIPLIST_MAXLEVEL 的值通常被定义为32，这意味着跳表的头节点会有32个前进指针，对应32个可能的层。然而，实际使用的层数通常会远远少于这个值，因为新节点的层数是通过上面描述的随机过程来确定的，而且这个过程会随着层数的增加而逐渐减少新层的概率。

过期 Key 的淘汰

Redis 中过期 Key 被存到了一个哈希表(被称为过期字典)里。里面有过期的时间。（这个字典里 key 是指针指向键对象，value 是 longlong，其实就是过期时间）

Redis 采用定期删除+惰性删除组合的策略进行过期Key 的清理。

其中惰性删除很好理解，被访问的时候才去校验。

但是定期删除，如果每次都是扫描整个哈希表来判断。就会非常耗时。

Redis 采用的策略是。随机拿20个，如果有超过25%的都过期了，则再来20个，如此反复。最后为了防止一直都有，也有个超时时间的控制。

炫杉：思想都很相似。没法完全删掉，我就删一部分。

内存淘汰

Redis中有多种缓存淘汰策略，比如 volatile-lru、 allkeys-lru、 volatile-random、 allkeys-random、 volatile-ttl 等。

在LRU这个方案中，Redis 又使用了『概率』的玩法：随机地从数据集中抽取一定数量的键（这个数量通过配置的 maxmemory-samples 设置）。然后，Redis比较这些被抽样的键的最后访问时间，并淘汰其中最”老”的一个或多个键。maxmemory-samples 的值越高，Redis的LRU算法越精确，但是相应的计算开销也越大。