redis 原理系列之--字符串存储的实现原理（1）
背景
redis功能强大，几乎已经成了现代大中型服务必备的缓存技术了。 除了十分给力的缓存功能，redis当做消息队列，数据库也有着不错的表现。
我们都知道，redis 有五种数据类型，string，list， hash， set 和zset。 其中 最基本的，同时也是最常用的 就是string了。 本文就来谈谈 redis内部，string 的实现原理：SDS（simple dynamic string）。
redis简单动态字符窜：SDS
- 在redis里，C语言的字符窜只用来放字符串字面量，即只有当无序对字符串修改的时候才用C的字符串，例如打印日志的时候。
- 除了基本的字符串存储之外，sds还用做缓冲区。AOF模块的缓冲区，和客户端状态的输入缓冲区，都是sds实现的。
SDS 定义
struct sdshdr {
// buf 中已占用空间的长度
int len;
// buf 中剩余可用空间的长度
int free;
// 数据空间
char buf[];
};
图示如下：
sds结构
-
简单解释一下： buf是一个字节数组，是用来放具体数据的。其长度是按一定策略伸缩的，具体解释在下面。 len 表示buf 中已经使用掉的长度，free表示 buf中尚未使用的长度。
-
buf内 sds 的字符串，总是以空字符结尾，这一点同c字符串一致。 因此sds 可以直接重用一部分c字符串函数库的函数。
SDS 与C字符串的对比 和优点
1，O(1) 获取字符串长度
- 因为sds已经存了数据的长度，所以获取字符串长度复杂度为O（1），而C字符串获取长度为O（n）。
2，杜绝缓冲区溢出导致的内存问题
- 假设内存区域有s1：“hi”，s2： “redis” 两个字符串，位置紧邻，如下图：
紧邻字符串被覆盖
- 此时需要给s1 追加一个“boy”， 如果是C字符串，忘记了在追加之前先给s1 分配空间，此时追加将导致 s2的值被意外的修改。 而使用 sds则不会有这个问题。 因为其封装好的函数，会在追加数据之前先检查 空间是否够用，如果不够用就扩容。
3，通过空间预分配和空间惰性释放 减少内存分配问题
-
当给sds的值追加一个字符串，而当前的剩余空间不够时，就会触发sds的扩容机制。扩容采用了空间预分配的优化策略，即分配空间的时候：如果sds 值大小< 1M ,则增加一倍； 反之如果>1M , 则当前空间加1M作为新的空间。
-
当sds的字符窜缩短了，sds的buf内会多出来一些空间，这个空间并不会马上被回收，而是暂时留着以防再用的时候进行多余的内存分配。这个是惰性空间释放的策略
4， 二进制安全
- c字符串必须符合某种编码（例如ASCII），且不能包含空字符。 这些限制使得 c字符窜不能保存图片，音频等二进制文件。 而sds的api 都是二进制安全的，其所有api 都会以处理二进制的方式来处理buf内的数据，所以不会有任何的限制。
SDS 的API接口列表
| 函数 | 作用 | 复杂度 |
|---|---|---|
| sdsnew | 以一个c字符窜为参数新建sds | O（N） |
| sdsempty | 新建空的sds字符串 | O(1) |
| sdsfree | 释放sds | O（N） |
| sdslen | 获取已使用长度 | O（1） |
| sdsavail | 获取未使用长度 | O（1） |
| sdsdup | 创建一个sds的副本 | O（N） |
| sdsclear | 清空 | O（1） |
| sdscat | 追加C字符串到sds | O（N） |
| sdscatsds | 追加sds字符串到sds | O（N） |
| sdscpy | 用c字符串覆盖sds值 | O（N） |
| sdsgrowzero | 用空字符串扩展 sds至给定长度 | O（N） |
| sdsrange | 删除给定区间外的数据 | O（N） |
| sdscmp | 对比sds是否相同 | O（N） |
| sdstrim | 从sds中去除给定c字符串中出现过的字符 | O（N*M） |
总结
sds 其实就是字符串数组的一个封装，但是由于考虑了多种场景，作者给它适配了多个高效、优雅的接口，使得 sds成为了一个存储字符串的优秀设计。使得sds成为一个独立的、可提供高效优质服务的基础实体。
我们在设计一些偏底层的数据结构、对象、甚至是数据库表的时候，可以参考sds的设计，从中寻找一些启发。
参考： 《Redis 设计与实现》 黄健宏
有收获就点个赞吧~
