关于redis:闲扯Redis十一Redis-有序集合对象底层实现

一、前言

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

原文解析

备注： 本节中波及到的跳跃表实现，曾经在上节《闲扯Redis十》Redis 跳跃表的构造实现一文中详情剖析过，本文中将间接援用，不再赘述。

二、命令实现

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

命令	ziplist 编码的实现办法	zset 编码的实现办法
ZADD	调用 ziplistInsert 函数，将成员和分值作为两个节点别离插入到压缩列表。	先调用 zslInsert 函数，将新元素增加到跳跃表，而后调用 dictAdd 函数，将新元素关联到字典。
ZCARD	调用 ziplistLen 函数，取得压缩列表蕴含节点的数量，将这个数量除以 2 得出汇合元素的数量。	拜访跳跃表数据结构的 length 属性，间接返回汇合元素的数量。
ZCOUNT	遍历压缩列表，统计分值在给定范畴内的节点的数量。	遍历跳跃表，统计分值在给定范畴内的节点的数量。
ZRANGE	从表头向表尾遍历压缩列表，返回给定索引范畴内的所有元素。	从表头向表尾遍历跳跃表，返回给定索引范畴内的所有元素。
ZREVRANGE	从表尾向表头遍历压缩列表，返回给定索引范畴内的所有元素。	从表尾向表头遍历跳跃表，返回给定索引范畴内的所有元素。
ZRANK	从表头向表尾遍历压缩列表，查找给定的成员，沿途记录通过节点的数量，当找到给定成员之后，途经节点的数量就是该成员所对应元素的排名。	从表头向表尾遍历跳跃表，查找给定的成员，沿途记录通过节点的数量，当找到给定成员之后，途经节点的数量就是该成员所对应元素的排名。
ZREVRANK	从表尾向表头遍历压缩列表，查找给定的成员，沿途记录通过节点的数量，当找到给定成员之后，途经节点的数量就是该成员所对应元素的排名。	从表尾向表头遍历跳跃表，查找给定的成员，沿途记录通过节点的数量，当找到给定成员之后，途经节点的数量就是该成员所对应元素的排名。
ZREM	遍历压缩列表，删除所有蕴含给定成员的节点，以及被删除成员节点旁边的分值节点。	遍历跳跃表，删除所有蕴含了给定成员的跳跃表节点。并在字典中解除被删除元素的成员和分值的关联。
ZSCORE	遍历压缩列表，查找蕴含了给定成员的节点，而后取出成员节点旁边的分值节点保留的元素分值。	间接从字典中取出给定成员的分值。

三、构造解析

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

压缩列表形式

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

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

redis> ZADD price 8.5 apple 5.0 banana 6.0 cherry(integer) 3

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

跳跃表和字典形式

skiplist 编码的有序汇合对象应用 zset 构造作为底层实现，一个 zset 构造同时蕴含一个字典和一个跳跃表：

typedef struct zset {    zskiplist *zsl;    dict *dict;} zset;

zset 构造中的 zsl 跳跃表按分值从小到大保留了所有汇合元素，每个跳跃表节点都保留了一个汇合元素：跳跃表节点的 object 属性保留了元素的成员，而跳跃表节点的 score 属性则保留了元素的分值。通过这个跳跃表，程序能够对有序汇合进行范畴型操作，比方 ZRANK 、ZRANGE 等命令就是基于跳跃表 API 来实现的。
除此之外， zset 构造中的 dict 字典为有序汇合创立了一个从成员到分值的映射，字典中的每个键值对都保留了一个汇合元素：字典的键保留了元素的成员，而字典的值则保留了元素的分值。通过这个字典，程序能够用 O(1) 复杂度查找给定成员的分值， ZSCORE 命令就是依据这一个性实现的，而很多其余有序汇合命令都在实现的外部用到了这一个性。
有序汇合每个元素的成员都是一个字符串对象，而每个元素的分值都是一个 double 类型的浮点数。值得一提的是，尽管 zset 构造同时应用跳跃表和字典来保留有序汇合元素，但这两种数据结构都会通过指针来共享雷同元素的成员和分值，所以同时应用跳跃表和字典来保留汇合元素不会产生任何反复成员或者分值，也不会因而而节约额定的内存

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

留神:
为了展现不便，图 8-17 在字典和跳跃表中反复展现了各个元素的成员和分值，但在理论中，字典和跳跃表会共享元素的成员和分值，所以并不会造成任何数据反复，也不会因而而节约任何内存。

四、编码转换

当有序汇合对象能够同时满足以下两个条件时，对象应用 ziplist 编码：
1.有序汇合保留的元素数量小于 128 个；
2.有序汇合保留的所有元素成员的长度都小于 64 字节；
不能满足以上两个条件的有序汇合对象将应用 skiplist 编码。

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

1.以下状况展现了有序汇合对象因为蕴含了过多元素而引发编码转换：

# 对象蕴含了 128 个元素redis> EVAL "for i=1, 128 do redis.call('ZADD', KEYS[1], i, i) end" 1 numbers(nil)redis> ZCARD numbers(integer) 128redis> OBJECT ENCODING numbers"ziplist"# 再增加一个新元素redis> ZADD numbers 3.14 pi(integer) 1# 对象蕴含的元素数量变为 129 个redis> ZCARD numbers(integer) 129# 编码已扭转redis> OBJECT ENCODING numbers"skiplist"

2.以下状况展现了有序汇合对象因为元素的成员过长而引发编码转换：

# 向有序汇合增加一个成员只有三字节长的元素redis> ZADD blah 1.0 www(integer) 1redis> OBJECT ENCODING blah"ziplist"# 向有序汇合增加一个成员为 66 字节长的元素redis> ZADD blah 2.0 oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo(integer) 1# 编码已扭转redis> OBJECT ENCODING blah"skiplist"

五、要点总结

1）有序汇合的编码能够是 ziplist 或者 skiplist。
2）一个 zset 构造同时蕴含一个字典和一个跳跃表。
3）zset 构造跳跃表和字典通过指针来共享雷同元素的成员和分值。
4）有序汇合对象 ziplist 或者 skiplist编码，符合条件时可产生编码转换。