作者：東燈原標題：用 MoonBit 實現(xiàn) CRDTs 算法并構(gòu)建實時協(xié)作應用
一.引言

當你在 Google Docs 中與同事同時編輯一份文檔，或者在 Figma 中與設(shè)計師協(xié)作調(diào)整界面時，你有沒有想過：為什么兩個人同時在同一位置輸入文字，最終結(jié)果卻不會互相覆蓋或產(chǎn)生亂碼？

這背后隱藏著分布式系統(tǒng)中最具挑戰(zhàn)性的問題之一：并發(fā)沖突（ Concurrent Conflict）。當多個用戶同時編輯同一份數(shù)據(jù)，且這些編輯需要在不同設(shè)備之間同步時，如何保證所有人最終看到相同的結(jié)果？

本文將帶你深入理解實時協(xié)作的核心算法演進——從經(jīng)典的操作轉(zhuǎn)換（OT）到經(jīng)典的 CRDTs 算法 RGA，再到現(xiàn)代的 EG-Walker。我們不僅會解釋這些算法的原理，還會用 MoonBit 實現(xiàn)算法的核心邏輯，并最終展示如何用它構(gòu)建一個簡單的、斷網(wǎng)重連可合并的協(xié)作編輯器。

二.實時協(xié)作的核心挑戰(zhàn)

假設(shè)我們要構(gòu)建一個多人協(xié)作的文本編輯器。每個用戶在自己的設(shè)備上都有一份文檔副本，當用戶進行編輯時，操作會通過網(wǎng)絡(luò)同步給其他用戶。為了保證流暢的編輯體驗，用戶的輸入應該立即生效，而不是等待服務(wù)器確認。

問題來了：當兩個用戶同時編輯時，會發(fā)生什么？讓我們考慮這個場景：

這就是并發(fā)沖突的本質(zhì)：相同的操作序列，以不同順序應用，可能產(chǎn)生不同的結(jié)果 。

我們需要的是一種機制，無論操作以什么順序到達，最終所有人看到的結(jié)果都相同，而且尊重所有編輯參與者的貢獻。這個性質(zhì)叫做 最終一致性 （Eventual Consistency） 。

三.操作轉(zhuǎn)換（ OT ）
1、原理與簡單實現(xiàn)

操作轉(zhuǎn)換（Operational Transformation，OT）是最早用于解決實時協(xié)作沖突的算法，誕生于 1989 年。Google Docs、Etherpad 等早期協(xié)作工具都采用了這種方案。OT 的基本思路是：既然操作之間會互相影響，那就在應用操作之前，根據(jù)已發(fā)生的操作對其進行“轉(zhuǎn)換”，使其適應當前狀態(tài)。

看看 OT 是如何解決沖突的：

• 初始文檔是 AB 。Alice 在位置 1 插入 X ，本地變成 AXB ；Bob 在位置 1 插入 Y ，本地變成 AYB ?，F(xiàn)在雙方需要同步對方的操作。

• 當 Alice 收到 Bob 的操作 insert(1, 'Y') 時，她不能直接執(zhí)行——因為她已經(jīng)在位置 1 插入了 X ，后面的字符都向右移了一位。OT 發(fā)現(xiàn) Bob 的插入位置（1）不在 Alice 插入位置之前，于是把位置 +1，變成 insert(2, 'Y') 。Alice 執(zhí)行后得到 AXYB 。

• 同樣，Bob 收到 Alice 的 insert(1, 'X') 。但 Alice 的插入位置（1）不比 Bob 的（1）大，所以不調(diào)整。Bob 直接執(zhí)行，在位置 1 插入 X ，也得到 AXYB 。

不妨簡單用 MoonBit 實現(xiàn)一下：

enum Op {
  Insert(Int, Char)  // Insert(位置, 字符)
  Delete(Int)        // Delete(位置)
}


 /// 轉(zhuǎn)換函數(shù)：將 op1 轉(zhuǎn)換為在 op2 已經(jīng)執(zhí)行后的等效操作
fn transform(op1 : Op, op2 : Op) -> Op {
  match (op1, op2) {
    (Insert(pos1, ch), Insert(pos2, _)) =>
      Insert(if pos1 <= pos2 { pos1 } else { pos1 + 1 }, ch)
    (Insert(pos1, ch), Delete(pos2)) =>
      Insert(if pos1 <= pos2 { pos1 } else { pos1 - 1 }, ch)
    // ... 其他 case 類似
  }
}

2、OT 存在的問題

OT 在工業(yè)界有廣泛應用（Google Docs 就基于 OT），但它有一些根本性的問題：

1、需要中央服務(wù)器 ：OT 需要一個權(quán)威的服務(wù)器來確定操作的全局順序。沒有服務(wù)器，就無法確定誰的操作“先”發(fā)生。

2、轉(zhuǎn)換規(guī)則復雜度爆炸 ：如果有 N 種操作類型，就需要定義 N2 個轉(zhuǎn)換規(guī)則。當操作類型增多（如富文本的加粗、斜體、鏈接等），復雜度急劇上升。

3、長分支合并極慢 ：如果兩個用戶離線編輯了很長時間，重新連接時需要轉(zhuǎn)換大量操作，性能很差。

四.RGA：一種經(jīng)典的序列 CRDT

CRDT（Conflict-free Replicated Data Type）采用了完全不同的思路： 不是在收到操作后轉(zhuǎn)換它，而是設(shè)計一種數(shù)據(jù)結(jié)構(gòu)，使得無論操作以什么順序應用，結(jié)果都相同 。這就像設(shè)計一種特殊的“加法”——無論你按什么順序把數(shù)字加起來，結(jié)果都一樣。數(shù)學上，這要求操作滿足 交換律 和 結(jié)合律 。

1、RGA：一種經(jīng)典的序列 CRDT

RGA（Replicated Growable Array）是 2011 年提出的一種序列 CRDT，專門用于解決協(xié)同文本編輯中的沖突問題。它的核心思想很簡單： 用相對位置代替絕對位置 。

還是用 Alice 和 Bob 的例子。初始文檔是 AB ，Alice 和 Bob 同時在位置 1 插入字符——Alice 插入 X ，Bob 插入 Y 。

OT 的做法是調(diào)整位置坐標。但 RGA 換了個思路： 不用數(shù)字位置，用“插在誰后面”來描述插入點 。

具體來說：

• Alice 的操作不再是“在位置 1 插入 X”，而是“在 A 后面插入 X”

• Bob 的操作是“在 A 后面插入 Y”

兩個操作都想插在 A 后面，怎么辦？RGA 給每個字符分配一個 全局唯一的 ID 。這個 ID 由兩部分組成：

• 用戶 ID ：每個用戶有一個唯一標識（如 Alice 是 A ，Bob 是 B ）

• 本地計數(shù)器 ：每個用戶維護一個遞增的計數(shù)器，每次插入新字符時 +1

所以 A@1 表示“Alice 的第 1 個操作”， B@1 表示“Bob 的第 1 個操作”。當兩個字符想插入同一位置時，比較 ID 來決定順序——先比本地計數(shù)器，計數(shù)器相同時再比用戶 ID（作為 tie-breaker）。這里兩個計數(shù)器都是 1，所以比較用戶 ID： B > A ，因此 B@1 排在 A@1 前面，結(jié)果就是 A → Y → X → B ，即 AYXB 。

如果用 MoonBit 實現(xiàn)，我們可以先定義每個節(jié)點的類型和它的 compare 規(guī)則：

/// 唯一標識符
struct ID {
  peer : UInt64    // 用戶 ID
  counter : Int    // 本地計數(shù)器
} derive(Eq)


 /// 比較兩個 ID，用于解決并發(fā)插入沖突
impl Compare for ID with compare(self, other) {
  // 先比較 counter，再比較 peer（打破平局）
  if self.counter != other.counter {
    other.counter - self.counter
  } else if self.peer > other.peer { -1 } 
  else if self.peer < other.peer { 1 } 
  else { 0 }
}

插入時，在目標位置之后找到正確的插入點——跳過所有 ID 更大的節(jié)點：

/// 在 target 之后插入，返回插入位置
fn find_insert_pos(order : Array[ID], target_pos : Int, new_id : ID) -> Int {
  let mut pos = target_pos + 1
  while pos < order.length() && new_id.compare(order[pos]) > 0 {
    pos = pos + 1  // new_id 更小，繼續(xù)往后找
  }
  pos
}

我們剛才假設(shè)了只有插入的情況，對于刪除問題，RGA 采用墓碑（Tombstone）策略：刪除字符時不真正移除，只標記為“已刪除”。

為什么不能真刪除？考慮這個場景：Alice 刪除了 B，同時 Bob（還沒收到刪除）在 B 后面插入 X。如果 B 真的沒了，Bob 的“在 B 后面插入”就找不到參照物了。墓碑讓 B 保留在數(shù)據(jù)結(jié)構(gòu)中，只是渲染時跳過，這樣 Bob 的操作仍然有效。

/// RGA 節(jié)點
struct RGANode {
  id : ID
  char : Char
  mut deleted : Bool  // 墓碑標記
}

 /// 刪除：標記為墓碑
fn RGANode::delete(self : RGANode) -> Unit {
  self.deleted = true
}

 /// 渲染：跳過墓碑
fn render(nodes : Array[RGANode]) -> String {
  let sb = StringBuilder::new()
  for node in nodes {
    if !node.deleted { sb.write_char(node.char) }
  }
  sb.to_string()
}

在上面的簡單實現(xiàn)當中，為了更加簡潔易懂，我們采用的是數(shù)組來存儲 RGA 的節(jié)點。而熟悉數(shù)據(jù)結(jié)構(gòu)的讀者很輕松就可以發(fā)現(xiàn)：RGA 會存在頻繁的插入情況，因此鏈表也許更適配這種算法。而實際的工程中則經(jīng)常使用更加穩(wěn)健高效的結(jié)構(gòu)如 B+ Tree 或跳表實現(xiàn)它。

2、RGA 的問題

RGA 解決了并發(fā)沖突問題，不需要中央服務(wù)器，支持 P2P 同步，但它也有顯著的缺點：

• 元數(shù)據(jù)膨脹 ：每個字符都需要存儲 ID（工程上很容易達到 16+ 字節(jié)）和前驅(qū)引用，一篇 10 萬字的文檔，元數(shù)據(jù)可能比內(nèi)容還大。

• 墓碑累積 ：刪除的字符永遠保留在內(nèi)存中。一篇編輯多次的文檔，可能 90% 的數(shù)據(jù)都是墓碑，而且文字上可能還有其他維度，比如富文本，會進一步加劇這個缺點造成的影響。

• 加載緩慢 ：從磁盤加載文檔時，需要重建整個數(shù)據(jù)結(jié)構(gòu)，這是 O(n) 甚至 O(n log n) 的操作。

五.Event Graph Walker：更好的方案
1、原理介紹

Event Graph Walker（簡稱 Eg-walker）是由 Joseph Gentle 和 Martin Kleppmann 在 2024 年提出的新 CRDT 算法。

前面我們看到，OT 操作簡單（只有位置索引）但需要中央服務(wù)器；CRDT 支持 P2P 但元數(shù)據(jù)膨脹嚴重。Eg-walker 的核心洞察是：兩者可以結(jié)合，即存儲時用簡單索引，合并時臨時構(gòu)建 CRDT。

操作像 OT 一樣輕量，只記錄 insert(pos, char) 和 delete(pos) 。需要合并并發(fā)操作時，臨時重放歷史、構(gòu)建 CRDT 狀態(tài)來解決沖突，合并完就丟掉。

可能很多讀者會這種“臨時構(gòu)建 CRDT 解決問題的方式”存在一些性能方面的顧慮，我們的確要承認雖然臨時構(gòu)建確實有開銷，但是由于大部分時間并不需要 CRDT 參與編輯工作，只有同步并發(fā)編輯的時候才需要，而且 Eg-Walker 的性質(zhì)很明顯支持增量構(gòu)建與局部構(gòu)建，只需要從快照構(gòu)建或者再沖突區(qū)域構(gòu)建 CRDT 解決沖突即可。而且可以設(shè)想的是，在操作歷史越來越復雜的情況下，臨時構(gòu)建會比維護一個會一直增長的結(jié)構(gòu)更加穩(wěn)健高效。

2、代碼實現(xiàn) 1）基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)

首先是操作的定義。與 RGA 使用“在某個 ID 后面插入”的相對定位不同，Eg-walker 直接使用數(shù)字位置索引，就像 OT 一樣簡單：

enum SimpleOp {
  Insert(Int, String)   // Insert(位置, 內(nèi)容)
  Delete(Int, Int)      // Delete(位置, 長度)
}

接下來是 事件（Event） 的定義。事件是對操作的包裝，添加了因果關(guān)系信息：

struct Event {
  id : ID               // 唯一標識符
  deps : Array[ID]      // 依賴的事件（父節(jié)點）
  op : SimpleOp         // 實際的操作內(nèi)容
  lamport : Int         // Lamport 時間戳，用于排序
}

然后我們就可以根據(jù)他們定義出一個事件圖（Event Graph）：

struct EventGraph {
  events : Map[ID, Event]  // 所有已知事件
  frontiers : Array[ID]        // 當前最新的事件 ID 集合
}

這里定義中的 frontiers 記錄了“當前版本”——那些沒有被任何其他事件依賴的事件。如果讀者熟悉 Git 的一些概念，那么可以把它理解為 Git 中當前所有分支的 HEAD 指針集合。

2）添加事件與維護 Frontier

當收到新事件時，除了將事件存入當前的事件表中，還需要更新 frontier。由于 frontier 記錄的是“沒有后續(xù)事件的事件”，當新事件依賴某個舊 head 時，說明這個舊 head 已經(jīng)有了后續(xù)，不再是“最新的”了，需要從 frontier 中移除，然后把新事件加入 frontier。

fn EventGraph::add_event(self : EventGraph, event : Event) -> Unit {
  self.events[event.id] = event
  self.frontiers = self.heads.retain(frontier => !event.deps.contains(frontier))
  self.frontiers.push(event.id)
}

合并兩個版本需要解決兩個問題：

1、找到分叉點（在 Event Graph 上找到 LCA ） ：確定從哪里開始重放

2、確定重放順序（根據(jù) Lamport 拓撲排序 ） ：按因果關(guān)系排序事件

這兩部分都屬于比較基本的圖論問題，相信讀者在查閱資料后可以很快的實現(xiàn)出來。不過需要注意的是，在工業(yè)實現(xiàn) Eg-Walker 算法時，我們通常不使用常規(guī)介紹的算法求 LCA，而是對數(shù)據(jù)結(jié)構(gòu)進行改進，應用一些緩存機制來提高效率。

4）合并算法

現(xiàn)在我們有了所有組件，可以實現(xiàn)完整的合并算法了：

fn EventGraph::merge(
  self : EventGraph,
  local_frontiers : Array[ID],
  remote_frontiers : Array[ID],  // 遠程 peer 的 frontiers，隨事件一起發(fā)送
  remote_events : Array[Event]
) -> String {
  // 步驟 1：將遠程事件添加到事件圖
  for event in remote_events {
    self.add_event(event)
  }
  // 步驟 2：找到本地版本和遠程版本的 LCA（用 VersionVector 取交集）
  let lca = self.find_lca(local_frontiers, remote_frontiers)
  // 步驟 4：收集從 LCA 到兩個分支的所有事件
  let events_to_replay = self.collect_events_after(lca)
  // 步驟 5：按 Lamport 時間戳拓撲排序
  let sorted = self.topological_sort(events_to_replay)
  // 步驟 6：創(chuàng)建臨時 RGA，重放所有事件
  let temp_rga = RGA::new()
  for event in sorted {
    self.apply_to_rga(temp_rga, event)
  }
  // 步驟 7：返回最終文本，丟棄臨時 RGA
  temp_rga.to_string()
}

合并流程可以總結(jié)為三個階段：

• Retreat（回退） ：找到 LCA，確定需要重放的事件范圍

• Collect（收集） ：收集兩個分支上的所有事件，按 Lamport 時間戳拓撲排序

• Advance（推進） ：創(chuàng)建臨時 RGA，按順序重放所有事件，用 CRDT 解決沖突

Loro 是一個基于 Eg-walker 算法的高性能 CRDT 庫，由 Rust 實現(xiàn)。它支持多種數(shù)據(jù)類型（文本、列表、Map、可移動列表、樹結(jié)構(gòu)等），提供豐富的協(xié)作功能，被用于構(gòu)建實時協(xié)作應用。而 Lomo 是 Loro 的 MoonBit 移植版本，與 Loro Rust 版本保持二進制兼容，這意味著用 lomo 生成的文檔可以被 Loro 讀取，反之亦然。

Lomo 的核心 API 非常簡潔：

let doc = LoroDoc::new()
doc.set_peer_id(1UL)
// 獲取文本容器并編輯
let text = doc.get_text("content")
doc.text_insert(text, 0, "Hello, World!")
doc.text_delete(text, 5, 2)
// 導出更新（用于同步）
let updates = doc.export_updates()
// 另一個 peer 導入更新
let doc2 = LoroDoc::new()
doc2.set_peer_id(2UL)
doc2.import_updates(updates)  // 兩邊內(nèi)容自動同步

因為協(xié)同需求經(jīng)常發(fā)生在前端，因此 Loro 發(fā)行了 Wasm API 以保證前端也可以使用這一優(yōu)秀的 CRDTs 庫。但 Rust 編譯的 Wasm 體積偏大，而且難以根據(jù)用戶某一項單獨需求進行 tree-sharking，因此成為很多前端開發(fā)者使用 Loro 的痛點。

但前端如果使用 MoonBit+Lomo 在 JavaScript 后端編寫，則編譯器只會按需編譯 API，最終編譯結(jié)果非常好。同時，MoonBit 的 Wasm 編譯結(jié)果往往會更小、更干凈，就算是使用 Wasm 后端進行發(fā)行也會得到很好的效果。

因此我們可以嘗試根據(jù) JavaScript 后端制作一個協(xié)同文本編輯器來驗證這一點，下面展示了大致的實現(xiàn)方式：

首先在 MoonBit 一側(cè)封裝文檔操作，供 JavaScript 調(diào)用：

///| 創(chuàng)建文檔
pub fn create_doc(peer_id : Int) -> Int {
  let doc = LoroDoc::new()
  doc.set_peer_id(peer_id.to_uint64())
  let text = doc.get_text("body")
  // 訂閱本地更新，自動收集待發(fā)送的數(shù)據(jù)
  let _ = doc.subscribe_local_update((bytes) => {
    pending_updates.push(bytes)
    true
  }
  // ...
}


 ///| 應用編輯操作
pub fn apply_edit_utf16(doc_id : Int, start : Int, delete_len : Int, insert_text : String) -> Bool {
  let doc = docs[doc_id]
  let text = texts[doc_id]
  if delete_len > 0 { doc.text_delete_utf16(text, start, delete_len)? }
  if insert_text.length() > 0 { doc.text_insert_utf16(text, start, insert_text)? }
  true
}

JavaScript 側(cè)處理用戶輸入和同步邏輯：

// 處理用戶輸入
function handleInput(side, other) {
  const nextText = side.el.textContent;
  const change = diffText(side.text, nextText);  // 計算新舊文本的差異
  // 應用到 CRDT（調(diào)用 MoonBit 導出的函數(shù)）
  apply_edit_utf16(side.id, change.start, change.deleteCount, change.insertText);
  side.text = nextText;
  syncFrom(side, other);  // 同步給另一方
}


 // 同步邏輯
function syncFrom(from, to) {
  const updates = drain_updates(from.id);  // 獲取待發(fā)送的更新（MoonBit 導出）
  if (state.online) {
    apply_updates(to.id, updates);  // 在線：立即應用（MoonBit 導出）
  } else {
    from.outbox.push(...updates);   // 離線：緩存到發(fā)件箱
  }
}

最終經(jīng)過一些樣式編寫和頁面編寫的工作，我們就可以得到一個基于 CRDTs 的協(xié)同編輯器：

該項目的源碼在文章末尾已經(jīng)給出，感興趣的讀者可以自行參考并開發(fā)更有意思的項目。

七.總結(jié)

本文從并發(fā)沖突問題出發(fā)，介紹了實時協(xié)作算法的演進：

• OT ：通過轉(zhuǎn)換操作解決沖突，但需要中央服務(wù)器

• RGA ：用唯一 ID 和相對位置實現(xiàn)去中心化，但元數(shù)據(jù)膨脹

• Eg-walker：結(jié)合兩者優(yōu)點，存儲簡單操作，合并時臨時構(gòu)建 CRDT

我們用 MoonBit 實現(xiàn)了上述算法的核心數(shù)據(jù)結(jié)構(gòu)與關(guān)鍵計算部分、還介紹了 Loro/lomo 庫和他們的基本使用，并使用 Lomo 開發(fā)了一個簡單的協(xié)作編輯應用。

從 1989 年 OT 的誕生，到 2011 年 RGA 等 CRDT 的形式化，再到 2024 年 Eg-walker 的創(chuàng)新融合，實時協(xié)作算法經(jīng)歷了三十余年的演進。而近年來隨著 Local-first 理念的興起，CRDT 正從學術(shù)論文走向生產(chǎn)實踐——Figma、Linear 背后都有它的身影。

未來，歷史壓縮、復雜數(shù)據(jù)結(jié)構(gòu)、端到端加密等方向仍在快速推進；MoonBit 高效編譯到 WebAssembly 的能力，也為 CRDTs 在瀏覽器和邊緣設(shè)備上的部署提供了新可能。

八.參考項目/文獻

Lomo-Demo（編輯器）演示：

https://lampese.github.io/lomo-demo/

Lomo-Demo（編輯器）源碼：

https://github.com/Lampese/lomo-demo

Loro：https://loro.dev/

Lomo：https://github.com/Lampese/lomo

Eg-walker 論文：

https://arxiv.org/abs/2409.14252