# 第 4 章：去重

> 重发带来了重复，服务器怎样认出“这条我已经存过了”？

深入理解 IM 系统 · https://im.liko.page/zh/duplicates/

第 3 章最后，Ben 看到 Ana 的“我到楼下了”出现了两次。

这是第 3 章的修法带来的：消息到了，服务器回的确认在路上丢了；手机以为没送到，又发了一次，服务器就存了两份。按全书 10% 的丢包算，约 10% 的消息会这样（有的被存了三份，平均每 100 条多出约 11 份）；真实的比例小得多，但 v1 每天 400 万条消息，哪怕只有 0.1% 重复，每天也是 4,000 条。

重发是对的，不能不发。要解决的是另一件事：**服务器收到一条它已经存过的消息时，怎么认出来。**

## 1. 看它坏掉

下面是第 3 章那组 8 条消息，用的是“等确认、没确认就重发”，这次加上了 Ben 看到的那一行：

*（互动图：请在网页上查看 https://im.liko.page/zh/duplicates/）*

在“不去重”下，7 号的确认丢了，重发的那份也被存下，Ben 看到两条 7 号。再勾上“App 被杀，一小时后从发件箱补发 3 号”：这是另一种真实的情况，App 发出 3 号后被系统杀掉，没来得及等到确认，下次打开时从发件箱里把它又发了一遍。Ben 又多看到一条 3 号。

先看两个“显然的办法”为什么不行：

- **看发送者和内容**：同一个人、同样的话、几秒之内，就当作重复？可 Ana 真的会连发两个“好”。把用户真心发的第二条吞掉，比显示两条更糟。
- **用服务器分配的 id**：服务器存下消息时会给它一个 id，可这个 id 是写在确认里发回手机的，而丢掉的恰恰就是这个确认。手机重发时，手里根本没有它。

## 2. 修好它：手机给每条消息起一个 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`](https://docs.stripe.com/api/idempotent_requests)，同一个键重复提交，只会扣一次钱。它也有窗口：[文档](https://docs.stripe.com/api/idempotent_requests)说键至少保存 24 小时，过期以后再用同一个键，就当作新请求。
- **Telegram**：发消息的接口带一个客户端生成的 [`random_id`](https://core.telegram.org/method/messages.sendMessage)，文档写明它就是用来防止消息重复发送的，和这一章的客户端消息 ID 一样。更底下一层，MTProto 的每个数据包也带 `msg_id`，[协议要求](https://core.telegram.org/mtproto/description)收方记住最近 N 个，再来一个相同的、或者比记住的都小的（`msg_id` 随时间递增，更小就说明更老），直接忽略：这是同一个“记住最近的 ID”，只是用在传输这一层。

**实践中**：作者以前做的系统里，去重用的是两个唯一 ID：一个是 IM 系统内部的消息 ID，就是这一章讲的；另一个是业务自己的 ID。比如业务系统通过服务端接口发一条通知，调用超时后自己又重试了一次：在 IM 看来这是两次新的发送，消息 ID 也不一样，只有业务自己的 ID 能认出“这是同一件事”。两层各管一段：IM 的 ID 挡住网络上的重发，业务的 ID 挡住业务自己的重试，和 Stripe 的幂等键是同一个道理。

## 6. 这一章的决定

*（互动图：请在网页上查看 https://im.liko.page/zh/duplicates/）*

**决策卡**

- 问题：第 3 章的重发会让同一条消息被存好几次，Ben 看到重复。
- 选择：手机在第一次发送前生成消息 ID，重发时不变；服务器记住最近见过的 ID（写入成功后才记），重复的不存、原样再回一次确认；数据库里“发送者 + 消息 ID”是唯一键，兜住更晚的和同时到达的重复。
- 代价：多一个唯一索引，重复时多一次查询；ID 要由手机保证不撞。
- 什么时候重新考虑：再回的确认还要带上原来的序号（第 5 章）；消息服务拆成多台、ID 要分开记时（第 27 章）；确认改成“写进日志就回”以后，去重要在写日志之前做（第 28 章）。
- 其他答案：先向服务器要 ID（多一个来回，问题不变）；支付接口的幂等键（同一个思路）；Telegram 的 random_id（同一做法）。

到这里，发送这一边的消息不丢、不重了。下一章：Ana 和 Ben 几乎同时发了一句话，两个人看到的顺序却不一样。