工程中的数据结构与教科书中的数据结构并不是两套知识,而是同一批结构在两类不同前提下的形态差异。教科书模型假定单线程、数据全在内存、进程不崩溃、容量可控;工程实现必须同时面对并发、内存层次、持久化、故障恢复与规模增长五项约束。本文按"起源—原理—实现—总结"的顺序展开这些差异:先界定五项约束如何改变结构的选择,再按缓存淘汰、队列与缓冲、存储与索引、定时与调度、概率与近似、分布式与组合七个方面给出原理,最后落到实现要点、指标观测、常见问题排查与选型演进。
一、起源:教科书结构与工程实现的差距
1.1 教科书模型的前提假设
教科书中的数据结构通常在一组明确的假设下讨论:
| 假设 | 含义 | 违反后的后果 |
|---|---|---|
| 单线程访问 | 同一时刻只有一个执行流操作结构 | 需要额外的同步或专门设计并发版本 |
| 数据全在内存 | 每次访问的代价相同 | 需要区分缓存、内存、磁盘的访问代价 |
| 进程不崩溃 | 结构状态与进程生命周期一致 | 需要日志、快照与恢复流程 |
| 容量可控 | 元素数量在内存可承载范围内 | 需要淘汰、分层与外部存储 |
| 代价用比较次数度量 | 时间复杂度的常数被忽略 | 实际代价由缓存缺失与 IO 次数主导 |
复杂度分析给出的是增长趋势,这个结论本身没有错。问题在于工程中的常数项往往跨越数个数量级:一次内存访问在纳秒量级,一次磁盘随机 IO 在毫秒量级,两者相差约百万倍。当常数差异达到这个量级时,"同为 O(log n)"的两种实现可能相差几个数量级。
1.2 并发带来的约束
并发对结构的改变不只是"加锁"。
第一层变化是正确性。同步容器能保证单个方法调用的原子性,但复合操作(先判断再写入、先读取再更新)仍需要外部同步,这一点在 Java 集合框架实现原理 与 Java 并发编程 中有系统讨论。结构本身不承诺的语义,调用方必须自己补上。
第二层变化是性能形态。加锁把并行访问串行化,并把锁竞争引入延迟分布:平均耗时可能变化不大,P99 却随竞争线程数显著上升。因此并发场景下结构的选择标准从"平均复杂度"变成"临界区长度与竞争概率"。无锁实现通过 CAS 与原子变量把临界区压缩到单条指令,代价是实现复杂度与内存序的正确性要求。
第三层变化是结构形态本身。并发需求会催生新的结构,例如跳表在并发场景下比平衡树更易实现(跳表),分段锁把一张哈希表拆成多张,序号机制让环形缓冲无需加锁(见第 2.2 节)。
1.3 内存层次带来的约束
CPU 缓存行通常为 64 字节,L1/L2/L3 的容量依次增大而延迟依次上升,主存访问延迟约为 L1 的百倍。这一层次结构使"内存中访问代价相同"的假设不成立。
具体到结构设计,它带来三点后果:
- 顺序访问远优于随机访问。同一条链表上的节点在堆中离散分布,遍历一次的缓存缺失次数远高于遍历数组。这也是开放寻址法在缓存友好性上优于链地址法的原因。
- 结构的内存布局成为设计变量。把"节点加指针"改为"紧凑数组加下标",可以在不改变渐近复杂度的前提下显著降低常数。
- 伪共享成为独立的性能问题。两个线程分别写同一缓存行内不同变量时,缓存行会在核心之间反复失效(见第 2.2 节)。
1.4 持久化与故障恢复带来的约束
数据一旦需要跨进程重启存活,结构就必须处理"内存状态与磁盘状态的分离":
- 写入路径要可恢复。直接修改磁盘上的结构在原地写入时,中途崩溃会留下结构损坏的中间状态。因此要么使用"先写日志再改数据"(WAL、redo),要么使用"只追加不原地修改"(LSM Tree、提交日志),见 mysql: InnoDB 存储引擎。
- 结构的原子性从"一次指针操作"变成"一次可恢复的事务"。内存结构中的指针替换是原子的,磁盘上的页更新不是。
- 代价从比较次数转为 IO 次数。磁盘的最小访问单位是页,一次读取的代价与页大小无关,因此索引结构的目标从"减少比较"变为"降低树高"(B 树与 B+ 树)。
1.5 规模带来的约束
规模增长的第一个后果是内存不再是足够的容器。缓存必须淘汰(第 2.1 节),日志必须切分与合并(第 2.3 节),精确集合可以用近似结构替代(第 2.5 节)。
第二个后果是单机容量与吞吐会出现上限,结构必须从"一个进程内的容器"扩展为"跨节点的数据分布",于是出现一致性哈希、哈希槽、副本与仲裁(第 2.6 节)。
第三个后果是后台任务的代价进入可观测范围。当元素数量达到千万级,哈希表的一次扩容、LSM 的一次合并、时间轮的一次推进都可能表现为毫秒到秒级的停顿,这些停顿在千级规模下不可见。
1.6 工程约束如何改变结构选择
把五项约束汇总,可以直接给出结构选择的判据:
| 约束 | 对结构选择的改变 | 典型结果 |
|---|---|---|
| 并发 | 要求临界区短、竞争可分摊、读操作不阻塞 | 分段锁、无锁队列、跳表替代平衡树 |
| 内存层次 | 顺序访问与紧凑布局优先 | 数组替代链表、批量处理、序号机制 |
| 持久化 | 写入必须可恢复,避免原地更新 | WAL、LSM、追加日志 |
| 故障恢复 | 状态需要可重建或可回放 | 快照加日志、幂等重放 |
| 规模 | 需要淘汰、分层、分片与近似 | LRU/LFU、LSM 分层、一致性哈希、布隆过滤器 |
由此得到的总体结论:工程中的结构选择很少由单一复杂度决定,而是由"在这个约束组合下,哪一种结构的代价落在可接受的延迟与内存预算内"决定。后续各节讨论的每一个结构,都可以对应到上表中的某一行或几行约束;按操作特征与数据规模反查候选结构的判据见 数据结构选型指南。
二、原理
2.1 缓存淘汰
缓存的容量必然小于被缓存的数据集,因此必须回答"满了之后淘汰谁"。淘汰策略是一类结构的统称:它需要在 O(1) 或接近 O(1) 的代价下维护"访问新旧程度"或"访问频率"这一信息。
2.1.1 LRU 的实现:哈希表加双向链表
LRU(Least Recently Used)的语义是:淘汰最久未被访问的元素。要在 O(1) 内完成"查找、把节点移到最新位置、删除最旧节点"三件事,单一结构都不够用:
- 哈希表提供 O(1) 定位,但无法表达顺序,也不知道"最旧的是谁";
- 链表可以表达顺序且头尾操作 O(1),但定位需要 O(n) 遍历。
两者组合后,各自负责自己擅长的部分:
结构:
map: key → node 哈希表,O(1) 找到节点
list: node ←→ node ←→ ... 双向链表,按访问时间排序
头部为最近访问,尾部为最久未访问
get(key):
node = map.get(key)
如果 node 存在:把 node 从链表中间摘出、挂到头部;返回 node.value
否则:返回未命中
put(key, value):
如果 key 已存在:更新值,并把节点移到头部
否则:
如果 元素数 == 容量:删除链表尾节点,并从 map 中移除对应键
新建节点,挂到头部,并写入 map
时间复杂度:get 与 put 均为 O(1),因为摘除与插入都只涉及常数个指针操作。空间复杂度为 O(容量),每个元素额外承担一份哈希表条目与两个指针。
"哈希表决定在哪里,链表决定顺序"这一分工是工程中最常见的组合方式,哈希表自身的实现细节见 散列表。需要注意的是,链表在这里承担的是有序结构的角色,性能上并不理想(指针追逐导致缓存缺失)。当元素数量很大且对淘汰精度要求不高时,通常会用近似结构替代(第 2.1.4 与 2.1.5 节);若顺序维护的代价成为瓶颈且需要范围能力,可考虑跳表这类有序结构(跳表)。
2.1.2 LFU 与频率统计的代价
LFU(Least Frequently Used)淘汰访问次数最少的元素。它的直觉是"访问次数反映长期价值",因此在访问模式稳定的场景下命中率高于 LRU。
实现上的困难有三处:
- 需要每个键的计数器。这使每个元素的内存开销从"两个指针"增加到"两个指针加一个计数器",在千万级元素下是可观的空间成本。
- 需要 O(1) 找到最小频率。常见做法是维护"频率到双向链表"的映射(
freq → list),并记录当前最小频率minFreq。访问某个键时,把它从freq对应的链表移到freq+1的链表;当minFreq对应的链表为空时递增minFreq。这样get与put仍是 O(1),但常数明显大于 LRU。 - 新元素的冷启动问题。新键的频率为 1,最容易被淘汰,即使它是刚被加入的热点。这对突发流量不友好。
更严重的问题是频率无法衰减。如果一个键在很久以前被访问过大量次数,它的计数会长期保持高位,从而难以被淘汰,即使它已经不再被访问。LRU 天然具备的时间局部性,在 LFU 中被计数器固化了下来。实际系统因此普遍采用带衰减的 LFU(如按时间对计数做衰减、或对计数使用对数增长)来缓解,Redis 的 LFU 实现即属于这一类(第 2.1.5 节)。
2.1.3 LRU-K 与 2Q 的改进动机
LRU 的失效场景有两类:
- 顺序扫描污染。一次全表扫描会把大量只访问一次的数据插入缓存,把原本的热点数据全部挤出。这种现象称为缓存污染(cache pollution)。
- 只访问一次的数据占比高。若大部分数据只被访问一次,LRU 会把它们短暂保存在缓存中,而真正会被重复访问的数据被挤走。
LRU-K 的思路是:不只记录最近一次访问,而是记录最近 K 次访问,用第 K 次访问的时间作为淘汰依据。只被访问过不足 K 次的元素其第 K 次访问时间视为无限久远,因此优先被淘汰。这样,只访问一次的数据不会进入"受保护"的集合。
LRU-K 的判据:
记录每个元素最近 K 次访问的时间戳
淘汰依据 = 第 K 次最近的访问时间
若访问次数 < K:视为最久未访问,优先淘汰
代价是需要维护每个元素的 K 个时间戳,空间与更新成本都高于 LRU。K = 2 时即为 LRU-2,是精度与成本的常见折中。
2Q(Two Queue)用另一种方式近似 LRU-2 的效果,把缓存空间分为两个队列:
| 队列 | 内容 | 进入条件 | 淘汰顺序 |
|---|---|---|---|
| A1(近期队列) | 只被访问过一次的元素 | 新元素首次访问 | 先淘汰 A1 |
| Am(频繁队列) | 被访问过至少两次的元素 | A1 中的元素再次被命中时晋升 | A1 为空后淘汰 Am |
| A1out(幽灵队列) | 从 A1 淘汰出的键,只记录键不记录值 | A1 淘汰时进入 | 作为晋升的历史依据 |
关键设计是 A1out:当某个键再次被访问且它的键存在于 A1out 中时,说明它是"被淘汰后又回来"的元素,直接晋升到 Am,从而避免了"被淘汰、再重新进入 A1、再被淘汰"的抖动。A1out 只保存键,内存开销远小于保存完整条目。
三个结构的共同结论是:淘汰策略的改进方向是提高对"未来是否还会被访问"的预测准确度,而所有改进都要用额外的元数据与更新成本来换取。
2.1.4 CLOCK 与二次机会
LRU 的链表版本在每个元素上都要维护两个指针,并且在每次命中时修改链表结构。对操作系统页缓存这类规模(数百万至上千万页)的场景,这两个成本都不可忽略。
CLOCK 算法用"引用位加环形扫描"来近似 LRU:
结构:
环形数组 frames[0..n-1],每个槽位有:引用位 referenced、页数据
指针 hand 指向当前检查位置
访问某个页:
把它的 referenced 置 1
需要淘汰时:
while true:
if frames[hand].referenced == 0:
淘汰该页,hand 后移一位,返回
else:
frames[hand].referenced = 0 // 给第二次机会
hand 后移一位
淘汰时扫描到的第一个引用位为 0 的页即为牺牲页;引用位为 1 的页被清 0 并保留,相当于获得一次"第二次机会"。指针循环前进,形似钟表指针,因此得名。
它的取舍非常明确:
| 维度 | LRU(链表实现) | CLOCK |
|---|---|---|
| 每个元素的开销 | 两个指针加链表节点 | 一个引用位(可复用页结构中的位) |
| 命中时的操作 | 修改链表结构(常数次指针写) | 置一位(一次内存写) |
| 淘汰精度 | 精确最近最少使用 | 近似,可能淘汰近期被访问过的页 |
| 实现复杂度 | 需处理链表边界 | 只需一个游标与一条循环 |
| 并发友好性 | 链表修改需要同步 | 引用位可原子置位,游标由单线程推进 |
在 CLOCK 基础上增加一个"修改位",即可让淘汰优先选择脏页之外的干净页,减少淘汰时的写回。这一变体(时钟页面置换的增强版)是多数操作系统页回收机制的基础。
CLOCK 的精度损失来自"引用位只记录最近一个时钟周期内是否被访问过",无法区分周期内被访问 1 次与 100 次的页。反过来,这也正是它的收益来源:它把 LRU 需要的完整顺序信息压缩为一位。
2.1.5 Redis 的近似 LRU 与淘汰策略
Redis 的做法是"不做精确 LRU,改用随机采样加候选池",因为在单线程中维护全局 LRU 链表会给每次访问都增加链表修改的开销。
机制包含三部分:
- 每个对象记录访问时间。对象头中的
lru字段保存一个 24 位的时钟值,精度为秒级。24 位可表示约 194 天,超出后会回绕,因此空闲时间的计算必须处理回绕。 - 采样淘汰。当内存超过
maxmemory时,随机抽取maxmemory-samples个键(默认 5),比较它们的空闲时间,淘汰其中最久未访问的那个。 - 候选池。为保证淘汰顺序更接近全局 LRU,被抽到的键会进入一个按空闲时间排序的小池(淘汰池),从池中选择空闲时间最大的键淘汰。池机制让"一次采样"的结果能够影响"后续淘汰",从而在采样数不变的情况下提高近似精度。
LFU 模式的差异在于它用 8 位计数器替代时间戳,并引入两个参数控制行为:
计数器增长:对数增长,受 lfu-log-factor 控制
计数越大,继续增长所需的访问次数越多,因此可以只用 8 位覆盖很宽的访问量范围
计数器衰减:按时间衰减,受 lfu-decay-time 控制
每隔一段时间把计数减 1,使长期不再访问的键重新变得"冷"
淘汰策略分为两大类,共八种:
| 类别 | 策略 | 含义 |
|---|---|---|
| 全体键 | allkeys-lru / allkeys-lfu / allkeys-random | 在全部键中按相应规则淘汰 |
| 仅带过期时间的键 | volatile-lru / volatile-lfu / volatile-random / volatile-ttl | 只在设置了过期时间的键中淘汰,volatile-ttl 选择剩余生存时间最短的 |
| 不淘汰 | noeviction | 内存达到上限后写入报错,读操作仍可用 |
noeviction 在把 Redis 当作数据库而非缓存使用时是必要的:淘汰意味着数据丢失,而这类场景不能接受静默丢失。两种用法下的选择依据,以及键空间与过期机制的关系,见 Redis 核心与数据结构 第 2.3 节。
2.1.6 缓存淘汰与应用缓存的一致性
淘汰是静默删除:键消失时不会回调业务代码,也没有"删除事件"可供业务感知。这一点决定了淘汰策略与一致性方案之间存在约束关系。
| 场景 | 淘汰的后果 | 应对 |
|---|---|---|
| 缓存是纯副本,数据源有真实记录 | 淘汰只导致一次回源,正确性不受影响 | 无需特殊处理 |
| 缓存承载了唯一状态(计数器、分布式锁、幂等标记) | 淘汰即状态丢失,业务逻辑出现错误 | 使用 noeviction,或改用持久化存储 |
| 缓存是唯一副本但可重建 | 淘汰导致重建成本,可能引发回源风暴 | 设置合理的淘汰策略并提供回源保护 |
| 缓存与数据库存在更新顺序约定 | 淘汰发生在更新窗口内会放大不一致 | 配合失效策略与延迟双删 |
第二行是最容易被忽略的风险:把 volatile-lru 用在既存缓存又存锁的场景时,锁可能被淘汰,而持有方并不知情。缓存与数据源的一致性模型、失效与更新顺序的取舍见 缓存基础与一致性。
2.2 队列与缓冲
队列在工程中的角色从"数据结构"扩展为"流量的缓冲区",这一转变带来了三个新的设计维度:如何在高并发下无锁地交换数据、如何用批量处理摊薄单次操作成本、以及队列满时如何把压力传回上游。
2.2.1 无锁环形缓冲的设计要点
环形缓冲(ring buffer)用一段固定长度的连续内存实现队列,避免了链式队列的节点分配与指针追逐。设计上有三个要点。
要点一:容量取 2 的幂,用位与替代取模。
容量 capacity = 2^k
下标推进: next = (index + 1) & (capacity - 1)
因为 capacity - 1 的低 k 位全为 1,位与运算等价于对 2 的幂取模,而位与比取模快,且在多数平台上取模的代价随数值增大而增加。
要点二:用序号而非环绕下标区分"空"与"满"。
如果只用 head 与 tail 两个环绕下标,head == tail 既可表示空也可表示满。两种常见解法:
| 解法 | 做法 | 代价 |
|---|---|---|
| 留一个空位 | 元素数达到 capacity - 1 即视为满 | 浪费一个槽位;容量不再是 2 的幂的整数倍 |
| 用单调递增序号 | 序号不取模、只增不减,tail - head 即元素数 | 需要 64 位序号并在使用时对容量取模 |
序号方案更常用,因为它让"空""满""当前元素数"三个判断都变成简单比较:
long head; // 下一个可读位置的序号(消费者推进)
long tail; // 下一个可写位置的序号(生产者推进)
判空: head == tail
判满: tail - head == capacity
元素数:tail - head
实际下标:seq & (capacity - 1)
要点三:单生产者单消费者(SPSC)下可以做到无锁。
在 SPSC 模型中,tail 只由生产者写、head 只由消费者写,每个变量都是"单写多读"。此时不需要 CAS,只需要保证可见性:生产者写入数据后以释放语义发布 tail,消费者以获取语义读取 tail。这条内存序要求在语言层面通常对应 volatile 写(Java 中配合 lazySet 或普通写加写屏障)与原子读。
多生产者(MPSC)或多消费者(MPMC)则必须用 CAS 竞争同一指针,竞争失败需要重试,吞吐随线程数增长而下降。
2.2.2 缓存行与伪共享
把 head 与 tail 放在同一个缓存行上,会引入伪共享(false sharing):
同一缓存行内:
[ head (8B) | tail (8B) | padding ... ]
生产者写 tail → 该缓存行在消费者核心上失效
消费者写 head → 该缓存行在生产者核心上失效
两者交替写入 → 缓存行在两个核心间反复迁移,即使逻辑上互不干扰
这两个变量在逻辑上被不同线程独占写入,却因共享缓存行而产生真实的总线流量。解决办法是把它们填充到各自的缓存行:
public final class RingBuffer<E> {
// 缓存行通常为 64 字节;用填充字段把生产端与消费端序号分开
private long head;
private long p1, p2, p3, p4, p5, p6, p7; // 填充,占满一个缓存行
private volatile long tail;
private long q1, q2, q3, q4, q5, q6, q7; // 填充
private final E[] entries;
private final int mask; // capacity - 1
@SuppressWarnings("unchecked")
public RingBuffer(int capacity) {
this.entries = (E[]) new Object[capacity];
this.mask = capacity - 1;
}
}
语言与运行时通常提供更可靠的填充手段:Java 的 @Contended 注解由虚拟机自动填充,C 与 C++ 中可用对齐属性或编译器的缓存行宏。手写填充字段时需要注意,编译器可能优化掉"看似无用"的字段,因此需要保证字段可达。
2.2.3 Disruptor 式高性能队列
Disruptor 的思路可以概括为四点在普通环形缓冲之上的加强。
一、槽位预分配,写入即覆盖。 环形数组中的每个槽位在初始化时创建一次事件对象,生产者拿到槽位后修改其字段而不新建对象。这样运行期没有对象分配,也就没有垃圾回收带来的停顿与内存压力。
二、序号替代指针。 生产者与消费者各自持有一个单调递增的序号,通过 序号 & (capacity - 1) 定位槽位。序号只增不减,因此"生产者是否追上消费者"这一判断不依赖环绕下标。
三、序列屏障(sequence barrier)表达依赖关系。 消费端不直接读取生产者的序号,而是通过一个屏障对象获取"当前可安全消费到的序号"。屏障由若干"上游序号"组成:
gatingSequences: 需要等待的其他消费者序号集合
↓
sequenceBarrier.waitFor(可消费序号)
↓
若上游尚未推进到该序号,则自旋或让出 CPU 等待
这样可以在多个消费者之间建立依赖:
消费者 B 的屏障包含 消费者 A 的序号
→ B 只在 A 处理完之后才开始处理,形成有向无环的处理链
序列屏障把"线程间顺序约束"从代码中抽离为数据结构,使得同一条数据可以按确定的拓扑顺序被多个处理阶段消费,且每个阶段独立推进。
四、批量消费。 消费者一次取到的是"当前已发布的最高序号",因此可以一次处理多个槽位:
availableSequence = barrier.waitFor(nextSequence)
while (nextSequence <= availableSequence):
process(ringBuffer[nextSequence & mask])
nextSequence++
批量处理把序号判断与屏障等待的开销按批次摊薄,这是它相对"逐条加锁"的主要吞吐来源。
单生产者的发布路径不需要 CAS,只需一次带释放语义的写;多生产者需要用 CAS 竞争序号,并且必须处理"序号已分配但数据尚未写完"的可见性问题(通常为每个槽位增加一个可用标记)。
2.2.4 阻塞队列与背压
进程内队列的容量选择是一个明确的取舍:
| 队列类型 | 容量 | 队列满时的行为 | 风险 |
|---|---|---|---|
| 无界队列 | 不受限 | 不阻塞,持续入队 | 积压转化为堆内存增长,最终 OOM,且错误发现得晚 |
| 有界队列 + 阻塞 | 固定 | 生产者阻塞等待 | 生产者被拖慢,需要确认上游可接受这种反压 |
| 有界队列 + 拒绝策略 | 固定 | 抛出异常、丢弃、或由提交线程执行 | 需要明确的丢弃语义与告警 |
| 同步移交队列 | 0 | 必须已有等待的消费者 | 适用于线程池与任务的生产者消费者直接配对 |
队列的语义与实现细节、循环队列的判空判满见 栈与队列;线程池的队列与拒绝策略属于并发编程的组成部分,各参数的相互作用见 Java 并发编程。
背压(backpressure)的实质是把"过载"这一事实沿调用链向上传递,而不是在某一层用缓冲区把它隐藏起来。它的实现形式有几种:
- 阻塞式:生产者线程在队列满时等待,压力自然传导;
- 拒绝式:拒绝策略触发告警与降级,由上游决定重试或丢弃;
- 请求式:消费方显式声明可接收的数量(如响应式流中的请求计数),生产方按需生产。
需要区分"削峰"与"背压":削峰是用缓冲区吸收短时突发,前提是突发可被后续处理能力消化;背压是承认处理能力上限并要求上游配合限速。若峰值持续高于处理能力,缓冲区只会推迟问题发生的时间点。
2.2.5 消息中间件的顺序写与消费位点
消息中间件把队列从进程内搬到进程外,其存储结构的选择与内存队列有本质差异:写入路径追求顺序追加,读取路径依赖位点而不是出队。
以日志型模型为例,核心结构有三部分:
提交日志(commit log)
所有消息按到达顺序追加写入,写满一个文件后切换到下一个
顺序写避免了随机写,是吞吐的主要来源
索引文件
记录"逻辑偏移量 → 物理文件位置"的映射,用于按偏移量快速定位
通常为稀疏索引,配合顺序扫描
消费位点(offset / consumer offset)
每个消费组在每个分区上维护一个已消费位置
消息本身不因消费而删除,删除由保留策略按时间或空间触发
由此产生的几个工程事实:
- 顺序性有粒度。全局顺序需要单一分区,而这会限制并行度。因此顺序性通常退化为"分区内有序",跨分区的全局顺序需要业务侧承担。
- 消费与删除解耦。位点可以回退,因此支持重放;同时位点回退也需要幂等的消费逻辑配合,否则重复消费会造成重复副作用。相关约定见 消息中间件运维与治理 中的消息治理与故障处置部分。
- 积压是容量问题。堆积量、位点滞后与磁盘水位是容量规划的核心输入,监控指标与容量维度的划分见 消息中间件运维与治理 第 2.2 与 2.3 节。
- 位点的提交频率是吞吐与重复消费之间的取舍。批量提交提高吞吐,代价是故障时重复消费的消息数量增加。
2.3 存储与索引结构
当数据量超过内存容量、或需要跨重启存活时,结构必须与磁盘的访问特性对齐。这一节讨论两类主流索引结构及其取舍。
2.3.1 B+ 树在数据库中的实现
B+ 树把"一次查找等于若干次随机 IO"作为设计前提,工程实现围绕页展开:
| 组成 | 作用 | 相关参数 |
|---|---|---|
| 页 | 一次 IO 的读写单位,通常 16 KB,节点大小与页对齐 | innodb_page_size |
| 页内槽目录 | 页内按键有序存放记录,用页目录做页内二分 | 页填充率 |
| 缓冲池 | 把热页驻留内存,减少物理 IO;页按需从磁盘读入 | innodb_buffer_pool_size |
| 扇出 | 一个内部节点可容纳的分隔键数量,由页大小与键长决定 | 受主键长度影响 |
| 分裂与合并 | 插入导致页满时分裂为两页并向上更新分隔键;删除导致页过空时借位或合并 | 填充因子 |
其中三个工程事实值得单独指出:
- 主键长度直接影响树高。分隔键越短,单页可容纳的键越多,扇出越大,树高越低,查找的 IO 次数越少。短主键(自增整数)与长主键(长字符串、UUID)在同样的数据量下树高差别可达一级以上。
- 随机主键导致页分裂热点。自增主键的插入总是追加到最右侧叶子页,页分裂可控;随机主键的插入分散到全部叶子页,会造成大量页分裂与随机写。
- 页是磁盘与内存之间的搬运单位,因此"把相关的数据放在同一页"是一个真实的设计目标。聚簇索引把整行数据按主键顺序存放,二级索引的叶子存放主键值(回表),这些选择都服务于减少页读取次数。
结构定义、分裂与合并过程、页与缓冲池的衔接,以及索引设计评审要点,见 B 树与 B+ 树;页、表空间与段的层级组织见 mysql: InnoDB 存储引擎 第 2.3 节。
2.3.2 LSM Tree 的分层与合并
LSM Tree(Log-Structured Merge Tree)把写入路径改为"只追加、不原地更新",把随机写转换为顺序写。它的结构自上而下分为四层:
内存(可写)
MemTable 内存中的有序结构(跳表或红黑树),提供 O(log n) 插入与有序遍历
WAL 预写日志,先写日志再写内存,保证崩溃后可恢复
内存(只读)
Immutable MemTable 写满后转为只读,等待后台刷盘;同时新建一个 MemTable 继续接收写入
磁盘
L0 从内存刷出的 SSTable,文件之间键范围可能重叠
L1 ... Ln 更下层的 SSTable,层内键范围互不重叠,层容量按倍数递增
写入路径为:追加 WAL → 写入 MemTable;MemTable 达到阈值后转为不可变并刷成 L0 的 SSTable。读取路径为:查 MemTable → 查不可变 MemTable → 从 L0 逐层向下查找,每层可能命中多个文件。
SSTable(Sorted String Table)是按键排序的不可变文件,内部通常包含:
| 组成部分 | 作用 |
|---|---|
| 数据块 | 按块(如 4 KB)存放有序的键值对,块内可压缩 |
| 索引块 | 稀疏索引,记录每个数据块的首键,用于块级二分 |
| 布隆过滤器 | 按块或按文件记录键的存在性,用于跳过不含目标键的文件 |
| 元数据 | 最小键、最大键、统计信息,用于层间查找时快速排除文件 |
合并(compaction) 是 LSM 的核心维护动作,把重复键、过期版本与删除标记(tombstone)清理掉,并保持层内有序。两种主流策略:
| 策略 | 做法 | 写放大 | 读放大 | 空间放大 |
|---|---|---|---|---|
| 分层合并(leveled) | 每层容量按倍数增长,层内键范围不重叠;合并时把上层文件与下层重叠区间的文件合并重写 | 高(数据每下沉一层都要重写一次) | 低(层内至多命中一个文件,L0 除外) | 低 |
| 大小分层(size-tiered) | 把大小相近的文件合并成更大的文件,层内允许重叠 | 低 | 高(一次查找要检查多个重叠文件) | 高(同一键的多个版本长期共存) |
删除在 LSM 中是"写入一条标记记录",真正的物理删除要等到标记与旧值在合并中相遇。因此删除操作的成本落在后台,而不是写入路径上。这一点与 B+ 树的原地删除形成明显对比。
2.3.3 写放大与读放大
LSM 的成本可以用三个放大系数刻画,它们是理解这类结构的关键:
写放大 = 写入磁盘的字节数 / 逻辑写入的字节数
读放大 = 一次查询需要读取的文件数或块数
空间放大 = 磁盘占用 / 逻辑数据大小
三者的数量关系是:在同一套参数下,降低其中一项通常要以升高另一项为代价。
- 分层合并的写放大可近似理解为"数据从 L0 下沉到 Ln 需要重写约 T × L 次"(T 为层容量倍数,L 为层数),T 取 10、L 取 4 至 7 时,写放大会达到数十倍。这是 LSM 在写密集场景下的主要成本。
- 大小分层把写放大压低,代价是读放大与空间放大上升,因为一次查找要扫描多个可能重叠的文件。
- 布隆过滤器的引入直接针对读放大:它能以极低的内存开销判定"这个文件一定不含目标键",从而跳过大量无效读取(见第 2.5.1 节与 位图与布隆过滤器)。
写放大还有一个不可忽视的后果:它把写入的 IO 压力从用户线程转移到后台线程,因此表现为"写入延迟的周期性抖动"而不是平均值的变化。当合并速度跟不上写入速度时,系统会触发写入限速(write stall),此时用户侧的写入延迟从微秒级跳到毫秒级甚至更高。
2.3.4 B 树与 LSM 的取舍
两类结构代表两种不同的设计重心:
| 维度 | B+ 树 | LSM Tree |
|---|---|---|
| 写入方式 | 原地更新页,可能随机写 | 只追加,顺序写 |
| 写放大 | 较低(一次更新影响有限个页) | 较高(合并会重复重写数据) |
| 读放大 | 低(树高决定,通常是常数级页读取) | 较高(需查内存表与多个层级的文件) |
| 空间放大 | 低(旧值被原地覆盖) | 较高(多版本共存直到合并) |
| 点查性能 | 稳定 | 依赖布隆过滤器与层数 |
| 范围扫描 | 叶子链表顺序推进,效果好 | 需要多文件归并,效果较差 |
| 后台负担 | 刷脏与页分裂 | 合并与合并引发的写入停顿 |
| 故障恢复 | 依赖 redo 前滚与 undo 回滚 | 重放 WAL 即可,恢复逻辑更简单 |
| 典型实现 | MySQL、PostgreSQL、多数关系数据库 | RocksDB、LevelDB、HBase、Cassandra 及以其为存储层的分布式数据库 |
选择依据可以概括为访问模式的偏向:写密集、以点查与追加为主、能接受后台合并开销的场景适合 LSM;读写混合、范围查询与扫描较多、希望读延迟稳定的场景适合 B+ 树。键值存储中两类结构的分工与对照见 B 树与 B+ 树。
2.3.5 列式存储与压缩编码
行式存储把一行记录连续存放,适合"取出整行"的点查。列式存储把同一列的值连续存放,适合"只取少数列并做聚合"的分析场景。它的收益直接来自两个事实:
- 同一列的数据类型相同,因此压缩算法可以有针对性,压缩比通常显著高于行式存储;
- 只读取用到的列,扫描的数据量按列裁剪,IO 成本随列数下降。
常用的编码方式:
| 编码 | 适用数据 | 原理 |
|---|---|---|
| 字典编码 | 基数低的字符串(枚举、状态、城市) | 把字符串映射为整数编号,只存编号 |
| 游程编码(RLE) | 连续重复值多的列 | 存"值 + 重复次数" |
| 增量编码 | 有序或近似有序的整数列 | 存相邻值的差值,差值更小、更易压缩 |
| 位打包 | 取值范围受限的整数 | 用刚好够用的位数表示每个值 |
| 帧参考 | 数值集中在小区间 | 减去区间下界后按固定位宽存储 |
需要区分两类收益:压缩节省的存储空间与扫描节省的 IO 与解压 CPU。后者才是列式存储在分析场景下的主要动机,而它的代价是点查(需要按行重组,代价高)与写入(列文件独立,逐行更新困难)。因此列式存储通常与批量写入、追加式文件格式配套使用。
2.3.6 倒排索引
倒排索引解决的是"按内容找文档"这一与"按键找值"方向相反的问题。它的结构由两部分组成:
词典(term dictionary)
全部词项的有序集合,用于把词项映射到倒排表
通常用有序数组、有限状态转换器(FST)或类似字典树的结构实现
→ 前缀查询、词典序枚举与模糊匹配的能力来自这一层
倒排表(posting list)
每个词项对应一个文档 ID 列表(可附带词频与位置)
文档 ID 通常按升序存放,并用增量编码压缩
常用跳表或块索引加速多表求交、求并
两个结构分别承担不同的职责:词典负责"找到词项",倒排表负责"找出包含词项的文档集合"。查询时对多个倒排表做求交(AND)、求并(OR)或差集(NOT),因此倒排表本身的访问效率(是否可按跳跃跳过、能否块级跳过)直接决定查询性能。词典层支持前缀与模糊匹配的能力,与字典树的原理一致,见 字典树与字符串索引。
工程上的三个要点:
- 倒排表用增量编码加跳表,是因为文档 ID 通常聚集(同一词项出现在连续文档中),增量值很小,压缩收益高;
- 词典的不可变性决定了索引更新方式:许多搜索引擎采用"不可变段 + 后台合并"的组织,这与 LSM 的分层合并思路同源;
- 位图与倒排表可以互相转换。当某个词项出现在大量文档中时,用位图表示倒排表在求交时有明显优势,这也是位图在检索引擎中的主要用途之一(位图与布隆过滤器)。
2.4 定时与调度
延迟任务的结构需求与线程池的普通任务不同:任务需要按"到期时间"而非"到达顺序"取出,且取出操作要与时间推进绑定。
2.4.1 时间轮的结构
时间轮用一个环形数组表示时间,数组的每个槽位(bucket)代表一个时间刻度,槽位内挂一个任务链表:
结构:
slots[N] N 个槽位,环状
tickDuration 每个槽位代表的时间长度
currentTime 当前时间轮的推进位置
插入到期时间为 expire 的任务:
index = (expire / tickDuration) & (N - 1) // N 取 2 的幂时可用位与
把任务挂入 slots[index] 的链表
推进:
每经过 tickDuration,指针后移一格,执行该槽位中的全部到期任务
它的核心收益是插入与删除均为 O(1),与任务数量无关。代价有三处:
- 精度受 tick 限制。到期时间不是 tick 整数倍时,向上取整到下一个刻度,最大误差为一个 tick;
- 单圈容量有限。单圈只能表达
N × tickDuration的时间跨度,超出需要记录"圈数"或多级时间轮; - 槽位内的任务是链表,同一刻度内的任务执行顺序不确定,若需要严格按到期时间排序,槽位内需再放置一个堆。
2.4.2 多级时间轮
多级时间轮用多个不同刻度的轮子表达大跨度时间,思路与钟表的时、分、秒针相同:
第一级:tick = 20ms, 槽数 20 → 覆盖 400ms
第二级:tick = 400ms, 槽数 20 → 覆盖 8s
第三级:tick = 8s, 槽数 20 → 覆盖 160s
...
按此逐级放大,L 级可覆盖 tick × N^L 的时间跨度
插入时按剩余时间选择层级:若到期时间落在当前层的覆盖范围内则放入该层,否则放入更高层,并在降级时逐级下推。这样既保持了 O(1) 的插入,又用有限的内存覆盖了很大的时间跨度。工程中常见的时间轮参数(如 Kafka 的层级时间轮与 Netty 的哈希时间轮)都采用这一思路,区别只在层数、槽数与 tick 的取值。
2.4.3 堆与时间轮的取舍
延迟任务有两种主流实现,选择依据是任务数量与精度要求:
| 维度 | 堆(优先队列) | 时间轮 |
|---|---|---|
| 插入 / 删除 | O(log n) | O(1) |
| 取最早到期 | O(1) 取堆顶,删除后 O(log n) 调整 | 由指针推进批量触发 |
| 时间精度 | 无限制,可到纳秒 | 受 tick 限制 |
| 时间跨度 | 无限制 | 单圈有限,大跨度需多级 |
| 任务取消 | 惰性删除(标记后跳过)或需索引堆支持任意删除 | 从槽位链表中摘除,或标记跳过 |
| 内存 | 每条任务一个堆节点 | 槽位数组加任务链表,槽位开销固定 |
| 适用规模 | 中小规模任务集,或到期时间分布分散 | 大规模任务、到期时间分布均匀且 tick 粒度可接受 |
两者的共同点是都需要一个"推进者":堆实现通常用条件变量等待到最早到期时间,避免空轮询;时间轮则由一个线程或事件循环按 tick 推进。堆在需要修改或删除任意元素时必须借助索引堆(反向索引记录元素在堆中的位置),这一点及其实现难点见 堆与优先队列。延迟任务的实现选择与常见陷阱见同一文档中延迟任务与时间轮相关小节,延迟队列作为队列变体的讨论见 栈与队列。
2.4.4 定时器管理在框架中的实现
不同层次上的定时设施使用的结构不同,职责也不同:
| 层次 | 典型设施 | 结构 | 特点 |
|---|---|---|---|
| 操作系统 | cron、systemd timer | 时间表达式 + 调度器内部的有序结构 | 跨进程、可持久化配置、精度到分钟级 |
| 运行时的线程池 | 定时线程池 | 延迟队列(内部为堆) | 进程内、精度到毫秒、进程退出即失效 |
| 网络框架 | 事件循环内置定时器 | 哈希时间轮 | 与 IO 事件统一调度,避免额外线程 |
| 应用框架 | 任务调度框架 | 数据库表 + 扫描触发,或内存堆 | 支持持久化、分布式抢占与重试 |
| 中间件 | 延时消息、延迟队列 | 内部时间轮或有序集合 | 跨进程共享,通常不提供精确的取消语义 |
操作系统层面的调度配置与两者的取舍见 linux: 计划任务与定时器。应用层需要持久化的调度通常退化为"把下次执行时间写入数据库或有序集合,由轮询取到期任务",这一做法的取舍在 Redis 核心与数据结构 与 Redis 高可用与集群 所描述的单线程与集群模型中均有体现:跨进程共享需要外部存储,而外部存储引入了可见性延迟与多实例抢占问题。
2.5 概率与近似结构
有一类问题不需要精确答案,只需要"在可控误差内给出结果",并且对内存有硬约束。近似结构的价值在于把内存需求从"与元素数量成正比"变为"与精度要求成正比"。
2.5.1 布隆过滤器在存储引擎中的用途
布隆过滤器用一个位数组与 k 个散列函数表示集合,查询时判定"某元素一定不在集合中"或"可能在集合中"。它的误差是单向的:假阳性(误判为存在)可能出现,假阴性(漏判)不会出现。
这一性质恰好匹配存储引擎的需求:查找一条不存在的键时,希望在不读磁盘的前提下排除大部分文件。因此它在 LSM 与按块组织的存储中被广泛使用:
| 用途 | 做法 | 收益 |
|---|---|---|
| 跳过不含目标键的 SSTable | 每个 SSTable 附带一个过滤器 | 把"一次查找读多个文件"降为"读少数几个文件",直接降低读放大 |
| 块级过滤 | 每个数据块附带更细粒度的过滤器 | 减少同一文件内的无效块读取 |
| 缓存穿透防护 | 在缓存层前置过滤器,拦截必然不存在的键 | 避免不存在的键把请求全部打到数据库 |
| 去重与判重 | 爬虫、内容去重、审计黑名单 | 用固定内存处理超大规模集合 |
参数选择是明确的定量问题:在给定元素数量 n 与目标假阳性率 p 时,位数组长度 m 与散列个数 k 由公式确定,且 k 存在最优值。相关公式、内存估算与持久化重建方式见 位图与布隆过滤器;在数据库与存储引擎中的具体应用见同一文档的工程应用部分。
两点工程约束需要注意:过滤器不能删除元素(删除会破坏其他元素的判定),需要删除时必须改用计数布隆过滤器或 Cuckoo Filter;过滤器随数据增长会饱和,填充度上升会抬高假阳性率,因此需要按数据增长周期重建,或使用可扩展方案。
2.5.2 HyperLogLog 在监控与统计中的应用
HyperLogLog(HLL)用于估计集合的基数(不同元素的个数),在固定内存下给出带误差的近似值。它的机制是:
1. 用散列函数把元素映射为足够长的比特串
2. 取前 p 位作为桶编号,共 m = 2^p 个桶
3. 在对应桶中记录"剩余比特中前导零的最大个数 + 1"
4. 估算时对全部桶取调和平均,再做偏差修正
估算的标准误差约为 1.04 / √m。取 m = 16384(p = 14)时误差约 0.81%,每个桶用 6 位存储,总内存约 12 KB,与元素数量无关。它还有两个对统计场景很重要的性质:
- 可合并。多个 HLL 合并时按桶取最大值即可,因此可以分机统计后合并结果,适合分布式场景;
- 不可枚举。它不保存元素本身,因此无法回答"某个元素是否属于该集合",也无法输出元素。
在监控中,HLL 常用于 UV 与活跃用户数估算、独立来源数统计这类"只需要数量、不需要名单"的指标。位图与 HLL 在"去重"这件事上的分工(精确去重与基数估算)见 位图与布隆过滤器。
2.5.3 Count-Min Sketch 与频率估计
Count-Min Sketch(CMS)用于在有限内存下估计元素的出现频次,结构是一个 d 行 w 列的计数器矩阵与 d 个散列函数:
更新(元素 x 出现一次):
for i in 1..d:
counters[i][hash_i(x)]++
查询(元素 x 的频次):
返回 min over i of counters[i][hash_i(x)]
误差特性:
只会高估,不会低估(冲突导致计数被"蹭高")
w 取 e/ε、d 取 ln(1/δ) 时,误差以 1-δ 的概率不超过 ε × 总计数
它的取舍与布隆过滤器同源:用"只高估"的单向误差换取与元素数量无关的内存。工程中的两个典型用法是热点识别(找出频次最高的若干元素,通常与 Space-Saving 或 Misra-Gries 这类算法配合)与限流计数(在大规模键空间下估计每键的请求量,从而避免为每个键维护一个精确计数器)。CMS 的不足是无法枚举元素本身,也无法处理"减少计数"的语义(需要引入带衰减的变体)。
2.5.4 近似结构的取舍与误差管理
近似结构的引入是一项需要业务确认的决策,因为误差会直接体现为业务行为。评估需要回答四个问题:
| 问题 | 影响 |
|---|---|
| 误差方向是什么 | 假阳性(布隆、CMS)会导致多做事(多回源、多过滤);假阴性会导致漏判,通常不可接受 |
| 误差幅度与业务容忍度 | 假阳性率 1% 与 0.01% 在回源量上相差百倍,必须与容量规划一起核算 |
| 是否需要删除与枚举 | 不能删除的结构无法支持数据过期;不能枚举的结构无法替代精确集合的功能 |
| 容量增长如何处理 | 位数组饱和后误差上升,需要按增长周期重建或采用可动态扩展的方案 |
一个常见的误区是"近似结构用一次就不用管了"。实际上参数是按当时的数据量计算的,数据增长、误判率上升、以及重建窗口内的内存峰值,都需要在设计与上线流程中明确。
2.6 分布式结构
当结构无法在单机内容纳或无法由单机提供服务时,问题的性质从"结构设计"变为"数据分布与一致性"。
2.6.1 一致性哈希与虚拟节点
普通取模分片(node = hash(key) mod N)在节点数 N 变化时,约 (N-1)/N 的键需要迁移,缓存场景下这意味着绝大部分缓存同时失效。一致性哈希把键与节点都映射到同一个环形空间,键归属于顺时针方向的第一个节点,因此节点增减只影响其在环上的相邻区间,迁移比例从接近全量降为 1/(N+1)。
虚拟节点解决的是另一个问题:物理节点数量少时,环上区间长度高度不均,会出现严重的数据倾斜。为每个物理节点在环上放置多个虚拟节点后,区间长度趋于均匀,代价是环的元数据增大与节点变化时需要迁移的虚拟节点增多。算法原理、环的构造方式与迁移范围的对照见 散列表 中一致性哈希与分片一节。
2.6.2 分布式缓存与分片的键路由
分片方案可以按"路由由谁决定"分为三类:
| 方案 | 路由位置 | 扩缩容操作 | 特点 |
|---|---|---|---|
| 客户端分片 | 客户端 | 客户端需感知节点列表并重新分布键 | 无代理跳数,但节点变更需要客户端配合 |
| 代理分片 | 代理层 | 代理负责重路由 | 客户端简单,代价是多一跳与代理的可用性要求 |
| 集群分片 | 存储节点之间 | 迁移分片单位 | 路由信息在集群内维护,客户端与节点需处理重定向 |
其中"固定逻辑分片加映射"的思路值得单独说明:先把散列空间切成固定数量的分片(如 16384 个哈希槽),键先映射到槽,槽再分配给节点。节点变化时只需迁移槽,而不必重新计算键到节点的映射。这样分片数成为与物理节点数无关的常量,扩容变成可控的迁移操作。
分片键的选择决定了三个后果:数据是否倾斜、跨分片查询的代价、以及节点扩缩容时的迁移量。这些取舍见 分库分表与全局唯一 ID 与 Redis 高可用与集群。
2.6.3 副本与仲裁
分布式结构中的可靠性来自副本,而副本带来一致性代价。三组参数刻画了取舍:
N:副本总数
W:写操作需要确认的副本数
R:读操作需要读取的副本数
当 W + R > N 时,读集合与写集合必然相交,读操作至少能读到一份最新写入
对于异步复制的主从模型,系统默认处于 W = 1 的状态:主节点写入成功即返回,从节点异步跟进。因此一致性被削弱为最终一致,主节点故障时存在数据丢失窗口。多数派机制(如集群投票与选主)在此之上处理"谁有权接受写入"的问题,其选举规则、分区表现与脑裂防护见 Redis 高可用与集群。
工程上需要明确的两点:副本数决定可用性上限(少数派无法独立提供服务,除非接受数据分歧),仲裁成员数决定容忍的故障节点数(多数派机制下 2 个节点与 3 个节点在容错能力上并不等价)。
2.6.4 分布式 ID 与有序键设计
ID 生成方式与存储结构的匹配关系常被忽略,但它直接影响写入性能:
| ID 方案 | 有序性 | 对存储结构的影响 |
|---|---|---|
| 数据库自增(含步长) | 严格递增,但依赖中心节点 | 适合 B+ 树追加写入;扩容需要调整步长 |
| 号段模式 | 段内递增,段间可能跳号 | 批量预取,减少中心依赖;适合 B+ 树 |
| 雪花算法 | 按时间近似递增,同毫秒内递增 | 趋势递增,写入集中在叶子页尾部,热点可控 |
| UUID | 随机分布 | 随机插入导致 B+ 树页分裂与随机写;在 LSM 中则使合并范围分散 |
由此得到的结论是:有序键是有价值的设计目标。使用有序主键时,B+ 树的插入集中在最右叶子页,页分裂可控;在 LSM 中,有序键让相邻键落在同一 SSTable 与同一层,减少合并时的范围重叠。一个常被忽略的细节是:为本来无序的 ID 加一个时间前缀(或反过来,为单调 ID 加随机后缀以避免热点),可以在"写入局部性"与"负载分散"之间做定向调整。分片键与 ID 方案的取舍、号段与雪花的可用性降级方式见 分库分表与全局唯一 ID。
2.7 组合原则
前面各节的结构很少单独使用,工程实现中的结构几乎都是组合体。这一节归纳组合的规律。
2.7.1 用简单结构组合出复杂能力
组合的一般形式是:用一个结构提供定位能力,用另一个结构提供顺序或语义。
| 目标能力 | 组合方式 | 分工 |
|---|---|---|
| 带淘汰的缓存 | 哈希表 + 双向链表 | 哈希表定位,链表维护最近使用顺序 |
| 支持任意删除的优先队列 | 堆 + 反向索引 | 堆维护最值,反向索引记录元素在堆中的位置 |
| 排序集合 + 按成员查排名 | 跳表 + 哈希表 | 跳表维护有序与排名,哈希表做 O(1) 成员定位 |
| 大规模存在性判断 | 位数组 + 多个散列函数 | 位数组省内存,散列函数提供定位 |
| 布隆过滤器 + 精确集合 | 过滤器前置,集合兜底 | 过滤器拦截大部分不存在的键,集合保证正确性 |
| 高吞吐队列 | 环形数组 + 序号 + 序列屏障 | 数组提供存储,序号表达进度,屏障表达依赖 |
| 稀疏矩阵或图 | 数组 + 索引 | 数组紧凑存放,索引表达非零或邻接位置 |
| 词典与倒排表 | 有序词典 + 增量编码的倒排表 | 词典定位词项,倒排表提供文档集合 |
几个组合之所以有效,是因为它们把"不同性质的操作"分配给不同的结构:哈希表擅长相等定位但不表达顺序,链表表达顺序但定位慢,堆表达优先级但不支持任意删除。组合的代价是元数据冗余与一致性维护成本,任何一处更新都要同时维护两个结构,这是实现中最容易出错的地方。
2.7.2 以空间换时间与以时间换空间的判定
这两条原则在工程中都需要量化才能判断:
| 方向 | 典型手段 | 收益的度量 | 成本与风险 |
|---|---|---|---|
| 空间换时间 | 缓存、索引、预计算、位图、布隆过滤器、列式编码的字典表 | 延迟下降、IO 次数下降、CPU 下降 | 内存占用上升、缓存一致性、容量规划压力 |
| 时间换空间 | 压缩编码、分块与惰性加载、LSM 的分层合并、外部排序 | 内存占用下降、可处理数据量上升 | 延迟上升、CPU 上升、写放大与读放大上升 |
判定的依据是资源受限的方向。当延迟或 IO 是瓶颈且内存有余量时,用空间换时间;当内存或存储是硬约束、而延迟可以在预算内消化时,用时间换空间。需要避免的是无度地朝一个方向推进,因为两类成本最终都会转化为对方:
- 内存缓存过量会触发淘汰与 GC,把空间优势变成延迟抖动;
- 压缩过度会占用 CPU,在高并发下把 IO 瓶颈换成计算瓶颈;
- 合并过于激进会放大写 IO,在写入高峰制造停顿。
2.7.3 可观测性对结构选择的影响
一个结构是否可观测,会影响它在生产环境中的可用性。具体体现在三个方面:
- 是否需要统计能力。若无法从结构中获得命中率、桶长分布、队列水位、合并次数这类指标,故障就只能等它表现为外部症状后才能被发现。因此淘汰策略通常需要暴露命中与淘汰计数,无锁队列需要暴露序号差(积压量),LSM 需要暴露层内文件数与合并等待字节数。
- 是否需要遍历能力。哈希表不承诺遍历顺序,布隆过滤器与 HLL 不支持枚举,这些限制在"事后排查"场景下会变成障碍:无法枚举意味着无法核对内容,只能通过统计推断。
- 内部状态的可见性。环形缓冲、时间轮这类结构的状态是"指针位置",如果不暴露,从外部无法判断任务是否堆积。反之,LSM 的层内文件数、B+ 树的页分裂次数,都是可以在不侵入结构内部的前提下采集的指标。
指标采集与埋点的规范、标签设计与成本控制见 Java 应用可观测性埋点。
三、实现
3.1 LRU 实现要点
3.1.1 哈希表与双向链表的配合
数据结构定义与操作骨架:
public class LruCache<K, V> {
private static class Node<K, V> {
K key;
V value;
Node<K, V> prev;
Node<K, V> next;
}
private final Map<K, Node<K, V>> index = new HashMap<>();
private final int capacity;
private final Node<K, V> head = new Node<>(); // 哨兵:head.next 是最新访问
private final Node<K, V> tail = new Node<>(); // 哨兵:tail.prev 是最久未访问
public LruCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public V get(K key) {
Node<K, V> node = index.get(key);
if (node == null) {
return null;
}
moveToFront(node); // 命中即更新顺序
return node.value;
}
public void put(K key, V value) {
Node<K, V> node = index.get(key);
if (node != null) {
node.value = value;
moveToFront(node);
return;
}
if (index.size() >= capacity) {
Node<K, V> victim = tail.prev; // 最久未访问
unlink(victim);
index.remove(victim.key); // 两个结构必须同步更新
}
node = new Node<>();
node.key = key;
node.value = value;
index.put(key, node);
linkToFront(node);
}
private void moveToFront(Node<K, V> node) {
unlink(node);
linkToFront(node);
}
private void unlink(Node<K, V> node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void linkToFront(Node<K, V> node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
}
实现中最容易出错的地方是"两个结构必须同步更新":淘汰节点时若只从链表摘除而没有从哈希表移除,哈希表中会残留一个已经不在链上的节点,后续 get 会返回错误结果;反之若只从哈希表移除而链表仍有引用,节点不会被回收,容量统计也会失准。
3.1.2 哨兵节点简化边界
双向链表的操作要处理四类边界:链表为空、操作头节点、操作尾节点、链表只有一个节点。用两个哨兵节点(头哨兵与尾哨兵)把链表首尾都变成"内部节点"后,四类边界退化为一种情况:
有哨兵: head ⇄ [节点1] ⇄ [节点2] ⇄ tail
头节点是 head.next,尾节点是 tail.prev
插入与删除永远是"在两个节点之间",不需要判空
无哨兵: 需要判断 prev/next 是否为 null,并单独处理空链表
代价是两个固定节点(可忽略),收益是消除全部分支判断。Java 的 LinkedList 因为没有哨兵,删除与插入的边界处理明显更复杂;LinkedHashMap 用一条双向链表维护插入或访问顺序,其 accessOrder 为真时即为 LRU 语义,可以直接作为简单实现使用,其内部实现见 Java 集合框架实现原理。
3.1.3 并发版本的锁分段与读写锁取舍
简单实现不是线程安全的,因为一次 get 会同时修改哈希表与链表(get 也不是只读操作)。三种并发方案:
| 方案 | 做法 | 优点 | 缺点 |
|---|---|---|---|
| 全局加锁 | 所有操作在同一把锁内 | 语义正确,实现最简单 | 竞争下吞吐低,锁成为瓶颈 |
| 分段加锁 | 按 key 散列分成若干段,每段一个独立的 LRU 与锁 | 竞争按段分摊,实现改动小 | 全局淘汰顺序不再精确,段间容量分配可能出现偏差 |
| 读写锁 | 读走读锁、写走写锁 | 理论读并发度高 | get 需要更新顺序,本质是写操作,读锁优势无法体现 |
第二种方案的取舍值得展开:分段之后,每个段独立执行 LRU,因此被淘汰的是"所在段中最久未访问的元素",而不是全局最久未访问的元素。当访问分布不均匀时,某些段可能频繁淘汰而另一些段长期不满。缓解方式是让段的数量与容量按预期分布设定,并对热点键做额外处理。
第三种方案的问题在于语义与锁类型不匹配:LRU 的 get 会写链表,因此不能放在读锁下。若把"更新顺序"改为异步或按概率执行(近似 LRU),get 才可能变成接近只读的操作。
高命中率场景下更彻底的方案是改变淘汰策略本身:以频率为主、结合近期窗口的 W-TinyLFU 类策略用一个小型频率草图判断"新元素是否比受害元素更有价值",可以在接近 LRU 的内存开销下获得明显更高的命中率。它的代价是引入了一个近似结构,误差特性需要按业务评估。
3.1.4 命中率、容量与淘汰策略的观测
缓存的效果只能通过指标判断,需要采集的最小集合:
| 指标 | 含义 | 判读 |
|---|---|---|
| 命中率 | 命中次数 / 总请求次数 | 明显低于预期时,区分容量不足、策略不匹配、键设计问题 |
| 淘汰速率 | 单位时间淘汰的元素数 | 持续高淘汰说明容量不足或访问模式为扫描型 |
| 平均与最大存活时间 | 元素从写入到被淘汰的时长 | 存活时间远小于 TTL 说明容量不足而非过期导致 |
| 回源量 | 未命中后到达数据源的请求数 | 与命中率互为印证,并与数据源容量一起核算 |
| 元素数与内存占用 | 当前规模与资源成本 | 用于验证容量设定与内存估算 |
观测顺序是先确认"容量是否足够",再判断"策略是否匹配"。若容量充足而命中率仍低,通常是访问模式为顺序扫描型(此时 LRU 会被污染,见第 2.1.3 节)或键的基数过高。指标埋点与标签设计的规范见 Java 应用可观测性埋点。
3.2 环形缓冲实现要点
3.2.1 读写指针与容量取模技巧
容量取 2 的幂是把取模变为位与的前提,同时它也让"扩容"变得不自然:环形缓冲的容量通常在创建时固定,扩容需要重新分配并搬迁全部未消费元素。因此容量应按峰值吞吐与可接受的最大积压量估算,并明确"满了之后怎么办",而不是把它当作可动态增长的容器。
/* C 语言实现的 SPSC 环形缓冲核心操作 */
#include <stdatomic.h>
#include <stdbool.h>
#define CAPACITY 1024 /* 必须是 2 的幂 */
#define MASK (CAPACITY - 1)
typedef struct {
void *slots[CAPACITY];
_Atomic size_t head; /* 消费者推进:下一个可读序号 */
_Atomic size_t tail; /* 生产者推进:下一个可写序号 */
} ring_t;
bool ring_push(ring_t *r, void *item) {
size_t tail = atomic_load_explicit(&r->tail, memory_order_relaxed);
size_t head = atomic_load_explicit(&r->head, memory_order_acquire);
if (tail - head == CAPACITY) {
return false; /* 满:交由调用方决定拒绝或覆盖 */
}
r->slots[tail & MASK] = item; /* 先写数据 */
atomic_store_explicit(&r->tail, tail + 1, memory_order_release); /* 再发布序号 */
return true;
}
bool ring_pop(ring_t *r, void **out) {
size_t head = atomic_load_explicit(&r->head, memory_order_relaxed);
size_t tail = atomic_load_explicit(&r->tail, memory_order_acquire);
if (head == tail) {
return false; /* 空 */
}
*out = r->slots[head & MASK];
atomic_store_explicit(&r->head, head + 1, memory_order_release);
return true;
}
上面的操作顺序不能颠倒:必须先把数据写入槽位,再以释放语义发布序号;消费者以获取语义读取序号,才能保证看到已写入的数据。
3.2.2 覆盖与拒绝策略
队列满时的处理方式必须在设计阶段明确,因为它决定了数据语义:
| 策略 | 行为 | 适用 | 风险 |
|---|---|---|---|
| 拒绝写入 | 返回失败或阻塞生产者 | 数据不可丢失 | 需要上游处理失败或接受阻塞 |
| 覆盖最旧 | 覆盖未消费的最旧元素 | 数据可丢弃(如最新状态采样、行情快照) | 静默丢数据,必须暴露丢弃计数 |
| 丢弃最新 | 直接丢掉本次写入 | 允许丢帧的场景 | 同上 |
| 阻塞生产者 | 等待消费 | 生产端可接受被拖慢 | 可能引发调用链整体变慢 |
在覆盖策略下,"丢弃计数"是与数据同等重要的输出:没有这个计数,覆盖造成的丢失在外部无法被察觉,故障表现为"数据不全"而不是"发生了丢弃"。
3.2.3 无锁实现的原子操作与内存序要求
无锁实现能够成立,依赖的前提是每个共享变量的写入者唯一:
| 模型 | 生产者 | 消费者 | 是否需要 CAS |
|---|---|---|---|
| SPSC | 单线程写 tail | 单线程写 head | 不需要,只需正确内存序 |
| MPSC | 多线程竞争写 tail | 单线程写 head | 生产者需要 CAS 抢占序号 |
| MPMC | 多线程写两个指针 | 多线程写两个指针 | 两者都需要 CAS,并需处理槽位的占用标记 |
三条常见错误:
- 内存序过弱。把发布写与读取都设为
relaxed时,消费者可能读到已推进的序号却看不到槽位中的数据。正确做法是"先写数据、后释放发布序号;先获取读序号、后读数据"。 - 用序号当数据依赖。序号与槽位下标是两套编号,混用会导致覆盖尚未消费的数据。
- 忘记处理回绕。使用 32 位序号时,序号会在短时间内回绕,
tail - head的比较失效;因此无锁实现的序号通常取 64 位,以换取足够长的回绕周期。内存序与可见性的系统讨论见 Java 并发编程。
3.2.4 批量读写的优化
单条入队出队的开销包含序号判断、内存屏障与函数调用,批量处理可以把它按批次摊薄:
// 消费端批量处理:一次取到可消费的最高序号
public void drain(SequenceBarrier barrier, long nextSequence) {
long available = barrier.waitFor(nextSequence);
while (nextSequence <= available) {
Event event = ringBuffer.get(nextSequence);
handler.onEvent(event, nextSequence, nextSequence == available);
nextSequence++;
}
}
批量处理的三个收益:屏障等待与序号判断按批摊薄、槽位访问集中在一个连续区间从而改善缓存命中、以及允许处理逻辑对一批数据做合并操作(如批量落盘、批量提交位点)。代价是单条数据的处理延迟略有上升,因为必须等到批量边界。
3.3 存储结构实践
3.3.1 LSM 与 B 树的参数
LSM 的参数按"内存、写路径、读路径"三类划分:
| 参数 | 作用 | 偏大的后果 | 偏小的后果 |
|---|---|---|---|
| 内存表大小 | 控制刷盘频率 | 恢复时需要重放的 WAL 更长,内存占用上升 | 刷盘频繁,产生大量小 SSTable,加剧合并 |
| L0 文件数阈值 | 控制 L0 到 L1 的合并时机 | 读放大上升(L0 文件越多,一次查找要检查的文件越多) | 合并频繁,写放大上升 |
| 层容量倍数 | 控制各层容量增长 | 写放大上升(数据下沉次数增加) | 空间放大与读放大上升 |
| 合并策略 | 分层或大小分层 | — | — |
| 每键位数(布隆过滤器) | 控制过滤器内存与误判率 | 内存占用上升 | 误判率上升,无效读取增多,读放大上升 |
| 块大小 | 控制索引粒度与压缩效率 | 块内扫描成本上升 | 索引与过滤器开销占比上升 |
B+ 树一侧的参数集中于缓冲池与刷盘:
-- 缓冲池大小决定热页的驻留能力,是读性能的首要参数
-- 观察命中率,判断缓冲池是否够用
SHOW STATUS LIKE 'Innodb_buffer_pool_read%';
-- 页大小影响扇出与树高,需在建库时确定,事后修改需要重建
SELECT @@innodb_page_size;
-- 通过索引统计信息判断索引是否被有效使用
EXPLAIN SELECT id, total FROM orders WHERE user_id = 1001 AND created_at > '2026-09-01';
参数调整的原则是一次只动一个参数,并给出可观测的目标(例如"把读放大从 8 降到 4"或"把合并导致的写停顿次数降为 0"),否则参数之间的相互作用无法归因。页、段与表空间的层级及其配置依据见 mysql: InnoDB 存储引擎;索引长度对扇出与树高的影响、填充因子与分裂策略的讨论见 B 树与 B+ 树。
3.3.2 写放大与读放大的观测方式
两个系数都需要用"系统级计数"与"业务级计数"相比得到,因此观测的第一步是让两侧都可计量:
写放大 = 存储引擎写入的字节数 / 业务逻辑写入的字节数
分子来源:存储引擎的写字节统计(如 compaction 写入量、redo 写入量)
分母来源:业务侧记录的逻辑写入量
读放大 = 一次查询实际读取的文件数或块数
来源:存储引擎的读次数统计、每层文件数与过滤器命中统计
分母:查询次数
判读方式:
| 现象 | 可能原因 | 观察点 |
|---|---|---|
| 写放大远高于层数倍数 | 层容量倍数过小、合并策略过于频繁、频繁覆盖同一批键 | 各层文件数与合并字节数 |
| 读放大随数据量上升 | L0 文件堆积、过滤器未生效或误判率高 | L0 文件数、过滤器命中率与每键位数 |
| 写入延迟周期性尖峰 | 合并争抢磁盘带宽、触发写入限速 | 合并等待字节数、限速触发次数与磁盘利用率 |
| 空间放大上升 | 删除标记与旧版本未及时清理、合并跟不上写入 | 各层数据量与逻辑数据量的比值 |
这些指标的意义在于把"结构调整"与"外部症状"对应起来:仅看到写入变慢无法判断是合并、刷盘还是磁盘带宽的问题,而合并等待字节数可以直接区分第一种情况。
3.3.3 压缩与编码的收益
压缩的收益有两处:减少存储与 IO,减少内存中的占用(若缓存的是压缩块)。代价是 CPU 与延迟。选择时可以按"压缩比 ÷ 压缩速度"排序:
| 算法族 | 压缩比 | 压缩速度 | 典型适用 |
|---|---|---|---|
| LZ4、Snappy | 低 | 高 | 对延迟敏感的在线路径 |
| Zstandard | 中等,可按级别调节 | 中等 | 通用,可在线可离线 |
| Gzip、Deflate | 中等 | 低 | 归档、对 CPU 不敏感的路径 |
| 专用编码(字典、增量、RLE、位打包) | 高(对特定数据分布) | 高(通常为线性扫描) | 列式存储、有序键、时间序列 |
一个实用的经验是:专用编码优先于通用压缩。对有序整数序列,增量编码加位打包的收益通常高于在其上再套一层通用压缩,而解码代价更低。这一点在列式存储与倒排表的实现中是决定性的(第 2.3.5 与 2.3.6 节)。参数与收益的实测方法、基线对照与压测环境差异见 linux: 压测与性能基线。
3.4 定时结构实践
3.4.1 时间轮的槽位与刻度设计
三个参数相互制约:
槽位数 N
tick 时长 T
覆盖跨度 = N × T
三个约束:
精度要求:T 应不大于业务可接受的最大延迟误差
内存要求:N 决定固定内存开销(每个槽位至少一个链表头)
跨度要求:N × T 应覆盖绝大多数任务的延迟范围,减少多级下推
设计顺序通常是:先由精度要求确定 T,再由任务的延迟分布确定所需的覆盖跨度,最后由跨度与 T 计算 N。若 N × T 无法覆盖长延迟任务,有两种做法:增加圈数字段(任务记录还需要转几圈),或引入多级时间轮。
多级时间轮的下推逻辑需要处理一类边界情况:任务在下推过程中可能已经过期(由于下推发生在刻度推进时),此时应立即执行而不是继续下推。忽略这一情况会导致任务被推迟到下一轮,表现为"偶发的延迟增大"。
3.4.2 任务迁移与过期扫描
三类操作需要明确实现方式:
| 操作 | 做法 | 注意事项 |
|---|---|---|
| 任务取消 | 从槽位链表中摘除,或打标记后跳过 | 链表摘除需要任务持有其所在槽位与前后指针;标记方式需要定期清理 |
| 层级下推 | 高层的刻度推进时,把该槽位的任务重新插入低层 | 下推时若已过期则立即执行 |
| 过期扫描兜底 | 定期扫描"已过期但未被触发"的任务 | 用于进程被挂起、时钟跳变等异常后的收敛 |
时钟跳变是定时结构必须处理的异常:系统时间被向前或向后调整时,"按绝对时间计算槽位"的实现在跳变后会集中触发或长时间不触发任务。常见对策是使用单调时钟计算间隔,并把绝对时间的判断留给持久化调度层。
3.4.3 与持久化调度的配合
内存中的定时结构与持久化调度解决的是不同问题,两者通常组合使用:
-- 持久化调度的典型表结构:把下次执行时间持久化,由调度器批量取到期任务
CREATE TABLE scheduled_task (
id BIGINT NOT NULL PRIMARY KEY,
task_type VARCHAR(64) NOT NULL,
payload TEXT,
next_run_time DATETIME(3) NOT NULL,
status TINYINT NOT NULL, -- 0 待执行、1 执行中、2 已完成、3 已取消
version INT NOT NULL, -- 乐观锁,避免多实例重复执行
KEY idx_next_run (status, next_run_time)
);
-- 调度器按到期时间拉取一批任务,配合状态与版本号做抢占
SELECT id, task_type, payload, version
FROM scheduled_task
WHERE status = 0 AND next_run_time <= NOW(3)
ORDER BY next_run_time
LIMIT 100;
三个工程要点:
- 抢占必须靠状态与版本号,而不是"查到就执行",否则多实例会重复执行同一任务;
- 内存中的时间轮只负责"何时唤醒",任务的持久状态、重试与幂等由数据库或外部存储承担;
- 批量拉取与位点或时间水位配合,避免每轮扫描全表。操作系统层面的定时设施(cron 与 systemd timer)在精度、持久化与执行环境上的差异见 linux: 计划任务与定时器。
3.5 结构与系统指标的关系
结构选择最终会体现为资源与延迟指标,因此可以用指标反推结构是否合适。
| 指标维度 | 与结构的关系 | 异常的典型含义 |
|---|---|---|
| 内存占用 | 每元素的元数据开销 × 元素数 + 结构自身的固定开销 | 单元素开销过大(指针、对象头、计数器);容量预分配过大 |
| 延迟均值 | 反映平均路径的代价 | 均值正常不能说明结构合适,长尾信息会被掩盖 |
| 延迟分位数(P95/P99/P999) | 反映长尾路径:扩容、合并、锁竞争、重新散列 | 周期性 P99 尖峰指向后台维护动作;随机 P99 抬高指向锁竞争或 GC |
| 吞吐 | 单位时间的操作数,受临界区长度与批量能力影响 | 吞吐不随并发上升而上升,说明存在串行瓶颈 |
| IO 次数与字节数 | 反映结构的访问模式(顺序或随机)与放大系数 | 随机 IO 比例高说明结构未与存储特性对齐 |
| CPU 分布 | 散列计算、比较、压缩、内存拷贝的占比 | 散列或压缩占比过高说明参数或算法选择需要调整 |
判断"结构选择不当"的两种典型模式:
- 均值与分位数背离。平均延迟在预算内,但 P99 高出数倍。这类问题通常由后台动作(扩容、合并、刷脏)或竞争引起,需要通过"延迟曲线与后台事件的时间相关性"定位。
- 资源与收益背离。内存或 CPU 投入持续上升,但吞吐与命中率没有相应改善。此时问题通常在结构之外的参数上:容量设定、键分布、批大小或缓存策略。监控指标的类型与判读方式见 linux: 监控与告警,压测方法与基线对照、分位数与并发模型的定义见 linux: 压测与性能基线。
3.6 常见问题与排查
| 现象 | 可能原因 | 验证方式 | 处理 |
|---|---|---|---|
| 缓存命中率持续偏低 | 容量不足;淘汰策略与访问模式不匹配(顺序扫描污染 LRU);键基数过高或键未覆盖全部输入维度 | 对比元素数、淘汰速率与平均存活时间;抽样统计键的重复访问比例 | 扩充容量或改用抗扫描策略;修正键设计;对写密集型访问改用频率类策略 |
| 缓存内存高但命中率不升 | 元素元数据开销过大;键的粒度太细(把可合并的多个键拆成多个条目) | 统计单元素内存占用与条目总数 | 合并键粒度;改用紧凑结构或近似结构替代精确集合 |
| 环形缓冲出现数据丢失 | 队列满时采用覆盖策略且未记录丢弃计数;序号用 32 位发生回绕;生产者与消费者下标语义混用 | 检查丢弃计数与积压量指标;检查序号宽度与判满条件 | 明确并暴露丢弃策略与计数;改用 64 位序号;统一"序号与下标"的换算方式 |
| 高并发下吞吐不升反降 | 伪共享(生产端与消费端序号同处一个缓存行);CAS 竞争失败重试;临界区过长 | 用性能分析工具查看缓存缺失与 CAS 失败率;检查字段内存布局 | 填充缓存行或使用运行时提供的填充注解;改为单生产者模型或分段;缩短临界区 |
| 写入延迟出现周期性尖峰 | LSM 合并争抢磁盘带宽或触发写入限速;B+ 树刷脏与检查点集中执行 | 对比延迟曲线与合并字节数、刷脏次数、磁盘利用率的时间关系 | 调整层容量倍数与合并策略;错峰刷脏;为合并保留 IO 预算 |
| 点查延迟随数据量上升 | 读放大上升:L0 文件堆积、布隆过滤器未生效或每键位数不足、误判率随填充度上升 | 统计 L0 文件数、过滤器命中率与假阳性率 | 调整 L0 阈值与合并节奏;提高每键位数;按增长周期重建过滤器 |
| 布隆过滤器误判导致回源增加 | 位数组填充度过高(元素数超过设计容量);散列个数偏离最优值;键的散列质量差 | 统计实际元素数、位数组使用位比例与误判率 | 重建过滤器并留出容量余量;按公式重算参数;更换散列函数 |
| 延迟任务触发时间不准 | tick 过大导致精度不足;任务被下推到下一轮;时钟跳变 | 统计实际触发时间与预期到期时间的差值分布 | 减小 tick 或改多级时间轮;修正下推时已过期的处理;改用单调时钟 |
| 定时任务重复执行 | 多实例抢占未使用状态与版本号;任务执行时间超过下次调度间隔 | 检查任务执行记录与实例日志 | 引入状态位与乐观锁;为长任务设置执行中状态与超时回收 |
| 并发结构出现数据竞争或偶发错误 | 复合操作未加锁;内存序过弱导致可见性问题;容器非线程安全却被并发访问 | 用并发测试与检测工具复现;检查共享变量的写入者数量 | 使用并发容器或显式同步;修正内存序;把共享结构的写入收敛到单线程 |
排查的通用顺序是:先确认问题属于"容量与参数"还是"结构与并发"。容量与参数问题的证据是资源指标与收益指标同时异常(内存与 CPU 高、命中率低、放大系数高);结构与并发问题的证据是随机性(偶发错误、延迟分布异常但资源指标正常)。两者的表现都可能表现为"慢",但排查路径完全不同。
3.7 选型与演进
结构的选择不是一次性决策。合理的路径是从最简结构开始,在指标证明它是瓶颈后再替换。
| 阶段 | 做法 | 触发替换的信号 |
|---|---|---|
| 单机、规模小 | 语言内置的字典、数组、双端队列,无容量上限但有明确的规模上界 | 内存占用接近上限;后台动作出现可观测停顿 |
| 需要对顺序有控制 | 保持插入顺序的映射、有序映射、优先队列 | 操作复杂度成为瓶颈;并发访问出现竞争 |
| 需要淘汰与容量控制 | 带容量与淘汰策略的缓存组件 | 命中率不足;淘汰策略与访问模式不匹配 |
| 需要跨重启存活 | 追加日志、快照、外部存储 | 恢复时间过长;单机容量不足 |
| 需要超出单机容量 | 分片、一致性哈希、分布式索引 | 迁移代价过高;一致性方案无法满足业务 |
替换结构的代价必须提前评估,主要包括四项:
- 数据迁移。结构的持久化格式变化需要迁移或双写,迁移期间新旧格式并存,需要版本标记与回滚方案。分片结构的替换还涉及大量数据的搬迁与搬迁期间的路由处理。
- 语义兼容。遍历顺序、精度、误差特性、并发语义的变化都可能影响调用方。例如把精确集合替换为近似结构时,调用方必须接受假阳性。
- 可观测性配套。新结构需要新的指标与告警规则,否则故障发现能力会退化。
- 容量规划重算。新结构的单元素开销与放大系数不同,原有的容量估算不再成立。
由此得到两条实践原则:替换前先用指标证明当前结构是瓶颈(避免为想象中的问题引入复杂度),替换时保留可回退的路径(双写、灰度、格式版本化)。分片与 ID 方案的演进、迁移与双写的实施步骤与回滚点,见 分库分表与全局唯一 ID。
四、总结
工程中的数据结构,是同一批结构在并发、内存层次、持久化、故障恢复与规模五项约束下的形态。本文的结论可以归为几条主线:
- 约束决定选择。同步需求把选择标准从平均复杂度改为临界区长度与竞争概率;内存层次把顺序访问与紧凑布局变成硬指标;持久化把原地更新换成追加与日志;故障恢复要求状态可重建;规模要求淘汰、分层、分片与近似。结构的复杂度表只是起点,不是结论。
- 缓存淘汰的改进方向是预测准确度。LRU 用哈希表加双向链表取得 O(1),代价是每个元素的指针开销与缓存局部性;LFU 提高稳定模式下的命中率,代价是频率固化与冷启动问题;LRU-K 与 2Q 通过记录多次访问历史与幽灵队列对抗扫描污染;CLOCK 用引用位与环形扫描把顺序信息压缩为一位,牺牲精度换取内存与并发友好性;Redis 用采样加候选池做近似 LRU,用带对数增长与衰减的 8 位计数器做 LFU。淘汰是静默删除,因此把缓存同时当作状态存储时必须选择不淘汰策略。
- 高吞吐队列的关键是把进度表达为序号。容量取 2 的幂让取模变为位与;单调递增的序号让空、满与元素数都成为简单比较;SPSC 下写者唯一,因此只需正确内存序而不需要 CAS;伪共享必须通过填充缓存行消除;Disruptor 用序号、序列屏障与批量消费把线程间依赖表达为结构;队列满时的行为(阻塞、拒绝、覆盖)必须在设计阶段确定并暴露计数。消息中间件把队列搬到进程外后,收益来自顺序追加写,代价是顺序性退化为分区内有序、消费与删除解耦后需要幂等。
- 存储与索引结构的取舍集中在三种放大。B+ 树以页为单位,用原地更新换来低读放大与低空间放大;LSM 以追加写与分层合并换来顺序写,代价是写放大、读放大与空间放大之间的三方权衡;布隆过滤器直接针对读放大,用可控的假阳性跳过无效读取。列式存储与倒排索引把结构从"按行"转向"按列或按词项",收益来自同类型数据的压缩与按需读取。
- 定时结构的取舍是精度、跨度与操作代价。堆提供无精度损失与任意时间跨度,代价是每次操作的对数代价;时间轮把插入与删除降为常数,代价是 tick 决定的精度上限与单圈跨度限制,多级时间轮用层级表达大跨度。定时结构的三个易错点是被取消任务的处理、下推时已过期任务的立即执行、以及时钟跳变后的收敛。
- 近似结构用可控的单向误差换取与元素数量无关的内存。布隆过滤器的假阳性可用于跳过无效读取与拦截穿透,但不能删除;HyperLogLog 用固定内存估算基数且可合并,但不可枚举;Count-Min Sketch 只高估不低估,可用于热点识别与限速计数。误差方向、幅度、删除与枚举能力、容量增长后的重建,是采用近似结构前必须确认的四项。
- 分布式结构的核心问题是让"节点变化"的影响局部化。一致性哈希把迁移范围限制在相邻区间,虚拟节点解决倾斜;固定逻辑分片加映射让扩容变为可控的槽迁移;副本与仲裁用 N、W、R 表达一致性与可用性的取舍;有序 ID 让存储结构的写入集中在局部,减少页分裂与合并范围。
- 组合是工程实现的常态,可观测性是可用性的前提。哈希表加链表得到缓存,堆加反向索引得到可删优先队列,位数组加散列函数得到过滤器,数组加序号加屏障得到高吞吐队列。组合的代价是元数据冗余与同步更新的一致性维护。结构若能暴露命中率、积压量、放大系数与后台动作计数,故障就能在表现为外部症状之前被发现。
工程中结构选择的一般方法可以概括为:先明确当前受哪一项约束的限制(延迟、内存、写入吞吐、恢复时间还是规模),再选择在该约束下代价最低的结构,用指标验证它确实落在预算内,最后在指标证明它是瓶颈时才替换。结构本身不值钱,结构与约束的匹配关系才是。