Redis底层实现及原理

关键词

SDS embstr 二进制安全 空间预分配

String类型不同的编码方式

• 使用整数存储： 只对长度小于或等于 21 字节，并且可以被解释为整数的字符串进行编码
• 使用EMBSTR 编码： 尝试将 RAW 编码的字符串编码为 EMBSTR 编码，
• 使用SDS编码: 这个对象没办法进行编码，尝试从 SDS 中移除所有空余空间 下面举个例子看一下👇

embstr与动态字符串

• embstr的创建只需分配一次内存，而raw为两次（一次为sds分配对象，另一次为redisObject分配对象，embstr省去了第一次）。 相对地，释放内存的次数也由两次变为一次。
• embstr的redisObject和sds放在一起，更好地利用缓存带来的优势
• 但是redis并未提供任何修改embstr的方式，即embstr是只读的形式。对embstr的修改实际上是先转换为raw再进行修改。

SDS(simple dynamic string)

SDS定义

1
2
3
4
5
6
7
8
9

struct sdshdr{
     //记录buf数组中已使用字节的数量
     //等于 SDS 保存字符串的长度
     int len;
     //记录 buf 数组中未使用字节的数量
     int free;
     //字节数组，用于保存字符串
     char buf[];
}

SDS有什么优点

1、常数复杂度获取字符串长度

sdshdr 中由于 len 属性的存在，获取 SDS 字符串的长度只需要读取 len 属性，时间复杂度为 O(1)，而对于 C 语言来说， 获取字符串的长度通常是遍历字符串计数来实现的，时间复杂度为 O(n)。

2、杜绝缓冲区溢出

我们知道在 C 语言中使用 strcat 函数来进行两个字符串的拼接，一旦没有分配足够长度的内存空间，就会造成缓冲区溢出。而对于 SDS 数据类型，在进行字符修改的时候， 会首先根据记录的 len
属性检查内存空间是否满足需求，如果不满足，会进行相应的空间扩展，然后在进行修改操作，所以不会出现缓冲区溢出。

3、减少修改字符串时带来的内存重分配次数

C语言由于不记录字符串的长度，所以如果要修改字符串，必须要重新分配内存（先释放再申请），因为如果没有重新分配，字符串长度增大时会造成内存缓冲区溢出，
字符串长度减小时会造成内存泄露。而对于SDS，由于len属性和free属性的存在，对于修改字符串SDS实现了空间预分配和惰性空间释放两种策略：

3.1 字符串长度增加操作时，进行空间预分配

对字符串进行空间扩展的时候，扩展的内存比实际需要的多，这样可以减少连续执行字符串增长操作所需的内存重分配次数。

3.2 字符串长度减少操作时，惰性空间释放

对字符串进行缩短操作时，程序不立即使用内存重新分配来回收缩短后多余的字节，而是使用 free 属性将这些字节的数量记录下来，等待后续使用。
（当然SDS也提供了相应的API，当我们有需要时，也可以手动释放这些未使用的空间。

4、二进制安全

因为C字符串以空字符作为字符串结束的标识，而对于一些二进制文件（如图片等），内容可能包括空字符串，因此C字符串无法正确存取； 而所有 SDS 的API 都是以处理二进制的方式来处理 buf 里面的元素，并且 SDS
不是以空字符串来判断是否结束，而是以 len 属性表示的长度来判断字符串是否结束。

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

虽然 SDS 是二进制安全的，但是一样遵从每个字符串都是以空字符串结尾的惯例，这样可以重用 C 语言库<string.h> 中的一部分函数。

为什么字符串长度大于44就是用raw方式编码

这个是因为C语言函数库分配内存的长度只能是2/4/8/16/32/64；最大分配64位的长度；
但是redisObj的长度加上字符串对象头的长度，占用20位，所以字符串长度最多是44位，超过这个长度，就是用raw方式进行编码； – 《Redis深度历险-String数据结构》

参考资料

1、《闲扯Redis二》String数据类型之底层解析
2、每个程序员都应该知道的Redis知识 - String底层原理
3、Redis详解（四）—— redis的底层数据结构
4、redis string底层数据结构