您当前的位置:首页 > 电脑百科 > 数据库 > Redis

你知道Redis的字符串是怎么实现的吗?

时间:2019-12-12 16:44:26  来源:  作者:

之前本人在找工作面试时在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的字符串是怎么实现的吗?

 

Redis的字符串也会遵守C语言的字符串的实现规则,即最后一个字符为空字符。然而这个空字符不会被计算在len里头。

2.SDS 动态扩展特点

SDS的最厉害最奇妙之处在于它的Dynamic。动态变化长度。举个例子

面试:你知道Redis的字符串是怎么实现的吗?

 

如上图所示刚开始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为字符个数,因为他是从头到尾(到空字符'')遍历相加。

2.避免缓冲区溢出

对一个C语言字符串进行strcat追加字符串的时候需要提前开辟需要的空间,如果不开辟空间的话可能会造成缓冲区溢出,而影响程序其他代码。如下图,有一个字符串s1="hello" 和 字符串s2="baby",现在要执行strcat(s1,"world"),并且执行前未给s1开辟空间,所以造成了缓冲区溢出。

面试:你知道Redis的字符串是怎么实现的吗?

 

而对于Redis而言由于每次追加字符串时都会检查空间是否够用,所以不会存在缓冲区溢出问题。每次追加操作前都会做如下操作:

  1. 计算出大小是否足够
  2. 开辟空间至满足所需大小

3.降低空间分配次数提升内存使用效率

字符串的追加操作会涉及到内存分配问题,然而内存分配问题会牵扯内存划分算法以及系统调用所以如果频繁发生的话影响性能,所以对于性能至上的Redis来说这是万万不能忍受的。所以采取了以下两种优化措施

  • 空间与分配
  • 惰性空间回收

1. 空间预分配

对于追加操作来说,Redis不仅会开辟空间至够用而且还会预分配未使用的空间(free)来用于下一次操作。至于未使用的空间(free)的大小则由修改后的字符串长度决定。

当修改后的字符串长度len < 1M,则会分配与len相同长度的未使用的空间(free)

当修改后的字符串长度len >= 1M,则会分配1M长度的未使用的空间(free)

有了这个预分配策略之后会减少内存分配次数,因为分配之前会检查已有的free空间是否够,如果够则不开辟了~

2. 惰性空间回收

与上面情况相反,惰性空间回收适用于字符串缩减操作。比如有个字符串s1="hello world",对s1进行sdstrim(s1," world")操作,执行完该操作之后Redis不会立即回收减少的部分,而是会分配给下一个需要内存的程序。当然,Redis也提供了回收内存的api,可以自己手动调用来回收缩减部分的内存。

到此为止结束了~

下次在遇到这个问题可以侃侃而谈了,哈哈哈

来源:juejin.im/post/5ca9d8ae6fb9a05e5c05c4e8



Tags:Redis   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
来源: my.oschina.net/xiaomu0082/blog/2990388首先说下问题现象:内网sandbox环境API持续1周出现应用卡死,所有api无响应现象刚开始当测试抱怨环境响应慢的时候 ,我们重启一下应...【详细内容】
2021-12-08  Tags: Redis  点击:(18)  评论:(0)  加入收藏
我不知道为什么你会选择对特定数量的“错误”(或警告)如此具体。听起来您正在寻找将要发布到 Yahoo! 的某些文章的内容。 Insider (N Foos to Blah for the BlahBlah)。那说:...【详细内容】
2021-12-07  Tags: Redis  点击:(14)  评论:(0)  加入收藏
目录 一、背景 二、步骤 0.理论支持 1、获取数据 2、结果 3、分析数据并评估大小 三、关于repl-backlog-size 一、背景 repl-backlog-size控制这个环形缓冲区. ​ 主从断...【详细内容】
2021-11-05  Tags: Redis  点击:(41)  评论:(0)  加入收藏
Redis 性能测试是通过同时执行多个命令实现的。1,Redis-benchmarkRedis性能命令:redis性能命令格式: redis-benchmark [option] [option value] redis 性能测试工具可选参数如...【详细内容】
2021-11-02  Tags: Redis  点击:(41)  评论:(0)  加入收藏
1 概述数据结构和内部编码 无传统关系型数据库的 Table 模型schema 所对应的db仅以编号区分。同一 db 内,key 作为顶层模型,它的值是扁平化的。即 db 就是key的命名空间。 key...【详细内容】
2021-11-01  Tags: Redis  点击:(28)  评论:(0)  加入收藏
普通java中使用引用Java redis 驱动,即可连接:import redis.clients.jedis.Jedis; public class RedisTestJava { public static void main(String[] args) { //连...【详细内容】
2021-10-13  Tags: Redis  点击:(34)  评论:(0)  加入收藏
Redis常用的数据结构有 string list set zset hashstringstring 是 Redis 的基本的数据类型,一个 key 对应一个 value。string 类型是二进制安全的,Redis的string可以包含任...【详细内容】
2021-10-12  Tags: Redis  点击:(36)  评论:(0)  加入收藏
列表类型可以存储一组按插入顺序排序的字符串,它非常灵活,支持在两端插入、弹出数据,可以充当栈和队列的角色。> LPUSH fruit apple(integer) 1> RPUSH fruit banana(integer)...【详细内容】
2021-09-17  Tags: Redis  点击:(54)  评论:(0)  加入收藏
Redis持久化意义 是做灾难恢复,数据恢复,也可以归类到高可用的一个环节里面去,比如你的redis整个挂了,然后redis就不可用了,你要做的事情是让redis变得可用,尽快变得可用 大量的请...【详细内容】
2021-08-12  Tags: Redis  点击:(77)  评论:(0)  加入收藏
Nginx来限制访问控制的方法有多种,nginx主要有2个模块控制,但是那些不支持自定义,非常死,在大多数场景下并不实用。今天分享一个:利用openresty+lua+redis 实现封杀频繁恶意访问I...【详细内容】
2021-08-12  Tags: Redis  点击:(119)  评论:(0)  加入收藏
▌简易百科推荐
来源: my.oschina.net/xiaomu0082/blog/2990388首先说下问题现象:内网sandbox环境API持续1周出现应用卡死,所有api无响应现象刚开始当测试抱怨环境响应慢的时候 ,我们重启一下应...【详细内容】
2021-12-08  Java识堂    Tags:Redis   点击:(18)  评论:(0)  加入收藏
我不知道为什么你会选择对特定数量的“错误”(或警告)如此具体。听起来您正在寻找将要发布到 Yahoo! 的某些文章的内容。 Insider (N Foos to Blah for the BlahBlah)。那说:...【详细内容】
2021-12-07  富集云科技有限公司    Tags:Redis   点击:(14)  评论:(0)  加入收藏
目录 一、背景 二、步骤 0.理论支持 1、获取数据 2、结果 3、分析数据并评估大小 三、关于repl-backlog-size 一、背景 repl-backlog-size控制这个环形缓冲区. ​ 主从断...【详细内容】
2021-11-05  弈秋的美好生活    Tags:redis   点击:(41)  评论:(0)  加入收藏
Redis 性能测试是通过同时执行多个命令实现的。1,Redis-benchmarkRedis性能命令:redis性能命令格式: redis-benchmark [option] [option value] redis 性能测试工具可选参数如...【详细内容】
2021-11-02  川石信息    Tags:Redis   点击:(41)  评论:(0)  加入收藏
1 概述数据结构和内部编码 无传统关系型数据库的 Table 模型schema 所对应的db仅以编号区分。同一 db 内,key 作为顶层模型,它的值是扁平化的。即 db 就是key的命名空间。 key...【详细内容】
2021-11-01  JavaEdge    Tags:Redis   点击:(28)  评论:(0)  加入收藏
普通java中使用引用Java redis 驱动,即可连接:import redis.clients.jedis.Jedis; public class RedisTestJava { public static void main(String[] args) { //连...【详细内容】
2021-10-13  faesuite    Tags:Redis   点击:(34)  评论:(0)  加入收藏
Redis常用的数据结构有 string list set zset hashstringstring 是 Redis 的基本的数据类型,一个 key 对应一个 value。string 类型是二进制安全的,Redis的string可以包含任...【详细内容】
2021-10-12  语霖    Tags:Redis   点击:(36)  评论:(0)  加入收藏
列表类型可以存储一组按插入顺序排序的字符串,它非常灵活,支持在两端插入、弹出数据,可以充当栈和队列的角色。> LPUSH fruit apple(integer) 1> RPUSH fruit banana(integer)...【详细内容】
2021-09-17  深夜敲代码    Tags:Redis   点击:(54)  评论:(0)  加入收藏
Redis持久化意义 是做灾难恢复,数据恢复,也可以归类到高可用的一个环节里面去,比如你的redis整个挂了,然后redis就不可用了,你要做的事情是让redis变得可用,尽快变得可用 大量的请...【详细内容】
2021-08-12  小李说IT    Tags:Redis   点击:(77)  评论:(0)  加入收藏
当查询Redis中没有的数据时,该查询会下沉到数据库层,同时数据库层也没有该数据,当这种情况大量出现或被恶意攻击时,接口的访问全部透过Redis访问数据库,而数据库中也没有这些数据...【详细内容】
2021-07-30  随便t    Tags:缓存穿透   点击:(91)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条