String
Redis没有直接使用C语言的传统的字符串表示,而是自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型。
下面我将解释为什么Redis要自己构建SDS而不是直接用C语言的String,原因其实很简单,一切都是为了提升Redis操作的性能。
SDS的定义
这里我先给出SDS的定义,下面我会对它特有的属性进行解析,大家在看的时候可以思考以下几点,为什么需要这个属性?
这个属性有什么用?没有这个属性会怎么样?在之后的数据结构解析中,希望大家也能带着相似的问题去思考Redis的设计。
struct sdshdr {//记录buf数组已经使用的长度//也就是SDS字符串的长度int len;//记录buf数组中未使用的长度int free;//字节数组,用于保存字符串char buf [] ;}
一个简单的SDS字符串
SDS字符串相比C语言字符串的优势
SDS字符串由于它比C语言字符串多出来的几个属性,所以SDS字符串很多操作效率都比C语言字符串快得多,属于典型的空间换时间策略。
常数复杂度获取字符串长度
众所周知,C语言字符串想获取长度,就得遍历整个字符串。
下图为C语言获取字符串长度的过程
SDS通过len属性使得获取一个SDS字符串的长度的时间复杂度从O(N)变为了O(1),这确保了获取字符串长度的工作不会成为Redis的性能瓶颈。
杜绝缓冲区溢出
除了获取字符串的长度的复杂度高之外,C字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出。
举个缓冲区溢出的例子:
假设程序里有两个在内存中紧邻着的 C 字符串s1
和s2
, 其中s1
保存了字符串"Redis"
, 而s2
则保存了字符串"MongoDB"
, 如图 2-7 所示。
如果一个程序员决定通过执行:
strcat(s1, " Cluster");
将s1
的内容修改为"Redis Cluster"
, 但粗心的他却忘了在执行strcat
之前为s1
分配足够的空间, 那么在strcat
函数执行之后,s1
的数据将溢出到s2
所在的空间中, 导致s2
保存的内容被意外地修改, 如图 2-8 所示
以上这个例子就是缓冲区溢出,而SDS不会发生缓冲区溢出的原因是:当SDS API需要对SDS进行修改时,API会通过free这个属性,判断其可用空间是否足够,如果足够的话就直接修改;如果不够,API会自动拓展SDS的空间至执行修改所需的大小,然后再执行实际的修改操作。
总结一下的话其实就是:C语言字符串的空间拓展需要程序员手动判断并拓展,如果没有拓展就有可能发生缓冲区溢出,而SDS的API会自动的帮我们拓展空间,不需要程序员手动拓展空间,这样就杜绝了缓冲区溢出的发生,并且SDS基于len和free这两个属性执行的拓展空间操作,也比C语言的执行效率快得多。
减少修改字符串池带来的内存重分配次数
内存重分配指的就是在修改字符串时,由于内存空间不足或者超出,而需要执行的内存重分配操作,该操作由于涉及到内存分配,执行操作的时间成本极高,所以我们应该尽量避免内存重分配,而SDS就利用了len和free这两个属性,使用两种优化策略,减少了内存重分配次数。
空间预分配(针对拓展空间)
C字符串的空间拓展策略,是你需要多少空间,我就给你多少空间,当你给字符串拓展空间后其实它的可用空间还是为0。
而SDS的API对一个SDS进行修改,并且需要对SDS进行空间拓展的时候,程序不仅会为SDS分配修改所必需的空间,还会为SDS分配额外的未使用空间。
其中, 额外分配的未使用空间数量由以下公式决定:
如果对 SDS 进行修改之后, SDS 的长度(也即是len
属性的值)将小于1 MB
, 那么程序分配和len
属性同样大小的未使用空间, 这时 SDSlen
属性的值将和free
属性的值相同。 举个例子, 如果进行修改之后, SDS 的len
将变成13
字节, 那么程序也会分配13
字节的未使用空间, SDS 的buf
数组的实际长度将变成13 + 13 + 1 = 27
字节(额外的一字节用于保存空字符)。如果对 SDS 进行修改之后, SDS 的长度将大于等于1 MB
, 那么程序会分配1 MB
的未使用空间。 举个例子, 如果进行修改之后, SDS 的len
将变成30 MB
, 那么程序会分配1 MB
的未使用空间, SDS 的buf
数组的实际长度将为30 MB + 1 MB + 1 byte
。
通过这种预分配策略, SDS 将连续增长N
次字符串所需的内存重分配次数从必定N
次降低为最多N
次。
惰性空间释放(针对回收空间)
C字符串的回收策略是立即使用内存重分配来回收缩短后多出来的字节。这样每一次缩短都会执行一次空间重分配。
而SDS不会立即执行内存重分配,而是使用free属性将这些字节的数量记录起来,并等待将来使用。
举个例子,sdstrim
函数接受一个 SDS 和一个 C 字符串作为参数, 从 SDS 左右两端分别移除所有在 C 字符串中出现过的字符。
比如对于图 2-14 所示的 SDS 值s
来说, 执行:
sdstrim(s, "XY"); // 移除 SDS 字符串中的所有 'X' 和 'Y'
会将 SDS 修改成图 2-15 所示的样子。
注意执行sdstrim
之后的 SDS 并没有释放多出来的8
字节空间, 而是将这8
字节空间作为未使用空间保留在了 SDS 里面, 如果将来要对 SDS 进行增长操作的话, 这些未使用空间就可能会派上用场。
通过惰性空间释放策略, SDS 避免了缩短字符串时所需的内存重分配操作, 并为将来可能有的增长操作提供了优化。
与此同时, SDS 也提供了相应的 API , 让我们可以在有需要时,真正地释放SDS 里面的未使用空间, 所以不用担心惰性空间释放策略会造成内存浪费。
存储任意格式的二进制文件
C 字符串中的字符必须符合某种编码(比如 ASCII), 并且除了字符串的末尾之外, 字符串里面不能包含空字符, 否则最先被程序读入的空字符将被误认为是字符串结尾 —— 这些限制使得 C 字符串只能保存文本数据, 而不能保存像图片、音频、视频、压缩文件这样的二进制数据。
而SDS可以用来存储这些二进制数据,这也是为什么我们把buff数组称为字节数组的原因,buff数组保存的是一系列二进制数据,而不是字符。
通过使用二进制安全的 SDS , 而不是 C 字符串, 使得 Redis 不仅可以保存文本数据, 还可以保存任意格式的二进制数据。
兼容部分C字符串函数
SDS 的API会把SDS保存的数据的末尾设置为空字符,所以保存了文本数据的SDS可以重用一部分<string.h>库定义的函数。
总结
参考书籍
《Redis 设计与实现》黄建宏