专业书籍精读 · System Design Interview 卷二 · 第 6 章
System Design Interview Vol 2 · Ch 6 · Alex Xu & Sahn Lam · 2022
你在手机上刷到一条广告，随手点了一下——就这一下，广告主要为它付钱给平台。全世界每天有十亿次这样的点击。这一章讲的就是：怎么把这十亿次点击，数成一份没人能挑出错的账单。
听上去这不就是「计数」吗，按一下加一，小学生都会。可一旦数字直接变成钱，性质就整个变了：它不是码表上的读数，是收银机里的账。码表少跳一格没人在意；收银机少收一笔，月底就对不上。这一章之所以难，全难在这个身份切换上。
难在三件事。太多：平均每秒一万次、高峰五万次，一台机器数不过来，得拆给几十台一起数、最后再汇总。会迟到：你在地铁里点了广告、信号断了，手机等出了站才把这条记录发出去——它可能晚三分钟，也可能晚三小时。这一下到底该算进「刚才那一分钟」，还是「现在这一分钟」？会重复：网络抖一下，手机没收到确认就再发一遍，同一次点击被数两遍，广告主就被多收了钱。
先记流水账。点击一进来不急着算，先原封不动排成一长队存下来——像超市把每张小票的存根都留着。以后算错了、口径改了，把存根重新过一遍就行。
按分钟分抽屉。不去维护「总数」这么一个一直在变的数，而是给每一分钟准备一个抽屉，每次点击落进它出生的那一分钟。抽屉首尾相接、互不重叠，所以同一次点击不会被数进两个抽屉。
给迟到的留宽限期。一分钟过完不立刻封箱，再多等三分钟——像末班车再等三分钟才开。绝大多数迟到的都赶得上；实在赶不上的，夜里统一补账。
每张小票编号。每次点击出生时就带一个全世界唯一的编号，收下之前先看这个号见没见过，见过就扔掉。这样同一条发一百遍，也只算一次。
快和准在这里是对着干的：宽限期留得越长，迟到的点击追回来越多、账越准，可结果也出得越晚——广告主盯着实时报表调出价，等太久就没法用了。所以行业里常见的做法是两条腿走路：几分钟内先出一份「够用的快数」给人看，夜里再拿全部存根重算一份「准数」去结账，两边一对，差得太多就报警。
代价也得说清楚：这套系统从此永远养着两份数字和一条对账线，运维复杂度比「数一个数」高出一个量级。
数点击不是「计数」，是「记账」。所以它先把每一笔原样存下来，再按分钟分抽屉数、给迟到的留宽限期、给每一笔编号防重复，夜里还要拿原始存根重算一遍来对账——快的那份给人看，准的那份用来付钱。
想进到具体机制、记号和示意图？ → 切到精读版
这一章表面上在做一个计数器，实质是在流处理（stream processing）上做一本会计账。一旦数字直接变成钱，系统的首要属性就不再是吞吐或延迟，而是可对账、可重算、不重不漏。作者借这道题，把流处理里最硬的三件事——事件时间与水位线、恰好一次语义、热点分区——按「正确性优先」的顺序串了一遍。
本章是 Vol 2 的第 6 章，紧接 Ch4（亲手造一个分布式消息队列）与 Ch5（监控告警的时序写入）：前者给了这一章赖以生存的可重放日志，后者给了按时间窗口聚合海量写入的套路。但它多加了一条前两章都没有的约束——结果要能拿去结账。现实里它对应 Google Ads、Meta Ads 的计费与报表管线，以及 Kafka + Flink + Druid/Pinot 这条今天近乎行业默认的实时数仓链路。
先把规模摆上桌。书里给的量级是：每天 10 亿次点击、在库广告 200 万个。10 亿 ÷ 86400 ≈ 平均 1 万 QPS；按峰值取平均值的 5 倍，峰值 5 万 QPS。单条点击事件约 0.1 KB（广告 id、时间戳、用户 id、IP、国家），于是每天约 100 GB 原始数据、每月约 3 TB。
要交付的东西有两类：查某个 ad_id 最近 M 分钟的点击数，以及每分钟给出点击最多的 Top 100 广告，都要支持按 IP、用户、国家过滤。端到端延迟要求是「几分钟以内」——不需要毫秒，但也不能等到第二天。
真正给这道题定调的，是非功能需求里那一句：这份数据要拿去计费。少算，平台白送广告主曝光；多算，是向客户超收，属于合规与信任问题。后面几乎每个设计选择——为什么必须落原始日志、为什么用事件时间、为什么非要恰好一次——都能从这一句倒推出来。说白了：监控指标掉几个点没人会打官司，广告账单错一分钱会。
点击事件不直接打进数据库，而是先进 Kafka。理由不止是削峰填谷：这条日志是全系统唯一的真相。原始事件同时旁路落一份到对象存储（S3 / HDFS），保留期以月计——所有重算、对账、口径变更，都靠把它重新过一遍。
书里还有一个容易被跳过的设计：聚合结果不直接写库，而是先写进第二道队列。因为一次消费要同时做两件事——把结果落盘、把消费位置（offset）往前推——它们跨了两个系统，天然不是原子操作，崩在中间要么重复计数、要么丢数。加一道队列，就把「原子性」收敛到一处（队列的事务提交），下游写库那段做成幂等的，重放也不会写错。
计算本身是 MapReduce 的形状，只是跑在流上：map 节点做校验、清洗、打标（比如把 IP 翻成国家），再按 ad_id 哈希把事件分发出去；aggregate 节点在内存里维护「每个 ad_id 每分钟的计数」；reduce 节点把各聚合节点的局部结果合并，算出全局 Top N。
给个量级感受为什么这能成立：200 万个 ad_id，每分钟一行计数（id 加计数不过十几字节），一分钟的完整计数表也就几十 MB 级，单机内存轻松装下；Top 100 用容量 100 的小顶堆维护，扫一遍 200 万条是 O(n log 100)——log 100 不到 7，等于乘了个常数，不是瓶颈。真正的瓶颈永远在「分区均不均匀」和「状态能不能可靠地存下来」，不在算力。
一条点击有两个时间：它发生的时刻（事件时间，由客户端打在数据里）和它被系统收到的时刻（处理时间）。
用处理时间实现起来简单得多——不用等、不用缓存乱序数据、窗口一到点就封箱。但它会把「用户在地铁里点了一下、出站后手机才补发」这类事件记进错误的分钟，跨零点时甚至记进错误的账单日。对报表这叫误差，对账单这叫错账。所以本章选事件时间。
代价是必须正面面对乱序：事件时间 12:00:30 的点击，可能 12:03 才到。解法是水位线——窗口的名义边界过去后，再多等一段才封箱结算。这是一场明码标价的赌：等 3 分钟，绝大多数迟到事件追得回来，代价是端到端延迟从 ~1 分钟变成 ~4 分钟；等 30 分钟，追回的增量已很小，延迟却让实时报表失去意义。而且水位线永远兜不住底——真正处理「迟到几小时」的是下面那条批处理回补线。
滚动窗口（tumbling window）把时间切成首尾相接、互不重叠的格子，一分钟一个。计费只能用它：窗口一旦重叠，同一次点击就会落进两个窗口被算两次。滑动窗口（sliding window）每次向前挪一小步、彼此大面积重叠，适合「最近 5 分钟最热的广告」这类问题。
实践上有个便宜的取巧：流里只算滚动窗口并落进 OLAP 库，「最近 M 分钟」在查询时把 M 个一分钟格子加起来——把滑动窗口的成本从「常驻内存维护」挪到「查询时求和」。
表 1 · 三档投递语义，以及这道题为什么必须选最贵的那档
| 语义 | 含义 | 代价 | 这道题能不能用 |
|---|---|---|---|
| 至多一次 | 不重试，失败就丢 | 最便宜、最快 | 不行——丢了就是少收钱 |
| 至少一次 | 失败就重试，可能重复 | 便宜；但结果会偏大 | 单独不行，必须配去重 |
| 恰好一次 | 结果等价于只处理了一次 | 吞吐下降、延迟随检查点抖动 | 必须——账不能错 |
要澄清的是：「恰好一次」从来不是指消息只在网络上传了一次。传输该重复还是会重复，它保证的是最终落到结果里的效果等价于只处理了一次（end-to-end exactly-once）。实现上两条路：
16 GB，必须带过期时间、按时间窗口分片，到期整片丢弃。有人想用布隆过滤器（Bloom filter，用少量内存判断「这个值见没见过」的概率结构）压缩去重成本——小心：它有假阳性，会把没见过的点击误判成重复丢掉，落在计费上就是少算钱。只能做前置粗筛，判成「可能重复」的再去精确存储查一次。
按 ad_id 哈希分区，前提是流量在各个 ad_id 之间大致均匀。广告业务偏偏不是：一个超大广告主搞一次大促，就能把单个分区的流量打到平均值的几十倍，而一个分区只能由一个消费者处理，加机器也救不了它。
标准解法是两段聚合：给热点键加随机后缀，把 ad_id 拆成 ad_id:0 … ad_id:N 散到 N 个分区各自局部计数，再由第二段把这 N 份加起来。代价有三：多一层合并的延迟、要动态识别哪些键是热点（今天的热点明天可能不是）、拆分因子 N 本身还得随流量调整。
流式结果是「快的那一份」。系统另外每天跑一次批处理，从对象存储的原始日志把昨天重算一遍，与流式结果逐广告比对，差异超阈值就报警，并以批处理结果为准结账。
同一条原始日志还支撑重算（recalculation）：口径改了、发现了 bug，就从某个时间点起把日志重放进一张新表，验完再切过去——不用改历史结果，也不用停机。这正是 Kappa 架构的做法：不维护两套代码，而是维护一条可重放的日志。
这一章的所有权衡，最后都收敛到同一条轴上：准确性 ↔ 延迟 ↔ 成本，三者不可能同时最优——这也正是 Google Dataflow 论文标题里并排的那三个词。
表 2 · 两条架构路线：Lambda vs Kappa
| Lambda（批 + 流两条线） | Kappa（单流 + 可重放日志） | |
|---|---|---|
| 正确性 | 批线是权威，最终一定对 | 靠重放同一条日志得到同样结果 |
| 代码 | 同一套逻辑写两遍，两边口径长期必然漂移 | 一套逻辑；改逻辑 = 重放一次 |
| 延迟 | 快线分钟级，权威结果 T+1 | 分钟级；重算按需触发 |
| 成本 | 两套集群、两套运维 | 一套集群，但日志保留期越长越贵 |
| 适合 | 强监管、必须有独立权威口径 | 多数实时分析场景；本章主推 |
本章推荐 Kappa，但保留一条每日批处理对账线——严格说这是「Kappa 为主 + 批处理当审计员」，真实广告公司大多也停在这个位置。
表 3 · 水位线该等多久（本章场景：日均 10 亿点击，端到端要求几分钟）
| 宽限期 | 能兜住什么 | 端到端延迟 | 代价 |
|---|---|---|---|
3 秒 | 只够兜网络抖动 | < 1 分钟 | 迟到率高，账不准，只配做监控面板 |
3 分钟 | 绝大多数移动端补发 | ~4 分钟 | 收益 / 延迟的甜点，本章取值 |
30 分钟+ | 边际收益已经很小 | 半小时以上 | 实时性丧失，报表失去意义 |
| 不设，交给批处理 | 100% 覆盖 | T+1 | 没有实时性；日终结算必须有这一层 |
还有两条不上表的判断：
这道题是「正确性优先的流处理」的标准样板，面试真正考的也是这一点：面试官想看你会不会在说完「用 Flink 做窗口聚合」之后，主动补一句「但这份数是要结账的，所以我需要事件时间、需要恰好一次、需要一条对账线」。选型上这条链路今天几乎固化成了 Kafka（日志）+ Flink（有状态流处理）+ Pinot / Druid / ClickHouse（OLAP 查询）+ S3 / HDFS（原始数据与批处理对账）。
3 TB。① 题眼不是「数得快」，而是「数得能拿去结账」——非功能需求里「用于计费」那一句，倒推出后面所有设计。
② 量级：每天 10 亿点击、200 万广告 → 平均 1 万 QPS、峰值 5 万 QPS、每天约 100 GB、每月约 3 TB；端到端要求几分钟。
③ 先落一条可重放的日志（Kafka + 对象存储），它是全系统唯一真相；聚合结果先写第二道队列，把原子性收敛到一处。
④ 计算是流上的 map–aggregate–reduce：按 ad_id 哈希分发、内存里按分钟计数、小顶堆合并 Top N；瓶颈在分区均匀性与状态可靠性，不在算力。
⑤ 计费必须用事件时间，代价是乱序，靠水位线多等几分钟封窗——水位线是赌注，不是保证。
⑥ 计费只能用滚动窗口（不重叠）；「最近 M 分钟」在查询时把 M 个一分钟格子加起来即可。
⑦ 恰好一次指的是效果：两条路——事务 / 两阶段提交，或至少一次 + UUID 幂等去重；后者的隐藏成本是去重存储（10 亿键/天）。
⑧ 热点广告主会打爆单分区，用加随机后缀的两段聚合打散再合并。
⑨ 压舱石是每日批处理对账 + 可重放重算：快的那份给人看，准的那份用来结账。