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

Redis简单动态字符串 全面剖析

时间:2019-12-26 10:43:37  来源:  作者:

原文地址:https://mp.weixin.qq.com/s/Cvqe56v3TAPC-OBGiZoAaw

redis没有直接使用C语言传统的字符串表示,而是自己构建了一种名为简单动态字符串(simple dynamic string, SDS)的抽象类型,并将SDS用作Redis的默认字符串表示。

SDS的定义

每个sds.h/sdshdr结构表示一个SDS值:

Struct sdshdr{  //记录buf数组中已使用字节的数  //等于SDS所保存字符串的长度  int len;  //记录buf数组中未使用字节的数量  int free;  //字节数组,用于保存字符串  char buf[];}
Redis简单动态字符串 全面剖析

 

free属性的值为0,表示这个SDS没有分配任何未使用空间。

len属性的值为5,表示这个SDS保存了一个五字节长的字符串。

buf属性是一个char类型的数组,数组的前五个字节分别保存了‘R’、‘e’、‘d’、‘i’、‘s’五个字符,而最后一个字节则保存了空字符‘’。

SDS遵循C字符串以空字符结尾的惯例,保存空字符的1字节空间不计算在SDS的len属性里面,并且为空字符分配额外的1字节空间,以及添加字符到字符串末尾等操作,都是由SDS函数自动完成的,所以这个空字符对于SDS的使用者来说是完全透明的。

遵循空字符结尾这一惯例的好处是,SDS可以直接重用一部分C字符串函数库里面的函数。

SDS与C语言字符串的区别

常数复杂度获取字符串长度

因为C语言字符串并不记录自身的长度信息,所有获取一个C字符串的长度,程序需要遍历整个字符串,对遇到的每个字符串进行计数,直到遇到代表字符串结尾的空字符为止,这个操作的复杂度为O(N)。

而SDS在len属性中记录了SDS本身的长度,所以获取一个SDS长度的复杂度仅为O(1)。

通过使用SDS而不是C语言字符串,Redis将获取字符串长度所需的复杂度从O(N)降低到了O(1),这确保了获取字符串长度的工作不会成为Redis的性能瓶颈。

杜绝缓冲区溢出

除了获取字符串长度的复杂度高之外,C语言字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出(buffer overflow)。

与C语言字符串不同,SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性:当SDS API需要对SDS进行修改时,API会先检查SDS的空间是否满足修改所需的要求,如果不满足的话,API会自动将SDS的空间扩展至执行修改所需的大小,然后才执行实际的修改操作,所以使用SDS既不需要手动修改SDS的空间大小,也不会出现前面所说的缓冲溢出问题。

减少修改字符串时带来的内存重分配次数

C语言字符串的长度和底层数组的长度之间存在着关联性,所以每次增长或者缩短一个C语言字符串时,程序要总要对保存这个C语言字符串的数组进行一次内存重分配操作。

  • 如果程序执行的是增长字符串的操作,那么在执行这个操作之前,程序需要先通过内存重分配来扩展底层数组空间的大小,如果忘记这一步操作就会产生缓冲区溢出。
  • 如果程序执行的是缩短字符串的操作,那么在执行这个操作之后,程序需要通过内存重新分配来释放字符串不再使用的那部分空间,如果忘记这一步就会产生内存泄漏。

为了避免C语言字符串这种缺陷,SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联:在SDS中,buf数组的长度不一定就是字符串数量加1,数组里面可以包含未使用的字节,而这些字节的数量就由SDS的free属性记录。

通过未使用空间,SDS实现了空间预分配和惰性空间释放两种优化策略。

空间预分配

空间预分配用于优化SDS的字符串增长操作:当SDS的API对一个SDS进行修改,并且需要对SDS进行空间扩展的时候,程序不仅会为SDS分配修改所必需的空间,还会为SDS分配额外的未使用空间。

其中额外分配的未使用空间数据由以下公式决定:

  • 如果对SDS进行修改之后,SDS的长度(也就是len属性的值)将小于1M,那么程序分配和len属性同样大小的未使用空间,这时SDS len值将和free属性值相同。
  • 如果对SDS进行修改之后,SDS的长度将大于等于1M,那么程序会分配1M的未使用空间。

通过空间预分配策略,Redis可以减少连续执行字符串增加操作所需的内存重分配次数。

在扩展SDS空间之前,SDS API会先检查未使用空间是否足够,如果足够的话,API就会直接使用未使用空间,而无须执行内存重分配。

通过这种预分配策略,SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次。

惰性空间释放

惰性空间释放用于优化SDS的字符串缩短操作:当SDS的API需要缩短SDS保存的字符串时,程序并不立即使用内存重分配来回收缩短后多出来的字节,而是使用free属性将这些字符的数量记录起来,并等待将来使用。

通过惰性空间释放策略,SDS避免来缩短字符串时所需的内存重分配操作,并为将来可能有的增长操作提供了变化。

二进制安全

C语言字符串中的字符必须符合某种编码(比如ASCII),并且除了字符串的末尾之外,字符串里面不能包含空字符,否则最先被程序读入空字符将被误认为是字符串结尾,这些限制使得C字符串只能保存文本数据,而不能保存像图片、音频、视频、压缩文件这样的二进制数据。

为了确保Redis可以适用于各种不同的使用场景,SDS的API都是二进制安全的,所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据,程序不会对其中数组做任何限制、过滤、或者假设,数据在写入时是什么样的,它被读取时就是什么样。

兼容部分C字符串函数

通过遵从C语言字符串以空字符结尾的惯例,SDS可以在有需要时重用<string.h>函数库,从而避免来不必要的代码重复。

总结

比起C语言字符串,SDS具有以下优点:

  • 常数复杂度获取字符串长度
  • 杜绝缓冲区溢出
  • 减少修改字符串时带来的内存冲分配次数
  • 二进制安全
  • 兼容部分C字符串函数


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)  加入收藏
最新更新
栏目热门
栏目头条