Redis底层数据结构之string

我们都知道， Redis 是由 C 语言编写的。在 C 语言中，字符串标准形式是以空字符 \0 作为结束符的，但是 Redis 里面的字符串却没有直接沿用 C 语言的字符串。主要是因为 C 语言中获取字符串长度可以调用 strlen 这个标准函数，这个函数的时间复杂度是 O(N) ，由于 Redis 是单线程的，承受不了这个时间复杂度。

在上一篇文章中，我们介绍了 Redis 的 RedisObject 的数据结构，如下所示：

对于不同的对象， Redis 会使用不同的类型来存储。对于同一种类型 type 会有不同的存储形式 encoding 。对于 string 类型的字符串，其底层编码方式共有三种，分别为 int 、 embstr 和 raw 。

使用 object encoding key 可以查看 key 对应的 encoding 类型，如下所示：

对于 embstr 和 raw 这两种 encoding 类型，其存储方式还不太一样。对于 embstr 类型，它将 RedisObject 对象头和 SDS 对象在内存中地址是连在一起的，但对于 raw 类型，二者在内存地址不是连续的。

在介绍 string 类型的存储类型时，我们说到，对于 embstr 和 raw 两种类型其存储方式不一样，但 ptr 指针最后都指向一个 SDS 的结构。那什么是 SDS 呢？ Redis 中的字符串称之为 Simple Dynamic String ，简称为 SDS 。与普通 C 语言的原始字符串结构相比， sds 多了一个 sdshdr 的头部信息， sdshdr 基本数据结构如下所示：

可以看出， SDS 的结构有点类似于 Java 中的 ArrayList 。 buf[] 表示真正存储的字符串内容， alloc 表示所分配的数组的长度， len 表示字符串的实际长度，并且由于 len 这个属性的存在， Redis 可以在 O(1) 的时间复杂度内获取数组长度。

为了追求对于内存的极致优化，对于不同长度的字符串， Redis 底层会采用不同的结构体来表示。在 Redis 中的 sds.h 源码中存在着五种 sdshdr ，分别如下：

上面说了， Redis 底层会根据字符串的长度来决定具体使用哪种类型的 sdshdr 。可以看出， sdshdr5 明显区别于其他四种结构，它一般只用于存储长度不会变化，且长度小于32个字符的字符串。但现在一般都不再使用该结构， 因为其结构没有 len 和 alloc 这两个属性,不具备动态扩容操作 ，一旦预分配的内存空间使用完，就需要重新分配内存并完成数据的复制和迁移，类似于 ArrayList 的扩容操作，这种操作对性能的影响很大。

上面介绍 sdshdr 属性的时候说过， flag 这个属性用于标识使用哪种 sdshdr 类型， flag 的低三位标识当前 sds 的类型，分别如下所示：

同时，注意到在每个 sdshdr 的头定义上都有一个 attribute((packed)) ，这个是为了告诉 gcc 取消优化对齐 ，这样，每个字段分配的内存地址就是 紧紧排列在一起的 ， Redis 中字符串参数的传递直接使用 char* 指针，其实现原理在于，由于 sdshdr 内存分配禁止了优化对齐，所以 sds[-1] 指向的就是 flags 属性的内存地址，而通过 flags 属性又可以确定 sdshdr 的属性，进而可以读取头部字段确定 sds 的相关属性。

sds的逻辑图如下所示：

相比较于 C 语言原始的字符串， sdshdr 的具备一些优势。

由于 sdshdr 中存在 len 这个属性，所以可以在 O(1) 的时间复杂度下获得长度；而传统的 C 语言得使用 strlen 这个标准函数获取，时间复杂度为 O(N) 。

原始的 C 语言一直使用与长度匹配的内存，这样在追加字符串导致字符串长度发生变化时，就必须进行内存的重新分配。内存重新分配涉及到复杂算法和系统调用，耗费性能和时间。对于 Redis 来说，它是单线程的，如果使用原始的字符串结构，势必会引发频繁的内存重分配，这个显然是不合理的。

因而， sds 每次进行内存分配时，都会通过内存的预分配来减少因为修改字符串而引发的内存重分配次数。这个原理可以参数 Java 中的 ArrayList ，一般在使用 ArrayList 时都会建议使用带有容量的构造方式，这样可以避免频繁 resize 。

对于 SDS 来说，当其使用 append 进行字符串追加时，程序会用 alloc-len 比较下剩下的空余内存是否足够分配追加的内容 ，如果不够自然触发内存重分配，而如果剩余未使用内存空间足够放下，那么将直接进行分配，无需内存重分配。其扩容策略为， 当字符串占用大小小于1M时，每次分配为 len * 2，也就是保留100%的冗余；大于1M后，为了避免浪费，只多分配1M的空间。

通过这种预分配策略， SDS 将连续增长 N 次字符串所需的内存重分配次数 从必定 N 次降低为最多 N 次。

缓冲区溢出是指当某个数据超过了处理程序限制的范围时，程序出现的异常操作。 原始的 C 语言中，是由编码者自己来分配字符串的内存，当出现内存分配不足时就会发生 缓存区溢出 。而 sds 的修改函数在修改前会判断内存，动态的分配内存，杜绝了 缓冲区溢出 的可能性。

对于原始的 C 语言字符串来说，它会通过判断当前字符串中是否存在空字符 \0 来确定是否已经是字符串的结尾。因而在某些情况下，如使用空格进行分割一段字符串时，或者是图片或者视频等二进制文件中存在 \0 等，就会出问题。而 sds 不是通过空字符串来判断字符串是否已经到结尾，而是通过 len 这个字段的值。所以说， sds 还具备 二进制安全 这个特性，即可以安全的存储具有特殊格式的二进制数据。

https://www.cnblogs.com/reecelin/p/13358432.html