初探富文本之CRDT協同演算法

CRDT的英文全稱是Conflict-free Replicated Data Type，最初是由協同文本編輯和移動計算而發展的，現在還被用作在線聊天系統、音頻分發平臺等等，當前CRDT演算法在富文本編輯器領域的協同依舊是典型的場景，常用于作為實作檔案協同的底層演算法，支持多個用戶同時編輯檔案，不會因為用戶并發修改導致沖突，而導致結果不一致甚至資料丟失的問題，

描述

Conflict-free Replicated Data Type直譯過來就是無沖突的復制資料型別，從名字可以看出來，CRDT的重點在于無沖突復制和資料型別，去掉定語的話就可以得到CRDT是一種資料結構，也就是說CRDT是通過資料結構來保證最終一致性的，在分布式系統中，不同節點之間的資料復制存在一致性問題即強一致性問題，CRDT是作為一種理論來指導如何將原有資料結構設計成在資料復制程序中通向最終一致性的一種新的資料結構，假設此時我們擁有多個副本或者操作，如果托管副本的計算機之間沒有協調，此時進行合并的話則可能導致副本之間的不一致，這通常是無法解決的，當更新存在沖突時，要恢復一致性和資料完整性，可能需要部分甚至全部更新的洗掉，由此CRDT指導我們在有多個副本或者操作進行合并或者更新時，使得我們的資料能根據一定的規則自動合并、解決沖突，最終達到強一致性的效果，回到富文本協同上，檔案協同編輯同樣可以理解為分布式應用的一種，而CRDT通過資料結構的設計保證并發操作資料的最終一致性，簡單來說，CRDT就是可以在網路中的多個終端上復制的資料結構，副本可以獨立和并行地更新，不需要在副本之間進行協調，并保證不會有沖突發生，從而保證最終各個副本的內容一致，

在討論具體的協同演算法之前，我們探究一下為什么要有協同演算法，如果沒有協同演算法的話會出現什么問題，以及具體會出現問題的場景，那么假如我們有一個在線的檔案應用，而我們是一個團隊，我們有可能對同一篇檔案進行編輯，既然我們會同時編輯，那么就有可能產生沖突，假設檔案此時的內容為A，此時U1和U2兩位用戶同時在編輯，也就是說這兩位都是從檔案的A狀態開始編輯，當U1編輯完成之后，檔案狀態是B，U1對檔案進行了保存，此時U2也寫完了，檔案狀態是C，U2也對檔案進行了保存，那么此時檔案的狀態就是C了，由U1撰寫的A -> B狀態的內容修改便丟失了，為了解決這樣的問題，通常有以下幾個方案，

樂觀鎖

樂觀鎖，主要就是一種對比于悲觀鎖的說法，因為樂觀鎖的操作程序中其實沒有沒有任何鎖的參與，嚴格的說樂觀鎖不能稱之為鎖，樂觀鎖總是假設最好的情況，每次去拿資料的時候都認為別人不會修改，所以不會上鎖，可能需要在更新的時候會判斷一下在此期間別人有沒有去更新這個資料提示一下，或者干脆不會給予任何的提示資訊，

那么具體到檔案編輯上邊，我們可以樂觀地認為永遠不會有兩個人同時編輯同一篇檔案，現實中也可能有這種情況，比如團隊中每個人只負責幾篇檔案，其他人不需要也沒有權限去編輯自己負責之外的檔案，那么基于這種要求，我們可以樂觀地認為永遠不會出現沖突的問題，那么自然也就不需要對檔案的管理做任何限制了，只需要完整地提供編輯能力即可，

悲觀鎖

悲觀鎖，顧名思義是基于一種以悲觀的態度類來防止一切資料沖突的方式，其以一種預防的姿態在修改資料之前把資料鎖住，然后再對資料進行讀寫，在其釋放鎖之前其他的任何人都不能對資料進行操作，直到前面一個人把鎖釋放后下一個人才可對資料進行加鎖，繼而才可以對資料進行操作，通過這種方式可以完全保證資料的獨占性和正確性，

那么具體到檔案編輯上邊，我們可以對同一篇檔案的編輯操作權限進行加鎖，這樣就可以保證同一時間只有一個人可以對檔案進行編輯，其他人只能等待，直到前面的人把檔案編輯完成并且釋放鎖之后，下一個人才可以對檔案進行編輯，當然也可以開一個口子允許強行搶占并且將被搶占者的現場存盤下來，相當于將一個并發操作壓成了線性操作，這樣就可以通過獨占的方式保證檔案的正確性，避免檔案的內容沖突與丟失，

自動合并

自動合并，檔案內容自動合并以及沖突處理的方式也是一個可行的方案，類似于Git的版本管理思想，可以對提交的內容進行diff差異對比、merge合并等操作，也可以在出現無法解決的沖突時出現時交給用戶主動處理，GitBook是采用這種方式解決沖突問題的，

協同編輯

協同編輯，可以支持多個用戶同時編輯檔案，不會因為用戶并發修改導致沖突，而導致結果不一致甚至資料丟失的問題，協同編輯重點在于協同演算法，主要有Operational Transformation(OT)與Conflict-free Replicated DATA Type(CRDT)兩種協同演算法，協同演算法不需要是正確的，其只需要保持一致，并且需要努力保持你的意圖，就是說協同演算法最主要的目的是在盡可能保持用戶的意圖的情況下提供最終的一致性，重點在于提供最終一致性而不是保持用戶的意圖，當前石墨檔案、騰訊檔案、飛書檔案、Google Docs都是基于OT協同演算法的，Atom編輯器使用的是CRDT協同演算法，

CRDT協同演算法

Conflict-free Replicated DATA Type(CRDT)協同演算法的核心思想在于解決沖突，而在于構造一種資料結構來避免沖突，避免了沖突就可以直接進行合并，最終得到檔案內容，CRDT協同演算法的目的是在盡可能保持用戶意圖的情況下，保持檔案的最終一致性，舉個例子，當A和B同時在檔案的L處插入了不同的字符，那么誰插入的字符在前協同演算法并不關心，其只需要盡可能地根據一定策略例如時間戳來判斷究竟是誰的字符在前，但是最終計算出的結果即究竟誰的字符在前并不影響協同演算法，其關心的重點在于經過協同演算法將用戶產生的Op調度之后，在每個人面前呈現的檔案內容是絕對一致的，這就是保持檔案的最終一致性，從功能的角度上說，協同演算法保證的是在多人同時在線編輯的情況下，由于每個人提交的內容是不一樣的，就需要通過協同演算法的調度，使得每個用戶最終都能看到一樣的內容，實際上在線檔案本身就是一個資料一致性要求很強的專案，所以無論是使用CRDT演算法還是OT演算法來實作協同，保證最終一致性就是必須要考慮的基本內容，

由于CRDT設計上可以完成對于各個副本的合并與更新而不會產生沖突，那么經由CRDT實作的演算法就可以直接在客戶端之間互相傳遞，相互同步至最終一致性的狀態，也就是各個用戶之間可以直接P2P進行資料合并而不需要中央服務器進行調度，由此CRDT可以很好地支持去中心化的應用，即使沒有中心化服務器各端之間也能完成同步，

談到了最終一致性和分布式系統，那么就不得不提到CAP理論，CAP理論指出在一個分布式系統中，最多只能同時滿足Consistency(一致性)、Availability(可用性)和Partition Tolerance(磁區容錯性)中的兩項，

• 一致性Consistency: 對于客戶端的每次讀操作，要么讀到的是最新的資料，要么讀取失敗，換句話說，一致性是站在分布式系統的角度，對訪問本系統的客戶端的一種承諾：要么我給你回傳一個錯誤，要么我給你回傳絕對一致的最新資料，不難看出，其強調的是資料正確，
• 可用性Availability: 任何客戶端的請求都能得到回應資料，不會出現回應錯誤，換句話說，可用性是站在分布式系統的角度，對訪問本系統的客戶的另一種承諾：我一定會給你回傳資料，不會給你回傳錯誤，但不保證資料最新，強調的是不出現回應錯誤，
• 磁區容錯性Partition tolerance:由于分布式系統通過網路進行通信，網路是不可靠的，當任意數量的訊息丟失或延遲到達時，系統仍會繼續提供服務，不會掛掉，換句話說，磁區容忍性是站在分布式系統的角度，對訪問本系統的客戶端的再一種承諾：我會一直運行，不管我的內部出現何種資料同步問題，強調的是不掛掉，

對于一個分布式系統而言，P是前提，必須保證，因為只要有網路互動就一定會有延遲和資料丟失，這種狀況我們必須接受，必須保證系統不能掛掉，所以只剩下C、A可以選擇，要么保證資料一致性即資料絕對正確，要么保證可用性即保證回應不出錯，首先我們要理解一下為什么P是前提，這里的場景是分布式系統，網路是不可靠的，一定會存在網路延遲與丟失等問題，如果不允許存在網路磁區也就是說網路是一直保證運行正常的，那么顯然每次寫入資料都可以進行同步，自然一致性和可用性顯然得到了保障，但這也不是分布式系統了，

我們來舉個例子，在網路發生問題時，為什么需要在C和A之間進行選擇，假設在分布式系統中存在100個節點，但由于故障，使得網路發生了磁區，其中有一半的節點無法向另外一半節點通信，于是系統被分割為A區與B區，在網路磁區的情況下，客戶端發送請求嘗試來對A區一個節點進行資料寫入，由于AB區網路不通，這時候無法同步寫入資訊給到B區節點，在這種場景下，究竟允不允許當前客戶端進行資料寫入呢，

• 如果允許客戶端資料寫入，那么當前節點的可用性得到了保證，但是由于網路磁區，所以網路不可觸達，資料無法同步，因此此時是無法滿足一致性，也就是分布式系統中，同時訪問兩個節點，可能會回傳不同資料，
• 如果不允許客戶端資料寫入，那么當前節點的一致性得到了保證，所有節點資料都是一致的，但是由于資料都無法寫入，這時系統顯然是不可用的，需要阻塞等待，直到網路連接恢復，也就是可用性無法滿足，

實際上CAP特性三選二的描述其實具有誤導性，從上邊的例子中也可以看出，不是在所有時候都只能選擇兩個特性，在不存在網路失敗的情況下即分布式系統正常運行時，C和A能夠同時保證，只有當網路發生磁區或失敗時，才會在C和A之間做出選擇，但是誰也無法保證任何時刻網路都是暢通無阻的，所以必須要處理在這種情況下的策略，以此來取得C和A的權衡，作者Eric Brewer在2012年也發表論文解釋了CAP實際上只是禁止了設計空間存在磁區時的完美可用性和一致性，而實際上在C和A之間的權衡的設計非常靈活，CRDT就是一個很好的例子，CRDT演算法正是在滿足Partition Tolerance(磁區容錯性)的前提下，盡可能地保證Consistency(一致性)和Availability(可用性)，同樣OT協同演算法也是一樣通過保證最終一致性來完成這個權衡的，

在協同編輯的場景下，我們似乎能夠同時滿足了CAP的三個場景限制，假設在網路差的情況下，兩個客戶端同時提交，雖然暫時一致性無法滿足，本地客戶端會看到不同的內容，但網路恢復后，通過協同演算法資料也能保持一致，這不是既滿足了一致性又滿足了可用性，這個想法是對的，只是這里我們保證的一致性不等于CAP理論的一致性，CAP理論是假設在沒有網路延遲的情況下的強一致性，也就是資料時刻都是一致的，而協同編輯的場景的一致性則是最終一致性，前文也提到過，在C和A之間的權衡的設計非常靈活，既然無法做到強一致性Strong consistency，那么應用可以根據自身的業務特點，采用適當的方式來使系統達到最終一致性Eventual consistency，這個就又需要說到BASE理論了，

• BA: Basically Avaliable，基本可用，允許損失部分可用性，允許犧牲回應時間、降級系統功能等操作，
• S: Soft State，軟狀態，允許存在資料中間狀態，不要求強一致性，并不影響整體可用性，允許副本之間的資料同步延遲，
• E: Eventually consistency，最終一致性，所有的副本，在最終都能達到資料一致的狀態，但不要求實時的強一致性，

在BASE理論中，我們可以看到協同編輯檔案的場景中，雖然CAP的強一致性無法滿足，但通過靈活地設計C和A，損失部分可用性，允許暫時的客戶端不一致情況，通過協同編輯沖突演算法，可以解決資料不一致問題，達到了最終的資料一致性，實際上在分布式理論上又有很多研究，有著強一致性、弱一致性、順序一致性、最終一致性、因果一致性等，而最終一致性也有讀寫一致性、寫讀一致性、單調讀一致性、單調寫一致性等劃分，在這里就不再贅述了，

之后我們再簡單舉一個例子，看看應該如何去實作最終一致的分布式系統，假設我們當前有一個賬戶是T，初始時這個賬戶有100塊錢，用戶可以通過系統里面好幾個節點，例如A、B、C，訪問T這個賬戶，并且可以在任何時刻都對T進行操作，注意此時我們并沒有中央服務器來保存這100塊錢，而是每個賬戶都各自存盤了這個數字，在這個分布式系統中我們不考慮安全方面的因素，我們只需要最終保證每個人的資料都是一致的即可，

假設某個時刻t1，A往T中存了10塊錢，B則向T中取了10塊錢，C則在接下來的一個時刻查詢T有多少錢，這幾個操作都是同時發生的，那么，我們的分布式系統會保證這三個操作都能完成，于是在本地:

• 在A系統看來，T有110塊錢，
• 在B系統看來，T有90塊錢；
• 在C系統看來，T有100塊錢，

在這個時刻t1，這三者都是對的，因為我們可以在最終一致性系統中，存在不一致的時刻，那么經過一段時間之后，假設是t2，我們需要使得A、B和C系統看來，T都有100塊錢，即保證最終一致，那么這中間肯定需要做一些操作，即A、B和C系統之間交換一些必要的資訊資料，那么現在麻煩來了，我們需要如何進行資料交換，如果在各節點我們只是存了T的余額，例如用一個整數變數，這樣顯然是不行的，因為當A系統和B系統的資料傳輸到C系統時，C無法分辨A或者B系統的結果到底誰對，那么重點來了，我們應該如何處理這個問題，最簡單的處理方案，加入額外的資料，通過額外的資料來保證合并的正確，這也就是CRDT的重點，

那么在這個例子里面，我們可以這樣設計，每個系統存盤的不是一個最終數值，而是一系列包含了時刻與余額的記錄，假設我們的系統是從t0時刻開始的，那么在我們的例子里面，t1時刻存盤的資料如下所示:

• A系統存盤的是(t0, 100)、(t1, 110)，
• B系統存盤的是(t0, 100)、(t1, 90)，
• C系統存盤的是(t0, 100)、(t1, 100)，

那么在t2時刻，我們進行了資料傳輸，對于C而言收到了A t0->t1 +10的操作，收到了B t0->t1 -10的操作，由此C在t2時刻依舊是100；而對于A而言，收到了B t0->t1 -10的操作，C沒有更新操作所以不需要同步；對于B而言收到了A t0->t1 +10的操作，C沒有更新操作所以不需要同步，最終A、B、C三者得到了一致的資料總和表示100，由此得到了最終一致性，當然這個例子足夠簡單，答案也足夠的粗糙，而且在實際的應用中，我們必須要考慮更多的資料型別和應用場景，于是設計一個能夠保持最終一致性的資料結構，就會變成一件很難的事情，由此才需要圍繞著CRDT的理論進行分布式系統的設計，從而減少我們的對于分布式協同設計的心智負擔，

回到協同，在了解CRDT協同演算法之前，我們也可以了解一下CRDT協同演算法與OT協同演算法的主要區別，首先CRDT與OT都提供了最終一致性，這也是協同編輯的最終目標，但是這兩種方案達成這一目標的方式不一樣：

• CRDT無沖突復制資料型別是通過資料結構來做到這一點，CRDT有兩種實作方式，基于狀態的CvRDT收斂復制資料型別和基于操作的CmRDT可交換復制資料型別，CvRDT是將各個副本進行合并，進行多少次合并或以何種順序進行合并并不重要，所有副本都會收斂，CmRDT則具有可交換的操作，因此無需轉換操作即可正確應用這些操作，
• CRDT更適合分布式系統，可以不需要中央服務器，
• CRDT通過資料結構保證了編輯的無沖突，增加了空間復雜度，
• OT操作轉換則是通過操作Operation轉換Transformation來做到這一點，終端所進行的操作O通過網路傳輸，其他終端在收到操作O后需要進行轉換T，之后才可以應用到檔案上，最基礎的OT是通過轉換索引位置以確保收斂，
• OT通常必須要有中央服務器進行協同調度，
• OT通過演算法處理編輯沖突的問題，增加了時間復雜度，

基本原理

在上邊我們討論到了CAP定理，我們需要在一致性與可用性之間做出取舍，能夠達到最終一致性而暫時地損失部分可用性是完全可以接受的，不過無論如何在實際情況中設計這樣一個分布式系統還是非常復雜的，而CRDT就是是這樣一個通向最終一致性的理論，可以指導我們去正確地設計一個高可用的分布式系統，CRDT同樣也并不僅僅應用在在協同領域，當前各種分布式系統和應用均開始嘗試CRDT，redislabs和riak已經實作多種資料結構，微軟的CosmosDB也在azure上使用CRDT作為多活一致性的解決方案，

那么CRDT究竟代表了什么，其是如何做到合并時不會出現沖突的，在分布式系統中復制有兩種實作途徑，一種是在主節點和從節點之間復制全量狀態，還有一種是就是復制操作本身，簡單解釋一下，全量復制狀態類似于我們把當前正在撰寫的整個檔案都復制出來同步到其他客戶端，而復制操作本身類似于我們只把當前編輯時造成的Op復制出來同步到其他客戶端，那么如果是復制狀態，也就是全量復制，就需要有一些狀態收斂規則，因此我們就可以創建Convergent Replicated Data Types，也就是CvRDT基于狀態的收斂復制資料型別，也被稱為State-based CRDT，而如果是復制操作，那么這個操作就需要被設計為Commutative可交換的，而并不需要進行操作變換，由此可以創建Commutative Replicated Data Types，也就是CmRDT可交換復制資料型別，也被稱為Op-based CRDT，在這兩種情況下，目標都是通過確保操作彼此不會沖突獨立發生從而為了避免協調，所以可以總稱為Conflict-free Replicated Data Type，也就是CRDT，

State-based CRDT

基于狀態的CRDT，名字聽著很嚇人，實際上突然理解起來也挺嚇人，但是拆開看就沒有那么難以理解了，State-based CRDT的結點和結點傳輸的是狀態，存在一個算子Merge: (SA, SB) => SC, 收到傳輸的狀態就和自己存盤的狀態Merge，這個算子必須滿足交換律、結合律和冪等律，所以如果用抽象代數的角度形容地話，其使整個狀態系統形成了一個半格，所以最終只要能接受到其他所有節點的新狀態，那么永遠能保證系統最侄訓收斂，由此并不會發生沖突，這樣也去除了對于CmRDT的底層通訊機制依賴，但是因為傳遞的是狀態，所以最后傳輸可能有點大，當然也是存在優化策略的，

上邊這段話可能有些難以理解，我們慢慢拆開來研究一下，首先我們看下算子Merge: (SA, SB) => SC，這也就是說我們同步狀態的內容是需要合并的，這也就是我們做State-based CRDT的目的，即收到傳輸的狀態就和自己存盤的狀態Merge，接下來就是我們這個算子需要保證的條件了，先來回顧一下交換律、結合律和冪等律:

• 交換律: A ∪ B = B ∪ A，
• 結合律: (A ∪ B) ∪ C = A U (B U C)，
• 冪等律: A U A = A，

看到這三個公式我們就可以比較容易地理解這個為什么這個算子需要滿足這三律了，我們首先需要關注的一點是網路是不可靠的，而分布式的系統必須要依賴于網路進行資料傳輸，由此我們來看下為什么需要保證這三個公式:

• 交換律，假設我們有A、B兩位用戶相互進行資料傳輸，A資料同步到B就是A ∪ B，B資料同步到A就是B U A，那么在需要保證最終一致性的前提下則必須保證交換律進而能夠保證正確地進行資料合并，即應用順序無關緊要，
• 結合律，假設我們有A、B、C、D、E五位用戶相互進行資料傳輸，此時A、B、C對資料進行了改動，對于D、E而言就需要從其他三個客戶端進行資料同步，由于存在網路延遲，無法哪個客戶端的位置先行到達，也就是D的合并順序可能是A B C，而E的合并順序可能是B C A，所以需要滿足結合律才能夠保證正確進行資料合并，即分組無關緊要，
• 冪等律，假設我們有A、B兩位用戶相互進行資料傳輸，當A用戶進行改動后將副本進行了網路傳輸，但是久久沒有得到ACK確認，那么此時可能會有一個超時重傳的機制，我們又將A發送了出去，但是巧合的是剛才那個包并沒有丟失，只是傳遞比較慢，而新的A包由于選擇了其他的路由線路也沒有丟失，此時兩個相同的A包同時到達了B，由于B未發生修改，B合并了第一個A之后相當于內容與A相同，此時再合并第二個A就需要保證冪等性從而保證能夠正確進行資料合并，即重復無關緊要，

可以看出其實滿足上邊三個公式都是由于網路的不可靠，而我們為了保證最終一致性從而需要對資料結構進行設計，此外需要注意的是如果我們能夠保證Exactly once的語意，則冪等律條件是可以放寬的，舉個例子加法本身滿足交換律結合律但不冪等，假如此時我們能夠保證加法操作只復制一次，其結果還是最終一致的，實際上保證了上述三個定理，我們在分布式系統同步資料的時候就可以無需考慮合并的順序以及多次合并的問題了，且能夠保證最終一致性，

下邊再看一下半格的概念，在了解半格之前我們需要探討一下偏序集的概念，實際上了解了半格之后，我們就可以大概理解CRDT如何做到合并不會出現沖突的問題了，設P是集合，P上的二元關系≤滿足以下三個條件，則稱≤是P上的偏序關系或部分序關系，

• 自反性: ?a∈P，a≤a，
• 反對稱性: ?a, b∈P，若a≤b且b≤a，則a=b，
• 傳遞性：?a, b, c∈P，若a≤b且b≤c，則a≤c，

需要注意的是這里的≤不必是指一般數學意義上的小于或等于，我們通常認為其意義是x排在y前面x precedes y，也就是說這個偏序關系不一定是比大小，也并不要求集合元素之間是數字，關鍵要如何定義這個二元關系，只要要滿足上述三條性質，即是偏序關系，可能有些抽象哈，我們舉個例子，自然數的集合配備了它的自然次序即小于等于關系，那么這個偏序是全序，我們同樣也可以定義一個關系≤為子集，也就是說我們可以通過子集來比較集合，從而構造一個偏序關系，下面這個例子中就可以由子集偏序關系看出{} ≤ {x} {x} ≤ {x, y} {x, y} ≤ {x, y, z} ...，

         {x, y, z}
{x, y}    {x, z}    {y, z}
  {x}       {y}       {z}
             {}

接下來我們再看一下格相關的概念，格是一個偏序集，具有不同的頂部(最小上界)和不同的底部(最大下界)，半格同樣也是一個偏序集，且每個非空集合都有上確界或者下確界，而上確界被稱為Least upper bound即LUB，也就是說半格相較于格來說，只有一個不同的頂部或底部，所以是在名字上也可以看出是叫做半個格，連接半格是具有不同頂部(最小上界)的半格，而相交半格是具有不同底部(最大下界)的半格，任何表示為半格的資料型別都可以實作為保證收斂的資料結構，例如，計算一組值的Max()將始侄訓傳相同的結果，無論接收值的順序如何，只要最終接收到所有值，因為Max()操作是保證了交換律、結合律和冪等律的，依舊拿上邊的這個集合例子來說，我們此時改變了定義，在這里有兩種格子，對于集合是定義了Union(items)格子，對于資料是定義了Max(value)格子，對于兩個半格而言，我們保證了一個最大上界，在例子中我們三個集合的最終一致性資料為{x, y, z} 3，

         {x, y, z}                 3   
{x, y}    {x, z}    {y, z}    2    3    3
  {x}       {y}       {z}     1    2    3
             {}                   null

在經歷了半格、偏序集之后，似乎我們最終又回到了交換律、結合律和冪等律，實際上我們在半格中也提到了，只要我們能夠定義一個有意義的最小上界LUB函式，我們就能創建CRDT，如果上邊的Max(x, y)不是很直觀的話，我們在本文資料結構一節中會有更多的資料結構示例來解釋這個問題，或許在富文本的資料結構中并沒有Max(x, y)這么簡單地能夠滿足半格條件的實作方法，但是別忘了我們可以為資料附加額外的資訊，在我們前邊提到了CRDT是通過資料結構保證了編輯的無沖突，從而增加了空間復雜度，而資料結構的設計很重要的一點就是攜帶其他的資訊，例如時間戳、邏輯時間戳、用戶唯一id等等，通過附帶元資訊的方式是讓其更新保持單調，從而能夠構建一個帶有最小上界偏序關系的半格，

Op-based CRDT

基于操作的CRDT，實際上類似于上邊的State-based CRDT，只不過我們操作的物件變成了操作Op的復制與同步，那么同樣對于操作，我們也需要為其設計為符合交換律、結合律與冪等律的，因為即使傳輸的物件從狀態轉換到了操作，也是需要經過網路進行傳輸的，那么就不可避免地出現了上述分布式系統必須要解決的問題，所以傳輸的操作也是需要經過設計的，而使用Op-based CRDT能夠獲得的明顯提升是同步程序中需要傳輸的資料顯著降低，

那么當前客戶端的更新操作本身滿足以上三律，那么復制過后的操作同步到其他客戶端的時候僅需要對傳輸過來的操作進行回放即可，最簡單的例子是集合求并集，如果本地的客戶端操作無法滿足上述的條件，則可以考慮將元資訊附加到操作Op上從而滿足三律條件，同樣的，如果我們能夠保證Exactly once的語意，則冪等律條件是可以放寬的，如果依舊無法滿足的話，則可以考慮同步副本資料即State-based CRDT，同時附帶額外元資訊，通過元資訊讓本地更新與其他客戶端合并操作具備以上三律，有趣的是，使用基于操作的方式總是能夠模擬基于狀態的方式，

由于這里操作的物件是Op，我們重新表示一下在快照的基礎上滿足于交換律、結合律與冪等律的方式，類似于OT的表示，我們需要定義一些概念，snapshot是當前檔案的內容，apply(snapshot, op)是在snapshot的基礎上應用Op從而更新檔案，那么三律的表示如下:

• 交換律: apply(apply(snapshot, A), B) = apply(apply(snapshot, B), A)，
• 結合律: apply(apply(apply(snapshot, A), B), C)= apply(apply(apply(snapshot, B), C), A)，
• 冪等律: apply(apply(snapshot, A), A) = apply(snapshot, A))，

在Op-based CRDT的設計中，我們還需要考慮到因果一致性，我們需要在apply之前對快照進行檢查，保證Op所依賴的因果順序成立，例如洗掉x節點的操作依賴于x節點被創建的操作，否則就無法應用該操作，在不滿足條件的情況下需要阻塞延遲，這也意味著我們有責任保證每個操作的前置狀態都是能夠得到滿足的，也就是說我們需要保證每個操作的前置條件都能通過按因果順序應用得到滿足，從而所有更新函式都會終止，最終各個客戶端的副本之間通過傳遞彼此缺失的Op，并進行apply操作來達到最終一致性，

同樣的，即使是同步Op，我們也可以通過保證一個偏序關系來保證三律的實作，我們可以根據每個Op在副本上的執行順序來確定偏序關系，也就是說我們此時附加的元資訊是時間戳或者是邏輯時間戳，

• 如果一個OpA在副本上先于OpB執行，那么A < B，
• 如果既沒有A < B也沒有B < A，那么我們就稱A和B是并行的操作，

由此在Op-based CRDT的設計中，我們需要設計使得Op滿足交換律、結合律與冪等律，并且需要保證每個操作的前置條件都能通過按因果順序應用得到滿足，從而所有更新函式都會終止，從而得到滿足Op-based CRDT的資料結構，實際上，在形式上Op-based CRDT和State-based CRDT是可以互相轉換的，所以在Op-based CRDT這一節當中大部分需要了解的內容在State-based CRDT一節中都有體現，在State-based CRDT這一節的最后我們提到了在富文本中通過附加元資訊的方式來滿足CRDT的條件，同樣我們也可以將元資訊附加到Op上來滿足條件，簡單一點的話，我們如果為富文本的每一個字都賦予了唯一的id，再配合上邏輯時間戳，我們就能精確地知道該如何將Op應用到檔案的位置，從而就不需要進行操作變換轉換索引了，當然這個實作非常非常粗糙，如果想深入涉及一下的話，可以看看YATA演算法與Yjs，在Yjs中，大部分操作都是基于Op-based CRDT設計實作的，只有處理洗掉操作的時候是類似于State-based CRDT的實作，

資料結構

下面是一些典型的CRDT資料結構的例子，可以幫助我們理解CRDT的設計思想，要注意的是我們在此處的例子是沒有中央服務器調度以及資料存盤的的，資料都是在各個客戶端之間進行同步，

Op-based Counter

Op-based Counter表示了一個整數計數器，假設此時我們有A、B兩個客戶端共同維護一個計數器，也就是說我們兩個客戶端都存盤了一個整數，假設當前值為10，那么此時A進行了increment操作，B進行了decrement操作，那么我們就可以暫時地得到A的值為11，B的值為9，之后便要進行資料同步，以便使得A和B得到最終一致性的10這個值，那么我們就可以在網路中同步A的increment操作，B的decrement操作，這樣就能夠使得A和B的值都變為10，

看起來這個操作是很容易實作的，那便是因為加法天然滿足交換律和結合律，減法也同樣可以看作是加法，只不過是加一個負值，那么在這個例子中需要注意的點是加法不冪等，所以同步程序中需要保證不丟不重，

Grow-only Counter

State-based Counter在組織形式并非那么的顯而易見，在這一小節我們先從Grow-only Counter看起，也就是只增的計數器，首先明確的概念是我們此時是將資料全量同步的CRDT實作，由于同步的是全量，如果每個副本單獨進行累加，在進行合并的時候無法知道每個副本具體累加了多少，也不能簡單的取一個max作為最終結果，例如此時我們有A、B兩個客戶端共同維護一個計數器，初始時兩個客戶端資料都是0，此時A增加了1，B增加了2，那么全量同步資料時如果max(1, 2) = 2是不行的，因為我們實際上想得到的資料是3，以上，雖然我們通過max設計的資料結構是符合了交換律結合律和冪等律，但是這個設計與我們的目的是相悖的，我們想得到的是一個計數器，而不是獲得客戶端的最大值，

那么一種可行的方案是在每個副本上都使用一個陣列保留其它所有副本的值，本地更新時只操作當前副本在陣列中對應項，合并只能修改陣列中除了當前副本的其他專案，并且對陣列每一項求max進行合并，在查詢時將本地所有副本的值求和，即為我們想要的計數器Counter，此時我們有A、B兩個客戶端共同維護一個計數器，初始時兩個客戶端資料都是0，那么A維護的資料是[0, 0]，B維護的資料是[0, 0]，此時A增加了1，B增加了2，那么A就變成了[1, 0]，B變成了[0, 2]，當資料同步之后，A即為[1, 2]，B為[1, 2]，這樣兩個客戶端的資料就是一致的了，最終的計數為3，

在上述的方式中，對陣列每一項求max進行合并就是我們維持交換律結合律和冪等律的方式，由于網路的不可靠，我們不能保證資料包都能夠正常同步，假如歷史遺留了一個[1, 1]的包在網路中剛到達某一個客戶端，而此時客戶端的值已經達到了[6, 10]，那么這個包一定是要被舍棄的，否則就不能達到我們需要保證的三律，由此我們維護了一個偏序關系，當然了自然數實際上是全序關系，當然我們也可以為資料附帶一個時間戳，或者邏輯時間戳，這也是可實作的方式，因為同樣符合我們前邊論述的，通過附加元資訊的方式來達到三律，

Positive-Negative Counter

在上述的Grow-only Counter的最后，我們舉了個假如歷史遺留了一個[1, 1]的包在網路中剛到達某一個客戶端，而此時客戶端的值已經達到了[6, 10]，那么這個包一定是要被舍棄的，否則就不能達到我們需要保證的三律的例子，其實也能夠看出來，這個例子維護的是一個僅增的資料結構，如果加的是一個負數，或者直接叫做減法的話，那么上述的這個系統就是無效的，

由此帶有Decrement的State-based CRDT也并非像G-Counter那樣顯而易見，帶有減法之后，不能滿足更新時時單調的偏序關系，所以在這里一種可行的方式是構造兩個G-Counter，一個存放Increment的累加值，一個存放Decrement的累加值，通過兩組帶有偏序關系的CRDT來達到我們維持三律的目的，

Grow-only Set

Grow-only Set表示的是一個僅增的集合，Set的Add操作本質上是求并，天然滿足交換律、結合律和冪等律, 可以很簡單地使用Op-based CRDT，此時也不需要與上述的Op-based Counter一樣需要保證不丟不重，因為集合求并集是冪等的，當然也可以使用State-based CRDT進行全量的資料求并集，此時每個客戶端的副本也只需要保存一份集合即可，

Two-Phase Set

在Two-Phase Set中，我們考慮到了洗掉操作，實作思路上和PN-Counter一致，使用兩個G-Set，Set A只負責添加，對于從Set A中remove的元素不做實際洗掉，只是復制到Set R中，在查詢時如果元素在Set A且不在Set R中，則表示該元素存在，實際上2P-Set十分不實用，一方面已經被洗掉的元素不能再次被添加，因為集合必須保持只增的偏序關系，一方面洗掉的元素還會保留在原Set中，占用大量空間，

Last-Write-Wins-Element Set

在Last-Write-Wins-Element Set中為了解決洗掉元素不能再次添加的問題，可以考慮給2P-Set中A和R的每個元素加一個更新時間戳，其它操作保持不變，那么在查詢的時候就需要判斷該元素是否存在，即如果一個元素在添加集A中，并且不在洗掉集R中，或者在洗掉集R中但時間戳早于添加集A中的最新時間戳，那么就認為該元素存在，另一個更優化的實作是不要R集合，而A集合中每一個元素除了維護一個更新時間戳之外，還有一個洗掉標志位，這也可以看出實際上通過附加元資訊的方式可以有很多實作，只要能夠滿足交換律、結合律和冪等律即可，

Observed-Remove Set

Observed-Remove Set類似于LWW-Element-Set的實作，但使用唯一標簽tag/uuid而不是時間戳，我們同樣需要維護一個增加集Set A與洗掉集Set R，在添加元素時生成一個新的唯一標記tag/uuid，在洗掉的時候就將該元素與tag復制到洗掉集Set R中，查詢時如果元素在Set A中且不在Set R中，元素才存在于集合當中，因為我們生成了全域唯一的tag，所以并不需要比較時間戳，這樣就可以保證洗掉元素后可以再次添加，這可以看作是State-based CRDT的實作，

還有一種滿足Op-based CRDT的設計，核心思想是每次Add(e)的時候都為元素e加一個唯一的tag/uuid，Remove(e)將當前節點上的所有e和對應的tag/uuid都洗掉，這樣在Remove(e)同時其它節點又有并發Add(e)的情況下e是能夠最終保證添加成功，此種語意稱為Add wins，接下來我們可以看看這種方式是如何滿足交換律、結合律和冪等律的，在這里的敘述都是要滿足因果一致性來表述的，首先對于交換律而言，由于tag/uuid是全域唯一的，無論是Add還是Remove顯然都是可以交換的，當然前提是滿足因果一致性，不滿足需要阻塞等待；同樣還有結合律，在滿足因果一致性的情況下我們是可以隨意對于集合進行結合操作的，主要是tag/uuid是全域唯一的，并不會出現不一致的問題；最后是冪等律，我們需要保證因為網路不可靠重新發送的包的tag/uuid與重試前的資料相同，那么因為該元素已經實際存在，我們并不會重復添加，因而這個操作是冪等的，其實類似于我們最初寫到的Op-based Counter，Op是可交換的，并且保證了冪等性，所以這也是一種合理的CRDT設計，

最后

由于CRDT是處理分布式系統資料同步問題的通用解決方案，所以本文并沒有局限于在富文本資料結構的設計，而是從分布式資料同步的角度來理解CRDT，并且穿插著CRDT在富文本領域上的應用，從而讓我們能夠更好地理解這個資料模型，同樣，本文介紹的內容也只是冰山一角，分布式資料的同步一直以來都是個復雜的問題，回歸到富文本領域上，如何保證多人協同的編輯器性能、在CAP理論下如何做取舍策略、如何保證資料的穩定性可恢復可回溯、游標的同步處理、如何處理Undo/Redo等等，都是需要深入研究并且設計的，

在富文本領域中，當前在線檔案的主流方案依舊是OT，ShareDB作者在2020年9月的文章CRDTs are the future中，說明了CRDT和OT的取舍問題，OT最大的問題就是必須依賴中央服務器，那在所有設備之間無縫共享資料就必須依賴于服務器調度資料，而通過CRDT來實作就能夠做到無需中央服務器來實作資料同步，可能CRDT是未來解決一致性問題的一個有力手段，與OT一樣，在CRDT的領域也有很多開源的實作，通過應用CRDT基礎庫為應用帶來了奇妙的可能，只需要一個API與Backbone幾乎一樣簡單的資料Model層，應用就能自然地獲得對多人協作場景下并發更新的支持，在這里推薦兩個CRDT實作，automerge https://github.com/automerge/automerge/與yjs https://github.com/yjs/yjs，

每日一題

https://github.com/WindrunnerMax/EveryDay

參考

https://zhuanlan.zhihu.com/p/50990721
https://zhuanlan.zhihu.com/p/424467723
https://zhuanlan.zhihu.com/p/452980520
https://zhuanlan.zhihu.com/p/510797688
https://zhuanlan.zhihu.com/p/425265438
http://www.alloyteam.com/2020/01/14221/
https://www.jdon.com/artichect/crdt.html
https://www.zhihu.com/question/507425610
https://juejin.cn/post/6844903672032264199
https://juejin.cn/post/7049939780477386759
https://josephg.com/blog/crdts-are-the-future/
https://www.zxch3n.com/crdt-intro/design-crdt/
https://my.oschina.net/fileoptions/blog/1819610
https://hal.inria.fr/file/index/docid/555588/filename/techreport.pdf

標籤：其他

上一篇：初探富文本之CRDT協同演算法

下一篇：互動玩法任務平臺介紹