内容简介:Redis 已经是大家耳熟能详的东西了,日常工作也都在使用,面试中也是高频的会涉及到,那么我们对它究竟了解有多深刻呢?我读了几本 Redis 相关的书籍,尝试去了解它的具体实现,将一些底层的数据结构及实现原理记录下来。本文将介绍 Redis 中
前言
Redis 已经是大家耳熟能详的东西了,日常工作也都在使用,面试中也是高频的会涉及到,那么我们对它究竟了解有多深刻呢?
我读了几本 Redis 相关的书籍,尝试去了解它的具体实现,将一些底层的数据结构及实现原理记录下来。
本文将介绍 Redis 中 五种基础数据类型 的实现方法。 这五种基本类型基本覆盖了我们业务中使用的 80%的场景,对面试也覆盖至少 90%.(其中重点当然是有序集合以及散列结构咯).
定义
在前面的八篇文章中,我们详细的介绍了 Redis 中的 8 种基本数据结构,但是众所周知,Redis 常用的数据类型有五种。包括,字符串,列表,集合,有序集合,哈希。
而这五种数据类型,底层就是用前面介绍的数据结构实现的,当然,并不是直接一对一的绑定关系,而是采用了精妙的设计,构建了一个对象系统。
熟悉 OOP 编程的读者,可能很快就能想到为什么要这么设计了,对象系统带来的好处是非常多的,但是并不在这一篇文章中讲。这里只是提到对象系统,让大家对于五种数据类型为什么可以用一些花里胡哨的方法来实现,有一个初步的了解。
接下来将逐一分析五种数据类型的底层实现数据结构,及实现方式(编码)之间的切换条件。
注:后续提到五种数据类型,用 xx 对象来指代。比如 字符串对象,列表对象。提到的底层数据结构,用全称来讲。
字符串对象
涉及到的数据结构, SDS
, 强烈建议阅读本系列第一篇文章。
字符串对象的底层实现有三种可能:int, raw, embstr.
int
如果一个字符串对象,保存的值是一个整数值,并且这个整数值在 long 的范围内,那么 redis 用整数值来保存这个信息,并且将字符串编码设置为 int
.
比如:
raw
如果字符串对象保存的是一个 字符串 , 并且长度大于 32 个字节,它就会使用前面讲过的 SDS(简单动态字符串)
数据结构来保存这个字符串值,并且将字符串对象的编码设置为 raw
.
embstr
如果字符串对象保存的是一个 字符串 , 但是长度小于 32 个字节,它就会使用 embstr
来保存了, embstr
编码不是一个数据结构,而是对 SDS 的一个小优化,当使用 SDS 的时候,程序需要调用两次内存分配,来给 字符串对象 和 SDS 各自分配一块空间,而 embstr
只需要一次内存分配,因为他需要的空间很少,所以采用 连续的空间保存,即将 SDS 的值和 字符串对象的值放在一块连续的内存空间上。这样能在短字符串的时候提高一些效率。
比如:
浮点数如何保存?
redis 的字符串数据类型是支持保存浮点数,并且支持对浮点数进行加减操作,但是 redis 在底层是把浮点数转换成字符串值,之后走上面三种编码的规则的。对浮点数进行操作时,也是从字符串转换成浮点数进行计算,然后再转换成字符串进行保存的。
编码转换条件
这块的知识其实是很符合我们的认知的,比如 int
编码只可以保存整数,那么当我们对一个 int 编码的字符串对象,修改它的值,它自然就会使用 raw 编码了。
但是有一个特性,Redis 没有为 embstr
编码提供任何的修改操作,这也就是为什么它只是个编码而不是一个数据结构的原因。
所以在 Redis 中, embstr
编码的值其实是 只读 的,只要发生修改,立刻将编码转换成 raw
.
总结
字符串对象底层的数据结构或者说编码有三种,分别是 int
, raw
, embstr
. 他们之间的使用条件如下:
编码 | 使用条件 |
---|---|
int | 可以用 long 保存的整数 |
embstr | 字符串长度小于 32 字节(或者浮点数转换后满足) |
raw | 长度大于 32 的字符串 |
列表对象
涉及到的数据结构, 压缩列表
, 双向链表
, 快速列表
, 强烈建议阅读本系列的第 二,三,四 篇文章。
在 Redis 3.2 版本之前,列表对象底层由 压缩列表和双向链表配合实现,当元素数量较少的时候,使用压缩列表,当元素数量增多,就开始使用普通的双向链表保存数据。
但是这种实现方式不够好,双向链表中的每个节点,都需要保存前后指针,这个内存的使用量 对于 Redis 这个内存数据库来说极其不友好。
因此在 3.2 之后的版本,作者新实现了一个数据结构,叫做 quicklist . 所有列表的底层实现都是这个数据结构了。它的底层实现基本上就是将 双向链表和压缩列表进行了结合,用双向的指针将压缩列表进行连接,这样不仅避免了压缩列表存储大量元素的性能压力,同时避免了双向链表连接指针占用空间过多的问题。
具体的原理讲解请 阅读对应的文章,这里不再赘述。
总结
编码 | 使用条件 |
---|---|
quicklist | 所有数据 |
集合对象
涉及到的数据结构: intset
, dict(hashtable)
, 强烈建议阅读本系列第五,第六篇文章。
集合对象的编码可以是 intset 或者 hashtable(字典) .
intset
当集合中的所有元素都是整数,且元素的数量不大于 512 个的时候,使用 intset 编码。
intset 编码时,底层使用 intset
数据结构。
hashtable
当元素不符合 全部为整数值且元素个数小于 512
时,集合对象使用的编码方式为 hashtable .
字典的每一个键都是一个字符串对象,其中保存了集合里的一个元素,字典的值全部被设置为 NULL.
总结
编码 | 使用条件 |
---|---|
intset | 所有元素都是整数且元素个数小于 512 |
hashtable | 其他数据 |
有序集合对象
涉及到的数据结构, 压缩列表
, 跳跃表
, 字典
, 强烈建议阅读本系列 第三篇,第六篇,第七篇文章。
有序集合对象的编码可以是 ziplist
以及 skiplist
.
ziplist 编码
当使用 ziplist 编码时,有序集合对象的实现数据结构为 ziplist
(听起来像句废话), 每个集合的元素 (key-value), 使用两个紧挨着的压缩列表的节点来表示,第一个节点保存集合元素的成员 (member), 第二个节点保存集合元素的分支 (score).
在压缩列表的内部,集合元素按照分值从小到大进行排序。
skiplist 编码
当使用 skiplist 编码的时候,内部使用 zset
来实现数据的保存, zset
的定义如下:
typedef struct zset{ zskiplist *zsl; dict *dict; }zset;
为什么需要同时使用跳跃表以及字典呢?
其实如果我们细想,单独使用字典或者跳跃表,都是可以实现有序集合的所有功能的,但是性能太差劲了。
- 当我们只使用字典来实现,我们可以以 O(1) 的时间复杂度获取成员的分值,但是由于字典是无序的,当我们需要进行范围性操作的时候,需要对字典中的所有元素进行排序,这个时间复杂度至少需要 O(nlogn).
- 当我们只使用跳跃表来实现,我们可以在 O(logn) 的时间进行范围 排序 操作,但是如果要获取到某个元素的分值,时间复杂度也是 O(logn).
因此,将字典和跳跃表结合进行使用,可以在 O(1) 的时间复杂度下完成查询分值操作,而对一些范围操作,使用跳跃表可以达到 O(logn) 的是缠绵复杂度。
可以看到,我在上一次的例子中,添加了一个很长的 key 之后,有序集合的编码方式就成为了 skiplist
.
总结
编码 | 使用条件 |
---|---|
ziplist | 元素数量少于 128 且 所有元素成员的长度小于 64 字节 |
skiplist | 不满足上述条件的其他情况 |
散列对象
涉及到的数据结构, 压缩列表
, 字典
, 强烈建议阅读本系列 第三篇,第六篇文章。
哈希对象的编码可以是 ziplist
或者 hashtable
.
ziplist 编码
ziplist 编码下的哈希对象,使用了压缩列表作为底层实现数据结构,用两个连续的压缩列表节点来表示哈希对象中的一个键值对。实现方式类似于上面的有序集合的场景。
如图中所示,当我放入了两个简单的键值对,此时哈希对象的编码为 ziplist.
hashtable 编码
这是对 hashtable 最直观的应用了~
哈希结构本身在结构上和字典 (hashtable) 就颇为相似,因此哈希对象中的每一个键值对都是字典中的一个键值对。
- 字典的每一个键都是一个字符串对象,对象中保存了键值对的键。
- 字典的每一个值都是一个字符串对象,对象中保存了键值对的值。
如图中所示,当我在上一个示例中额外加入一个很长的值,那么编码方式就来到了 hashtable
.
总结
编码 | 使用条件 |
---|---|
ziplist | 键值对的键和值的长度都小于 64 字节,且 键值对个数小于 512. |
hastable | 不满足上述条件的其他条件 |
全文总结
其实在前面的几篇文章写完之后,也就是在所有的底层数据结构介绍完之后,所谓的 Redis 的五种基础数据类型的底层实现原理
就已经没有了难度。
所有用到的底层数据结构都知道了,剩下的无非是个排列组合问题以及各种实现方式之间的切换条件,然后这个条件也仅仅是了解性知识,强行记住也没有必要。
这里把五种基础数据类型的可能的编码列出来方便理解及记忆。
基础数据类型 | 可能的编码方式 |
---|---|
字符串 | int, raw, embstr |
列表 | 之前是 ziplist 和 linkedlist, 现在全是 quicklist 了。 |
集合 | intset 或者 hashtable |
有序集合 | ziplist 或者 skiplist , skiplist 编码中使用了跳跃表+字典 |
散列 | ziplist 或者 hashtable |
至于他们的转换条件,由于我不会用 markdown 画多维表格,但是又不想写 html, 就不做总结了,需要的读者可以点击目录跳转至每一个小结的总结~.
参考文章
《Redis 的设计与实现(第二版)》
《Redis 深度历险:核心原理和应用实践》
完。
联系我
最后,欢迎关注我的个人公众号【 呼延十 】,会不定期更新很多后端工程师的学习笔记。
也欢迎直接公众号私信或者邮箱联系我,一定知无不言,言无不尽。
以上皆为个人所思所得,如有错误欢迎评论区指正。
欢迎转载,烦请署名并保留原文链接。
联系邮箱:huyanshi2580@gmail.com
更多学习笔记见个人博客或关注微信公众号 < 呼延十 >------> 呼延十
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 数据结构 – 用于构建文件系统的数据结构?
- 数据库索引背后的数据结构
- 基础数据结构及js数据存储
- R中数据结构与数据的输入
- 荐 用Python解决数据结构与算法问题(三):线性数据结构之栈
- 无需理解数据结构也不需编程技能 Tableau如何通过数据问答再降低数据使用门槛
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
The Black Box Society
Frank Pasquale / Harvard University Press / 2015-1-5 / USD 35.00
Every day, corporations are connecting the dots about our personal behavior—silently scrutinizing clues left behind by our work habits and Internet use. The data compiled and portraits created are inc......一起来看看 《The Black Box Society》 这本书的介绍吧!