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

发表于 2020-11-30 分类于 Redis

1. 对象处理机制

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

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

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

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

redisObject 的定义位于 redis.h ：

/*
* 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）：

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

/*
对象编码
*/
#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 的执行过程：

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

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 类型值。

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 数据类型

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

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

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

redis 数据类型

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

脱离阻塞的方式：

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

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

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

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

redis 数据类型

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

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

readyList 结构的定义如下：

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 编码的有序集

/*
* 有序集
*/
typedef struct zset {
  // 字典
  dict *dict;
  // 跳跃表
  zskiplist *zsl;
} zset;

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

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

redis 数据类型