REDIS_QUICKLIST

quickList(快速列表)是Redis对List对象的一个实践。

在 Redis 3.0 之前，List 对象的底层数据结构是双向listNode或者zipList。

在 Redis 3.2 更新中，List 对象的底层改由 quickList 实现。

前文提到，zipList当元素个数比较多时，每当修改元素时，必须重新分配存储空间，对执行效率影响很大。

quickList本质上是listNode+zipList的组合，quickList的顶层设计就是一个链表，链表的每个节点就是一个zipList。

从源码分析结构

// QuickList顶层链表
typedef struct quicklist {
    // 链表头
    quicklistNode *head;
    // 链表尾
    quicklistNode *tail; 
    // 所有zipList总元素个数
    unsigned long count;
    // node个数
    unsigned long len;       
    ...
} quicklist;

// QuickList节点设计
typedef struct quicklistNode {
    // 前指针
    struct quicklistNode *prev;
    // 后指针
    struct quicklistNode *next;
    // 该节点所指向的zipList指针
    unsigned char *zl;              
    // zipList的的字节大小
    unsigned int sz;                
    // zipList的元素个数
    unsigned int count : 16;        //ziplist中的元素个数 
    ....
} quicklistNode;

用图表达：

在向 quicklist 添加一个元素的时候，会先检查插入位置的压缩列表是否能容纳该元素，如果能容纳就直接保存到 quicklistNode 结构里的压缩列表，如果不能容纳，才会新建一个新的 quicklistNode 结构。

quicklist 会控制 quicklistNode 结构里的压缩列表的大小或者元素个数，来规避潜在的连锁更新的风险，但是这并没有完全解决连锁更新的问题。

REDIS_LISTPACK

Redis在5.0设计了一个新的数据结构：listPack，用于替代zipList。

它最大特点是 listpack 中每个 entry 不再包含前一个节点的长度。

zipList正因需要保存前一个节点的长度字段，才导致了连锁更新的隐患。

在Redis7.0版本中已经用listPack重构。

结构设计

在每个Entry中，又包含如下结构：

• encoding用于定义该元素的编码类型，会对不同长度的整数和字符串进行编码；
• data存放实际数据；
• len代表encoding+data的总长度；

listPack之于zipList最大的改变就是不再记录前一个节点的字段长度，这样无论节点如何变化，每个节点都不再因为其他节点的更新而连锁更新。

listPack如何逆向遍历

uint64_t lpDecodeBacklen(unsigned char *p) {
    uint64_t val = 0;
    uint64_t shift = 0;
    do {
        val |= (uint64_t)(p[0] & 127) << shift;
        if (!(p[0] & 128)) break;
        shift += 7;
        p--;
        if (shift > 28) return UINT64_MAX;
    } while(1);
    return val;
}

从当前列表项起始位置的指针开始，向左逐个字节解析，得到前一项的 entry-len 值。