Redis中的对象底层实现

Redis的优点之一就是支持丰富的对象，这个对象系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象。本文将对上述五种对象逐一介绍。

I、对象的类型与编码

Redis使用对象来表示数据库中的键和值，其中键对象只能使用字符串，而值对象可以使用五种对象中的任意一种。

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

typedef struct redisObject {

    // 类型
    unsigned type:4;

    // 编码
    unsigned encoding:4;

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

    // ...

} robj;

1.1 类型

对象的type属性记录了对象的类型，这个类型可以是下表中的任意一个。

当我们对一个数据库执行TYPE命令时，命令返回的结果为数据库键对应的值对象的类型。

1.2 编码和底层实现

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

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

每种type的对象都至少使用了两种不同的编码：

使用OBJECT ENCODING命令可以查看一个数据库的值对象的编码。

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

例如：在list对象包含元素较少时，Redis使用ziplist作为list对象的底层实现：
因为ziplist比linkedlist更节约内存，并且在元素较少时，在内存中以连续块方式保存的ziplist比linkedlist能更快的载入到缓存中。

II、字符串对象

2.1 字符串对象编码类型

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

字符串对象底层数据结构

三种底层结构的存储结构如下：
int：

raw：

embstr：
embstr编码是专门用于保存短字符串的一种优化编码方式，这种编码方式与raw一样，都使用RedisObject结构和sdshdr结构来表示字符串对象，但raw编码对调用两次内存分配函数来分别创建RedisObject和sdshdr结构，而embstr编码则通过一次内存分配函数来分配一块连续的空间，空间中依次包含RedisObject和sdshdr；此外因为embstr编码的字符串对象将所有数据保存在一块连续的内存空间中，这样可以更好的利用缓存来带来优势。

下表再次展示了string对象的底层数据结构:

2.2 编码的转换

int编码的字符串对象和embstr编码的字符串对象在满足条件的情况下会被转化为raw编码的字符串对象。

Redis没有为embstr编码的字符串对象编写任何相应的修改程序，所以embstr编码的字符串对象实际上是只读的。当我们队embstr编码的字符串对象执行任何修改命令时，程序会先将对象的编码转化为raw，然后在执行修改命令。

2.3 字符串命令的实现

III、列表对象

3.1 列表对象编码类型

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

list对象底层数据结构

如果list对象使用ziplist，这个值对象的结构如下图：

如果list对象使用linkedlist（双端链表）作为底层实现，每个双端链表节点都保存了一个字符串对象，而每个字符串对象都保存了一个列表元素。

linkedlist编码的列表对象在底层的双端链表结构中包含了多个字符串对象，这种嵌套字符串对象的行为在后面的哈希对象、集合对象和有序集合对象中都会出现，字符串对象是Redis五种类型的对象中唯一一种会被其他对象嵌套的对象。

3.2 编码转换

当列表对象同时满足数量与长度的两个条件时发生编码转换。

3.3 列表命令的实现

IV、哈希对象

4.1 哈希对象编码类型

哈希对象的编码可以是ziplist或者hashtable。

哈希对象底层数据结构

当使用ziplist作为哈希对象的底层实现时，每当有新的键值对要加入到哈希对象时，程序会先向保存了键的ziplist节点推入到表尾，然后再将保存了值的ziplist节点推到表尾：
· 保存了同一键值对的两个节点总是紧挨在一起。
· 先添加的键值对在表头方向。

在使用hashtable编码的哈希对象使用字典作为底层实现，哈希对象中的每个键值对都是用一个字典键来保存：
· 字典的每个键都是一个字符串对象，对象中保存了键值对的键。
· 字典中的每个值都是一个字符串对象，对象保存了键值对的值。

4.2 编码转换

当哈希对象同时满足长度与数量两个条件时，发生编码转换。

4.3 哈希命令的实现

V、集合对象

5.1 集合对象编码类型

集合对象的编码可以是intset或者hashtable。

set对象底层数据结构

如果使用inset作为set对象底层实现，则其结构如下：

另一方面，hashtable编码的set对象使用字典作为底层实现，字典的每个键都是一个字符串独享，每个字符串对象包含一个集合元素，而字典的值全部设置为NULL

5.2 编码的转换

当set对象可以同时满足保存元素与数量的两个条件时，发生编码的转换。

5.3 集合命令的实现

VI、有序集合对象

6.1 有序集合对象编码类型

zset的编码可以是ziplist或者skiplist&dict。

zset对象底层数据结构

ziplist编码的有序集合对象使用压缩列表作为底层实现，每个集合元素使用两个紧邻的ziplist节点来保存，第一个节点保存元素成员（member），第二个元素保持元素分值（score）。

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

typedef struct zset {

    zskiplist *zsl;

    dict *dict;

} zset;

zset结构中跳跃表按分值从小到大保存了所有集合元素，每个跳跃表节点都保持一个集合元素：跳跃表节点的object保存member，跳跃表节点的score保存元素的score。通过跳跃表，程序可以对zset进行范围型操作，如ZRANK, ZRANGE就是通过跳跃表的API实现的。
除此之外，zset结构中的dict为有序集合创建了一个从member到score的映射。
通过skiplist与dict的组合，zset实现了O(1)时间查找member的score，并且满足有序与范围操作。

6.2 编码的转换

当zset对象同时满足元素数量与元素长度的时候，发生编码转换。

6.3 有序集合命令的实现

【参考】
[1] 《Redis设计与实现》

欢迎转载，转载请注明出处wenmingxing Redis中的对象底层实现