Redis `ziplist` 压缩列表原理：小数据集合的内存极致优化

各位观众，各位朋友，欢迎来到今天的“Redis数据结构奇妙夜”！今天我们要聊的是Redis里一个非常低调但又极其重要的角色——ziplist，也就是压缩列表。

别看它名字里带“压缩”两个字就觉得它很复杂，其实啊，它就是Redis为了节省内存，对小数据集合进行极致优化的一种数据结构。简单来说，如果你的列表或者哈希只存几个小猫小狗，Redis就懒得给你动用重量级的链表或者哈希表了，直接用ziplist伺候着，省钱！

ziplist：小身材，大智慧

想象一下，你有一个小杂物间，里面就放了几件东西。如果专门为了这几件东西搭个钢筋混凝土的房间，是不是有点浪费？ziplist就相当于这个杂物间，它把数据紧凑地排列在一起，不搞多余的指针，能省一点是一点。

ziplist的结构

ziplist本质上就是一段连续的内存空间，里面存储着一系列的节点（entry）。它的结构可以用下图来简单概括（别嫌弃，这可是纯文字版架构图）：

<zlbytes> <zltail> <zllen> <entry1> <entry2> ... <entryN> <zlend>

咱们来逐个解释一下这些字段都是干嘛的：

• zlbytes (4 bytes): 整个ziplist占用的总字节数。这个字段方便我们直接计算出ziplist的末端地址，而不用遍历整个列表。

• zltail (4 bytes): ziplist尾节点（也就是最后一个entry）距离ziplist起始地址的偏移量。有了这个偏移量，我们就可以直接定位到尾节点，而不用从头开始遍历。这对于从尾部进行操作（比如rpush）非常有用。

• zllen (2 bytes): ziplist中entry的数量。但是，当entry的数量超过65535 (2^16 – 1) 时，zllen的值会被设置为65535，并且需要遍历整个ziplist才能知道真实的entry数量。所以，ziplist不适合存储过多的元素。

• entry1, entry2, …, entryN: 实际存储数据的节点。每个entry的结构比较复杂，后面会详细讲解。

• zlend (1 byte): 特殊值0xFF (255)，用于标记ziplist的末端。

entry的秘密

entry是ziplist的核心，它存储着实际的数据。entry的结构也比较特殊，它包含以下几个部分：

• prevlen (1 or 5 bytes): 前一个entry的长度。这个字段用于实现从后向前遍历ziplist。如果前一个entry的长度小于254字节，那么prevlen只需要1个字节来存储；否则，需要5个字节来存储，并且第一个字节会被设置为0xFE (254)，后面的4个字节存储实际的长度。

• encoding (1, 2 or 5 bytes): 当前entry存储的数据的编码方式。encoding字段决定了后面data字段的类型和长度。

• data (variable length): 实际存储的数据。数据的类型和长度由encoding字段决定。

encoding的奥秘

encoding字段是entry结构中最复杂的部分，它决定了如何解释data字段。encoding字段可以分为两大类：

• 字符串编码: 表示data字段存储的是字符串。
• 整数编码: 表示data字段存储的是整数。

字符串编码的格式如下：

• 00pppppp (1 byte): 长度小于等于63 (2^6 – 1) 字节的字符串。pppppp表示字符串的长度。
• 01pppppp qqqqqqqq (2 bytes): 长度小于等于16383 (2^14 – 1) 字节的字符串。ppppppqqqqqqqq表示字符串的长度。
• 10000000 aaaaaaaa bbbbbbbb cccccccc dddddddd (5 bytes): 长度大于等于16384字节的字符串。后面的4个字节 aaaaaaaa bbbbbbbb cccccccc dddddddd 表示字符串的长度。

整数编码的格式如下：

• 11000000 (1 byte): data字段存储的是int16类型的整数。
• 11010000 (1 byte): data字段存储的是int32类型的整数。
• 11100000 (1 byte): data字段存储的是int64类型的整数。
• 11110000 (1 byte): data字段存储的是24位有符号整数。
• 11111111 (1 byte): data字段存储的是8位有符号整数。
• 1111xxxx (1 byte): xxxx的范围是1-13，表示data字段存储的是0-12的整数。注意，这里直接把整数存储在encoding字段里，而不需要额外的data字段。

代码示例

为了让大家更直观地理解ziplist的结构，我们来模拟一下ziplist的创建和插入操作（以下代码仅为演示原理，不代表Redis源码）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

// 定义一些常量
#define ZIP_END 255 // ziplist 结尾标志
#define ZIP_INT_IMM_MIN 0xf1    /* 11110001 */
#define ZIP_INT_IMM_MAX 0xfd    /* 11111101 */
#define ZIP_INT_IMM_MASK 0x0f   /* Mask to extract the 4 bits value. Usefull for small integers */

// 模拟 ziplist 结构
typedef struct {
    unsigned int zlbytes;  // ziplist 占用的总字节数
    unsigned int zltail;   // 尾节点偏移量
    unsigned short zllen;  // entry 的数量
    unsigned char *data;   // 实际存储数据的指针
} ziplist;

// 创建一个新的 ziplist
ziplist *ziplistNew() {
    ziplist *zl = malloc(sizeof(ziplist));
    if (!zl) return NULL;

    zl->zlbytes = 4 + 4 + 2 + 1; // zlbytes, zltail, zllen, zlend
    zl->zltail = 4 + 4 + 2;
    zl->zllen = 0;
    zl->data = malloc(zl->zlbytes);
    if (!zl->data) {
        free(zl);
        return NULL;
    }
    zl->data[zl->zlbytes - 1] = ZIP_END; // 设置结尾标志

    return zl;
}

// 计算存储字符串所需的字节数
int zipStoreStrLen(unsigned char *buf, unsigned int len) {
    if (len <= 63) {
        if (buf) buf[0] = len | 0x00;
        return 1;
    } else if (len <= 16383) {
        if (buf) {
            buf[0] = (len >> 8) | 0x40;
            buf[1] = len & 0xff;
        }
        return 2;
    } else {
        if (buf) {
            buf[0] = 0x80;
            buf[1] = (len >> 24) & 0xff;
            buf[2] = (len >> 16) & 0xff;
            buf[3] = (len >> 8) & 0xff;
            buf[4] = len & 0xff;
        }
        return 5;
    }
}

// 计算存储整数所需的字节数
int zipStoreInt(unsigned char *buf, long long value) {
    if (value >= 0 && value <= 12) {
        if (buf) buf[0] = ZIP_INT_IMM_MIN + value;
        return 1;
    } else if (value >= INT8_MIN && value <= INT8_MAX) {
        if (buf) {
            buf[0] = 0xff;
            *(int8_t *)(buf + 1) = value;
        }
        return 2;
    } else if (value >= INT16_MIN && value <= INT16_MAX) {
        if (buf) {
            buf[0] = 0xc0;
            *(int16_t *)(buf + 1) = value;
        }
        return 3;
    } else if (value >= INT32_MIN && value <= INT32_MAX) {
        if (buf) {
            buf[0] = 0xd0;
            *(int32_t *)(buf + 1) = value;
        }
        return 5;
    } else {
        if (buf) {
            buf[0] = 0xe0;
            *(int64_t *)(buf + 1) = value;
        }
        return 9;
    }
}

// 获取存储字符串所需的字节数
int zipEncodedStrLen(unsigned char *p, unsigned int *len) {
    unsigned char encoding = p[0];

    if (encoding < 0x40) {
        *len = encoding & 0x3f;
        return 1;
    } else if (encoding < 0x80) {
        *len = ((encoding & 0x3f) << 8) | p[1];
        return 2;
    } else {
        *len = (p[1] << 24) | (p[2] << 16) | (p[3] << 8) | p[4];
        return 5;
    }
}

// 插入一个字符串到 ziplist
ziplist *ziplistPush(ziplist *zl, unsigned char *s, unsigned int slen) {
    unsigned int prevlen = 0;
    unsigned int prevlenBytes = 0;
    unsigned int encodingBytes = 0;
    unsigned int dataBytes = slen;

    // 计算前一个 entry 的长度
    if (zl->zllen > 0) {
        unsigned char *p = zl->data + zl->zltail;
        prevlenBytes = zipEncodedStrLen(p, &prevlen);
    }

    // 计算存储字符串长度所需的字节数
    encodingBytes = zipStoreStrLen(NULL, slen);

    // 计算新 entry 所需的总字节数
    unsigned int required = prevlenBytes + encodingBytes + dataBytes;

    // 重新分配内存
    zl->data = realloc(zl->data, zl->zlbytes + required);
    if (!zl->data) return NULL;

    // 计算插入位置
    unsigned char *p = zl->data + zl->zltail;
    unsigned char *newEntry = p;

    // 写入前一个 entry 的长度
    if (prevlenBytes == 1) {
        newEntry[0] = prevlen;
    } else if (prevlenBytes == 5) {
        newEntry[0] = 0xfe;
        *(unsigned int *)(newEntry + 1) = prevlen;
    }

    // 写入字符串长度
    zipStoreStrLen(newEntry + prevlenBytes, slen);

    // 写入字符串数据
    memcpy(newEntry + prevlenBytes + encodingBytes, s, slen);

    // 更新 ziplist 信息
    zl->zltail += required;
    zl->zlbytes += required;
    zl->zllen++;
    zl->data[zl->zlbytes - 1] = ZIP_END; // 更新结尾标志

    return zl;
}

// 打印 ziplist 的内容
void ziplistPrint(ziplist *zl) {
    printf("zlbytes: %un", zl->zlbytes);
    printf("zltail: %un", zl->zltail);
    printf("zllen: %un", zl->zllen);

    unsigned char *p = zl->data;
    int i;
    for (i = 0; i < zl->zllen; i++) {
        unsigned int prevlen = 0;
        unsigned int len = 0;
        int prevlenBytes = 0;
        int encodingBytes = 0;

        // 读取 prevlen
        if (i > 0) {
            prevlenBytes = zipEncodedStrLen(p, &prevlen);
            p += prevlenBytes;
        }

        // 读取 encoding
        encodingBytes = zipEncodedStrLen(p, &len);
        p += encodingBytes;

        printf("Entry %d: Length = %u, Data = %.*sn", i, len, len, p);

        p += len;
    }
}

int main() {
    ziplist *zl = ziplistNew();
    if (!zl) {
        printf("Failed to create ziplistn");
        return 1;
    }

    zl = ziplistPush(zl, (unsigned char *)"hello", 5);
    zl = ziplistPush(zl, (unsigned char *)"world", 5);
    zl = ziplistPush(zl, (unsigned char *)"redis", 5);

    ziplistPrint(zl);

    free(zl->data);
    free(zl);

    return 0;
}

这段代码模拟了ziplist的创建和插入字符串的操作。虽然简化了很多细节，但希望能帮助大家理解ziplist的基本原理。

ziplist的连锁更新

ziplist有一个比较著名的缺点，叫做“连锁更新”（cascading update）。当在一个ziplist的中间位置插入一个新的entry时，如果这个entry的长度很大，导致后面的entry的prevlen字段需要从1个字节扩展到5个字节，那么后面的entry的长度也会增加。如果后面的entry的长度也很大，导致再后面的entry的prevlen字段也需要扩展，以此类推，就会发生连锁更新。

连锁更新会导致ziplist的性能急剧下降，因为每次更新都需要重新分配内存和移动大量的数据。

ziplist的优缺点

优点：

• 内存效率高: ziplist将数据紧凑地存储在一起，没有多余的指针，节省了大量的内存空间。
• 访问速度快: 由于数据存储在连续的内存空间中，可以利用CPU缓存，提高访问速度。

缺点：

• 不适合存储过多的元素: ziplist的zllen字段只有2个字节，最多只能存储65535个元素。
• 插入和删除操作效率低: 在ziplist中间位置插入或删除元素需要移动大量的数据。
• 连锁更新: 插入或删除操作可能导致连锁更新，降低性能。

ziplist的应用场景

ziplist适合存储少量、简单的数据。在Redis中，ziplist被广泛应用于以下场景：

• 列表对象: 当列表对象中的元素数量较少，并且每个元素都是小整数或者短字符串时，Redis会使用ziplist来存储列表。
• 哈希对象: 当哈希对象中的键值对数量较少，并且每个键和值都是小整数或者短字符串时，Redis会使用ziplist来存储哈希。
• 有序集合对象: 当有序集合对象中的元素数量较少，并且每个元素的分值都是小整数时，Redis会使用ziplist来存储有序集合。

listpack：ziplist的继任者

在Redis 7.0中，ziplist已经被listpack取代。listpack解决了ziplist的连锁更新问题，并且在其他方面也做了一些优化。

listpack的结构与ziplist类似，也是一段连续的内存空间，里面存储着一系列的节点（element）。但是，listpack的每个节点都存储了自己的长度，而不是存储前一个节点的长度。这样，即使插入或删除一个节点，也不会影响到后面的节点，从而避免了连锁更新。

总结

ziplist是Redis为了节省内存而设计的一种特殊的数据结构。它通过紧凑地存储数据，减少了内存占用。但是，ziplist也有一些缺点，比如不适合存储过多的元素，插入和删除操作效率低，以及可能发生连锁更新。在Redis 7.0中，ziplist已经被listpack取代。

希望今天的讲解能帮助大家更好地理解ziplist的原理和应用。感谢大家的收看，我们下次再见！