Redis 数据结构

发表于 更新于 分类于 ， ， 本文字数： 14k 阅读时长 ≈ 12 分钟

Redis 数据结构

关键词：对象、SDS、链表、字典、跳表、整数集合、压缩列表

SDS

SDS 简介

SDS 是 Simple Dynamic String 的缩写，即简单动态字符串。Redis 为 SDS 做了一些优化，以替代 C 字符串来表示字符串内容。此外，SDS 还被 Redis 用作缓冲区（buffer），如：AOF 模块中的 AOF 缓冲区；客户端状态中的输入缓冲区。

SDS 相比 C 字符串，具有以下优势：

C 字符串 SDS
获取字符串长度的复杂度为 O(N) 。 获取字符串长度的复杂度为 O(1) 。
API 是不安全的，可能会造成缓冲区溢出。 API 是安全的，不会造成缓冲区溢出。
修改字符串长度 N 次必然需要执行 N 次内存重分配。 修改字符串长度 N 次最多需要执行 N 次内存重分配。
只能保存文本数据。 可以保存文本或者二进制数据。
可以使用所有 <string.h> 库中的函数。 可以使用一部分 <string.h> 库中的函数。

SDS 实现

每个 sds.h/sdshdr 结构表示一个 SDS 值：

1
2
3
4
5
6
7
8
9
10
11
12
13
struct sdshdr {

    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;

    // 记录 buf 数组中未使用字节的数量
    int free;

    // 字节数组，用于保存字符串
    char buf[];

};

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

SDS 特性

SDS 与 C 字符串相比，做了一些优化，具有以下优势：

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

  • C 字符串 - 因为 C 字符串并不记录自身的长度信息， 所以为了获取一个 C 字符串的长度， 程序必须遍历整个字符串， 对遇到的每个字符进行计数， 直到遇到代表字符串结尾的空字符为止， 这个操作的复杂度为 O(N) 。
  • SDS - 因为 SDS 在 len 属性中记录了 SDS 本身的长度， 所以获取一个 SDS 长度的复杂度仅为 O(1) 。设置和更新 SDS 长度的工作是由 SDS 的 API 在执行时自动完成的， 使用 SDS 无须进行任何手动修改长度的工作。

杜绝缓冲区溢出

  • C 字符串 - C 字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出（buffer overflow）。
  • SDS - 当 SDS API 需要对 SDS 进行修改时， API 会先检查 SDS 的空间是否满足修改所需的要求， 如果不满足的话， API 会自动将 SDS 的空间扩展至执行修改所需的大小， 然后才执行实际的修改操作， 所以使用 SDS 既不需要手动修改 SDS 的空间大小， 也不会出现前面所说的缓冲区溢出问题。

减少修改字符串长度时所需的内存重分配次数

  • C 字符串 - 对于一个包含了 N 个字符的 C 字符串来说， 这个 C 字符串的底层实现总是一个 N+1 个字符长的数组（额外的一个字符空间用于保存空字符）。因为 C 字符串的长度和底层数组的长度之间存在着这种关联性， 所以每次增长或者缩短一个 C 字符串， 程序都总要对保存这个 C 字符串的数组进行一次内存重分配操作。
    • 增长字符串时，如果没有内存重分配，就会产生缓冲区溢出。
    • 缩减字符串是，如果没有内存重分配，就会产生内存泄露。
  • SDS - 因为内存重分配涉及复杂的算法， 并且可能需要执行系统调用， 所以它通常是一个比较耗时的操作。SDS 通过未使用空间解除了字符串长度和底层数组长度之间的关联： 在 SDS 中， buf 数组的长度不一定就是字符数量加一， 数组里面可以包含未使用的字节， 而这些字节的数量就由 SDS 的 free 属性记录。通过未使用空间， SDS 实现了空间预分配和惰性空间释放两种优化策略。
    • 空间预分配 - 空间预分配用于优化 SDS 的字符串增长操作。 当 SDS 的 API 对一个 SDS 进行修改， 并且需要对 SDS 进行空间扩展的时候， 程序不仅会为 SDS 分配修改所必须要的空间， 还会为 SDS 分配额外的未使用空间。通过空间预分配， SDS 将连续增长 N 次字符串所需的内存重分配次数从必定 N 次降低为最多 N 次。
    • 惰性空间 - 惰性空间释放用于优化 SDS 的字符串缩短操作。当 SDS 的 API 需要缩短 SDS 保存的字符串时， 程序并不立即使用内存重分配来回收缩短后多出来的字节， 而是使用 free 属性将这些字节的数量记录起来， 并等待将来使用。通过惰性空间释放策略， SDS 避免了缩短字符串时所需的内存重分配操作， 并为将来可能有的增长操作提供了优化。

二进制安全

  • C 字符串 - C 字符串中的字符必须符合某种编码（比如 ASCII）， 并且除了字符串的末尾之外， 字符串里面不能包含空字符， 否则最先被程序读入的空字符将被误认为是字符串结尾 —— 这些限制使得 C 字符串只能保存文本数据， 而不能保存像图片、音频、视频、压缩文件这样的二进制数据。
  • SDS - SDS 的 API 都是二进制安全的（binary-safe）： 所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据， 程序不会对其中的数据做任何限制、过滤、或者假设 —— 数据在写入时是什么样的， 它被读取时就是什么样。通过使用二进制安全的 SDS ， 使得 Redis 不仅可以保存文本数据， 还可以保存任意格式的二进制数据。

兼容部分 C 字符串函数

虽然 SDS 的 API 都是二进制安全的， 但也会遵循 C 字符串惯例，将保存的数据的末尾设置为空字符， 并且总会在为 buf 数组分配空间时多分配一个字节来容纳这个空字符， 这是为了让那些保存文本数据的 SDS 可以重用一部分 <string.h> 库定义的函数。因此，SDS 可以兼容部分 C 字符串函数。

链表

链表简介

链表被广泛用于实现 Redis 的各种功能，比如 List 键，订阅与发布，慢查询，监视器等。此外，Redis 服务器本身还使用链表来保存多个客户端的状态信息， 以及使用链表来构建客户端输出缓冲区（output buffer）。

由于 C 语言没有内置的链表，因此 Redis 自实现了一个链表：Redis 的链表实现其实就是一个双链表。

  • 每个链表使用一个 list 结构来表示，这个结构带有表头节点指针、表尾节点指针、以及链表长度等信息。
  • 因为链表表头节点的前置节点和表尾节点的后置节点都指向 NULL，所以 Redis 的链表实现是无环链表。
  • 通过为链表设置不同的类型特定函数，Redis 的链表可以用于保存各种不同类型的值。

链表实现

每个链表节点由一个 adlist.h/listNode 结构来表示，每个节点都有一个指向前置节点和后置节点的指针，所以 Redis 的链表实现是双链表。

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct listNode {

    // 前置节点
    struct listNode *prev;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;

} listNode;

多个 listNode 可以通过 prev 和 next 指针组成双链表。

虽然仅仅使用多个 listNode 结构就可以组成链表， 但使用 adlist.h/list 来持有链表的话， 操作起来会更方便：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef struct list {

    // 表头节点
    listNode *head;

    // 表尾节点
    listNode *tail;

    // 链表所包含的节点数量
    unsigned long len;

    // 节点值复制函数
    void *(*dup)(void *ptr);

    // 节点值释放函数
    void (*free)(void *ptr);

    // 节点值对比函数
    int (*match)(void *ptr, void *key);

} list;

list 结构为链表提供了表头指针 head 、表尾指针 tail ， 以及链表长度计数器 len ， 而 dup 、 free 和 match 成员则是用于实现多态链表所需的类型特定函数：

  • dup 函数 - 用于复制链表节点所保存的值；
  • free 函数 - 用于释放链表节点所保存的值；
  • match 函数 - 用于对比链表节点所保存的值和另一个输入值是否相等。

字典

字典简介

字典是一种用于保存键值对（key-value pair）的抽象数据结构。字典中的每个键都是独一无二的， 程序可以在字典中根据键查找与之关联的值， 或者通过键来更新值， 又或者根据键来删除整个键值对， 等等。

由于 C 语言没有内置的链表，因此 Redis 自实现了一个字典。

字典被广泛用于实现 Redis 的各种功能， 其中包括数据库和 Hash 键。

字典实现

Redis 的字典使用哈希表作为底层实现， 一个哈希表里面可以有多个哈希表节点， 而每个哈希表节点就保存了字典中的一个键值对。

Redis 字典所使用的哈希表由 dict.h/dictht 结构定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dictht {

    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;

} dictht;
  • table 属性是一个数组， 数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针， 每个 dictEntry 结构保存着一个键值对。
  • size 属性记录了哈希表的大小， 也即是 table 数组的大小， 而 used 属性则记录了哈希表目前已有节点（键值对）的数量。
  • sizemask 属性的值总是等于 size - 1 ， 这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。

哈希表节点使用 dictEntry 结构表示， 每个 dictEntry 结构都保存着一个键值对：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dictEntry {

    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;
  • key 属性保存着键值对中的键， 而 v 属性则保存着键值对中的值， 其中键值对的值可以是一个指针， 或者是一个 uint64_t 整数， 又或者是一个 int64_t 整数。
  • next 属性是指向另一个哈希表节点的指针， 这个指针可以将多个哈希值相同的键值对连接在一次， 以此来解决键冲突（collision）的问题。

Redis 中的字典由 dict.h/dict 结构表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;

type 属性和 privdata 属性是针对不同类型的键值对， 为创建多态字典而设置的：

  • type 属性是一个指向 dictType 结构的指针， 每个 dictType 结构保存了一簇用于操作特定类型键值对的函数， Redis 会为用途不同的字典设置不同的类型特定函数。
  • 而 privdata 属性则保存了需要传给那些类型特定函数的可选参数。
  • ht 属性是一个包含两个项的数组， 数组中的每个项都是一个 dictht 哈希表， 一般情况下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。
  • rehashidx 属性记录了 rehash 目前的进度， 如果目前没有在进行 rehash ， 那么它的值为 -1 。

哈希算法

当字典被用作数据库的底层实现， 或者哈希键的底层实现时， Redis 使用 MurmurHash2 算法来计算键的哈希值。

Redis 计算哈希值和索引值的方法如下：

1
2
3
4
5
6
# 使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);

# 使用哈希表的 sizemask 属性和哈希值，计算出索引值
# 根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

哈希冲突

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时， 我们称这些键发生了冲突（collision）。

Redis 使用链地址法（separate chaining）来解决哈希冲突： 每个哈希表节点都有一个 next 指针， 多个哈希表节点可以用 next 指针构成一个单向链表， 被分配到同一个索引上的多个节点可以用这个单向链表连接起来， 这就解决了键冲突的问题。

rehash

rehash 的步骤

  1. 为字典的 ht[1] 哈希表分配空间， 这个哈希表的空间大小取决于要执行的操作， 以及 ht[0] 当前包含的键值对数量 （也即是 ht[0].used 属性的值）。
  2. 将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面： rehash 指的是重新计算键的哈希值和索引值， 然后将键值对放置到 ht[1] 哈希表的指定位置上。
  3. 当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后 （ht[0] 变为空表）， 释放 ht[0] ， 将 ht[1] 设置为 ht[0] ， 并在 ht[1] 新创建一个空白哈希表， 为下一次 rehash 做准备。

rehash 的条件

当以下条件中的任意一个被满足时， 程序会自动开始对哈希表执行扩展操作：

  1. 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 1 ；
  2. 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 5 ；

其中哈希表的负载因子可以通过公式计算得出：

1
2
# 负载因子 = 哈希表已保存节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size

渐进式 rehash

渐进式 rehash 的详细步骤：

  1. 为 ht[1] 分配空间， 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
  2. 在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始。
  3. 在 rehash 进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一。
  4. 随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。

跳表

跳表简介

跳表（skiplist）是一种有序数据结构， 它通过在每个节点中维持多个指向其他节点的指针， 从而达到快速访问节点的目的。

跳表支持平均 O(log N) 最坏 O(N) 复杂度的节点查找， 还可以通过顺序性操作来批量处理节点。

在大部分情况下， 跳表的效率可以和平衡树相媲美， 并且因为跳表的实现比平衡树要来得更为简单， 所以有不少程序都使用跳表来代替平衡树。

Redis 使用跳表作为有序集合键的底层实现之一： 如果一个有序集合包含的元素数量比较多， 又或者有序集合中元素的成员（member）是比较长的字符串时， Redis 就会使用跳表来作为有序集合键的底层实现。

此外，Redis 还在集群节点中用跳表作为内部数据结构。

跳表实现

Redis 的跳表实现由 zskiplist 和 zskiplistNode 两个结构组成， 其中 zskiplist 用于保存跳表信息（比如表头节点、表尾节点、长度）， 而 zskiplistNode 则用于表示跳表节点。

zskiplist 结构的定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct zskiplist {

    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;

    // 表中层数最大的节点的层数
    int level;

} zskiplist;
  • header 和 tail 指针分别指向跳表的表头和表尾节点， 通过这两个指针， 程序定位表头节点和表尾节点的复杂度为 O(1) 。
  • 通过使用 length 属性来记录节点的数量， 程序可以在 O(1) 复杂度内返回跳表的长度。
  • level 属性则用于在 O(1) 复杂度内获取跳表中层高最大的那个节点的层数量， 注意表头节点的层高并不计算在内。每个跳表节点的层高都是 1 至 32 之间的随机数。

跳表节点的实现由 redis.h/zskiplistNode 结构定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef struct zskiplistNode {

    // 后退指针
    struct zskiplistNode *backward;

    // 分值
    double score;

    // 成员对象
    robj *obj;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;
  • 层（level）：每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。在上面的图片中，连线上带有数字的箭头就代表前进指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行。
  • 后退（backward）指针：它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
  • 分值（score）：在跳表中，节点按各自所保存的分值从小到大排列。在同一个跳表中， 多个节点可以包含相同的分值， 但每个节点的成员对象必须是唯一的。跳表中的节点按照分值大小进行排序， 当分值相同时， 节点按照成员对象的大小进行排序。
  • 成员对象（obj）：各个节点中的 o1 、 o2 和 o3 是节点所保存的成员对象。

整数集合

整数集合简介

整数集合（intset）是集合键的底层实现之一。当一个集合只包含整数值元素， 并且这个集合的元素数量不多时， Redis 就会使用整数集合作为集合键的底层实现。

整数集合的底层实现为数组， 这个数组以有序、无重复的方式保存集合元素， 在有需要时， 程序会根据新添加元素的类型， 改变这个数组的类型。

升级操作为整数集合带来了操作上的灵活性， 并且尽可能地节约了内存。

整数集合只支持升级操作， 不支持降级操作。

整数集合实现

整数集合是 Redis 用于保存整数值的集合抽象数据结构， 它可以保存类型为 int16_t 、 int32_t 或者 int64_t 的整数值， 并且保证集合中不会出现重复元素。

每个 intset.h/intset 结构表示一个整数集合：

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct intset {

    // 编码方式
    uint32_t encoding;

    // 集合包含的元素数量
    uint32_t length;

    // 保存元素的数组
    int8_t contents[];

} intset;
  • contents 数组是整数集合的底层实现： 整数集合的每个元素都是 contents 数组的一个数组项（item）， 各个项在数组中按值的大小从小到大有序地排列， 并且数组中不包含任何重复项。
  • length 属性记录了整数集合包含的元素数量， 也即是 contents 数组的长度。
  • 虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组， 但实际上 contents 数组并不保存任何 int8_t 类型的值 —— contents 数组的真正类型取决于 encoding 属性的值：
    • 如果 encoding 属性的值为 INTSET_ENC_INT16 ， 那么 contents 就是一个 int16_t 类型的数组， 数组里的每个项都是一个 int16_t 类型的整数值 （最小值为 -32,768 ，最大值为 32,767 ）。
    • 如果 encoding 属性的值为 INTSET_ENC_INT32 ， 那么 contents 就是一个 int32_t 类型的数组， 数组里的每个项都是一个 int32_t 类型的整数值 （最小值为 -2,147,483,648 ，最大值为 2,147,483,647 ）。
    • 如果 encoding 属性的值为 INTSET_ENC_INT64 ， 那么 contents 就是一个 int64_t 类型的数组， 数组里的每个项都是一个 int64_t 类型的整数值 （最小值为 -9,223,372,036,854,775,808 ，最大值为 9,223,372,036,854,775,807 ）。

整数集合升级

每当我们要将一个新元素添加到整数集合里面， 并且新元素的类型比整数集合现有所有元素的类型都要长时， 整数集合需要先进行升级（upgrade）， 然后才能将新元素添加到整数集合里面。

升级整数集合并添加新元素共分为三步进行：

  1. 根据新元素的类型， 扩展整数集合底层数组的空间大小， 并为新元素分配空间。
  2. 将底层数组现有的所有元素都转换成与新元素相同的类型， 并将类型转换后的元素放置到正确的位上， 而且在放置元素的过程中， 需要继续维持底层数组的有序性质不变。
  3. 将新元素添加到底层数组里面。

因为每次向整数集合添加新元素都可能会引起升级， 而每次升级都需要对底层数组中已有的所有元素进行类型转换， 所以向整数集合添加新元素的时间复杂度为 O(N) 。

压缩列表

压缩列表简介

压缩列表是一种为节约内存而开发的顺序型数据结构。

压缩列表（ziplist）被用作列表键和哈希键的底层实现之一。

  • 当一个列表键只包含少量列表项， 并且每个列表项要么就是小整数值， 要么就是长度比较短的字符串， 那么 Redis 就会使用压缩列表来做列表键的底层实现。
  • 当一个哈希键只包含少量键值对， 并且每个键值对的键和值要么就是小整数值， 要么就是长度比较短的字符串， 那么 Redis 就会使用压缩列表来做哈希键的底层实现。

压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。

添加新节点到压缩列表， 或者从压缩列表中删除节点， 可能会引发连锁更新操作， 但这种操作出现的几率并不高。

压缩列表实现

压缩列表各个组成部分的详细说明

属性 类型 长度 用途
zlbytes uint32_t 4 字节 记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配， 或者计算 zlend 的位置时使用。
zltail uint32_t 4 字节 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节： 通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。
zllen uint16_t 2 字节 记录了压缩列表包含的节点数量： 当这个属性的值小于 UINT16_MAX （65535）时， 这个属性的值就是压缩列表包含节点的数量； 当这个值等于 UINT16_MAX 时， 节点的真实数量需要遍历整个压缩列表才能计算得出。
entryX 列表节点 不定 压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
zlend uint8_t 1 字节 特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。

对象

Redis 并没有直接使用这些数据结构来实现键值对数据库， 而是基于这些数据结构创建了一个对象系统， 这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象， 每种对象都用到了至少一种我们前面所介绍的数据结构。

对象简介

Redis 数据库中的每个键值对的键和值都是一个对象。

Redis 共有字符串、列表、哈希、集合、有序集合五种类型的对象， 每种类型的对象至少都有两种或以上的编码方式， 不同的编码可以在不同的使用场景上优化对象的使用效率。

服务器在执行某些命令之前， 会先检查给定键的类型能否执行指定的命令， 而检查一个键的类型就是检查键的值对象的类型。

基于引用计数技术的内存回收机制 - Redis 的对象系统带有引用计数实现的内存回收机制， 当一个对象不再被使用时， 该对象所占用的内存就会被自动释放。

基于引用计数技术的对象共享机制 - Redis 会共享值为 0 到 9999 的字符串对象。

计算数据库键的空转时长 - 对象会记录自己的最后一次被访问的时间， 这个时间可以用于计算对象的空转时间。

对象的类型

Redis 使用对象来表示数据库中的键和值。每次当我们在 Redis 的数据库中新创建一个键值对时， 我们至少会创建两个对象， 一个对象用作键值对的键（键对象）， 另一个对象用作键值对的值（值对象）。

Redis 中的每个对象都由一个 redisObject 结构表示， 该结构中和保存数据有关的三个属性分别是 type 属性、 encoding 属性和 ptr 属性：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct redisObject {

    // 类型
    unsigned type:4;

    // 编码
    unsigned encoding:4;

    // 指向底层实现数据结构的指针
    void *ptr;

    // ...

} robj;

对象的 type 属性记录了对象的类型，有以下类型：

对象 对象 type 属性的值 TYPE 命令的输出
字符串对象 REDIS_STRING "string"
列表对象 REDIS_LIST "list"
哈希对象 REDIS_HASH "hash"
集合对象 REDIS_SET "set"
有序集合对象 REDIS_ZSET "zset"

Redis 数据库保存的键值对来说， 键总是一个字符串对象， 而值则可以是字符串对象、列表对象、哈希对象、集合对象或者有序集合对象的其中一种。

【示例】通过 TYPE 命令查看数据库键的值对象的类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 键为字符串对象，值为字符串对象
> SET msg "hello world"
OK
> TYPE msg
string

# 键为字符串对象，值为列表对象
> RPUSH numbers 1 3 5
(integer) 6
> TYPE numbers
list

# 键为字符串对象，值为哈希对象
> HMSET profile name Tome age 25 career Programmer
OK
> TYPE profile
hash

# 键为字符串对象，值为集合对象
> SADD fruits apple banana cherry
(integer) 3
> TYPE fruits
set

# 键为字符串对象，值为有序集合对象
> ZADD price 8.5 apple 5.0 banana 6.0 cherry
(integer) 3
> TYPE price
zset

对象的编码

对象的 ptr 指针指向对象的底层实现数据结构， 而这些数据结构由对象的 encoding 属性决定。

encoding 属性记录了对象所使用的编码， 也即是说这个对象使用了什么数据结构作为对象的底层实现。

Redis 中每种类型的对象都至少使用了两种不同的编码，不同的编码可以在不同的使用场景上优化对象的使用效率。

Redis 支持的编码如下所示：

类型 编码 对象 OBJECT ENCODING 命令输出
REDIS_STRING REDIS_ENCODING_INT 使用整数值实现的字符串对象。 “int”
REDIS_STRING REDIS_ENCODING_EMBSTR 使用 embstr 编码的简单动态字符串实现的字符串对象。 “embstr”
REDIS_STRING REDIS_ENCODING_RAW 使用简单动态字符串实现的字符串对象。 “raw”
REDIS_LIST REDIS_ENCODING_ZIPLIST 使用压缩列表实现的列表对象。 “ziplist”
REDIS_LIST REDIS_ENCODING_LINKEDLIST 使用双端链表实现的列表对象。 “linkedlist”
REDIS_HASH REDIS_ENCODING_ZIPLIST 使用压缩列表实现的哈希对象。 “ziplist”
REDIS_HASH REDIS_ENCODING_HT 使用字典实现的哈希对象。 “hashtable”
REDIS_SET REDIS_ENCODING_INTSET 使用整数集合实现的集合对象。 “intset”
REDIS_SET REDIS_ENCODING_HT 使用字典实现的集合对象。 “hashtable”
REDIS_ZSET REDIS_ENCODING_ZIPLIST 使用压缩列表实现的有序集合对象。 “ziplist”
REDIS_ZSET REDIS_ENCODING_SKIPLIST 使用跳表和字典实现的有序集合对象。 “skiplist”

【示例】使用 OBJECT ENCODING 命令可以查看数据库键的值对象的编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
> SET msg "hello wrold"
OK
> OBJECT ENCODING msg
"embstr"

> SET story "long long long long long long ago ..."
OK
> OBJECT ENCODING story
"raw"

> SADD numbers 1 3 5
(integer) 3
> OBJECT ENCODING numbers
"intset"

> SADD numbers "seven"
(integer) 1
> OBJECT ENCODING numbers
"hashtable"

类型检查与命令多态

Redis 中用于操作键的命令基本上可以分为两种类型。

  • 多态命令 - 可以对任何类型的键执行。如 DEL、 EXPIRE 、 RENAME 、 TYPE 、 OBJECT 等命令。
  • 特定类型命令
    • SET 、 GET 、 APPEND 、 STRLEN 等命令只能对字符串键执行；
    • HDEL 、 HSET 、 HGET 、 HLEN 等命令只能对哈希键执行；
    • RPUSH 、 LPOP 、 LINSERT 、 LLEN 等命令只能对列表键执行；
    • SADD 、 SPOP 、 SINTER 、 SCARD 等命令只能对集合键执行；
    • ZADD 、 ZCARD 、 ZRANK 、 ZSCORE 等命令只能对有序集合键执行；

为了确保只有指定类型的键可以执行某些特定的命令，Redis 在执行一个类型特定的命令之前， Redis 会先检查输入键的类型是否正确， 然后再决定是否执行给定的命令。类型特定命令所进行的类型检查是通过 redisObject 结构的 type 属性来实现的：

  • 在执行一个类型特定命令之前， 服务器会先检查输入数据库键的值对象是否为执行命令所需的类型， 如果是的话， 服务器就对键执行指定的命令；
  • 否则， 服务器将拒绝执行命令， 并向客户端返回一个类型错误。

Redis 除了会根据值对象的类型来判断键是否能够执行指定命令之外， 还会根据值对象的编码方式， 选择正确的命令实现代码来执行命令。

内存回收

由于 C 语言不支持内存回收，Redis 内部实现了一套基于引用计数的内存回收机制。

每个对象的引用计数信息由 redisObject 结构的 refcount 属性记录：

1
2
3
4
5
6
7
8
9
10
typedef struct redisObject {

    // ...

    // 引用计数
    int refcount;

    // ...

} robj;

对象的引用计数信息会随着对象的使用状态而不断变化：

  • 在创建一个新对象时， 引用计数的值会被初始化为 1 ；
  • 当对象被一个新程序使用时， 它的引用计数值会被增一；
  • 当对象不再被一个程序使用时， 它的引用计数值会被减一；
  • 当对象的引用计数值变为 0 时， 对象所占用的内存会被释放。

对象共享

在 Redis 中， 让多个键共享同一个值对象需要执行以下两个步骤：

  1. 将数据库键的值指针指向一个现有的值对象；
  2. 将被共享的值对象的引用计数增一。

共享对象机制对于节约内存非常有帮助， 数据库中保存的相同值对象越多， 对象共享机制就能节约越多的内存。

Redis 会在初始化服务器时， 共享值为 0 到 9999 的字符串对象。

对象的空转时长

redisObject 的 lru 属性记录了对象最后一次被命令程序访问的时间：

1
2
3
4
5
6
7
8
9
typedef struct redisObject {

    // ...

    unsigned lru:22;

    // ...

} robj;

OBJECT IDLETIME 命令可以打印出给定键的空转时长， 这一空转时长就是通过将当前时间减去键的值对象的 lru 时间计算得出的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
> SET msg "hello world"
OK

# 等待一小段时间
> OBJECT IDLETIME msg
(integer) 20

# 等待一阵子
> OBJECT IDLETIME msg
(integer) 180

# 访问 msg 键的值
> GET msg
"hello world"

# 键处于活跃状态，空转时长为 0
> OBJECT IDLETIME msg
(integer) 0

注意

OBJECT IDLETIME 命令的实现是特殊的， 这个命令在访问键的值对象时， 不会修改值对象的 lru 属性。

除了可以被 OBJECT IDLETIME 命令打印出来之外， 键的空转时长还有另外一项作用： 如果服务器打开了 maxmemory 选项， 并且服务器用于回收内存的算法为 volatile-lru 或者 allkeys-lru ， 那么当服务器占用的内存数超过了 maxmemory 选项所设置的上限值时， 空转时长较高的那部分键会优先被服务器释放， 从而回收内存。

参考资料