Redis String 的三种编码

发布日期: 2021-11-19

更新日期: 2024-10-10

文章字数: 4.2k

阅读时长: 15 分

阅读次数:

1 概述

在 Redis 5.x 版本 中, String (OBJ_STRING) 数据类型的编码 (encoding) 中有 3 种:

int (OBJ_ENCODING_INT): 存储 8 个字节的长整型 (long, 2^64 - 1)

embstr (OBJ_ENCODING_EMBSTR): 存储小于 44 个字节的字符串

raw (OBJ_ENCODING_RAW): 存储大于 44 个字节的字符串 (3.2 版本之前是 39 字节)

向 Redis 存入一个 String 类型的值时, Redis 可以根据存储的内容和长度, 自动的在上面 3 种编码中选择其中一个, 用来组织存储的数据。
整数优先考虑用 int 处理, int 无法处理的情况, 再从 embstr 和 raw 中选择一个。

embstr 和 raw 虽说是 2 者不同的编码, 但是 2 者在内部的实现都是一个字符串。
基于 char[] 封装的一组结构体 (类比 Java 的 Class), 官方统一叫做 sds (类比 Java 的 String)。

注: 下面的分析也是按照 Redis 5.x 进行分析。

2 Sds

在了解 Redis String 的 3 种编码之前, 需要先了解一下 Redis 中的 sds。

2.1 char[] 实现字符串的问题

在 Java 中, 如果不借助 String, 实现存储一段字符如何实现比较好呢？

进到 String 的源码, 可以发现 String 本身是对 char[] 的封装, 所以可以直接使用 char[] 来存储一段字符, 达到存储字符串的效果

Alt 'Java char 实现字符串'

我们知道 Redis 是用 C 语言编写的, C 语言本身像 Java 一样提供类似 String 的封装类。
所以要实现字符串的效果需要借助 char[] 数组的, 而直接使用 char[] 时, 在使用时有一些问题:

字符串长度变化, char[] 数组就需要重新分配内存

获取字符串长度时, 需要遍历数组, 或者通过内存进行计算等, C 语言的数组没有提供 len 属性或者 len() 方法直接获取长度

C 语言中的数组不记录自身长度和空闲空间, 在使用上容易造成数组越界等问题

C 语言中的 char[] 数组是二进制不安全的. 通过 char[] 实现字符串时, 内部会通过 “\0” 代表字符串的结束, 也就是数组的结束的位置追加一个 “\0” 以表示字符串的结束。

比如存储 “one” 3 个字符, 却需要 4 个字符进行存储, 实际的存储情况为 “one\0”。这个特点在存储其他的格式的内存, 如二进制表示的音频图片等, 可能会出现问题, 比如本身的内容上就包含一个 \0, 但是 C 语言读到这个位置, 认为结束了, 后面的内容被舍弃了, 这就是二进制不安全。

Alt 'C 语言 char 实现数组特点'

2.2 低版本 Redis 中的 sds

因为 C 语言中 char[] 实现字符串的存在着问题。
所以, Redis 内部自定义了一个 sds (Simple Dynamic String) 的结构体, 来代替 char[], 实现字符串。
达到的效果很像 Java 中的 ArrayList, 采用预分配冗余空间和惰性空间释放的方式来减少内存的频繁分配, 同时在达到内存的上限时, 自动扩容等。

sds 的定义如下

struct sds {

    /** buf 中已经使用的字节 */
    int len; 

    /** buf 中剩余多少字节 */
    int free;

    /** 存储数据的数组 */
    char buf[];
}

这个就是 3.2 版本之前 Redis 对字符串的实现。本质还是一个 char[] 数组, 但是多了 2 个字段 len 和 free。

有长度统计变量 len 的存在, 读写字符串时不依赖 \0 终止符, 保证了二进制安全和长度的获取的便利 (读取内容直接从数组的开始位置读取对应长度的内存数据)

借助 len 和 free 可以做到空间预分配和惰性空间释放, 同时更安全的使用数组

buf[] 是一个柔性数组, 在内存中查找性能影响不大 (柔性数组的地址和结构体是连续的, 这样查找内存更快, 因为不需要额外通过指针找到字符串的位置)

上面的实现是否是最好的实现呢? Redis 是一款基于内存的数据库, 那么内存是极其重要的, 结合平时使用字符串的长度和内存的使用上考虑有什么问题吗?

2.3 Redis 3.2 之后的 sds

在 3.2 版本之前 sds 的 len / free, 用的是 int 修饰的, 最大值为 2147483647, 正常情况下字符串的长度会超过这个吗？
应该不会, 那么是否可以用 2 个字节的 uint16_t (Java 层面的 short, 最大值为 32768) 进行存储呢?

一直往下推导下去
1 个字节的 uint8_t (Java 层面的 byte, 最大值为 127) 是否也可以呢?
一个字节 8 位, 乃至用位级别的大小呢?

所以在 Redis 3.2 后, 对 sds 更进一步的细化, 分成了 5 种实现, 基于 5bit, 8bit (1 个字节), 16bit (2 个字节), 32bit (4 个字节), 64bit (8 个字节) 的实现,
同时在结构体内追加了一个 1 个字节的 flags 表示这个结构体的类型。

struct __attribute__ ((__packed__)) sdshdr5 {

    // flags 1个字节, 8 位,  低位的 3 位表示 sds 的类型, 剩下的 5 位表示下面 char[] 的内容长度
    unsigned char flags; 

    // 具体的内容
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr8 {

    // char[] 已使用的长度
    uint8_t len;

    // 总长度, 不包含最后追加的 \0 结束符
    uint8_t alloc;

    // 低位的 3 位表示 sds 类型, 剩余 5 位没有使用, 表示当前字符数组的属性, 用来标识到底是 sdshdr8 还是 sdshdr16 等
    unsigned char flags;
    
    // 具体的内容
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; 
    uint16_t alloc; 
    unsigned char flags;
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len;
    uint32_t alloc;
    unsigned char flags;
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len;
    uint64_t alloc;
    unsigned char flags;
    char buf[];
};

len/ alloc / buf, 三个属性都和一开始简单版的 sds 用法类似的。只是在结构体内追加多了一个 flags 的属性。
这个 flag 是一个 8 位, 1 个字节的 char, 而在实际中, 现在只使用到了低位的 3 位, 剩余 5 位暂时没有使用到。

flag 的取值如下

// flag 的值 0 ~ 4
#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

备注: sds5 基本不用用到, 实际上在使用上时, 即使字符串的长度很小, 满足 sds5 的情况下, 也会被转换为 sds8 进行存储。这个情况满足大部分的情况,
但是在某些情况下, Redis 内部 key 还是可以用 sds5 进行存储的。
想要了解的可以看一下这篇文章

思考一下, 这个 flags (代表当前 sds 是具体什么类型的) , 是否有存在的意义呢?

实际是有用的。
在面向对象的编程语言中, 默认 sds 这个对象代表字符串 (如 Java 中, 声明了一个 String, 都会任务 String, 代表了我们存储的字符串, 而不是 String 中的 value)。

而在 Redis 中, 初始的是 sds 这个结构体中所有属性的值, 而实际在使用时, 还是 char[], 这样可以兼容很多系统的函数等。
需要时, 通过 buf[-1] (在 C 语言中, 数组变量就是内存地址, 所有索引值可以为 - 1, 逆推到前面的地址, 而上面的几个结构体的定义中 char[] 前面就是 flags) 就能获取到 flags 这个属性, 得到了 flags, 很容易逆推出len 和 alloc 的属性。

上文说过了, C 语言中是没有自己的字符串类型的, sds 是 Redis 自己封装的, 所以很多系统的函数, 比如 strlen, strcpy 等, 入参都是 char[], 而不是 sds。
所以 Redis 创建字符串时, 是用 sds 进行创建的。但是在使用时, 依旧是用 char[], 这样就可以兼容很多系统的函数等。
读取内容时, 再根据 C 语言的内存操作, 获取到结构体内其他值, 再进行其他操作。

为了实现这个效果, 上面的结构体都通过了 attribute((packed)) 就行修饰了, 强制结构体中所有的变量按照 1 个字节进行对齐 (结构体会按其所有变量大小的最小公倍数做字节对齐),
避免了系统的内存对齐, 影响到了 buf[-1] 获取不到真正的 flags 值, 同时间接的达到了节省内存的效果。

所以, 在 Redis 中通过 sds 来实现字符串的效果。

sds 不用担心内存溢出问题, 如果需要会对 sds 进行自动扩容。

通过 空间预分配 和 惰性空间释放, 防止多次重分配内存。

sds 中存储了 len 变量, 存储当前字符串的长度, 那么可以直接通过 len 获取到字符串的长度, 变为了 O(1)

字符串的结束可以完全通过 len 进行判断, 而忽略 C 语言中的遇 \0 结束的特点。

综上: sds 具备了可动态扩展内存, 二进制安全, 快速遍历字符串和与传统的 C 语言字符串类型兼容的特点。

注: sds 的扩容规则

sds 长度修改后小于 1M, 则 alloc = len * 2, 以原本的大小的两倍进行扩容

sds 长度修改后大于 1M, 则 alloc += 1M, 以 1M 的大小进行扩容

3 embstr 和 raw 编码

上面普遍了那么久的字符串, 实际都是在介绍 embstr 和 raw。因为 2 者本身都是一个 sds, 唯一的区别就是在内存分配不同！

当我们向 Redis 存入一个 String 的数据, Redis 需要为我们存储一个 key 和 value。
key 没必要说, 这时就是一个 sds, 而 value 是一个 String, 那么也同样是一个 sds。

但是因为 Redis 中 value 涉及到涉及到引用次数, 回收策略等配置, 所以官方对所有的编码外面多包装了一层 redisObject。

typedef struct redisObject {
    
    /** 4 位, 数据类型: OBJ_STRING, OBJ_LIST, OBJ_HASH, OBJ_SET, OBJ_ZSET 等*/
    unsigned type:4;

    /** 4 位, 底层存储的数据结构编码: raw, int embstr 等 */
    unsigned encoding:4;

    /** 24 位, 对象最后一次被命令程序访问的时间或者访问的次数, 与内存回收有关 */
    unsigned lru:LRU_BITS;

    /** 4 个字节 被引用的次数, 当 refcount 为 0 的时候, 表示该对象已经不被任何对象引用, 则可以进行垃圾回收了 */
    int refcount;

    /** 指针对象的大小和操作系统的位数有关, 64 位系统, 8 个节点 */
    /** 指向对象实际的数据结构, 也就是真正的值, 比如 sds8, sds16 等 */
    void *ptr;

} robj;

这样, Redis 在创建一个 String 类型的 value, 需要分配内存有 2 个, redisObject 本身 + 存储内容的 sds。
分配 redisObject 自身需要 (4 + 4 + 24)bit + 4 字节 + 8 字节 = 16 个字节
分配一个最少内存的 sds, 也就是 sds8 需要 1 (uint8_t len) + 1 (uint8_t alloc) + 1 (unsigned char) + 1 (别忘了, char[] 系统会在后面自动填充一个 \0) = 4 个字节 (sds5 会被转换为 sds8 进行分配)
这样创建一个不包含任何内容的 String 类型的 value, 需要 16 字节的 redisObject + 4 字节的 sds8 = 20 字节的内存。

在 C 语言中常用的内存分配器为 jemalloc、tcmalloc
这 2 个的共同特点就是在进行内容分配时, 都是按照 2 的 n 次方进行分配的, 既 2, 4, 8 的方式进行分配。

所以在为一个不包含任何内容的 String 类型的 value (20 个字节) 进行内存分配时, 需要分配 32 个字节, 多分配了 12 个字节。

上面讨论的是 sds8 的 char[] buf 为空的情况, 实际中, sds8 是一定会有内容的, 如果这时, 这些内容的大小在 12 个字节以内,
那么我们创建一个 String 类型的 value, 只用到了一次内存分配就完成了。

在 Redis 中, 认为一次分配的内存大于 64 字节, 是一个得不偿失的行为, 大内存的申请消耗的时间更长等。
超过 64 字节的内存分配, 会多次进行。

到这里, 可以得到 embstr 和 raw 的区别了。

embstr: redisObject + sds, 内存是一起分配的, 只需要一次内存分配, 同时内存是相连在一起。

raw : redisObject + sds 是分开分配的, 需要 2 次内存分配以上, 内存也不一定相连在一起。

Alt 'embstr 和 raw 的内存分配'

同时这里也可以看到, embstr 和 raw 的分界线为什么是 44 字节?
分配一个不含任何内容的 redisObject + sds 需要 20 字节, 最大一次分配 64 字节, 64 - 20 = 44 字节, 所以在 Redis 中创建一个 String 对象

String 的内容长度小于等于 44 字节, 编码为 embstr
String 的内容长度大于 44 字节, 编码为 raw

4 int 编码

String 的另一个编码 int, 很简单,
因为存储的是整数, 完全可以不用 char[] 存储, 直接用一个整数进行存储即可了, 所以在 Redis 中 int 编码就是一个整数数据类型, 没了。

唯一要说的话, Redis 有一个整数的缓存池, 和 Java 中 Long 的数据缓存一样。会预先初始一定的数据, 同时缓存起来。

在 Redis 没有设置最大内存值或者内存过期方式不是为 MAXMEMORY_FLAG_NO_SHARED_INTEGERS (lru/lfu 策略) 的前提下,
value 为 0 - 9999, 直接使用缓存的数据, 而不是创建对象。

大体的流程如下：

robj *createStringObjectFromLongLongWithOptions(long long value, int valueobj) {

    robj *o;

    if (server.maxmemory == 0 || !(server.maxmemory_policy & MAXMEMORY_FLAG_NO_SHARED_INTEGERS)) {
        valueobj = 0;
    }

    if (value >= 0 && value < OBJ_SHARED_INTEGERS && valueobj == 0) {
        incrRefCount(shared.integers[value]);
        // 直接使用缓存的数据, 而不是创建对象
        o = shared.integers[value];
    } else {
        // 创建对象

        // LONG_MIN <  value < LONG_MAX, 创建 int 编码的对象
        if (value >= LONG_MIN && value <= LONG_MAX) {
            // 创建对象
            o = createObject(OBJ_STRING, NULL);
            o->encoding = OBJ_ENCODING_INT;
            o->ptr = (void*)((long)value);
        } else {
            // 超出范围, 用字符串处理
            o = createObject(OBJ_STRING,sdsfromlonglong(value));
        }
    }
    return o;
}

5 问题

5.1 int 和 embstr 什么时候转化为 raw

当 int 数据不再是整数或大小超过了 long 的范围 (2^63-1 = 9223372036854775807) 时, 自动转化为 embstr。
在 Redis 中, embstr 是被设置为只读的, 当对 embstr 字符串进行修改 (例如: append), 无论 embstr 是否超过了 44 个字节, 都会变为 raw

5.2 embstr 和 raw 的区别

embstr 的使用只分配一次内存空间 (因为 redisObject 和 sds 是连续的), 而 raw 需要分配多次内存空间 (分别为 redisObject 和 sds 的空间不是连续的)。
因此, 与 raw 相比, embstr 的好处在于创建时只分配一次空间, 删除时只释放一次空间, 以及对象的所有数据连在一起, 寻找方便。
而 embstr 的坏处也很明显, 如果字符串的长度增加需要重新分配内存时, 整个 redisObject 和 sds 都需要重新分配空间, 因此 Redis 中的 embstr 实现为只读。

5.3 当长度小于阈值时, 会还原吗

Redis 内部编码的转换, 都符合以下规律: 编码转换在 Redis 写入数据时完成, 且转换过程不可逆, 只能从小内存编码向大内存编码转换。但是可以通过重新 set, 可以重新分配。

5.4 为什么要对底层的数据结构进行一层包装呢

通过封装, 可以根据对象的类型动态地选择存储结构和可以使用的命令, 实现节省空间和优化查询速度

6 String 的使用场景

热点数据缓存 (报表, 促销库存等), 可以提升热点数据的访问速度

Redis 是分布式的独立服务, 可以在多个应用之间共享, 可以用于分布式 Session

同样因为 Redis 的分布式的独立服务, 可以通过 setnx, 实现分布式锁

利用其原子性, 通过 incr 实现全局 Id 和计数器(文章阅读量, 点赞等)

限流, 同样可以通过 incr, 以访问者的 IP 和其他信息作为 key, 访问一次增加一次计数, 超过次数则返回 false

Redis 支持位运算, 因为 bit 非常节省空间 (1 MB = 8388608 bit), 可以用来做大数据量的统计, 如: 在线用户统计, 用户签到情况等

利用其自动过期的功能, 做有限时操作, 比如验证码