Redis 把字符串String设计成 SDS的原因
之前的米扑博客《Redis 数据结构底层实现》介绍了Redis底层数据原理。
今天，再次回顾一遍，并以Redis 把字符串String设计成 SDS的原因，做深入探讨。
Redis 数据结构图
Redis 数据模型
用键值对 name:"小明" 来展示Redis的数据模型如下：
1）dictEntry: 在一些编程语言中，键值对的数据结构被称为字典，而在Redis中，会给每一个key-value键值对分配一个字典实体，就是“dictEntry”。dictEntry包含三部分： key的指针、val的指针、next指针，next指针指向下一个dictEntry形成链表，这个next指针可以将多个哈希值相同的键值对链接在一起，通过链地址法来解决哈希冲突的问题
2）SDS（Simple Dynamic String，简单动态字符串）：存储字符串数据。
3）redisObject：Redis的5种常用类型都是以RedisObject来存储的，redisObject中的type字段指明了值的数据类型（也就是5种基本类型)。ptr字段指向对象（数据value）所在的地址。
RedisObject对象很重要，Redis对象的类型、内部编码、内存回收、共享对象等功能，都是基于RedisObject对象来实现的。
这样设计的好处是：可以针对不同的使用场景，对5种常用类型设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率。
Redis将jemalloc作为默认内存分配器，减小内存碎片。
Redis中所有的数据结构类型
| 底层数据结构 | 编码常量 | object encoding指令输出 |
|---|---|---|
| 整数类型 | REDIS_ENCODING_INT | "int" |
| embstr字符串类型 | REDIS_ENCODING_EMBSTR | "embstr" |
| 简单动态字符串 | REDIS_ENCODING_RAW | "raw" |
| 字典类型 | REDIS_ENCODING_HT | "hashtable" |
| 双端链表 | REDIS_ENCODING_LINKEDLIST | "linkedlist" |
| 压缩列表 | REDIS_ENCODING_ZIPLIST | "ziplist" |
| 整数集合 | REDIS_ENCODING_INTSET | "intset" |
| 跳表和字典 | REDIS_ENCODING_SKIPLIST | "skiplist" |
补充说明
redis的官方网站打开官方的数据类型介绍：https://redis.io/topics/data-types-intro
假如面试官问：redis的数据类型有哪些？
回答：string、list、hash、set、zset、Bitmaps、Streams、HyperLogLogs
Redis 把字符串String设计成 SDS的原因
面试官：了解redis的String数据结构底层实现嘛?
求职者：当然知道，是基于SDS实现的
面试官：redis是用C语言开发的，那为啥不直接用C的字符串，还单独设计SDS这样的结构呢?
其实，看得出面试官是想看看，求职者是只停留在redis的使用层面，还是对Redis底层数据结构，有过更深入的研究，面试嘛都爱这样问大家都懂得，面的都是造飞机的题目，进公司后拧螺丝钉。。。
我们知道redis是用C写的，但Redis却没有完全直接使用C的字符串，而是自己又重新构建了一个叫简单动态字符串SDS（simple dynamic string）的抽象类型。
redis也支持使用C语言的传统字符串，只不过会用在一些不需要对字符串修改的地方，比如静态的字符输出。
而我们开发中使用redis，往往会经常性的修改字符串的值，这个时候就会用SDS来表示字符串的值了。
有一点值得注意：在redis数据库中，key-value键值对含有字符串值的，都是由SDS来实现的。
比如：
在redis执行一个最简单的set命令，这时redis会新建一个键值对。
127.0.0.1:6379> set xiaofu "程序员内点事"
此时键值对的key和value都是一个字符串对象，而对象的底层实现分别是两个保存着字符串 xiaofu 和 程序员内点事 的SDS结构。
再比如：
向一个列表中压入数据，redis 又会新建一个键值对。
127.0.0.1:6379> lpush xiaofu "程序员内点事" "程序员小富"
这时候键值对的键和上边一样，还是一个由SDS实现的字符串对象，键值对的值是一个包含两个字符串对象的列表对象了，而这两个对象的底层也是由SDS实现。
1、SDS 结构
一个SDS值的数据结构，主要由 len、free、buf[] 这三个属性组成。
struct sdshdr{
int free; // buf[]数组未使用字节的数量
int len; // buf[]数组所保存的字符串的长度
char buf[]; // 保存字符串的数组
}
其中
buf[]为实际保存字符串的char类型数组；
free表示buf[]数组未使用字节的数量；
len表示buf[]数组所保存的字符串的实际长度。
例如上图，表示的是buf[]保存长度为6个字节的字符串，未使用的字节数free为0，但是眼尖的同学会发现这明明是7个字符，还有一个"\0"啊？
上边提到过，SDS没有完全直接使用C的字符串，还是沿用了一些C特性的，比如遵循C的字符串以空格符结尾的规则，这样还可以使用一部分C字符串的函数。而对于SDS来说，空字符串占用的一字节是不计算在len属性里的，会为他分配额外的空间。
简单了解SDS结构后，下边我们来看看SDS相比于C字符串有哪些优点。
2、SDS 效率高
举个例子：工作中使用redis，经常会通过STRLEN命令得到一个字符串的长度，在SDS结构中len属性记录了字符串的长度，所以我们获取一个字符串长度直接取len的值，复杂度是O(1)。
而如果用C字符串，在获取一个字符串长度时，需对整个字符串进行遍历，直至遍历到空格符结束（C中遇到空格符代表一个完整字符串），此时的复杂度是O(N)。
在高并发场景下频繁遍历字符串，获取字符串的长度很有可能成为redis的性能瓶颈，所以SDS性能更好一些。
3、数据溢出
上边提到C字符串是不记录自身长度的，相邻的两个字符串存储的方式可能如下图，为字符串分配了合适的内存空间。
如果此时我想把“程序员内点事”改成“程序员内点事123”，可之前分配的内存只有6个字节，修改后的字符串需要9个字节才能放下啊，怎么搞？
没办法只能侵占相邻字符串的空间，自身数据溢出，导致其他字符串的内容被修改。
而SDS很好的规避了这点，当我们需要修改数据时，首先会检查当前SDS空间len是否满足，不满足则自动扩容空间至修改所需的大小，然后再执行修改,如下图所示。
不过有个特殊的地方，在把“程序员内点事”的6个字节扩容到“程序员内点事123”9个字节后，发现free属性的值变成了扩容后字符串的总长度，这就涉及到下边要说的内存重分配策略了。
4、内存重分配策略
C字符串长度是一定的，所以每次在增长或者缩短字符串时，都要做内存的重分配，而内存重分配算法通常又是一个比较耗时的操作，如果程序不经常修改字符串还是可以接受的。
但很不幸，redis作为一个数据库，数据肯定会被频繁修改，如果每次修改都要执行一次内存重分配，那么就会严重影响性能。
SDS通过两种内存重分配策略，很好的解决了字符串在增长和缩短时的内存分配问题。
1）空间预分配
空间预分配策略用于优化SDS字符串增长操作，当修改字符串并需对SDS的空间进行扩展时，不仅会为SDS分配修改所必要的空间，还会为SDS分配额外的未使用空间free，下次再修改就先检查未使用空间free是否满足，满足则不用在扩展空间。
通过空间预分配策略，redis可以有效的减少字符串连续增长操作，所产生的内存重分配次数。
额外分配未使用空间free的规则：
-
如果对 SDS 字符串修改后，
len值小于1M，那么此时额外分配未使用空间free的大小与len相等。 -
如果对 SDS 字符串修改后，
len值大于等于1M，那么此时额外分配未使用空间free的大小为1M。
2）惰性空间释放
惰性空间释放策略，则用于优化SDS字符串缩短操作，当缩短SDS字符串后，并不会立即执行内存重分配来回收多余的空间，而是用free属性将这些空间记录下来，如果后续有增长操作，则可直接使用。
5、数据格式多样性
C字符串中的字符必须符合某些特定的编码格式，而且上边我们也提到，C字符串以\0空字符结尾标识一个字符串结束，所以C语言里，字符串里边是不能包含\0的，不然就会被误认是多个。
由于这种限制，使得C语言字符串只能保存文本数据，像音视频、图片等二进制格式的数据是无法存储的。
redis 会以处理二进制的方式操作Buf数组中的数据，所以对存入其中的数据做任何的限制、过滤，只要存进来什么样，取出来还是什么样。
总结
上边只是 redis 数据结构的一点基础知识，没什么难度，但以我的面试经验，如果被问这类问题，不要只含糊其辞的说出底层是SDS，有理有据的把为什么这样实现也说出来。
一来可以显得自己基本功扎实，如果表达的在条理清晰，是个很不错的加分项；
二来主动打消面试官问下去的念头，当然就怕不按套路出牌的人！
最后，附上一张 Redis 核心知识图谱
Redis 内存淘汰机制
Redis的内存淘汰机制一般有6种，如下图所示：
参考推荐：
BloomFilter + Redis 大数据去重策略的实现
版权所有: 本文系米扑博客原创、转载、摘录，或修订后发表，最后更新于 2021-03-28 05:41:54
侵权处理: 本个人博客，不盈利，若侵犯了您的作品权，请联系博主删除，莫恶意，索钱财，感谢！