1当限流、分片与布隆同时失效：一次 DB 被打穿的复合链路
某内容平台在 DAU 突破 3000 万（合成示例）后，对用户画像服务做水平扩容：
将 user_profile 从 8 库扩到 16 库，路由规则从 userId % 8 改为 userId % 16，
同时在 API 网关接入 Sentinel 限流，单 IP QPS 上限 200；Redis 前置层增加 Guava 布隆过滤器，
用于拦截「不存在用户 ID」的恶意扫描，预期将无效查询挡在缓存之外。
变更窗口 T+0，灰度 5% 流量。T+8 min，监控显示 3 号分片 MySQL CPU 飙至 92%， 其余分片负载均衡在 35% 左右——典型的分片热点。 同时网关 429 响应率仅 0.3%，远低于预期，说明限流规则未生效于真实攻击流量： 攻击者使用 2 万代理 IP 轮换，每个 IP 未触发单 IP 阈值，聚合 QPS 已达 4.8 万（合成示例）。
T+15 min，布隆过滤器报「可能存在」的比例从常态 12% 升至 78%。
排查发现：攻击者构造的随机 userId 经哈希后大量落在布隆已登记的正向集合边界附近，
叠加误判率参数按旧 DAU 估算，m/n 比值不足，假阳性的绝对数量被放大。
每条假阳性仍穿透 Redis miss 直打 DB——3 号分片承接了 40% 的 miss 流量（合成示例）。
T+22 min，3 号分片连接池耗尽，画像 API P99 从 45 ms 升至 8 s，下游推荐服务超时熔断。 值班工程师的三个困惑正是本文要拆解的复合模式： 限流上了为何仍被打穿？取模扩容为何制造热点？布隆过滤器为何在攻击下「反向帮凶」？ T+35 min 紧急回滚路由规则、切换用户维度限流、临时调大布隆位数组—— 事后架构组写入结论：三类算法必须联合评审不变量，不能各管一摊。
上述场景折射出一个在《labuladong 算法笔记》中反复强调、却在工程落地中常被忽略的观点： 算法不是面试题，而是在约束下维护不变量的工具。 labuladong 在限流章节用漏桶与令牌桶说明「平滑输出 vs 允许突发」的权衡； 在哈希章节强调「映射函数决定冲突与迁移成本」； 在布隆过滤器章节给出误判率与位数组大小的数学关系—— 架构师的工作是把这三套语言翻译成可观测、可压测、可回滚的工程决策。
版本说明：本文模式层与语言无关，示例基于 Sentinel 1.8.x 流控规则、Redis 7.x Cluster 分片、
Guava 33.x BloomFilter API。算法复杂度与误判率公式来自经典文献与书中推导，
压测数字若无特别说明均为合成示例。
信息截止 2026-08；若你使用 Sentinel 2.x 或 Redis 8.x，流控与 probabilistic 类型语义请以对应版本官方文档为准，机制层结论不变。
阅读前提：你已理解 QPS、连接池、缓存穿透与分库分表基本概念。
本文不再解释「什么是哈希表」，而是聚焦三类结构在失败窗口如何耦合。
60% 篇幅用于框架训练与不变量推导，25% 用于问题迁移练习，15% 留给复合现场与排障顺序。
目标读者为已在生产环境处理过流量尖峰、分片扩容或穿透事故的 P6-P7+ 工程师——
若你尚未独立负责过分库分表变更，建议先通读第 5～6 章再回读第 1 章复合场景，对照 invariant 表做笔记。
对于位数组大小 m、插入元素数量 n、哈希函数个数 k 的布隆过滤器，
近似误判率 p ≈ (1 - e^(-kn/m))^k。
给定目标误判率 p 与预期元素数 n，最优 k ≈ (m/n) ln 2，m ≈ -n ln p / (ln 2)²。
来源：Bloom (1970)；与《labuladong 算法笔记》布隆过滤器章节一致。
1.1 告警时间线：三类信号交织
复合算法事故的识别特征是限流指标、分片负载、布隆命中率、DB 连接池四类信号在同一时间窗重叠。 下表按演练时间线整理（数字为合成示例）：
| 时刻 | 限流侧 | 分片侧 | 布隆 / 缓存侧 |
|---|---|---|---|
| T+0～8 min | 429 率 0.3%，规则按 IP | 16 库负载方差 1.2× | 布隆 pass 率 12% |
| T+8～15 min | 聚合 QPS 4.8 万未拦截 | 3 号分片 CPU 92% | 布隆 pass 率升至 78% |
| T+15～22 min | 切换用户维度限流中 | 连接池等待 > 500 | Redis miss 率 65% |
| T+22 min+ | 全局限流 1.2 万 QPS | 紧急回滚路由 | 临时 m 扩容 2× |
1.2 与单点慢查询的边界区分
| 维度 | 单点慢 SQL（可索引优化） | 复合算法事故（需架构介入） |
|---|---|---|
| 负载形态 | 各分片均匀升高 | 单分片 CPU/连接池异常 |
| 限流指标 | 429 与流量正相关 | 429 低但 DB QPS 高 |
| 根因层 | 执行计划、缺索引 | 路由函数 + 限流维度 + 布隆参数 |
| 修复手段 | 加索引、改 SQL | 联合调整不变量与观测面 |
1.3 现场应急：有序止损
复合算法事故的恢复顺序应为全局限流兜底 → 隔离热点分片 → 回滚路由 → 调参布隆 → 对账： 先在网关启用用户维度或全局限流（即使误伤部分正常用户），再临时将 3 号分片只读或引流至备用库； 路由规则回滚优先于「在线 rehash 修复」，因为错误映射会持续制造新热点； 布隆参数调整需重建位数组，应异步进行而非在 peak 窗口原地扩容。 顺序颠倒——尤其「只加索引不 LIMIT」——往往把穿透变成更贵的慢查询。
1.4 需求翻译：把「加算法组件」改写成 invariant
复盘会上业务方坚持「必须加布隆，书上都说能防穿透」，架构组用 invariant 表完成需求翻译： 「无效 userId 查询不得击穿 DB」可量化为「穿透 DB QPS ≤ 200（合成阈值）」； 「扩容不能停服」可量化为「迁移窗口双写延迟 ≤ 50 ms、读不一致窗口 ≤ 5 min」。 前者需要布隆 + 空值缓存 + 限流联合，后者需要一致性哈希或双写 SOP，而非单纯改 % N。 这一翻译步骤若前置到立项阶段，可避免 70% 的「组件堆叠但 invariant 不成立」（合成经验比例，非统计结论）。 labuladong 在书中反复提醒「先分析题目再动手」——架构评审的第一交付物应是 invariant 表，而非技术选型 PPT。
war room 中架构师还应划定观测冻结窗口：在回滚完成前禁止改 hash 盐值、禁止手工 truncate 布隆、 禁止调大 burst 试图「扛过去」。这三类操作都会让事后对比基线失真，使根因分析无法复现。 与 T19 大促稳定性衔接：算法层事故的时间线往往比业务层投诉早 10～15 min， 若 SRE 面板仅看 HTTP 5xx 而不看 shard CPU 方差与布隆 pass 率，会错失最佳止损窗口。 On-call Runbook 应把「布隆 pass 率环比 +50%」与「单 shard CPU 偏离均值 2×」列为 P2 告警，而非仅盯错误率。
2架构师算法思维：从题型识别到不变量声明
labuladong 在全书开篇强调：刷题的价值在于识别问题类型，而非记忆某一道题的代码。 迁移到架构场景，「题型」对应三类高频工程问题： （1）流量整形——请求速率超过下游承载，需限流/排队/拒绝； （2）数据分片——单机存储或单库 QPS 不足，需映射函数将 key 分散； （3）.membership 近似——需快速判断「元素是否可能存在」，可接受可控误判以换空间。 限流漏斗、分片哈希、布隆过滤器分别是这三类问题的经典解。
2.1 四步框架：识别 → 声明不变量 → 选结构 → 验证观测
- 识别：当前瓶颈是 CPU、连接池、磁盘还是网络？是突发流量还是 sustained 高压？
- 声明不变量：用可测语句写出必须成立的性质，例如「单分片 QPS ≤ 8000」「假阳 DB 查询 ≤ 总请求 5%」。
- 选结构：漏桶/令牌桶/滑动窗口；取模/一致性哈希/范围分片；标准布隆/计数布隆/Scalable BF。
- 验证观测：压测覆盖边界（扩容、攻击、峰值）；监控对齐不变量而非仅看「有没有开开关」。
在工程语境下，推荐默认立场为： 先声明不变量，再选算法结构，最后绑定观测指标。 禁止「因为 Redis 有布隆就加布隆」「因为 Sentinel 文档有例子就配 IP 限流」的配置驱动开发。 与 labuladong「先想清楚题目考什么再写代码」同构——架构评审应看到 invariant 表，而非组件清单。
2.2 工程迁移：从leetcode到生产
书中限流题常问「实现 RateLimiter 接口」——生产还需回答：分布式环境下计数存哪？ 时钟漂移怎么办？拒绝策略是抛异常还是排队？哈希题常问「设计 LRU」—— 生产分片还需回答：扩容时迁移多少数据？热点 key 如何二次散列？ 布隆题常问「实现 insert/query」——生产还需回答：谁重建过滤器？假阳性的业务代价是多少？ 框架训练的核心，是把「实现正确」升级为「在威胁模型下不变量成立」。
| 算法结构 | 书中核心问题 | 工程 invariant 示例 | 首要观测指标 |
|---|---|---|---|
| 漏桶 / 令牌桶 | 平滑输出、允许突发 | 下游 QPS ≤ R，排队 ≤ B | 429 率、队列深度、P99 |
| 取模 / 一致性哈希 | 映射均匀、扩容迁移少 | 分片负载方差 ≤ θ | 各 shard QPS/CPU、rehash 进度 |
| 布隆过滤器 | 空间换 membership | 假阳率 ≤ p，无假阴 | pass 率、穿透 DB QPS |
2.3 与周边架构任务的衔接
限流与 T10 可靠性（熔断、舱壁）、T16 SCA Sentinel 治理面直接耦合—— 限流是舱壁的「入口版」，规则维度必须对齐注册中心中的 resource 名。 分片哈希与 T06 Kafka 分区、T08 ES 分片、T11 缓存热 key 同属「映射函数」问题域—— 换中间件不换思路：都是 hash(key) → bucket。 布隆与 T11 缓存穿透、T12 秒杀非法请求过滤同域—— 误判代价决定 m/n 预算，而非「1% 听起来够小」的直觉。
2.4 识别清单：三问分诊
架构评审收到「性能有问题」时，用三问快速分诊到算法结构： 第一问，流量是持续高压还是瞬时 burst？前者偏漏桶/匀速排队，后者偏令牌桶并严控 B。 第二问，数据访问是点查还是范围扫描？前者 hash 分片，后者 range 分片或二级索引。 第三问，查询 key 是否大概率不存在？若是，布隆前置；若否，布隆收益低且占内存。 三问答案应写入 ADR（Architecture Decision Record），避免半年后无人记得为何选 % 16 而非一致性哈希。
labuladong 算法笔记中的「框架思维」章节列举常见题型模板—— 滑动窗口、前缀和、二分答案——在工程侧有对应物： 滑动窗口对应限流计数；前缀和对应 cumulative quota； 二分答案对应「给定 p 反推 m」的布隆参数搜索。 架构师不必实现 LeetCode 题解，但必须能指出当前生产问题属于哪类题型， 从而复用书中已有复杂度分析与边界讨论，而非从零争论。
3限流漏斗与令牌桶：流量整形的不变量
labuladong 在限流章节对比漏桶（Leaky Bucket）与令牌桶（Token Bucket）： 漏桶以恒定速率出水，超出容量的请求排队或丢弃，适合严格平滑； 令牌桶以恒定速率发牌，桶满时可突发消费多个令牌，适合允许短 burst 的 API。 架构师选型时先问：下游怕的是「平均过高」还是「瞬时过高」？答案决定结构。
3.1 漏桶：恒定输出率
漏桶不变量：任意窗口长度为 T 的输出请求数 ≤ R × T（R 为漏水速率）。
实现可用队列 + 定时器或计数器近似。nginx limit_req 的 leaky 模式、
某些消息中间件的消费 pacing 属于此类。优点：保护下游绝对速率；缺点：无法利用下游空闲容量，
burst 被强制抹平，可能误杀合法突发（如整点秒杀开始 1 s 内的合法峰值）。
《labuladong 算法笔记》在讲解「队列 + 固定出队速率」时与漏桶同构——
架构师应把「消息消费 pacing」与「API 限流」视为同一题型的不同实例，复用同一套 invariant 声明方式。
3.2 令牌桶：允许可控突发
令牌桶不变量：长期平均速率 ≤ 发牌速率 r；瞬时消费 ≤ 桶容量 b + 当前令牌数。
Guava RateLimiter.create(permitsPerSecond) 与 Sentinel 流控中的 QPS 模式在语义上接近令牌桶。
参数 b（burst）设置过大，攻击者可攒牌后一次性打穿；过小则正常业务体验差。
生产常用「r = 下游容量 × 0.7，b = r × 2 s」作为压测起点（合成经验，需按 SLA 重算）。
3.3 滑动窗口：修复固定窗口边界突发
固定窗口计数（每分钟 1000 次）在窗口边界可双倍通过（第 59 s 1000 + 第 0 s 1000）。 滑动窗口（或滑动日志）将窗口划分为多个 sub-window 求和，Sentinel 的匀速排队 + 预热模式与此相关。 不变量：任意连续 W 时间内请求数 ≤ N。代价是内存存 timestamp 或 sub-counter，分布式下需 Redis Lua 原子更新。
| 算法 | 突发处理 | 实现复杂度 | 典型场景 |
|---|---|---|---|
| 固定窗口 | 边界双倍 | 低 | 粗粒度配额 |
| 滑动窗口 | 平滑 | 中 | API 公平限流 |
| 漏桶 | 不允许 | 中 | 下游严格 pacing |
| 令牌桶 | 可控 burst | 中 | 微服务入口 |
团队仅在网关配「单 IP 100 QPS」，未配用户 ID、API Key、全局限流。 分布式攻击每个 IP 低于阈值，聚合流量仍可打穿。 限流维度必须对齐威胁模型：ToC 公网 API 至少「IP + 用户 + 全局」三层，且 429 率应纳入 SLO 告警。
3.4 预热与冷启动：Warm Up 曲线
Sentinel 的 Warm Up（冷启动）模式源于「系统刚启动时间片未打满」的观察： 初始阈值从 coldFactor × count 渐增至 count，避免重启瞬间流量打满冷缓存。 这与令牌桶「桶空时不允许 burst」在效果上部分重叠，但 Warm Up 是时间驱动而非令牌累积。 架构师在变更窗口启用 Warm Up，可叠加 composite 场景中「扩容后缓存冷、DB 易被打穿」的风险—— 合成示例：无 Warm Up 时重启后 30 s 内 DB QPS 为常态 3×；有 Warm Up 时峰值降至 1.4×。
3.5 排队 vs 拒绝：用户体验与 backlog 风险
匀速排队（Uniform Rate Limiter）将超阈值请求排队而非立即 429，适合「可等待、不可失败」的异步任务； 同步 API 读路径应默认直接拒绝，避免 Tomcat 线程被排队占满导致全站阻塞。 labuladong 实现题常忽略队列上限——生产必须设 maxQueueTime 或 maxQueueLength， 否则限流器退化为无界阻塞队列，与 composite 场景「429 低但 P99 极高」的症状一致。
4分布式限流：Sentinel 规则与维度设计
单机 Guava RateLimiter 无法跨 Pod 累计计数。分布式限流需中心化或分片计数器： Redis INCR + EXPIRE、Sentinel Token Server、Envoy 全局限流等。 labuladong 的实现题停在进程内；架构师必须补全「多实例一致性」与「fail-open vs fail-close」。
4.1 Sentinel 流控维度
Sentinel 1.8.x 支持 QPS 与线程数两种 grade；流控效果含直接拒绝、Warm Up、匀速排队。
规则可绑定 resource 名，并通过参数索引做热点参数限流（如按 userId 限 50 QPS）。
与 composite 场景对照：若仅 resource=/profile 全局限流而未开热点，
合法大 V 用户与攻击随机 ID 无法区分——需结合业务标记（新注册、可疑 score）动态调参。
Sentinel 流控规则核心字段：resource、grade（QPS/线程数）、
count（阈值）、strategy（直接/关联/链路）、controlBehavior（拒绝/预热/排队）。
热点参数限流通过 ParamFlowRule 指定 parameterIndex 与 item 例外值。
来源：Sentinel 官方文档 · 流控规则。
4.2 维度矩阵：谁该被限
| 维度 | 防御对象 | 误伤风险 | 建议层级 |
|---|---|---|---|
| 全局限流 | 聚合 DDoS | 峰值活动误伤 | 网关 + 服务双保险 |
| IP | 单源刷接口 | NAT 共享 IP | 网关，阈值从宽 |
| 用户 ID | 账号级滥用 | 低 | 服务入口，热点规则 |
| 租户 / API Key | B 端配额 | 低 | 网关 + 计费对齐 |
4.3 fail-open 与降级
Redis 限流计数器不可用时：fail-open（放行）可能打挂 DB；fail-close（全拒）可能误杀全站。 架构上应分层——网关本地令牌桶兜底 + 远程精确计数；Redis 超时 5 ms 内 fallback 本地。 与 T10 舱壁结合：限流触发后的排队队列需有上限，避免「限流变堆积」导致 OOM。
上线前必须压测三类路径：（1）单 IP 未触发、聚合超阈值；（2）窗口边界双倍请求； （3）Redis 故障时 fallback 行为。监控除 429 率外，看被限流请求的 retry 放大—— 客户端盲目重试会把 429 变成 2× 流量。合成示例：retry 放大系数 1.8 时，有效攻击 QPS = 显示 QPS × 1.8。
4.4 Redis 分布式计数器模式
常用 Lua 脚本实现滑动窗口：以当前 timestamp 为 key 后缀，ZADD 记录请求时间，ZREMRANGEBYSCORE 清理过期， ZCARD 与阈值比较。原子性由 Lua 保证，避免 INCR 与 EXPIRE 之间的 race。 多 key 分片计数器（按 userId hash 到 256 个 Redis key）可降低单 key 热点，但全局限流仍需独立 global key。 与 Sentinel 对比：Redis 方案灵活但需自研规则面板；Sentinel 集成 Spring Cloud 但 Token Server 成为新依赖。 选型看组织是否已有 Redis 集群与 SRE 熟悉度——算法结构相同，差异在治理面与故障域。
4.5 关联限流与链路入口
Sentinel strategy=RELATED 可配置「当关联资源超阈值时限流当前资源」—— 例如 DB 连接池告警 resource 触发 API 只读降级。这与漏桶「保护最弱下游」思想一致。 链路入口（CHAIN）限流仅统计从指定入口进入的调用，适合网关透传后内部服务不重复全局限流。 composite 场景若网关与服务双重全局限流且阈值未对齐，可能出现「网关放行、服务 429」的割裂体验—— 需在 T16 治理规范中统一 resource 命名与阈值比例（合成示例：网关 12000、服务合计 10000，留 20% 给内部调用）。
5分片哈希：从取模到一致性哈希环
labuladong 在哈希相关章节强调：哈希函数将大 key 空间映射到有限桶，冲突与负载均衡由函数质量与桶数量决定。
最简单分片 shard = hash(key) % N：实现零成本，但扩容时 N 变化导致几乎全部 key 迁移。
一致性哈希（Consistent Hashing）通过哈希环减少扩容迁移量——仅相邻区间受影响。
5.1 取模分片的不变量与代价
取模不变量：同一 key 永远映射到 hash(key) % N 的固定 shard（N 不变时）。
N 从 8 变 16 时，约 50% key 改变归属（合成估算：1 - 8/16）。
在线直接改 N 会导致双读不一致——须双写迁移或停写 rehash。
composite 场景中「3 号分片热点」常因：业务 key 非均匀（大 V 用户集中）、
或攻击者刻意构造 hash(id) % 16 == 3 的 id（若 hash 可预测则更危险，应用 HMAC 或加盐哈希）。
5.2 一致性哈希与虚拟节点
将 shard 与 key 均映射到 [0, 2^32) 环上，key 顺时针找第一个 shard 节点。 物理节点少时映射不均——引入虚拟节点（每物理机 100～200 个 vnode）摊平负载。 Redis Cluster、Cassandra、部分 Kafka 分区分配均基于此思想。 不变量：增删节点仅迁移相邻区间 key，迁移量 ≈ 1/N。
5.3 范围分片与混合策略
按 userId 范围 [0,1M) → shard0 适合有序范围查询，但易出热点（最新注册用户集中在最大 range）。
工程常见混合：hash(userId) % N 做 primary 分片，热点 key 加 random suffix 做 secondary 散列。
Kafka 用 partition key；ES 用 routing；思路同构——先识别 access pattern，再选映射。
5.4 哈希函数选型：均匀性与可预测性
labuladong 在哈希章节强调 good hash 应近似均匀——工程上选用 MurmurHash3、xxHash、CityHash 等，
避免 Java Object.hashCode() 在跨语言路由时的不一致。
可预测性是安全维度：若攻击者知悉 hash(id)%16 算法，可构造命中 3 号分片的 id 序列。
对外部不可信 id 应用 HMAC-SHA256(secret, id) 再取模，盐值轮换需与双写 SOP 同步。
Redis Cluster 槽位（16384 slots）本质是固定 N 的一致性哈希工程实现——
读官方文档时应用本文框架理解「slot 迁移」而非死记命令。
5.5 分片数 N 的容量规划
N 并非越大越好：每增一分片，连接池、监控、备份、故障域各 +1。 经验起点（合成）：单 MySQL shard 写 QPS 预算 3000～5000，读 QPS 视缓存命中 1～2 万； 总 QPS 除以单 shard 预算得 N 下限，再乘 1.5～2 预留扩容空间。 N 取 2 的幂次（8/16/32）便于运维心算，但不是算法必需—— 一致性哈希对任意 N 成立，取模分片则 2 幂次 rehash 时部分 key 可留在原 slot（仅当 oldN 整除 newN 时有特殊性质）。
6扩容、迁移与热点：分片哈希的失败窗口
问题推导占本文 25%：当映射函数或 N 变化时，哪些 invariant 会被打破？窗口多长？如何观测？ labuladong 习题很少讨论「在线迁移」——工程上这是分片算法的主战场。
6.1 双写与灰度切读
标准扩容 SOP：（1）新 shard 就绪；（2）写路径双写 old+new mapping；（3）后台迁移历史数据； （4）按 key 范围灰度切读；（5）停止双写，下线 old mapping。 不变量：迁移期间任意 key 至少一个 shard 可读、最终一个 shard 可写。 跳过双写直接改路由，是 composite 场景 3 号热点的外因之一——旧缓存 key 与新 shard 不对齐导致 miss 风暴。
6.2 热点检测与二次散列
监控各 shard QPS 方差：超过 θ（如 2.0）持续 5 min 判定热点。
手段：热点 key 本地缓存（T11）、read replica、或将 key 拆为 key#0…key#k 分散读写。
注意：二次散列破坏范围查询语义，仅适用于 point lookup 场景。
对大 V 用户、超级租户等已知热点，应在路由层白名单分流至独立 shard 或只读副本，
而非依赖 hash 自然均匀——labuladong 习题假设 key 均匀分布，生产 key 空间几乎必然偏斜（Zipf）。
合成示例：top 0.1% userId 贡献 18% 读 QPS 时，即使 hash 完美均匀，业务语义仍会把「头部用户」集中至某些推广活动窗口。
一致性哈希 + 虚拟节点
- 扩容迁移量小，约 1/N
- 适合缓存、KV、对象存储
- 对渐进扩缩容友好
裸取模 % N
- N 变化时大规模 rehash
- 攻击者可试探热点 slot
- 双写窗口长、易不一致
DB 分片从 8→16，Redis 仍用 profile:{userId} 无 shard 前缀。
迁移期 DB 读新 shard、缓存读 old entry，表现为「DB 有数据、接口 404」。
分片变更必须同步缓存 key 命名空间版本（如 v2:profile:{shard}:{userId}）并计划 bulk invalidation。
6.3 迁移进度可观测与回滚判据
双写迁移必须暴露 metrics：rehash_lag_keys、dual_write_conflict_count、
read_from_new_shard_ratio。回滚判据示例：冲突率 > 0.1% 或 lag 在窗口内未下降则 abort。
labuladong 题解不关心进度条——架构师必须定义可自动化判定的终止条件，避免人工「感觉差不多了」上线。
合成示例：1.2 亿 key 迁移，单线程 5000 key/s，理论 6.7 h；并行 8 worker 仍须限流防 DB 过载。
6.4 跨分片查询与聚合的算法代价
分片后 WHERE userId IN (...) 跨多个 shard 需 scatter-gather：
fan-out 到 N 个 shard 再 merge，延迟 = max(shard latency)，QPS 消耗 × shard 命中数。
架构上应尽量避免跨分片事务与跨分片 JOIN——这不是「优化 SQL」能解决，而是 access pattern 错误。
若业务必须「按地区统计用户」，应维护独立汇总表或 ES 索引，而非在线扫全分片。
这与书中「用空间换时间」「预处理」的算法思想一致，只是载体从数组变成物化视图。
7布隆过滤器： membership 近似与参数预算
布隆过滤器是 bit 数组 + k 个哈希函数的概率结构： insert 将 k 个位置置 1；query 若 k 个位均为 1 则「可能存在」，否则「一定不存在」。 无假阴（未插入的元素若 query 为否则一定不存在）； 有假阳（未插入也可能全 1）。 labuladong 用此结构讲解「用可控错误换 O(k) 时间与 O(m) 空间」——架构师需量化「可控」。
7.1 参数 m、n、k、p 的预算
预期元素数 n 必须按峰值而非均值估算：composite 场景中布隆按 DAU 3000 万配参，
攻击流量注入大量「不在集合内的随机 id」，等价于增大 effective n，p 上升。
m 每元素约 10 bit、p=1% 是常见起点（书中示例同量级）；n 翻倍则 m 也需约翻倍以维持 p。
Guava BloomFilter.create(Funnel, expectedInsertions, fpp) 三参数即 n 与 p。
7.2 变体：Counting Bloom、Scalable BF
需删除时用 Counting Bloom（位改为计数器，空间 ×4 或更多）。 元素数持续增长用 Scalable Bloom Filter 或分层 BF。 Redis 7.x 模块 RedisBloom 提供 BF/CF 命令，适合跨进程共享； 进程内 Guava BF 适合嵌入服务、无网络 hop，但各 Pod 副本需同步 rebuild 或接受短暂不一致。
7.3 重建策略
用户集合变更（注册、注销）需定期或增量 rebuild 布隆。 双 BF 切换：build BF_new 完成后 atomic 切指针，旧 BF 保留只读窗口防抖动。 重建窗口若停更，新注册用户可能假阴——须保证新用户写路径 bypass 布隆直写 DB 并回填。
7.4 假阳性的业务代价估算
架构评审常写「误判率 1%」却不算绝对值：QPS 1 万时假阳 100 次/s 直打 DB，若每次 5 ms 则 500 ms CPU/s 仅处理假阳。 当 QPS 升至 5 万（composite 攻击聚合），假阳 500 次/s 可能超过 DB 正常负载——百分比在小数上好看，绝对值在峰值上致命。 应用公式：假阳 QPS = 总 QPS × p × (1 - 真实存在率)。恶意扫描时真实存在率趋近 0，假阳 QPS ≈ 总 QPS × p。 调 p 从 1% 到 0.1%，m 约增 50%（按公式）——这是明确的内存换 DB trade-off，应写入成本表。
7.5 与空值缓存、参数校验的分工
布隆不能替代 API 参数校验：非法格式 id 应在网关 reject，避免无意义 hash 与布隆 query。 空值缓存（cache null with short TTL）处理布隆 pass 后的 miss——二者串联闭合「不存在 key」路径。 T11 多级缓存章节强调穿透三分法——本文布隆是第一道概率挡板，空值是第二道精确挡板，限流是最后一道兜底。 缺任一环节，composite 场景中的攻击模型都会找到最低成本路径。
8工程应用与三算法联合决策
三类结构在真实链路中串联：网关限流 → 布隆拦截无效 id → 哈希路由分片 → DB。 任一层 invariant 失败都会放大下一层压力。框架训练要求能画联合决策树，而非孤立回答三个面试题。
8.1 典型应用场景
- 缓存穿透：布隆挡不存在 key；假阳 miss 后 Redis 空值缓存 + DB。
- 爬虫 URL 去重：布隆 first pass + 精确 Set second pass，亿级 URL 节省内存。
- 秒杀防刷：用户维度限流 + 商品分片 + 布隆挡非法 sku id。
- Feed 去重：Bloom 或 Roaring Bitmap 判断「是否已推」。
| 场景 | 限流 | 分片 | 布隆 | 联合 invariant |
|---|---|---|---|---|
| 用户画像 API | 用户 + 全局 | hash(userId) | 全量 userId 集合 | 单 shard QPS ≤ 8k，假阳 DB ≤ 5% |
| 订单号查询 | 租户配额 | range(时间) | 可选 | 热点租户隔离 |
| 日志 traceId | 采样非限流 | hash(traceId) | 不去重 | 写入均衡方差 ≤ 1.5 |
| 恶意扫描 | IP + 全局 | — | 挡非法 id | 穿透 DB QPS ≤ 阈值 |
8.2 工程迁移练习（labuladong → 生产）
练习 1：书中实现 RateLimiter——补充分布式 Redis 版，并写清 fail-open 策略。
练习 2：实现一致性哈希环——补充 virtual node 数量压测脚本，输出负载方差。
练习 3：实现布隆——给定 n=1e8、p=0.01，计算 m 与 k，并估算 Redis 内存占用。
三题共用一份 invariant 表，是架构评审的可交付模板，也可作为新人 onboarding 的动手实验与验收清单。
| 练习 | 书中输出 | 生产补全项 | 验收标准 |
|---|---|---|---|
| RateLimiter | 进程内令牌桶 | Redis Lua + 降级策略 | 聚合压测 429 生效 |
| 一致性哈希 | 环 + 查找 O(log N) | vnode 数 + 迁移 job | 负载方差 ≤ 1.3 |
| 布隆过滤器 | insert/query O(k) | 双 BF 切换 + 监控 pass 率 | 假阳 DB QPS ≤ 预算 |
听到「QPS 太高」→ 先限流维度与 burst，再谈扩容。 听到「单库撑不住」→ 先 access pattern（点查 vs 范围），再选 hash vs range。 听到「穿透打穿 DB」→ 先算假阳绝对值（p × QPS），再调 m/n；空值缓存与布隆互补，不互替。
8.3 反模式：算法组件堆叠而不联合评审
反模式一：网关限流、服务布隆、DB 分片由三个小组分别上线，无联合压测——composite 场景即由此而来。 反模式二：布隆 假阳后打 DB，DB 无索引——假阳从「便宜 query」变成「慢 scan」。 反模式三：一致性哈希环已上，但客户端仍本地缓存 old 路由表 TTL 24 h——扩容后 24 h 内持续 miss。 架构委员会应对「算法三件套」变更实行联合变更单：任一变更需附 invariant 回归测试报告。
8.4 语言无关的实现边界
本文版本假设「算法工程化，不绑定语言」：Java Guava、Go rate.Limiter、Rust governor、 Nginx limit_req 均可实现同类语义，但分布式一致性与配置热更新能力不同。 选型时比较：规则是否可动态推送（Sentinel Dashboard）、BF 是否跨进程共享（RedisBloom）、 分片路由是否在 SDK 层统一（ShardingSphere）——这些是工程化溢价，不是算法本身。 labuladong 代码用 Python/Java 伪代码——迁移到生产时，优先对齐团队已有中间件，避免为「算法 purity」引入新故障域。
9总结、检查表与延伸阅读
架构师必备算法思维，胜负手不在「会不会写布隆」，而在能否为威胁模型声明不变量并绑定观测。 labuladong 提供的漏斗、哈希、概率结构是工具箱；工程落地需叠加分布式一致性、扩容 SOP 与攻击面假设。 复合现场几乎总是限流维度错误、分片迁移粗糙、布隆参数过期三者交织——先用第 2 章四步框架分诊，再按场景查第 8 章决策表。 与纯理论架构文不同，本文刻意保持 60% 框架训练比重：每一章都应对应「能带走的模板或检查项」， 而非仅建立直觉。这是 execution-plan 对 T17「工程迁移练习」路由的直接体现。
带走三句话：限流防的是聚合流量，维度比阈值更重要； 分片哈希的生命周期在扩容迁移，不在初次上线； 布隆过滤器卖的是假阳预算，攻击流量下 n 会骗过你的参数表。 第四句补记：算法组件单独上线、联合失效——评审时必须三张 invariant 表同屏，而非分三个 sprint 各改一处。 上线前用下列检查表逐项打钩，责任到人——空白项即下一个 composite 事故的温床。
| 检查项 | 标准 | 责任人 |
|---|---|---|
| 限流维度 | 至少全局 + 用户/API Key，IP 仅作辅助 | 网关 Owner |
| burst 参数 | 令牌桶 B 经压测，文档化合法峰值 | 服务 Owner |
| 分片扩容 SOP | 双写 + 灰度切读 + 缓存 key 版本 | DBA / 架构 |
| shard 负载 | 方差 > 2.0 持续 5 min 告警 | SRE |
| 布隆 m/n | 按峰值 n 与 p 预算，攻击场景复算 | 服务 Owner |
| 布隆 rebuild | 双 BF 切换，新用户 bypass 路径 | 服务 Owner |
| 联合压测 | 代理 IP 轮换 + 随机 id 扫描脚本 | QA / SRE |
| fail-open | Redis 限流故障 fallback 策略评审 | 架构组 |
延伸阅读建议先读《labuladong 算法笔记》限流、哈希表与布隆过滤器章节建立实现直觉， 再对照 Sentinel、RedisBloom、Guava 官方文档更新分布式与内存参数语义。 若你来自 T11 多级缓存背景，可把「穿透」与本文布隆章节联读—— 空值缓存解决「已知不存在」的重复查询，布隆解决「首次不存在」的挡板，二者叠加才闭合 invariant。
故障演练建议每季度执行一次「算法联合注入」：同时启动代理 IP 轮换压测、分片只读一台、布隆 stop rebuild， 验证 On-call 能否在 15 min 内完成第 1 章时间线中的止损顺序，并产出书面复盘。 演练通过标准：全局限流生效、热点 shard 隔离、无手工删 BF 误操作—— 与 T19 大促演练共享 Runbook 入口，避免算法层与业务层各练各的、结论无法交叉验证。
最后强调：限流、分片、布隆不是三个可勾选 checkbox，而是同一流量方程的三个变量—— 限流约束入口速率，分片约束单点容量，布隆约束无效请求的 DB 到达率。 变更任一变量而不重算其余两个，invariant 即失效。 完成第 9 章检查表打钩后，建议在预发环境用第 8.2 节三道练习题做参数演算，再批准生产变更窗口。
- BOOK《labuladong 的算法笔记》— 限流、哈希表、布隆过滤器相关章节
- DOCSentinel 1.8.x 官方文档 — 流控、热点参数与降级
- DOCRedis 7.x Probabilistic Data Types — RedisBloom
- DOCGuava Wiki · Hashing & BloomFilter
- PAPERBloom, Burton H. (1970). Space/Time Trade-offs in Hash Coding with Allowable Errors.