Redis设计与实现——字符串

6个月前 (05-24) wang 技术杂谈, 数据结构 1评论 已收录 225℃ 浏览数:156

之前使用过Redis做一个第三方缓存,但是一直事情多,没有静下心去研究Redis的底层。近期有点空,准备去研究一下Redis的底层,借了本书,Redis的设计与实现。打算好好研究研究。

Redis支持五种数据结构。字符串、hash、set、zset、list。

Redis中的字符串称为SDS,(simple dynamic string ,SDS)。

在Redis里,C语言字符串也是存在的,只会做为字符串字面量用在一些无须对字符串值进行修改的地方,比如打印日志。

但是Redis需要的不仅仅是一个字符串字面量,而是一个可以被修改的字符串值的时候,Redis就会使用SDS来表示字符串的值。在Redis的数据库里面,包含字符串值的键值在底层都是SDS实现的。

每个sds .h/sdshdr结构表示一个SDS值:


struct sdshdr{

    // 记录buf数组中已使用的字节的数量 等于SDS所保存字符串的长度

    int len;

    // 记录buf数组中未使用字节的数量

    int free;

    // 字节数组,用于保存字符串

    char buf[];

}

这样的好处就是主要有五个。

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

SDS的len属性记录了SDS本身的长度,所以获取字符串的长度只需要获取len值,时间复杂度为O(1),确保了获取字符串长度的工作不会造成Redis的性能瓶颈。

二、拒绝缓冲区溢出

C的字符串不记录自身长度带来的另一个问题是造成缓冲区溢出。比如在内存中有两个紧邻着的字符串s1和s2。然后执行命令去修改s1的值,有可能将s1的数据溢出到s2所在的空间,导致s2保存的内容被意外的修改。

SDS的空间分配策略会首先去检查SDS的空间是否满足修改的需求,如果不满足会自动扩容到可以执行操作的大小,然后再进行修改。这样完全就杜绝了发生缓冲区溢出的可能性。

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

在C字符串中,不记录自身的长度,那就是说一个长度为N的字符串,底层实现是一个N+1的数组。

每一次增长字符串,比如拼接,那么在执行的时候,需要先通过内存重分配扩展底层数组的空间大小。如果忘了这个步骤就会有缓冲区溢出。

每一次缩短字符串,比如截断,那么在执行的时候,需要通过内存重分配来释放字符串不再使用那部分空间。如果忘了这个步骤就会产生内存泄漏。

为了避免这种缺陷,SDS使用未使用空间解除了字符串长度和底层数组长度之间的关系。SDS中,buf数组的长度不一定就是字符数量加一,数组中还可能有未被使用的支付,这些字符就是SDS的free属性记录。

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

空间预分配

空间预分配用于优化SDS的字符串增长操作。分为两种。

一、对SDS修改后,SDS的长度,len属性小于1MB,那么程序分配和len属性同样大的未使用空间。这时len长度和free长度相同。

二、对SDS修改后,SDS的长度,len属性大于1MB,那么程序分配1MB的未使用空间。

惰性空间释放

空间预分配用于优化SDS的字符串缩短操作。

当SDS缩短后,程序并不立刻使用内存重分配回收缩短后多出来的直接,而是使用free属性将这些字节的数量记录起来,并等待将来使用。

四、二进制安全

C字符串的字串必须符合某种编码,并且除了字符串的末尾以外,字符串里面不可以包含空字符串,否则最先被程序读入的空字符串误以为为结尾。这样使得C字符串只能保存文本数据,不能保存图片、音频、视频等数据。

为了确保Redis可以适用于各种场景,所有的SDS API会以二进制的方式来处理SDS存放的buf数组的数据。所以我们把buf数组称为字节数组,Redis不是用这个数组保存字符,而是一系列二进制数据。

五、兼容部分C函数API

虽然SDS的API是二进制安全的,但是依然遵循了C字符串以控制符结尾的惯例,可以重用部分<string.h>的库定义的函数,避免了不必要的代码重复。

 

 

博主

Just do it. Now or never.

相关推荐

1 条评论

  1. avatar
    -49#

    mark了 过几天再来学习一下

    第一菜鸡 于2018-05-24 20:06 评论 回复