0%

Redis 设计与实现-对象

发表于 更新于 分类于 ， 阅读次数： Valine：
本文字数： 3.2k 阅读时长 ≈ 3 分钟

在前面的数个章节里,我们陆续介绍了Redis用到的所有主要数据结构,比如简单动态字符串(SDS)、双端链表、字典、压缩列表、整数集合等等。

我们知道，Redis 用到的所有主要数据结构包括有简单动态字符串(SDS)、双端链表、字典、压缩列表、整数集合等等。Redis 并没有直接使用这些数据结构来实现键值对数据库,而是基于这些数据结构创建了一个对象系统, 这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象, 每种对象都用到了至少一种我们前面所说的数据结构。

通过这五种不同类型的对象, Redis 可以在执行命令之前,根据对象的类型来判断一个对象是否可以执行给定的命令。使用对象的另一个好处是, 我们可以针对不同的使用场景, 为对象设置多种不同的数据结构实现,从而优化对象在不同场景下的使用效率。

本文接下来将逐一介绍以上提到的 Redis 对象系统的各个特性。

1. 对象的类型与编码

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

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

1.1 类型

对象的 type 属性记录了对象的类型, 这个属性的值可以是表8-1列出的常量的其中一个。

1.2 编码

对象的 ptr 指针指向对象的底层实现数据结构, 而这些数据结构由对象的 encoding 属性决定。encoding 属性记录了对象所使用的编码, 也即是说这个对象使用了什么数据结构作为对象的底层实现, 这个属性的值可以是表8-3列出的常量的其中一个。

每种类型的对象都至少使用了两种不同的编码, 表8-4列出了每种类型的对象可以使用的编码。

通过 encoding 属性来设定对象所使用的编码, 而不是为特定类型的对象关联一种固定的编码,极大地提升了Redis的灵活性和效率,因为 Redis 可以根据不同的使用场景来为一个对象设置不同的编码, 从而优化对象在某一场景下的效率。

2. 字符串对象

字符串对象的编码可以是 int、raw 或者 embstr。

如果一个字符串对象保存的是整数值, 并且这个整数值可以用 Long 类型来表示, 那么字符串对象会将整数值保存在字符串对象结构的 ptr 属性里面 (将 void* 转换成 Long), 并将字符串对象的编码设置为 int。例如下图：

如果字符串对象保存的是一个字符串值, 并且这个字符串值的长度大于32字节,那么字符串对象将使用一个简单动态字符串(SDS)来保存这个字符串值, 并将对象的编码设置为 raw。

如果字符串对象保存的是一个字符串值, 并且这个字符串值的长度小于等于32字节, 那么字符串对象将使用 embstr 编码的方式来保存这个字符串值。

2.1 编码的转换

int 编码的字符串对象和 embstr 编码的字符串对象在条件满足的情况下, 会被转换为 raw 编码的字符串对象。对于 int 编码的字符串对象来说, 如果我们向对象执行了一些命令, 使得这个对象保存的不再是整数值, 而是一个字符串值, 那么字符串对象的编码将从 int 变为 raw。

3. 列表对象

列表对象的编码可以是 ziplist 或者 linkedllist。

ziplist 编码的列表对象使用压缩列表作为底层实现, 每个压缩列表节点 (entry) 保存了一个列表元素。例如图8-5所示：

另一方面, linkedllist 编码的列表对象使用双端链表作为底层实现, 每个双端链表节点 (node) 都保存了一个字符串对象, 而每个字符串对象都保存了一个列表元素。

3.1 编码的转换

当列表对象可以同时满足以下两个条件时, 列表对象使用 ziplist 编码:

  • 列表对象保存的所有字符串元素的长度都小于64字节;

  • 列表对象保存的元素数量小于512个; 不能满足这两个条件的列表对象需要使用 linkedllist 编码。

4. 哈希对象

哈希对象的编码可以是 ziplist 或者 hashtable。
ziplist 编码的哈希对象使用压缩列表作为底层实现, 每当有新的键值对要加入到哈希对象时, 程序会先将保存了键的压缩列表节点推人到压缩列表表尾, 然后再将保存了值的压缩列表节点推人到压缩列表表尾, 因此:

  • 保存了同一键值对的两个节点总是紧换在一起, 保存键的节点在前, 保存值的节点在后;
  • 先添加到哈希对象中的键值对会被放在压缩列表的表头方向, 而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。

示例如下：

其中压缩列表结果如下：

另一方面, hashtable 编码的哈希对象使用字典作为底层实现, 哈希对象中的每个键值对都使用一个字典键值对来保存:

  • 字典的每个键都是一个字符串对象, 对象中保存了键值对的键;
  • 字典的每个值都是一个字符串对象, 对象中保存了键值对的值。

示例如下：

3.1 编码转换

当哈希对象可以同时满足以下两个条件时, 哈希对象使用 ziplist 编码:

  • 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节;

  • 哈希对象保存的键值对数量小于512个; 不能满足这两个条件的哈希对象需要使用 hashtable 编码。

5. 集合对象

集合对象的编码可以是 intset 或者 hashtable。intset 编码的集合对象使用整数集合作为底层实现, 集合对象包含的所有元素都被保存在整数集合里面。举个例子, 以下代码将创建一个如图8-12所示的 intset 编码集合对象:

1
2
redis> SADD numbers 1 3 5
(integer) 3

另一方面, hashtable 编码的集合对象使用字典作为底层实现, 字典的每个键都是一个字符串对象, 每个字符串对象包含了一个集合元素, 而字典的值则全部被设置为NULL。举个例子,以下代码将创建一个如图8-13所示的 hashtable 编码集合对象:

5.1 编码的转换

当集合对象可以同时满足以下两个条件时,对象使用 intset 编码:

  • 集合对象保存的所有元素都是整数值;

  • 集合对象保存的元素数量不超过512个。

不能满足这两个条件的集合对象需要使用 hashtable 编码。

6. 有序集合对象

有序集合的编码可以是 ziplist 或者 skiplist。

ziplist 编码的压缩列表对象使用压缩列表作为底层实现, 每个集合元素使用两个紧挨在一起的压缩列表节点来保存, 第一个节点保存元素的成员(member), 而第二个元素则保存元素的分值(score)。压缩列表内的集合元素按分值从小到大进行排序, 分值较小的元素被放置在靠近表头的方向, 而分值较大的元素则被放置在靠近表尾的方向。示例如下：

其中压缩列表部分如下图所示：

skiplist 编码的有序集合对象使用 zset 结构作为底层实现, 一个zset结构同时包含一个字典和一个跳跃表:

1
2
3
4
typedef struct zset {
    zkiplist *zsl;
    dict *dict;
} zset;

示例如下：

6.1 编码的转换

当有序集合对象可以同时满足以下两个条件时, 对象使用 ziplist 编码:

  • 有序集合保存的元累数量小于128个;
  • 有序集合保存的所有元素成员的长度都小于64字节; 不能满足以上两个条件的有序集合对象将使用 skiplist 编码。

7. 对象共享

目前来说, Redis 会在初始化服务器时, 创建一万个字符串对象, 这些对象包含了从0到9999的所有整数值, 当服务器需要用到值为0到9999的字符串对象时, 服务器就会使用这些共享对象,而不是新创建对象。

------ 本文结束------