Redis数据结构：List

Redis 中的 list 是类似于双端队列的一种实现，其底层的数据结构涉及到 linkedlist、ziplist、quicklist 和 listpack 的演进

linkedlist

redis 中的 linkedlist 是双链表，这也是我们实现 list 时首先想到的数据结构之一。redis 中的双链表并没有非常特殊的地方，我们来简单看下对应的代码实现即可

typedef struct list {
    listNode *head;//头指针
    listNode *tail;//尾指针
    void *(*dup)(void *ptr);//节点复制函数
    void (*free)(void *ptr);//节点释放函数
    int (*match)(void *ptr, void *key);//节点值是否相等
    unsigned long len;//链表节点数量
} list;

typedef struct listNode {
    struct listNode *prev;//前驱节点
    struct listNode *next;//后继节点
    void *value;//值
} listNode;

我们可以发现，双链表是一种非常标准的结构，链表维护首尾节点指针，维护长度，还和维护必要的工具函数指针地址，链表节点维护前驱、后继节点以及对应的值，正常来讲这套结构没有问题，但挑剔一点的话，它会有两个问题：

1. 当数据较小的情况下，数据结构维护的额外信息比数据本身还要占内存
2. 链表这种结构一个特点是内存不连续的，在遍历时效率较低

为了解决张两点，Redis 创造了 ziplist

ziplist

针对我们上面提到的两个问题，对应的解决思路就是结构简单+内存连续，而 ziplist 正是这样一种结构。

ziplist 首先是一块连续的内存，然后按一定的规范维护了简单的节点结构，如下图所示

ziplist 各组成部分功能为：

• zlbytes：ziplist 占用的总字节数
• zltail：尾结点的偏移量
• zllen：维护的节点数
• entries：节点信息
  • prelen：前一个节点占用的字节数。根据前一个节点的大小不同，会有两种表示方式
    • 当前一个节点字节数小于 254 时（即 11111110），prelen 用 1 字节表示
    • 当前一个节点字节数大于等于 254 时，prelen 用 5 字节表示，第一字节恒为 11111110，后面四个字节用于表示真实字节数
  • encoding：用于表示当前 entry 的类型和长度
    • 前两位表示类型，11 表示 int 型数据，其余表示字符串
  • entry-data：节点数据，特殊的，当 entry 中存储的是 int 类型时，entry-data 会合并到 encoding 中，此时就没有 entry-data 这部分
• zlend：结尾特殊字节，恒为 255，即 11111111

我们看到 ziplist 节点没有维护首尾指针，又针对不同情况实现各种变长存储，为了应对变长存储下的变量，维护了一个 prelen 字段，可以理解为用时间换了部分空间，在数据量小的情况下会有不错表现，但是它有个注明的缺点：连锁更新

我们现在知道，对于节点序列 ABC，节点 A 的长度可能会影响到节点 B 的 prelen 的长度，而节点 B 的 prelen 字段长度变更会导致节点 B 整体长度变更，这就有可能触发节点 C 遇到类似的情况，所以在极端场景下，一个节点数据的变更可能会引发后续节点的连锁反应，这就是 ziplist 的连锁更新。

为了解决连锁更新的问题，redis 又造了一个新的结构：quicklist

quicklist

todo

listpack

todo