Redis - String 类型数据结构（SDS、Int）图文详解_redis string数据结构

​

一 前言

String 是最基本的 key-value 结构。 而 SDS 则作为 String 数据类型的一种数据结构实现。

String 类型没有直接使用C语言传统的字符串表示(以空字符 \0 结尾的字符数组，以下简称 C字符串)，而是自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型，并将 SDS 作为默认字符串表示。

Redis 客户端传入服务器的协议内容、 aof 缓存、 返回给客户端的回复等等， 这些重要的内容都是由 SDS 类型来保存的。只有在字符串不需要修改的时候采用 C字符串，其余情况都采用 SDS。

不直接使用 C字符串的原因大致下面几种：

1. C语言的字符串不记录自身长度，想要知道一个字符串的长度就必须遍历一遍字符串，复杂度为 O(N)，而Redis的字符串同样使用命令 STRLEN 的时候，复杂度为 O(1)。

2. 二进制安全，可以存储非文本数据的，包括视频，音频，图片等。SDS并不是像传统的C字符串(字符数组)一样，而SDS常被称作字节数组，采用以字节为单位的形式存储数据，而最后的 \0 也是一个字节，这样数据怎么样存入的，取出来的时候还是怎么样的，因此是二进制安全的。 因为在结构中定义了 len 属性，所以及时在字符串中间出现 \0 也是可以完整存储而不会被截断。

3. 可以高效地执行追加操作（append），加快追加操作的速度，并降低内存分配的次数，代价是多占用了一些内存，而且这些内存不会被主动释放。

二 应用场景

1. 存储数据 如常见存储 K-V 字符串、JSON字符串。
2. 程序计数 INCR 命令递增或递增一个数。
3. 分布式锁 使用 SET key value NX ，NX 不存在才写入。
4. 单点登录 可作为存储共享会话实现单点登录。

三 内部编码

String 对象的内部编码（encoding）有 3 种 ：int、raw和 embstr。

3.1 int 编码

String 如果存储的是整数值，并且这个整数值可以用 long 类型来表示，那么字符串对象会将整数值保存在字符串对象结构的ptr属性里面（将void*转换成 long），并将字符串对象的编码设置为int。

3.2 embstr 编码

String 如果存储的是字符串，并且字符串长度小于等于一定的长度则使用 embstr 编码方式（专门用于保存短字符串的一种优化编码方式）。

其中 redis 2.+ 长度小于等于 32 字节、redis 3.0-4.0 是 39 字节、redis 5.0 是 44 字节
。

3.3 raw 编码

String 如果存储的是字符串，并且字符串长度大于 embstr 编码的取值长度则使用 raw 方式编码。

3.4 小结

embstr 和 raw 编码都会使用SDS来保存值，但不同之处在于embstr会通过一次内存分配函数来分配一块连续的内存空间来保存 redisObject 和 SDS。

而 raw 编码会通过调用两次内存分配函数来分别分配两块空间来保存 redisObject 和 SDS。

1. embstr 编码将创建 redisObject 所需的内存分配次数从 raw 编码的两次降低为一次，释放内存也是如此。
2. redisObject 和数据在一块连续内存中，有助于 CPU 预读。

但如果对 embstr 编码字符串进行修改，需要对 redisObject 和 SDS 都进行重新分配。且不能直接对 embstr 进行修改，需要先转化为 raw 编码，故一般最好用于不会修改的字符串。

四 SDS 源码解读

Redis 有五种 SDS 实现方式 SDS_TYPE_5、SDS_TYPE_8、SDS_TYPE_16、SDS_TYPE_32、SDS_TYPE_64。

根据初始化的长度决定使用哪种类型，从而减少内存的使用。

4.1 数据结构

位于 sds.h 头文件

struct __attribute__ ((__packed__)) sdshdr8 {

    uint8_t len;         // 已经使用的字节数
    uint8_t alloc;       // 总共可用的字符空间大小，应该是实际buf的大小减1 (因为c字符串末尾必须是 \0, 不计算在内)。
    unsigned char flags; // 标志位，主要是识别这是sdshdr几，目前只用了3位，还有5位空余
    char buf[];          // 实际存储字符串的地方 其实就是 C 原生字符串+部分空余空间

};

1
2
3
4
5
6
7
8
9

但是当初始化为空和 SDS_TYPE_5 较为特殊，在源码中会强制转换为 SDS_TYPE_8。
猜想是开发则认为这种情况下，很大可能后续会追加数据。故给一个比较合适的等级。
位于 sds.c

sds sdsnewlen(const void *init, size_t initlen) {
...

    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    
...
}
1
2
3
4
5
6
7

有意思的是对于 Key 和 Value 都很小，只有 Value 会被强转，我理解是 Key 不怎么会更新。故给最小的值即可。

sds sdsnewlen(const void *init, size_t initlen) {
    
...
    s[initlen] = '\0';
    return s;
}
1
2
3
4
5
6

sdsnewlen() 返回的 SDS 指针并不是直接指向 sdshdr 的地址，而是直接指向了 sdshdr 中 buf 的地址。

因为这样可以兼容 C语言原生字符串, buf 其实就是 C 原生字符串 + 部分空余空间，中间是特殊符号’\0’隔开，‘\0’是标识C字符串末尾的符号，这样就实现了和C原生字符串的兼容，部分C字符串的API也就可以直接使。

4.2 扩容操作

若新申请的内存加已使用内存没有超过 SDS_MAX_PREALLOC(1024*1024) 则按 * 2 倍申请。反之按 SDS_MAX_PREALLOC 递增。

// 扩大sds的实际可用空间，以便后续能拼接更多字符串。
// 这里实际不会改变sds的长度，只是增加了更多可用的空间(buf)
sds sdsMakeRoomFor(sds s, size_t addlen) {
...

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);

    // 在未超出SDS_MAX_PREALLOC前，扩容都是按2倍的方式扩容，超出后只能递增
    if (newlen < SDS_MAX_PREALLOC)  // SDS_MAX_PREALLOC = 1024*1024
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
...
    sdssetalloc(s, newlen);
    return s;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

五 总结

String 类型不仅仅只能存储字符串类型数据，所以对于赋予不同的数据类型时候，String 是会区别对待。

1. 当存储的数据是整数类型时候，String 类型会使用 int 编码方式来存储。具体为使用一个 8字节的 Long 类型来实现。
2. 当存储的数据中包含字符串时候，String 类型会使用 SDS 结构体来存储。

结构如下:

struct {
 
 flags;     // 占 8 个字节，标志位，主要是识别这是sdshdr几，目前只用了3位，还有5位空余   
 len  ;     // 占 4 个字节，表示 buf 的已用长度。    
 alloc;     // 占 4 个字节，表示 buf 的实际分配长度，一般大于 len。
 buf ;      // 字节数组，保存实际数据。为了表示字节数组的结束，Redis 会自动在数组最后加一个“\0”，这就会额外占用 1 个字节的开销。

}
1
2
3
4
5
6
7
8

除了记录实际数据，String 类型还需要额外的内存空间记录数据长度、空间使用、最后一次访问的时间、被引用的次数等元数据.。

所以Redis 会用一个 RedisObject 结构体来统一记录这些元数据，同时指向实际数据。

一个 RedisObject 包含了 8 字节的元数据和一个 8 字节指针，这个指针再进一步指向具体数据类型的实际数据所在或者为真实值。

为了节省内存使用，对 Long 和 SDS 做了不同的处理：

1. 当保存的是 Long 类型整数时，RedisObject 中的指针就直接赋值为整数数据了，这样就不用额外的指针再指向整数了，节省了指针的空间开销。
2. 当保存的是字符串数据，并且字符串小于等于 44 字节时，RedisObject 中的元数据、指针和 SDS 是一块连续的内存区域，这样就可以避免内存碎片。这种布局方式也被称为 embstr 编码方式。
   3。 当保存的是字符串数据，并且字符串大于 44 字节时，SDS 的数据量就开始变多了，Redis 就不再把 SDS 和 RedisObject 布局在一起了，而是会给 SDS 分配独立的空间，并用指针指向 SDS 结构。这种布局方式被称为 raw 编码模式。
   总结

SDS 最为 Redis 最常用的数据机构，总结有下面几种原因。

1. 常数复杂度获取字符串长度：O(1)。
2. 避免缓冲区溢出。
3. 减少修改字符串时带来的内存重分配次数。
4. 二进制安全。

SDS 虽好，但是也不能乱用。可以继续看这篇文章：Redis 请慎用 String 类型

六 其他文章

• SDS-简单动态字符串
• Redis - String 类型数据结构（SDS、Int）图文详解
• ziplist-压缩列表
• zipmap-压缩字典
• quicklist-快速列表
• skiplist-跳表
• dict-字典
• intset-整数数组
• redis 通信协议讲解
• listpack-紧凑列表
• Redis7.0 新特性（超详细）
• Redis 请慎用String类型
• Redis 为什么使用单线程？
• Redis AOF日志备份原理
• Redis - ACID分析

​