Redis数据结构

本文大部分知识整理自网上，在正文结束后都会附上参考地址。如果想要深入或者详细学习可以通过文末链接跳转学习。

前言

本文主要介绍关于Redis的五种基本数据结构的底层实现原理，然后来分析我们常用的使用场景。先简单回顾一下知识点。

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

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

结构模型介绍

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

总结一下

（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 结构）地址。

示意图如下：

String类型

关于string内部结构，上面也介绍了主要是以三种编码形式来组成的，分别是int，raw，embstr。这里int主要是用来存放整形值的字符串，embstr用来存放字符串的短字符串（大小不超过44个字节），raw存放字符的长字符串（大小不超过44个字节）。

SDS结构

我们在上面介绍了关于键的基本结构redisObject，但其实在我们的String中还用着另外一种结构，也就是我们的SDS结构（Simple Dynamic String 结构）。

从源码的文件里面可以看见，同样一组结构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就不易处理。

表格区别汇总如下。

raw与embstr的区别

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

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

String的应用场景

（1）缓存功能

字符串最经典的使用场景，redis最为缓存层，Mysql作为储存层，绝大部分请求数据都是 redis中获取，由于redis具有支撑高并发特性，所以缓存通常能起到加速读写和降低后端压力的作用。

（2）计数器

许多应用都会使用redis作为计数的基础工具，因为redis的INCR命令具有原子性的自增操作，在并发下也可以保证一个线程安全的问题。如果我们常见的论坛，网站的点赞数或者视频播放数就是使用redis作为计数的基础组件。

（3）共享session

出于负载均衡的考虑，分布式服务会将用户信息的访问均衡到不同服务器上，这样可能我们用户在第一次访问和第二次访问的时候不是同一台服务器的话，session不同步，就会导致重新登录。为避免这个问题可以使用redis将用户session集中管理。（示意图如下）

当客户端第一次发送请求后，nginx将这个请求分发给服务器实例M ，然后将服务器实例M 产生的Session 放入Redis中，此时客户端、服务器实例M 和Redis中都会有一个相同的Session，当客户端发送第二次请求的时候，nginx将请求分发给服务器实例N （已知服务器实例N 中无Session），因为客户端自己携带了一个Session，那么服务器实例N就可以拿着客户端带来的Session中的ID去Redis中找到Session，找到这个Session后，就能正常执行之后的操作。

（5）限流

我们的redis处于安全考虑或者在高并发访问，都会进行一个限流或者限速。比如防止某个接口被频繁调用而崩溃或者像手机验证码验证，防止短信接口不被频繁访问。

我们常见的限流算法有很多，如令牌桶，漏桶，计数器，滑动窗口等。而用String的话，就可以使用计数器，我们如果要设置一个一分钟最多只能访问100次的限流接口，只要设置键的一分钟过期时间就行，然后在一分钟之内通过计数器来进行计数。关于具体的限流算法，我后面会继续更新补充一下这一块的知识点。(点击跳转，待补充)

List类型

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

压缩列表

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

ziplist的结构表如下：

　　　　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之间使用双指针串接起来。

ziplist的长度

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

压缩深度

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

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

关于压缩具体介绍可以参考这里