Redis 中常用算法

sds

quicklist

skiplist

skiplist 本质也是一种查找结构，用于解决算法中的查找问题，即根据给定的 key，快速查到他所在的位置或者对应的 value。一般查找问题的解法分为两个大类：一个是基于各种平衡树，一个是基于哈希表。但是 skiplist 比较特殊，它没法归属到这两个大类中。

skiplist 跳表又称跳跃表，指的是除了最下面第一层链表之外，会产生若干层稀疏的链表，这些链表里面的指针故意跳过一些节点（而且越高层的链表跳过的节点越多）。这就使得我们在查找数据的时候能够现在高层的链表中进行查找，然后珠层减低，最终见到第一层链表来精确地确定数据位置。

skiplist与平衡树、哈希表的比较

skiplist 和各种平衡树（如 AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个 key 的查找，不适宜做范围查找。
在做范围查找的时候，平衡树比 skiplist 操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其他不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在 skiplist 上进行范围查找就非常简单，只需要在找到小值之后，对第一层链表进行若干步的遍历就可以实现。
平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而 skiplist 的插入和删除只需要修改相邻节点的指针，操作简单又快速。
从内存占用来说，skiplist 比平衡树更灵活一些。一般来说，平衡树每个节点包含 2 个指针（分别指向左右子树），而 skiplist 每个节点包含的指针数目平均为 1/(1-p) ，具体取决于参数 p 的大小。如果想 Redis 里的实现一样，取 p = 1/4，那么平均每个节点包含 1.33 个指针，比平衡树更有优势。
查找单个 key， skiplist 和平衡树的时间复杂度都为 O(log n)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近 O（1），性能更高一些。所以我们平常使用的各种 Map 或 dictionaty 结构，大都是基于哈希表实现的。
从算法实现难度上来比较，skiplist 比平衡树要简单得多。

Redis 中 skiplist 的实现

分数（score）允许重复，即 skiplist 的 key 允许重复。
在比较时，不仅比较分数（相当于 skiplist 的 key），还比较数据本身。在 Redis 的 skiplist 实现中，数据本身的内容唯一标识这份数据，而不是由 key 来唯一标识。另外，当多个元素分数相同的时候，还需要根据数据内容来进字典排序。
第一层链表不是一个单向链表，而是一个双向链表。这是为了方便以倒叙方式获取一个范围内的元素。
在 skiplist 中可以很方便计算出每个元素的排名（rank）。

Redis 中 zset 包含一个 dict + skiplist。dict 用来查询数据到分数（score）的对应关系，而 skiplist 用来根据分数查询数据（可能是范围查找）。

lru

迁移槽和数据的流程

目标节点准备导入槽
源节点准备导出槽
获取 slot 下个键
批量迁移相关键的数据
重复 3 4 步骤
通知槽分配给目标节点

键命令执行步骤

一、计算槽

根据键的有效部分使用 CRC16 函数计算出散列值，再取对 16383 的余数，使每个键都可以映射到 0 ~ 16383 槽范围内

二、查找槽所对应的节点

通常集群客户端都采用一种实现：Smart （智能）客户端

Smart 客户端通过在内部维护 slot -> node 的映射关系，本地就可以实现键到节点的查找，从而保证 IO 效率的最大化，而 MOVED 重定向负责协助 Smart 客户端更新 slot -> node 映射

本文由 Meridian 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 6,2020

Redis中常用算法