[大数据] Redis（1）----浅谈SDS（简单动态字符串）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 大数据 -> Redis（1）----浅谈SDS（简单动态字符串） -> 正文阅读

[大数据]Redis（1）----浅谈SDS（简单动态字符串）

1，前言

读黄健宏老师的《Redis设计与实现》所作笔记

2，概述

Redis并没有直接使用C语言传统的字符串，而是自己构建了一种名为简单动态字符串的抽象类型，并将SDS用作Redis的默认字符串表示。

Redis只有在不需要对字符串值进行修改的场景下，才会使用C的字符串，例如在打印日志时。

SET msg "hello world"

执行上面的命令后，Redis将在数据库中创建一个新的键值对，其中：

键值对的键是一个字符串对象，其底层实现是一个保存着字符串“msg”的SDS
键值对的值也是一个字符串对象，对象的底层实现是一个保存着字符串“hello world”的SDS

除了用于保存字符串值之外，SDS还被用作缓冲区（buffer）：例如AOF模块中的AIF缓冲区，以及客户端状态中的输入缓冲区。

3，结构

每个sdshdr结构表示一个SDS值

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

若保存一个值为“Redis”的字符串，其图解为：
在这里插入图片描述

4，好处

Redis使用SDS来存储字符串，这样做的好处是？

4.1，获取字符串长度

因为C字符串不记录自身的长度信息，这就导致了每当要获取字符串长度信息的时候，需要遍历整个字符串来获取长度，这种遍历当遇到空字符时停止【因为C规定每个字符串后面实际上都有一个空字符(\0)来表示这个字符串到此为止了】

对于SDS，其长度信息是有一个专门的属性进行记录的：len

所以不难得出，C字符串获取长度的操作，其复杂度为O(N)；而SDS的复杂度为O(1)

4.2，杜绝缓冲区溢出

C字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出。例如我们用指针来存储两个字符串：”Redis“和”MongoDB“

那么这两个字符串有可能会这样存储：
在这里插入图片描述

那么当我们想要给S1字符串追加一些内容，例如” Cluster“；那么修改后的结果应为：“Redis Cluster”，但如果程序员在修改之前，忘记为S1字符串分配足够的空间，那么追加后的结果就有可能为：
在这里插入图片描述
这是因为S1的字符串覆盖了S2指向的内存空间，

SDS的空间分配策略能完全杜绝发生缓冲区溢出的可能性：当SDS API需要对SDS进行修改时，API会先检查剩余的空间（free的值）是否足够；如果不足的话，就会进行空间的扩展，再进行修改操作。

改为SDS来进行操作的话，该是怎么样的？

用SDS存储“Redis”
使用sdscat函数进行字符串拼接

（1）用SDS存储“Redis”
在这里插入图片描述

（2）执行sdscat

在这里插入图片描述

使用SDS的API里面用于拼接操作的sdscat函数，它可以将一个C字符串拼接到给定的SDS所保存的字符串值后面。但是在拼接前，它会检查SDS的剩余空间是否足够，不够的话就会进行扩展，然后再执行拼接操作。

这里要值得注意的是，执行操作后，SDS里面的字符串长度（属性len）为13，并且还预分配了13字节长度的内存空间（属性free）供使用。

4.3，减少修改字符串带来的内存重分配次数

C字符串并不记录自身的长度，一个长度为N的字符串，其底层实现是一个长度为N+1的数组。

每当增长或缩减一个字符串时，就需要对这个数组进行一次内存再分配：

当增长一个字符串时，需要给其申请更多的空间以存放新增的字符
当缩减字符串时，给数组“裁剪”到一定的长度，进行存储

在一般的程序中，如果修改字符串长度的操作不太常出现，那么每次执行修改操作就进行一次内存重分配，这并非无法接受。但在Redis这种对速度要求严格、数据频繁修改的场合里，这无疑是致命的，因为内存重分配是一个耗时操作，频繁的修改意味着频繁的内存重分配。

那么SDS是如何解决这个问题的？

这与free属性有关，SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联。在SDS中，buf数组的长度不一定就是字符串长度+1，也有可能是字符串长度+1+未使用空间长度

通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略【分别对应增长和缩减字符串两种情况】

空间预分配

当SDS的API对一个SDS进行修改并且需要扩展空间的时候，程序除了分配必要的空间外，还会分配额外的未使用空间。

其中，分配多少未使用空间由以下的公式决定：

如果对修改过后的SDS，字符串的长度（也就是属性len）将会小于1MB，那么程序分配和len属性同样大小的未使用空间。这使得free属性的值会和len属性的值相等
如果修改过后的长度大于1MB，那么程序除了分配必要的空间之外，还会分配1MB的未使用空间

举个例子：

Redis中声明字符串s，值为Redis
执行sdscat(s, " Cluster")
再执行sdscat(s," Tutorial")

那么这个SDS的变化会是这样的：
在这里插入图片描述

惰性空间释放

当使用SDS的API进行字符串修改，会缩减字符串长度的时候，程序不会马上释放多出来的空间，而实使用free属性将那些空间保存下来，并等待将来使用。

如果下次需要对这个SDS进行拼接操作，而free属性记录的长度又满足拼接的需求，那么就不需要再进行内存重分配。

值得一提的是，SDS提供了相应的API，供我们在有需要的时候释放SDS的未使用空间。所以不需要担心惰性空间释放会造成内存浪费

4.4，二进制安全

SDS的API都是二进制安全的，所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其中的数据做任何的限制、过滤、或者假设，数据在写入时是怎么样的，它被读取时就是怎么样的。这也就是我们将SDS的buf属性称为字节数组的原因----Redis不是用这个数组来保存字符，而是用它来保存一系列二进制数据。