Summer Reverie

外观

数据类型

约 2622 字大约 9 分钟

2025-08-30

基础数据类型

String（字符串）

用途

  • 计数器：例如，文章阅读量、用户点赞数。
  • 分布式锁：通过 SET NX EX 命令实现。
  • 存储序列化对象：如 JSON 格式的用户信息。

底层实现

  • SDS（Simple Dynamic String，简单动态字符串）：Redis 自主实现的动态字符串结构，相较于 C 语言的字符串，具有自动扩容、记录长度、二进制安全等优点。
  • 整数编码（Embedded String）：如果存储的字符串可以表示为 64 位有符号整数，Redis 会将其存储为整数类型，以节省内存并提高操作效率。

Hash（哈希）

用途

  • 缓存对象：存储结构化数据，例如，一个用户对象的所有属性。

底层实现

  • ZipList（压缩列表）：当哈希表中元素数量较少且所有键值对的长度都较小时使用。它是一种连续内存存储结构，节省空间。
  • Dict（哈希表）：当不满足 ZipList 的条件时，Redis 会将底层存储结构从 ZipList 转换为 Dict。
  • Listpack（列表包）：Redis 7.0 以后，Listpack 取代了 ZipList 作为底层实现。

List（列表）

用途

  • 消息队列：实现简单的先进先出（FIFO）或后进先出（LIFO）队列。
  • 朋友圈点赞/评论列表：按时间顺序展示动态。

底层实现

  • QuickList（快速列表）：双向链表和 ZipList 或 Listpack 的混合体。

Set（集合）

用途

  • 共同关注：通过 SINTER 命令求两个用户共同关注的人。
  • 数据去重：Set 自动保证元素的唯一性。
  • 标签系统：存储某个对象的所有标签。

底层实现

  • IntSet（整数集合）：当集合中所有元素都是整数且元素数量较少时使用。
  • Dict（哈希表）：当不满足 IntSet 的条件时，Redis 会将底层存储结构从 IntSet 转换为 Dict。Set 在 Dict 中只使用键存储元素，值通常设为 NULL。

ZSet（有序集合）

用途

  • 排行榜：根据分数对元素进行排序，例如游戏积分榜。
  • 延时队列：利用分数作为时间戳，实现定时任务。

底层实现

  • ZipList（压缩列表）/Listpack（列表包）：当有序集合中元素数量较少（默认小于 128 个）且所有元素成员的长度都较小（默认小于 64 字节）时使用。
  • Dict + SkipList（字典 + 跳表）：当不满足 ZipList/Listpack 的条件时，Redis 会使用 Dict 和 SkipList 两种数据结构来共同实现 ZSet。
    • Dict（哈希表）：用于存储成员（member）到分数（score）的映射，可以通过成员快速查找其分数，时间复杂度为 O(1)\mathcal{O}(1)。
    • SkipList（跳表）：用于存储成员和分数，并按照分数进行排序。它是一个多层链表，可以实现 O(log⁡N)\mathcal{O}(\log N) 的查找、插入和删除操作，特别适用于范围查询和按分数排序。

BitMap（位图）

用途

  • 用户签到记录：每个位代表一天，记录用户是否签到。
  • 布隆过滤器：作为布隆过滤器的底层数据结构。
  • 统计活跃用户：通过位运算快速统计特定时间段的活跃用户。

底层实现

  • String：BitMap 本质上是 String 类型，Redis 将 String 视为一个字节数组，每个字节包含 8 个位，通过位操作（SETBIT, GETBIT, BITCOUNT 等）来操作这些位。

HyperLogLog（基数估算）

用途

  • 基数统计：估算一个集合中不重复元素的数量（例如，网站 UV 统计），允许一定误差但占用极少内存。

底层实现

  • String：HyperLogLog 的底层也是 String 类型，它使用了一种基于概率的数据结构，通过哈希函数和位模式来估算基数。

Geo（地理空间）

用途

  • 附近的人/地点查询：根据经纬度查询指定范围内的地理位置。
  • 地理位置范围查询

底层实现

  • ZSet（有序集合）：Geo 的底层实现是 ZSet。每个地理位置（成员）被编码成一个 52 位的 Geohash 整数作为 ZSet 的分数，经纬度信息存储为 ZSet 的成员。利用 ZSet 的范围查询能力实现地理位置查询。

Stream（流）

用途

  • 消息队列：提供持久化、消费者组、消息确认等功能，比 List 更适合作为消息队列。
  • 事件日志记录

底层实现

  • Radix Tree（基数树）：用于存储 Stream 的消息 ID，实现高效的 ID 查找和范围查询。
  • Listpack（列表包）：用于存储 Stream 的消息内容（键值对）。

核心数据结构

Dict（哈希表）

Dict 是 Redis 哈希键（Hash）的底层实现之一，采用数组加链表的哈希表结构处理键值对存储和哈希冲突。

底层原理

  • 结构设计：基于数组和链表的哈希表实现，包含两个哈希表数组 ht[0] 和 ht[1]。
    • ht[0]：当前活动哈希表，用于存储数据。
    • ht[1]：备用哈希表，仅在 rehash 过程中使用。
  • 哈希函数：使用 MurmurHash 或 SipHash 算法计算键的哈希值，确保均匀分布。哈希值通过取模运算（index = hash(key) % size）定位到数组索引。

Rehash（扩容与收缩）

当键值对数量变化触发负载因子（used_entries / size）阈值时，Redis 执行 rehash：

  • 扩容：负载因子超过 1（默认）时，创建 ht[1]，其大小为 ht[0] 的两倍（向上取整为 2 的幂），以降低冲突概率。
  • 收缩：负载因子低于 0.1 时，创建更小的 ht[1]（大小为 ht[0] 的 1/2），节省内存。

渐进式 Rehash

为避免一次性迁移数据导致阻塞，Redis 采用渐进式 rehash：

  • 在 rehash 期间，ht[0] 和 ht[1] 共存。
  • 操作规则：
    • 新增键值对直接写入 ht[1]。
    • 查询、修改或删除操作先在 ht[0] 查找，未命中时再查 ht[1]。
  • 迁移机制：每次处理客户端命令时，Redis 迁移 ht[0] 的一个桶到 ht[1]。当 ht[0] 为空时，释放 ht[0] 并将 ht[1] 设置为新活动表。

ZipList（压缩列表）

ZipList 是 Redis 列表（List）和哈希（Hash）的底层实现之一，适用于小数据存储，以连续内存节省空间。

底层原理

  • 内存布局： 一段连续内存块，包含：
    • 头部：zlbytes（总字节数）、zltail（尾节点偏移量）、zllen（节点数）。
    • 节点：每个节点存储 prevlen（前驱节点长度）、encoding（数据类型编码）、content（实际数据）。节点双向链接，通过 prevlen 实现反向遍历。
  • 编码优化：使用变长编码（如整数用 1-5 字节存储），减少内存占用。例如，小整数直接内联存储。

特点

  • 内存高效：无指针开销，适合存储少量小尺寸元素（如短字符串或整数）。
  • O(N)\mathcal{O}(N) 遍历：支持顺序访问，但随机访问需遍历。

缺点

  • 修改成本高：插入或删除元素可能触发内存重分配和数据移动，时间复杂度 O(N)\mathcal{O}(N)。
  • 连锁更新（Cascade Update）：当节点长度变化导致 prevlen 字段需扩展时（例如，从 1 字节扩展到 5 字节），后续节点的 prevlen 可能连锁更新。最坏情况下，时间复杂度 O(N2)\mathcal{O}(N^2)，影响性能。

QuickList（快速列表）

QuickList 是 Redis 列表（List）的主要底层实现，结合双向链表和压缩列表，平衡内存与性能。

底层原理

  • 结构设计：双向链表结构，每个节点（QuickListNode）存储一个 ZipList 或 Listpack。

    • 链表节点：包含指向前驱和后继的指针，以及子列表的指针。
    • 子列表：默认为 ZipList，Redis 7.0 后支持 Listpack，存储多个元素。

  • 内存管理：通过配置参数（如 list-max-ziplist-size）控制子列表大小。例如，子列表元素过多时自动分裂，反之合并。

特点

  • 高效操作：
    • 头部/尾部插入/删除：O(1)\mathcal{O}(1)（通过链表指针）。
    • 范围查询：O(N)\mathcal{O}(N)（但子列表连续存储减少遍历开销）。
  • 内存优化：子列表连续存储减少指针开销，内存利用率高。
  • 灵活性：支持动态调整子列表大小，适应数据变化。

SkipList（跳表）

SkipList 是 Redis 有序集合（ZSet）的底层实现之一，用于高效范围查询和排序。

底层原理
  • 多层索引结构：基于有序链表，添加多层索引（L0 为数据层，L1-LN 为索引层）。
    • 节点结构：存储分数（score）、成员（member）和前进指针数组（forward[]）。指针数组高度由随机算法确定（概率为 1/2 的幂次）。
    • 查找过程：从最高层开始，比较分数并“跳跃”到下一节点，逐步降层至数据层。时间复杂度 O(log⁡N)\mathcal{O}(\log N)。
  • 排序机制：所有元素按分数升序存储，分数相同时按字典序排序成员。

特点

  • 高效查找：平均 O(log⁡N)\mathcal{O}(\log N) 的查找、插入和删除性能。
  • 范围查询优化：高层索引快速定位范围起点，实现 O(log⁡N+M)\mathcal{O}(\log N + M) 的范围查询（MM 为结果数）。
  • 空间换时间：索引层占用额外内存（平均 O(N)\mathcal{O}(N) 空间），但提升查询效率。
  • 随机性：新节点层数由随机算法决定，确保平衡性。

Listpack（列表包）

Listpack 是 Redis 5.0 引入的结构，用于替代 ZipList，解决其性能缺陷。

底层原理

  • 内存布局：连续内存块，包含：
    • 头部：lp_bytes（总字节数）、lp_len（元素数）。
    • 节点：每个节点存储 encoding（数据类型和长度编码）、content（数据）、back_len（节点总长度，包括自身）。移除了 prevlen 字段，back_len 明确记录当前节点长度。
  • 编码机制：back_len 使用变长整数存储（1-5 字节），确保长度变化不影响后续节点。

特点

  • 解决连锁更新：节点长度变化仅影响自身，不触发后续更新（时间复杂度 O(1)\mathcal{O}(1)）。
  • 内存高效：连续存储减少指针开销，内存利用率优于链表。
  • 兼容性：作为 ZipList 的替代，用于哈希（Hash）和列表（List）等场景。

总结

为什么 ZSet 需要存储两份数据？

ZSet 需要同时支持 O(1)\mathcal{O}(1) 的成员到分数的查找（通过 Dict）和 O(log⁡N)\mathcal{O}(\log N) 的按分数范围查找/排序（通过 SkipList）。这是其特性需求，为了在不同操作场景下都能保持高效性能。