Redis数据结构一之对象的介绍及各版本对应实现

你的名字 2024-03-22 17:19 23阅读 0赞

本篇笔记开始介绍 Redis 数据结构的底层实现。

当我们被问到 Redis 中有什么数据结构，或者说数据类型，我们可能会说有字符串、列表、哈希、集合、有序集合。

其实这几种数据类型在 Redis 中都由对象构成，而且是两个对象，一个键对象，一个值对象。

在这些数据类型中，它们的键都是字符串对象，而值可以是前面说的字符串对象、列表对象、哈希对象、集合对象、有序集合对象中的一种，这个取决于键值对的数据类型。

而在 Redis 中，这些对象都有其更底层的实现方式，也就是说这一篇笔记我们要介绍的，更底层的数据结构，而且不同的 Redis 版本有不一样的数据结构，最基础的数据结构包括简单动态字符串、字典、跳跃表、整数集合等，

接下来我们先介绍一下 Redis 中对象的构成，然后介绍一下不同 Redis 版本中每个对象所使用的的底层数据结构，之后再逐个介绍这些数据结构的实现原理，以下是本篇笔记的目录：

1.  Redis 对象的介绍
2.  不同版本的 Redis 对象的数据结构

**注意**：本篇文章的主体框架内容是基于书籍《Redis设计与实现》进行描述的，部分过时内容都基于网上查询的相应资料与最新版本进行了对齐，如有其他疏漏，还望指正。

#### 1、Redis 对象的介绍 ####

举一个例子，当我们设置一个字符串类型的数据：

set msg "hello world"

这样，我们就创建了两个对象，且两个都是字符串对象，因为键值对的 key 和 value 都是字符串。

如果我们创建了一个列表数据，那么 key 是字符串对象，而值 value 是列表对象。

在 Redis 中，每个对象都由一个 redisObject 结构来表示：

typedef struct redisObject{
        //类型
        unsigned type:4;
        
        //编码
        unsigned encoding:4;
        
        //指向底层实现数据结构的指针
        void *ptr
        
        //...
    } robj;

**type**

在上面的结构中，type 指的是这个对象的类型，比如我们创建了一个列表数据，那么这个数据的 key 就是一个字符串对象，由这个结构里的 type 来指定，这个数据的 value 就是一个列表对象，也是由 type 来进行指定区分。

但是，当我们想要知道一条数据的数据类型是字符串、列表、哈希、集合、有序集合的哪一种时，我们常常是需要知道的这条数据的 value 的类型，一般也是指的 value 的类型，因为数据的 key 的类型总是字符串对象。

一条数据的值对象类型的获取我们可以用 TYPE 命令来操作：

TYPE msg

TYPE 类型的值输出就是我们那五种类型：string、list、hash、set、zset

**encoding**

encoding 指的是这个对象底层数据结构使用的编码。

一个对象在不同的情况下的编码及底层数据结构可能是不一样的，比如对于字符串对象，它的编码包括 int，embstr，raw 这三种，但后两种的底层结构其实都是简单动态字符串（SDS），不过它们的底层使用方式略有不同，这个我们在下一节再介绍。

获取对象的值的编码使用 `OBJECT ENCODING` 命令：

OBJECT ENCODING msg

**ptr**

ptr 则是作为指针指向的是对象的底层数据结构地址。

上面这些查看对象底层编码的命令，我们会在介绍完各个底层数据结构之后根据存储的不同数据类型进行使用。

#### 2、不同版本的 Redis 对象的数据结构 ####

Redis 3.2 版本以前

在 Redis 3.2 版本以前，每个对象对应的编码，及底层数据结构如下：

**字符串对象**

<table> 
 <thead> 
  <tr> 
   <th>编码（OBJECT ENCODING输出结果）</th> 
   <th>底层数据结构</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>int</td> 
   <td>整数</td> 
  </tr> 
  <tr> 
   <td>embstr</td> 
   <td>embstr编码的SDS</td> 
  </tr> 
  <tr> 
   <td>raw</td> 
   <td>SDS</td> 
  </tr> 
 </tbody> 
</table>

**列表对象**

<table> 
 <thead> 
  <tr> 
   <th>编码（OBJECT ENCODING输出结果）</th> 
   <th>底层数据结构</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>ziplist</td> 
   <td>压缩列表</td> 
  </tr> 
  <tr> 
   <td>linkedlist</td> 
   <td>双向链表</td> 
  </tr> 
 </tbody> 
</table>

**哈希对象**

<table> 
 <thead> 
  <tr> 
   <th>编码（OBJECT ENCODING输出结果）</th> 
   <th>底层数据结构</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>ziplist</td> 
   <td>压缩列表</td> 
  </tr> 
  <tr> 
   <td>hashtable</td> 
   <td>字典</td> 
  </tr> 
 </tbody> 
</table>

**集合对象**

<table> 
 <thead> 
  <tr> 
   <th>编码（OBJECT ENCODING输出结果）</th> 
   <th>底层数据结构</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>intset</td> 
   <td>整数集合</td> 
  </tr> 
  <tr> 
   <td>hashtable</td> 
   <td>字典</td> 
  </tr> 
 </tbody> 
</table>

**有序集合对象**

<table> 
 <thead> 
  <tr> 
   <th>编码（OBJECT ENCODING输出结果）</th> 
   <th>底层数据结构</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>ziplist</td> 
   <td>压缩列表</td> 
  </tr> 
  <tr> 
   <td>skiplist</td> 
   <td>跳跃表</td> 
  </tr> 
 </tbody> 
</table>

Redis 3.2 版本

而在 3.2 版本，主要对列表对象的底层实现做了修改，由 quicklist 构成底层实现，quicklist 实际上是 linkedlist 和 ziplist 的混合结构。

**列表对象**

<table> 
 <thead> 
  <tr> 
   <th>编码（OBJECT ENCODING输出结果）</th> 
   <th>底层数据结构</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>quicklist</td> 
   <td>快速列表</td> 
  </tr> 
 </tbody> 
</table>

Redis 5.1 之后版本

在 Redis 5.1 版本，引入了新的数据结构 listpack，6.x 版本作为过渡阶段，并且在 7.0 版本，listpack 已经完全替换了 ziplist，成为了哈希对象、有序集合对象的底层数据结构的原有实现之一，更改如下：

**哈希对象**

<table> 
 <thead> 
  <tr> 
   <th>编码（OBJECT ENCODING输出结果）</th> 
   <th>底层数据结构</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>listpack</td> 
   <td>listpack</td> 
  </tr> 
  <tr> 
   <td>hashtable</td> 
   <td>字典</td> 
  </tr> 
 </tbody> 
</table>

**有序集合对象**

<table> 
 <thead> 
  <tr> 
   <th>编码（OBJECT ENCODING输出结果）</th> 
   <th>底层数据结构</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>listpack</td> 
   <td>listpack</td> 
  </tr> 
  <tr> 
   <td>skiplist</td> 
   <td>跳跃表</td> 
  </tr> 
 </tbody> 
</table>

而且 quicklist 也变成了 linkedlist 和 listpack 的混合结构