Redis-数据结构详解（下）
上期，我们详细介绍了 Redis 的3种底层数据结构。下面我们介绍其余的数据结构，来看看它们是如何实现的。
压缩列表
压缩列表是 Redis 为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序性数据结构，我们可以从源码的注释中看到官方对它的定义。
The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values, where integers are encoded as actual integers instead of a series of characters. It allows push and pop operations on either side of the list in O(1) time. However, because every operation requires a reallocation of the memory used by the ziplist, the actual complexity is related to the amount of memory used by the ziplist.也就是说，ziplist 是一种特殊编码的双向链表，目标是为了提高内存的存储效率。它的每个节点可用于存储字符串或整数值，其中整数是按真正的整数进行编码，而不是一系列字符。它允许在列表的任意一端以 O(1) 的时间复杂度提供 push 和 pop 操作。但是，它的每个操作都需要进行内存重分配，实际的复杂性与 ziplist 使用的内存大小有关，也就是和它的存储的节点个数有关。
实际上，ziplist 充分体现了 Redis 对于存储效率的追求。一个普通的双向链表，链表中每一项都占用独立的一块内存，各项之间用指针连接起来，这种方式会带来大量的内存碎片，而且地址指针也会占用额外的内存。而 ziplist 却是将表中每一项存放在前后连续的地址空间内，一个 ziplist 整体占用一大块内存。从这种方式理解，其实它是一个表（list），并不是一个链表（linked list）。
另外，ziplist 为了在细节上节省内存，对于值的存储采用了变长的编码方式，也就是说，对于大的整数，就多用一些字节来存储，而对于小的整数，就少用一些字节来存储。我们接下来就会讨论到这些实现细节。
实现
从源码注释中可以看到 ziplist 的组成结构：
... 它并没有像其他数据结构一样，用自定义的 struct 之类的来表达，而就是简单的 unsigned char *，可以从它的创建 API 中就可以看出。
// 创建一个新的压缩列表
unsigned char *ziplistNew(void) {
unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
unsigned char *zl = zmalloc(bytes);
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
ZIPLIST_LENGTH(zl) = 0;
zl[bytes-1] = ZIP_END;
return zl;
}其中，各个部分的含义如下：
| 属性 | 说明 |
|---|---|
| zlbytes | uint32_t，记录整个压缩列表占用的内存字节数，在对压缩列表进行内存重分配或者计算zlend 的位置时使用。 |
| zltail | uint32_t，记录压缩列表表尾节点距离起始地址的字节数，可以无需遍历整个列表就可以确定表尾节点的地址，方便进行 pop 等操作。 |
| zllen | uint16_t，记录压缩列表包含的节点数量，但当数量超过 2^16 - 2 时，这个值被设为 2^16 - 1，我们需要遍历整个列表，才能知道它包含多少个节点。 |
| entry | 压缩列表的各个节点，真正存放数据的地方，节点的长度由保存的内容决定。 |
| zlend | uint8_t，标记压缩列表的末端，值固定等于 255。 |
有时
| 属性 | 说明 |
|---|---|
| prevlen | 记录了压缩列表前一个节点的长度，此属性的长度为 1 字节或 5 字节，当前一个节点的长度小于 254 字节，长度为 1 字节；当大于等于 254 字节时，为 5 字节，其中第一个字节固定为254，后 4 个字节记录其长度。 |
| encoding | 记录了节点的 content 属性所保存数据的类型以及长度。当保存的是字符串时，前两位为 00、01 或者 10；当保存的是整数值时，前两位为 11。 |
| entry-data | 负责保存节点的值。 |
上面介绍中，entry 属性中保存的 prevlen 有 1 字节和 5 字节，所以就会出现一种情况：当压缩列表存储的节点 e1 到 eN 的长度都介于 250 字节到 253 字节之间，如果在 e1 之前插入了一个长度大于等于 254 字节的新节点，由于 prevlen 的改变，会导致连锁更新，时间复杂度为 O(n^2)。虽然连锁更新的复杂度较高，但它真正造成性能问题的概率是很低的，原因如下：
- 压缩列表要恰好有多个连续的、长度介于 250 字节到 253 字节之间的节点，连锁更新才会被触发，但在实际中，这种情况很少见。
- 即使出现，但只要被更新的节点数量不多，就不会对性能造成任何影响。
ziplist 是 哈希对象的底层实现之一，当一个哈希对象包含少量键值对，并且每个键值对要么就是小整数值，要么就是长度比较短的字符串时，Redis 就会使用 ziplist 来作为哈希对象的底层实现。在 Redis 3.2 版本之前，ziplist 也是列表对象的底层实现之一，但 3.2 版本之后被 quicklist 取代。
跳跃表 跳跃表是一种有序数据结构，通过在每个节点中维持多个指向其他节点的指针，来达到快速访问节点的目的。相比平衡树，其实现简单，而且在大部分情况下的效率能和平衡树相媲美。
实现
// 跳跃表节点实现
typedef struct zskiplistNode {
// 成员对象（不可与其他节点重复）
sds ele;
// 节点分值（可重复，所有节点按此属性从小到大排序）
double score;
// 后退指针
struct zskiplistNode *backward;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned long span;
} level[];
} zskiplistNode;
// 跳跃表实现
typedef struct zskiplist {
// 表头指针，表尾指针
struct zskiplistNode *header, *tail;
// 跳跃表中节点的数量（不含表头节点）
unsigned long length;
// 跳跃表中层数最大的节点（不含表头节点）
int level;
} zskiplist;
多个跳跃表节点组成了跳跃表，程序可以以 O(1) 的时间复杂度获取表头、表尾指针以及节点的数量；跳跃表中以 score 属性的大小进行排序，score 相同，则以成员 ele 属性的字典序排列；新增节点的层数根据幂次定律取得一个介于 1 和 32 之间的值。
文章图片
跳跃表的实现中，存在着一个不填充数据，但满层的头结点，头结点存在的原因如下：
- zskiplist 的头指针 head 不会随数据的变动而变动。
- 头结点的层数达到了最大值 32，在第一次查找时，可以和 zskiplist 中 level 属性定位查找节点，没有头结点的话，只能从第一个填充了数据的节点开始，但它的层数可能不是分层最高的，会拖慢查询的效率。
Redis 使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员是比较长的字符串时，Redis 就会使用跳跃表来作为有序集合键的底层实现。这里就有个问题，为什么 Redis 不使用平衡树呢？原因有以下几点：
- 从算法实现难度比较，skiplist 比平衡树要简单得多，更加直观，便于调试。
- 从区间查找效率比较，平衡树比 skiplist 操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在 skiplist 上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。
- 从插入和删除效率比较，平衡树的插入和删除操作可能引发子树的调整，需要左旋或者右旋保证平衡，逻辑复杂，而 skiplist 的插入和删除只需要修改相邻节点的指针，操作简单又快速。
- 从内存占用上比较，skiplist 比平衡树更灵活一些。一般来说，平衡树每个节点包含 2 个指针（分别指向左右子树），而 skiplist 每个节点包含的指针数目平均为 1/(1-p)，具体取决于参数p的大小。如果像 Redis 里的实现一样，取 p = 1/4，那么平均每个节点包含 1.33 个指针，比平衡树更有优势。
实现
// 整数集合实现
typedef struct intset {
// 编码方式
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组
int8_t contents[];
} intset;
其中，
1.encoding 属性的值有 3 个
- INTSET_ENC_INT16：代表元素为 16 位的整数
- INTSET_ENC_INT32：代表元素为 32 位的整数
- INTSET_ENC_INT64：代表元素为 64 位的整数
文章图片
升级
当整数集合中元素的类型都是 int16_t 类型的值时，如果你需要添加一个 int32_t 类型的整数，会发生什么呢？这时就会执行升级操作，来保证大类型可以被放入数组。升级可表述为以下几步：
- 按照升级后的类型和元素数量，分配内存空间。
- 将元素的类型升级为新元素的类型，在保证有序性不变的前提下，放在新的位置上。
- 将新元素添加到数组中（因为新元素的长度肯定最大，所以总是在头或尾两个位置上）
那么，提到升级，大家肯定会想到是不是有降级，但整数集合不支持降级，原因就是，既然已经有大的元素插入，那么以后大概率也会有，降级后，再插入大类型的整数，还会进行升级操作，所以降级操作价值不大，而且降级涉及内存重分配，也不是一种廉价的操作。
使用场景
整数集合是集合对象的底层实现之一，当一个集合只包含整数值元素，并且元素数量不多时，Redis 就会使用整数集合作为集合对象的底层实现。
快表 快表是 Redis 在 3.2 版本中提供的一种数据结构，是一个基于 ziplist 的双向链表，从源码注释中对快表的定义就可以看出这一点。
A doubly linked list of ziplistsquicklist 是 ziplist 和 linkedlist 的混合体，它将 linkedList 按段切分，每一段使用 ziplist 来紧凑存储，多个 ziplist 之间使用双向指针链接起来。quicklist 为什么要这样设计呢，其实就是在空间和时间上进行的平衡：
- 附加空间：双向链表每个节点除了保存数据，还要保存两个指针，占去 16 个字节 (64bit 系统的指针是 8 个字节)。
- 内存碎片：双向链表的各个节点是单独的内存快，地址不连续，节点过多容易造成内存碎片，影响内存管理效率。
- ziplist 是一整块连续内存，所以存储效率很高。但它不利于进行修改操作，每次数据变动都会引发一次内存的 realloc。特别是当 ziplist 很长的时候，一次 realloc 可能会导致大批量的数据拷贝，进一步降低性能。
- 每个 quicklist 节点上的 ziplist 越短，则内存碎片越多，有可能在内存中产生很多无法被利用的小碎片，从而降低存储效率。这种情况的极端是每个 quicklist 节点上的 ziplist 只包含一个数据项，这就蜕化成一个普通的双向链表。
- 每个 quicklist 节点上的 ziplist 越长，则为 ziplist 分配大块连续内存空间的难度就越大。有可能出现内存里有很多小块的空闲空间（它们加起来很多），但却找不到一块足够大的空闲空间分配给 ziplist 的情况。这同样会降低存储效率。这种情况的极端是整个 quicklist 只有一个节点，所有的数据项都分配在这仅有的一个节点的 ziplist 里面，这其实就蜕化成一个 ziplist。
- 当配置为正值时，表示每个 quicklist 节点上的 ziplist 的最大数据项个数。例如，list-max-ziplist-size = 5 时，表示 ziplist 最多包含 5 个数据项。
- 当配置为负值时，表示按照占用字节数来限定每个 quicklist 节点上的 ziplist 长度。但这时，它只能取 -1 到 -5 这五个值，每个值含义如下：
| 值 | 说明 |
|---|---|
| -5 | 每个 quicklist 节点上的 ziplist 大小不能超过64 Kb。 |
| -4 | 每个 quicklist 节点上的 ziplist 大小不能超过32 Kb。 |
| -3 | 每个 quicklist 节点上的 ziplist 大小不能超过16 Kb。 |
| -2 | 每个 quicklist 节点上的 ziplist 大小不能超过8 Kb（默认值）。 |
| -1 | 每个 quicklist 节点上的 ziplist 大小不能超过4 Kb。 |
- 0: 是个特殊值，表示都不压缩。这是 Redis 的默认值。
- 1: 表示 quicklist 两端各有 1 个节点不压缩，中间的节点压缩。
- 2: 表示 quicklist 两端各有 2 个节点不压缩，中间的节点压缩。
- 3: 表示 quicklist 两端各有 3 个节点不压缩，中间的节点压缩。
- 依此类推...
实现
// 快表节点
typedef struct quicklistNode {
// 上一个节点
struct quicklistNode *prev;
// 下一个节点
struct quicklistNode *next;
// 数据指针，如果未压缩，指向一个ziplist，压缩后指向quicklistLZF
unsigned char *zl;
// 指向的压缩列表的大小，如果被压缩，仍是未压缩前的大小
unsigned int sz;
/* ziplist size in bytes */
// ziplist中包含的数据项的个数
unsigned int count : 16;
/* count of items in ziplist */
// 是否被压缩，1：未压缩 2：压缩（LZF）
unsigned int encoding : 2;
/* RAW==1 or LZF==2 */
// 数据容器，表示底层用什么数据结构存储数据，目前只有ziplist一个容器
unsigned int container : 2;
/* NONE==1 or ZIPLIST==2 */
// 如果是一个被压缩的数据，因使用类似lindex这样的命令要暂时解压，需要标记一下，等后面重新压缩
unsigned int recompress : 1;
/* was this node previous compressed? */
// Redis自动化测试中使用的字段
unsigned int attempted_compress : 1;
/* node can't compress;
too small */
// 扩展字段，供未来扩展使用
unsigned int extra : 10;
/* more bits to steal for future usage */
} quicklistNode;
// 被压缩的ziplist结构
typedef struct quicklistLZF {
/// 压缩后的ziplist大小
unsigned int sz;
/* LZF size in bytes*/
// 是个柔性数组，存放被压缩后ziplist的字节数组
char compressed[];
} quicklistLZF;
// 快表结构
typedef struct quicklist {
// 表头节点
quicklistNode *head;
// 表尾节点
quicklistNode *tail;
// 所有ziplist数据项的总和
unsigned long count;
/* total count of all entries in all ziplists */
// quicklist节点的数量
unsigned long len;
/* number of quicklistNodes */
// 单个节点的填充因子，存放list-max-ziplist-size参数的值
int fill : QL_FILL_BITS;
/* fill factor for individual nodes */
// 节点压缩深度，存放list-compress-depth参数的值
unsigned int compress : QL_COMP_BITS;
/* depth of end nodes not to compress;
0=off */
unsigned int bookmark_count: QL_BM_BITS;
quicklistBookmark bookmarks[];
} quicklist;
文章图片
上图中是一个含有 3 个节点的 quicklist，其中每个节点有 4 个数据项，两边的节点是未压缩的，中间的节点是压缩的。
使用场景
Redis 使用快表作为列表对象的底层实现，不过在 3.2 版本之前，列表对象的底层实现是链表或者压缩列表，使用快表替换链表和压缩列表的实现原因，上面已经讲解，这里就不再赘述了。
zipmap zipmap 看名字，感觉和 ziplist 很像，zip 有压缩的意思，map 说明是一个有关于键值对的数据结构，可以猜测是对 map 实现上的一种内存优化，下面我们就来验证一下。
String -> String Map data structure optimized for size.从上述源码注释中得知，zipmap 其实就是一个 String，是一个压缩了的 map 结构，分配了一段连续的内存空间，用来保存连续的 key-value 集合。它的特点是维护 map 所需要的额外信息很少，对于一个键值对最少只需要额外的三个字节来描述。不过这样做的后果就是，对 map 操作时需要进行遍历，时间复杂度为 O(n)，但由于键值对的个数不会很多，所以并不会有性能问题。
实现
zipmap 的数据结构特别简单，简单到新创建后的 zipmap 只有两个字节，其中，首字节保存长度，尾字节保存结尾标志 ZIPMAP_END，其中 ZIPMAP_END = 255，可以从 zipmap 的创建API就可以看出来。
/* Create a new empty zipmap. */
unsigned char *zipmapNew(void) {
unsigned char *zm = zmalloc(2);
zm[0] = 0;
/* Length */
zm[1] = ZIPMAP_END;
return zm;
}那么 zipmap 是怎样保存键值对的呢，源码注释中有一个例子，如果要保存 "foo" => "bar"，"hello" => "world"，那么会是这样：
"foo""bar""hello""world" 其中
| 属性 | 说明 |
|---|---|
| zmlen | 记录键值对的个数。当其值小于 254 时，可以从该属性直接得到键值对的个数；当大于等于 254 时，需要遍历 zipmap 来获取键值对个数。 |
| len | 记录保存的 key 或者 value 的字符串的长度，占用 1 个字节或者 5 个字节。当其长度小于 254 时，占用 1 个字节；当大于等于 254 时，第一个字节设置为 ZIPMAP_BIGLEN = 254，后四个字节用来记录实际长度。 |
| free | 记录 value 未使用的空闲字节数。比如，当 key 为 "foo"，修改其 value 从 "bar" -> "hi"，那么之前的 1 字节就会记录到 free 中，当然，free 是有上限的，当大于等于ZIPMAP_VALUE_MAX_FREE = 4，会进行 resize，以保证字符串尽可能紧凑，节省空间。 |
Redis 中的哈希键，当元素个数比较少时，会使用到 zipmap，当达到给定的个数时，会切换到字典。因为字典保存一个键值对需要的额外信息比较大 sizeof(struct dictEntry) = 24，而 zipmap 最少只需要三个字节，最多 11 个字节。在查询效率上，当数据量特别小的时候，顺序查询花费的时间成本虽然是 O(n)，但是 n 小，所以是可以接受的，这样做可以节约内存。不过，这是在 Redis 2.6 版本之前才有，在 2.6 版本及之后的版本中已经被 ziplist 替代，也就是说，当键值对比较少时，会采用 ziplist 去实现哈希类型的对象。
流 stream 是 Redis 5.0 版本新增加的数据结构，它底层数据的存储依赖于 一棵 radix tree，主要用于消息队列的实现，stream 可以说是 Redis 底层数据结构中最复杂的一个。
实现
typedef struct streamID {
// unix时间戳
uint64_t ms;
/* Unix time in milliseconds. */
// 序号
uint64_t seq;
/* Sequence number. */
} streamID;
typedef struct stream {
// 指向radix tree的指针
rax *rax;
/* The radix tree holding the stream. */
// stream 中保存的元素的数量，以消息ID为统计维度
uint64_t length;
/* Number of elements inside this stream. */
// stream中最后一个消息ID
streamID last_id;
/* Zero if there are yet no items. */
// 保存监听该stream的消费者信息
rax *cgroups;
/* Consumer groups dictionary: name -> streamCG */
} stream;
从上述实现中可以看出， streamID，也就是消息ID，是由时间戳 + 序号两部分组成，各占 64 位，一共 128 位，此 ID 可由 Redis 自动生成，或者自定义，为了保证消息的有序性，Redis 自动生成的 ID 是单调递增的。由于消息 ID 中包含了时间戳，为了避免 Redis 服务器时间错误，比如发生了时钟向后跳跃，stream 中都维护了一个 last_id，来记录最后一个消息 ID，若与 last_id 比较发现时间戳退后，则采用时间戳延用 last_id，递增序号的方式生成消息 ID（这也是序号使用 64 位表示的原因，保证有足够多的序号使用），从而保证消息 ID 的单调递增。
然后，我们再来看 rax 这个属性表示什么，从源码中的注释中可以得到答案，即 rax 是一棵 radix tree 的实现。
Rax -- A radix tree implementation.
typedef struct raxNode {
uint32_t iskey:1;
uint32_t isnull:1;
uint32_t iscompr:1;
uint32_t size:29;
unsigned char data[];
} raxNode;
typedef struct rax {
// radix tree头结点指针
raxNode *head;
// radix tree中存储元素的总数
uint64_t numele;
// radix tree中节点总数
uint64_t numnodes;
} rax;
下面我们来详细介绍一下 raxNode 的属性：
| 属性 | 说明 |
|---|---|
| iskey | 标识从根节点到当前节点保存的字符是否是完整的键。0：不是；1：是。 |
| isnull | value 值是否为 null，value 存储在 data 中。 |
| iscompr | 是否有压缩，决定了 data 存储的数据结构。 |
| size | 子节点的个数或压缩字符串的长度。 |
| data | 存储路由键、子节点指针和 value。 |
- 如果节点没有被压缩，那么会有 size 个子节点，每个子节点占1个字节，并且有 size 个子节点指针，指向每个子节点。
[header iscompr=0][abc][a-ptr][b-ptr][c-ptr](value-ptr?)- 如果节点是被压缩的，那么该节点只有 1 个子节点，占 size 个字节，也仅有 1 个子节点指针。
[header iscompr=1][xyz][z-ptr](value-ptr?)当我们使用 xadd key id field value [field value ...] 向其中添加消息时，还会涉及另外一个数据结构 listpack，它是什么，也可以从源码中得到答案：
Listpack -- A lists of strings serialization format其实也是一个字符串，和 zipmap 很相似，从创建一个新的 listpack 的 API 就可以看出。
unsigned char *lpNew(void) {
unsigned char *lp = lp_malloc(LP_HDR_SIZE+1);
if (lp == NULL) return NULL;
lpSetTotalBytes(lp,LP_HDR_SIZE+1);
lpSetNumElements(lp,0);
lp[LP_HDR_SIZE] = LP_EOF;
return lp;
}添加元素时，会先找到 radix tree 中的最后一个节点，校验这个节点的 data 是否超过配置规定的大小（从占用空间和元素总数上），没有超过，则使用这个空间；若超过，则会新创建一个 listpack 结构，一个新创建的 listpack 中 field 的组织方式如下：
+-------+---------+------------+---------+--/--+---------+---------+-+
| count | deleted | num-fields | field_1 | field_2 | ... | field_N |0|
+-------+---------+------------+---------+--/--+---------+---------+-+对于 value 的处理有两种方式，通常是以第一种方式组织，但当添加的 field 和原有的 field 相同时，就采用第二种方式。
// 方式1
+-----+--------+----------+-------+-------+-/-+-------+-------+--------+
|flags|entry-id|num-fields|field-1|value-1|...|field-N|value-N|lp-count|
+-----+--------+----------+-------+-------+-/-+-------+-------+--------+// 方式2
+-----+--------+-------+-/-+-------+--------+
|flags|entry-id|value-1|...|value-N|lp-count|
+-----+--------+-------+-/-+-------+--------+由于 stream 的实现比较复杂，涉及的内容比较多，后面会单独来讲 stream，这里仅做以上概述。
使用场景
Redis 使用 stream 作为流对象的底层实现，功能就是我们熟知的消息队列，虽然 Redis 本身就有一个发布订阅（pub/sub）可以实现消息队列的功能，但消息不支持持久化，很容易造成消息丢失。另外 rax 还被用在了 Redis Cluster 中用于记录 slot 与 key 的对应关系。
总结 从上述对 Redis 底层数据结构的介绍，我们可以看出，Redis 针对底层数据结构的设计是非常精细的，针对每个字节，甚至每一位都进行了考量，可以表现为以下几点：
- 存储效率。Redis 是基于内存来存储数据的，所以如何节省内存资源就是 Redis 数据结构努力的一个方向，上述数据结构中，基本上都能看到为了减少内存碎片，以及压缩存储空间等做出的设计。
- 响应时间。对于 Redis 主模块单线程设计，如果对一个数据结构操作过慢，那将是灾难一样的事情，所以也能看到 Redis 对数据结构操作的时间复杂度的优化。
【Redis-数据结构详解（下）】
文章图片
本文系哈啰技术团队出品，未经许可，不得进行商业性转载或者使用。非商业目的转载或使用本文内容，敬请注明“内容转载自哈啰技术团队”。
推荐阅读
- 云硬盘EVS详解以及如何用与避坑【华为云至简致远】
- vue|使用vue音频播放器（vue-aplayer）详解
- k8s证书有效期时间修改的方法详解
- Oracle数据库服务器修改操作系统时间的注意事项详解
- 图文详解梯度下降算法的原理及Python实现
- Java8新特性:|Java8新特性: CompletableFuture详解
- 【JS 逆向百例】某网站加速乐 Cookie 混淆逆向详解
- Vue|Vue nextTick延迟回调获取更新后DOM机制详解
- Android|Android studio 3.5.2安装图文教程详解
- Flutter有状态组件使用详解