跳至主要内容

Redis数据结构的实现原理

Redis 五种基本数据类型的底层实现

Redis 对外暴露的是 String、Hash、List、Set、Sorted Set 五种类型，但内部每种类型往往有 两种（甚至多种）底层编码，根据数据量大小自动切换。核心设计哲学是：小数据用紧凑、连续内存的结构省内存；数据量大了再切换成哈希表/跳表这类效率更高但更耗内存的结构。

1. String —— SDS（Simple Dynamic String）

Redis 没有直接用 C 语言原生字符串，而是自己实现了 SDS。

结构（以 sdshdr8 为例）：

len   : 已使用长度
alloc : 总分配空间
flags : 类型标记
buf[] : 实际字节数组（以 \0 结尾，但不依赖它判断长度）

根据字符串长度不同，还细分为 sdshdr5/8/16/32/64，用最小的头部类型存放，进一步省内存。

为什么这样设计： - C 字符串要遍历到 \0 才能拿到长度，SDS 直接读 len 字段，O(1)。 - C 字符串不是二进制安全的（遇到 \0 就截断），SDS 靠 len 判断边界，可以存图片、序列化数据等任意二进制内容。 - 拼接前会检查剩余空间，杜绝了缓冲区溢出。 - 空间预分配：字符串变长时，若新长度 < 1MB，分配双倍空间；若 ≥ 1MB，每次只多分配 1MB，避免频繁 realloc。 - 惰性空间释放：字符串变短时不立即释放内存，留着以后用。

优缺点： 换来了安全性、O(1) 长度获取、减少内存重分配次数，代价是比原生 C 字符串多占一点元数据空间。

2. Hash —— listpack / hashtable

  • 小对象：用 listpack（Redis 7.0 之前叫 ziplist），本质是一段连续内存，紧凑存放 key1 value1 key2 value2...，没有指针开销。
  • 大对象：转为 hashtable（Redis 自己实现的 dict），本质是数组 + 链地址法解决哈希冲突，支持渐进式 rehash。

触发转换的阈值（可配置）： - hash-max-listpack-entries（默认 128） - hash-max-listpack-value（默认 64 字节）

任一超限，整个 hash 从 listpack 升级为 hashtable（且不可逆）。

为什么这样设计： - 小规模数据下，指针、哈希桶这些元数据的开销占比反而比数据本身还大，用连续内存的 listpack 更省空间，也更利于 CPU cache 命中。 - 数据量一大，listpack 的查找是 O(n)（要顺序扫描），性能会急剧下降，所以切到 O(1) 查找的 hashtable。

优缺点对比：

优点 缺点
listpack 内存紧凑，省空间 查找/插入 O(n)
hashtable O(1) 查找/插入/删除 内存开销大（指针+桶数组），rehash 有额外开销

3. List —— quicklist（listpack 节点）

List 的实现经历了几次演进：

  • 早期：小数据用 ziplist，大数据用普通双向链表 linkedlist。
  • Redis 3.2 之后至今：统一用 quicklist——一个双向链表，每个节点本身是一个 ziplist（7.0 后为 listpack）。

为什么这样设计： - 纯链表：每个元素都要额外存 prev/next 指针，元素多时内存开销很大，且内存不连续，cache 不友好。 - 纯 ziplist：所有数据挤在一块连续内存里，一旦数据量大，中间插入/删除会导致大量数据搬移，且单个 entry 过大会引发"连锁更新"问题。 - quicklist 折中：把数据切成多个小 ziplist/listpack 节点，用链表串起来——链表层面保证两端 push/pop 是 O(1)，节点内部又保持紧凑存储。 - 额外优化：不常访问的中间节点可以用 LZF 算法压缩，进一步省内存。

优缺点： 兼顾了内存效率和操作效率，但随机访问中间某个索引的元素仍然要沿链表遍历，时间复杂度是 O(n)；同时结构本身比单一的数组或链表更复杂。

4. Set —— intset / listpack / hashtable

三种编码，按数据特征选择：

  • intset：当集合里所有元素都是整数，且数量不多（默认 set-max-intset-entries 512）时使用。本质是有序的整数数组，根据实际存的数值大小自动升级为 int16/int32/int64，查找用二分查找 O(log n)。
  • listpack（Redis 7.2 引入）：元素不全是整数，但数量少、长度短时使用，进一步补充了 intset 覆盖不到的场景。
  • hashtable：元素多，或类型复杂时使用，本质是 value 为空的 dict，O(1) 查找。

为什么这样设计： 业务中大量集合场景其实是纯数字 ID 集合（比如粉丝 ID、标签 ID），intset 用一个紧凑数组就能表示，比 hashtable 省下大量指针和桶开销。

优缺点：

优点 缺点
intset 极省内存 只能存整数，查找 O(log n)
listpack 省内存，支持非整数 操作 O(n)
hashtable 任意类型、O(1) 内存开销大

5. Sorted Set（Zset）—— listpack / skiplist + dict

  • 小对象：listpack（阈值同样可配 zset-max-listpack-entries 默认 128、zset-max-listpack-value 默认 64）。
  • 大对象：skiplist（跳表）+ dict 双结构组合。
    • dict 负责 member → score 的映射，支持 O(1) 的 ZSCORE。
    • skiplist 按 score 排序存储，支持 O(log n) 的范围查询（ZRANGE、ZRANGEBYSCORE）、排名查询。
    • 两个结构共享同一份 member 和 score 数据（通过指针复用，不会重复存两份完整数据）。

为什么用跳表而不是红黑树等平衡树： - 跳表实现简单，代码量小，出错概率低，维护成本低于红黑树的旋转平衡逻辑。 - 跳表本质是有序链表 + 多级索引，天然适合范围查询——找到起点后沿链表顺序遍历即可，红黑树做范围查询还要中序遍历，逻辑更复杂。 - 平均时间复杂度两者都是 O(log n)，但跳表的常数因子更小，插入/删除不需要像红黑树那样做旋转操作。 - 内存开销上跳表和平衡树相当，谈不上明显劣势。

优缺点：

优点 缺点
listpack 省内存 O(n) 操作
skiplist+dict 同时支持 O(1) 按成员查分数 和 O(logN) 范围/排名查询 两份结构都要维护，内存有一定冗余

总结：一以贯之的设计思想

  1. 小规模数据 → 内存连续的紧凑结构（listpack/intset）：省内存、cache 友好，牺牲的是操作复杂度（O(n)），但反正数据量小，O(n) 也很快。
  2. 大规模数据 → 哈希表/跳表类结构：牺牲内存开销，换取 O(1) 或 O(log n) 的操作效率。
  3. 阈值可配置、编码可自动升级（不可降级）：这是 Redis "面向真实业务场景做工程权衡"的体现——多数业务中容器类型的元素数并不多，紧凑编码能大幅节省整体内存占用，只有真正的大 key 才需要付出哈希表/跳表的内存代价。
  4. dict 的渐进式 rehash：无论是独立的 Hash 类型还是 Zset 内部用到的 dict，扩容时都不会一次性 rehash 阻塞主线程，而是维护 ht[0]、ht[1] 两张表，每次操作顺带迁移一小部分，分摊到多次请求中完成。

此博客中的热门博文

Elasticsearch 读写原理指南

### 1. 什么是 segment，里面装了什么？ 在 Lucene（也是 Elasticsearch）里，索引被切分成若干 **segment（段）**，每个 segment 是一个完整的、只读的倒排索引单元。一个 segment 包含： * **倒排词典** —— 用 **FST（Finite‑State Transducer）** 以高度压缩的形式保存每个字段出现的所有 term 以及 term→ord 的映射。对应的磁盘文件是 `*.tim`（新版）或 `*.tis/*.tii`（旧版）。 * **倒排列表（postings）** —— 保存每个 term 出现的文档 ID、频次、位置信息等，文件名通常是 `*.doc`、`*.pos`、`*.pay`。 * **存储字段**（_source、store:true 的字段）—— 以二进制块的形式写入 `*.fdt` / `*.fdx`。 * **doc‑values、norms、向量** 等辅助结构，分别保存在 `*.dv`、`*.norm`、`*.tv` 等文件里。 * **deleted‑docs bitmap**（`*.del`），标记哪些文档已被删除或被更新。 所有这些文件在 segment **写入磁盘后即成为只读**，后续的查询只能读取，永远不会在原文件上进行增删改。 --- ### 2. 原始文档和 FST 为什么都在 segment 里？ * **原始文档**：Elasticsearch 默认把完整的 JSON（_source）以及任何 `store:true` 的字段写入 segment 的 `*.fdt/*.fdx` 文件。每个 segment 保存自己的那部分文档，旧的 segment 在合并前仍然保留，直到合并后被删除。 * **FST**：每个字段的词典在每个 segment 中单独维护，采用 FST 进行前缀共享和字节压缩。这样即使同一个 term 在多个 segment 中出现，也会在每个 segment 里拥有独立的映射，查询时只需要在对应 segment 的 FST 中定位即可。 --- ### 3. 查询时到底是怎么遍历 segment 的？ 1. **请求入口**      客户端的搜索请求先到达 **协调节点**，协调节点把请求 ...
阅读全文

LLM缓存详解

 可以把“大模型缓存”理解成： 把已经算过的结果（或中间结果）存下来，下次尽量复用 。但这里面其实分几层，不只是简单的“问题→答案”缓存。 1️⃣ 常见的几种缓存类型 （1）KV Cache（推理内部缓存） Transformer 在生成时，会把前面 token 的 Key/Value 向量 缓存下来。 本质：避免重复计算 attention 作用： 同一请求内部加速 特点： 👉 只对“同一上下文继续生成”有效 👉 不跨用户、不跨请求 这类缓存是你体感“流式输出越来越快”的原因之一。 （2）Prompt Cache（提示词缓存） 缓存的是： 相同（或高度相似）的 prompt → 对应的中间表示 / 输出 典型场景： 系统提示词（system prompt）很长 多轮对话里前文基本不变 👉 这里能省掉 前缀计算成本（prefill） （3）Embedding / 语义缓存（Semantic Cache） 这个才是你问题的关键 👇 不是按“字符串完全一致”，而是： 把问题转成向量 → 找“语义相似”的历史问题 → 直接复用答案 2️⃣ 为什么命中缓存成本低很多？ 因为大模型推理成本主要在两块： （1）Prefill（吃 prompt） 复杂度 ~ O(n²) 很贵（尤其长 prompt） （2）Decode（逐 token 生成） 每个 token 都要算一遍模型 而缓存命中后： KV cache：不用重复 attention Prompt cache：不用重新 encode 语义缓存： 直接跳过模型推理 👉 相当于从： 几十~几百毫秒 + GPU算力 变成： 一次向量检索（毫秒级）+ 直接返回 所以成本差一个数量级是正常的。 3️⃣ “每个人问法不同，怎么命中缓存？” 这是核心难点，也是工程重点👇 ❌ 不能靠字符串匹配 比如： “今天天气怎么样” “今天外面热不热” 字符串完全不同 → 必须 miss ✅ 用语义相似度（Embedding） 流程一般是： 把问题转 embedding（向量） 在向量数据库里找 TopK 相似问题 如果相似度 > 阈值（比如 0.9） 直接返回缓存答案 一个简单示意 Q1: 北京天气怎么样 → embedding A Q2: 北京今天热吗 → embedding B cosine(A, B) ≈ 0.95...
阅读全文

事务的ACID是什么

 事务的 ACID 是数据库事务必须满足的四个基本性质，用来保证在并发和故障情况下数据的正确性与可靠性： A（Atomicity，原子性） 一个事务中的操作要么 全部成功 ，要么 全部失败回滚 ，不存在“只做了一半”的中间状态。 C（Consistency，一致性） 事务执行前后，数据库都必须处于 一致的合法状态 ，满足约束（如主键、外键、唯一性、业务规则等）。 I（Isolation，隔离性） 并发执行的多个事务之间 相互隔离 ，一个事务未提交的中间结果对其他事务不可见（具体强弱由隔离级别决定）。 D（Durability，持久性） 一旦事务提交成功，其结果会被 永久保存 ，即使系统崩溃也不会丢失（通常依赖 WAL/redo log 等机制）。 一句话记忆： 要么全做完、前后不破坏规则、互不干扰、做完不丢。
阅读全文