关于redis:闲扯Redis五List数据类型底层之quicklist

39次阅读

共计 2475 个字符,预计需要花费 7 分钟才能阅读完成。

一、前言

Redis 提供了 5 种数据类型:String(字符串)、Hash(哈希)、List(列表)、Set(汇合)、Zset(有序汇合),了解每种数据类型的特点对于 redis 的开发和运维十分重要。

<p align=”right”> 原文解析 </p>

Redis 中的 list 是咱们常常应用到的一种数据类型,依据应用形式的不同,能够利用到很多场景中。

二、底层解析

1、上节回顾

 上节《闲扯 Redis 四》List 数据类型底层编码转换 说道,在 3.0 版本的 Redis 中,List 类型有两种实现形式:

1、应用压缩列表(ziplist)实现的列表对象。

2、应用双端链表(linkedlist)实现的列表对象。

在 3.2 版本后新增了 quicklist 数据结构实现了 list,当初就来剖析下 quicklist 的构造

2、官网形容

 先来看看 Redis 官网对 quicklist 的形容:

    A doubly linked list of ziplists

    A generic doubly linked quicklist implementation

 可见 quicklist 是一个双向链表,并且是一个 ziplist 的双向链表,也就是说 quicklist 的每个节点都是一个 ziplist。而通过后面的文章咱们能够晓得,ziplist 自身也是一个能维持数据项先后顺序的列表,而且数据项保留在一个间断的内存块中。那是不是意味着 quicklist 联合了压缩列表和双端链表的特点呢!

3、构造剖析

quicklist 构造定义

/* 
 * quicklist
 */
typedef struct quicklist {
    // 头结点
    quicklistNode *head; 
    // 尾节点
    quicklistNode *tail; 
    // 所有 ziplist 中 entry 数量
    unsigned long count; 
    //quicklistNodes 节点数量
    unsigned int len;   
    //ziplist 中 entry 能保留的数量, 由 list-max-ziplist-size 配置项管制 
    int fill : 16;       
    // 压缩深度, 由 list-compress-depth 配置项管制
    unsigned int compress : 16; 
} quicklist;

quicklist 构造属性正文

正文:

fill:ziplist 中 entry 能保留的数量, 由 list-max-ziplist-size 配置项管制

    示意了单个节点 (quicklistNode) 的负载比例(fill factor),正数限度 quicklistNode 中的 ziplist 的字节长度, 
    负数限度 quicklistNode 中的 ziplist 的最大长度。
-5: 最大存储空间: 64 Kb <-- 通常状况下不要设置这个值
-4: 最大存储空间: 32 Kb <-- 十分不举荐
-3: 最大存储空间: 16 Kb <-- 不举荐
-2: 最大存储空间: 8 Kb <-- 举荐
-1: 最大存储空间: 4 Kb <-- 举荐
对于正整数则示意最多能存储到你设置的那个值, 以后的节点就装满了
通常在 -2 (8 Kb size) 或 -1 (4 Kb size) 时, 性能体现最好

compress:压缩深度, 由 list-compress-depth 配置项管制

    示意 quicklist 中的节点 quicklistNode, 除开最两端的 compress 个节点之后, 两头的节点都会被压缩(LZF 压缩算法)。

quicklistNode 构造定义

typedef struct quicklistNode {
    // 前节点指针
    struct quicklistNode *prev; 
    // 后节点指针
    struct quicklistNode *next; 
    // 数据指针。以后节点的数据没有压缩,那么它指向一个 ziplist 构造;否则,它指向一个 quicklistLZF 构造。unsigned char *zl;
    //zl 指向的 ziplist 理论占用内存大小。须要留神的是:如果 ziplist 被压缩了,那么这个 sz 的值依然是压缩前的 ziplist 大小
    unsigned int sz;  
    //ziplist 外面蕴含的数据项个数
    unsigned int count : 16;   
    //ziplist 是否压缩。取值:1--ziplist,2--quicklistLZF 
    unsigned int encoding : 2; 
    // 存储类型,目前应用固定值 2 示意应用 ziplist 存储
    unsigned int container : 2; 
    // 当咱们应用相似 lindex 这样的命令查看了某一项原本压缩的数据时,须要把数据临时解压,这时就设置 recompress= 1 做一个标记,等有机会再把数据从新压缩
    unsigned int recompress : 1;
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

quicklistLZF 构造定义

typedef struct quicklistLZF {
    unsigned int sz;  // 压缩后的 ziplist 大小
    char compressed[];// 柔性数组,寄存压缩后的 ziplist 字节数组} quicklistLZF;

4、quicklist 结构图

 根据上述构造体定义,咱们能够绘制一下 quicklist 的构造:

三、要点总结

1、双端链表

1. 双端链表便于在表的两端进行 push 和 pop 操作,然而它的内存开销比拟大;

2. 双端链表每个节点上除了要保留数据之外,还要额定保留两个指针;

3. 双端链表的各个节点是独自的内存块,地址不间断,节点多了容易产生内存碎片;

2、压缩列表

1.ziplist 因为是一整块间断内存,所以存储效率很高;

2.ziplist 不利于批改操作,每次数据变动都会引发一次内存的 realloc;

3. 当 ziplist 长度很长的时候,一次 realloc 可能会导致大批量的数据拷贝,进一步升高性能;

3、quicklist

1. 空间效率和工夫效率的折中;

2. 联合了双端链表和压缩列表的长处;

正文完
 0