Redis 中 SDS 相比 C 字符串有哪些优势?

本贴最后更新于 3060 天前,其中的信息可能已经斗转星移

SDS 是什么鬼?

其实,SDS 是 Redis 中实现的一种数据结构,主要用来存储字符串。那 SDS 与 C 字符串相比有什么优势呢?那就看看下面小编为大家的分享吧。

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

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

而 SDS 使用结构体实现,结构体中的 len 属性直接记录了该 SDS 结构体中 buf 数组中已使用的长度,因此获取字符串长度时,只需要获取 len 属性的值,这个操作的复杂度为 O(1)。SDS 结构体的实现确保了获取字符串长度的工作不会成为 Redis 的性能瓶颈。

2、杜绝缓冲区溢出

因为,C 字符串不记录自身的长度,所以当进行字符串复制的时候,如果分配内存不够,就有可能产生缓冲区溢出。

而在 Redis 中,当 SDS API 需要对 SDS 进行修改时,API 会先检查 SDS 的空间是否满足修改所需的要求,如果不满足的话,API 会自动将 SDS 的空间扩展至执行修改所需的大小,然后才执行实际的修改操作。所以,使用 SDS 既不需要手动修改 SDS 的空间大小,也不会出现前面所说的缓冲区溢出问题。

Redis 中 strcat 的实现代码:

sds sdscat(sds s, const char *t) {

return sdscatlen(s, t, strlen(t));

}

sds sdscat(sdss,constchar*t){

returnsdscatlen(s,t,strlen(t));

}

Redis 中 sdscatlen 的实现代码:

sds sdscatlen(sds s, const void *t, size_t len) {

struct sdshdr *sh;

// 原有字符串长度 直接获取len属性

size_t curlen = sdslen(s);

// 扩展 sds 空间

// T = O(N)

s = sdsMakeRoomFor(s,len);

// 内存不足?直接返回

if (s == NULL) return NULL;

// 复制 t 中的内容到字符串后部

// T = O(N)

sh = (void*) (s-(sizeof(struct sdshdr)));

memcpy(s+curlen, t, len);

// 更新属性

sh->len = curlen+len;

sh->free = sh->free-len;

// 添加新结尾符号

s[curlen+len] = '\0';

// 返回新 sds

return s;

}

sds sdscatlen(sdss,constvoid*t,size_tlen){

structsdshdr*sh;

// 原有字符串长度 直接获取 len 属性

size_tcurlen=sdslen(s);

// 扩展 sds 空间

// T = O(N)

s=sdsMakeRoomFor(s,len);

// 内存不足?直接返回

if(s==NULL)returnNULL;

// 复制 t 中的内容到字符串后部

// T = O(N)

sh=(void*)(s-(sizeof(structsdshdr)));

memcpy(s+curlen,t,len);

// 更新属性

sh->len=curlen+len;

sh->free=sh->free-len;

// 添加新结尾符号

s[curlen+len]='\0';

// 返回新 sds

returns;

}

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

常规 C 字符串,在执行拼接操作或者截断操作时,通常会对数组进行内存重分配,而内存重分配操作涉及复杂的算法,并且可能执行系统调用,所以它通常是一个比较耗时的操作。

Redis 作为数据库,会对数据进行频繁的修改,并且对速度要求极为严苛,所以每次修改字符串长度都需要进行内存重分配,这会对性能造成极大的影响。

为此,Redis 的 SDS 实现了空间预分配和惰性空间释放两种优化策略。

  1. 空间预分配

当 SDS 的 API 对一个 SDS 进行修改时,程序不仅会为 SDS 分配必须要的空间,还会为 SDS 分配额外的未使用空间。

额外分配未使用空间数量的规则:

当 SDS 的 len 属性值小于 1MB,程序分配和 len 属性同样大小的未使用空间。

当 SDS 的 len 属性值大于 1MB,程序将多分配 1M 的未使用空间。

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

  1. 惰性空间释放

当对 SDS 进行字符串缩短操作时,SDS 的 API 不会立即使用内存重分配回收多出来的字节,而是使用 free 属性将这些字节的数量记录起来,等待将来使用。

当然,SDS 也提供了相应的 API,可以用来真正释放 SDS 的未使用空间,所以不用担心惰性空间释放策略会造成内存浪费。

以上就是 redis 中,SDS 简单动态字符串相比 C 字符串的一些好的地方,个人还是比较实用的,希望对大家有帮助吧。

相关文章:《PHP 开发常用的 8 款 Laravel 软件包》 http://www.maiziedu.com/group/article/663/

  • Redis

    Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。从 2010 年 3 月 15 日起,Redis 的开发工作由 VMware 主持。从 2013 年 5 月开始,Redis 的开发由 Pivotal 赞助。

    284 引用 • 247 回帖 • 210 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • 钉钉

    钉钉,专为中国企业打造的免费沟通协同多端平台, 阿里巴巴出品。

    15 引用 • 67 回帖 • 381 关注
  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖
  • 七牛云

    七牛云是国内领先的企业级公有云服务商,致力于打造以数据为核心的场景化 PaaS 服务。围绕富媒体场景,七牛先后推出了对象存储,融合 CDN 加速,数据通用处理,内容反垃圾服务,以及直播云服务等。

    25 引用 • 215 回帖 • 160 关注
  • Sandbox

    如果帖子标签含有 Sandbox ,则该帖子会被视为“测试帖”,主要用于测试社区功能,排查 bug 等,该标签下内容不定期进行清理。

    362 引用 • 1212 回帖 • 580 关注
  • 酷鸟浏览器

    安全 · 稳定 · 快速
    为跨境从业人员提供专业的跨境浏览器

    3 引用 • 59 回帖 • 21 关注
  • 安全

    安全永远都不是一个小问题。

    189 引用 • 813 回帖 • 2 关注
  • 百度

    百度(Nasdaq:BIDU)是全球最大的中文搜索引擎、最大的中文网站。2000 年 1 月由李彦宏创立于北京中关村,致力于向人们提供“简单,可依赖”的信息获取方式。“百度”二字源于中国宋朝词人辛弃疾的《青玉案·元夕》词句“众里寻他千百度”,象征着百度对中文信息检索技术的执著追求。

    63 引用 • 785 回帖 • 249 关注
  • 微信

    腾讯公司 2011 年 1 月 21 日推出的一款手机通讯软件。用户可以通过摇一摇、搜索号码、扫描二维码等添加好友和关注公众平台,同时可以将自己看到的精彩内容分享到微信朋友圈。

    129 引用 • 793 回帖 • 1 关注
  • 思源笔记

    思源笔记是一款隐私优先的个人知识管理系统,支持完全离线使用,同时也支持端到端加密同步。

    融合块、大纲和双向链接,重构你的思维。

    18150 引用 • 66978 回帖
  • Caddy

    Caddy 是一款默认自动启用 HTTPS 的 HTTP/2 Web 服务器。

    10 引用 • 54 回帖 • 126 关注
  • TextBundle

    TextBundle 文件格式旨在应用程序之间交换 Markdown 或 Fountain 之类的纯文本文件时,提供更无缝的用户体验。

    1 引用 • 2 回帖 • 45 关注
  • CAP

    CAP 指的是在一个分布式系统中, Consistency(一致性)、 Availability(可用性)、Partition tolerance(分区容错性),三者不可兼得。

    11 引用 • 5 回帖 • 552 关注
  • 持续集成

    持续集成(Continuous Integration)是一种软件开发实践,即团队开发成员经常集成他们的工作,通过每个成员每天至少集成一次,也就意味着每天可能会发生多次集成。每次集成都通过自动化的构建(包括编译,发布,自动化测试)来验证,从而尽早地发现集成错误。

    14 引用 • 7 回帖
  • DevOps

    DevOps(Development 和 Operations 的组合词)是一组过程、方法与系统的统称,用于促进开发(应用程序/软件工程)、技术运营和质量保障(QA)部门之间的沟通、协作与整合。

    37 引用 • 24 回帖 • 1 关注
  • Wide

    Wide 是一款基于 Web 的 Go 语言 IDE。通过浏览器就可以进行 Go 开发,并有代码自动完成、查看表达式、编译反馈、Lint、实时结果输出等功能。

    欢迎访问我们运维的实例: https://wide.b3log.org

    30 引用 • 218 回帖 • 594 关注
  • Ubuntu

    Ubuntu(友帮拓、优般图、乌班图)是一个以桌面应用为主的 Linux 操作系统,其名称来自非洲南部祖鲁语或豪萨语的“ubuntu”一词,意思是“人性”、“我的存在是因为大家的存在”,是非洲传统的一种价值观,类似华人社会的“仁爱”思想。Ubuntu 的目标在于为一般用户提供一个最新的、同时又相当稳定的主要由自由软件构建而成的操作系统。

    123 引用 • 168 回帖
  • RIP

    愿逝者安息!

    8 引用 • 92 回帖 • 284 关注
  • Angular

    AngularAngularJS 的新版本。

    26 引用 • 66 回帖 • 498 关注
  • LaTeX

    LaTeX(音译“拉泰赫”)是一种基于 ΤΕΧ 的排版系统,由美国计算机学家莱斯利·兰伯特(Leslie Lamport)在 20 世纪 80 年代初期开发,利用这种格式,即使使用者没有排版和程序设计的知识也可以充分发挥由 TeX 所提供的强大功能,能在几天,甚至几小时内生成很多具有书籍质量的印刷品。对于生成复杂表格和数学公式,这一点表现得尤为突出。因此它非常适用于生成高印刷质量的科技和数学类文档。

    9 引用 • 32 回帖 • 178 关注
  • Vue.js

    Vue.js(读音 /vju ː/,类似于 view)是一个构建数据驱动的 Web 界面库。Vue.js 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。

    261 引用 • 662 回帖 • 1 关注
  • 禅道

    禅道是一款国产的开源项目管理软件,她的核心管理思想基于敏捷方法 scrum,内置了产品管理和项目管理,同时又根据国内研发现状补充了测试管理、计划管理、发布管理、文档管理、事务管理等功能,在一个软件中就可以将软件研发中的需求、任务、bug、用例、计划、发布等要素有序的跟踪管理起来,完整地覆盖了项目管理的核心流程。

    5 引用 • 15 回帖 • 223 关注
  • Unity

    Unity 是由 Unity Technologies 开发的一个让开发者可以轻松创建诸如 2D、3D 多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

    25 引用 • 7 回帖 • 248 关注
  • HHKB

    HHKB 是富士通的 Happy Hacking 系列电容键盘。电容键盘即无接点静电电容式键盘(Capacitive Keyboard)。

    5 引用 • 74 回帖 • 402 关注
  • FreeMarker

    FreeMarker 是一款好用且功能强大的 Java 模版引擎。

    23 引用 • 20 回帖 • 427 关注
  • 微软

    微软是一家美国跨国科技公司,也是世界 PC 软件开发的先导,由比尔·盖茨与保罗·艾伦创办于 1975 年,公司总部设立在华盛顿州的雷德蒙德(Redmond,邻近西雅图)。以研发、制造、授权和提供广泛的电脑软件服务业务为主。

    8 引用 • 44 回帖
  • 知乎

    知乎是网络问答社区,连接各行各业的用户。用户分享着彼此的知识、经验和见解,为中文互联网源源不断地提供多种多样的信息。

    10 引用 • 66 回帖
  • jsDelivr

    jsDelivr 是一个开源的 CDN 服务,可为 npm 包、GitHub 仓库提供免费、快速并且可靠的全球 CDN 加速服务。

    5 引用 • 31 回帖 • 33 关注