【Redis 系列 2】Redis 字符串对象之 SDS(简单动态字符串) 实现原理分析
Redis 中为了实现二进制安全的字符串，对原有的 C 语言中的字符串做了改进。如下所示就是一个 SDS 字符串的结构：
struct sdshdr{
int len;//记录 buf 数组已使用的长度，即 SDS 的长度(不包含末尾的'\0')
int free;//记录 buf 数组中未使用的长度
char buf[];//字节数组，用来保存字符串
}
经过改进之后，在 Redis 中如果想要获取 SDS 的长度不用去遍历 buf 数组了，直接读取 len 属性就可以得到长度，时间复杂度一下就变成了 O(1)，效率大大提升，而且因为判断字符串长度不再依赖空字符’\0’，所以其能存储图片，音频，视频和压缩文件等二进制数据。
PS：不过需要注意的是，SDS 依然遵循了 C 语言字符串以’\0’结尾的惯例，这么做是为了方便复用 C 语言字符串原生的一些 API。
在 Redis 3.2 之后的版本，Redis 对 sds 又做了优化，按照存储空间的大小拆分成为了sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64，分别用来存储大小为：32 字节(25),256 字节(28)，64KB(216),4GB 大小(232)以及 264 大小的字符串（因为目前版本 key 和 value 都限制了只能使用 512MB，所以sdshdr64暂时并未使用到）。看源码的注释，对 value 而言sdshdr5并不会被使用到，但是 key 会被使用到，因为sdshdr5和其他类型也不一样，其并没有存储未使用空间，所以我的猜测是比较适用于使用大小固定的场景(比如 key 值)：
任意选择一种类型，其具体含义代表如下：
struct attribute ((packed)) sdshdr8 {
uint8_t len; //已使用空间大小
uint8_t alloc; //总共申请的空间大小(包括未使用的)
unsigned char flags; //用来表示当前 sds 类型是 sdshdr8 还是 sdshdr16 等
char buf[]; //真实存储字符串的字节数组
};
C 语言中因为字符串内部没有记录长度，所以如果扩充字符串的时候非常容易造成缓冲区溢出(buffer overflow)。
请看下面这张图，假设下面这张图就是内存里面的连续空间，可以很明显的看到，此时lonely和Redis两个字符串之间只有两个空位，那么这时候如果我们要将lonely字符串修改为lonelyWolf，那么就需要 4 个空间，这时候下面这个空间是放不下的，必须要重新申请空间，但是假如说程序员忘了申请空间，或者说申请了空间但是还是不够，那么就会出现后面的Redis字符串中的Re被覆盖了。
同样的，假如要缩小字符串的长度，那么也需要重新申请释放内存，否则，字符串一直占据着未使用的空间，会造成内存泄露。
所以说 C 语言避免缓存区溢出和内存泄露完全依赖于人为，很难把控，但是使用 SDS 就不会出现这两个问题，因为当我们操作 SDS 时，其内部会自动执行空间分配策略，无需人为操作，从而杜绝了上述两种情况的出现。
空间预分配
空间预分配指的是当我们通过 API 对 SDS 进行扩展空间的时候，假如未使用空间不够用，那么程序不仅会为 SDS 分配必须要的空间，还会额外分配未使用空间，未使用空间分配大小主要有两种情况：
1、假如扩大长度之后的 len 属性小于等于 1MB(即 1024*1024)，那么同时就会分配和 len 属性一样大小的未使用空间(此时 buf 数组已使用空间=未使用空间)。
2、假如扩大长度之后的 len 属性大于 1MB，那么就会分配 1MB 未使用空间大小。
执行空间预分配策略的好处是提前分配了未使用空间备用后，就不需要每次增大字符串都需要分配空间，减小了内存重分配的次数。
惰性空间释放
惰性空间释放指的是当我们需要通过 API 减小 SDS 长度的时候，程序并不会立即释放未使用的空间，而只是更新 free 属性的值，这样空间就可以留给下一次使用。而为了防止出现内存溢出的情况，SDS 单独提供给了 API 让我们在有需要的时候去真正的释放内存。
现在我们总结一下 SDS 和 C 语言中实现的字符串的区别
| C 字符串 | SDS |
| --- | --- |
| 只能保存文本类不含空字符串’\0’数据 | 可以保存文本或者二进制数据，允许包含空字符串’\0’ |
| 获取字符串长度的复杂度为 O(n) | 获取字符串长度的复杂度为 O(1) |
| 操作字符串可能会造成缓冲区溢出 | 不会出现缓冲区溢出情况 |
| 修改字符串长度 N 次，必然需要 N 次内存重分配 | 修改字符串长度 N 次，最多需要 N 次内存重分配 |
| 可以使用 C 字符串相关的所有函数 | 可以使用 C 字符串相关的部分函数 |
=======================================================================
上面讲了这么多，可能很多人会以为 Redis 底层就是直接用了 SDS 数据结构来存储，然而实际上并不是，我们回想一下 Redis 的全称是远程字典服务，所以在 Redis 中所有的数据类型都是将对应的数据结构再进行了一次包装，创建了一个字典对象来存储的。
每次创建一个 key-value 键值对，Redis 都会创建两个对象，一个是键对象，一个是值对象，而且**在 Redis 中，任何一个对象总是被包装成`redisObject
对象**，并同时将键对象和值对象通过dictEntry对象进行封装，如下就是一个dictEntry`对象（源码 dict.h 内）：
typedef struct dictEntry {
void *key;//指向 key，即 SDS
union {
void *val;//执行 value，即 5 大常用数据类型
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;//指向下一个 key-value 键值对(哈希值相同的键值对会形成一个链表，这种方式可以解决哈希冲突问题)
} dictEntry;
当我们执行如下命令：
set name lonely_wolf
会得到这样的一个对象(省略了一些无关的属性）：
上面的redisObject就是我们的值对象（实际上 key 也是一个 redisObject 对象）如下就是一个redisObject对象的数据结构定义(源码 server.h 内)：
typedef struct redisObject {
unsigned type:4;//对象类型（4 位=0.5 字节）
unsigned encoding:4;//编码（4 位=0.5 字节）
unsigned lru:LRU_BITS;//记录对象最后一次被应用程序访问的时间（24 位=3 字节）
int refcount;//引用计数。等于 0 时表示可以被垃圾回收（32 位=4 字节）
void *ptr;//指向底层实际的数据存储结构，如：SDS 等(8 字节)
} robj;
所以，最终我们可以把上面的图简化为如下图所示([x]会根据长度选择为合适的值)：
对象类型 type
对象类型即redisObject中的 type 属性，主要分为以下 5 种：
| 类型属性 | 描述 | type 命令返回值 |
| --- | --- | --- |
| REDIS_STRING | 字符串对象 | string |
| REDIS_LIST | 列表对象 | list |
| REDIS_HASH | 哈希对象 | hash |
| REDIS_SET | 集合对象 | set |
| REDIS_ZSET | 有序集合对象 | zset |
可以看到，这就是对应了我们 5 种常用的基本数据类型。
编码 encoding
编码即redisObject中的encoding属性。我们可以使用命令 object encoding 来查看当前对象的编码。
从上图也可以看到，在字符串对象中，主要有 3 种编码类型，如下表所示：
| 编码属性 | 描述 | object encoding 命令返回值 |
| --- | --- | --- |
| OBJ_ENCODING_INT | 使用整数的字符串对象 | int |
| OBJ_ENCODING_EMBSTR | 使用 embstr 编码的 SDS 实现的字符串对象 | embstr |
| OBJ_ENCODING_RAW | 使用 SDS 实现的字符串对象 | raw |
int 编码
当我们用字符串对象存储的是整型，且能用 8 个字节的 long 类型进行表示（即 263-1），则 Redis 会选择使用 int 编码来存储，而且此时redisObject对象中的 ptr 指针直接替换为 long 类型。
embstr 编码
当字符串对象中存储的是字符串，且长度小于 44(3.2 版本之前是 39)时，Redis 会选择使用 embstr 编码来存储。
raw 编码
当字符串对象中存储的是字符串，且长度大于 44 时，Redis 会选择使用 raw 编码来存储。
embstr 编码为什么从 39 位修改为 44 位
embstr 编码中，redisObject 和 SDS 是连续的一块内存空间，这块内存空间 Redis 限制为了 64 个字节，而 redisObject 占了 16 字节，Redis3.2 版本之前的 sds 占了 8 个字节，再加上字符串末尾’\0’占用了 1 个字节，所以：64-16-8-1=39 字节。
Redis3.2 之后 sds 做了优化，对于 embstr 编码会采用 sdshdr8 来存储，而 sdshdr8 占用的空间只有 24 位：3 字节(len+alloc+flag)+1 字节(’\0’字符)，所以最后就剩下了：64-16-3-1=44 字节。
评论