【Redis】 April

List

Redis 的 List 类型底层数据结构经历了显著演进，从双向链表和压缩列表的双重实现，发展为快速列表，最终在内部节点结构上进行了现代化改进。其演进体现了 Redis 在内存效率、操作性能和实现复杂度之间的持续权衡。

演进时间线

Redis 早期版本 (≤ 3.0)：linkedlist（双向链表）与 ziplist（压缩列表）共存，根据配置自动切换。
Redis 3.2 (2016年)：引入 quicklist，作为 List 类型的唯一默认实现，并沿用至今。
Redis 5.0 (2018年)：quicklist 内部节点开始支持实验性的 listpack 结构。
Redis 7.0 (2022年)：listpack 正式取代 ziplist，但仅用于 Hash 和 Sorted Set 的紧凑编码。List 的默认实现仍为 quicklist，但其内部节点结构可配置为 listpack。

一、早期实现 (≤ Redis 3.0)：`linkedlist` 与 `ziplist` 共存

在 Redis 3.2 之前，List 的底层实现由两个配置参数 list-max-ziplist-entries 和 list-max-ziplist-value 控制，在两个结构间切换：

结构	触发条件	结构描述	优点	缺点
双向链表 (`linkedlist`)	元素数量或元素大小超过阈值	标准双向链表，每个节点(`listNode`)独立分配内存，存储指向前后节点的指针(`prev`, `next`)和值的指针(`value`)。	1. 两端插入/删除 O(1)。 2. 节点独立，无内存重分配风险。	1. 内存利用率低：每个节点需额外存储两个指针和一个值的指针，内存开销大。 2. 内存碎片化严重。
压缩列表 (`ziplist`)	元素数量少且每个元素为小字符串或整数	一块连续内存，所有元素紧凑排列，元素间通过“前一节点长度”字段(`prevlen`)和“编码”字段(`encoding`)解析。	1. 内存利用率极高，无额外指针开销。 2. 数据连续，缓存友好。	1. 任何插入/删除操作都可能导致后续元素的连锁更新，最坏情况 O(n²)。 2. 查找中间元素需遍历。

缺点凸显：linkedlist 内存浪费，ziplist 在长列表下性能风险高。两者非此即彼，无法平衡。

二、现代实现 (≥ Redis 3.2)：`quicklist` (快速列表)

quicklist 是 Redis 为 List 类型设计的终极解决方案，它结合了双向链表和压缩列表的优点，是一种“宏观链表，微观压缩列表”的复合结构。

1. 核心设计

quicklist 本质上是一个双向链表，但链表中的每个节点（quicklistNode）不再直接存储单个元素，而是指向一个压缩列表 (ziplist) 或紧凑列表 (listpack)，这个子结构被称为一个“数据块”。

/* quicklist 结构 */
typedef struct quicklist {
    quicklistNode *head;      // 头节点指针
    quicklistNode *tail;      // 尾节点指针
    unsigned long count;      // 所有数据块中元素的总数
    unsigned long len;        // quicklistNode 的数量（数据块数量）
    int fill : 16;            // 控制每个数据块的大小（由 list-max-ziplist-size 配置）
    unsigned int compress : 16; // 头尾不压缩的节点数（由 list-compress-depth 配置）
} quicklist;

/* quicklist 节点结构 */
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;        // 指向底层数据块（ziplist 或 listpack）的指针
    size_t sz;                // 数据块占用的内存大小
    unsigned int count : 16;  // 本数据块中存储的元素个数
    // ... 其他字段
} quicklistNode;

2. 工作原理

分块存储：一个包含 1000 个元素的列表，可能被存储为 10 个节点，每个节点的 ziplist 中包含约 100 个元素。
平衡策略：通过 fill 参数（对应配置 list-max-ziplist-size）控制每个数据块的容量。当对一个已满的数据块进行插入时，会触发节点分裂；当相邻数据块元素过少时，会触发节点合并。
压缩优化：通过 compress 参数（对应配置 list-compress-depth）可以对中间的数据块进行 LZF 压缩，进一步节省内存（适用于很少访问的中间节点，如消息队列的旧消息）。

3. 核心优势

内存效率：相比纯链表，指针开销大幅降低（N 个元素共享 M 个节点指针，M « N）。
性能稳定：相比大 ziplist，将潜在的 O(N) 或 O(N²) 操作局部化。插入/删除操作通常只影响一个数据块，将风险限制在可控范围内。
灵活适配：通过调整 fill 参数，可以根据实际场景在“内存紧凑性”（fill 值大）和“操作性能”（fill 值小）之间取得最佳平衡。

三、内部节点的演进：从 `ziplist` 到 `listpack`

尽管 quicklist 的宏观结构稳定，但其微观数据块结构也在演进：

时期	默认数据块结构	说明
Redis 3.2 - 6.x	`ziplist`	初始实现，存在连锁更新的理论风险。
Redis 7.0+	可配置，默认仍为 `ziplist`，但鼓励使用 `listpack`	Redis 7.0 的核心目标是用 `listpack` 全面替换 `ziplist` 以消除连锁更新。对于 List 类型，可通过配置项 `list-max-listpack-size` 启用 `listpack` 作为数据块。

重要：尽管 listpack 是更安全、更现代的紧凑结构，但 List 类型的主要实现机制始终是 quicklist。listpack 只是作为其内部数据块的一种可选（且更优的）存储格式。

四、操作复杂度与配置

下表总结了在 quicklist 实现下，List 主要操作的时间复杂度：

操作	时间复杂度	说明
`LPUSH` / `RPUSH`	平摊 O(1)	在头/尾节点的数据块头部/尾部插入。
`LPOP` / `RPOP`	O(1)	从头/尾节点的数据块头部/尾部弹出。
`LINDEX`	O(n)	需要遍历数据块找到对应索引。
`LINSERT`	O(n)	先找到位置，再在数据块中插入，可能触发分裂。
`LRANGE`	O(n)	从起始索引遍历到结束索引。

关键配置参数：

list-max-ziplist-size / list-max-listpack-size：控制每个数据块的最大容量（正数表示元素个数，负数表示内存字节数）。例如 -2 表示每个数据块不超过 8KB。
list-compress-depth：控制两端不被压缩的节点数。例如 1 表示头节点和尾节点不压缩，从第二个节点开始压缩。0 表示禁用压缩。

五、总结

Redis List 的底层结构演进，清晰地展示了其设计哲学：

linkedlist + ziplist 时代：简单粗暴的阈值切换，无法兼顾内存和性能。
quicklist 时代：通过“分而治之”的思想，用链表管理宏观结构，用压缩列表管理微观数据，完美实现了内存效率和操作性能的动态平衡。它将长列表的操作代价“切片”，避免了单点性能灾难。
内部优化：在保持 quicklist 优秀架构不变的基础上，将其内部数据块从有缺陷的 ziplist 逐步替换为更健壮的 listpack，体现了持续优化底层基础设施的工程精神。

因此，当你今天使用 Redis 的 List 时，你实际上是在使用一个经过深度优化的、分块的、可压缩的复合数据结构。它既不是简单的链表，也不是原始的数组，而是为现代缓存和队列场景量身定制的 quicklist。理解这一点，对于合理配置参数（如数据块大小、压缩深度）以适配特定业务场景（如用作消息队列、时间线、缓存列表）至关重要。

Set

好的，Redis 的整数集合是 Set 数据类型的一种内存效率极高的底层实现，专门用于存储全是整数的集合。它是 Redis 为了在特定场景下，在内存效率和操作性能之间取得极致平衡而设计的精巧数据结构。

核心定义

整数集合是一个有序、不重复的整数数组。它将集合元素紧凑地存储在一块连续内存中，并且具备一个关键的“升级”特性，能够根据新加入元素的大小，动态扩展底层数组的类型，以节省内存。

一、数据结构与内存布局

整数集合的结构体定义（简化）如下：

typedef struct intset {
    uint32_t encoding;  // 编码方式，决定元素类型
    uint32_t length;    // 集合包含的元素数量
    int8_t contents[];  // 柔性数组，按`encoding`类型存储元素
} intset;

关键字段解析：

encoding：决定了 contents 数组中每个元素的实际数据类型。它有三种可能的值：
- INTSET_ENC_INT16：contents 是 int16_t 类型的数组，每个元素占 2 字节。存储范围：-32,768 到 32,767。
- INTSET_ENC_INT32：contents 是 int32_t 类型的数组，每个元素占 4 字节。
- INTSET_ENC_INT64：contents 是 int64_t 类型的数组，每个元素占 8 字节。
length：集合中当前包含的元素个数。因此，获取集合大小（SCARD命令）是 O(1) 操作。
contents：一个柔性数组，它是实际存储整数的地方。虽然声明为 int8_t，但其实际类型由 encoding 动态解释。数组中的元素按值的大小严格升序排列，且不允许重复。

内存布局示例：假设一个整数集合初始存储了三个 int16_t 类型的数字：1， 3， 5。在内存中，它的布局大致如下：

| encoding=INTSET_ENC_INT16 | length=3 | contents[0]=1 | contents[1]=3 | contents[2]=5 |

这是一个紧凑的、连续的内存块。

二、核心特性：升级

“升级”是整数集合最核心、最精妙的设计。当尝试插入一个新整数，而这个整数的取值范围超出了当前 encoding 所能表示的范围时，整数集合会触发升级。

升级步骤：

计算新编码：根据新元素的值，决定新的、更宽的数据类型（int16_t -> int32_t -> int64_t）。
重新分配内存：根据新的 encoding 和集合长度 length，重新分配底层数组的内存空间。
数据迁移与转换：从最后一个元素开始，依次将旧数组中的元素转换为新类型，并放置到新数组的正确位置。必须从后往前拷贝，以防止数据被覆盖。
插入新元素：将新元素插入到合适的位置（保持有序性）。
更新元数据：更新 encoding 和 length。

示例：上述存储了 [1, 3, 5]（int16_t）的集合，现在要插入一个数字 32768（这超过了 int16_t 的范围）。

触发升级，新编码确定为 INTSET_ENC_INT32。
重新分配内存，新数组需要容纳 4 个 int32_t 元素。
从后往前迁移：先将 5 从 2 字节转换为 4 字节放入新位置，再转换 3，再转换 1。
在有序位置插入 32768，假设数组变为 [1, 3, 5, 32768]。
更新 encoding=INTSET_ENC_INT32, length=4。

升级的重要特性：

提升灵活性：可以安全地从存储小整数过渡到存储大整数，无需预先声明类型。
节省内存：这是最关键的优势。在绝大多数情况下，集合中的元素都是小整数（如用户ID、状态码），使用最小的数据类型（int16_t）存储。只有必要时才升级，最大程度节约了内存。
不支持降级：一旦升级，即使删除导致升级的大元素，编码也不会降级。

三、主要操作与时间复杂度

由于底层是有序数组，其操作复杂度有其特点：

操作	时间复杂度	说明
查找	O(log n)	因为数组有序，使用二分查找。
插入	O(n)	1. 二分查找位置 O(log n)。 2. 可能触发升级 O(n)。 3. 移动后续元素 O(n)。综合为 O(n)。
删除	O(n)	1. 二分查找元素 O(log n)。 2. 移动后续元素填补空缺 O(n)。

与哈希表实现的对比：当集合无法使用整数集合（包含非整数元素，或元素过大/过多触发转换）时，Redis 会使用哈希表作为 Set 的底层实现。

特性	整数集合	哈希表实现
内存效率	极高，无指针开销，使用最小类型。	较低，需存储哈希表结构、指针、entry 等元数据。
查找复杂度	O(log n)	平均 O(1)
插入/删除复杂度	O(n)	平均 O(1)
适用场景	纯整数，元素数量不多。	任意元素（字符串等），或大整数集合。

四、应用场景与配置

典型场景：存储用户标签、IP 黑名单（IP转为整数）、状态码集合、小的用户ID集合等纯整数且规模可控的数据。
配置阈值：Set 类型何时使用整数集合，何时转换为哈希表，由以下两个参数控制（redis.conf）：
- set-max-intset-entries：默认 512。如果整数集合中的元素数量超过此值，即使所有元素都是整数，也会被转换为哈希表实现，以确保在大集合下的操作效率。
如何查看：使用 OBJECT ENCODING key 命令。如果返回 “intset”，则表示该 Set 键正在使用整数集合。

五、总结

整数集合是 Redis 针对纯整数、小规模集合场景设计的内存优化利器。

设计精髓：通过紧凑的连续数组和动态升级机制，在存储小整数集合时，达到了近乎极致的空间效率。
代价：其有序数组的结构导致写入操作（增、删）为 O(n)，不适合频繁修改或元素数量过多（>512） 的场景。此时，Redis 会自动转换为哈希表实现，以时间换空间。
演进体现：它与 ziplist/listpack 的设计哲学一脉相承，都体现了 Redis “为特定场景定制最优化结构” 和 “在内存与CPU之间做精细权衡” 的核心思想。理解它，有助于你在开发中做出更优的数据结构选择，例如，当需要存储大量整数ID时，可以考虑使用 ZSET 或拆分多个键，以避免其自动转换为更耗内存的哈希表。

HyperLogLog

Redis 的 HyperLogLog 是一种概率性数据结构，用于在极小内存空间（固定约 12KB）内高效估算海量数据集的基数（即不重复元素的数量），标准误差率约为 0.81%。

一、核心思想：用概率统计换空间

传统精确计数（如 SET 或 BITMAP）需要存储所有元素，内存消耗与数据量成正比。HLL 的核心突破在于：

不存储元素本身，而是通过元素的哈希值来估算基数。它基于一个统计学观察：一个随机比特序列中，前导零的数量与这个序列的随机性（即不重复元素的数量）存在可估算的关系。

二、核心原理：观察随机比特中的“最大前导零”

想象一个理想的哈希函数，它能将任意输入均匀映射为一个固定长度的二进制串（例如 64 位）。对于基数估算，HLL 遵循以下逻辑：

哈希转换：将每个元素通过哈希函数（Redis 使用 64 位 MurmurHash2）转换成一个 64 位的比特串。我们可以认为这个比特串是随机的，每一位为 0 或 1 的概率各为 1/2。
关键观察：对于一个随机的 64 位比特串，我们可以计算其从最低位（或最高位）开始，连续 0 的个数（即第一个“1”出现的位置，记为 ρ）。
- 概率计算：在一个完全随机的比特串中，前导零数量为 k 的概率是 1 / 2^(k+1)。例如：
  - 第一位就是 1 的概率：1/2（k=0）
  - 第一个 1 出现在第 2 位的概率：1/4（k=1，即序列 01...）
  - 以此类推，连续 10 个 0 后才出现 1 的概率极低，约为 1/2048。
统计洞察：如果我们有 n 个不同的元素（即基数），我们就会得到 n 个独立的、随机分布的 64 位比特串。在这 n 个串中，前导零数量的最大值 max(ρ) 会随着 n 的增大而增大。
- 直觉：抛 1 次硬币就得到正面（k=0）很容易，但想连续抛 10 次都是反面（k=10）再得正面，就需要极多的尝试次数。因此，观察到的最大前导零位数 max(ρ) 越大，说明我们很可能已经处理了越多的不同元素。

三、算法演进：从 LogLog 到 HyperLogLog

直接使用单个 max(ρ) 来估计基数，方差会非常大，结果极不稳定。

分桶平均：为了降低估计误差，HLL 引入了“分桶”思想。将哈希值空间划分为 m 个桶（bucket 或 register）。
- 具体做法：取哈希值的高位来确定桶的索引（例如，前 14 位可表示 2^14 = 16384 个桶）。
- 用哈希值的剩余低位来计算前导零的数量 ρ。
- 这样，每个元素都会根据其哈希值的前 14 位，被分配到这 16384 个桶中的一个，并更新该桶的 ρ 值（仅保留最大值）。
调和平均：LogLog 算法对每个桶的 max(ρ) 求算术平均，然后代入公式估算。HyperLogLog 的改进在于使用调和平均，它能更好地处理极端值（某个桶的 ρ 特别大），使估算更稳定、更准确。

四、 Redis HLL 的具体实现

Redis 的 HLL 实现严格遵循了上述原理，并进行了工程优化。

1. 内存结构：16384 个桶，每个桶 6 比特

桶数量：m = 2^14 = 16384 个桶。这是误差率和内存消耗的平衡点。
桶大小：每个桶只需存储该桶内观测到的最大前导零位数 ρ。由于使用的是 64 位哈希值，ρ 的最大可能值是 64 - 14 = 50（因为用 14 位定桶，剩下 50 位计算前导零）。存储 0-50 的数字只需要 6 比特（2^6=64 > 50）。
总内存：16384 桶 * 6 比特/桶 = 98304 比特 = 12288 字节 = 12 KB。这就是 HLL 内存消耗固定为约 12KB 的原因。

2. 估算公式

将所有桶的 ρ 值收集后，使用以下修正的调和平均公式计算基数估计值 E：

E = α * m * m / (sum(2^(-M[j])))

其中：

m = 16384（桶数）
M[j] 是第 j 个桶中存储的最大前导零值
α 是一个修正常数，用于校正系统偏差（当 m=16384 时，α ≈ 0.7213 / (1 + 1.079/16384) ≈ 0.7213）

3. 对小基数的修正

上述公式在基数非常大时（n >> m）非常准确，但在基数很小时会有明显偏差。因此，Redis 进行了针对性修正：

当估计值 E 小于 2.5 * m 时：算法会检查是否有空桶。如果有，则使用线性计数（Linear Counting）进行修正，公式为：E = m * log(m / V)，其中 V 是空桶的数量。
当估计值 E 非常小（例如小于某个常量）时：可能会直接返回观测到的不同元素的数量（即 PFADD 时实际去重的数量）。

4. 存储格式优化：稀疏与密集表示

为了进一步优化极小基数场景，Redis HLL 使用了两种内部编码：

稀疏表示：当基数很小时，很多桶的值是 0。此时，HLL 不会立即分配完整的 12KB 数组，而是使用一种特殊的、更紧凑的编码（如运行长度编码 RLE）来存储非零桶，可能只需几十字节。
密集表示：当基数增长到一定程度，或稀疏表示不再高效时，自动转换为固定的 12KB 数组。

通过 OBJECT ENCODING key 命令查看 HLL 键，可能会看到 “hyperloglog” 的编码信息。

五、操作与特性

添加元素 (PFADD)：计算元素的 64 位哈希值，用高 14 位找到桶索引，用低 50 位计算前导零位数 ρ，如果 ρ 大于该桶当前值，则更新。
获取基数 (PFCOUNT)：应用上述估算公式和修正规则，返回基数的近似值。
合并 (PFMERGE)：将多个 HLL 合并时，对每个桶，取所有源 HLL 中该桶值的最大值。因此，HLL 支持分布式统计，只需合并各节点的 HLL 即可得到全局去重估算。

六、总结：为什么是 HyperLogLog？

HyperLogLog 是用固定、极小的内存（12KB）换取可预测的误差率（约0.81%） 的典范。

优势：
- 内存效率极致：无论统计 1 亿还是 10 亿不重复元素，都只用约 12KB。
- 可合并：支持分布式统计，合并操作无损。
- 误差可控：标准误差率约为 0.81%，且可通过增加桶数（m）进一步降低（内存会相应增加）。
局限：
- 仅是估算：无法提供精确结果。
- 无法取出元素：HLL 只存储摘要信息，无法像集合一样枚举成员。
- 单条添加：不支持批量添加，但 PFADD 可一次添加多个元素。

适用场景：需要统计海量数据独立访客（UV）、搜索关键词去重数、大型网络事件数等，且可接受微小误差，同时对内存有严格限制的场景。它是大数据时代“近似计算”思想的杰出代表，在有限资源下解决了无限规模数据的统计难题。

List

演进时间线

一、 早期实现 (≤ Redis 3.0)：linkedlist 与 ziplist 共存

二、 现代实现 (≥ Redis 3.2)：quicklist (快速列表)

1. 核心设计

2. 工作原理

3. 核心优势

三、 内部节点的演进：从 ziplist 到 listpack

四、 操作复杂度与配置

五、 总结

Set

核心定义

一、 数据结构与内存布局

二、 核心特性：升级

三、 主要操作与时间复杂度

四、 应用场景与配置

五、 总结

HyperLogLog

一、 核心思想：用概率统计换空间

二、 核心原理：观察随机比特中的“最大前导零”

三、 算法演进：从 LogLog 到 HyperLogLog

四、 Redis HLL 的具体实现

1. 内存结构：16384 个桶，每个桶 6 比特

2. 估算公式

3. 对小基数的修正

4. 存储格式优化：稀疏与密集表示

五、 操作与特性

六、 总结：为什么是 HyperLogLog？

一、早期实现 (≤ Redis 3.0)：`linkedlist` 与 `ziplist` 共存

二、现代实现 (≥ Redis 3.2)：`quicklist` (快速列表)

三、内部节点的演进：从 `ziplist` 到 `listpack`

四、操作复杂度与配置

五、总结

一、数据结构与内存布局

二、核心特性：升级

三、主要操作与时间复杂度

四、应用场景与配置

五、总结

一、核心思想：用概率统计换空间

二、核心原理：观察随机比特中的“最大前导零”

三、算法演进：从 LogLog 到 HyperLogLog

五、操作与特性

六、总结：为什么是 HyperLogLog？