Redis设计与实现笔记(一) | 字符串
目录
本书侧重于讲解redis的实现,对实践案例等讲解不多。Redis是开源的数据库,源代码 https://github.com/antirez/redis 官网 https://redis.io/ 有需要的小伙伴,可以去看看。
总所周知,redis所支持的基本数据类型有五种:字符串、列表、哈希、集合、有序集合。本笔记针对字符串进行讲解。Redis是使用C语言开发的,kv型的数据库。那么,Redis的字符串与C的字符串有哪些区别呢?又是怎么实现的呢?
1.1 与C字符串的区别
在 C 语言中,字符串实际上是使用空字符 '\0' 终止的一维字符数组。在C语言中,初始化一个字符串:
char greeting[] = "Hello";
以下是 C/C++ 中定义的字符串的内存表示:
Redis的字符串则不然,它是使用SDS(simple dynamic string ,简单动态字符串)作为默认的字符串类型。在Redis中,只会在一些不需要修改的字符串字面量,使用C语言的字符串实现,这些字符串主要用于展示、日志、提示等,例如,开启redis服务器的提示,如下: 2026:M 10 Oct 10:10:14.134 # Server initialized 2026:M 10 Oct 10:10:14.135 * DB loaded from disk: 0.002 seconds 2026:M 10 Oct 10:10:14.135 * Ready to accept connections
对于在Redis中需要修改的字符串,而不是字符串字面量的话,redis就会用SDS表示字符串。例如在Redis数据库中,字符串的键值对都是使用SDS实现的。这些是Redis实际存储的内容,是可被改变的。例如:
在数据库中,键name 会作为一个SDS进行存储,值“tyltr”也会作为一个SDS进行存储。
1.2 SDS是什么鬼?
在源代码中,sds.h 文件中,定义了一个sdshdr结构体表示一个SDS值
struct sdshdr{
//SDS中保存字符串的长度
int len;
// buf中未使用的字节长度
int free;
// 字节数组,保存字符串,实质上buf是C语言的字符串
char buf[];
}
结构图示例:(图 1.2.1)
由上图可以看出,free 为 0 表明buf内可分配的空间为0;len表示字符串“Redis”保的长度,不包括空字符“\0”;buf是一个C语言字符串。
这样设计有什么好处呢?
- 获取字符串长度的复杂度为常数复杂度:C语言中,获取一个字符串的长度,需要遍历整个数组,复杂度O(n);在Redis中可直接访问len,获取字符串长度,复杂度O(1)
- 杜绝了溢出现象:在Redis修改字符串时,先检测分配的空间是否能满足修改的需求。如果不满足,API则自动申请内存,以满足修改需求,再进行修改操作
- 减少了字符串修改时的内存分配次数,详见 1.3 内存分配的优化策略
- 二进制安全性(有些理论化,一般这个特性用不到)
1.3 内存分配的优化策略
内存分配的优化策略主要有两种:空间预分配、惰性空间释放
1.3.1 空间预分配
空间预分配,用于SDS字符串的增长优化。在C语言中,每次修改字符串的长度,都会执行内存的重新分配。而SDS在执行字符串的增长的操作时,不仅分配本次所需的内存空间,而且预分配出一些未使用的空间,以备下次执行字符串的增长操作。Redis的这种预分配策略,可以减少因字符串增长操作而带来的内存分配次数(把连续增长N次的字符串所需的内存分配次数必定也是N次,减低到最多N次内存分配次数)
1.3.2 惰性空间释放
惰性空间释放,用于SDS字符串的缩短优化。在SDS中,数组buf中的字符串缩短时,Redis并不立即执行free命令,进行内存的释放,而是把空余的空间数量记录在sdshdr结构体的free字段中,以备再次使用,减少空间分配的操作。对于数组(数组是物理连续的,buf实质就是C语言的char 数组)来说,空间分配是耗时操作,所以减少空间的分配,是提升性能的一个途径。但这势必会造成内存的空间利用率降低。笔者在读一些资料时,看到一些作者是这样写道的:这是通过降低内存利用率来保证性能的措施,是一种“折中”的妥协和无奈。而笔者却不这么认为。通过这个降低内存利用率的方式换取了性能上的提升,四两拨千斤。这是一种“以小易大”的智慧,而不是“妥协和无奈”
1.4 总结
- redis是采用SDS作为默认方式存储字符串的
- redis的字符串内存分配的优化策略:空间预分配、惰性空间释放
- redis的SDS是由sdshdr结构体实现,sdshdr结构体中由三部分信息:
- len:字符串长度 ;
- free :SDS中的可用空间;
- buf:SDS字符串的实质存储在buf数组内。
- SDS优势
- 获取字符串长度的复杂度为O(1)
- 杜绝了溢出现象
- 减少了字符串修改时的内存分配次数
- 二进制安全性