概述

Redis中的List是一个有序（按加入的时序排序）的数据结构，一般有序我们会采用数组或者是双向链表，其中双向链表由于有前后指针实际上会很浪费内存。3.2版本之前采用两种数据结构作为底层实现：

  • 压缩列表ziplist
  • 双向链表linkedlist

ziplist的结构

ziplist的数据结构及解释如下：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3sqBo573-1610531492142)(https://s3.ax1x.com/2021/01/10/s18atJ.png)]
ziplist的节点信息如下：

typedef struct zlentry {<!-- -->
    // prevrawlen ：前置节点的长度
    // prevrawlensize ：编码 prevrawlen 所需的字节大小,有1字节和5个字节两种。
    unsigned int prevrawlensize, prevrawlen;
    // len ：当前节点值的长度
    // lensize ：编码 len 所需的字节大小
    unsigned int lensize, len;
    // 当前节点 header 的大小
    // 等于 prevrawlensize + lensize
    unsigned int headersize;
    // 当前节点值所使用的编码类型
    unsigned char encoding;
    // 指向当前节点的指针
    unsigned char *p;
} zlentry;

返回一个zlenrty

static zlentry zipEntry(unsigned char *p) {<!-- -->
    zlentry e;
    // e.prevrawlensize 保存着编码前一个节点的长度所需的字节数
    // e.prevrawlen 保存着前一个节点的长度
    // T = O(1)
    ZIP_DECODE_PREVLEN(p, e.prevrawlensize, e.prevrawlen);
    // p + e.prevrawlensize 将指针移动到列表节点本身
    // e.encoding 保存着节点值的编码类型
    // e.lensize 保存着编码节点值长度所需的字节数
    // e.len 保存着节点值的长度
    // T = O(1)
    ZIP_DECODE_LENGTH(p + e.prevrawlensize, e.encoding, e.lensize, e.len);
    // 计算头结点的字节数
    e.headersize = e.prevrawlensize + e.lensize;
    // 记录指针
    e.p = p;
    return e;
}

ziplist的原理

ziplist是使用连续的内存块存储的：

  • zlbytes：表示整个ziplist占用的字节数，一般用于内存重分配或者计算列表尾端
  • zltail：到达列表最后一个节点的偏移量，方便直接找到尾部节点
  • zllen：列表节点的数量
  • entryX：列表中的各节点
  • zlend：作用就是用来标记列表尾端，占用一个字节

注意zllen用16个比特位存储，也就是说起长度最大表示65535，所以如果长度超过这个值，只能够通过节点遍历来确定列表元素数量

每个节点zlentry是如何存储的，完整的zlentry由以下几个部分组成：

  • prevrawlen： 记录前一个节点所占内存的字节数，方便查找上一个元素地址
  • unsigned int lensize, len： lensize表示编码 len 所需的字节大小，len表示当前节点值的长度
  • unsigned int headersize： 当前节点 header 的大小，等于 prevrawlensize + lensize
  • unsigned char encoding： 当前节点值所使用的编码类型

ziplist数据结构中prevrawlen是变长编码的，如果上一个节点长度小于254个字节，则只是用一个字节存储prevrawlen，如果大于等于254，那么第一个字节用254标记，后面四个字节表示上一个节点长度

ziplist 的优缺点

  • ziplist存储在一段连续的内存上，所以存储效率很高。但是，它不利于修改操作，插入和删除操作需要频繁的申请和释放内存。特别是当ziplist长度很长的时候，一次realloc可能会导致大批量的数据拷贝。
  • 双向链表linkedlist便于在表的两端进行push和pop操作，在插入节点上复杂度很低，但是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还要额外保存两个指针；其次，双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片。 ziplist 最大的确定就是连锁更新问题

因为在ziplist中，每个zlentry都存储着前一个节点所占的字节数，而这个数值又是变长编码的。假设存在一个压缩列表，其包含 e1、e2、e3、e4…，e1 节点的大小为 253 字节，那么 e2.prevrawlen 的大小为 1 字节，如果此时在 e2 与 e1 之间插入了一个新节点 e，e 编码后的整体长度（包含 e1 的长度）为 254 字节，此时 e2.prevrawlen 就需要扩充为 5 字节；如果 e2 的整体长度变化又引起了 e3.prevrawlen 的存储长度变化，那么 e3 也需要扩…如此递归直到表尾节点或者某一个节点的 prevrawlen 本身长度可以容纳前一个节点的变化。其中每一次扩充都需要进行空间再分配操作。删除节点亦是如此，只要引起了操作节点之后的节点的 prevrawlen 的变化，都可能引起连锁更新，引发内存 realloc。

连锁更新在最坏情况下需要进行 N 次空间再分配，而每次空间再分配的最坏时间复杂度为 O(N)，因此连锁更新的总体时间复杂度是 O(N^2)。

基于上述来看ziplist的缺点大于优点，所以3.2版本之后采用了另外一个数据结构为quicklist

应用场景

  • 压缩列表（ziplist）是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现。redis数据列表list操作，在列表中添加一个或多个值RPUSH:
redis> RPUSH lst 1 3 5 10086 "hello" "world"  
  (integer)6  
redis> OBJECT ENCODING lst  
  "ziplist"
  • 当一个哈希键只包含少量键值对，比且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做哈希键的底层实现。
redis> HMSET profile "name" "Jack" "age" 28 "job" "Programmer"  
  OK  
redis> OBJECT ENCODING profile  
  "ziplist"

哈希键里面包含的所有键和值都是小整数值或者短字符串

ps: 以上截图来自《Redis设计与实现一书》

--完--