Redis底层原理--03. Redis 数据类型

Redis底层原理--03. Redis 数据类型

1. 对象处理机制

由于 redis 需要对每一个 key 产生不同的操作,所以Redis 必须让每个键都带有类型信息,使得程序可以检查键的类型,并为它选择合适的处理方式

为了解决以上问题, Redis 构建了自己的类型系统,这个系统的主要功能包括:

  • redisObject 对象。基于 redisObject 对象的类型检查。
  • 基于 redisObject 对象的显式多态函数。
  • 对 redisObject 进行分配、共享和销毁的机制。

1.2 redisObject 数据结构,以及 Redis 的数据类型

redisObject 的定义位于 redis.h :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
* Redis 对象
*/
typedef struct redisObject {
// 类型
unsigned type:4;
// 对齐位
unsigned notused:2;
// 编码方式
unsigned encoding:4;
// LRU 时间(相对于 server.lruclock)
unsigned lru:22;
// 引用计数
int refcount;
// 指向对象的值
void *ptr;
} robj;

type 、 encoding 和 ptr 是最重要的三个属性。
type 记录了对象所保存的值的类型,它的值可能是以下常量的其中一个(定义位于 redis.h):

1
2
3
4
5
6
7
/*对象类型 type*/
#define REDIS_STRING 0 // 字符串
#define REDIS_LIST 1 // 列表
#define REDIS_SET 2 // 集合
#define REDIS_ZSET 3 // 有序集
#define REDIS_HASH 4 // 哈希表

1
2
3
4
5
6
7
8
9
10
11
/*
对象编码
*/
#define REDIS_ENCODING_RAW 0 // 编码为字符串
#define REDIS_ENCODING_INT 1 // 编码为整数
#define REDIS_ENCODING_HT 2 // 编码为哈希表
#define REDIS_ENCODING_ZIPMAP 3 // 编码为 zipmap
#define REDIS_ENCODING_LINKEDLIST 4 // 编码为双端链表
#define REDIS_ENCODING_ZIPLIST 5 // 编码为压缩列表
#define REDIS_ENCODING_INTSET 6 // 编码为整数集合
#define REDIS_ENCODING_SKIPLIST 7 // 编码为跳跃表

ptr 是一个指针,指向实际保存值的数据结构,这个数据结构由 type 属性和 encoding 属性决定。

举个例子,如果一个 redisObject 的 type 属性为 REDIS_LIST , encoding 属性为 REDIS_ENCODING_LINKEDLIST ,那么这个对象就是一个 Redis 列表,它的值保存在一个双端链表内,而 ptr 指针就指向这个双端链表;

另一方面,如果一个 redisObject 的 type 属性为 REDIS_HASH , encoding 属性为 REDIS_ENCODING_ZIPMAP ,那么这个对象就是一个 Redis 哈希表,它的值保存在一个 zipmap 里,而 ptr 指针就指向这个 zipmap .

对应关系:

redis 数据类型

1.2 命令的类型检查和多态

一个 Key 的执行过程:

  1. 根据给定 key ,在数据库字典中查找和它像对应的 redisObject ,如果没找到,就返回 NULL
  2. 检查 redisObject 的 type 属性和执行命令所需的类型是否相符,如果不相符,返回类型错误。
  3. 根据 redisObject 的 encoding 属性所指定的编码,选择合适的操作函数来处理底层的数据结构
  4. 返回数据结构的操作结果作为命令的返回值

Demo: LPOP 的完整的执行过程

redis 数据类型

1.3 对象共享

命令的返回值 OK 、 ERROR 、 WRONGTYPE 等常见的字符情况, Redis 在内部使用了一个 Flyweight 模式 :通过预分配一些常见的值
对象,并在多个数据结构之间共享这些对象,程序避免了重复分配的麻烦,也节约了一些 CPU 时间。(怎么样预分配,节约了 CPU 时间,单例或者静态模式?

Redis 预分配的值对象有如下这些:

  • 各种命令的返回值,比如执行成功时返回的 OK ,执行错误时返回的 ERROR ,类型错误时返回的 WRONGTYPE ,命令入队事务时返回的 QUEUED ,等等。
  • 包 括 0 在 内, 小 于 redis.h/REDIS_SHARED_INTEGERS 的 所 有 整 数(REDIS_SHARED_INTEGERS 的默认值为 10000)

因为命令的回复值直接返回给客户端,所以它们的值无须进行共享;另一方面,如果某个命令的输入值是一个小于 REDIS_SHARED_INTEGERS 的整数对象,那么当这个对象要被保存进数据库时, Redis 就会释放原来的值,并将值的指针指向共享对象。

redis 数据类型

1.4 引用计数以及对象的销毁

Redis 的对象系统使用了引用计数技术来负责维持和销毁对象,它的运作机制如下:

  • 每个 redisObject 结构都带有一个 refcount 属性,指示这个对象被引用了多少次。
  • 当新创建一个对象时,它的 refcount 属性被设置为 1 。
  • 当对一个对象进行共享时, Redis 将这个对象的 refcount 增一。
  • 当使用完一个对象之后,或者取消对共享对象的引用之后,程序将对象的 refcount 减一。
  • 当对象的 refcount 降至 0 时,这个 redisObject 结构,以及它所引用的数据结构的内存,都会被释放。

1.5 字符串

字符串类型分别使用 REDIS_ENCODING_INT 和 REDIS_ENCODING_RAW 两种编码:

  • REDIS_ENCODING_INT 使用 long 类型来保存 long 类型值。

  • REDIS_ENCODING_RAW 则使用 sdshdr 结构来保存 sds (也即是 char* )、 long long 、
    double 和 long double 类型值。

    redis 数据类型

2. 哈希表

哈希表有两种实现方式,压缩列表(REDIS_ENCODING_ZIPLIST)和 字典(REDIS_ENCODING_HT)

redis 数据类型

创建空白哈希表时,程序默认使用 REDIS_ENCODING_ZIPLIST 编码,当以下任何一个条件被满足时,程序将编码从切换为 REDIS_ENCODING_HT :

  • 哈希表中某个键或某个值的长度大于 server.hash_max_ziplist_value (默认值为 64)。
  • 压缩列表中的节点数量大于 server.hash_max_ziplist_entries (默认值为 512 )。

3. 列表

使用 REDIS_ENCODING_ZIPLIST 和 REDIS_ENCODING_LINKEDLIST 这两种方式编码:

redis 数据类型

创建新列表时 Redis 默认使用 REDIS_ENCODING_ZIPLIST 编码,当以下任意一个条件被满足时,列表会被转换成 REDIS_ENCODING_LINKEDLIST 编码:

  • 试 图 往 列 表 新 添 加 一 个 字 符 串 值, 且 这 个 字 符 串 的 长 度 超 过 server.list_max_ziplist_value (默认值为 64 )。
  • ziplist 包含的节点超过 server.list_max_ziplist_entries (默认值为 512 )。

3.1 阻塞的条件

BLPOP 、 BRPOP 和 BRPOPLPUSH 三个命令都可能造成客户端被阻塞,阻塞原语并不是一定会造成客户端阻塞:

  • 只有当这些命令被用于空列表时,它们才会阻塞客户端。
  • 如果被处理的列表不为空的话,它们就执行无阻塞版本的 LPOP 、 RPOP 或 RPOPLPUSH 命令。

执行的过程和原理:

redis 数据类型

阻塞一个客户端需要执行以下步骤:

  1. 将客户端的状态设为“正在阻塞” ,并记录阻塞这个客户端的各个键,以及阻塞的最长时限(timeout)等数据。
  2. 将客户端的信息记录到 server.db[i]->blocking_keys 中(其中 i 为客户端所使用的数据库号码)。
  3. 继续维持客户端和服务器之间的网络连接,但不再向客户端传送任何信息,造成客户端阻塞。

步骤 2 是将来解除阻塞的关键, server.db[i]->blocking_keys 是一个字典,字典的键是那些造成客户端阻塞的键,而字典的值是一个链表,链表里保存了所有因为这个键而被阻塞的客户端(被同一个键所阻塞的客户端可能不止一个):

redis 数据类型

在上图展示的 blocking_keys 例子中, client2 、 client5 和 client1 三个客户端就正被 key1 阻塞,而其他几个客户端也正在被别的两个 key 阻塞。

脱离阻塞的方式:

  1. 被动脱离:有其他客户端为造成阻塞的键推入了新元素。
  2. 主动脱离:到达执行阻塞原语时设定的最大阻塞时间。
  3. 强制脱离:客户端强制终止和服务器的连接,或者服务器停机。

3.2 阻塞因 LPUSH 、 RPUSH 、 LINSERT 等添加命令而被取消

通过将新元素推入造成客户端阻塞的某个键中,可以让相应的客户端从阻塞状态中脱离出来(取消阻塞的客户端数量取决于推入元素的数量).

LPUSH 、 RPUSH 和 LINSERT 这三个添加新元素到列表的命令, 在底层都由一个 pushGenericCommand 的函数实现,这个函数的运作流程如下图

redis 数据类型

当向一个空键推入新元素时, pushGenericCommand 函数执行以下两件事:

  1. 检查这个键是否存在于前面提到的 server.db[i]->blocking_keys 字典里,如果是的话,那么说明有至少一个客户端因为这个 key 而被阻塞,程序会为这个键创建一个 redis.h/readyList 结构,并将它添加到 server.ready_keys 链表中。
  2. 将给定的值添加到列表键中。

readyList 结构的定义如下:

1
2
3
4
typedef struct readyList {
redisDb *db;
robj *key;
} readyList;

readyList 结构的 key 属性指向造成阻塞的键,而 db 则指向该键所在的数据库。

假设某个非阻塞客户端正在使用 0 号数据库,而这个数据库当前的 blocking_keys 属性的值如下:

redis 数据类型

如果此时执行 PUSH key3 value 命令,那么 pushGenericCommand 将创建一个 db 属性指向 0 号数据库、 key 属性指向 key3 键对象的 readyList 结构,并将它添加到服务器 server.ready_keys 属性的链表中:

redis 数据类型

4. 集合

它 使 用 REDIS_ENCODING_INTSET 和 REDIS_ENCODING_HT 两种方式编码

一个添加到集合的元素,决定了创建集合时所使用的编码:

  • 如果第一个元素可以表示为 long long 类型值(也即是,它是一个整数),那么集合的初始编码为 REDIS_ENCODING_INTSET 。
  • 否则,集合的初始编码为 REDIS_ENCODING_HT

redis 数据类型

4.1 编码的切换

如果一个集合使用 REDIS_ENCODING_INTSET 编码,那么当以下任何一个条件被满足时,这个
集合会被转换成 REDIS_ENCODING_HT 编码:

  • intset 保存的整数值个数超过 server.set_max_intset_entries (默认值为 512 )。
  • 试图往集合里添加一个新元素,并且这个元素不能被表示为 long long 类型(也即是,它不是一个整数)

字典编码

当使用 REDIS_ENCODING_HT 编码时,集合将元素保存到字典的键里面,==而字典的值则统一设
为 NULL ==。(为啥??)
作为例子,以下图片展示了一个以 REDIS_ENCODING_HT 编码表示的集合,集合的成员为 elem1
、 elem2 和 elem3

redis 数据类型

4.2 有序集

使 用 REDIS_ENCODING_ZIPLIST 和 REDIS_ENCODING_SKIPLIST 两种方式编码。

如果第一个元素符合以下条件的话,就创建一个 REDIS_ENCODING_ZIPLIST 编码的有序集:

  • 服务器属性 server.zset_max_ziplist_entries 的值大于 0 (默认为 128 )。
  • 元素的 member 长度小于服务器属性 server.zset_max_ziplist_value 的值(默认为 64)。

否则,程序就创建一个 REDIS_ENCODING_SKIPLIST 编码的有序集。如果元素在增加的过程中,不满足上面的任意一个条件,则会转化成 REDIS_ENCODING_SKIPLIST

redis 数据类型

SKIPLIST 编码的有序集

1
2
3
4
5
6
7
8
9
/*
* 有序集
*/
typedef struct zset {
// 字典
dict *dict;
// 跳跃表
zskiplist *zsl;
} zset;

zset 同时使用字典和跳跃表两个数据结构来保存有序集元素。
其中,元素的成员由一个 redisObject 结构表示,而元素的 score 则是一个 double 类型的浮点数,字典和跳跃表两个结构通过将指针共同指向这两个值来节约空间(不用每个元素都复制两份)

下图展示了一个 REDIS_ENCODING_SKIPLIST 编码的有序集:

redis 数据类型

Redis底层原理--03. Redis 数据类型

http://blog.laofu.online/2020-11-30-redis03/

作者

付威的网络博客

发布于

2020-11-30

更新于

2020-11-30

许可协议

评论