Redis - 跳跃表，压缩列表，quicklist

傷城~ 2022-12-19 09:29 101阅读 0赞

### 文章目录 ###

*  1. 跳跃表
 *  2. 跳跃表的结构
 *  3. 压缩列表
 *   *  连锁更新
 *  4. quicklist
 *   *  数据压缩

# 1. 跳跃表 #

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。跳跃表支持平均O（logN）、最坏O（N）复杂度的节点查找，还可以通过顺序性操作来批量处理节点。

在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单。

**Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员（member）是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。**

Redis只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构，除此之外，跳跃表在Redis里面没有其他用途。

--------------------

Redis的配置文件中关于有序集合底层实现的两个配置。  
1）zset-max-ziplist-entries 128:zset采用压缩列表时，元素个数最大值。默认值为128。  
2）zset-max-ziplist-value 64:zset采用压缩列表时，每个元素的字符串长度最大值。默认值为64。  
zset插入第一个元素时，会判断下面两种条件：

*  zset-max-ziplist-entries的值是否等于0；
 *  zset-max-ziplist-value小于要插入元素的字符串长度。满足任一条件Redis就会采用跳跃表作为底层实现，否则采用压缩列表作为底层实现方式。

一般情况下，不会将zset-max-ziplist-entries配置成0，元素的字符串长度也不会太长，所以在创建有序集合时，默认使用压缩列表的底层实现。zset新插入元素时，会判断以下两种条件：

*  zset中元素个数大于zset\_max\_ziplist\_entries；
 *  插入元素的字符串长度大于zset\_max\_ziplist\_value。当满足任一条件时，Redis便会将zset的底层实现由压缩列表转为跳跃表。

> zset在转为跳跃表之后，即使元素被逐渐删除，也不会重新转为压缩列表。

# 2. 跳跃表的结构 #

其c语言代码如下：

typedef struct zskiplistNode { 
    	//成员对象
        robj *obj;
        double score;//分值
        struct zskiplistNode *backward;//回退指针
        //层
        struct zskiplistLevel { 
        	//前进指针
            struct zskiplistNode *forward;
            //跨度
            unsigned int span;
        } level[];
    } zskiplistNode;

1）obj：用于存储字符串类型的数据。  
2）score：用于存储排序的分值。  
3）backward：后退指针，只能指向当前节点最底层的前一个节点，头节点和第一个节点——backward指向NULL，从后向前遍历跳跃表时使用。  
4）level：为柔性数组。每个节点的数组长度不一样，在生成跳跃表节点时，随机生成一个1～64的值，值越大出现的概率越低。  
level数组的每项包含以下两个元素。

*  forward：指向本层下一个节点，尾节点的forward指向NULL。
 *  span:forward指向的节点与本节点之间的元素个数。span值越大，跳过的节点个数越多。

除了跳跃表节点外，还需要一个跳跃表结构来管理节点，Redis使用zskiplist结构体，定义如下：

typedef struct zskiplist { 
        struct zskiplistNode *header, *tail;
        unsigned long length;
        int level;
    } zskiplist;

1）header：指向跳跃表头节点。头节点是跳跃表的一个特殊节点，它的level数组元素个数为64。头节点在有序集合中不存储任何member和score值，ele值为NULL, score值为0；也不计入跳跃表的总长度。头节点在初始化时，64个元素的forward都指向NULL, span值都为0。  
2）tail：指向跳跃表尾节点。  
3）length：跳跃表长度，表示除头节点之外的节点总数。  
4）level：跳跃表的高度。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70_pic_center]

> 查找从最高层开始，如果本层的next节点大于要查找的值或next节点为NULL，则从本节点开始，降低一层继续向后查找，依次类推，如果找到则返回节点；否则返回NULL。采用该原理查找节点，在节点数量比较多时，可以跳过一些节点，查询效率大大提升，这就是跳跃表的基本思想。

1）跳跃表由很多层构成。  
2）跳跃表有一个头（header）节点，头节点中有一个64层的结构，每层的结构包含指向本层的下个节点的指针，指向本层下个节点中间所跨越的节点个数为本层的跨度（span）。  
3）除头节点外，层数最多的节点的层高为跳跃表的高度（level）  
4）每层都是一个有序链表，数据递增。  
5）除header节点外，一个元素在上层有序链表中出现，则它一定会在下层有序链表中出现。  
6）跳跃表每层最后一个节点指向NULL，表示本层有序链表的结束。  
7）跳跃表拥有一个tail指针，指向跳跃表最后一个节点。  
8）最底层的有序链表包含所有节点，最底层的节点个数为跳跃表的长度（length）（不包括头节点）。  
9）每个节点包含一个后退指针，头节点和第一个节点指向NULL；其他节点指向最底层的前一个节点。

> Redis通过zslRandomLevel函数随机生成一个1～64的值作为新建节点的高度

# 3. 压缩列表 #

压缩列表ziplist本质上就是一个字节数组，是Redis为了节约内存而设计的一种线性数据结构，可以包含多个元素，每个元素可以是一个字节数组或一个整数。

> Redis的有序集合、散列和列表都直接或者间接使用了压缩列表。当有序集合或散列表的元素个数比较少，且元素都是短字符串时，Redis便使用压缩列表作为其底层数据存储结构。列表使用快速链表（quicklist）数据结构存储，而快速链表就是双向链表与压缩列表的组合。

一个压缩列表可以包含任意多个节点（entry），**每个节点可以保存一个字节数组或者一个整数值。**  
![在这里插入图片描述][20201106202154824.png_pic_center]  
1）zlbytes：压缩列表的字节长度，占4个字节，因此压缩列表最多有232-1个字节。  
2）zltail：压缩列表尾元素相对于压缩列表起始地址的偏移量，占4个字节。3）zllen：压缩列表的元素个数，占2个字节。zllen无法存储元素个数超过65535（216-1）的压缩列表，必须遍历整个压缩列表才能获取到元素个数。4）entryX：压缩列表存储的元素，可以是字节数组或者整数，长度不限。entry的编码结构将在后面详细介绍。  
5）zlend：压缩列表的结尾，占1个字节，恒为0xFF。

而压缩列表元素(entry)的编码结构：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70_pic_center 1]

*  previous\_entry\_length字段表示前一个元素的字节长度  
    占1个或者5个字节，当前一个元素的长度小于254字节时，用1个字节表示；当前一个元素的长度大于或等于254字节时，用5个字节来表示。
 *  encoding字段表示当前元素的编码
 *  数据内容存储在content字段

其中包含了很多复杂的解码运算，想详细了解的可以找对应的书来看。

## 连锁更新 ##

每个节点的previous\_entry\_length属性都记录了前一个节点的长度，添加新节点可能会引发连锁更新之外，删除节点也可能会引发连锁更新。  
因为某个可能的结点previous\_entry\_length属性仅长1字节，它没办法保存新节点new的长度，所以程序将对压缩列表执行空间重分配操作，并将则个节点的previous\_entry\_length属性从原来的1字节长扩展为5字节长。进而引发后面的连锁更新。  
其最坏复杂度是O（N 2）。

尽管连锁更新的复杂度较高，但它真正造成性能问题的几率是很低的：

*  压缩列表里要恰好有多个连续的、长度介于250字节至253字节之间的节点，连锁更新才有可能被引发，在实际中，这种情况并不多见；
 *  即使出现连锁更新，但只要被更新的节点数量不多，就不会对性能造成任何影响：比如说，对三五个节点进行连锁更新是绝对不会影响性能的；

# 4. quicklist #

quicklist是Redis底层最重要的数据结构之一，它是Redis对外提供的6种基本数据结构中List的底层实现，在Redis 3.2版本中引入。

在引入quicklist之前，Redis采用压缩链表（ziplist）以及双向链表（adlist）作为List的底层实现。当元素个数比较少并且元素长度比较小时，Redis采用ziplist作为其底层存储；当任意一个条件不满足时，Redis采用adlist作为底层存储结构。

这么做的主要原因是，当元素长度较小时，采用ziplist可以有效节省存储空间，但ziplist的存储空间是连续的，当元素个数比较多时，修改元素时，必须重新分配存储空间，这无疑会影响Redis的执行效率，故而采用一般的双向链表。

结构如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70_pic_center 2]  
c语言代码如下:

typedef struct quicklist{ 
    	quicklistNode *head;
    	quicklistNode *tail;
    	unsigned long count;//quicklist中元素总数
    	unsigned long len;//quicklist Node（节点）个数
    	int fill : 16;//每个quicklistNode中ziplist长度
    }quicklist;

typedef struct quicklistNode{ 
    	struct quicklistNode *prev;
    	struct quicklistNode *next;
    	unsigned char *zl;//zl指向该节点对应的ziplist结构；
    	unsigned int sz;//整个ziplist结构的大小
    	unsigned int count:16;//ziplist的个数
    	unsigned int coding：2;//1代表是原生的，2代表使用LZF进行压缩；
    	unsigned int containnr：2;//container为quicklistNode节点zl指向的容器类型：1代表none,2代表使用ziplist存储数据；
    	unsigned int recompress:1;//recompress代表这个节点之前是否是压缩节点
    	unsigned int extra:10;//extra为预留
    }quicklistNode;

## 数据压缩 ##

quicklist每个节点的实际数据存储结构为ziplist，这种结构的主要优势在于节省存储空间。为了进一步降低ziplist所占用的空间，Redis允许对ziplist进一步压缩，Redis采用的压缩算法是LZF，压缩过后的数据可以分成多个片段，每个片段有2部分：一部分是解释字段，另一部分是存放具体的数据字段。  
解释字段可以占用1～3个字节，数据字段可能不存在。

typedef struct quicklistLZF{ 
    	unsigned int sz;//sz表示compressed所占字节大小
    	char compress[];
    }quicklistLZF;

解释字段有3种:  
1）字面型，解释字段占用1个字节，数据字段长度由解释字段后5位决定。  
2）简短重复型，解释字段占用2个字节，没有数据字段，数据内容与前面数据内容重复，重复长度小于8。  
3）批量重复型，解释字段占3个字节，没有数据字段，数据内容与前面内容重复。

压缩：  
数据与前面重复的，记录重复位置以及重复长度，否则直接记录原始数据内容。压缩算法的流程如下：遍历输入字符串，对当前字符及其后面2个字符进行散列运算，如果在Hash表中找到曾经出现的记录，则计算重复字节的长度以及位置，反之直接输出数据。  
解压：  
可能存在重复数据与当前位置重叠的情况，例如在当前位置前的15个字节处，重复了20个字节，此时需要按位逐个复制。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/58da92a7928f4903a3d842ec41fd3a4f.png
[20201106202154824.png_pic_center]: /images/20221120/76fdd87ab32644df90f78af4e80da1da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/f1f3bb693b3c4e5a865a35b80579fff7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/d539aa3149794e349dbb72b894b893d4.png