第 4 章
去重
重发带来了重复，服务器怎样认出“这条我已经存过了”？
第 3 章最后，Ben 看到 Ana 的“我到楼下了”出现了两次。
这是第 3 章的修法带来的：消息到了，服务器回的确认在路上丢了；手机以为没送到，又发了一次，服务器就存了两份。按全书 10% 的丢包算，约 10% 的消息会这样（有的被存了三份，平均每 100 条多出约 11 份）；真实的比例小得多，但 v1 每天 400 万条消息，哪怕只有 0.1% 重复，每天也是 4,000 条。
重发是对的，不能不发。要解决的是另一件事：服务器收到一条它已经存过的消息时，怎么认出来。
1. 看它坏掉
下面是第 3 章那组 8 条消息，用的是“等确认、没确认就重发”，这次加上了 Ben 看到的那一行：
服务器收到一条它已经存过的消息，怎么才能认出来？
服务器存下认出来，不存，再回一次确认Ben 看到的重复
- Ben 看到
- –
- 重复的
- –
- 认出来没存的
- –
在“不去重”下，7 号的确认丢了，重发的那份也被存下，Ben 看到两条 7 号。再勾上“App 被杀，一小时后从发件箱补发 3 号”：这是另一种真实的情况，App 发出 3 号后被系统杀掉，没来得及等到确认，下次打开时从发件箱里把它又发了一遍。Ben 又多看到一条 3 号。
先看两个“显然的办法”为什么不行：
- 看发送者和内容：同一个人、同样的话、几秒之内，就当作重复？可 Ana 真的会连发两个“好”。把用户真心发的第二条吞掉，比显示两条更糟。
- 用服务器分配的 id：服务器存下消息时会给它一个 id，可这个 id 是写在确认里发回手机的，而丢掉的恰恰就是这个确认。手机重发时，手里根本没有它。
2. 修好它：手机给每条消息起一个 ID
- 客户端消息 ID消息 IDmessage ID客户端在发送之前给每条消息生成的唯一 ID，重发时不变。服务端靠它认出重发的消息。在术语表里查看（不是服务器存下时给的那个 id）由手机在第一次发送之前生成，不用问服务器：最简单的是 128 位的随机数；也可以用“设备 + 自增计数”，但计数器要和发件箱一起存在磁盘上，App 重启、重装以后也不能从头再数。它和消息一起放在发件箱里（存在磁盘上，第 3 章），之后的每一次重发，包括 App 重启后的补发、用户看到“!”以后手动点的重发，带的都是同一个 ID。这个 ID 只要在同一个发送者内部不重复就够了，所以服务器认的是“发送者 + 消息 ID”。
- 服务器记住最近见过的 ID。再来一条带同样 ID 的，就不再存，而是原样再回一次确认，带上第一次存下时的服务器 id（第 5 章起还有它的序号）。这样手机最后的状态，和第一次的确认没丢时一模一样。
在上面的模拟器里切到“记住最近的 ID”：7 号的第二份被认了出来，标成“见过”，Ben 只看到一条。
3. 估算：要记多久、记多少
- 按模拟器的重发时间表（第 3 章：最后一次在第 15 秒，第 31 秒放弃），服务器把 ID 记 32 秒就够。v1 高峰每秒 139 条消息：139 × 32 ≈ 4,400 个 ID，每个按 32 字节算（ID 本身 16 字节，加上发送者和时间），一共约 142 KB。
- 真实的 App 断网时会一直等着、连上后再补发（第 3 章），重发可能在几分钟后才到，所以真实的窗口要按重连的时间来定，比如 5 分钟：139 × 300 ≈ 4.2 万个 ID、约 1.3 MB。哈希表本身的开销会让它再大两三倍，仍然微不足道，放在内存里就行。
- 到 v3，高峰每秒 13,900 条：32 秒是约 44 万个 ID、14 MB；5 分钟是约 420 万个 ID、133 MB，分在多台消息服务器上（第 27 章），每台只占一小份。
- 模拟 10,000 条消息（不含一小时后的补发）：不去重时，Ben 看到 1,113 条重复（11.1%）；记住最近 32 秒的 ID，一条不剩。
4. 窗口的漏洞，和真正的保证
再看那条“一小时后补发”的 3 号：它来的时候，服务器早就不记得 3 号了，于是又存了一份。比窗口更晚的重复，窗口挡不住。这种情况并不少见：
- App 发出消息后被系统杀掉，一小时后才重新打开，从发件箱里补发；
- 第 3 章说过的“显示失败、其实已存”：最后一次的确认丢了，用户看到红色的“!”，点了重发。
所以真正的保证放在数据库里：给“发送者 + 消息 ID”加一个唯一键。服务器照常写入；如果这条是重复的，写入会因为唯一键冲突而失败，服务器就知道“存过了”，再把原来那条查出来，回同样的确认。最近 ID 的窗口还留着，但它只是一条快路径：绝大多数重复都在几秒内到，在内存里就能认出来，省掉一次注定失败的写入和随后的那次查询。
还有一个并发的细节：同一条消息的两份，可能同时到了两个线程甚至两台服务器上，“先查窗口、再写入”会两边都以为没见过。所以最终拍板的永远是唯一键：两个写入只有一个成功，另一个撞上冲突，转去查原来那条。ID 也要等写入真正成功以后才放进窗口，否则写入失败时，下一次重发会被误认成“见过”而丢掉。
切到“唯一约束”：一小时后的 3 号也被认了出来。
代价：
- 每次写消息，多维护一个唯一索引；碰上重复时，多一次查询。
- 去重全靠手机守规矩：ID 不能撞（随机位数要够，或者计数器真的存住了），重发时也不能换 ID。
5. 其他答案
- 先找服务器要一个 ID，再发消息：每发一条都多一个来回；而且“要 ID”的那个请求一样会丢，问题只是往前挪了一步。
- 每台设备一个递增序号：服务器只记每台设备最大的序号，不大于它的就是重复，一个数字就代替了整个窗口。代价是手机必须严格按顺序发：4 号还在重发时 5 号不能先存，否则 4 号再到时会被当成重复丢掉；而第 3 章的发件箱是好几条一起在路上的。XMPP 的流管理（XEP-0198）用的就是这种按顺序的计数。服务器给每个会话分配的序号是另一回事，管的是顺序，第 5 章讲。
- 支付接口里的幂等键：同一个思路。比如 Stripe 的 API，请求头里带一个
Idempotency-Key，同一个键重复提交，只会扣一次钱。它也有窗口：文档说键至少保存 24 小时，过期以后再用同一个键，就当作新请求。 - Telegram：发消息的接口带一个客户端生成的
random_id，文档写明它就是用来防止消息重复发送的，和这一章的客户端消息 ID 一样。更底下一层，MTProto 的每个数据包也带msg_id，协议要求收方记住最近 N 个，再来一个相同的、或者比记住的都小的（msg_id随时间递增，更小就说明更老），直接忽略：这是同一个“记住最近的 ID”，只是用在传输这一层。
实践中：作者以前做的系统里，去重用的是两个唯一 ID：一个是 IM 系统内部的消息 ID，就是这一章讲的；另一个是业务自己的 ID。比如业务系统通过服务端接口发一条通知，调用超时后自己又重试了一次：在 IM 看来这是两次新的发送，消息 ID 也不一样，只有业务自己的 ID 能认出“这是同一件事”。两层各管一段：IM 的 ID 挡住网络上的重发，业务的 ID 挡住业务自己的重试，和 Stripe 的幂等键是同一个道理。
6. 这一章的决定
到这里，发送这一边的消息不丢、不重了。下一章：Ana 和 Ben 几乎同时发了一句话，两个人看到的顺序却不一样。