《闲扯Redis十一》Redis 有序集合对象底层实现

一、前言

Redis提供了5种数据类型：String（字符串）、Hash（哈希）、List（列表）、Set（集合）、Zset（有序集合），理解每种数据类型的特点对于redis的开发和运维非常重要。

备注：本节中涉及到的跳跃表实现，已经在上节《闲扯Redis十》Redis 跳跃表的结构实现一文中详情分析过，本文中将直接引用，不再赘述。

二、命令实现

 因为有序集合键的值为有序集合对象，所以用于有序集合键的所有命令都是针对有序集合对象来构建的。

三、结构解析

 由前文和上图可知，有序集合的编码可以是 ziplist 或者 skiplist 。ziplist 编码的有序集合对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员（member），而第二个元素则保存元素的分值（score）。

压缩列表方式

压缩列表内的集合元素按分值从小到大进行排序， 分值较小的元素被放置在靠近表头的方向， 而分值较大的元素则被放置在靠近表尾的方向。

例如，如果我们执行以下 ZADD 命令， 那么服务器将创建一个有序集合对象作为 price 键的值：

如果 price 键的值对象使用的是 ziplist 编码， 那么这个值对象将会是图 8-14 所示，， 而对象所使用的压缩列表则会是 8-15 所示。

跳跃表和字典方式

 skiplist 编码的有序集合对象使用 zset 结构作为底层实现， 一个 zset 结构同时包含一个字典和一个跳跃表：

zset 结构中的 zsl 跳跃表按分值从小到大保存了所有集合元素， 每个跳跃表节点都保存了一个集合元素：跳跃表节点的 object 属性保存了元素的成员， 而跳跃表节点的 score 属性则保存了元素的分值。通过这个跳跃表， 程序可以对有序集合进行范围型操作， 比如 ZRANK 、ZRANGE 等命令就是基于跳跃表 API 来实现的。

除此之外， zset 结构中的 dict 字典为有序集合创建了一个从成员到分值的映射， 字典中的每个键值对都保存了一个集合元素：字典的键保存了元素的成员， 而字典的值则保存了元素的分值。通过这个字典， 程序可以用 O(1) 复杂度查找给定成员的分值， ZSCORE 命令就是根据这一特性实现的， 而很多其他有序集合命令都在实现的内部用到了这一特性。

有序集合每个元素的成员都是一个字符串对象， 而每个元素的分值都是一个 double 类型的浮点数。值得一提的是， 虽然 zset 结构同时使用跳跃表和字典来保存有序集合元素， 但这两种数据结构都会通过指针来共享相同元素的成员和分值， 所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或者分值， 也不会因此而浪费额外的内存

skiplist 编码的有序集合对象， 那么这个有序集合对象将会是图 8-16 所示， 而对象所使用的 zset 结构将会是图 8-17 所示。

注意: 为了展示方便，图 8-17 在字典和跳跃表中重复展示了各个元素的成员和分值，但在实际中，字典和跳跃表会共享元素的成员和分值，所以并不会造成任何数据重复，也不会因此而浪费任何内存。

四、编码转换

当有序集合对象可以同时满足以下两个条件时， 对象使用 ziplist 编码：

有序集合保存的元素数量小于 128 个；

有序集合保存的所有元素成员的长度都小于 64 字节；

不能满足以上两个条件的有序集合对象将使用 skiplist 编码。

注意: 以上两个条件的上限值是可以修改的， 具体请看配置文件中关于zset-max-ziplist-entries选项和zset-max-ziplist-value选项的说明。对于使用 ziplist 编码的有序集合对象来说， 当使用 ziplist 编码所需的两个条件中的任意一个不能被满足时， 程序就会执行编码转换操作， 将原本储存在压缩列表里面的所有集合元素转移到 zset 结构里面， 并将对象的编码从 ziplist 改为 skiplist 。

五、要点总结

1）有序集合的编码可以是 ziplist 或者 skiplist。

2）一个 zset 结构同时包含一个字典和一个跳跃表。

3）zset 结构跳跃表和字典通过指针来共享相同元素的成员和分值。

4）有序集合对象 ziplist 或者 skiplist编码，符合条件时可发生编码转换。