Redis字符串,门道也不少

作者: JerryCodes  更新时间:2021-01-15 11:24:13  原文链接


这是我2021年的第4篇原创文章,原汁原味的技术之路尽在Jerrycodes

  • 底层数据结构

    • SDS底层构建

  • SDS优化了什么

    • 空间预分配

    • 惰性空间释放

    • 常数级获取字符串长度

    • 杜绝缓存区溢出

  • 二进制安全

  • 总结

  • 尾语

Redis中有五种数据类型:

  1. String: 字符串

  2. Hash: 散列

  3. List: 列表

  4. Set: 集合

  5. Sorted Set: 有序集合

字符串类型 是 Redis 最基础的数据结构。其值实际可以是 字符串(简单 和 复杂 的字符串,例如 JSON、XML)、数字(整数、浮点数),甚至是 二进制(图片、音频、视频),但是值最大不能超过 512MB

底层数据结构

它不是普通字符串,而是 SDS 字符串,这个 SDS的意思是「 Simple Dynamic String 」。

Redis是由C语言编写的,C语言里面的字符串是以 0x\0 结尾,通常我们就说以 NULL 结尾。它不包含长度信息,当我们需要获取字符串长度时,需要调用 strlen(s) 来获取长度,它的时间复杂度是 O(n) ,如果一个字符串太长,这个函数就太浪费 CPU了。

所以如果线上有个数据需要知道key对应的value的值的长度,那这个请求的处理速度可是一只行走的乌龟。 所以对C语言的做法重新设计

SDS底层构建

来看一下SDS的结构

/*
* 类型别名,用于指向 sdshdr 的 buf 属性
*/

typedef char *sds;

struct sdshdr {
// buf 中已占用空间的长度
int len;
// buf 中剩余可用空间的长度
int free;
// 数据空间 实际上不占用内存空间sizeof(struct sdshdr) = 8
char buf[];
};

如图展示了一个SDS的示例:

free属性的值为0,表示这个SDS没有任何剩余的可使用字节数。

len为5,表示这个SDS保存了一个长度为5的字符串

buf属性是一个char类型的数组,数组的前五个字节分别保存了'R'、'e'、'd'、'i'、's'五个字符,而最后一个字节则保存空字符'\0',代表字符串结束

SDS优化了什么

一句话,SDS就是为了解决C语言中字符串的弊端。

C语言中字符串存在什么问题?

  1. 缓存区溢出

  2. 字符长度计算复杂

接下来介绍以下SDS是如何解决这些问题并优化的

空间预分配

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

我们都知道当SDS除了分配给本身所需的字节空间,还会 再额外分配一些备用空间 。备用空间怎么决定,有以下两种方式:

1. (len属性<1MB) 总长度len<1MB: 总空间为2*len+1

如果对SDS进行修改后,SDS的长度(即len属性的值)小于1MB,那么程序分配和len属性同样大小的未使用空间,这时SDS的free属性的值将于len属性的值相同。

比如经过修改之后,SDS的len将变为13个字节,那么程序也会分配13个字节的备用空间,外加一个字节用于存储空字符串标识字符串结束,所以SDS的buf数组实际长度为13+13+1=27字节

2. (len属性>1MB) 修改之后总长度len>=1MB: 总空间为len+1MB+1

如果对SDS进行修改之后,SDS的长度大于等于1MB,那么程序会多分配1MB的未使用时间。

比如经修改后,SDS的len为30MB,那么程序会多分配1MB的未使用空间,SDS的buf数组的实际长度为30MB+10MB+1字节

惰性空间释放

惰性空间用于优化SDS字符串的 缩短 操作。

当SDS的API需要缩短SDS保存的字符串时, 程序并不立即使用内存重分配来回收缩短后多出来的字节 ,而是使用 free 属性将这些字节的数量记录起来,并等待将来使用。

例如操作前字符串s1=”aabbcc“等价于

SDS struct{
free=0,
len=6
buf="aabbcc"
}

执行截断操作,只保留前三位,那么根据SDS的特性,操作后s2="aab",等价于

SDS struct{
free=3,
len=3
buf="aab"
}

SDS并没有释放多出来的3字节空间,而是将这3字节空间作为未使用的空间存在了SDS中,如果以后还有扩充操作的话可以派上用场。

常数级获取字符串长度

不同于C语言中strlen获取字符串长度为O(N)的复杂度,SDS中直接读取len的值,当然len属性是在字符串更新的时候也随之更新,复杂度为 O(1) ,相当于是一个 空间换时间 的操作了。

杜绝缓存区溢出

我们知道在C语言中不记录自身长度带来的一个后果就是容易造成缓存溢出。如使用strcat函数进行拼接时,若原有字符串的空间不足时,会发生 截断 现象。

如str1 = "aabbcc",str2 ="ddeeff"; 如果str1中至多只能存放10个字符,那么经过strcat(str1,str2)函数后的输出结果为"aabbccddee",这就是 缓存区溢出 现象。

而SDS对象恰好可以解决这个问题的存在。如果buf的长度小于新字符串的长度,则声明一个新的数组存放新字符串,反之,无需再声明一个新的数组来容纳新字符串,节省开支。

二进制安全

二进制安全是指,在传输数据时, 保证二进制数据的信息安全 ,也就是不被篡改、破译等,如果被攻击,能够及时检测出来。

c中的strlen函数依赖于特殊的字符 '\0' 来判断字符串是否结束,所以对于字符串str = "1234\0123"来说,strlen(str)=4,但实际上str的长度为9.

使用SDS就不需要依赖控制符,而是用len来指定存储数据的大小,所有的 SDS API都会以处理二进制的方式来处理SDS的buf的数据 。程序不会对buf的数据做任何限制、过滤或假设,数据写入的时候是什么,读取的时候依然不变。

所以使用SDS,可以放心的存储二进制数据

总结

C字符串 SDS
获取字符串长度复杂度为 O(N) 获取字符串长度复杂度为 O(1)
会导致缓存区溢出 不会导致缓存区溢出
修改N次字符串 必定 导致N次字符串的新建 修改N次字符串 最多 导致N次字符串的新建
二进制下不安全 二进制安全

尾语

Jerry哥建立了一个优质的技术微信群,主要用于2022秋招/实习交流群,正在准备2021春招的人也可以加入。群内嘉宾有 前美团技术人索隆,微软工程师C哥和已经成功上岸的J哥 。欢迎大家扫码加我,备注学校+姓名+岗位,我会拉大家进群。

码到这里,何不来个在看?