這一次，徹底搞懵 CRDT

作者：西瓜 2024-05-15 10:14:00

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

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

CRDT 是什么？

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

CRDT 有以下特性：

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

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

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

算法能夠自動(dòng)地處理不一致的問題。

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

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

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

CRDT 的類型

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

Operation-based

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

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

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

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

operataion 之所以要滿足交換律，是因?yàn)榫W(wǎng)絡(luò)并不可知。

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

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

因?yàn)榻粨Q律這個(gè)特性，Operation-based CRDTs 還有另一個(gè)名字 commutative replicated data types（CmRDTs）。

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

State-based

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

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

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

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

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

一些 CRDT

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

我們來看幾個(gè)簡(jiǎn)單的 CRDT 模型。

AWSet

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

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

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

副本 B 刪除了 a。

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

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

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

RWSet

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

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

LWW

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

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

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

2P-Set

Two-Phase Set。

此模型會(huì)維護(hù)兩個(gè)集合，一個(gè)是新增集合，保存新增的元素，另一個(gè)是刪除集合，保存被刪除的元素。

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

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

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

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

G-Counter

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

此模型使用 n 個(gè)節(jié)點(diǎn)的容器（一個(gè)整數(shù)數(shù)組），每個(gè)副本會(huì)分配一個(gè) id，某個(gè)副本給計(jì)數(shù)器 +1，其實(shí)就會(huì)給對(duì)應(yīng)的數(shù)組元素 +1。

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

PN-Counter

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

多個(gè) CRDT 可以組合成一個(gè)更復(fù)雜的 CRDT。

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

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

YATA

最后我們看看復(fù)雜點(diǎn)的，簡(jiǎn)單介紹一下 Y.js 的 YATA（Yet Another Transformation Approach）模型。

假設(shè)我們有值為 "ABCD" 的字符串。

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

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

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

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

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

至于刪除操作，因?yàn)椴迦氩僮餍枰业皆谧笥夜?jié)點(diǎn)的位置，所以節(jié)點(diǎn)即使被刪除了也是不能從雙鏈表中移出的。

對(duì)此，YATA 選擇使用墓碑機(jī)制。YATA 將對(duì)應(yīng)節(jié)點(diǎn)標(biāo)記為刪除（item.deleted 設(shè)置為 true），并將節(jié)點(diǎn)記錄到刪除集合 DeleteSet 里。

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

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