這一次，徹底搞懵 CRDT
我是前端西瓜哥，今天我們來簡單入門一下 CRDT。
CRDT 是什么？
CRDT，全稱為 conflict-free replicated data type（無沖突復制數據類型），它是一種數據類型，或者說是方案，確保在網絡中的不同副本最后數據保持一致的，可以用協同編輯領域。
CRDT 在 2011 年在論文中被正式提出，雖相比 OT 算法（1989年）起步晚了很長的時間，但實現難度低很多，且出現了高性能的 CRDT 庫 Y.js，越來越多產品選擇使用 CRDT 來實現協同編輯功能。
CRDT 有以下特性：
每個客戶端可獨自操作副本，即支持并發，不需要和其他副本協同溝通。
這是一種樂觀復制（Optimistic replication）的策略。
各個副本可以獨立地在本地編輯，不用把更新提交到服務器，等待服務端返回最新的狀態，用這個新狀態覆蓋掉舊狀態。即可做到離線編輯，本地更新了狀態后再同步到服務端。
算法能夠自動地處理不一致的問題。
一個副本和另一個副本通常是不同的，當其他副本同步過來時，有可能會出現沖突（不一致）的地方，比如兩個副本同時刪除和新增一個元素。
這個需要 CRDT 算法使用特定的策略去自動處理，而不是像 git merge 那樣去手動處理沖突。
同一時刻不同副本的狀態可能不同，但同步后它們能最終收斂（converge），達到相同的狀態（最終一致性）。
CRDT 的類型
CRDT 主要分為兩大類型：Operation-based 和 State-based。
Operation-based
Operation-based CRDTs，基于操作的 CRDT。
副本進行同步時，只會把 新增的本地操作（operation） 發送出去。
另一個副本拿到這個 operation 會將其應用到自己的狀態上，operataion 需要滿足交換律（commutative）。
交換律，指的是交換運算順序，最后的結果不變。比如加法就滿足交換律，a+b 和 b+a 的結果是相等的。
operataion 之所以要滿足交換律，是因為網絡并不可知。
假設有兩個副本 a 和 b 要同步過來給其他副本，你不知道到底誰先到達。對于一些副本可能是先 a 后 b，另一些可能是先 b 后 a，我們需保證在不同順序下，結果是一致的。
通常我們是通過 Generator 函數生成新的 opreation，發送給其他副本，然后這些副本通過 Effector 函數應用這些副本。
因為交換律這個特性，Operation-based CRDTs 還有另一個名字 commutative replicated data types（CmRDTs）。
基于操作的 CRDT 的優點是， 傳輸的數據量較少。
State-based
State-based CRDTs，基于狀態的 CRDT。
一個副本進行同步時，會將 整個完整的本地狀態（state） 發送出去。另一個副本需要支持將其他副本進行合并（merge）的操作，這個 merge 方法需要滿足交換律、分配律，以及冪等性。
基于狀態的 CRDT 的問題是，在文檔很大時，需要傳輸大量的數據，會耗費大量的帶寬，且花費時間長。所有實際生產很少會使用它。
優點是實現更簡單，如果數據量不大，是可以考慮使用的。
State-based CRDTs 同樣也有另一個名字：Convergent Replicated Data Types（CvRDTs）。Convergent 是收斂的意思。
一些 CRDT
CRDT 做到數據最終一致性，是基于數學上的特性來保證的。
我們來看幾個簡單的 CRDT 模型。
AWSet
AWSet（Add-wins set），一種新增優先于刪除的集合數據結構。
假如剛開始的時候，副本 A 和 副本 B 的狀態是一致的，有一個 a 在集合中。
副本 A 刪除了 a，然后再新增 a。
副本 B 刪除了 a。
副本 A 的新增 a 和 副本 B 的刪除 a 同時發生。
此時我們會選擇新增，忽略刪除，最后兩個副本的狀態還是 a 在集合中。
為判斷兩個操作是否是 “同時” 的，我們會附加一個和時序相關的元數據，比如時間戳、版本向量。
RWSet
RWSet（Remove-win set），一種刪除優先新增的集合數據結構。
AWSet 類似，但對于并發的操作，會保留刪除，丟棄新增。
LWW
LWW（Last-writer-wins），最后寫入者優先。
所有的操作會有一個時間戳元數據，副本會對比同步操作的時間戳。
如果大于當前狀態時間戳，覆蓋掉原來的狀態；如果小于當前狀態時間戳，則忽略。
2P-Set
Two-Phase Set。
此模型會維護兩個集合，一個是新增集合，保存新增的元素，另一個是刪除集合，保存被刪除的元素。
模型的最終狀態為新增集合和刪除集合的差集。
另外，集合比較特殊，它是只增集合（grow-only set），只能往集合里加元素，不能從集合里移除元素。
這意味著一個元素如果被刪除了，就再也不能添加回來。所以刪除集合也被叫做 tombstone set（墓碑集合），人噶不能復生。
2P-Set 也算是一種 RW-Set（刪除優先），特別的點在于元素被刪除后不能新增回來。
G-Counter
G-Counter，Grow-only Counter，只增計數器，一個只能增加計數的計數器。
此模型使用 n 個節點的容器（一個整數數組），每個副本會分配一個 id，某個副本給計數器 +1，其實就會給對應的數組元素 +1。
計數器的值為數組的求和。
PN-Counter
PN-Counter，Positive-Negative Counter，一個支持增減的計數器。
多個 CRDT 可以組合成一個更復雜的 CRDT。
類似 G-Counter，但 PN-Counter 使用兩個 G-Counter，一個保存新增數（新增操作），另一個保存減少數（減少操作）。
計數器的值為新增數組求和減去減少數組的和。
YATA
最后我們看看復雜點的，簡單介紹一下 Y.js 的 YATA（Yet Another Transformation Approach）模型。
假設我們有值為 "ABCD" 的字符串。
YATA 模型會將其拆分成一個個字符，加上元數據，然后按順序首尾相連組成一個雙鏈表。
// 大概這樣子
{
id: '2:0', // 客戶端 ID + clock ID
val: 'B',
left: a, // 當前節點的左節點
right: c, // 右節點
origin: a, // 節點創建時的左節點
rightOrigin: c // 節點創建時的右節點
}操作有 “插入” 和 “刪除”。
假設本地在 AB 之間插入 E，此時沒有發送同步，然后收到其他副本傳過來的 F，也是要插入到 AB 之間。
此時 E 和 F 是沖突的，我們會對唯一的 id（某種意義上的時間戳）使用特定的規則來決定先后順序。
至于刪除操作，因為插入操作需要找到在左右節點的位置，所以節點即使被刪除了也是不能從雙鏈表中移出的。
對此，YATA 選擇使用墓碑機制。YATA 將對應節點標記為刪除（item.deleted 設置為 true），并將節點記錄到刪除集合 DeleteSet 里。
這里其實可以看到，CRDT 通常是需要加很多元數據的，尤其是復雜數據結構且數據量較大的場景，所以這也是 CRDT 起初被詬病占用內存高的原因。
但 Y.js 通過一系列手段（比如將多個節點合并為一個大節點），將性能優化到足夠面對大多數場景，證明了用 CRDT 是做協同編輯的是不用擔心性能問題的，如果有，一定是你沒優化好。
結尾
本文只是簡單介紹一些 CRDT 是什么，并感受了一些簡單的 CRDT 模型，希望對你有所幫助。
