文章详情

短信预约信息系统项目管理师 报名、考试、查分时间动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Redis 数据结构 之 SDS

2021-12-02 23:11

关注

Redis 数据结构 之 SDS

SDS(simple dynamic string),简单动态字符串。s同时它被称为 Hacking String。hack 的地方就在 sds 保存了字符串的长度以及剩余空间。sds 的实现在 sds.c 中。

C语言字符串使用长度为n+1的字符数组来表示长度为n的字符串,并且字符数组的最后一个元素总是空字符"",这样的方式存储,时存在安全隐患的,并且它不能满足效率方面的需求。

因此Redis没有使用C原生的string而是自己构建了SDS。在Redis里,C语言字符串只用于一些无须对字符串值进行修改的地方,比如:日志。

在Redis中,包含字符串值的键值对都是使用SDS实现的,除此之外,SDS还被用于AOF缓冲区、客户端状态的输入缓冲区。

SDS定义

struct sdshdr{
     //字节数组
     char buf[]; 
     //buf数组中已使用字节数量
     int len;
     //buf数组中未使用字节数量
     int free;
}

如上图所示,len表示该SDS保存了一个6字节长度(不包含结束符)的字符串,free表示该SDS还有6个字节的未使用空间,buf是一个char类型的数组 ,保存了该SDS所存储的字符串值。

高效

相比C语言字符串,使获取字符串长度时间复杂度降为O(1)而C原生的获取长度为O(N) 遍历整个数组。

安全

同时SDS杜绝缓冲区溢出,不会像C那样造成数组数据不安全,绝对不会越界。

当需要对SDS进行修改时,API会先检查SDS当前剩余空间是否满足修改之后所需的空间,如果不满足的话API会自动将SDS的空间扩展至足够用的空间然后才进行下一步操作,所以SDS不会出现缓冲区溢出问题。

减少内存分配

C语言字原生符串底层是使用一个n+1个字符长度的char类型数据实现的,所以每次增长或缩短一个原生字符串,程序都要对这个字符串数组进行一次内存重分配操作:

同时因为内存重分配涉及复杂的算法,并且可能需要执行系统调用,所以它通常是一个比较耗时的操作。Redis经常被用于速度要求严苛、数据被频繁修改的场合,如果每次修改字符串都需要执行一次内存重分配的话,那么对于性能会造成很大影响。

SDS 在分配了内存之后(往往空间会存在盈余,也就是空间的预分配),然后自己通过len 和 free 来维护已使用的和未使用的内存,不再依赖系统来重新划分,这样能有效的提升性能。

空间预分配

用于字符串增长操作,当字符串增长时,程序会先检查需不需要对SDS空间进行扩展,如果需要扩展,程序不仅会为SDS分配修改所必要的空间,还会为SDS分配额外的未使用空间,额外分配的未使用空间公式如下:

SDS空间 < 1MB

如果对SDS修改之后,SDS的长度(修改之后len属性的值)小于1MB,那么则分配和len属性同样大小的未使用空间,这时SDS的len属性和free属性的值相同。如:如果修改之后SDS的len将变为10字节,那么程序也会分配10字节的未使用空间,SDS的buf数组实际长度变为10 + 10 + 1 = 21(额外一个字节用于保存结束符 )

SDS空间 > 1MB

如果对SDS修改之后,SDS的长度大于等于1MB,那么程序会分配1MB的未使用空间。如:修改之后的len将变为10MB,那么程序会分配1MB的未使用空间,SDS的bug数组长度为10MB + 1MB + 1byte

SDS空间 > 512MB

Game over~ 报错!

惰性空间释放

用于优化SDS的字符串收缩操作,当字符串收缩时,程序不会立即执行内存重分配来回收收缩后内存多出来的空间,而是使用free属性记录下来,以备将来使用。

通过空间预分配,Redis可以减少连续执行字符串增长操作所需的内存重分配次数,通过惰性空间释放,SDS避免了缩短字符串时所需的内存重分配操作,并为将来由可能的增长操作提供了优化。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-数据库
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯