Redis01-Redis的数据结构之简单动态字符串SDS

前言

Redis用了这么久，一直没有认真的去了解其内部的数据结构和实现原理。从今天开始正式系统性的学习Redis。首先，还是从工作中经常打交道的数据类型开始说起，然后，在说到其内部使用的数据结构。

Redis的简介

Redis是一个开源的高性能的key-value数据库，与其他的key-value缓存产品相比有以下三个特点：

Redis支持数据的持久化，可以将内存中的数据持久化到硬盘中，主要有RDB和AOF两种方式。

Redis 不仅仅支持简单的key-value类型的数据，还提供了list、set、zset、hash等数据类型的存储。

Redis支持数据的备份，即master-slaver模式的数据备份。

数据类型

Redis支持5种数据类型：如下表所示：

数据结构

Redis中有如下几种数据结构。分别是：

简单动态字符串（sds）

链表

字典

跳跃表

整数集合

压缩列表

Redis的key是顶层模型，它的value是扁平化的，Redis中，所有的value都被包装成一个对象object。所以，Redis并不是直接使用这些数据结构来实现键值对数据库。而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象，每种对象都用到了至少一种上面提到的数据结构。

这个redisObject的定义是：

typedef struct redisObject { unsigned [type] 4; unsigned [encoding] 4; unsigned [lru] REDIS_LRU_BITS; int refcount; void *ptr; } robj;

1

2

3

4

5

6

7

type: 数据类型，就是我们熟悉的String、hash、list等。

encoding: 内部编码，其实就是数据结构，指的是当前的这个value底层是用的什么数据结构，因为同一个数据类型底层也有多种数据结构的实现，所以这里需要指定数据结构。

lru: 当前对象可以保留的时长，这个我们在后面的讲键的过期策略的时候会讲。

refcount: 对象引用计数，用于GC。

ptr: 指针，指向以encoding的方式实现的这个对象的实际地址。

下面就是数据类型与数据结构的对应关系：(图片来源于Redis基本类型及其数据结构)

简单动态字符串（SDS）

Redis没有直接使用C语言传统的字符串（以空字符串结尾的字符数组，在Redis中C字符串只会作为字符串字面量，用在一些无需对字符串进行修改的地方，如打印日志），而是自己构建了一种名为简单动态字符串（simple dynamic string,SDS）的抽象类型，并将SDS用作Redis的默认字符串表示，在Redis数据库中，包含字符串值的键值对都是由SDS实现的（Redis中所有的值对象中包含的字符串对象底层也是由SDS实现）。

其数据结构的定义如下：

struct sdshdr{ //记录buf数组中未使用字节的数量，如上图free为0代表未使用字节的数量为0 int free; //记录buf数组中已使用字节的数量即SDS的长度，如上图len为5代表未使用字节数量为5 int len; //字节数组用于保存字符串 sds遵循了c字符串结尾的惯例目的是为了重用c字符串函数库里的函数 char buf[]; }

1

2

3

4

5

6

7

8

为什么要用SDS

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

由于C字符串并不记录自身的长度信息，所以为了获取一个C字符串的长度，程序必须遍历整个字符串，对遇到的每个字符串进行计数，直到遇到代表字符串结尾的空字符串为止，时间复杂度是O(N)，而SDS的len属性中记录了SDS本身已使用自己的长度。所以获取一个SDS长度的复杂度是O(1)。

2. 杜绝缓冲区溢出

C字符串并不记录自身长度带来的另一个问题是容易造成缓冲区溢出（buffer overflow）。例如：有两个紧邻着的C字符串S1和S2,其中S1保存了字符串"REDIS",而S2 则保存了字符串"MYSQL"。如果一个程序员执意要通过strcat(s1,“ORCAL”); 将S1的内容修改为 “REDISORCAL”，但是粗心的他去忘记了在执行stact之前为s1分配足够的空间，那么在strcat 函数执行之后，s1的数据将溢出到s2所在的空间中，导致s2保存的内容被意外的修改，如下图所示：

与C字符串不同的是，当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需要的要求，如果不满足的话，API会自动将SDS的空间扩展至执行修改时所需要的大小，然后才执行实际的修改操作，所以使用SDS既不需要手动修改SDS的空间大小，也不会出现前面说的缓冲区溢出的问题。

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

C字符串中，如果对字符串进行修改，那么我们就不得不面临内存重分配，因为C字符串是由一个N+1长度的数组组成，如果字符串的长度变长，我们就必须对数组进行扩容，否则会产生内存溢出，而如果字符串长度变短，我们就必须释放掉不再使用的空间，否则会发生内存泄露。所以，每次增长或者缩短一个C字符串，程序都总要对保存这个C字符串的数组进行一次内存重分配操作。

因为内存重分配涉及复杂的算法，并且可能需要执行系统调用，所以它通常是一个比较耗时的操作，由于Redis作为数据库，经常被用于速度要求严苛，数据被频繁修改的场合，如果每次修改字符串的长度都需要执行一次内存重分配的话，那么光是执行内存重分配的时间就会占去修改字符串所有事件的一大部分。为了避免C字符串的这种缺陷，SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联：在SDS中，buf数组的长度不一定就是字符串数量加一，数组里面可以包含未使用的字节，而这些字节的数量就是由SDS的free属性记录的。

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

空间预分配

数组在进行扩容的时候，往往会申请一个更大的数组，然后把数组复制过去。为了提升性能，我们在分配空间的时候并不是分配一个刚噶好的空间，而是分配一个更大的空间，Redis同样基于这种策略提供了空间预分配，当执行字符串增长操作并且需要扩展内存时，程序不仅仅会给SDS分配必要的空间还会分配额外的未使用空间，其长度存到free属性中。

如果修改后len的长度小于1M，这时分配给free的大小和len一样，例如修改后为10字节，那么给free也是10字节，buf的长度变成了10+10+1=21byte。

如果修改后len长度将大于等于1M，这是分配给free的长度为1M，例如修改过后为30M，那么给free是1M，buf的实际长度变成了30M+1M+1byte。

惰性空间释放

惰性空间释放用于字符串缩短的操作，当字符串缩短时，程序并不是立即使用内存重分配来收缩短出来的字节，而是使用free属性记录起来，并等待将来使用。

4.二进制安全

C字符串中的字符必须符合某种编码（比如ASCII）,并且除了字符串的末尾之外，字符串里面不能包含空字符串，否则最先被程序读入的空字符串将被误认为是字符串的结尾，这些限制使得C字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据。而SDS的buf字节数组不是在保存字符，而是一系列二进制数组，SDS API都会以二进制的方式来处理buf数组里的数据，使用len属性的值而不是空字符串来判断字符串是否结束。

总结

本文主要介绍了Redis数据库用来存储字符串对象的数据结构—简单动态字符串SDS，SDS相对于C语言传统的字符串优势明显，主要表现在杜绝缓存区内存溢出，减少字符串操作的内存重分配，二进制安全。

参考

《Redis的设计与实现》

Redis基本类型及其数据结构

简单动态字符串SDS

Redis 数据结构

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。