系统设计：在线协作编辑

多人实时编辑同一文档，光标闪烁、文字同步、冲突自动解决——这是系统设计面试中的高级话题。

Google Docs、Notion、飞书文档、腾讯文档的背后，是分布式系统与算法交叉的经典问题。

场景分析（Scenario）

需求

• 功能需求：多人实时编辑同一文档，看到彼此的修改和光标位置
• 用户规模：支持单文档 100 人同时在线编辑
• 延迟要求：本地操作 < 50ms 响应，远程操作 < 200ms 同步
• 一致性：最终一致性（不要求强一致，但要保证收敛）
• 离线支持：断网后可编辑，重连后自动合并

核心挑战

1. 并发编辑冲突：两人同时修改同一位置，谁为准？
2. 操作顺序问题：网络延迟导致操作乱序到达
3. 光标同步：多人光标位置实时同步
4. undo/redo：在协作场景下如何工作？
5. 离线合并：断网期间的操作，重连后如何合并？

核心算法：OT vs CRDT

OT（Operational Transformation）

Google Docs 早期使用的技术。核心思想：转换操作，使不同顺序的操作产生相同的结果。

用户 A: 在位置 0 插入 "a"     →  文档 = "a"
用户 B: 在位置 0 插入 "b"     →  文档 = "b"

如果 B 的操作先到达服务器：
- 服务器先执行 B: 文档 = "b"
- A 的操作到达时，需要被"转换"：
  A 原来想在位置 0 插入 "a"，但此时文档已有 "b" 在位置 0
  转换后: A' = 在位置 1 插入 "a"
- 最终文档 = "ba"（与 A 先执行、B 后执行的结果一致）

OT 的两条规则：

• TP1：转换后两操作在对方上下文执行结果相同
• TP2：多次转换的组合满足结合律

OT 的难点：

• TP2 在某些情况下无法满足（需要 ad-hoc 处理）
• 实现复杂，容易有边界 bug
• 需要中央服务器做操作排序

CRDT（Conflict-free Replicated Data Type）

现代协作系统的主流选择。核心思想：数据结构天然满足交换律、结合律、幂等性，无需中央协调。

最简单的 CRDT：G-Counter（增长计数器）

class GCounter:
    """只增的分布式计数器"""
    def __init__(self, node_id, num_nodes):
        self.node_id = node_id
        self.p = [0] * num_nodes  # 每个节点只改自己的位置

    def increment(self):
        self.p[self.node_id] += 1

    def query(self):
        return sum(self.p)

    def merge(self, other):
        self.p = [max(a, b) for a, b in zip(self.p, other.p)]

文本 CRDT：RGA（Replicated Growable Array）

文本协作的核心是给每个字符一个全局唯一的 ID，插入/删除操作带上这个 ID，不再依赖位置索引。

文档初始: []

用户 A 插入 "H"，分配 ID = (A, 1, timestamp=100)
文档: [(A,1,100): 'H']

用户 B 插入 "i"，分配 ID = (B, 1, timestamp=105)
文档: [(A,1,100): 'H', (B,1,105): 'i']

用户 A 在 H 前插入 "!"，ID = (A, 2, timestamp=110)
文档: [(A,2,110): '!', (A,1,100): 'H', (B,1,105): 'i']

排序规则： timestamp 升序，timestamp 相同则 node_id 升序

删除：不是真正删除，而是标记为 tombstone（墓碑）。

class CRDTChar:
    def __init__(self, id, value, prev_id=None, deleted=False):
        self.id = id           # 全局唯一 ID
        self.value = value     # 字符值
        self.prev_id = prev_id # 前驱节点 ID
        self.deleted = deleted # 墓碑标记

class TextCRDT:
    def __init__(self):
        self.chars = {}  # id -> CRDTChar
        self.order = []  # 有序字符 ID 列表

    def insert(self, char_id, value, prev_id):
        char = CRDTChar(char_id, value, prev_id)
        self.chars[char_id] = char
        # 根据 prev_id 找到插入位置
        self._rebuild_order()

    def delete(self, char_id):
        if char_id in self.chars:
            self.chars[char_id].deleted = True

    def get_text(self):
        return ''.join(
            self.chars[cid].value
            for cid in self.order
            if not self.chars[cid].deleted
        )

OT vs CRDT 对比

面试建议：提到 CRDT 是趋势，CRDT 的核心优势是去中心化和离线支持。

服务架构

┌─────────┐     ┌─────────┐     ┌─────────┐
│ User A  │     │ User B  │     │ User C  │
└────┬────┘     └────┬────┘     └────┬────┘
     │               │               │
     └───────────────┼───────────────┘
                     ▼
              ┌─────────────┐
              │  WebSocket   │
              │   Gateway    │
              └──────┬──────┘
                     │
        ┌────────────┼────────────┐
        ▼            ▼            ▼
   ┌─────────┐ ┌─────────┐ ┌─────────┐
   │ Doc Svc │ │ Auth Svc│ │ Hist Svc│
   └────┬────┘ └─────────┘ └────┬────┘
        │                        │
        ▼                        ▼
   ┌─────────┐            ┌─────────┐
   │MongoDB  │            │  S3     │
   │(Doc)    │            │(History)│
   └─────────┘            └─────────┘

实时同步流程

用户 A 输入 "H"
    │
    ▼
前端 CRDT 算法处理
    │
    ▼
WebSocket 发送 Op 到 Gateway
    │
    ▼
Gateway 广播给其他在线用户
    │
    ├──▶ 用户 B: CRDT 合并 → 更新视图
    └──▶ 用户 C: CRDT 合并 → 更新视图

操作格式

{
  "op": "insert",
  "char_id": {"node": "A", "seq": 1, "clock": 100},
  "value": "H",
  "prev_id": null,
  "timestamp": 1698000000000
}

光标/选区同步

光标位置也是 CRDT 的一种：

• 光标 = (anchor_id, focus_id, anchor_offset, focus_offset)
• 当文档内容变化时，光标"粘附"在离它最近的 character ID 上
• 避免了传统行/列偏移在内容插入时光标漂移的问题

def translate_cursor(cursor, applied_ops):
    """文档变更后，将光标映射到新的位置"""
    for op in applied_ops:
        if op is insert and op.pos <= cursor.pos:
            cursor.pos += len(op.text)
        elif op is delete and op.pos < cursor.pos:
            cursor.pos -= min(cursor.pos - op.pos, len(op.text))
    return cursor

版本历史与快照

快照策略

实现

class DocumentHistory:
    def __init__(self):
        self.operations = []  # 所有有序操作
        self.snapshots = {}   # version -> snapshot

    def save_snapshot(self, version):
        """基于 operations 重建指定版本"""
        doc = TextCRDT()
        for op in self.operations[:version]:
            doc.apply(op)
        self.snapshots[version] = doc.get_text()

    def get_version(self, version):
        # 找最近的快照，然后 replay 到目标版本
        nearest = max(v for v in self.snapshots if v <= version)
        doc = self._load_snapshot(nearest)
        for op in self.operations[nearest:version]:
            doc.apply(op)
        return doc

权限控制

class Permission:
    NONE = 0
    VIEW = 1
    COMMENT = 2
    EDIT = 3
    ADMIN = 4

# 权限检查
def check_permission(user_id, doc_id, required):
    role = db.get_role(user_id, doc_id)
    return role >= required

• Viewer：只读，看到实时更新但不能编辑
• Commenter：可批注，不能改正文
• Editor：完全编辑权限
• Admin：管理权限、分享设置

面试答题框架

协作编辑面试回答结构

阶段一：需求澄清（2 分钟）

• 文档类型？纯文本 / 富文本 / 表格？
• 同时在线人数上限？
• 是否需要离线编辑？
• 版本历史需要保存多久？

阶段二：核心冲突解决（5 分钟）

• 介绍 OT 和 CRDT 两种方案
• CRDT 的优势：去中心化、离线支持、天然收敛
• 字符级 CRDT：全局唯一 ID + tombstone 删除
• 排序规则：timestamp + node_id

阶段三：同步架构（3 分钟）

• WebSocket 全双工通信
• 操作广播 vs 状态同步的选择
• 心跳与断线重连处理

阶段四：扩展功能（3 分钟）

• 光标同步：基于 character ID 的粘附光标
• 版本历史：全量 + 增量混合快照
• 权限控制：RBAC 模型
• 富文本：把 formatting 也当成 CRDT（如 Quill 的 Delta）

阶段五：性能与优化（2 分钟）

• Tombstone 清理：定期压缩，合并相邻未删除字符
• 分页加载：大文档分段加载和操作转发
• 边缘计算：CDN 级别的操作中继

常见追问

关键知识点总结