多人編輯面臨一個根本問題:當兩個人在離線或不同連線下編輯同一份文件時,兩份副本都會變更,必須有人來調和。傳統做法不是鎖住文件的部分區域——阻礙協作——就是採用操作轉換(operational transformation),但其狀態組合會爆炸性增長,且眾所周知難以證明正確。

2011 年,Marc Shapiro 與同事提出了無衝突複製資料型別(CRDT):這類資料結構經過設計,使並行更新可交換。若每次更新都可交換,且合併具結合性,那麼已分歧的副本便能以任意順序合併,仍收斂到同一個完全相同的狀態,既不需要中央協調者,也不需要衝突對話框。暫存器、計數器、集合與文字編輯器都能以此方式建構。

接下來幾年,這套理論逐漸穩固:Martin Kleppmann 與同事於 2018 年發表的 OpSets 論文建立了一個可執行的框架,能以機械方式驗證複製資料型別演算法,揭露了協作文字的一項正確性性質——數個已發表的演算法違反了它——並規格化了一個先前被認為沒有鎖定就不可能做到的原子移動操作。

生產系統採用了這個構想。Figma 的多人引擎明確受到 CRDT 研究啟發:其伺服器權威、逐屬性的設計運作起來就像最後寫入者勝出的暫存器,這是在該公司以不必要地複雜為由否決操作轉換之後所做的選擇。Redis、Riak 與 Cosmos DB 都提供基於 CRDT 的資料型別,而 Apple 的 Notes 則使用 CRDT 在裝置之間同步離線編輯。

讓資料型別在設計上即具合併可交換性

可交換的合併使結果與更新順序無關

副本可以離線編輯,並在沒有任何中央權威的情況下收斂

機械驗證取代了含糊其辭的正確性證明

Figma 式產品獲得了即時協作,而不必承受 OT 的複雜度

若協調是瓶頸,就重新設計資料,使協調變得多餘:選擇結果與順序無關的操作,並行使用者便能免費獲得一致性。

CRDT 如今是離線優先協作與複製的標準答案:Figma 的多人同步、Apple Notes、Redis 與 Riak 的資料型別,以及點對點編輯工具都建立在這個構想之上,而這條研究路線仍在持續,處理文字編輯、樹狀移動與拜占庭環境等困難部分。

追溯依據

參考來源

  1. OpSets: Sequential Specifications for Replicated Datatypes arXiv · arxiv.org ·
  2. How Figma's multiplayer technology works Figma Engineering Blog · figma.com
  3. Conflict-free replicated data type Wikipedia · en.wikipedia.org