02 Redis 的数据结构

2.6 压缩列表

压缩列表是 list 和 hash 的底层实现之一，当 list 只包含少量元素，并且每个元素都是小整数值，或者是比较短的字符串，压缩列表会作为 list 的底层实现。

压缩列表（ziplist）是 Redis 为节约内存而开发，它的理念是多大元素用多大内存。

如下图，根据每个节点的实际存储的内容决定内存的大小，第一个节点占用 5 字节，第二个节点占用 5 字节，第三个节点占用 1 字节，第四个节点占用 4 字节，第五个节点占用 3 字节。

图示为 ziplist 的结构：它类似于一个数组，不同的是它在表头有三个字段 zlbytes、zltail 和 zllen；分别表示列表长度、列表尾的偏移量和元素的个数；表尾有 zlend，列表结束的标识。

2.6.0 节点构成

图示一个压缩列表中一个节点的构成：

• previous_entry_length：记录前一个节点的长度
• encoding：编码，控制 content 的类型和长度；分为字节数组编码和整数编码
• content：保存节点值，可以是一个字节数组或整数

2.6.1 压缩列表的查找

如果查找的是第一个元素或最后一个元素，可通过表头三个字段的长度直接定位，复杂度是 O (1)。而查找其他元素时，只能逐个查找，复杂度是 O (N) 。

倒序遍历：首先指针通过 zltail 偏移量指向表尾节点，然后通过指向节点记录的前一个节点的长度依次向前遍历访问整个压缩列表。

03 数据类型与数据结构

还记得文章开头那张数据类型与底层数据结构的对应关系图吗？长这样：

Redis 这种对应关系实际上是由 redisObject 的 type（类型）和 encoding （编码）共同决定的，详细对应关系如下：

下面来具体介绍下，什么条件下使用那种类型实现对应的对象。比如：String 什么情况下用 int 编码实现？什么情况下用 embstr 编码实现？什么情况下用 raw 编码实现呢？

3.0 字符串（String）对象

从上图得知，String 有 int、raw、embst 三种编码格式：

• int：整数值，可以用 long 类型表示，使用整数值保存对象
• raw：字符串值且长度 > 32 字节，使用 SDS 保存对象
• embstr：字符串值且长度 < 32 字节，使用 embstr 编码的 SDS 保存对象

PS：对于浮点数（long double 类型表示的），Redis 会将浮点数转换成字符串值；最终视长度决定用那种编码（embstr 或 raw）保存。取出时，再将其转成浮点值。

3.0.0 embstr 和 raw 有啥区别？

• raw 分配内存和释放内存的次数是两次，embstr 是一次
• embstr 编码的数据保存在一块连续的内存里面

3.0.1 编码的转换

• int 类型的字符串，当保存的不再是整数值，将转换成 raw 类型
• embstr 类型的字符串是只读的，修改时会转换成 raw 类型。原因：Redis 没有为 embstr 提供修改程序，所以它是只读的；要修改只能先转成 raw。

3.1 列表（list）对象

还是从上图得知，列表的编码可以是 ziplist 或 linkedlist：

• ziplist：所有元素长度都小于 64 字节且元素数量少于 512 个

• 以上两个条件的上限值可以通过配置文件的 list-max-ziplist-value 和 list-max-ziplist-entries 修改

• linkedlist：不满足上述条件时，将从 ziplist 转换成 linkedlist

3.1.0 区别

执行 RPUSH 命令将创建一个列表对象，比如：

redis> RPUSH numbers 1 "three" 5
(integer) 3

如果 numbers 使用 ziplist 编码，对象结构如下：

否则使用 linkedlist，就是双端链表作为底层实现。结构如下：

3.2 哈希（hash）对象

又是从上图得知，哈希的编码可以是 ziplist 或 hashtable：

• ziplist：哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节且键值对数量小于 512

• 以上两个条件的上限值可以通过配置文件的 hash-max-ziplist-value 和 hash-max-ziplist-entries 修改

• hashtable：不能满足上述条件，将从 ziplist 转成 hashtable

3.2.0 区别

执行 HSET 命令，可以创建一个 hash 对象并保存数据：

redis> HSET profile name "Tom"
(integer) 1
redis> HSET profile age 25
(integer) 1
redis> HSET profile career "Programmer"
(integer) 1

ziplist 保存的 hash 对象：

hashtable 保存的 hash 对象：

• 字典中每个键都是一个字符串对像，对象中保存键值对的键
• 字典中每个值都是一个字符串对像，对象中保存键值对的值

架构如下：

3.3 集合（set）对象

又又是从上图得知，哈希的编码可以是 intset 或 hashtable：

• intset：集合对象保存的所有元素都是整数值且元素数量小于 512 个

• 以上两个条件的上限值可以通过配置文件的 set-max-intset-entries 修改

• hashtable：不能满足上述条件，将从 intset 转成 hashtable

3.3.0 区别

使用 SADD 命令可构建一个 intset 编码的 set 对象并保存数据：

redis> SADD numbers 1 3 5
(integer) 3

intset 编码的集合对象结构如下：

使用 SADD 命令可构建一个 hashtable 编码的 set 对象并保存数据：

redis> SADD fruits "apple" "banana" "cherry"
(integer) 3

hashtable 编码的 set 使用字典作为底层实现，每个键都是字符串对象，每个对象包含一个集合元素，字典值全部置为 null 。

hashtable 编码的集合对象结构如下：

3.4 有序集合（Sorted Set）对象

又又又是从上图得知，有序集合的编码可以是 ziplist 或 skiplist：

• ziplist：保存的元素数量小于 128 个且所有元素长度都小于 64 字节

• 以上两个条件的上限值可以通过配置文件的 zset-max-ziplist-entries 和 zset-max-ziplist-value 修改

• skiplist：不能同时满足上述条件，将从 ziplist 转成 skiplist

3.4.0 区别

使用 ZADD 命令可以构建一个 Sorted Set 对象并保存数据：

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

ziplist 编码实现的 Sorted Set 对象，每个集合元素使用两个相邻的节点保存，第一个节点是元素成员，第二个节点是元素分值。按分值从小到大进行排序，结构如下：

skiplist 编码实现的 Sorted Set 使用 zset 作为底层实现，它包含 跳跃表和字典，源码如下：

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

大体结构如下：

• 跳跃表 zsl 按分值从小到大保存所有集合元素；每个节点保存一个集合元素；object 属性保存元素成员、score 属性保存元素分值。目的：实现快速的范围查询操作。

• 字典 dict 创建一个从成员到分值的 key-value；字典中每个键值对都保存一个集合元素；键保存元素成员、值保存元素分值。目的：用 O (1) 复杂度 get 元素分值。

最后，详细的结构如下所示：

听到这里有人可能有疑问：zset 结构同时使用跳跃表和字典来保存有序集合元素，不会重复吗？

不会，因为二者会通过指针来共享同一个元素，并不会产生重复。

为什么 skiplist 编码实现的有序集合要同时用跳跃表和字典实现？随便用一个行吗？

答案是：不好。我们来看看两种情况：

• 只用 dict ，可以保留以 O (1) 复杂度 get 成员分值；但字典是无序的，所以每次进行范围操作都要对所有元素排序；显然这是性能更低的。

• 只用跳跃表，快速范围操作得以保留；但是没了字典，get 成员分值的复杂度将提高至 O (logN)，这也影响性能。

所以，Redis 为了把两者有点结合起来，采用了通过指针共享的方式，使用两种数据结构实现。

04 一些注意的点

4.0 Redis 如何执行命令

Redis 执行命令前，会先检查值对象类型，判断键是否能执行该命令；再检查值对象的编码方式选择合适的命令执行。

举个例子：列表对象有 ziplist 和 linkedlist 两种编码格式可用；前者通过 ziplist 的 API 执行命令、后者通过 linkedlist 的 API 执行命令。

如果我们执行 LLEN 命令，Redis 第一步判断执行的命令是不是针对列表的？是的话，第二步判断值的编码格式，如果是 ziplist，使用 ziplistLen 函数操作；如果是 linkedlist 则使用 listLength 函数操作。

4.1 Redis 内存回收机制与共享对象

Redis 为每个对象构建一个引用计数属性，通过它可实现内存回收机制（当一个对象的引用计数为 0 时，将会释放所占用内存）。

Redis 会共享值为 0 到 9999 的字符串对象（这个值可能通过修改 redis.h 文件的 REDIS_SHARDED_INTEGER 常量修改）

Redis 只共享字符串对象本身，为什么不共享包含字符串的对象？

能共享的前提是目标对象和共享对象完全相同。要共享就需要验证两者是否相同？因为包含字符串的对象复杂度更高，验证消耗的 CPU 时间也更多，而性能将会下降。

4.2 lru 属性的作用

redisObject 的 lru 属性记录对象最后一次被访问的时间，这个时间可以用于计算对象的空转时间（公式：当前时间 - lru 时间）。

05 巨人的肩膀

• 《Redis 设计与实现》
• redis 源码：github.com/antirez/redis
• redis 源码中文注释版：github.com/huangz1990/redis-3.0-annotated
• cnblogs.com/Java3y/p/9870829.html
• time.geekbang.org/column/article/268253
• http://www.fidding.me/article/108
• segmentfault.com/a/1190000019980165
• cnblogs.com/chenchen0618/p/13260202.html

06 总结

本文从常用的缓存技术讲起，深入 Redis 的数据类型与底层数据结构。第一小节从 Redis 和缓存聊起；第二节站在源码角度跟你分析 Redis 的 6 种数据结构：SDS、链表、哈希表、跳跃表、整数集合以及压缩列表的特性；第三节着重和你分享 5 种数据类型和 6 中底层结构的对应关系；第四节则是画龙点睛地和你分享了 Redis 是怎么执行命令的？怎么释放内存等问题。

全文将近，张图，希望能帮到你。好啦，以上就是狗哥关于 MySQL 锁的总结。感谢各技术社区大佬们的付出，尤其是极客时间，真的牛逼。如果说我看得更远，那是因为我站在你们的肩膀上。希望这篇文章对你有帮助，我们下篇文章见～