Redis字符串键的底层原理

发布时间:2019-08-06 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了Redis字符串键的底层原理脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。

redis字符串键的底层原理


不要遗忘最初的目标。 --RuiDer


本篇文章:《Redis设计与实现》一书,特别推荐

before

导入

redis的命令如下:

@H_304_29@ set x "hello"; get x; hello

Redis作为一种存储字符串的缓存结构,其具体实现是由C语言完成,在C语言中,字符串是通过字符数组实现的,即char[],那么Redis对于字符串的实现是不是也是基于字符数组吗?不是的,Redis对字符串的处理是通过SDS(Simple Dynamic String)实现的。

SDS介绍

SDS(Simple Dynamic String)简单动态字符串,它是由C语言完成,如下是其具体实现

struct sdshdr{
    //记录buf数组已使用字节的数量
    //等于SDS所保存字符串的长度
    int length; 
    //记录buf数组未使用字节的数量
    int free;
    //buf数组
    char[] buf;
};

看看redis的示例:
    sdshdr
    free 0
    length 5
    buf     -->|'R'|'e'|'d'|'i'|'s'|''|
解释:
        - free0,表示这个SDS没有分配任何未使用的空间
        - length为5,表示这个SDS保存了一个长度为5的字符串    
        - buf数组中保存着“Redis”字符串

SDS遵循C字符串以空字符串结尾的惯例,保存空字符串的1字节空间不计算在SDS的len属性之中。

再看看SDS的free不为0的情况:

    sdshdr
    free 3
    length 5
    buf      -->|'R'|'e'|'d'|'i'|'s'| | | |

free的值为3,表示这个SDS分配了三个空闲的空间

SDS与字符串的区别

C语言使用简单的字符串表示方式,并不能满足Redis对字符串在安全性,效率,以及功能方面的要求,SDS更使用Redis。

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

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

SDS:
与C语言不同的是,SDS结构中的属性length记录了SDS本身的长度,所以获取一个SDS长度的复杂度为O(1)。有人疑问那么SDS的length值是哪来的?这里的length值是SDS API在设置和更新SDS时自动完成的。

总结1:通过使用SDS而不是C字符串,Redis获取字符串长度的复杂度由O(N)降为O(1),这确保了字符串长度的获取的工作不会成为Redis的性能瓶颈。

@ 2杜绝缓冲区溢出

C字符串:
由于C自身不记录字符串的长度带来一个问题是容易造成缓冲区溢出(buffer overflow)。在<string.h>/strcat函数中,可以将一个字符串拼接到另外一个字符串的末尾。

    `char *strcat(char *dest,const char *src)`

理想状态下,用户在使用这个函数时,假定C为dest分配了足够多的内存,可以容纳src字符串中的所有内容,而一旦这个假定不成立,就会产生缓冲区溢出。举个例子,假定内存中有相邻的两个字符串s1,s2,如图:

    s1                        s2
     |                         |
...|'R'|'e'|'d'|'i'|'s'|''||'g'|'o'|'o'|'d'|''|...

如果执行strcat(s1," cluster");将Redis改为”Redis cluster“,但是粗心的却忘了在执行这句之前为s1分配足够的空间,那么在执行之后,s1的数据将会溢出到s2所在的空间,导致s2保存的内容意外的被修改。

SDS:

    与C语言不同的是,SDS空间分配政策完全杜绝了发生缓冲区溢出的可能性:当SDS API需要对字符串进行修改时,首先会检查SDS的空间是否满足修改所需的要求,因为SDS自身有对字符串长度记录的属性length和空闲空间属性free,可以借助这两个参数进行检查。SDS会在执行动作之前判断SDS的空间大小,再去执行操作,如果空间不够的话,SDS API会自动扩展空间。
@ 3减少修改字符串时带来的内存重分配次数

C字符串:

因为C字符串不记录自身长度,每次增长或者缩短字符串长度时,程序都要对这个C字符串数组进行一次内存重新分配操作,不然容易造成内存益出。因为内存,分配设计复杂的算法,并且可能需要执行系统调用,所以它通常是一个比较耗时和耗能的操作。但是Redis作为缓存,追求速度,所以不能经常发生内存分配操作。

SDS:

SDS数组中的未使用空间字节数量由SDS的属性free记录,通过free记录,SDS实现了空间预分配和惰性释放两种优化策略
1. 空间预分配
空间预分配用于优化SDS的字符串增长操作:当SDS的API对一个SDS进行修改,并且需要对SDS的空间进行扩展时,程序不仅会为SDS分配修改所需要的空间,而且还会为SDS分配额外的空间。额外的空间分配规则如下:

(1)如果修改SDS之后,SDS的长度小于1MB,那么程序会给SDS分配和length一样大的额外空间,这是SDSlength和free的值相等。举个例子,如果修改后的字符串长度为13k,那么SDS的空间将会占据13+13+1=27k(额外的一个字节用于保存空字符串)。

(2)如果修改SDS之后,SDS的长度大于1MB,那么程序会给SDS分配额外的1MB空间,举个例子,比如修改后的SDS有30MB的大小,那么程序会分配1MB的未使用空间,SDS的buf数组实际大小将是30MB+1MB+1byte。

2.惰性释放

惰性释放用于优化SDS的字符串缩短操作:当SDS的API要缩短SDS保存的字符串时,程序并不需要立即使用内存重分配策略来回收缩短后多出来的字节,而是使用free属性将这些字节记录起来,并等待使用。

@4 二进制安全

C字符串中的字符必须符合某种编码(比如ASCII),并且除了字符串末尾之外,字符串里面不能包含空字符串,否则最先被程序读入的空字符串将被误认为是字符串结尾。

SDS API都是二进制安全的,所有SDS API都会以处理二进制的方式来处理存放在SDS buf中的数据,数据写什么样,它被读取时就是什么样子。

@5 兼容部分C字符串函数

SDS的API总会以SDS保存的数据的末尾设置为空字符串,并且在分配SDS空间时会多分配一个字节的空间来容纳空字符串,这是为了那些保存的数据可以重用一部分<string.h>库中的函数。

总结

字符串和SDS之间的区别总结如下:

C字符串 SDS
C字符串获取长度复杂度O(n) SDS获取字符串长度复杂度O(1)
API不是安全的,会出现缓冲区溢出 API是安全的,不会出现缓冲区溢出
修改字符串长度N次必然执行N此内存重分配 修改字符串长度N次必然执行最多N此内存重分配
只保存文本数据 可以保存文本数据或者二进制数据
可以使用<string.h>库中的函数 可以使用一部分<string.h>库中的函数

About Me

欢迎交流
我的Github

个人博客

脚本宝典总结

以上是脚本宝典为你收集整理的Redis字符串键的底层原理全部内容,希望文章能够帮你解决Redis字符串键的底层原理所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。