深入理解 IM 系统

第 5 章

顺序

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

这一章是初稿，会在写完前八章后再修订。

本章目录
  1. 看它坏掉
  2. 估算
  3. 修好它
  4. 代价
  5. 其他答案
  6. 这一章的决定

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

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

1. 看它坏掉

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

Ana 和 Ben 几乎同时各发了一句。服务器只有一台，id 只有一个顺序。两个人屏幕上的顺序会一样吗？

推送推送丢了重发后才到

和服务器顺序相反的对数
–
缺了没发现
–
补拉
–
自己的消息挪了位置
–

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

两人同时发。 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）序号（seq）会话里每条消息的编号，由负责这个会话的消息服务连续分配。它决定会话里的顺序，也让客户端发现缺了哪一条。信箱另有一套按人递增的序号。在术语表里查看。

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

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

6. 这一章的决定

第 5 章加的一块：每个会话一个计数器，消息层在写入的同一个事务里取下一个 seq；推送和确认都带上它，手机按 seq 排，跳号就补拉。
Ana发件箱Ben消息 → ← ACK推送带 seq；跳号补拉；重连 after=<id>一个程序连接层持有长连接；记着 用户 → 连接消息层（收）查消息 ID，取会话的下一个 seq，写入，回 ACK分发层（发）推送带 seq；跳号时手机来补拉业务层（旁路）Ana 在这个会话里吗存储层两个唯一键发送者+消息ID会话+seq会话.last_seq

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