大家好啊!,我是一名北漂的小小程序员最近大哥们去大厂面试,集中反馈说,只知道Redis数据类型的使用已经不行了,他们开始卷源码了,基本上都会让你说一到两个数据类型在Redis中的底层实现,想想也是哈!如果知道这些数据类型的底层实现,咱们就会更优雅的使用Redis,而且能了解这些大神们的设计思想,也更有助于自己写的代码更优雅~~~
上篇文章也介绍了redis的八个数据类型的使用(Redis数据类型的使用)点击括号中的字可以查看上篇文章哦!下面小小的成员就从源码角度说说Redis数据类型的底层实现,这也是Redis为什么快的原因之一(高效的数据结构)。
一、Redis的数据结构
简单来说,五个基本数据类型在Redis中以这样的数据结构存在,下图所示:

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

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
其实就是一个ziplist
quickListNode: 这里的
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
七、总结
这些高效的数据结构也是Redis快的原因之一,Redis五大基本数据类型的底层实现也是由几种数据类型组成,如下图所示:上篇文章介绍了Redis的基本使用,这篇文章介绍了Redis五种数据类型的底层实现。问题又来了:Redis在使用应该注意什么呢?
小小的程序员要连载文章了,咱们下期见~~~

码字不易,最后请大家动动小手,点波关注

原文始发于微信公众号(Java的编程之美):大厂面试之Redis数据类型底层实现
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/37726.html