我是前端西瓜哥，今天我們來簡單入門一下 CRDT。

CRDT 是什么？

CRDT，全稱為 conflict-free replicated data type（無沖突復制數(shù)據(jù)類型），它是一種數(shù)據(jù)類型，或者說是方案，確保在網(wǎng)絡中的不同副本最后數(shù)據(jù)保持一致的，可以用協(xié)同編輯領域。

CRDT 在 2011 年在論文中被正式提出，雖相比 OT 算法（1989年）起步晚了很長的時間，但實現(xiàn)難度低很多，且出現(xiàn)了高性能的 CRDT 庫 Y.js，越來越多產(chǎn)品選擇使用 CRDT 來實現(xiàn)協(xié)同編輯功能。

CRDT 有以下特性：

每個客戶端可獨自操作副本，即支持并發(fā)，不需要和其他副本協(xié)同溝通。

這是一種樂觀復制（Optimistic replication）的策略。

各個副本可以獨立地在本地編輯，不用把更新提交到服務器，等待服務端返回最新的狀態(tài)，用這個新狀態(tài)覆蓋掉舊狀態(tài)。即可做到離線編輯，本地更新了狀態(tài)后再同步到服務端。

算法能夠自動地處理不一致的問題。

一個副本和另一個副本通常是不同的，當其他副本同步過來時，有可能會出現(xiàn)沖突（不一致）的地方，比如兩個副本同時刪除和新增一個元素。

這個需要 CRDT 算法使用特定的策略去自動處理，而不是像 git merge 那樣去手動處理沖突。

同一時刻不同副本的狀態(tài)可能不同，但同步后它們能最終收斂（converge），達到相同的狀態(tài)（最終一致性）。

CRDT 的類型

CRDT 主要分為兩大類型：Operation-based 和 State-based。

Operation-based

Operation-based CRDTs，基于操作的 CRDT。

副本進行同步時，只會把 新增的本地操作（operation） 發(fā)送出去。

另一個副本拿到這個 operation 會將其應用到自己的狀態(tài)上，operataion 需要滿足交換律（commutative）。

交換律，指的是交換運算順序，最后的結(jié)果不變。比如加法就滿足交換律，a+b 和 b+a 的結(jié)果是相等的。

operataion 之所以要滿足交換律，是因為網(wǎng)絡并不可知。

假設有兩個副本 a 和 b 要同步過來給其他副本，你不知道到底誰先到達。對于一些副本可能是先 a 后 b，另一些可能是先 b 后 a，我們需保證在不同順序下，結(jié)果是一致的。

通常我們是通過 Generator 函數(shù)生成新的 opreation，發(fā)送給其他副本，然后這些副本通過  Effector 函數(shù)應用這些副本。

因為交換律這個特性，Operation-based CRDTs 還有另一個名字 commutative replicated data types（CmRDTs）。

基于操作的 CRDT 的優(yōu)點是， 傳輸?shù)臄?shù)據(jù)量較少。

State-based

State-based CRDTs，基于狀態(tài)的 CRDT。

一個副本進行同步時，會將 整個完整的本地狀態(tài)（state） 發(fā)送出去。另一個副本需要支持將其他副本進行合并（merge）的操作，這個 merge 方法需要滿足交換律、分配律，以及冪等性。

基于狀態(tài)的 CRDT 的問題是，在文檔很大時，需要傳輸大量的數(shù)據(jù)，會耗費大量的帶寬，且花費時間長。所有實際生產(chǎn)很少會使用它。

優(yōu)點是實現(xiàn)更簡單，如果數(shù)據(jù)量不大，是可以考慮使用的。

State-based CRDTs 同樣也有另一個名字：Convergent Replicated Data Types（CvRDTs）。Convergent 是收斂的意思。

一些 CRDT

CRDT 做到數(shù)據(jù)最終一致性，是基于數(shù)學上的特性來保證的。

我們來看幾個簡單的 CRDT 模型。

AWSet

AWSet（Add-wins set），一種新增優(yōu)先于刪除的集合數(shù)據(jù)結(jié)構。

假如剛開始的時候，副本 A 和 副本 B 的狀態(tài)是一致的，有一個 a 在集合中。

副本 A 刪除了 a，然后再新增 a。

副本 B 刪除了 a。

副本 A 的新增 a 和 副本 B 的刪除 a 同時發(fā)生。

此時我們會選擇新增，忽略刪除，最后兩個副本的狀態(tài)還是 a 在集合中。

為判斷兩個操作是否是 “同時” 的，我們會附加一個和時序相關的元數(shù)據(jù)，比如時間戳、版本向量。

RWSet

RWSet（Remove-win set），一種刪除優(yōu)先新增的集合數(shù)據(jù)結(jié)構。

AWSet 類似，但對于并發(fā)的操作，會保留刪除，丟棄新增。

LWW

LWW（Last-writer-wins），最后寫入者優(yōu)先。

所有的操作會有一個時間戳元數(shù)據(jù)，副本會對比同步操作的時間戳。

如果大于當前狀態(tài)時間戳，覆蓋掉原來的狀態(tài)；如果小于當前狀態(tài)時間戳，則忽略。

2P-Set

Two-Phase Set。

此模型會維護兩個集合，一個是新增集合，保存新增的元素，另一個是刪除集合，保存被刪除的元素。

模型的最終狀態(tài)為新增集合和刪除集合的差集。

另外，集合比較特殊，它是只增集合（grow-only set），只能往集合里加元素，不能從集合里移除元素。

這意味著一個元素如果被刪除了，就再也不能添加回來。所以刪除集合也被叫做 tombstone set（墓碑集合），人噶不能復生。

2P-Set 也算是一種 RW-Set（刪除優(yōu)先），特別的點在于元素被刪除后不能新增回來。

G-Counter

G-Counter，Grow-only Counter，只增計數(shù)器，一個只能增加計數(shù)的計數(shù)器。

此模型使用 n 個節(jié)點的容器（一個整數(shù)數(shù)組），每個副本會分配一個 id，某個副本給計數(shù)器 +1，其實就會給對應的數(shù)組元素 +1。

計數(shù)器的值為數(shù)組的求和。

PN-Counter

PN-Counter，Positive-Negative Counter，一個支持增減的計數(shù)器。

多個 CRDT 可以組合成一個更復雜的 CRDT。

類似 G-Counter，但 PN-Counter 使用兩個 G-Counter，一個保存新增數(shù)（新增操作），另一個保存減少數(shù)（減少操作）。

計數(shù)器的值為新增數(shù)組求和減去減少數(shù)組的和。

YATA

最后我們看看復雜點的，簡單介紹一下 Y.js 的 YATA（Yet Another Transformation Approach）模型。

假設我們有值為 "ABCD" 的字符串。

YATA 模型會將其拆分成一個個字符，加上元數(shù)據(jù)，然后按順序首尾相連組成一個雙鏈表。

// 大概這樣子
{
  id: '2:0', // 客戶端 ID + clock ID
  val: 'B',
  left: a, // 當前節(jié)點的左節(jié)點
  right: c, // 右節(jié)點
  origin: a, // 節(jié)點創(chuàng)建時的左節(jié)點
  rightOrigin: c // 節(jié)點創(chuàng)建時的右節(jié)點
}

操作有 “插入” 和 “刪除”。

假設本地在 AB 之間插入 E，此時沒有發(fā)送同步，然后收到其他副本傳過來的 F，也是要插入到 AB 之間。

此時 E 和 F 是沖突的，我們會對唯一的 id（某種意義上的時間戳）使用特定的規(guī)則來決定先后順序。

至于刪除操作，因為插入操作需要找到在左右節(jié)點的位置，所以節(jié)點即使被刪除了也是不能從雙鏈表中移出的。

對此，YATA 選擇使用墓碑機制。YATA 將對應節(jié)點標記為刪除（item.deleted 設置為 true），并將節(jié)點記錄到刪除集合 DeleteSet 里。

這里其實可以看到，CRDT 通常是需要加很多元數(shù)據(jù)的，尤其是復雜數(shù)據(jù)結(jié)構且數(shù)據(jù)量較大的場景，所以這也是 CRDT 起初被詬病占用內(nèi)存高的原因。

但 Y.js 通過一系列手段（比如將多個節(jié)點合并為一個大節(jié)點），將性能優(yōu)化到足夠面對大多數(shù)場景，證明了用 CRDT 是做協(xié)同編輯的是不用擔心性能問題的，如果有，一定是你沒優(yōu)化好。

結(jié)尾

本文只是簡單介紹一些 CRDT 是什么，并感受了一些簡單的 CRDT 模型，希望對你有所幫助。