返回文章列表

用 Rust 从零搭一个 IM 系统:消息序号比消息内容难

946 字·7 分钟阅读
Rust从零造轮子实时通信

前面几个系统都在处理"数据"。IM 处理的是视图——同一条消息,在两个客户端上必须显示在同一个位置,而且这个位置在断线、重连、换设备之后都不能变。

难的不是把消息发过去,是让所有人对"发生了什么、我读到哪了"有一致的理解。

而支撑这个一致理解的,不是消息体本身,是一个看起来极其不起眼的整数:消息序号。

第一步:先把三个概念拆开

绝大多数 IM 的架构混乱,都源于把这三件事当成了一件事:

① 消息内容 (message body)
   这条消息说了什么。不可变,写一次读多次。
 
② 消息在会话中的位置 (seq)
   这条消息在这个会话里排第几。必须单调递增、不重不漏。
 
③ 用户的读取位置 (read cursor)
   这个用户在这个会话里读到哪了。每个用户独立,会变。

为什么必须拆开?因为它们的生命周期和一致性要求完全不同:

消息内容 会话序号 读取位置
是否可变 不可变(编辑另算) 不可变 频繁变化
写入频率 每条消息一次 每条消息一次 每次已读上报
一致性要求 最终一致即可 严格单调、不可重复 可最终一致,但多端要收敛
谁拥有 会话 会话(服务端分配) 用户(可多端)
存储位置 消息表 消息表的 key 独立的游标表

把它们混在一起,最典型的表现是"删掉一条消息之后所有人的未读数都不对了"——因为未读数是"读取位置 - 消息数",而消息数依赖消息表。序号和读取位置必须独立存在,即使消息被删了,计数也不能错。

任何"位置"概念都必须独立于"内容"存在。 这个原则在别的地方也出现过:WAL 的 LSN 独立于日志内容、流处理的水位线独立于数据。一旦位置是从内容推出来的,删改内容就会让位置失真。

第二步:会话序号——谁来分配,什么时候分配

为什么不能用时间戳

最直觉的做法是给每条消息打一个毫秒时间戳当序号。它会在这三个地方崩掉:

问题一:两台机器时钟不同步。 服务端是多机的,A 机比 B 机快 100 毫秒,那么 B 机先收到的消息会排在后面。同一群两千人,每个人看到的顺序不一样。

问题二:并发写入同一毫秒。 两个消息时间戳相同,排序变成了不确定的——而且这个不确定性会在每次读取时重新出现(不同的排序算法给出不同结果)。

问题三:无法做增量拉取。 客户端重连后想"给我 100 之后的消息",时间戳做不到——因为时间戳有跳变、有空洞、有重复。

所以唯一可用的结构是"每个会话一个单调递增的整数计数器"。

序号分配的三个约束

pub struct SequenceAllocator {
    /// 每个会话的当前最大序号
    /// 真实实现里这份状态必须持久化,不能只在内存里
    counters: HashMap<ConversationId, u64>,
}
 
impl SequenceAllocator {
    /// 分配一串连续的序号
    pub fn allocate(&mut self, conv: ConversationId, n: u64) -> Result<u64> {
        let counter = self.counters.entry(conv).or_insert(0);
 
        // ★ 约束一:必须在持久化之后才能返回给调用方
        //    崩溃恢复后如果重用了已经发出去的序号,
        //    客户端会认为"这条消息我已经见过了",然后永久丢掉它
        let start = *counter + 1;
        let end = *counter + n;
        self.persist_counter(conv, end)?;   // 先落盘
        *counter = end;
        Ok(start)
    }
}

约束一:先持久化,再返回。 这是整篇最容易被忽略、后果最严重的一条。

设想:服务端分配了 seq=100 给客户端,还没落盘就崩溃了。重启后从 99 继续,下一条消息又拿到 seq=100。客户端收到两条 seq=100 的消息,去重逻辑会把第二条丢掉——用户永久丢失了一条消息,而且没有任何报错。

约束二:同一会话内不能有空洞。 如果分配了 100 但写入失败了,就会留下一个洞。有洞的序号会直接破坏"按 seq 区间拉取"这种增量同步逻辑(客户端拉到 100 和 102,会以为 101 丢了,触发无谓的重试)。

处理方式是把"分配序号"和"写入消息"放在同一个原子操作里:

pub struct MessageStore {
    db: LsmStore,   // 就是前面写过的 LSM-Tree
}
 
impl MessageStore {
    /// 分配序号 + 写入消息,要么都成功要么都失败
    pub fn append(&mut self, conv: ConversationId, msg: &Message) -> Result<u64> {
        let mut batch = WriteBatch::new();
 
        // ① 取当前最大序号(从存储里读,不是从内存计数器读)
        let next = self.max_seq(conv)? + 1;
 
        // ② 序号计数器 + 消息本体,写进同一个 batch
        batch.put(counter_key(conv), &next.to_be_bytes());
        batch.put(message_key(conv, next), &encode_message(msg));
 
        // ③ 一次原子提交
        self.db.write(batch)?;
        Ok(next)
    }
}

注意第 ① 步是"从存储里读当前最大序号",而不是维护一个内存计数器。 内存计数器需要额外的持久化协议(还要考虑多个服务实例同时写入的情况),而把序号存在存储里、和消息同一个 batch 提交,就天然获得了原子性。

约束三:分布式的坑。 如果同一个会话的消息可能来自多个服务实例(比如用户连接到不同节点),那么"读当前最大序号"就成了一个竞态。这就是为什么 IM 系统通常会做"会话级路由"——同一个会话的所有写入都固定到同一个节点(用一致性哈希,room_id → node)。

序号分配的可靠性,等于"序号和消息在同一个原子边界内"。 一旦它们分离(先分配后写入、或者内存分配异步落盘),就一定会出现"序号泄漏"或者"序号重复"——而两者的表现都是"用户偶尔丢一条消息",这种 bug 几乎不可能在测试环境复现。

第三步:存储布局——key 的设计决定了一切

消息表用什么结构?答案是键值存储 + 精心设计的 key。

/// 会话消息的 key:会话 id + 序号,都是大端序
fn message_key(conv: ConversationId, seq: u64) -> Vec<u8> {
    let mut k = Vec::with_capacity(16);
    k.extend_from_slice(&conv.to_be_bytes());
    k.extend_from_slice(&seq.to_be_bytes());
    k
}

为什么是"拼接"而不是"分开存两张表"?因为这样一次范围扫描就能拿到一个会话的连续消息。

存储里的 key 排列(按字节序):
  会话 A + seq 001  ┐
  会话 A + seq 002  ├─ 物理相邻,一次 range scan 全拿到
  会话 A + seq 003  ┘
  会话 B + seq 001
  会话 B + seq 002
 
拉取请求:"给我会话 A 里 seq > 100 的最近 50 条"
  → scan(会话A + 101 .. 会话A + 151)
  → 一次顺序读,不需要过滤任何其他会话的数据

三个必须注意的细节:

细节一:必须是大端序。 小端序下 seq = 256 的字节是 00 01 00 00 00 00 00 00(反着写),排序会完全错乱——256 会排在 1 前面。这是一个只按字节序比较的存储层上的经典陷阱,写反了功能测试还能过(因为小数字的顺序恰好一致),上了量才会暴露。

细节二:会话 id 和 seq 的长度必须固定。 如果用变长编码,conv=1 和 conv=12 的 key 会互相干扰前缀匹配。定长拼接下来,[8字节 conv][8字节 seq] 的字典序严格等于 (conv, seq) 的元组序。

细节三:消息体大不大,决定它存哪里。

消息类型 存储位置 原因
纯文本(< 4KB) 直接内联在 KV 的 value 里 一次读就拿全
图片 / 视频 / 文件 存对象存储,KV 里存 URL + 元数据 KV 的 value 太大会拖累 compaction
转发的大消息 引用(存原消息 id) 避免同一份内容存 N 次

这一条和前面对象存储那篇的结论是一致的:索引和数据要分离。 把 10MB 的视频塞进 LSM 的 value 里,会让 compaction 变成一场灾难——因为 compaction 要重写整段数据,而大 value 的重写成本是压倒性的。

会话列表:另一张表,读写模式完全不同

用户打开 App 看到的不是消息,是会话列表:

/// 用户的会话列表项
pub struct ConversationItem {
    pub conv_id: ConversationId,
    /// 我能看到的这个会话的最新序号
    pub last_seq: u64,
    /// 我读到的位置
    pub read_seq: u64,
    /// 未读数 = 我可见的消息数 - 已读数(不能用 last_seq - read_seq!)
    pub unread_count: u32,
    /// 排序用的时间戳
    pub updated_at: i64,
}

注意 unread_count 不能用 last_seq - read_seq 算出来。 因为 last_seq 是会话的全局序号,包含了"我加入群之前"的消息。如果用减法,新入群的人会看到一个巨大的未读数。

正确做法是维护一个"我能看到的最小序号"(joined_seq),未读数按可见区间计算。 这是产品需求深入到数据结构的一个典型例子——"入群之前的消息看不看得见"这个产品问题,直接决定了表结构。

计数类字段能不能推导出来,取决于"推导公式里有没有产品语义"。 unread = last - read 在数学上干净,在语义上是错的。凡是公式里有产品规则的,都必须显式存储。

第四步:投递模型——写扩散还是读扩散

一条消息要能被会话的所有成员看到。这里有两种完全相反的模型:

读扩散(fan-out on read)

消息只存一份(存在会话里)
每个成员读的时候,去会话里按 seq 拉
 
优点:写一次,写成本 O(1)
缺点:读的时候要合并"用户的所有会话"

一个用户的会话列表可能有几百个,每个会话都要读一次最新几条来排序——读成本很高。 但写成本极低,而且消息只有一份,天然没有一致性问题。

写扩散(fan-out on write)

发一条消息 → 写进每个成员的收件箱
每个成员读的时候,只读自己的收件箱
 
优点:读一次搞定(读自己的收件箱就够)
缺点:写成本 O(成员数),而且收件箱数据量 = 消息数 × 成员数

群里 2000 人,一条消息就要写 2000 次。 这在万人大群里是灾难。

真实的做法是混合

pub enum DeliveryMode {
    /// 单聊 / 小群:写扩散,收件箱里只存指针
    FanoutOnWrite,
    /// 大群:读扩散,读的时候去会话里拉
    FanoutOnRead,
}
 
fn delivery_mode(member_count: usize) -> DeliveryMode {
    // 阈值是可调参数,通常几百到几千
    if member_count <= 500 {
        DeliveryMode::FanoutOnWrite
    } else {
        DeliveryMode::FanoutOnRead
    }
}

但注意写扩散时收件箱存的是"指针",不是消息体:

/// 收件箱条目:只有位置,没有内容
pub struct InboxEntry {
    pub conv_id: ConversationId,
    pub seq: u64,
    /// 可选:消息摘要,用于免推送时显示通知
    pub preview: Option<String>,
}

为什么存指针?因为消息体只应该有一份。

如果收件箱里存了完整消息体,那么"编辑一条消息"或者"撤回一条消息"就需要改 2000 份副本——而且这 2000 份副本会在某个时刻不一致,用户在手机上看到了编辑前的内容,在电脑上看到了编辑后的。 存指针就完全回避了这个问题:消息体改一次,所有人下次读到的都是新的。

这也是"索引与数据分离"第三次出现(时序库的段目录、对象存储的元数据、IM 的收件箱)。只要有多份"对同一份数据的引用",就应该让引用只包含位置信息。

写扩散和读扩散不是二选一,而是"按会话规模分档"。 而且分档的阈值必须可调——因为它是"写成本 × 成员数"和"读成本"的天平,而这两个成本会随着你的存储和网络状况变化。

第五步:推拉结合——在线推送和离线拉取会重叠

这一层是最容易出诡异 bug 的地方。

在线:服务端通过 WebSocket 主动推 → 客户端即时显示
离线:客户端重连后,按"我读到哪了"主动拉
 
问题:这两个通道送来的消息会重叠。
      推送到一半断线了,重连后又拉了一遍,用户看到两条。

所以去重是必须的,但去重的实现方式决定了一个隐蔽的正确性边界。

错误做法:客户端只记"最大 seq"

// 错误:只记最大序号
pub struct BadClientState {
    pub max_seq: u64,   // 我见过的最大序号
}
 
impl BadClientState {
    fn on_message(&mut self, seq: u64) {
        if seq > self.max_seq {
            self.max_seq = seq;
        }
    }
}

它会丢消息。 设想客户端收到 seq 10、12、11:

  • 收到 10 → max = 10
  • 收到 12 → max = 12(但 11 还没到)
  • 收到 11 → 11 > 12 不成立 → 被当成重复丢掉

结果:消息 11 永久丢失。 而如果这时客户端断线重连,它会说"我读到 12 了",服务端从 13 开始给——11 就再也不会出现了。

正确做法:区分"连续已收到"和"乱序收到"

pub struct ClientState {
    /// 最大连续序号:从 1 到 contiguous_until 都已经收到了
    pub contiguous_until: u64,
    /// 乱序收到的、还没补齐的序号
    pub gaps: BTreeSet<u64>,
}
 
impl ClientState {
    pub fn on_message(&mut self, seq: u64) -> bool {
        // 返回 false 表示这是重复消息,不需要显示
        if seq <= self.contiguous_until || self.gaps.contains(&seq) {
            return false;
        }
 
        if seq == self.contiguous_until + 1 {
            // 恰好接上:推进连续位,并把后续所有已收到的洞补上
            self.contiguous_until = seq;
            while self.gaps.remove(&(self.contiguous_until + 1)) {
                self.contiguous_until += 1;
            }
        } else {
            // 中间有洞:记下来,等它被填
            self.gaps.insert(seq);
        }
 
        true
    }
 
    /// 重连时告诉服务端"从哪开始拉"
    pub fn resume_from(&self) -> u64 {
        self.contiguous_until + 1
    }
}

关键点是 resume_from 返回 contiguous_until + 1,而不是"收到的最大 seq + 1"。

如果返回最大 seq,那些洞就永远补不上了。 而返回连续位置之后,重连会重新拉一遍那些洞——因为推送是 at-least-once,重复收到是预期行为,去重逻辑会处理它。

注意这里的 gaps 是一个 BTreeSet,不是无限增长的。 正常情况下洞会很快被填上(乱序窗口很小)。但如果某个 seq 永远不来(消息被删了、或者服务端漏发了),这个集合会一直留着它——所以必须有一个上限或者超时机制。

"我读到哪了"这个问题的正确答案,永远不是一个数字,而是"连续的一段 + 几个待补的洞"。 只记一个数字的话,你既没法补齐空洞,也没法在重连时说明自己缺什么。这个结论在别的地方也一样:Raft 的日志匹配、流处理的窗口完成状态、CRDT 的版本向量——都是"一个连续前缀 + 若干孤立集合"。

第六步:多端同步——已读游标的归属问题

这是 IM 里最"产品驱动"的一个设计决策,没有技术上的唯一答案:

场景:用户晚上在手机上看了群消息,第二天打开电脑。
      电脑上的这个群,应该是"已读"还是"未读"?

两种答案对应两套完全不同的数据模型:

方案 游标归属 存储 用户体验
A:按用户 (user_id, conv_id) → read_seq 一份 手机读了,电脑也变已读
B:按设备 (user_id, device_id, conv_id) → read_seq 每设备一份 手机读了,电脑还是未读

方案 A 的问题是"多端同时上报会互相覆盖"。 手机上报 read_seq = 100,电脑同时上报 read_seq = 50(因为电脑上还停在旧位置)——如果处理方式是用"最后写入的值",电脑的 50 会把 100 覆盖掉,用户会看到"刚读过的群又变成未读"。

解法是单调合并:

impl ReadCursorStore {
    /// 上报已读位置:只能前进,不能后退
    pub fn update(&mut self, user: UserId, conv: ConversationId, read_seq: u64) -> Result<u64> {
        let key = (user, conv);
        let current = self.get(key).unwrap_or(0);
 
        // ★ 单调取最大:多端并发上报时,小的不会覆盖大的
        let next = current.max(read_seq);
 
        if next != current {
            self.put(key, next)?;
            // 通知该用户的其他在线设备
            self.notify_other_devices(user, conv, next)?;
        }
 
        Ok(next)
    }
}

"只能前进"这条规则的必要性是显然的,但它有一个代价:用户没法"标记为未读"。

如果产品要支持"标记未读",那么游标就不能用单个数字表示——要么允许后退(然后用版本号/时间戳解决并发覆盖),要么用"已读区间集合"。这是又一个"产品需求决定数据结构"的例子:一个看起来只是 UI 功能的需求,会让存储结构从"一个整数"变成"一个区间集合"。

多端同步的事件不只有已读

该用户在设备 A 上的动作,哪些需要广播给设备 B?

动作 要广播吗 原因
发消息 不要 消息本身通过会话广播,所有设备都会收到
已读位置变更 要 未读数要在多端一致
删除会话(本地) 不要 这是纯本地视图
标记未读 要 同上,它是共享状态
草稿 不要 每设备独立,而且变化太频繁

判断标准很清晰:只广播"共享状态",不广播"设备本地状态"。

草稿是最典型的反例。 如果草稿也同步,那么用户在手机上打了一半的字,会实时出现在电脑上——技术上能做,产品上是灾难。

"多端同步"的价值不在于同步得多,而在于同步得对。 每引入一个需要同步的状态,就多一份冲突处理逻辑和一次网络往返。所以边界必须划在"用户认为这是同一份状态"的地方——已读是,草稿不是。

第七步:单连接的写路径——一个队列是必需的

WebSocket 连接是典型的"多生产者单消费者":

谁在往这条连接上写?
  ├─ 消息推送任务
  ├─ 心跳任务
  ├─ 系统通知(踢下线、强制刷新)
  └─ 已读回执

如果这些任务各自直接 socket.write(),帧会交错,协议直接坏掉。

所以每个连接必须有一个写队列 + 一个专职 writer:

pub struct Connection {
    /// 有界队列:满了说明这个客户端跟不上了
    tx: mpsc::Sender<Outbound>,
    /// 连接的唯一标识,用于日志和踢下线
    id: ConnId,
}
 
pub enum Outbound {
    Message(MessageFrame),
    Ping,
    Close(u16, String),
}
 
impl Connection {
    pub fn spawn_writer(id: ConnId, mut socket: WebSocketStream, mut rx: mpsc::Receiver<Outbound>) {
        tokio::spawn(async move {
            while let Some(out) = rx.recv().await {
                let frame = match out {
                    Outbound::Message(f) => f.into_frame(),
                    Outbound::Ping => Frame::ping([]),
                    Outbound::Close(code, reason) => {
                        let _ = socket.send(Frame::close(code, reason.as_bytes())).await;
                        return;   // 关闭后退出 writer
                    }
                };
 
                if let Err(e) = socket.send(frame).await {
                    // 写失败就是连接死了,通知上层清理
                    tracing::info!(conn = %id, error = %e, "连接写失败");
                    return;
                }
            }
        });
    }
 
    /// 推送:队列满就返回错误,由调用方决定怎么办
    pub fn try_push(&self, out: Outbound) -> Result<(), PushError> {
        self.tx.try_send(out).map_err(|_| PushError::Backpressure)
    }
}

这里有三个决定,每一个都有明确的理由:

决定一:队列必须有界。 如果用一个无界队列,一个慢客户端(网络差、或者故意不读)会让消息在服务端堆积到内存耗尽。一个卡住的客户端不能拖垮整个服务。

决定二:队列满了要断开慢客户端,而不是丢弃消息。

fn on_push_failed(conn: ConnId) {
    // 丢弃消息会导致客户端"不知道丢了什么",
    // 而断开连接会让它走重连 + 按 seq 补齐的路径 —— 这是有恢复机制的路径
    disconnect(conn, CloseCode::TOO_SLOW);
}

丢弃消息在 IM 里是危险的:客户端不知道丢了哪条,它的 contiguous_until 会一直等着那个永远不来的 seq。而断连是安全的——客户端重连后按 contiguous_until + 1 重新拉,正好把缺的补上。这就是第五步那套游标机制的价值:它给了"断开重连"一个正确的语义。

决定三:这里不需要无锁队列。

前面写过无锁队列(MPMC),但在这个场景里 mpsc 就够了,而且更好——因为:

  • 写端是多个任务,但每个连接一个队列,竞争其实很低
  • 无锁队列的优势在"高竞争 + 极短临界区",而这里的瓶颈是网络 IO,不是队列本身
  • mpsc 提供背压语义(try_send 立刻返回失败),这正是需要的

"前面写过的轮子"不等于"这里该用的轮子"。 无锁队列很酷,但一个每连接一个队列、每队列每秒最多几千次操作的场景,锁的成本完全可以忽略。引入无锁结构的唯一理由是"测出来锁是瓶颈"——没测出来就不要引入,因为无锁的调试成本远高于收益。

第八步:可靠性的边界——at-least-once + 去重

最后把可靠性的账算清楚。

推送是 at-least-once

服务端推送失败、超时、或者客户端没 ack,都会导致重传。所以客户端必然会收到重复消息——这不是 bug,是协议的设计。

而"去重"这件事已经由第五步的游标机制完成了:seq <= contiguous_until 就是重复。

ack 应该是累积的

/// 客户端上报:"我已经连续收到 100 之前的所有消息"
pub struct Ack {
    pub conn_id: ConnId,
    pub conv_id: ConversationId,
    pub contiguous_until: u64,
}

累积 ack 比单条 ack 省得多。

方式 100 条消息的 ack 数 语义
单条 ack 100 "我收到了第 N 条"
累积 ack 1~3(按间隔或按数量触发) "N 之前的我都有"

而且累积 ack 还顺带表达了"没有任何洞"这个信息——单条 ack 做不到(你 ack 了 100 条,但中间有 5 个洞,服务端以为你都收到了)。

服务端的未确认队列

pub struct PendingQueue {
    /// 每个连接上"已经发出但还没被 ack"的消息
    inflight: HashMap<ConnId, BTreeMap<u64, Instant>>,
    /// 重传定时器(就是前面写过的定时器轮)
    timers: TimerWheel,
}

注意 BTreeMap<seq, Instant> 这个结构: 因为 ack 是累积的,收到 contiguous_until = 100 时,只需要 split_off 一次就把 100 之前的所有项全部摘掉——O(log n) 而不是遍历。

重传的边界: 如果客户端一直没有 ack(比如它其实在正常接收,只是 ack 丢了),服务端会重传。这时客户端会收到重复消息,而去重会把它挡掉。 这就是"at-least-once + 客户端去重 = 显示上恰好一次"的完整链条。

"恰好一次"通常不是靠协议做到的,是靠"至少一次投递 + 幂等的接收方"组合出来的。 而这个组合要成立,接收方必须有能力判断"这条我见过"——所以那个单调递增的序号,才是整个可靠性方案的地基。

结论

把长连接、LSM 存储、定时器拼成一个 IM 之后,能看清它是所有系统里"位置"概念最密集的一个:

                    ┌─ 内容(不可变,存一份)
一条消息由三个坐标确定 ──── seq(会话内位置,服务端分配,严格单调)
                    └─ read_seq(用户读到哪,可多端,单调前进)
 
                ┌─ 消息表:key = (conv, seq) 大端拼接 → 一次 range scan
存储布局决定读性能 ─── 收件箱:只存指针,不存内容
                └─ 游标表:(user, conv) → read_seq,独立于消息表
 
                ┌─ 在线:推送(at-least-once)
传递路径 ───────├─ 离线:按 contiguous_until + 1 拉取
                └─ 重叠部分靠 seq 去重
 
                ┌─ 队列必须有界
连接并发 ───────└─ 满则断连(不要丢消息),重连正好补齐

四条最值得记住的判断:

  1. 序号必须先持久化再返回。 否则崩溃后重用序号,客户端会永久丢掉那条消息——而且没有任何报错。
  2. "读到哪了"不是一个数字,是"连续前缀 + 待补的洞"。 只记一个数字必然丢消息。
  3. 收件箱只存指针。 存内容会让"编辑/撤回"变成改 N 份副本,而且必然出现多端不一致。
  4. 队列满时断连,不要丢消息。 丢消息没有恢复路径,断连有。

这四条的共同点是:它们都不是性能问题,而是"状态的一致性"问题。 IM 系统可以在所有性能指标上都正常,同时持续地、静默地丢消息——因为丢消息不会让任何监控告警,只会让用户觉得"这个 App 有点不稳"。

下一篇换到"多个人同时改同一份数据"的场景(协同编辑),那是一个连"谁先谁后"这个问题本身都需要被重新定义的地方。