redis为什么不直接使用C字符串,而要自定义简单动态字符串?

栏目: IT技术 · 发布时间: 4年前

内容简介:来源:公众号【编程珠玑】作者:守望先生ID:shouwangxiansheng

来源:公众号【编程珠玑】

作者:守望先生

ID:shouwangxiansheng

Redis ( 一个使用ANSI C编写的开源、支持网络、基于内存、可选持久性的键值对存储数据库。 )没有直接使用 C 语言传统的字符串表示 redis 中的字符串,而是使用了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型, 并将 SDS 用作 Redis 的默认字符串。

那么,为什么要用这种数据结构替代传统的字符串呢?我们先回顾一下C字符串。

C语言传统字符串

C语言传统字符串是以空字符结尾的字符数组。例如:

char str[] = "hello"; 

计算字符串的长度:

strlen(str); 

C语言传统字符串我们应该已经很熟悉了,这里就不再继续介绍了。

简单动态字符串

redis中的简单动态字符串定义如下:

struct __attribute__ ((__packed__)) sdshdr64 {     uint64_t len; //已使用     uint64_t alloc; //分配的内存,包括结尾\0     unsigned char flags; //标志位     char buf[];//真正存储字符串的地方 }; 

它有很多种,这里选择了长度为8字节范围的进行介绍。看起来很简单对不对?

__attribute__ (( packed )) 取消了默认的字节对齐,使得flags前后不会有潜在的填充字段,也便于网络传输(扩展内容参考《 理一理字节对齐的那些事 》)。len表示buf中存储了的内容的长度;alloc表示已经分配的空间。

那么,定义成这样的SDS有什么好处呢?

常数复杂度获取长度

我们都知道,strlen获取 C传统字符串长度的时间复杂度为O(N) ,而上面的结构中,获取字符串长度的 时间复杂度为常数 ,因为len字段存储了字符串的长度,这样的做法虽然多占用了一点空间,换来的却是效率的提升。

实际上这种做法,在很多地方都很常见,例如C++中的标准容器,如vector获取其大小,string获取其长度。

预分配空间减少内存分配次数

实际上,在创建新的sds的时候,它并不仅仅申请要使用的内存,而是额外申请了一些空间,以避免下次修改的时候又需要重新申请内存。

什么意思呢?

比如说,你有一个字符数组:

char str[] = "hello"; 

现在你想存储helloworld,怎么办?原先的空间已经确定了,没有办法存储这么多字符串,你只能重新申请空间,然后还要把原先的hello拷贝到新申请的空间中去。如果有频繁地修改字符串,就会导致系统中频繁的内存申请,释放,拷贝,这样还能有高效的redis吗?

因此在redis中,如果有这样的情况,分配新的空间的时候, 会预分配一些空间,以备下次使用

惰性释放空间

而正因如此,出现字符串缩短的时候,也没有必要直接释放内存,只需要更新字符串,记录当前使用的长度即可,你说,下次字符串又增长的时候,不就又用上了吗?

保存二进制数据

看下面的字符串:

char str[] = "hello\0world"; 

你说下面的字符串,strle长度是多少?不是10,也不是11,而是5。为啥?遇到\0就计算结束了呗。所以要想存储一些特殊的字符串,即中间可能出现\0的字符串,传统的C字符串还不好办呢。

sds就不一样了,管你存什么,反正我长度是记录在len字段中了,输入写入多少,我记录多少。因此它可以保存二进制数据。

扩展可以参考《 NULL,0,'\0',“0”,"\0"你真的分得清吗?

兼容传统字符串的常见用法

虽然redis新定义了sds这样的结构,但是能应用于传统C字符串的函数,同样可以应用于sds。这点在《 数组下标-1你见过吗? 》中已经简单提到过了。

它在创建的时间,将指针指向了buf,而不是sdshdr64结构的开头,即:

len alloc flag buf

所以,类似下面这样的操作,也是安全的:

strlen(pSds);/pSds为sds类型 strcasecmp(pSds, "hello world");//pSds为sds类型 

所以你现在明白为什么要指向buf了吧? 适用于传统C字符串的函数,也能用在sds上。

而正因如此,我们看到源码中,有很多地方sds使用了下标-1访问一些内容:
例如sdsIncrLen函数中

void sdsIncrLen(sds s, ssize_t incr) {     unsigned char flags = s[-1];     size_t len; 

s[-1],等价于 *(s-1),下面就很容易理解了:

len alloc flag buf

所以下次看到下标为负,可不要觉得奇怪了。

总结

实际上当你了解C++的vector的时候,你会发现,它们利用的思想是惊人的相似

  • 预分配

  • 常数获取长度

  • 惰性释放

  • ……

本文旨在通过了解redis中sds的实现,学习其中的设计思想和策略。

关注公众号【编程珠玑】,获取更多Linux/C/C++/数据结构与算法/计算机基础/工具等原创技术文章。 后台免费获取经典电子书和视频资源

redis为什么不直接使用C字符串,而要自定义简单动态字符串?


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Python高级编程(第二版)

Python高级编程(第二版)

[波兰] Michał Jaworski、[法] Tarek Ziadé / 张亮、阿信 / 人民邮电出版社 / 2017-9-19 / 89.00元

Python作为一种高级程序设计语言,凭借其简洁、易读及可扩展性日渐成为程序设计领域备受推崇的语言之一。 本书基于Python 3.5版本进行讲解,通过13章的内容,深度揭示了Python编程的高级技巧。本书从Python语言及其社区的现状开始介绍,对Python语法、命名规则、Python包的编写、部署代码、扩展程序开发、管理代码、文档编写、测试开发、代码优化、并发编程、设计模式等重要话题......一起来看看 《Python高级编程(第二版)》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

在线进制转换器
在线进制转换器

各进制数互转换器

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具