redis的五种数据结构原理分析

淡淡的烟草味﹌ 2023-01-05 09:52 207阅读 0赞

Redis 是一个开源（BSD许可）的，内存中的数据结构存储系统，它可以用作数据库、缓存和消息中间件. 它支持多种类型的数据结构，如 字符串（strings）， 散列（hashes）， 列表（lists）， 集合（sets）， 有序集合（sorted sets） 与范围查询， bitmaps， hyperloglogs和 地理空间（geospatial） 索引半径查询。

简单来说，Redis的数据结构主要分为五种基本的数据结构+三种高级的数据结构。我们下面所要介绍的就是这五种基本的数据结构的相关知识。

# 结构模型 #

在我们基本的数据结构中，它又有自己的内部编码。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvYm96YWk4Ng_size_16_color_FFFFFF_t_70][]

**总结一下**

（1）每种数据结构都有自己底层的内部编码实现，而且是多种实现，这样Redis会在合适的场景选择合适的内部编码。

（2）可以看到每种数据结构都有两种以上的内部编码实现，例如string数据结构就包含了raw、int和embstr三种内部编码。

（3）同时，有些内部编码可以作为多种外部数据结构的内部实现，例如ziplist就是hash、list和zset共有的内部编码。

# 基础结构模型 #

我们在上面了解到了关于键的基本数据结构。而我们Redis中的所有value都是以object的形式存在的。其通用结构结构源码如下：

typedef struct redisObject {
        unsigned [type] 4;
        unsigned [encoding] 4;
        unsigned [lru] REDIS_LRU_BITS;
        int refcount;
        void *ptr;
    } robj;

（1）type指的就是我们的基本数据结构，如string，list等其他类型；

（2）encoding指的是这些结构内部类型的具体实现方式，如string可以用int来实现也可以用char\[\]来实现；list可以用ziplist或者链表来实现；

（3）lru表示本对象的空转时长，用于有限内存下长时间不访问的对象清理；

（4）refcount对象引用计数，用于GC；

（5）ptr指向以encoding方式实现这个对象实际实现者的地址，如String对象对应的SDS（*Simple Dynamic String* 结构）地址。

示意图如下：

![e0b7afa6136c80a5f660b712c80a4a56.png][]

# 字符串类型 #

## 字符串类型内部编码 ##

字符串类型的内部编码有3种：

*  **int**：8个字节的长整型。
 *  **embstr**：小于等于39个字节的字符串。
 *  **raw**：大于39个字节的字符串。

Redis会根据当前值的类型和长度决定使用内部编码实现。

redis是使用C语言开发，但C中并没有字符串类型，只能使用指针或符数组的形式表示一个字符串，所以redis设计了一种简单动态字符串(SDS\[Simple Dynamic String\])作为底实现：

struct __attribute__ ((__packed__)) sdshdr5 {
       unsigned char flags; 
       char buf[];
    };
    struct __attribute__ ((__packed__)) sdshdr8 {
       uint8_t len; 
       uint8_t alloc; 
       unsigned char flags; 
       char buf[];
    };
    struct __attribute__ ((__packed__)) sdshdr16 {
       uint16_t len;
       uint16_t alloc; 
       unsigned char flags;
       char buf[];
    };
    struct __attribute__ ((__packed__)) sdshdr32 {
       uint32_t len;
       uint32_t alloc; 
       unsigned char flags; 
       char buf[];
    };
    struct __attribute__ ((__packed__)) sdshdr64 {
       uint64_t len; 
       uint64_t alloc;
       unsigned char flags; 
       char buf[];
    };

从源码的文件里面可以看见，同样一组结构Redis使用泛型定义了好多次。那么为什么不直接用int类型呢？这里呢主要是因为当字符串比较短的时候，len和alloc可以使用byte和short来表示，Redis为了对内存做极致的优化，不同长度的字符串使用不同的结构体来表示。

**为什么不直接使用C字符串呢？**

我们为什么要重新在定义一个SDS的动态字符串的结构？其实呢这主要是为了从Redis对字符串安全性和效率以及功能方面的要求。C 语言使用了一个长度为 N+1 的字符数组来表示长度为 N 的字符串，并且字符数组最后一个元素总是 `'\0'`。而在Redis中`\0`可能会被判定为提前结束而识别不了字符串。通过分析可以发现，总共有以下一些缺点：

（1）获取字符串长度为O(n)，因为C字符串需要去遍历。

（2）不能很好的杜绝缓冲区溢出/内存泄漏的问题，因为原因同上，进行字符串拼接等其他操作获取长度的时候易出现问题。

（3）C字符串只能保存文本数据，因为必须符合某种编码（如ASCLL）。像一些`\0`就不易处理。

表格区别汇总如下。

<table> 
 <thead> 
  <tr> 
   <th>C字符串</th> 
   <th>SDS</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>获取字符串长度的复杂度为O(N)</td> 
   <td>获取字符串长度的复杂度为O(1)</td> 
  </tr> 
  <tr> 
   <td>API是不安全的，可能会造成缓冲区溢出</td> 
   <td>API是安全的，不会造成缓冲区溢出</td> 
  </tr> 
  <tr> 
   <td>修改字符串长度N次必然需要执行N次内存重分配</td> 
   <td>修改字符串长度N次最多需要执行N次内存重分配</td> 
  </tr> 
  <tr> 
   <td>只能保存文本数据</td> 
   <td>可以保存文本或者二进制数据</td> 
  </tr> 
  <tr> 
   <td>可以使用所有&lt;string.h&gt;库中的函数</td> 
   <td>可以使用一部分&lt;string.h&gt;库中的函数</td> 
  </tr> 
 </tbody> 
</table>

**raw与embstr的区别**

（1）redis并未提供任何修改embstr的方式，即embstr是只读的形式。对embstr的修改实际上是先转换为raw再进行修改。

（2）采用内存分配方式不同，虽然raw和embstr编码方式都是使用redisObject结构和sdshdr结构。但是raw编码方式采用两次分配内存的方式，分别创建redisObject和sdshdr，而embstr编码方式则是采用一次分配，分配一个连续的空间给redisObject和sdshdr。（embstr一次性分配内存的方式：1，使得分配空间的次数减少。2、释放内存也只需要一次。3、在连续的内存块中，利用了缓存的优点。）

# List类型 #

我们在最开始的图上面也介绍了，list列表的数据结构使用的是压缩列表ziplist和普通的双向链表linkedlist组成。元素少的时候会用ziplist，元素多的时候会用linkedlist。然后针对这两种的弊端又设计出了一个快速列表。关于双向链表，老数据结构不介绍了，这里重点介绍一下压缩列表和快速列表。

## 压缩列表 ##

**ziplist**是一种压缩链表，它的好处是更能节省内存空间，因为它所存储的内容都是在连续的内存区域当中的。当列表对象元素不大，每个元素也不大的时候，就采用ziplist存储。但当数据量过大时就ziplist就不是那么好用了。因为为了保证他存储内容在内存中的连续性，插入的复杂度是O(N)，即每次插入都会重新进行realloc。如下图所示，对象结构中ptr所指向的就是一个ziplist。整个ziplist只需要malloc一次，它们在内存中是一块连续的区域。

ziplist的结构表如下：

![adf9f00a42df50570a3bcd418c9716d8.png][]

1、zlbytes:用于记录整个压缩列表占用的内存字节数

2、zltail：记录要列表尾节点距离压缩列表的起始地址有多少字节

3、zllen：记录了压缩列表包含的节点数量。

4、entryX：要说列表包含的各个节点

5、zlend：用于标记压缩列表的末端

**为什么数据量大不使用ziplist？**

我们在上面也说到了，因为它的插入的时间复杂度是O(n)，而且插入一个新的元素就要调用realloc进行扩展内存。取决于内存分配器算法和当前的ziplist内存大小，realloc可能会重新分配新的内存空间，并将之前的内容一次性拷贝到新的地址，也可能直接原地扩展。而如果我们的数据量大的话，那么重新分配内存和拷贝内存就会有很大的消耗。所以ziplist不适合大型字符串，存储的元素也不宜过多。

## 快速列表 ##

其实这里如果看网上早期的博客很容易漏掉一个数据结构。我们的Redis早期版本list内部编码是ziplist或者linkedlist，但是这两者都有着自己的缺点。ziplist的数据量大不适合用，在上面也重点介绍了，而linkedlist的附加空间相对太高，prev和next指针就要占去16个字节，而且每一个结点都是单独分配，会加剧内存的碎片化，影响内存管理效率。

所以针对这两种编码数据结构，后续版本进行了改造了，诞生了quicklist。

quicklist是ziplist和linkedlist的混合体，它将linkedlist按段切分，每一段使用ziplist来紧凑存储，多个ziplist之间使用双指针串接起来。

![4deec5780def48c7112e825da2a5118a.png][]

**ziplist的长度**

quicklist内部默认单个ziplist长度为8k字节，超出了这个字节数，就会新起一个ziplist。关于长度可以使用`list-max-ziplist-size`来决定。

**压缩深度**

我们上面说到了quicklist下是用多个ziplist组成的，同时为了进一步节约空间，Redis还会对ziplist进行压缩存储，使用LZF算法压缩，可以选择压缩深度。

![e16a2e02cccc2ac0cf4195cfeb0e5bf3.png][]

quicklist默认的压缩深度是0，也就是不压缩。压缩的实际深度由配置参数`list-compress-depth`决定。为了支持快速的 `push/pop` 操作，quicklist 的首尾两个 ziplist 不压缩，此时深度就是 1。如果深度为 2，就表示 quicklist 的首尾第一个 ziplist 以及首尾第二个 ziplist 都不压缩。

# Hash类型 #

哈希类型的底层编码可以是ziplist也可以是我们的hashtable。ziplist在上面我们已经介绍了，这里我们着重介绍一下hashtable。

## HashTable结构 ##

我们的hashtable主要是通过dict来实现的。

typedef struct dict {
        dictType *type;
        void *privdata;
        dictht ht[2];
        long rehashidx; /* rehashing not in progress if rehashidx == -1 */
        int iterators; /* number of iterators currently running */
    } dict;

可以看到我们每个dict结构里面都有两个hashtable。（ht\[0\]和ht\[1\]）

虽然dict结构有两个hashtable，但是通常情况下只有一个hashtable是有值的。但是在dict扩容缩容的时候，需要分配新的hashtable，然后进行渐近式搬迁，这时候两个hashtable存储的旧的hashtable和新的hashtable。搬迁结束后，旧hashtable删除，新的取而代之。

![699ad253746df81c008ec19ed8317801.png][]

hashtable的结构和Java的HashMap几乎是一样的，都是通过分桶的方式来解决hash冲突的。第一维是数组，第二维是链表。而数组中存储的是第二维链表的第一个元素的指针。

![6fab9de7864bf74bc2e88965f9175455.png][]

# Set类型 #

Redis 的集合相当于 Java 语言中的 **HashSet**，它内部的键值对是无序、唯一的。它的内部实现相当于一个特殊的字典，字典中所有的 value 都是一个值 NULL。集合Set类型底层编码包括hashtable和inset。hashtable在上面介绍过了，我们就只介绍inset。

## inset的结构 ##

intset底层本质是一个有序的、不重复的、整型的数组、支持不同类型整数。

typedef struct intset {
        uint32_t encoding;
        uint32_t length;
        int8_t contents[];
    } intset;

（1）encoding 的值可以是以下三个常量的其中一个 ：

#define INTSET_ENC_INT16 (sizeof(int16_t))
    #define INTSET_ENC_INT32 (sizeof(int32_t))
    #define INTSET_ENC_INT64 (sizeof(int64_t))

（2）length就是数组的实际长度。

（3）contents 数组是实际保存元素的地方，数组中的元素有以下两个特性：

*  没有重复元素；
 *  元素在数组中从小到大排列；

**inset的查询**

intset是一个有序集合，查找元素的复杂度为O(logN)**（采用二分法）**，但插入时不一定为O(logN)，因为有可能涉及到升级操作。比如当集合里全是int16\_t型的整数，这时要插入一个int32\_t，那么为了维持集合中数据类型的一致，那么所有的数据都会被转换成int32\_t类型，涉及到内存的重新分配，这时插入的复杂度就为O(N)了。是intset不支持降级操作。

**补充**

这里需要注意的是，这里的说inset是有序不要和我们zset搞混，zset是设置一个score来进行排序，而inset这里只是单纯的对整数进行升序而已。

# Zset类型 #

Zset有序集合和set集合有着必然的联系，他保留了集合不能有重复成员的特性，但不同的是，有序集合中的元素是可以排序的，但是它和列表的使用索引下标作为排序依据不同的是，它给每个元素设置一个分数，作为排序的依据。 （有序集合中的元素不可以重复，但是csore可以重复，就和一个班里的同学学号不能重复，但考试成绩可以相同）。

简单来说，它类似于 Java 中 **SortedSet** 和 **HashMap** 的结合体，一方面它是一个 set，保证了内部 value 的唯一性，另一方面它可以为每个 value 赋予一个 score 值，用来代表排序的权重。

zet的底层编码有两种数据结构，一个ziplist，一个是skiplist。这里因为ziplis也做了排序，所以也要简单再介绍一下。

## ziplist排序 ##

我们之前也介绍过了ziplist，底层就是压缩列表。这里我们为了实现排序，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员（member），而第二个元素则保存元素的分值（score）。

压缩列表内的集合元素按分值从小到大进行排序，分值较小的元素被放置在靠近表头的方向，而分值较大的元素则被放在靠近表尾的方向。可以参考示意图如下。

[![5455eccbc00cc5bb06a70d4ea1a84e31.png][]][5455eccbc00cc5bb06a70d4ea1a84e31.png 1]

## skiplist跳表 ##

关于skiplist比较复杂，这里我只简单介绍一下，具体可以参考这篇文章，可以全面了解这个数据结构。[点击跳转][Link 1]

skiplist是与dict结合使用的，结构如下：

/*
     * 跳跃表
     */
    typedef struct zskiplist {
        // 头节点，尾节点
        struct zskiplistNode *header, *tail;
        // 节点数量
        unsigned long length;
        // 目前表内节点的最大层数
        int level;
    } zskiplist;
    /* ZSETs use a specialized version of Skiplists */
    /*
     * 跳跃表节点
     */
    typedef struct zskiplistNode {
        // member 对象
        robj *obj;
        // 分值
        double score;
        // 后退指针
        struct zskiplistNode *backward;
        // 层
        struct zskiplistLevel {
            // 前进指针
            struct zskiplistNode *forward;
            // 这个层跨越的节点数量
            unsigned int span;
        } level[];
    } zskiplistNode;

head和tail分别指向头节点和尾节点，然后每个skiplistNode里面的结构又是分层的(即level数组)。每一列都代表一个节点，保存了member和score，按score从小到大排序。每个节点有不同的层数，这个层数是在生成节点的时候随机生成的数值。每一层都是一个指向后面某个节点的指针。这种结构使得跳跃表可以跨越很多节点来快速访问。**（前进可以跳跃式的跳过几个节点，而后退只能后退一个节点，可以看看下面示意图可比较容易理解）。**

![f6ada7cc65b97671cbf3f8d3f27e7a30.png][]

**为什么不使用平衡树，而使用跳跃表？**

这里redis的设计者antirez也给出了原因，主要是从内存占用、对范围查找、实现难易程度来考虑的。

（1）在做范围查找的时候，平衡树比skiplist操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。

（2）平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。

（3）从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。

**为什么要使用skiplist与dict结合使用呢？**

这里需要我们去思考一下，为什么我们要两个混合着使用呢？

其实呢，我们可以分析一下就知道了。首先是我们的跳跃表，可以跨过多个节点进行查询，时间复杂度是O(lgn)左右，但是可以保持有序性。我们的dict是用hashtable实现，因为是哈希，所以查询是O(1)的大小，但是是无序性。

而我们使用两者混合，在进行分数索引的时候查询使用跳跃表，进行数据索引查找的时候，可以使用哈希的O(1)查找。设想如果没有字典, 如果想按数据查分数, 就必须进行遍历O(logn)。两套底层数据结构均只作为索引使用, 即不直接持有数据本身.。数据被封装在SDS中, 由跳跃表与字典共同持有，而数据的分数则由跳跃表结点直接持有(double类型数据), 由字典间接持有。

参考：

[https://www.cnblogs.com/CryFace/p/13762241.html][https_www.cnblogs.com_CryFace_p_13762241.html]

[https://blog.csdn.net/xpsallwell/article/details/84030285][https_blog.csdn.net_xpsallwell_article_details_84030285]

[https://www.cnblogs.com/yangmingxianshen/p/8054094.html][https_www.cnblogs.com_yangmingxianshen_p_8054094.html]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvYm96YWk4Ng_size_16_color_FFFFFF_t_70]: /images/20221119/f905be489dde44d780d8676cf03f5893.png
[e0b7afa6136c80a5f660b712c80a4a56.png]: /images/20221119/bed6367f3c5b4ce5843324071f2ce58d.png
[adf9f00a42df50570a3bcd418c9716d8.png]: https://img-blog.csdnimg.cn/img_convert/adf9f00a42df50570a3bcd418c9716d8.png
[4deec5780def48c7112e825da2a5118a.png]: https://img-blog.csdnimg.cn/img_convert/4deec5780def48c7112e825da2a5118a.png
[e16a2e02cccc2ac0cf4195cfeb0e5bf3.png]: https://img-blog.csdnimg.cn/img_convert/e16a2e02cccc2ac0cf4195cfeb0e5bf3.png
[699ad253746df81c008ec19ed8317801.png]: https://img-blog.csdnimg.cn/img_convert/699ad253746df81c008ec19ed8317801.png
[6fab9de7864bf74bc2e88965f9175455.png]: https://img-blog.csdnimg.cn/img_convert/6fab9de7864bf74bc2e88965f9175455.png
[5455eccbc00cc5bb06a70d4ea1a84e31.png]: https://img-blog.csdnimg.cn/img_convert/5455eccbc00cc5bb06a70d4ea1a84e31.png
[5455eccbc00cc5bb06a70d4ea1a84e31.png 1]: https://img2020.cnblogs.com/blog/1993240/202010/1993240-20201002160252776-1435470436.png
[Link 1]: https://github.com/linmuhan/JavaGuide/blob/master/docs/database/Redis/redis-collection/Redis%282%29%E2%80%94%E2%80%94%E8%B7%B3%E8%B7%83%E8%A1%A8.md
[f6ada7cc65b97671cbf3f8d3f27e7a30.png]: https://img-blog.csdnimg.cn/img_convert/f6ada7cc65b97671cbf3f8d3f27e7a30.png
[https_www.cnblogs.com_CryFace_p_13762241.html]: https://www.cnblogs.com/CryFace/p/13762241.html
[https_blog.csdn.net_xpsallwell_article_details_84030285]: https://blog.csdn.net/xpsallwell/article/details/84030285
[https_www.cnblogs.com_yangmingxianshen_p_8054094.html]: https://www.cnblogs.com/yangmingxianshen/p/8054094.html