redis的5种对象与8种数据结构之字符串对象(下)

引言

本文是对《redis设计与实现(第二版)》中数据结构与对象相关内容的整理与说明。本篇文章只对对象结构，1种对象——字符串对象。以及字符串对象所对应的两种编码——raw和embstr，进行了详细介绍。表达一些本人的想法与看法，也希望更多朋友一起来讨论，分享交流。

字符串对象

字符串对象可以存储整数、浮点数、字符串，具体策略是：

当存储整数时，用到的编码是int，底层的数据结构可以用来存储long类型的整数；
当存储字符串时，如果字符串的长度小于等于32字节，那么将用编码为embstr的格式来存储；如果字符串的长度大于32字节，将用编码为raw的SDS格式来存储；
当存储浮点数时会先将浮点数转换为字符串，如果转换后的字符串长度小于32字节就用编码为embstr的格式来存储，否则用编码为raw的SDS格式来存储。

下图是一个字符串对象的结构图，最左侧是对象结构，中间跟右侧合起来是raw编码的SDS数据结构(sdshdr)，示例图：

raw编码，简单动态字符串(simple dynamic string-SDS)

redis用的并不是C语言传统的字符串，而是自己构建了简单动态字符串(simpledynamic string,SDS)。

当redis打印日志信息或输出报错信息，这些输出的字符串是不会被修改的字符串字面量(sting literal)，此时用的是C语言传统的字符串来存储这些信息的。当redis需要存储的是可以被修改的字符串时，就会使用SDS结构。

除了用来保存数据库中的字符串值之外，SDS还被用作缓冲区(buffer)：AOF模块中的AOF缓冲区，以及客户端状态中的输入缓冲区，都是由SDS实现的。

SDS的结构

SDS结构示意图如下所示：

sdshdr是该数据结构的名称即SDS，其中：

buf属性，是一个字节数组，用来保存字符串，后面箭头对应的就是实际保存的字符串内容，最后以’0’空字符串结尾；

len属性，记录的是buf数组中实际已使用的字节数量，等于SDS所保存字符串的长度；

free属性，记录的是buf数组中未使用字节的数量。

SDS优点

一、可以用O(1)的复杂度获取到字符串长度

SDS的len属性记录了字符串的长度，而传统C字符串要想知道长度需要遍历整个字符串。相比于传统C字符串，redis获取字符串长度所需的复杂度从O(N)降低到了O(1)。

即使对非常长的字符串反复执行STRLEN命令(获取字符串长度)，也不会造成过多的性能消耗。

二、杜绝缓冲区溢出

在传统的C字符串中，如果要修改字符串的内容，但修改后字符串的长度超过原先的长度就会发生溢出现象。详见下图：

在SDS中，当需要对buf字节数组中存储的内容进行修改(增添或删除)时，API会先通过free和len属性检查SDS的空间是否足够，如果不够的话，SDS会自动扩展空间再对内容进行修改。关于自动扩展空间的策略见下方“空间预分配”的内容。

三、减少修改字符串长度时所需的内存重分配次数

对于传统C字符串：

如果执行的是增长字符串的操作，如拼接操作(append)，那么在执行命令之前，程序需要先通过内存重分配来扩展底层数据的空间大小——否则会产生缓冲区溢出。

如果执行的是缩短字符串的操作，如截断操作(trim)，那么在执行这个操作之后，程序需要通过内存重分配来释放字符串不再使用的空间——否则会产生内存泄漏。

对于redis中的SDS结构：

内存重分配设计复杂的算法，是一个比较耗时的操作，redis作为速度要求严苛、数据会被频繁执行的数据库，如果每次修改字符串都需要进行一次内存重分配，会严重影响性能。

使用SDS，buf数组里可以包含未使用的字节，这些字节的数量由free属性记录，可以减少修改字符串长度时所需的内存重分配次数。

空间预分配和惰性空间释放

通过SDS中free属性定义的未使用空间，SDS可以实现空间预分配和惰性空间释放两种优化策略：

1、空间预分配策略——可以降低字符串增长操作引起的内存重分配

当需要修改SDS的内容，且需要进行空间扩展的时候，程序不仅会为SDS分配修改所需的必须空间，还会为SDS分配额外的未使用空间。

其中，额外分配的未使用空间数量由以下公式决定：

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

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

说明

如果对一个字符串的末尾持续追加内容，当字符串整体大小大于1MB时，即使只追加一字节的字符，程序也会额外分配1MB的空间，当再次追加一字节的字符时，程序不会再额外分配1MB的空间，而是使用已有的空闲空间。

即在扩展空间之前，会先检查未使用的空间是否足够，如果足够，是不会额外再扩展的。

通过空间预分配策略，SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次。

2、惰性空间释放策略——可以降低字符串缩短操作引起的内存重分配

当SDS中的字符串长度被缩短时，程序并不会立即使用内存重分配来回收缩短后多出来的字节空间，而是使用free属性将这些字节的数量记录起来，以备将来使用。

当然，redis提供了相应的命令来真正释放这些未使用空间，避免不必要的内存浪费。

四、二进制安全

C字符串中的字符必须符合某种编码(比如ASCII)，并且除了字符串的末尾之外，字符串里面不能包含空字符，如果字符串除末尾外还有其它空字符，那么最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据，而不能保存图片、音频、视频、压缩文件这样的二进制数据。

为了确保redis可以适用于各种不同的使用场景，SDS的API都是二进制安全的(binary-safe)，所有SDS API都会以处理二进制的方式来处理SDS存放buf数组里的数据，程序不会对其中的数据做任何限制、过滤或者假设，数据在写入时是什么样的，它被读取时就是什么样。

这也是RDS的buf属性被称为字节数组的原因——redis不是用这个数组来保存字符，而是用它来保存一系列二进制数据。

五、兼容部分C字符串函数

SDS遵循空字符串结尾这一惯例，好处是可以直接重用C字符串函数库里的函数，从而避免了不必要的代码重复。

embstr编码

如果字符串对象保存的是长度小于等于32字节的字符串，那么将会使用embstr编码，embstr编码是专门用来保存短字符串的一种优化编码方式。embstr编码与raw编码对应的字符串对象，都是由对象结构(redisObject)和数据结构(sdshdr)组成的。

区别在于用raw编码的字符串对象会调用两次内存分配函数来分别创建redisObject结构和sdshdr结构，而embstr编码则通过调用一次内存分配函数来分配一块连续的空间，空间中一次包含redisObject和sdshr两个结构，embstr编码的字符串对象结构图如下所示：

两者的区别

embstr编码的字符串对象在执行命令时，产生的效果和raw编码的字符串对象执行命令时产生的效果是相同的的，但使用embstr编码的字符串对象来保存短字符串值有以下好处：

1、embstr编码将创建字符串对象所需的内存分配次数从raw编码的两次降低为一次；

2、释放embstr编码的字符串对象只需要调用一次内存释放函数，而释放raw编码的字符串对象需要调用两次内存释放函数；

3、embstr编码的字符串对象的所有数据都保存在一块连续的内存里，结构更加紧凑，而raw编码是分散开的，redisObject对象结构和sdshdr数据结构彼此间是用指针相关联的，embstr编码的对象比raw编码的对象能够更好的利用缓存带来的优势。

编码的转换

int编码的字符串对象和embstr编码的字符串对象在条件满足的情况下，会被转换成raw编码的字符串对象。encoding命令可以查看键对应的值，底层用的是什么编码。

int转换为raw

对于int编码的字符串对象来说，如果我们向对象执行了一些命令，使得这个对象保存的不再是整数值，而是一个字符串值，那么字符串对象的编码将从int变为raw。

27.0.0.1:6379> set a 100    //设置a=100
OK
127.0.0.1:6379> object encoding a    //查看键a存储的值用的是什么编码
"int"    
127.0.0.1:6379> append a 'a'  //向键a的值中追加内容’a’，此时键a存储的值将变为字符串类型
(integer) 4
127.0.0.1:6379> get a  //查询键a的值
"100a"  
127.0.0.1:6379> object encoding a    //查看键a存储的值现在对应的编码，发现已经变为raw格式的编码，表示里面现在存储的是字符串
"raw"

int编码的字符串，存储的是long类型的整数，范围是2^63-1(2的63次方减一) ~ -2^63(2的63次方)，当存储的整数在该范围内时，编码为int，当值超过该范围，编码将转换为embstr。

27.0.0.1:6379> set number1 9223372036854775807  
OK
127.0.0.1:6379> object encoding number1    
"int"
127.0.0.1:6379> set number2 9223372036854775808  
OK
127.0.0.1:6379> object encoding number2
"embstr"
127.0.0.1:6379> set number3 -9223372036854775808
OK
127.0.0.1:6379> object encoding number3
"int"
127.0.0.1:6379> set number4 -9223372036854775809
OK
127.0.0.1:6379> object encoding number4
"embstr"

embstr转换为raw

embstr编码的字符串对象无法被修改(redis没有为embstr编码的字符串对象编写任何响应的修改程序)，只有int、raw编码的字符串对象可以被修改，所以embstr编码的字符串实际上是只读的。

当对embstr编码的字符串对象执行任何修改命令时，程序都会先将对象的编码从embstr转换为raw，然后再执行修改命令。所以一旦embstr编码的字符串被修改，它的数据结构就会变成raw编码的格式。

127.0.0.1:6379> set a 'ab'
OK
127.0.0.1:6379> object encoding a
"embstr"
127.0.0.1:6379> append a 'c'
(integer) 
3127.0.0.1:6379> get a
"abc"
127.0.0.1:6379> object encoding a
"raw"

以上就是根据《redis设计与实现(第二版)》中数据结构与对象相关内容进行的部分整理与分享。