Redis底层数据结构

IntSet

IntSet是Redis中一种用于存储整数类型的集合数据结构，主要用于实现特定条件时的SET类型键的底层数据存储。它的特点是在元素数量较少且均为整型时，能够有效地节省内存空间，提高数据的存储和检索效率。

当集合中的元素都是整数且数量不多时，Redis使用intset来实现SET类型。

当集合中的元素数量较多或者元素不是整数时，Redis会使用哈希表来实现SET类型。

IntSet的定义与特点

定义

IntSet本质上是一个由整数构成的有序集合，其数据结构定义包含三个主要部分：encoding（编码方式）、length（元素个数）和contents（存储整数数组的柔性数组）。

IntSet 的结构定义在 Redis 源码中的 intset.h 文件中，以下是简化版的结构：

typedef struct intset {
    uint32_t encoding; // 编码方式
    uint32_t length;   // 集合中元素的数量
    int8_t contents[]; // 柔性数组，实际存储元素的数组
} intset;

encoding 表示contents中每个整数的编码方式，它可以是以下三种之一：

• INTSET_ENC_INT16：表示contents中的每个整数都是16位有符号整数。
• INTSET_ENC_INT32：表示contents中的每个整数都是32位有符号整数。
• INTSET_ENC_INT64：表示contents中的每个整数都是64位有符号整数。

特点

• 有序性：IntSet 中的元素是有序的，这意味着它可以快速进行查找和范围查询操作。
• 唯一性：IntSet 中所有元素都是唯一的，不会有重复的元素。
• 升级：当向 IntSet 添加一个整数时，如果这个整数的大小超出了当前 IntSet 的编码方式，IntSet 会进行“升级”操作，即改变编码方式，将所有元素转换为更大的整数类型，然后再添加新元素。

升级操作

当添加一个新元素时，如果这个元素的大小超过了当前 IntSet 的编码方式所能表示的范围，IntSet 就会进行升级操作。例如：

• 如果 IntSet 当前的编码方式是 INTSET_ENC_INT16，而要添加一个超出 int16_t 范围的整数，IntSet 将升级为 INTSET_ENC_INT32。
• 升级过程会重新分配 contents 数组，将所有元素转换为新的编码方式，然后再添加新元素。

Dict

在 Redis 中，Dict 是一个核心的数据结构，负责键值对的存储和检索。它类似于 Java 中的 HashMap，底层采用数组加链表的方式解决哈希冲突，同时包含两个哈希表，ht[0] 用于存储实际数据，ht[1] 用于 rehash 过程。

Dict 的组成部分

• dictEntry (哈希节点): 每个 dictEntry 包含一个键 (key) 和一个值 (value)，以及一个指向下一个节点的指针 (next)。当发生哈希冲突时，会形成链表。
• dictht (哈希表头): 每个 dictht 包含一个指向 dictEntry 数组的指针 (table)，哈希表大小 (size)，哈希表大小掩码 (sizemask)，以及已使用的 dictEntry 数量 (used)。
• dict (字典): 每个 dict 包含两个 dictht 对象 (ht[0] 和 ht[1])，以及一些控制 rehash 过程的变量，例如 rehashidx 和 pauserehash。

Dict 的操作

• 添加键值对:
  1. 计算键的哈希值 h。
  2. 利用 h & sizemask 计算元素应该存储到数组中的哪个索引位置。
  3. 如果该位置为空，则直接插入；如果该位置已存在相同的键，则返回错误；如果该位置存在链表，则将新元素添加到链表头部。
• 查找键值对:
  1. 计算键的哈希值 h。
  2. 利用 h & sizemask 计算元素应该存储到数组中的哪个索引位置。
  3. 如果该位置为空，则返回 NULL；如果该位置存在相同的键，则返回该键对应的值；如果该位置存在链表，则遍历链表查找键。
• 删除键值对:
  1. 计算键的哈希值 h。
  2. 利用 h & sizemask 计算元素应该存储到数组中的哪个索引位置。
  3. 如果该位置为空，则返回错误；如果该位置存在相同的键，则删除该键值对；如果该位置存在链表，则遍历链表删除键值对。
• 扩容和收缩:
  1. 扩容: 当负载因子 (used/size) 达到一定程度时，会创建一个新的哈希表，并将所有元素重新哈希到新表中。
  2. 收缩: 当负载因子低于一定程度时，会创建一个新的哈希表，并将所有元素重新哈希到新表中，同时减小哈希表大小。
• rehash:
  1. Redis 采用渐进式 rehash，将 rehash 分成多个步骤，在每次事件循环中处理少量元素，避免阻塞主线程。
  2. rehash 过程中，新元素会存储到 ht[1] 中，ht[0] 中的元素会逐个 rehash 到 ht[1] 中。
  3. rehash 完成后，ht[0] 和 ht[1] 交换，并释放 ht[0] 的内存。

SDS

SDS （Simple Dynamic String）是 Redis 自己实现的一种字符串表示方式，旨在解决 C 语言标准字符串的一些问题，比如字符串长度需要额外计算、内存不连续等问题。SDS被广泛用于存储键、值以及内部的数据结构。

SDS的结构

一个SDS字符串由以下部分组成：

1. buf[]：字节数组，用于存储实际的字符串数据。
2. len：记录buf[]中已使用的字节数量，这也就是SDS字符串的长度。
3. alloc：记录buf[]的总分配字节数量，即buf[]数组的大小。
4. flags：表示SDS的类型，用于确定是否需要处理特定类型的SDS（例如，是否包含空字符）。

flags 的比特位分配

• Bit 0: LF: 表示 SDS 是否包含换行符（Line Feed）。
• Bit 1: EM: 表示 SDS 是否以空字符结尾（End Marker）。
• Bit 2: FREE: 保留位，用于将来可能的功能。
• Bits 3-7: TYPE: 表示 SDS 的类型，目前仅支持 SDS_TYPE_SDS。
• Bits 8-9: ALLOC_ALIGN: 分配对齐方式，用于指示内存分配器的对齐方式。
• Bits 10-11: LEN_ALIGN: 长度对齐方式，用于指示长度字段的对齐方式。
• Bits 12-15: RESERVED: 保留位，用于将来可能的功能。

以下是SDS的内存布局：

+--------+---------------------+-----------+----------+
| flags  | len                 | alloc     | buf[]    |
+--------+---------------------+-----------+----------+

SDS的特点

1. 常数时间获取长度：由于SDS中直接记录了字符串的长度（len），获取一个SDS字符串的长度只需要O(1)的时间复杂度。
2. 防止缓冲区溢出：在进行字符串操作时，SDS会检查len和alloc的值，确保不会发生缓冲区溢出。
3. 减少修改字符串时的内存重新分配次数：
   • SDS使用了空间预分配和惰性空间释放的策略，减少频繁修改字符串时的内存重新分配次数。
   • 空间预分配：当SDS字符串需要进行扩展时，Redis不仅会分配必要的空间，还会额外分配一些未使用的空间，以减少未来可能发生的重新分配次数。
   • 惰性空间释放：当SDS字符串缩短时，Redis不会立即释放多余的内存，而是将这部分内存保留，以备后续使用。
4. 二进制安全：SDS以二进制的方式来处理数据，这意味着它可以存储任意格式的数据，包括图片、视频等，而不需要担心字符串中的空字符（'\0'）。
5. 兼容部分C字符串函数：虽然SDS是二进制安全的，但它仍然可以通过特定的API来兼容部分C字符串函数。

SDS与C字符串的比较

与传统的C字符串相比，SDS具有以下优势：

• 长度获取：C字符串需要O(n)的时间复杂度来获取长度，而SDS是O(1)。
• 缓冲区溢出安全：C字符串操作容易发生缓冲区溢出，而SDS则通过len和alloc字段来防止。
• 修改字符串时的内存分配：C字符串每次修改都需要重新分配内存，而SDS通过预分配和惰性释放策略减少内存分配次数。
• 二进制安全：C字符串以空字符结尾，不适合处理二进制数据，而SDS可以。
• 数据处理能力：C 字符串只能处理文本数据，而 SDS 可以处理包括二进制数据在内的任何数据类型。

SDS的使用场景

SDS在Redis中几乎无处不在，以下是几个主要的使用场景：

• 存储键和值：Redis 中的键和值大多使用 SDS 存储。
• 内部缓冲区：许多内部结构和客户端状态的缓冲区都是基于 SDS 实现的。
• AOF 缓冲区：Redis 的 AOF（Append Only File）持久化策略中的缓冲区也是使用 SDS。

listpack

Redis 使用多种内部数据结构来实现其数据类型，以优化不同的操作和使用场景。对于列表（LIST）类型，Redis 使用了一种名为 quicklist（快速列表）的数据结构。但在讨论 quicklist 之前，我们需要了解 Redis 中的基础列表表示——listpack。

Redis的ListPack是一种用于存储字符串列表的内存效率极高的数据结构。在Redis 5.0版本之前，Redis中用于存储列表的底层数据结构主要是ziplist（压缩列表）和linkedlist（链表）。ziplist虽然内存效率很高，但是它的扩展性和修改操作的效率不是很好。因此，Redis在5.0版本中引入了ListPack，用以替代ziplist。与ziplist相比，listpack在内存布局上更为紧凑，实现更简洁，并且避免了ziplist在极端情况下的连锁更新问题。

内存结构

• 内存布局：listpack的内存布局包括三个主要部分：总长度、元素个数和结尾标志。与ziplist相比，listpack没有记录最后一个元素的地址，这简化了内存结构。
• 元素存储：listpack的每个元素包含三部分内容：编码方案（包含数据长度）、具体的数据内容以及该元素前面两个元素数据长度编码后的字节数。

编码方案

• 数字编码：listpack使用7种不同的编码规则来存储整数数值和数字组成的字符串，根据数值大小范围采用不同的编码方式和字节长度。
• 字符串编码：对于非数字或不可打印的二进制字符等，listpack使用三种字符串编码方法，这些方法根据字符串长度采取不同的编码方式。
• 长度编码：每个数据元素的尾部包含一个表示当前数据长度占用的总字节数的长度数据，主要用于从右往左遍历和搜索数据。

特点

• 连续内存：ListPack中的所有元素都存储在一段连续的内存中，这有助于减少内存碎片并提高访问速度。
• 双向遍历：尽管ListPack是连续的内存块，但它支持从头部和尾部进行遍历。
• 可变长度：ListPack能够存储长度可变的字符串，这比固定大小的元素更加灵活。

优缺点

• 优点
  • 高内存效率：通过紧凑的存储格式减少内存使用。
  • 支持不同长度的字符串：相比ziplist，ListPack可以更灵活地处理不同大小的字符串。
• 缺点
  • 写操作可能导致大量内存拷贝：当ListPack需要扩容时，可能需要复制整个ListPack到新的内存位置。

使用场景

ListPack在Redis中用于实现新的数据结构，比如Streams。Streams是一种支持持久化消息队列的数据结构，ListPack在其中用于存储消息。

https://juejin.cn/post/7220950867339247653

quicklist

Redis 中的 quicklist（快速列表）是一种用于实现列表（LIST）类型的数据结构。从 Redis 4.0 版本开始，quicklist 成为了列表类型的默认实现，取代了之前的纯链表实现。quicklist 的设计目标是提高内存效率和操作性能，尤其是在处理大量小元素时。

快速列表的特点

quicklist 是一个双向链表，其中的每个节点是一个 listpack（列表包）。listpack 是一种紧凑的存储格式，用于存储连续的列表元素。以下是 quicklist 的主要特点：

1. 双向链表：quicklist 由一系列 listpack 组成的双向链表构成。
2. 紧凑存储：每个 listpack 包含多个连续的列表元素，可以有效地减少内存使用。
3. 动态调整：quicklist 根据列表的大小动态调整 listpack 的数量，以优化内存使用。
4. 高效操作：对于列表两端的操作（如 lpush 和 rpush），quicklist 提供了高效的性能。

数据结构

quicklist 的节点结构定义如下：

查看代码

typedef struct quicklistNode {
    void *zl;      // 指向 listpack 的指针
    struct quicklistNode *prev;
    struct quicklistNode *next;
} quicklistNode;

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long len;
} quicklist;

其中：

• zl 指向 listpack 的指针。
• prev 和 next 分别指向双向链表中当前节点的前一个和后一个节点。
• len 记录了整个 quicklist 的长度，即元素的数量。

Skip List

Skip List（跳表）是是种概率平衡的数据结构，由William Pugh在1990年提出，用于在有序数据集中进行快速的搜索、插入和删除操作。Redis使用跳表作为其有序集合（sorted set）的底层实现之一，尤其是在集合元素较多，且元素成员是较长的字符串时。

跳表的概念

Redis的跳表（ZSkipList）是一种特殊的数据结构，它被用于实现有序集合（ZSET）。

在Redis中，有序集合用于存储不重复的字符串成员，每个成员关联一个分数，用于排序。

跳跃表的基本思想是在一个有序的链表之上建立多层索引。每一层索引都包含指向链表中某些节点的指针。每一层的索引节点数量逐渐减少，最底层的索引包含了所有节点，而顶层索引只包含少数几个节点。

跳表的结构

跳表节点

typedef struct zskiplistNode {
    sds ele;              // 成员对象
    double score;         // 分数
    struct zskiplistNode *backward; // 后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned long span;            // 跨度
    } level[]; // 层
} zskiplistNode;

• ele：存储成员的字符串，例如一个成员的名称。
• score：存储与成员关联的分数，用于排序。
• backward：指向跳表中该节点的前一个节点的指针，这有助于快速地进行反向遍历。
• level：一个数组，每个元素代表跳表中的一层。数组的大小是随机的，决定了节点在跳表中的层数。
  • forward：指向跳表中当前层的下一个节点的指针。
  • span：记录两个节点之间的距离，即当前节点到下一个节点的跨度（包括下一个节点），用于计算元素排名。

跳表

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 头节点和尾节点
    unsigned long length;                 // 跳表中的节点数量
    int level;                            // 跳表的最大层数
} zskiplist;

• header：指向跳表的头节点，头节点是一个特殊的节点，它的层数等于跳表的最大层数。
• tail：指向跳表的尾节点，方便快速访问跳表的最后一个元素。
• length：记录跳表中节点的总数，不包括头节点。
• level：记录跳表中所有节点中的最大层数。

有序集合

typedef struct zset {
    dict *dict; // 字典
    zskiplist *zsl; // 跳表
} zset;

• dict：一个字典，用于存储成员到分数的映射，这使得Redis可以快速通过成员来获取分数。
• zsl：指向跳表结构的指针，用于按分数排序成员。

跳表的操作

搜索

跳表的搜索操作从最顶层开始，从左向右搜索，如果当前节点的下一个节点的分数大于要搜索的分数，或者到达了链表的末尾，则下降一层继续搜索。这样可以跳过很多不必要的节点，从而提高搜索效率。

插入

跳表的插入操作首先进行搜索，找到合适的插入位置。然后，随机决定新节点的层数，并将新节点插入到每一层中。

删除

跳表的删除操作也是先进行搜索，找到要删除的节点后，从每一层中移除该节点。

跳表的随机化

1. 初始化： 当一个新元素插入跳表时，Redis会使用一个随机算法来决定这个元素应该有多少层。这个算法不是固定的，但通常会采用以下步骤：
2. 概率： Redis使用一个概率值P（例如0.25或1/4），这个值表示一个元素有25%的概率出现在上一层的链表中。这个概率值是预先设定的，可以通过调整这个值来影响跳表的性能和空间复杂度。
3. 随机高度： Redis会生成一个0到1之间的随机数，如果这个数小于概率P，那么就会为这个元素增加一个层级。这个过程会重复进行，直到随机数不再小于P为止。因此，每个元素的高度是随机的，但平均来说，一个元素出现在第k层的概率是$P^k$。

跳表的优缺点

优点

• 高效：跳表可以实现与平衡树（如AVL树、红黑树）相似的搜索、插入和删除操作的时间复杂度，但实现起来更简单。
• 易理解：跳表的结构比平衡树简单，更易于理解和实现。

缺点

• 空间复杂度：跳表的空间复杂度比平衡树要高，因为它需要存储额外的指针。

使用场景

在Redis中，跳表主要用于实现有序集合（sorted set），特别是当有序集合的元素数量较多，且成员是较长的字符串时，Redis会选择跳表作为其底层实现。有序集合允许用户存储带有分数（score）的成员，并按照分数进行排序。跳表在Redis中的使用，使得有序集合的操作能够保持高效和稳定。

当有序集合满足特定条件时，Redis会使用不同的编码策略来优化存储和性能。如果有序集合的元素数量小于128个并且每个元素的成员长度小于64字节，那么会使用listpack编码。在这种情况下，Redis会将每个集合成员及其对应的分数紧密地存储在一起，按照分数的升序排列。具体来说，成员（element）位于前，分数（score）紧跟其后，二者形成一个存储单元。

当集合中的元素数量超过128个或者成员的长度超过64字节时，Redis会转而使用skiplist编码。这种编码结构包含一个字典和一个跳跃表。字典用于保存成员到分数的映射，而跳跃表则按分数大小保存所有的集合元素。这使得在对成员进行排序和查找时，能够以对数时间复杂度进行操作。

HyperLogLog

Redis的HyperLogLog是一种概率型数据结构，主要用于估计集合的基数（即集合中不同元素的数量）。

HyperLogLog的主要优点在于其固定的内存消耗和高效的计算性能。不管集合有多大，每个HyperLogLog只需要12KB的内存，在标准误差为0.81%的情况下，可以处理多达2^64个元素的基数。

基本原理

• 伯努利试验：HyperLogLog的核心基于伯努利试验，该试验类似于抛硬币实验。通过不断抛硬币直到出现正面朝上并记录次数k，最终通过这些记录来估计总体数量。
• 分桶平均：为了减少误差，HyperLogLog将输入元素哈希后分成多个桶（Redis中使用2^14个桶），对每个桶中的结果进行调和平均处理，从而优化估计值。

主要特点

• 内存效率：HyperLogLog只存储估计基数所需的信息，不保存元素具体内容，这使得它非常节省内存。
• 概率估计：由于基于概率算法，HyperLogLog提供的是近似值而非精确值，但误差率通常较低，适用于允许一定误差的大规模数据集。
• 计算性能：无论集合大小如何，HyperLogLog都可以在常量时间内计算出估计基数，性能优异。

实际应用

• 网页访问量统计：在大量用户访问网页的统计中，使用Set、Hash或Bitmap虽然可以实现去重计数，但在数据量巨大时会占用大量内存。HyperLogLog通过固定内存消耗实现高效统计，尤其适用于千万级或亿级的数据量。
• 实战应用：Redis提供了便捷的指令如PFADD、PFCOUNT和PFMERGE，使得使用HyperLogLog变得简单。在实际应用中，一个用户多次访问同一页面，每次访问都调用PFADD指令将用户ID添加到HyperLogLog中，然后通过PFCOUNT获取UV值。

命令操作

• PFADD：用于将元素添加到HyperLogLog中，如果添加成功（即影响了基数估计），则返回1，否则返回0。
• PFCOUNT：用于获取指定HyperLogLog的估算基数值。
• PFMERGE：用于合并多个HyperLogLog结构，以便于对多个数据集进行统一计数。

实际案例

• APP日活月活统计：统计APP的日活跃用户数和月活跃用户数，每天或每月调用PFADD将用户ID加入HyperLogLog中，再通过PFCOUNT获取活跃用户数。
• 搜索词条统计：统计用户每天搜索的不同词条数量，同样使用PFADD和PFCOUNT实现。
• 注册IP统计：对于需要知晓注册IP数量的场景，HyperLogLog也能有效率地完成统计任务。

Bitmap

Redis 的 Bitmaps（位图）是一种非常高效的数据结构，用于存储二进制位的信息。Bitmaps 主要用于表示集合的状态，例如某个用户是否登录过、某篇文章是否被阅读过等。Bitmaps 在 Redis 中的实现非常简单，但功能强大，特别是在处理大量布尔值时。

Bitmaps 的概念

Bitmaps 在 Redis 中本质上是一个非常大的整数数组，每个整数代表一组位（通常 32 位或 64 位），每个位可以用来存储一个布尔值（0 或 1）。通过索引这些位，可以高效地读取和修改单个位的状态。

Bitmaps 的操作

Redis 提供了几种命令来操作 Bitmaps：

1. SETBIT：设置或获取指定偏移量处的位。
2. GETBIT：获取指定偏移量处的位。
3. BITCOUNT：计算位图中设置为 1 的位的数量。
4. BITOP：对多个 Bitmaps 执行位运算，如 AND、OR、NOT 和 XOR。

Bitmaps 的数据结构

在 Redis 中，Bitmaps 是作为字符串类型的数据存储的。这意味着它们实际上是 SDS（Simple Dynamic Strings）的实例。Redis 不会在内部维护特殊的位图数据结构，而是将位图表示为一系列的字节。每个字节可以表示 8 个位，因此，可以通过简单的数学运算来计算和访问位的位置。

在Redis中，Bitmap的最大长度是2^32位，即512MB。

根据官方文档，在特定硬件上对不同大小的Bitmap进行分配所需时间有明显差异。例如，分配512MB（offset为2^32-1）需约300ms，而分配8MB（offset为2^26-1）只需约8ms。大致的空间占用计算公式为：(offset/8/1024/1024)MB。

Bitmap的使用场景

• 横向扩展：适用于记录单个实体的多种状态。例如，一个key中记录一个用户的各种状态。这种情况较少使用，因为每个key携带的uid信息可能导致存储空间大于value本身。
• 纵向扩展：适用于记录多个实体的单一状态。例如，每个key记录一类业务属性的状态，每个uid作为比特位记录信息。这种方式应用更广泛，特别适用于业务区分和资源回收。

Bitmap的实际案例

• 视频属性标记：对于一个拥有亿级数据量的短视频app，视频存在各种属性（如是否加锁、是否特效等）。通过Bitmap，将key设计为属性id加上视频分片id组成，value按视频id对分片范围取模来决定偏移量。这样，十亿视频一个属性大约只需120MB存储空间，相比其他存储方式大大节约了空间。
• 用户在线状态：在一个需要记录3亿用户在线状态的场景中，每个用户用一个比特位表示（在线为1，离线为0）。整个Bitmap大约只需36MB的空间，非常有效地解决了用户状态记录问题。

Redis数据类型和底层数据结构的对应关系