# 第 5 章：顺序

> 只有一台服务器、一个自增 id，Ana 和 Ben 看到的顺序为什么还会不一样？

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

Ana 和 Ben 聊得正热。Ana 发了一句，几乎同一刻 Ben 也发了一句。过了一会儿两人发现对不上：Ana 的屏幕上她那句在上面，Ben 的屏幕上他那句在上面。

这有点奇怪。v1 还是只有一台服务器，消息写进一张表，id 自增（第 1 章）。id 只有一个顺序，所有人看到的应该一样才对。这句话对服务器成立，对屏幕不一定：**屏幕上的顺序，是手机自己排出来的。** 这一章看手机怎么排、哪里会排错，以及 id 还缺了什么。

这一章有一个前提：每条消息在服务器上**只存一份**，就是第 1 章 `messages` 表里的一行，用 `conversation_id` 标明属于哪个会话；会话是服务器上的东西，Ana 和 Ben 读的是同一份。所以“一个会话一个顺序”才说得通。别的存法也很常见：每人一个信箱、各存一份（第 6 章加上信箱，第 10 章比较两种存法）；会话列表由手机自己拼，还是由服务器管（第 17 章）。存法变了，编号的单位也可能跟着变，比如 Telegram 的私聊用的是每个用户一条序列（见第 5 节）。

## 1. 看它坏掉

模拟器里，Ana 和 Ben 在 12 秒里一共发了 7 条消息（A1 是 Ana 的第一条，B1 是 Ben 的第一条）。规则和前两章一样：每一程丢 10%，没等到确认就重发（第 3 章），重发的不会存两份（第 4 章）。服务器按存下的先后给消息编号，再推给对方；推送也会丢。手机用的是到现在为止最自然的做法：**自己发的立刻显示在最下面，别人的推过来就接在后面。**

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

下面三栏是最后每块屏幕上的样子，中间是服务器的顺序。默认这一组里，三件事各发生了一次。

**两人同时发。** Ana 在 6.78 秒发 A3，Ben 在 6.83 秒发 B3，只差 50 毫秒。A3 先存下。可 Ben 的手机在 6.83 秒就显示了 B3，A3 的推送 6.98 秒才到，接在 B3 下面。Ben 的屏幕上是 B3、A3，服务器和 Ana 那边是 A3、B3。

**重发的晚到。** Ana 在 5.04 秒发 A1，路上丢了，1 秒后重发才存下；5.51 秒发的 A2 一次就到，反而先存。服务器的顺序是 A2、A1，Ana 自己的屏幕是 A1、A2。第 3 章预告过这件事。

**推送丢了，没人发现。** 推给 Ben 的 A2 丢了：服务器以为连接还活着，写了进去，字节却再也没到（第 2 章）。Ben 能发现吗？他手上最大的 id 是 B2 的 1012，下一条到的是 A1，id 1016。中间跳过的三个号里，1013 是 A2，1014 和 1015 是别的会话的消息。**id 只管顺序，不管连续**（第 1 章），跳号是常态，所以手机没法把“跳了号”当成“丢了消息”，只能等下一次重连时的拉取（手机主动去问服务器要）补上。在那之前，Ben 的对话少一句，而他不知道。

等 Ana 下次打开这个对话，App 按 id 重新加载，A1 和 A2 会突然换个位置：聊天记录自己变了。

第 1 章还留了一个洞，模拟器没有画：id 在插入时分配，提交后才看得见，两者的先后可能不一致。第 3 节修它时再细说。

## 2. 估算

**多常见？** 一条消息会和别人的“撞车”，是因为它发出前的一个来回里，别人刚发了一句：那句已经存下，推送还没到。假设群里聊得正热，别人平均每 2 秒说一句（每秒 0.5 句），手机网络一个来回 0.2 秒：

- 你的一句撞上别人的，概率约 0.5 × 0.2 = **0.1**，十句里一句。模拟两个人各自每 2 秒一句、共 9,952 条消息，不丢包时，每 100 条有 **9.3 对**在某一方屏幕上和服务器相反。
- 信号差、一个来回 1 秒，同样算是 0.5 × 1 = **0.5**（这么大时乘法会偏高，但大约每两句就有一句撞上）。重发会让窗口更宽：按全书 10% 的丢包，每 100 条是 **19.6 对**。

一对一的聊天里，人们多半看到对方那句再回，撞车少得多。

**会缺多少？** 每丢一次推送，对方屏幕上就缺一条，直到下次拉取。按 10% 算，每 100 条消息缺 **10.0 条**。真实的推送丢得少得多，但和第 3 章一样：比例小，乘上每天 400 万条，就不是小数目。

## 3. 修好它

### 第一步：按服务器的号排，发送中的留在最下面

撞车和重发，原因是同一个：手机按“我什么时候看到它”排，而不是按服务器给的顺序。改法：

- 每条消息按服务器的编号排。推送带着编号；自己发的，确认（第 3 章）带回编号；重复那条的确认，带的是原来的编号（第 4 章）。
- 还没确认的消息（发送中、失败）没有编号，**统一放在最下面**，按发送的先后排。确认一到，它就挪到自己的位置。

在模拟器里切到“按 id 排”：两块屏幕和服务器的顺序一样了（Ben 还少一条 A2）。Ben 那边，B3 在发送中，A3 推来时放在它上面；B3 的确认到了，编号比 A3 大，不用动。Ana 那边，A1 和 A2 都在发送中，A2 先确认，跳到了 A1 上面。

要说清楚：**这一步用 id 就够了。** 只有一台服务器时，id 已经是大家都认的顺序，只是屏幕没用它。代价是自己的消息会挪：不丢包时（模拟器里）一次也不挪（发送中的一直在最下面，别人的只会插到它上面）；按 10% 的丢包，每 100 条里有 **15.8 条**自己的消息挪过。

可 Ben 仍然缺 A2，仍然不知道。这一步 id 做不到。

### 第二步：每个会话一个连续的序号

要让手机知道“缺了一条”，编号就得**在这个会话里连续**：1、2、3……别的会话不占这里的号。这就是序号（seq）。

服务器端只多一个字段：会话表里记着这个会话最后用到的序号。写一条消息时，在**同一个事务**里（PostgreSQL，默认的 READ COMMITTED 隔离级别）：

```sql
BEGIN;
UPDATE conversations SET last_seq = last_seq + 1 WHERE id = :conv RETURNING last_seq;
-- :seq 就是上一句 RETURNING 回来的 last_seq
INSERT INTO messages (conversation_id, seq, sender_id, msg_id, text) VALUES (:conv, :seq, ...);
COMMIT;
```

`messages` 表上再加一个唯一键（会话, seq）。（若用 REPEATABLE READ，同一行的第二个写入者会报序列化错误、要重试；MySQL 没有 `RETURNING`，常用 `last_seq = LAST_INSERT_ID(last_seq + 1)` 再取 `LAST_INSERT_ID()`。）

`UPDATE` 给这一行会话加了**行锁**，直到提交才放开：同一个会话的写入者排队轮流拿号，别的会话用别的行，互不等待。再看第 1 章的那个洞：

- 事务 T1 拿到 id 101，还没提交；
- 事务 T2 拿到 102，先提交了；
- Ben 的手机来拉 `after=100`，只看得见 102，把 `after` 记成 102；
- T1 提交，101 再也不会被拉到。

有了行锁，同一个会话里 T2 要等 T1 提交才能拿号，**在一个会话里，序号的先后就是提交的先后**。重连时按 id 的拉取还留着这个洞，到第 6 章才换掉；但被跳过的消息，现在会在之后的序号跳号时露出来。

手机这边，每个会话记着自己连续拿到了第几号：

- 有 1 到 5，来了 6，接上。
- 有 1 到 5，来了 8：**6 和 7 缺了**，去拉“这个会话 seq 6 到 7 的消息”。
- 自己消息的确认带回的序号也算：Ana 的确认带回 7，而她只有 1 到 5，那 6 就是缺的。

补拉之前先等一小会儿（模拟器里 0.5 秒）。一条 TCP 连接本身是按顺序的，但服务器那头可能是不同的线程在各自提交以后推送，后提交的 8 可能先推出去，6 和 7 紧跟着就到。模拟器里推送从不乱序，所以这里的等待只是让补拉晚 0.5 秒。

切到“按序号排，跳号就补拉”：Ben 在 6.24 秒收到 A1，序号 #4，而他只有 #1、#2。等了 0.5 秒 #3 还没来，6.74 秒去拉，6.94 秒 A2 就回来了，排在 A1 上面。按 10% 的丢包模拟 9,952 条消息，“缺了没发现”从每 100 条 10.0 条降到 **0.01 条**。剩下的是丢了推送的**最后一条**：它后面没有新消息，就没有跳号可看。

这个会话自己的游标（手机记着这个会话拿到了第几号）现在也可以跟着连续的推送往前走了。重连时的拉取仍按第 2 章的 `after=<id>`，到第 6 章才改。

## 4. 代价

- **一个会话的写入要排队。** 存储正常时一次写入约 5 毫秒，一个会话每秒最多 1 ÷ 0.005 = **200 条**；存储变慢到 500 毫秒一次时，只剩**每秒 2 条**。不同会话的行互不争抢。v3 的麻烦不在某个会话，而在一台服务器要给所有会话发号，每秒 13,900 条（第 27 章）。
- **自己的消息会挪。** 另一种做法是发件箱在同一个会话里一条一条地按顺序发：前一条没确认，后一条不发。自己的顺序不会乱，代价是一条丢了，后面的都跟着等，至少多一个超时。
- **最后一条丢了推送，看不出来。** 要等下一条消息，或者下次拉取（第 6 章）。
- **序号不能凭空跳。** 这里的号在写入的事务里分配，事务失败就一起回滚，不留空洞。以后号如果在事务之外分配（第 27 章），就可能有一个号永远没有消息；手机来拉，服务器要明确回答“6 号不存在”，手机跳过去，而不是一直问。

| 资源 | 按到达的顺序 | 按序号排 |
|---|---|---|
| 服务器磁盘 IO | 每条消息一次插入 | 同一个事务里多更新一行会话、多维护一个索引；落盘次数不变 |
| 手机请求 | 缺的消息要等下次拉取 | 每次跳号一个补拉请求（10% 丢包时每 100 条消息 13.4 次；真实网络少得多） |

## 5. 其他答案

- **按时间排**：要两台机器的时钟对得上，还要处理同一毫秒的两条消息；只用服务器自己的时钟，在一台服务器上和 id 一样能用，也一样看不出缺了哪条。
- **Lamport 时钟**（[Lamport, 1978](https://lamport.azurewebsites.net/pubs/time-clocks.pdf)）：没有中心发号时，每个参与者自己计数，收到别人的计数就把自己的调得比它大，排出的顺序不违反因果。IM 本来就有服务器在中间，直接让它发号更简单，而且 Lamport 时钟的数会跳，看不出缺号。
- **Telegram 的 `pts`**：[文档](https://core.telegram.org/api/updates)里，每个事件（新消息，也包括编辑、删除）都带一个自增的 `pts` 和 `pts_count`。客户端检查“本地 pts + pts_count”是否等于新的 `pts`：相等就应用，更大说明应用过、忽略，更小就是有空缺，**可以先等最多 0.5 秒**（服务器可能把更新乱序发出），还缺就调用 `updates.getDifference` 补。检查空缺和等待都是这一章的思路，只是单位不同：私聊和普通群共用每个用户的一条公共序列，只有频道和超级群各有自己的 `pts`。
- **微信的 seqsvr**：微信公开过它的序列号生成器（[InfoQ, 2016](https://www.infoq.cn/article/wechat-serial-number-generator-architecture)）：**每个用户**一个 64 位的序列号，文章明说“只要求递增，并没有要求连续”；客户端带着已经同步到的最大序列号来，服务器把更新的给它。它管的是“同步到哪了”（第 6 章），不是“缺了哪条”。
- **为什么不要一个全局的顺序**：两个不相干的会话谁先谁后，没人关心，也没人看得出来；用户在乎的只是同一个会话里的顺序。一台服务器上，全局 id 是白来的，但它要所有消息都过同一个计数器；按会话分开，每个计数器只管自己，可以分到不同的机器上（第 27 章）。

## 6. 这一章的决定

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

**决策卡**

- 问题：只有一台服务器，屏幕上的顺序却是手机自己排的：自己的消息立刻放在最下面，重发的消息晚存，两个人看到的顺序不一样；推送丢了，跳号的 id 说明不了什么，手机发现不了。
- 选择：每个会话一个计数器，在写入的同一个事务里取下一个 seq；推送和确认都带上它（重复的确认带原来的 seq）。手机按 seq 排，发送中的放在最下面；seq 跳号先等 0.5 秒，还缺就补拉。
- 代价：一个会话的写入排队（5 毫秒一次时每秒最多 200 条）；自己的消息会挪位置；最后一条丢了推送要等下一条或下次拉取才发现；序号不能凭空跳，跳了服务器要说明。
- 什么时候重新考虑：一台服务器要给所有会话发号、发不过来时（第 27 章）；按游标同步一个人的所有会话（第 6 章）。
- 其他答案：按时间排（时钟对不上，也看不出缺号）；Lamport 时钟（给没有中心的系统用）；Telegram 的 pts（同一思路，私聊按用户、频道按频道）；微信 seqsvr（按用户递增、不连续，用来同步）；全局顺序（没人需要，还是瓶颈）；按顺序发（自己的不挪，但一条丢了后面都等）。

到这里，一个会话里的消息不丢、不重、不乱，缺了也知道。下一章：Ben 的手机离线了 10 分钟，他有 200 个会话，回来时该怎么补？