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

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

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 回帖

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • 数据库

    据说 99% 的性能瓶颈都在数据库。

    345 引用 • 742 回帖
  • flomo

    flomo 是新一代 「卡片笔记」 ,专注在碎片化时代,促进你的记录,帮你积累更多知识资产。

    6 引用 • 140 回帖
  • OpenResty

    OpenResty 是一个基于 NGINX 与 Lua 的高性能 Web 平台,其内部集成了大量精良的 Lua 库、第三方模块以及大多数的依赖项。用于方便地搭建能够处理超高并发、扩展性极高的动态 Web 应用、Web 服务和动态网关。

    17 引用 • 54 关注
  • 链滴

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

    记录生活,连接点滴

    171 引用 • 3848 回帖 • 2 关注
  • 安全

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

    203 引用 • 818 回帖
  • MongoDB

    MongoDB(来自于英文单词“Humongous”,中文含义为“庞大”)是一个基于分布式文件存储的数据库,由 C++ 语言编写。旨在为应用提供可扩展的高性能数据存储解决方案。MongoDB 是一个介于关系数据库和非关系数据库之间的产品,是非关系数据库当中功能最丰富,最像关系数据库的。它支持的数据结构非常松散,是类似 JSON 的 BSON 格式,因此可以存储比较复杂的数据类型。

    90 引用 • 59 回帖 • 7 关注
  • WebComponents

    Web Components 是 W3C 定义的标准,它给了前端开发者扩展浏览器标签的能力,可以方便地定制可复用组件,更好的进行模块化开发,解放了前端开发者的生产力。

    1 引用 • 10 关注
  • GitLab

    GitLab 是利用 Ruby 一个开源的版本管理系统,实现一个自托管的 Git 项目仓库,可通过 Web 界面操作公开或私有项目。

    46 引用 • 72 回帖
  • 倾城之链
    23 引用 • 66 回帖 • 162 关注
  • 程序员

    程序员是从事程序开发、程序维护的专业人员。

    588 引用 • 3538 回帖
  • 友情链接

    确认过眼神后的灵魂连接,站在链在!

    24 引用 • 373 回帖 • 1 关注
  • 资讯

    资讯是用户因为及时地获得它并利用它而能够在相对短的时间内给自己带来价值的信息,资讯有时效性和地域性。

    56 引用 • 85 回帖
  • MyBatis

    MyBatis 本是 Apache 软件基金会 的一个开源项目 iBatis,2010 年这个项目由 Apache 软件基金会迁移到了 google code,并且改名为 MyBatis ,2013 年 11 月再次迁移到了 GitHub。

    173 引用 • 414 回帖 • 367 关注
  • CongSec

    本标签主要用于分享网络空间安全专业的学习笔记

    1 引用 • 1 回帖 • 28 关注
  • SQLServer

    SQL Server 是由 [微软] 开发和推广的关系数据库管理系统(DBMS),它最初是由 微软、Sybase 和 Ashton-Tate 三家公司共同开发的,并于 1988 年推出了第一个 OS/2 版本。

    21 引用 • 31 回帖
  • 以太坊

    以太坊(Ethereum)并不是一个机构,而是一款能够在区块链上实现智能合约、开源的底层系统。以太坊是一个平台和一种编程语言 Solidity,使开发人员能够建立和发布下一代去中心化应用。 以太坊可以用来编程、分散、担保和交易任何事物:投票、域名、金融交易所、众筹、公司管理、合同和知识产权等等。

    34 引用 • 367 回帖 • 5 关注
  • gRpc
    11 引用 • 9 回帖 • 93 关注
  • 一些有用的避坑指南。

    69 引用 • 93 回帖 • 1 关注
  • HBase

    HBase 是一个分布式的、面向列的开源数据库,该技术来源于 Fay Chang 所撰写的 Google 论文 “Bigtable:一个结构化数据的分布式存储系统”。就像 Bigtable 利用了 Google 文件系统所提供的分布式数据存储一样,HBase 在 Hadoop 之上提供了类似于 Bigtable 的能力。

    17 引用 • 6 回帖 • 61 关注
  • Kafka

    Kafka 是一种高吞吐量的分布式发布订阅消息系统,它可以处理消费者规模的网站中的所有动作流数据。 这种动作(网页浏览,搜索和其他用户的行动)是现代系统中许多功能的基础。 这些数据通常是由于吞吐量的要求而通过处理日志和日志聚合来解决。

    36 引用 • 35 回帖 • 2 关注
  • JetBrains

    JetBrains 是一家捷克的软件开发公司,该公司位于捷克的布拉格,并在俄国的圣彼得堡及美国麻州波士顿都设有办公室,该公司最为人所熟知的产品是 Java 编程语言开发撰写时所用的集成开发环境:IntelliJ IDEA

    18 引用 • 54 回帖
  • 京东

    京东是中国最大的自营式电商企业,2015 年第一季度在中国自营式 B2C 电商市场的占有率为 56.3%。2014 年 5 月,京东在美国纳斯达克证券交易所正式挂牌上市(股票代码:JD),是中国第一个成功赴美上市的大型综合型电商平台,与腾讯、百度等中国互联网巨头共同跻身全球前十大互联网公司排行榜。

    14 引用 • 102 回帖 • 316 关注
  • abitmean

    有点意思就行了

    36 关注
  • OkHttp

    OkHttp 是一款 HTTP & HTTP/2 客户端库,专为 Android 和 Java 应用打造。

    16 引用 • 6 回帖 • 85 关注
  • 阿里巴巴

    阿里巴巴网络技术有限公司(简称:阿里巴巴集团)是以曾担任英语教师的马云为首的 18 人,于 1999 年在中国杭州创立,他们相信互联网能够创造公平的竞争环境,让小企业通过创新与科技扩展业务,并在参与国内或全球市场竞争时处于更有利的位置。

    43 引用 • 221 回帖 • 71 关注
  • 负能量

    上帝为你关上了一扇门,然后就去睡觉了....努力不一定能成功,但不努力一定很轻松 (° ー °〃)

    89 引用 • 1243 回帖 • 411 关注
  • C

    C 语言是一门通用计算机编程语言,应用广泛。C 语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。

    85 引用 • 165 回帖 • 1 关注