Reids五种数据类型的底层实现

上篇文章介绍了redis的八个数据类型的使用（点击阅读），接着上篇的写，Redis数据类型的底层实现，这也是Redis为什么快的原因之一（高效的数据结构）。

一、Redis的数据结构

简单来说，五个基本数据类型在Redis中以这样的数据结构存在，下图所示：

二、String

2.1 String的底层实现（SDS）

String的底层是由一个叫简单动态字符串实现的，Simple Dynamic String，

简称SDS，在Redis的数据结构中大概长这个样子：

注意：一个String最大容量是512M。

看一下Reids中的源码，就和上图对上了

len：表示 SDS 的长度，这样获取字符串长度的时间复杂度就是O(1),而不是像 C 语言那样需要遍历一遍字符串。

alloc：当前字符数组总分配的内存大小，有了这个值就可以引入预分配空间的算法了，而不用去考虑内存分配的问题。

flags：当前数组的属性，用来表示当前数组的属性是 sdshdr8还是sdshdr16等。

buf[]：表示字符串数组，存的是当前字符串的真实数据。

2.2 String的三种编码格式

为什么叫动态字符串（SDS）呢？单从字面上理解：这个字符串的动态可变的，会根据所存数据类型，大小动态的调整不同的编码格式，这样在有限计算机内存中可以存储更多的数据。三种编码格式如下：

• int

• emStr

• raw

int

长整型的64位(8个字节)有符号整数，只有整数才会使用 int，如果是浮点数， Redis 内部其实先将浮点数转化为字符串值，然后再保存。在Reids中，Long是有符号64位整数，符号以二进制补码表示:

• 最小值：-2的63次幂

即：-9223372036854775808

• 最大值：2的63次幂

即：9223372036854775807

• 其默认值是0L

因此，String中int类型的范围是：

-9223372036854775808 至 9223372036854775807

如果String类型value的值大于最大值(2的63次幂)或者小于最小值(-2的63次幂)，都会就会转成embStr。

验证：

SET普通值666后，查看到SDS的编码格式是int

再来个极限最小值试一下，查看到SDS的编码格式仍是int

把极限最小值再减1，然后SDS的编码格式就变成了emStr

最大极限值也同样道理，我比较懒，就不做演示了。

注意：也只有整数才会使用int，如果是浮点数，即使在上面所说的最大或最小值范围之内，其内部也是先将浮点数转化为emStr，然后再保存

验证：

embstr

embedded string(嵌入式字符串)保存长度小于44字节的字符串，如果大于44个字节，就会转成raw来存储数据

验证：value的长度小于等于44字节的时候，编码是embStr，大于44位编码的时候，编码是raw

raw

保存长度大于44字节的字符串，如果要是对embStr中的值进行修改时，底层会先转化为raw在进行修改，而且这个过程不可逆，因此，只要对embStr中的值进行修改，无论修改后的值的长度是否大于44个字节，其存储格式一定是raw。

验证：

2.3 SDS的优势

Redis是由C语言实现的，直接使用C语言中的char[]来存储数据不香吗？干嘛非要自己造轮子呢？SDS的优势在哪里呢？

可以三个方面阐述：

字符串长度处理：

• C语言：要想获取字符串的长度，需要从头开始遍历，直到‘’，时间复杂度O(N)

• SDS：而在SDS中有个len专门记录字符串的长度，获取字符串长度的时间复杂度O(1)。

内存重新分配：

• C语言：分配内存空间超过后，会导致数组下标越级或者内存分配溢出

• SDS：空间预分配：SDS修改后，len 长度小于1M，那么将会额外分配与 len 相同长度的未使用空间。如果修改后长度大于 1M，那么将分配1M的使用空间。惰性空间释放：SDS 缩短时并不会回收多余的内存空间，而是使用 free 字段将多出来的空间记录下来。如果后续有变更操作，直接使用 free 中记录的空间，减少了内存的分配。

二进制安全：

• C语言：二进制数据并不是规则的字符串格式，可能会包含一些特殊的字符，比如 ‘’ 等。C中字符串遇到 ‘’ 会结束，那 ‘’ 之后的数据就读取不上了

• SDS：根据 len 长度来判断字符串结束的，二进制安全的问题就解决了

三、Hash

3.1：Hash底层实现（zipList / hashTable）

Hash是由zipList和hashTable组成，默认是zipList存储，当zipList达到阈值之后就会转成hashTable，但是这个过程是不可逆的（可类比synchronized升级）。

3.2：zipList

zipList在Redis源码中简介

用我半把刀子的英语水平翻译的大概意思是：

zipList是一种特殊的双向链表，高效的内存使用率，支持String和integer类型存储，其中整数编码为实际整数，而不是一系列字符串。存取操作的时间复杂度是O(1),并且需要重新分配内存，zipList的复杂度与它的内存使用有关。

数据结构:

zipList优势

1：普通的双向链表会有两个指针，在存储数据很小的情况下，存储的实际数据的大小可能还没有指针占用的内存大，得不偿失。ziplist 是一个特殊的双向链表没有维护双向指针:prev next；而是存储上一个 entry的长度和当前entry的长度，通过长度推算下一个元素在什么地方。牺牲读取的性能，获得高效的存储空间，因为(简短字符串的情况)存储指针比存储entry长度更费内存。这是典型的“时间换空间”。

2：链表在内存中一般是不连续的，遍历相对比较慢，而ziplist可以很好的解决这个问题（zipList在内存中是连续的），普通数组的遍历是根据数组里存储的数据类型找到下一个元素的(例如int类型的数组访问下一个元素时每次只需要移动一个sizeof(int)就行，但是ziplist的每个节点的长度是可以不一样的，而我们面对不同长度的节点又不可能直接申请sizeof(entry)，所以ziplist只好将一些必要的偏移量信息记录在了每一个节点里，使之能跳到上一个节点或下一个节点。

3：头节点里有头节点里同时还有一个参数 len，和string类型提到的 SDS 类似，这里是用来记录链表长度的。因此获取链表长度时不用再遍历整个链表，直接拿到len值就可以了，这个时间复杂度是 O(1)。

3.3：hashTable

OBJ_ENCODING_HT 这种编码方式内部才是真正的哈希表结构，或称为字典结构，其可以实现O(1)复杂度的读写操作，因此效率很高。

在 Redis内部，从 OBJ_ENCODING_HT类型到底层真正的散列表数据结构是一层层嵌套下去的，组织关系见面图：

对外的宏观编码是OBJ_ENCODING_HT,通过OBJ_ENCODING_HT找到dict，再通过dict找到dictht，最后通过dictht找到真正的数据存数据的节点dictEntry

源码体现：

3.3：zipist转hashTable（过程不可逆的）

转换所触发的阈值有两个参数：

hash-max-zipist-entries：最大元素的个数，（默认是512个）

hash-max-ziplist-value：单个元素的最大长度。（默认是64字节）

通CONFIG GET hash* 可以查看参数大小，

Redis支持对两个参数的大小进行修改。

转换阈值：

hash-max-ziplist-entries：中哈希对象保存的键值对数量小于 512 个；

hash-max-ziplist-value：中的键值对的键和值的字符串长度都小于等于 64byte；

当满足以上任意一个条件时，zipList就会转成hashTable

证明：由于hash-max-zipList-entries和hash-max-zipList-value的阈值比较大，先将hash-max-zipList-entries和hash-max-zipList-value阈值修改为3，这样方便测试

修改参数的阈值后，这时已经变成hashTable了（只让单个键的值超过3，或只让键值对的数量超过3等其他满足zipList转hashTable的条件，大家可自行测试）

源码体现：

四、List

4.1：List简介

List底层是quickList，quickList实际上是由zipList和linkList组成，每个quickList的Node都是一个zipList，一张简图就看明白了：

4.2：Redis中List参数配置

通过config get list* 命令可以查看参数配置，可以看到有两个参数：

list-max-ziplist-size指ziplist中entry配置

参数说明：

当取正值的时候，表示按照数据项个数来限定每个quicklist节点上的ziplist长度。比如，当这个参数配置成5的时候，表示每个quicklist节点的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。

list-compress-depth指zipList压缩配置

参数说明：

表示一个quicklist两端不被压缩的节点个数。这里的节点是指quicklist双向链表的节点，而不是指ziplist里面的数据项个数

参数list-compress-depth的取值含义如下：

0: 是个特殊值，表示都不压缩。（默认值）

1: 表示quicklist两端各有1个节点不压缩，中间的节点压缩。

2: 表示quicklist两端各有2个节点不压缩，中间的节点压缩。

依此类推…

4.3：底层实现

quickList是双向链表，每个quicklistNode其实就是一个ziplist

quickListNode：这里的unsigned char *zl 就是指向ziplist

一图说明quickList

五、Set

Set是一个无序并唯一的键值集合，底层由inset和hashTable组成。当元素都是long类型且元素的个数小于等于set-max-inset-entries时，用intset，否则就用hashTable，hashTable在上文中已经介绍。

验证

查看底层数据结构并修改测试。将set-max-intset-entries默认值修改为3方测试

添加值

添加三个整数，元素的数量等于3且是long类型数据，没有超过设置的set-max-intset-entries=3的值，此时，编码是intset

再添加一个long类型元素，这时的编码已经是hashTable

直接添加其他数据类型的元素，这时编码是hashTable

六、Zset

6.1：Zset简介

Zset是一个有序集合，底层是由zipList和skipList组成，默认是zipList，当集合中元素的数量超过zset_max_ziplist_entries 的值（默认值为 128 ），或者集合中单个元素的长度超过zset_max_ziplist_value 的值（默认值为 64 ）时，zipList就会变成skipList。zipList上文中已经做过介绍。