Redis的内部数据结构之SDS

redis的内部数据结构

前言

自从换了新工作还没有这么有时间编辑过文章，熟悉新业务和新架构是一个自我提升的过程，现在终于腾出手来，回顾这段时间接触到的技术，发现还是有许多不足的地方，很多东西你会用是会用，懂也是懂，但是不清楚原理，还是没有那种这门技术完完全全就脱光了在你面前，那种透彻的感觉。

这一次的话也是发现这边很多用到 redis 的地方，对于 redis 的内部实现也越来越干兴趣，看了下相关书籍，于是这边也是有了几个问题想去详细的解决:

  • Redis五中数据类型分别是有什么数据结构实现的？
  • Redis的字符串数据类型既可以存储字符串（比如"hello world"），又可以存储整数和浮点数（比如10086和3.14），甚至是二进制位（使用SETBIT命令），Redis内部是如何存储这些值的？

像这种问题还有好几个，不过这里主要是想说一下 数据结构 相关的问题。

redis的数据结构与对象

我们都知道 redis 面试经常遇到的问题：

redis的五种基本数据结构分别是哪几种？答：字符串(strings)，哈希表(hashes)，列表(lists)，集合(sets)，有序集合(sorted sets)等等。

这里的话，在回答完这五种基本数据结构之后，假如你继续说：

这里我还有了解对应redis源码里面的数据结构，比如。。。。。

我相信是个面试官都不会打断你，并等你装完。如果你答的还算可以的话，这是可以成为一个比较小的加分项的！

首先，Redis源码是 C语言 实现的，所以往下的话我会基于c的语法来给大家讲解。

简单动态字符串

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

redis中，C 字符串只会作为普通常量用在一些无需对字符串进行修改的地方，比如打印日志。

redisLog(REDIS_WARNING, "Redis is now ready to exit. bye bye");

为什么需要用到SDS呢？

SDS

我们来看看SDS的定义：
每个 sds.h/sdshdr 结构表示一个SDS值：

struct sdshdr {
    int len;
    int free;
    char buf[];
}

简单带大家了解以下SDS结构，如图：

  • free 属性表示这个SDS未使用的空间大小，这里表示该SDS没有分配任何未使用空间。
  • len 属性表示这个SDS已使用的空间大小，这里表示该SDS保存了五字节长的字符串。
  • buf 属性是一个char类型的数组，数组前五个字节分别保存了'R'、'e'、'd'、'i'、's'五个字符，而最后一个字节则保存了空字符'\0'。

SDS 遵循 C 字符串以 空字符结尾 的惯例，保存空字符的 1 字节空间不计算在 SDS 的 len 属性里面，并且为空字符分配额外的 1 字节空间，以及添加空字符到字符串末尾等操作，都是由 SDS 自己完成的，所以这个空字符对于使用者来说 完全透明 。这么做的好处在于以空字符结尾的话，SDS 可以直接重用一部分 C 字符串函数库里面的函数。

举个例子：

// 打印 sds 的 buf 数组。
printf("%s", s->buf);
// 输出：Redis

我们可以直接打印出 SDS 保存的字符串值 'Redis'，而无需另外编写打印函数。

然后我们再看另外一个 SDS 示例：

我们可以看到，free为5，这里我们提前给 SDS 多分配了 5 个未使用的字节空间。那么这未使用的字节空间到底有啥用？我们继续往下看。

SDS 和 C 字符串的区别

我们都知道，C 语言使用长度为 N+1 的字符数组来表示长度为 N 的字符串，结尾的 1 则为 '\0'。
上面也有提到，Redis 使用 SDS 来替代了 C字符串作为默认字符串表示。主要的原因就是在于以下几点：

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

首先我们得清楚 C 字符串并不会记录本身的长度信息，所以为了获取 C 字符串的长度就得遍历整个字符串，对遇到的每个字符进行计数，直到遇到空字符串位置，这个 操作的复杂度为 O(N) 。而 SDS 的话相信不用我说都可以理解，直接返回 len就行了，所以 SDS 查看字符串长度 操作的复杂度为O(1) 。

# 所以即使我们反复的对一个非常长的字符串键值对执行 STRLEN 命令
# 也不会对系统造成任何影响，因为STRLEN命令的复杂度仅为O(1)
redis> STRLEN KEY
(Integer) 6666

杜绝缓冲区溢出

除了获取字符串长度复杂度高以外，C字符串不记录自身长度带来的问题是容易造成 缓冲区溢出（buffer overflow）。

举个例子，假如程序里有两个在内存中紧邻着的 C 字符串 s1 和 s2，其中 s1 保存了字符串 "Redis"，而 s2 则保存了字符串 "MongoDB"，如图：

如果在这时执行 strcat 并 忘记在执行前未 s1 分配足够的空间 ：

// 将 s1 "Redis" -> "Redis Cluster"
strcat(s1, " Cluster");

那么在这之后， s1 的数据将会被溢出到 s2 所在的空间中，导致 s2 保存的内容被意外修改 （Mongodb -> Cluster），如图：

这就是 C 字符串缓冲区溢出的场景。而 SDS 的空间分配策略则完全杜绝了发生缓冲区溢出的可能性: 当 SDS API 需要对 SDS 进行修改时，API 会先检查 SDS 的空间是否满足修改所需的要求，如果不满足的话 API 会自动将 SDS 的空间进行扩容，然后再执行修改操作，所以 相比于 C 字符串，SDS完全杜绝了缓冲区溢出的问题 。

下面给大家看看 SDS 具体是如何扩容的：
SDS 的 API 里也有一个用于执行拼接的 sdscat 函数，它可以将一个 C 字符串拼接到给定 SDS 所保存的字符串后面，但是再执行拼接操作之前，SDS 会先检查给定的 SDS 的空间 free 够不够，如果不够则先扩容，然后再进行拼接操作。

// 同样是 s1 的场景，假如 s1 类型为 SDS 如上图
// 插入 " Cluster"
sdscat(s1, " Cluster");
// 我们可以发现 SDS 内部做了一次扩容的操作，如下图

s1 在修改前，先判断，发现 s1 的空间不足以拼接 " Cluster" 后，sdscat 就会先扩展 s1 的空间，然后再执行拼接操作。

ps: sdscat 不仅对这个 SDS 进行了拼接操作，它还为 SDS 分配了 13 字节的未使用空间 ，并且拼接之后的字符串也正好是 13 字节长，这种现象与 SDS 的空间分配策略有关，那我们来看看。

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

现在我们知道，C 字符串并不记录自身的长度，所以对于一个包含了 N 个字符的 C 字符串来说，这个 C 字符串的底层 实现的总是一个 N+1 个字符长的数组 （额外一个字符用于保存空字符），所以每次增长或者缩短一个 C 字符串，程序总要对保存这个 C 字符串的数组进行一次内存重分配操作：

  • 如果对一个 C 字符串进行增长的操作（append），那么在执行这个操作 之前 ，程序需要先 通过内存重分配来扩展底层数组的空间大小 （如果忘了这一步，就会产生 缓冲区溢出 ）。
  • 如果对一个 C 字符串进行缩短的操作（trim），那么在这个操作 之后 ，程序需要 通过内存重分配来释放字符串不再使用的那部分空间 （如果忘了这一步，就会产生 内存泄漏 ）。

这里的 内存重分配 涉及复杂的算法，并且可能需要执行系统调用，所以它通常是一个比较耗时的操作：

  • 在一般程序中，如果修改字符串长度的情况不太常现，那么每次修改都执行一次内存重分配是可以接受的。
  • 但是 Redis 作为数据库，对性能的要求极高，如果每次修改长度都需要一次内存重分配的话，那么光执行内存重分配的时间就会占用修改字符串所用时间的一大部分，十分影响性能。

让我们再来看看 SDS 的数据结构：

struct sdshdr {
    int len;
    // 未使用空间，可以在长度足够的情况下避免内存再分配。
    int free;
    char buf[];
}

SDS 为了避免反复分配内存的缺陷，我们可以看到它通过了未使用空间解除了字符串长度和底层数组长度之间的关联：在 SDS 中，buf 数组的长度不一定就是字符数量加一，数字里面可以包含未使用的字节，这就是一种预分配空间的做法。

在这里就有人问了：上面说到在字符串缩短操作之后，有可能会出现内存泄漏的情况，那么 SDS 既然预分配了空间，它是如何避免内存泄漏的呢？

这里通过未使用空间， SDS 不仅仅实现了 空间预分配 ，它还实现了 惰性空间释放 的优化策略，下面简单介绍以下这两种优化策略：

  1. 空间预分配

空间预分配用于优化 SDS 的 字符串增长 操作：当 SDS 的 API 对一个 SDS 进行修改，并且需要对 SDS 进行空间扩展的时候，程序不仅会为 SDS 分配修改所必要的空间，还会为 SDS 分配额外的未使用空间。

  • 如果修改完 SDS 后，SDS 的长度（len）小于 1 MB，那么程序分配和 len 属性同样大小的未使用空间，这时（扩展后） SDS len 属性的值将与 free 的值相同 。比如修改后，SDS 的 len 改为了 13 字节，那么程序也会预分配 13 字节给 free 属性，SDS 的 buf 数组的实际长度将变成 13B+13B+1B（'/0'）=27 字节。
  • 如果修改完 SDS 后，SDS 的长度将大于 1 MB，那么程序会分配 1 MB 的未使用空间。比如修改后，SDS 的 len 改为 30 MB，那么程序会分配 1 MB 的未使用空间，SDS 的 buf 数组的实际长度将变成 30MB + 1MB + 1B。

通过这种空间预分配策略，Redis 可以 减少 连续执行字符串涉及长度修改操作所需的 内存重分配次数 。

  1. 惰性空间释放

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

举个例子：

// 移除字符串中所有的 'X' 和 'Y'
ststrim(s, "XY")；

在这一步缩短操作后，空出来的 8 个字节并 没有被立即释放 ，而是存在了未使用空间 free 上，假如同时：

// 在字符串后面插入字符串 ' Redis'
stscat(s, " Redis");

由于上面没有释放空间，而是作为预留空间存在了 SDS 里面，新来的这一次增长操作则 避免了一次内存重分配操作 。

所以通过惰性空间释放策略，SDS 避免了缩短字符串时所需的内存重分配操作，并未将来可能有的增长操作提供了优化 。

同时 SDS 也提供了相应的 API，让我们在有需要时，真正地释放 SDS 的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费。

二进制安全

首先我们来看一张图：

我们知道，C 字符串中的字符必须符合某种编码（比如 ASCII），并且除了字符串的结尾外，字符串里面不能包含空字符（'/0'），否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得 C 字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据 。

如上图，假如是 C 字符串的函数的话只会识别到 "Redis"，而忽略之后的 "Cluster"。

虽然数据库一般用于保存文本数据，但使用数据库来保存二进制数据的场景也不少见，因此，为了确保 Redis 可以适用于各种不同的场景，SDS 的 API 是 二进制安全 的（binary-safe），所有 SDS API 都会以处理二进制的方式来处理 SDS 存放的 buf 数组里的数据，程序不会对其中的数据做任何限制、过滤或者假设， 数据在写入时是什么样的，它被读取时就是什么样的 。

总结


Redis 只会使用 C 字符串作为字面量，在大多数情况下，Redis 使用 SDS （Simple Dynamic String，简单动态字符串）作为字符串表示。

  1. 常数级别获取字符串长度。
  2. 杜绝缓冲区溢出。
  3. 减少字符串长度修改所需的内存再分配次数。
  4. 二进制安全。

参考资料

  • 《Redis的设计与实现》
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 213,099评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,828评论 3赞 387
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 158,540评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,848评论 1赞 285
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,971评论 6赞 385
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,132评论 1赞 291
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,193评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,934评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,376评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,687评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,846评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,537评论 4赞 335
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,175评论 3赞 317
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,887评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,134评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,674评论 2赞 362
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,741评论 2赞 351