Redis快速表、压缩表和双向链表(重点介绍quicklist)

前言

最近在看《Redis的设计与实现》这本书，写的真的是太好了，一下子就看入迷了，谢谢作者。不过在学习的时候发现一个问题，我服务器上安装的是Redis5.0.9版本的，而作者介绍的是Redis3.0版本的，在第一部分将数据结构与对象章节的时候，出现了一些差别，就是在redis对外暴露的list结构底层使用的数据结构问题。由于书上没有记录，所以就在网上查阅了些资料学习了一下， 自己再做个总结，当做自己的笔记。

差别

出现的差别就是，在redis3.2版本之前，它使用的是ziplist和linkedlist编码作为列表键的底层实现，在它之后，就采用了一个叫做quicklist的数据结构来作其底层实现。
先来介绍下redis3.2之前的版本的知识点：
在使用ziplist和linkedlist作为列表键底层实现的时候，他们之间会有一个选择标准：
选择ziplist的时候：

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

上面的是选择ziplist作为底层实现所必须满足的条件，如果没满足的话就选用linkedlist作为其底层实现。

127.0.0.1:6379> rpush blah "hello" "world" "again"
3
127.0.0.1:6379> object encoding blah
ziplist
127.0.0.1:6379> rpush blah "wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww"
4
127.0.0.1:6379> object encoding blah
linkedlist

再来介绍下redis3.2之后的版本：

这个涉及到quicklist这个数据结构了，书上没有记录，所以我查了下资料，也总结到自己的博客当中。

我安装的时候redis5.0.9版本的，所以上面的几个指令执行的结果会有所不同

127.0.0.1:6379> rpush blah "hello" "world" "again"
3
127.0.0.1:6379> object encoding blah
quicklist
127.0.0.1:6379> rpush blah "wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww"
4
127.0.0.1:6379> object encoding blah
quicklist

quicklist数据结构的介绍

ziplist和linkedlist就不介绍了，书本上有，我们来看看quicklist。
quicklist其实现也是依赖于ziplist和linkedlist来实现的，它是两个结构的结合。它将ziplist来进行分段存储，也就是分成一个个的quicklistNode节点来进行存储。每个quicklistNode指向一个ziplist，然后quicklistNode之间是通过双向指针来进行连接的。我们来看下大致的结构：

看到这个结构可能会有些疑问：

• 这个结构啥意思啊，为什么有的节点是ziplist，有的是quicklistZF？
• 为什么quicklist头部和尾部各有两个节点是ziplist，剩下中间的是quicklistZF？
• 为什么每个quicklistNode节点的ziplist内部的数据个数不一致呢？

为什么要把底层数据结构优化成quicklist？

在解决上面的问题之前我们先来解决一个首要的问题，也就是redis为什么要把列表键的底层数据结构优化成quicklist？
其实可以从两个方面来考虑这个原因：

• ziplist这个结构，它内部的数据存储是一段连续的空间，这样的话，就要求很大一块内存空间。就比如说，我们想存储很多的数据，但是内存中并没有符合要求的连续的存储空间，而是存在很多不连续的小空间（加起来可以符合要求）。
• 再来说说linkedlist这个结构，它数据存储不要求连续，就可以避免上面的弊端，不过这样以来，每个节点都分配一个一块内存，那就有可能造成大量的内存碎片。

综上两个考虑，redis在3.2版本以后就对此情况进行了优化，就出来了quicklist这个数据结构，quicklist其实就是一个分段的ziplist，为什么这么说呢？其实quicklist存储数据基本单位是quicklistNode，每个quicklistNode的内容区就是以ziplist数据结构存储的。也就是上面图示展示的。

为什么每个quicklistNode节点的ziplist内部的数据个数不一致呢？

现在转化到quicklist了，但是还需要考虑，quicklistNode里的ziplist里的内容处理呢？一个ziplist我需要存储多少个数据呀？也跟上面两个点考虑的一样

• 如果ziplist里的内容分配的越少的话，也就是往linkedlist方向发展了，就可能会产生很多的内存碎片
• 但要如果ziplist里的内容分配的越多的话，也会出现问题，就是需要很大一块连续的内存空间。

redis设计者已经给我们想好了，它的配置文件里有这样一个参数：list-max-ziplist-size

看到这个配置，我们来解释下这个参数，它既可以设置正数，也可以设置负数

当它取正数的时候，表示按照数据项个数来限定quicklist节点上的ziplist长度，比如我们设置为4，就说明每个ziplist的数据项最多不能超过5个

当它取负数的时候，表示按照占用字节来限定quicklsit节点上的ziplist长度，这时，它只能取-1到-5这五个值，每个值的含义如下：
1)、-5：每个quicklist节点上的ziplist大小不能超过64kb。（1kb == 1024 byte）
2)、-4：每个quicklsit节点上的ziplist大小不能超过32kb。
3)、-3：每个quicklsit节点上的ziplist大小不能超过16kb。
4)、-2：每个quicklsit节点上的ziplist大小不能超过8kb。
5)、-1：每个quicklsit节点上的ziplist大小不能超过4kb。

所以就会出现问题所说的，ziplist内存存储数据个数不一致的问题，我们也可以自己手动设置参数值。

这个结构啥意思啊，为什么有的节点是ziplist，有的是quicklistZF？

这里又出现了一个配置参数：list-compress-depth
其实，当链表很长的时候，最频繁访问的就是两端的数据，中间被访问的频率比较低，所以我们可以将中间部分节点进行压缩，从而能够进一步节省空间。上面说的list-compress-depth就是来设置这个的。
这个参数的取值含义如下：

0：是个特殊值，表示都不压缩。这是redis的默认值

1：表示quicklist两端各有一个节点不被压缩，中间节点进行压缩

2：表示quicklist两端各有两个节点不被压缩，中间节点进行压缩

3：表示quicklist两端各有三个节点不被压缩，中间节点进行压缩…

以此类推

也就是会出现问题所说的，两端节点为ziplist，中间节点为quicklistZF

我们看看上面的redis配置文件的默认配置。

简单了解源码结构

我通过上面这个图来简单说一下quicklist的存储方式，它底层有两个结构，一个quicklist，一个就是quicklistNode。下面是我找的源码，可以简单看下。

typedef struct quicklistNode {
  struct quicklistNode *prev;
  struct quicklistNode *next;
  unsigned char *zl;
  unsigned int sz;       /* ziplist size in bytes */
  unsigned int count : 16;   /* count of items in ziplist */
  unsigned int encoding : 2;  /* RAW==1 or LZF==2 */
  unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */
  unsigned int recompress : 1; /* was this node previous compressed? */
  unsigned int attempted_compress : 1; /* node can't compress; too small */
  unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

typedef struct quicklistLZF {
  unsigned int sz; /* LZF size in bytes*/
  char compressed[];
} quicklistLZF;

typedef struct quicklist {
  quicklistNode *head;
  quicklistNode *tail;
  unsigned long count; /* total count of all entries in all ziplists */
  unsigned int len; /* number of quicklistNodes */
  int fill : 16; /* fill factor for individual nodes */
  unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

quicklist的主要作用就是来指向节点的头和尾

总结

总的来说quicklist就是对ziplist和linkedlist两者优点的结合，来进一步优化redis的列表键底层存储。

到此这篇关于Redis快速表、压缩表和双向链表(重点介绍quicklist)的文章就介绍到这了,更多相关Redis快速表、压缩表和双向链表内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞！