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

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

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 赞助。

    286 引用 • 248 回帖 • 17 关注

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • AngularJS

    AngularJS 诞生于 2009 年,由 Misko Hevery 等人创建,后为 Google 所收购。是一款优秀的前端 JS 框架,已经被用于 Google 的多款产品当中。AngularJS 有着诸多特性,最为核心的是:MVC、模块化、自动化双向数据绑定、语义化标签、依赖注入等。2.0 版本后已经改名为 Angular。

    12 引用 • 50 回帖 • 499 关注
  • WebClipper

    Web Clipper 是一款浏览器剪藏扩展,它可以帮助你把网页内容剪藏到本地。

    3 引用 • 9 回帖 • 5 关注
  • 七牛云

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

    28 引用 • 226 回帖 • 137 关注
  • 链滴

    链滴是一个记录生活的地方。

    记录生活,连接点滴

    169 引用 • 3834 回帖 • 1 关注
  • IDEA

    IDEA 全称 IntelliJ IDEA,是一款 Java 语言开发的集成环境,在业界被公认为最好的 Java 开发工具之一。IDEA 是 JetBrains 公司的产品,这家公司总部位于捷克共和国的首都布拉格,开发人员以严谨著称的东欧程序员为主。

    181 引用 • 400 回帖
  • Access
    1 引用 • 3 回帖 • 5 关注
  • 机器学习

    机器学习(Machine Learning)是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能。

    83 引用 • 37 回帖 • 1 关注
  • SMTP

    SMTP(Simple Mail Transfer Protocol)即简单邮件传输协议,它是一组用于由源地址到目的地址传送邮件的规则,由它来控制信件的中转方式。SMTP 协议属于 TCP/IP 协议簇,它帮助每台计算机在发送或中转信件时找到下一个目的地。

    4 引用 • 18 回帖 • 637 关注
  • Chrome

    Chrome 又称 Google 浏览器,是一个由谷歌公司开发的网页浏览器。该浏览器是基于其他开源软件所编写,包括 WebKit,目标是提升稳定性、速度和安全性,并创造出简单且有效率的使用者界面。

    62 引用 • 289 回帖
  • uTools

    uTools 是一个极简、插件化、跨平台的现代桌面软件。通过自由选配丰富的插件,打造你得心应手的工具集合。

    7 引用 • 27 回帖
  • Netty

    Netty 是一个基于 NIO 的客户端-服务器编程框架,使用 Netty 可以让你快速、简单地开发出一个可维护、高性能的网络应用,例如实现了某种协议的客户、服务端应用。

    49 引用 • 33 回帖 • 32 关注
  • 生活

    生活是指人类生存过程中的各项活动的总和,范畴较广,一般指为幸福的意义而存在。生活实际上是对人生的一种诠释。生活包括人类在社会中与自己息息相关的日常活动和心理影射。

    230 引用 • 1454 回帖 • 1 关注
  • Spring

    Spring 是一个开源框架,是于 2003 年兴起的一个轻量级的 Java 开发框架,由 Rod Johnson 在其著作《Expert One-On-One J2EE Development and Design》中阐述的部分理念和原型衍生而来。它是为了解决企业应用开发的复杂性而创建的。框架的主要优势之一就是其分层架构,分层架构允许使用者选择使用哪一个组件,同时为 JavaEE 应用程序开发提供集成的框架。

    945 引用 • 1460 回帖 • 1 关注
  • sts
    2 引用 • 2 回帖 • 222 关注
  • Office

    Office 现已更名为 Microsoft 365. Microsoft 365 将高级 Office 应用(如 Word、Excel 和 PowerPoint)与 1 TB 的 OneDrive 云存储空间、高级安全性等结合在一起,可帮助你在任何设备上完成操作。

    5 引用 • 34 回帖
  • JavaScript

    JavaScript 一种动态类型、弱类型、基于原型的直译式脚本语言,内置支持类型。它的解释器被称为 JavaScript 引擎,为浏览器的一部分,广泛用于客户端的脚本语言,最早是在 HTML 网页上使用,用来给 HTML 网页增加动态功能。

    729 引用 • 1278 回帖
  • SSL

    SSL(Secure Sockets Layer 安全套接层),及其继任者传输层安全(Transport Layer Security,TLS)是为网络通信提供安全及数据完整性的一种安全协议。TLS 与 SSL 在传输层对网络连接进行加密。

    70 引用 • 193 回帖 • 414 关注
  • Vim

    Vim 是类 UNIX 系统文本编辑器 Vi 的加强版本,加入了更多特性来帮助编辑源代码。Vim 的部分增强功能包括文件比较(vimdiff)、语法高亮、全面的帮助系统、本地脚本(Vimscript)和便于选择的可视化模式。

    29 引用 • 66 回帖 • 1 关注
  • Log4j

    Log4j 是 Apache 开源的一款使用广泛的 Java 日志组件。

    20 引用 • 18 回帖 • 34 关注
  • 笔记

    好记性不如烂笔头。

    311 引用 • 796 回帖
  • 宕机

    宕机,多指一些网站、游戏、网络应用等服务器一种区别于正常运行的状态,也叫“Down 机”、“当机”或“死机”。宕机状态不仅仅是指服务器“挂掉了”、“死机了”状态,也包括服务器假死、停用、关闭等一些原因而导致出现的不能够正常运行的状态。

    13 引用 • 82 回帖 • 74 关注
  • Telegram

    Telegram 是一个非盈利性、基于云端的即时消息服务。它提供了支持各大操作系统平台的开源的客户端,也提供了很多强大的 APIs 给开发者创建自己的客户端和机器人。

    5 引用 • 35 回帖
  • 开源

    Open Source, Open Mind, Open Sight, Open Future!

    409 引用 • 3586 回帖 • 1 关注
  • OpenShift

    红帽提供的 PaaS 云,支持多种编程语言,为开发人员提供了更为灵活的框架、存储选择。

    14 引用 • 20 回帖 • 649 关注
  • 面试

    面试造航母,上班拧螺丝。多面试,少加班。

    325 引用 • 1395 回帖
  • OneNote
    1 引用 • 3 回帖
  • 安全

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

    203 引用 • 818 回帖