大厂面试之Redis数据类型底层实现

大家好啊！，我是一名北漂的小小程序员最近大哥们去大厂面试，集中反馈说，只知道Redis数据类型的使用已经不行了，他们开始卷源码了，基本上都会让你说一到两个数据类型在Redis中的底层实现，想想也是哈！如果知道这些数据类型的底层实现，咱们就会更优雅的使用Redis，而且能了解这些大神们的设计思想，也更有助于自己写的代码更优雅~~~

上篇文章也介绍了redis的八个数据类型的使用（Redis数据类型的使用）点击括号中的字可以查看上篇文章哦！下面小小的成员就从源码角度说说Redis数据类型的底层实现，这也是Redis为什么快的原因之一（高效的数据结构）。

一、Redis的数据结构

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

二、String

2.1 String的底层实现（SDS）

String的底层是由一个叫简单动态字符串实现的，Simple Dynamic String，简称SDS，一个String最大容量是512M，在Redis的数据结构中大概长这个样子：

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

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

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

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

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

2.2 String的三种编码格式

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

int

emStr

raw

2.2.1 int

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

最小值：-2的63次幂:即: -9223372036854775808

最大值：2的63次幂: 即:223372036854775807

因此，String中int类型的范围是：-9223372036854775808 至 9223372036854775807 如果String类型value的值大于最大值(2的63次幂)或者小于最小值(-2的63次幂)，都会就会转成 mbStr。

验证：SET普通值666后，查看到SDS的编码格式是int再来个极限最小值试一下，查看到SDS的编码格式仍是int把极限最小值再减1，然后SDS的编码格式就变成了emStr最大极限值也同样道理，这里不做演示。注意：也只有整数才会使用int，如果是浮点数，即使在上面所说的最大或最小值范围之内，其内部也是先将浮点数转化为emStr，然后再保存。

2.2.2 embstr

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

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

2.2.3 raw

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

验证：

2.3 SDS的优势

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

可以三个方面阐述

（1）字符串长度处理

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

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

（2）内存重新分配

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

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

（3）二进制安全

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

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

三、Hash

3.1 Hash底层实现（zipList / hashTable）

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

3.2.1 zipList

zipList在Redis源码中简介,用我半把刀子的英语水平翻译的大概意思是：

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

其数据数据结构如下图:

3.2.2 zipList优势

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

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

头节点里有头节点里同时还有一个参数 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其实就是一个ziplistquickListNode： 这里的unsigned char *zl1就是指向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上文中已经做过介绍:

6.2 skipList（跳跃表）

6.2.1 是什么

他是一种空间换时间的数据结构，在普通链表中，无法进行二分查找，查找效率低，为了解决这个问题，借鉴了数据库索引的思想，从链表中提取关键节点，现在关键节点上查找，在进入下层的链表中查找。因为提取了多层关键节点，就形成跳跃表，简单说或就是给链表加上多级索引。

6.2.2 普通链表痛点

在查询单个元素时，如果想要找的元素是88，需要比较9次，假如链表中数据量特别大，想找到指定的元素最坏的时间复杂度是O(N)，效率很低。

6.2.3 实现思路

为了提升查找效率，可以采用类似数据库索引的思想，给链表加上“索引”，这样查找效率就高了，它是这个样子的首先每一级索引我们提升了2倍的跨度，那就是减少了2倍的步数，所以是n/2、n/4、n/8以此类推；

第k级索引结点的个数就是n/(2^k)；

假设索引有h级，最高的索引有2个结点；n/(2^h) = 2, 从这个公式我们可以求得 h = log2(N)-1；

所以最后得出跳表的时间复杂度是O(logN)，这样查找效率就提高了很多。

6.2.4 结论

跳跃表是一个最典型的空间换时间解决方案，而且只有在数据量较大的情况下才能体现出来优势。而且应该是读多写少的情况下使用，所以它的适用范围应该还是比较有限，维护成本相对要高：新增或者删除时需要把所有索引都更新一遍；最后在新增和删除的过程中的更新，时间复杂度也是O(log n)

6.3 zipList转skipList

在Zset中，有两个关键值，他们控制着zipList转skipList的转换，

当前ziplist中元素个数（zset_max_ziplist_entries）：默认值为 128

当前ziplist中单个元素大小（zset_max_ziplist_value）：默认值为 64

当前ziplist中元素个数超过zset_max_ziplist_entries或者当前ziplist中单个元素大小超过zset_max_ziplist_value时，zipList会转换成skipList 为了方便测试，将zset_max_ziplist_entries的值改为3，zset_max_ziplist_value的值改为6情况一： 元素的数量等于zset_max_ziplist_entries，且单个元素的大小小于zset_max_ziplist_value，底层是zipList，元素的数量大于zset_max_ziplist_entries，底层是skipList。情况二： 元素的数量小于zset_max_ziplist_entries，但单个元素的大小大于zset_max_ziplist_value