乐趣区

Redis 数据结构之String

目的
Redis 现在是各个系统几乎都在使用的一种分布式高可用的缓存内存中的数据结构存储系统。可以作为数据库、缓存消息中间件、订阅发布系统等。我们都知道 redis 中有 string、sets、sorted sets、hash、list 类型。但是这些我们经常使用的数据结构的底层是怎么实现的。今天先记录一下 string 的结构。主要是参照 Redis 设计与实现和一些网上的资料总结的一个学习笔记。
C 语言字符串和 SDS 在 Redis 中的使用
redis 是用 C 语言实现的,所以在 redis 中的 string 有一些是直接使用 C 语言的字符串。但是在 redis 中还使用了叫做简单动态字符串 (simple dynamic string)。redis 中的 string 主要就是使用这两种 string。但是什么时候用哪种呢?具体我们来看一下。C 语言 string:主要使用在一些无序对字符串进行修改的地方,比如说作为 key、打印日志 SDS:SDS 是 redis 中默认字符串表示。几乎用于所有需要使用字符串操作的地方,包括 AOF 缓冲区等模块。我们举一个例子:
redis> set aaa “bbb” 这个时候 aaa 使用的是 C 语言字符串,bbb 则是使用 SDSRPUSH list “aaa” “bbb” “ccc”list 这个 key 使用的是 C 语言字符串,aaa bbb ccc 则是使用了 3 个 SDS 来保存
SDS 定义
SDS 的定义其实很简单,一共有 3 个属性。len、free、buf
struct sdshdr{
// 记录 buf 数组中已经使用的数量
// 等于整个字符串目前已经使用的长度(不包括结束字符 ”\0″)
int len;
// 记录 buf 数组中未使用的字节数量
int free;
// 字节数组,用于保存字符串的地方
char buf[]
}
我们可以看到相比 C 语言中的字符串,SDS 多了两个属性 len 和 free。但就是这两个简单的属性再加上一些扩容策略就可以是的性能有一个很大的提升。接下来我们可以看一下 SDS 的优势点在哪里。
SDS 优势点

快速获取字符串的长度在 SDS 的结构中有一个 len 的属性,如果要获取字符串长度则直接返属性即可。如果 C 语言字符串,则需要循环字节数组遇到了 ”0″ 计算出整个字符串的长度。很明显可以看到 SDS 使用的复杂度是 O(1)。所以说在 redis 中获取字符串的长度对性能几乎是没有影响的。

杜绝缓冲区溢出在 C 语言字符串中,当你添加字符到一个字符串是 s1 长度时如果忘记在执行前为 s1 分配足够多的空间,那么 s1 的数据将溢出到之后的字符串 s2 中,导致 s2 被意外的修改。然而 SDS 不同,每次对 SDS 字符串修改之前都会去判断字符串的容量是否足够。如果不够则会扩充 SDS 的内存大小。所以完全避免了这个错误。

减少字符串修改带来的内存分配次数在 C 语言字符串中,每次对字符串的修改都会影响到内存的分配。如果增长字符串,则会为字符串重新分配一个新的内存空间。如果减少字符串,则会对减少的内存空间做内存回收,否则会引起内存泄漏。那么 SDS 是如何减少内存分配的呢?是通过两点

空间的预分配当 SDS 的 API 对一个 SDS 进行修改,并且需要扩展空间的时候,不仅会对 SDS 分配所需要的空间,还会为 SDS 分配额外的未使用空间。这个未使用空间的长度则记录在 free 属性中。这个预分配空间的策略根据 SDS 的长度决定。1 当 SDS 小于 1MB 的时候。每次扩容长度则跟 len 相同。举一个例子如果一个 SDS 扩容为 12 个字节,那么 SDS 函数将会再添加一个 12 字节的预分配长度。既 len=12 free=12 buf 长度则为 25 字节(多出来的 1 个是结束符 ”0″)2 当 SDS 大于 1MB 的时候,每次预分配长度则为 1MB。相当于如果这个 SDS 是 10MB,那么每次扩容之后的 free 的长度回是 1MB
惰性空间释放当一个 SDS 字符串缩短操作时,程序并不会马上重新收回多余出来的内容,而是用 free 字段将这些空余的空间记录下来。当下次如果需要往 SDS 添加字符,则可以再次使用这些空余空间。当然也不是意味着永远不会被回收,SDS 有 API 来释放这些内存空间。

二进制安全开始没有理解什么事二进制安全,网上找了一些资料。简单总结:** 二进制安全的意思就是,只关心二进制化的字符串,不关心具体格式,只会严格的按照二进制的数据存取,不会妄图以某种特殊格式解析数据。C 语言字符串的字符必须符合某种编码(比如 ASCII)并且不能包含空字符,否则空字符之后的字符将会被忽略。二 SDS 则都是使用二进制处理,不仅可以存放字符串还可以放字节流,比如图片,视频等。因为 redis 不使用空字符串来判断长度而是用 len 属性。
总结
因为 redis 作为一个数据库存储来使,而且 redis 是一个单线程,一旦一个操作阻塞了之后之后的所有操作都会被影响。所以对性能的要求特别高,所以 redis 自己构建了这种字符串。其实 SDS 结构十分简单,简单的使用了 len,free 两个字段配合一些策略,就大幅度的提高了性能和减少了内存重新分配的次数。值得我们学习,可以应用在其他程序设计中。

退出移动版