Redis是用ANSI C语言编写的，它是一个高性能的key-value数据库，它能够作用在数据库、缓存和消息中间件。其中 Redis 键值对中的键都是 string 类型，而键值对中的值也是有 string 类型，在 Redis 中 string 类型使用还是很宽泛的。本文次要介绍 string 的数据结构—— 简略动静字符串（Simple Dynamic String） 简称sds。

sds 实现

sds 的数据结构:

struct sdshdr {     //buf 已占用的长度     int len;     // buf 残余的可用的长度     int free;        // 保留字符串数据的中央     char buf[]; }

构造 sdshdr 保留了 len、free 和 buf 三个属性，别离记录字符的已应用的长度，未应用的长度，以及理论保留字符串的数组。
以下是一个新建的，保留 hello world 字符串的 sdshdr 构造：

struct sdshdr {    len = 5;    free = 0;    buf = "hello\0"; }
  • free 属性值为0，示意这个sds没有调配未应用的空间。
  • len 属性值为5，示意这个sds保留了一个五字节长的字符串。
  • buf 属性是一个 char 类型的数组，数组的前五个字节别离保留了 'h'、'e'、'l'、'l'、'o' 五个字符，而最初一个字节保留了空字符'\0'。

sds 恪守 C 字符串以空字符串结尾的常规，保留的空字符串一个字节空间不计算在 sds 的 len 属性外面。增加空字符串到字符串开端等操作，都是由 sds 函数主动实现的，所以这个空字符对于使用者来说齐全是通明的。

通过 len 属性，能够实现工夫复杂度 O(1) 的长度计算。另外通过对 buf 调配一些额定的空间，并应用 free 记录未应用空间的长度，sdshdr 能够缩小内存的重新分配。这是 sds 绝对 c 字符串的一个劣势。

为何 Redis 不必 C 语言示意字符串

Redis 是应用 C 语言开发的，而在应用最多的字符串上，Redis 没有应用 C 语言传统的字符串示意，而且应用本人构建的简略动静字符串（sds）。
在 C 语言中，字符串能够用一个 \0 结尾的 char 数组示意。比方 hello world 在 C 语言中就能够示意为"hello world\0"。数组个别初始化当前长度就曾经固定了，不能反对字符串追加append和长度计算操作：

  • 每次计算字符串长度都要遍历一遍数组，所以工夫复杂度是O(N)
  • 对字符串每次进行追加操作，须要对字符串进行一次内存调配

sds 优化追加字符操作

Redis 作为数据库，对于查问速度要求严格，数据批改也比拟频繁，如果每次批改字符串都须要执行一次内存调配的话，都会占用大量的工夫。所以 Redis 抉择了 sds 而不是 C 字符串，sds 能够缩小追加字符的内存调配。通过举例来说明，执行以下操作时，sds 外部的变动：

redis> set msg "hello world"OKredis> append msg " again"(integer)18redis> get msg"hello world again"

首先 set 命令创立并保留hello world 到一个 sdshdr 中，这个 sdshdr 的值如下：

struct sdshdr {     len = 11;     free = 0;     buf = "hello world\0";}

当执行 append 命令时，绝对应的 sdshdr 被更新，字符串 " again" 会被追加到原来的 "hello world" 之后：

struct sdshdr {     len = 17;     free = 17;     buf = "hello world again\0                ";}

当调用 set 命令创立 sdshdr 时，Redis 没有给 sdshdr 调配多余的空间，free 属性为0。而在执行 append 操作之后，Redis 为 buf 调配了多于所需空间一倍的大小。

在执行 append 命令之后，保留 "hello world again" 共须要17 + 1 个字节，然而程序为 sdshdr 调配了 17 + 17 + 1 = 35 个字节，而后续如果在对 sdshdr 进行追加操作，只有追加的长度不超过 free 属性值，那么就不须要对 buf 进行内存重调配。

比方执行当前命令并不会引起 buf 的内存重调配，因为新追加的字符串长度小于17：

redis> append msg  " again"(integer) 23

对应的 sdshdr 构造如下：

struct sdshdr {     len = 23;     free = 11;     buf = "hello world again again\0               ";}

redis 内存调配能够查看源码 sds.s/sdsMakeRoomFor，sdsMakeRoomFor 函数形容了内存调配的策略，上面的该函数的伪代码：

// sdshdr:追加前的字符// addlen：追加字符串sds sdsMakeRoomFor(sdshdr, addlen) {       // 多余空间大于追加空间，无序再分配内存，间接返回    if (free >= addlen) return s;    // 计算新字符的长度    newlen = (len+addlen);    // 如果新字符的长度小于 SDS_MAX_PREALLOC，就调配两倍新字符空间  //  如果新字符的长度大于 SDS_MAX_PREALLOC，就调配新字符空间 + SDS_MAX_PREALLOC 空间    if (newlen < SDS_MAX_PREALLOC)        newlen *= 2;    else        newlen += SDS_MAX_PREALLOC;    // 分配内存    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);    // 更新 free 属性    newsh.free = newlen - len;    return newsh;}
而对于字符的缩短操作，Redis 保留缩短后的字符串，此时并不会进行内存重调配，而是应用 free 属性记录缩短的字符长度。

总结

Redis 的 string 类型为何应用sds而不是 C 字符串，因为sds有两点劣势：

  • 计算字符长度，C 字符串复杂度O（n），而 sds 复杂度为 O（1）
  • 字符追加操作，C 字符串每次都须要对内存进行重调配，而 sds 每次会进行动静扩容，当增加字符小于闲暇字符时，不会对内容进行调配，缩小零碎等待时间

参考

Redis 设计与实现

如果感觉文章对你有帮忙的话，请点个赞吧!