震惊!Redis 的字符串居然是这样实现的…
云栖号资讯:【点击查看更多行业资讯】
在这里您可以找到不同行业的第一手的上云资讯,还在等什么,快来!
之前本人在找工作面试时在Redis相关问题上可栽了跟头。
在面试前按常规套路准备了一下,比如 Redis 的常用5种数据结构,Redis持久化策略,Redis实现分布式锁,简单发布订阅等等都准备了,当时不知天高地厚以为十拿九稳了,可是万万没想到我终究还是在Redis的被问的第一个问题上翻船了~~
面试官 : 看你简历上写了熟悉常用数据结构,都有哪些说说
本人 : 常用有5种,string,list,set,zset,hash(内心很得意)
面试官 : 那你说说都用过哪些数据结构_
本人 : 用的最多的是string,通常会把json字符串存进去_
面试官 : 那你知道Redis内部是怎么实现它的string的么?_
本人 : 呃~,我了解Redis是用C语言写的,至于具体实现就不清楚了~
到此一面卒~~~
有相同经历的朋友么?
回去后恶补了一下Redis有关原理性的知识点,恰好最近在最总结面试经历于是有了今天这篇文章。
本篇会讲以下内容:
Redis字符串的实现
Redis字符串的性能优势
Redis字符串的实现
Redis虽然是用C语言写的,但却没有直接用C语言的字符串,而是自己实现了一套字符串。目的就是为了提升速度,提升性能,可以看出Redis为了高性能也是煞费苦心。
Redis构建了一个叫做简单动态字符串(Simple Dynamic String),简称SDS
1.SDS 代码结构
struct sdshdr{ // 记录已使用长度 int len; // 记录空闲未使用的长度 int free; // 字符数组 char[] buf; };
SDS ?什么鬼?可能对此陌生的朋友对这个名称有疑惑。只是个名词而已不必在意,我们要重点欣赏借鉴Redis的设计思路。下面画个图来说明,一目了然。
Redis的字符串也会遵守C语言的字符串的实现规则,即最后一个字符为空字符。然而这个空字符不会被计算在len里头。
2.SDS 动态扩展特点
SDS的最厉害最奇妙之处在于它的Dynamic。动态变化长度。举个例子
如上图所示刚开始s1 只有5个空闲位子,后面需要追加' world' 6个字符,很明显是不够的。那咋办?Redis会做以下三个操作:
1.计算出大小是否足够
2.开辟空间至满足所需大小
3.开辟与已使用大小len相同长度的空闲free空间(如果len < 1M)开辟1M长度的空闲free空间(如果len >= 1M)
看到这儿为止有没有朋友觉得这个实现跟Java的列表List实现有点类似呢?看完后面的会觉得更像了。
Redis字符串的性能优势
- 快速获取字符串长度
- 避免缓冲区溢出
- 降低空间分配次数提升内存使用效率
1.快速获取字符串长度
再看下上面的SDS结构体:
struct sdshdr{ // 记录已使用长度 int len; // 记录空闲未使用的长度 int free; // 字符数组 char[] buf; };
由于在SDS里存了已使用字符长度len,所以当想获取字符串长度时直接返回len即可,时间复杂度为O(1)。如果使用C语言的字符串的话它的字符串长度获取函数时间复杂度为O(n),n为字符个数,因为他是从头到尾(到空字符'0')遍历相加。
2.避免缓冲区溢出
对一个C语言字符串进行strcat追加字符串的时候需要提前开辟需要的空间,如果不开辟空间的话可能会造成缓冲区溢出,而影响程序其他代码。如下图,有一个字符串s1="hello" 和 字符串s2="baby",现在要执行strcat(s1,"world"),并且执行前未给s1开辟空间,所以造成了缓冲区溢出。
而对于Redis而言由于每次追加字符串时都会检查空间是否够用,所以不会存在缓冲区溢出问题。每次追加操作前都会做如下操作:
- 计算出大小是否足够
- 开辟空间至满足所需大小
3.降低空间分配次数提升内存使用效率
字符串的追加操作会涉及到内存分配问题,然而内存分配问题会牵扯内存划分算法以及系统调用所以如果频繁发生的话影响性能,所以对于性能至上的Redis来说这是万万不能忍受的。
所以采取了以下两种优化措施
空间与分配
惰性空间回收
- 空间预分配
对于追加操作来说,Redis不仅会开辟空间至够用而且还会预分配未使用的空间(free)来用于下一次操作。至于未使用的空间(free)的大小则由修改后的字符串长度决定。
当修改后的字符串长度len < 1M,则会分配与len相同长度的未使用的空间(free)
当修改后的字符串长度len >= 1M,则会分配1M长度的未使用的空间(free)
有了这个预分配策略之后会减少内存分配次数,因为分配之前会检查已有的free空间是否够,如果够则不开辟了~
- 惰性空间回收
与上面情况相反,惰性空间回收适用于字符串缩减操作。比如有个字符串s1="hello world",对s1进行sdstrim(s1," world")操作,执行完该操作之后Redis不会立即回收减少的部分,而是会分配给下一个需要内存的程序。当然,Redis也提供了回收内存的api,可以自己手动调用来回收缩减部分的内存。
到此为止结束了~
下次在遇到这个问题可以侃侃而谈了,哈哈哈~
【云栖号在线课堂】每天都有产品技术专家分享!
课程地址:https://yqh.aliyun.com/zhibo立即加入社群,与专家面对面,及时了解课程最新动态!
【云栖号在线课堂 社群】https://c.tb.cn/F3.Z8gvnK
原文发布时间:2020-08-06
本文作者:小小木的博客
本文来自:“互联网架构师”,了解相关信息可以关注“互联网架构师”

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Mybatis trim 标签的 2 个妙用!
云栖号资讯:【点击查看更多行业资讯】在这里您可以找到不同行业的第一手的上云资讯,还在等什么,快来! mybatis的trim标签一般用于去除sql语句中多余的and关键字,逗号,或者给sql语句前拼接 “where“、“set“以及“values(“ 等前缀,或者添加“)“等后缀,可用于选择性插入、更新、删除或者条件查询等操作。以下是trim标签中涉及到的属性: 下面使用几个例子来说明Mybatis trim标签的使用。 1、使用trim标签去除多余的and关键字 有这样的一个例子: <select id="findActiveBlogLike" resultType="Blog"> SELECT * FROM BLOG WHERE <if test="state != null"> state = #{state} </if> <if test="title != null"> AND title like #{title} </if> <if test="author != null and author.name ...
- 下一篇
混合多云为何具有技术优势
云栖号资讯:【点击查看更多行业资讯】在这里您可以找到不同行业的第一手的上云资讯,还在等什么,快来! 如今,越来越多的企业将业务迁移到云平台,但并不是简单地将其新的应用程序,微服务或机器学习模型部署到公共云,并且没有那么快。 如果询问那些在IT运营中花费大部分时间管理数据中心的工作人员,就会听到私有云比公共云具有优势的很多原因,例如可靠性、可扩展性和安全性,并认为他们可以通过控制基础设施的选择、部署和管理来达到更高的标准。 如果询问首席信息官,他们会有其他理由考虑采用私有云和混合多云架构。他们将围绕公共云成本的可变性、长期支持原有系统的需要,以及数据中心长期合同的现实提供理论依据。与公共云架构相比,许多企业首席信息官在管理数据中心方面有着更强的实践,并希望避免陷入公共云供应商锁定的困境。 大公司在业务转型时并不像中小企业那样快,首席信息官必须考虑根据业务影响和实现价值的时间确定优先级,以实现应用程序现代化。正如CTO Advisor公司联合创始人Keith Townsend在推特上所说:“企业将其所有的Oracle应用程序转移到Amazon RDS上,还是利用这些人才为不同的业务计划创建...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- Linux系统CentOS6、CentOS7手动修改IP地址
- CentOS关闭SELinux安全模块
- CentOS8安装Docker,最新的服务器搭配容器使用
- Hadoop3单机部署,实现最简伪集群
- SpringBoot2初体验,简单认识spring boot2并且搭建基础工程
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- Windows10,CentOS7,CentOS8安装Nodejs环境
- 设置Eclipse缩进为4个空格,增强代码规范