牛逼！Redis 的字符串是这样实现的…

迈不过友情╰ 2023-02-08 15:58 135阅读 0赞

> 来源：小小木的博客
> 
> www.cnblogs.com/wyc1994666/p/10669212.html

之前本人在找工作面试时在Redis相关问题上可栽了跟头。

在面试前按常规套路准备了一下，比如 Redis 的常用5种数据结构，Redis持久化策略，Redis实现[分布式锁][Link 1]，简单[发布订阅][Link 2]等等都准备了，当时不知天高地厚以为十拿九稳了，可是万万没想到我终究还是在Redis的被问的第一个问题上翻船了～～

**面试官 ：** 看你简历上写了熟悉常用数据结构，都有哪些说说  
**本人 ：** 常用有5种，string,list,set,zset,hash（内心很得意）

**面试官 ：** 那你说说都用过哪些数据结构\_    
**本人 ：** 用的最多的是string，通常会把json字符串存进去\_

**面试官 ：** 那你知道Redis内部是怎么实现它的string的么？\_    
**本人 ：** 呃～，我了解Redis是用C语言写的，至于具体实现就不清楚了～

到此一面卒～～～

有相同经历的朋友么？

--------------------

回去后恶补了一下Redis有关原理性的知识点，恰好最近在最总结面试经历于是有了今天这篇文章。

本篇会讲以下内容：

*  Redis字符串的实现
 *  Redis字符串的性能优势

## Redis字符串的实现 ##

Redis虽然是用C语言写的，但却没有直接用C语言的字符串，而是自己实现了一套字符串。目的就是为了提升速度，提升性能，可以看出Redis为了高性能也是煞费苦心。

Redis构建了一个叫做简单动态字符串（Simple Dynamic String），简称SDS

### 1.SDS 代码结构 ###

struct sdshdr{  
        //  记录已使用长度  
        int len;  
        // 记录空闲未使用的长度  
        int free;  
        // 字符数组  
        char[] buf;  
    };

SDS ？什么鬼？可能对此陌生的朋友对这个名称有疑惑。只是个名词而已不必在意，我们要重点欣赏借鉴Redis的设计思路。下面画个图来说明，一目了然。

![20200724133429168.png][]

Redis的字符串也会遵守C语言的字符串的实现规则，即最后一个字符为空字符。然而这个空字符不会被计算在len里头。

### 2.SDS 动态扩展特点 ###

SDS的最厉害最奇妙之处在于它的Dynamic。动态变化长度。举个例子

![20200724133547586.png][]

如上图所示刚开始s1 只有5个空闲位子，后面需要追加' world' 6个字符，很明显是不够的。那咋办？Redis会做以下三个操作：

1.  计算出大小是否足够
2.  开辟空间至满足所需大小
3.  开辟与已使用大小len相同长度的空闲free空间（如果len < 1M）开辟1M长度的空闲free空间（如果len >= 1M）

看到这儿为止有没有朋友觉得这个实现跟Java的列表List实现有点类似呢？看完后面的会觉得更像了。

## Redis字符串的性能优势 ##

*  快速获取字符串长度
 *  避免缓冲区溢出
 *  降低空间分配次数提升内存使用效率

### 1.快速获取字符串长度 ###

再看下上面的SDS结构体：

由于在SDS里存了已使用字符长度len，所以当想获取字符串长度时直接返回len即可，时间复杂度为O(1)。如果使用C语言的字符串的话它的字符串长度获取函数时间复杂度为O(n),n为字符个数，因为他是从头到尾（到空字符'\\0'）遍历相加。

### 2.避免缓冲区溢出 ###

对一个C语言字符串进行strcat追加字符串的时候需要提前开辟需要的空间，如果不开辟空间的话可能会造成缓冲区溢出，而影响程序其他代码。如下图，有一个字符串s1="hello" 和 字符串s2="baby",现在要执行strcat(s1,"world"),并且执行前未给s1开辟空间，所以造成了缓冲区溢出。

![format_png][]

而对于Redis而言由于每次追加字符串时都会检查空间是否够用，所以不会存在缓冲区溢出问题。每次追加操作前都会做如下操作：

1.  计算出大小是否足够
2.  开辟空间至满足所需大小

### 3.降低空间分配次数提升内存使用效率 ###

字符串的追加操作会涉及到内存分配问题，然而内存分配问题会牵扯内存划分算法以及系统调用，如果频繁发生的话会影响性能，所以对于性能至上的Redis来说这是万万不能忍受的。推荐：[Redis 内存满了怎么办][Redis]？

所以采取了以下两种优化措施

*  空间预分配
 *  惰性空间回收

**1. 空间预分配**

对于追加操作来说，Redis不仅会开辟空间至够用而且还会预分配未使用的空间(free)来用于下一次操作。至于未使用的空间(free)的大小则由修改后的字符串长度决定。

当修改后的字符串长度len < 1M,则会分配与len相同长度的未使用的空间(free)

当修改后的字符串长度len >= 1M,则会分配1M长度的未使用的空间(free)

有了这个预分配策略之后会减少内存分配次数，因为分配之前会检查已有的free空间是否够，如果够则不开辟了～

**2. 惰性空间回收**

与上面情况相反，惰性空间回收适用于字符串缩减操作。比如有个字符串s1="hello world"，对s1进行sdstrim(s1," world")操作，执行完该操作之后Redis不会立即回收减少的部分，而是会分配给下一个需要内存的程序。当然，Redis也提供了回收内存的api,可以自己手动调用来回收缩减部分的内存。

到此为止结束了～

下次在遇到这个问题可以侃侃而谈了，哈哈哈~

[Link 1]: http://mp.weixin.qq.com/s?__biz=MzI3ODcxMzQzMw==&mid=2247490786&idx=2&sn=c8e8eb055714a912a3c95da3aeaa053c&chksm=eb5399d4dc2410c2e111c2508a70340b46f0ae83aac1f4b7cf0caa1e11d04c14316deabb76f3&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzI3ODcxMzQzMw==&mid=2247492816&idx=2&sn=2f563a5c6feadf55ebb8bd2bbd011dc2&chksm=eb5061e6dc27e8f05b2e89bda91b05f26f1cdd2e7af9e9c0b956424a65bf699adfa1510a0fd5&scene=21#wechat_redirect
[20200724133429168.png]: /images/20230208/1609c6a77e70439bb5d7db9ccdd0f044.png
[20200724133547586.png]: https://img-blog.csdnimg.cn/20200724133547586.png
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9UTlV3S2hWMEpwU1dpYnBsOFFSWlBwQnBCVWljQ0hYcmljNlFFeWljUUJORUZyeHNZWjhyUnVRdG5zUVRYalRYV2JEeVl4U2Qxb0tHaWJLNmtrN1BnY2ljdFl3QS82NDA?x-oss-process=image/format,png
[Redis]: http://mp.weixin.qq.com/s?__biz=MzI3ODcxMzQzMw==&mid=2247491125&idx=2&sn=38b8fe0def22de8da49d49b42793dee9&chksm=eb539b03dc241215d5860327cacf923cf2aa709635f2bc6f14a098721dcb4fe717008c460636&scene=21#wechat_redirect