Redis 底层数据结构

时间：2020-03-02 19:41:13 收藏：0 阅读：72

简单动态字符串（SDS）

字符串（String）是 Redis 中最简单的数据结构，但是这里的字符串（String）并不是 Java 中的字符串，也不是 C 语言中的字符串。尽管 Redis 是用 C 语言开发的。

Redis 自己构建了一种名为简单动态字符串（Simple Dynamic String, SDS）的抽象类型，作为它的默认字符串表示。所以，Redis 数据类型中的字符串指的是 SDS。

举个例子，如果客户端执行下面这个 set 命令：

1 SET msg "Hello World"

那么 Redis 将在数据库中创建一个新的键值对。其中：

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

SDS 除了用来保存数据库中的字符串值之外，还可以被用作缓冲区（buffer）。AOF 模块中的 AOF 缓冲区以及客户端状态中的输入缓冲区，都是由 SDS 实现的。

SDS 的定义

SDS 的文件中有几个重要属性：

buf：是一个 char 类型的数组，用于保存 SDS 字符串的值；
len：记录 buf 中已使用字节的数量，等于 SDS 中保存的字符串的长度；
free：记录 buf 数组中未使用的字节数，也就是剩余的空闲空间；

SDS 遵循 C 语言中字符串以空字符结尾的惯例，保存空字符的 1 字节空间不计算在 SDS 的 len 属性中，并且为空字符分配额外 1 字节的空间，以及添加空字符到字符串末尾等操作，都是由 SDS 函数自动完成的。遵循 C 语言中字符串以空字符串结尾这一惯例的好处，就是 SDS 可以直接重用一部分 C 字符串函数库中的函数。

Redis 中为什么不用 C 语言中的字符串存储键值？

常数复杂度获取字符串长度

因为 C 字符串并不记录自身的长度信息，所以要获取一个 C 字符串的长度，需要遍历整个字符串，直到遇到字符串结尾的空字符为止，这个操作的时间复杂度是 O(N)。而与 C 字符串不同的是：SDS 中维护了一个 len 属性，记录字符串长度，直接读取 len 值就可以得到字符串的长度，时间复杂度为 O(1)。设置和更新 SDS 长度的工作是由 SDS 的 API 在执行时自动完成的，不需要开发人员干预。

避免缓冲区溢出

在 C 语言中，使用字符串不当可能会导致缓冲区溢出的问题。比如使用字符串的 strcat 函数将字符串 “Redis” 和 “MongoDB” 拼接到一起时，如果此时字符串 “Redis” 中的剩余空间 free 为 3，存不下字符串 “MongoDB”，那么将会发生缓冲区溢出的问题。而 SDS 的空间分配策略杜绝了发生缓冲区溢出的可能：当 SDS API 需要对 SDS 修改时，API 会先检查 SDS 的空间是否满足修改所需的要求。如果不满足的话，API 会自动将 SDS 的空间扩展至执行修改所需的大小，然后再执行修改操作。

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

在 C 语言中，一个包含了 N 个字符的字符串，它的底层实现总是一个 N+1 个字符长的数组（数组末尾的 1 个字符空间用于保存空字符），所以每次增长或缩短一个 C 字符串，程序总要对保存这个字符串的数组进行一次内存重分配操作。

Redis 经常被用于高并发的场景中，对于数据性能有着非常高的要求。如果每次修改字符串的长度，都需要执行一次内存重新分配的话，当字符串修改频繁发生时，可能会影响 Redis 的性能。为了避免 C 字符串中的这种缺陷，SDS 中的 buf 数组长度不一定就是字符数量加 1，它可以包含一些未使用的空闲空间，用 free 属性记录。

通过未使用空间，SDS 实现了空间预分配和惰性空间释放两种优化策略。

空间预分配

空间预分配用于优化 SDS 的字符串增长操作：当 SDS 的 API 对一个 SDS 进行修改，且需要扩展 SDS 的存储空间的时候，程序不仅会为 SDS 分配执行修改所必须的空间，还会为 SDS 分配额外的未使用空间。其中，分配的未使用空间时遵循以下策略：

如果对 SDS 修改后，SDS 的长度（len）将小于 1MB，那么程序会为 SDS 分配一个和 len 属性同样大小的未使用空间。例如字符串 str 修改后，长度为 13KB，程序会为它分配 13KB 的未使用空间，那么字符串 str 的实际长度将变成 13KB+13KB+1byte。
如果对 SDS 修改后，SDS 的长度（len）会大于或等于 1MB，那么程序会为 SDS 分配 1MB 的未使用空间。例如字符串 str 修改后，长度将变成 30MB，程序会为它分配 1MB 的未使用空间，则字符串 str 的实际长度将为 30MB+1MB+1byte。

惰性空间释放

惰性空间释放用于优化 SDS 的字符串缩短操作：当 SDS 的 API 需要缩短 SDS 中的字符串时，程序并不会立即使用内存重分配回收字符串缩短后多出来的字节空间，而是使用 free 属性将这些字节的数量记录起来，并等待将来使用。

通过空间预分配和惰性空间释放策略，Redis 可以缩减字符串修改时的内存重分配次数。对 SDS 修改 N 次时，最多触发 N 次内存重分配，实际中很可能会小于 N。

二进制安全

C 语言中，字符串中的字符必须符合某种编码（如 ASCII），并且除了字符串末尾外，字符串里面不能包含空字符（C 字符串以空字符作为结束标志）。这些限制使得字符串只能保存文本数据，而不能保存图片、音频、压缩文件这样的二进制数据。而 SDS 中的 API 是二进制安全的，它不会对 buf 数组中的数据做任何限制、过滤，数据在写入时是什么样，它被读取时就是什么样。SDS 的 API 会以处理二进制的方式来处理 buf 数组中的数据。这也是我们将 buf 数组称为字节数组的原因----Redis 不是用这个数组来保存字符，而是用它来保存一系列二进制数据。

兼容部分 C 字符串函数

SDS 保存了 C 字符串的惯例，在它的 buf 数组中会多维护 1 字节的空间，存储一个空字符，作为字符串的结尾。以使 SDS 可以兼容 C 字符串函数库中的部分函数。如 strcasecmp 函数，可以比较两个字符串的值。

链表

原文：https://www.cnblogs.com/juxiemushu/p/12396335.html