内容简介: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如何通过数据问答再降低数据使用门槛
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Essential C++中文版
[美] Stanley B. Lippman / 侯捷 / 华中科技大学出版社 / 2001-8 / 39.80元
书中以4个面向来表现C++的本质:procedural(程序性的)、generic(泛型的)、object-based(个别对象的)、object-oriented(面向对象的),全书围绕着一系列逐渐繁复的程序问题,以及用以解决这些问题的语言特性。循此方式,读者不只学到C++的函数和结构,也会学习到它们的设计目的和基本原理。一起来看看 《Essential C++中文版》 这本书的介绍吧!