古风名字,我欲封天耳根小说零

多人協(xié)同編輯算法 —— CRDT 算法

當(dāng)前位置：點(diǎn)晴教程→知識管理交流 →『技術(shù)文檔交流』

freeflydom

2025年4月14日 9:58 本文熱度 1322

什么是 CRDT

無沖突復(fù)制數(shù)據(jù)類型（CRDT，Conflict-free Replicated Data Types）是一類在分布式系統(tǒng)中用于數(shù)據(jù)復(fù)制的數(shù)據(jù)結(jié)構(gòu)，旨在解決多副本并發(fā)更新時(shí)的數(shù)據(jù)一致性問題。CRDT 允許各個(gè)副本獨(dú)立且并發(fā)地進(jìn)行更新，而無需協(xié)調(diào)，且能夠在最終自動解決可能出現(xiàn)的不一致性。

CRDT 的關(guān)鍵特性主要有以下三個(gè)方面：

獨(dú)立更新：每個(gè)副本可以獨(dú)立地進(jìn)行更新，無需與其他副本進(jìn)行通信。
自動合并：當(dāng)副本之間交換數(shù)據(jù)時(shí)，CRDT 會自動合并更新，確保所有副本最終達(dá)到一致狀態(tài)。
最終一致性：盡管副本可能在某些時(shí)刻處于不同狀態(tài)，但通過合并操作，所有副本最終會收斂到相同的狀態(tài)。

CRDT 的種類

CRDT 有兩種方法，都可以提供強(qiáng)最終一致性：基于操作的 CRDT 和基于狀態(tài)的 CRDT。

基于操作的 CRDT（CmRDT）

基于操作的 CRDT（也稱為交換性復(fù)制數(shù)據(jù)類型，CmRDT）是一類通過傳輸更新操作來同步副本的 CRDT。在 CmRDT 中，每個(gè)副本只發(fā)送更新操作，而不是完整的狀態(tài)。例如，操作可以是"+10"或"-20"，它們表示對某個(gè)值的增減。副本接收到這些操作后，會在本地應(yīng)用這些更新。

操作是可交換的，這意味著操作的順序不影響最終結(jié)果。也就是說，即使操作以不同的順序應(yīng)用，最終的結(jié)果也會是一樣的。然而，這些操作不一定是冪等的，即重復(fù)應(yīng)用相同操作可能會產(chǎn)生不同的結(jié)果。

由于操作是以獨(dú)立的方式廣播的，通信基礎(chǔ)設(shè)施必須保證所有操作都被傳輸?shù)剿懈北?，而且操作不會丟失或重復(fù)。在此過程中，操作的順序是靈活的，可以按照任何順序傳輸。

純基于操作的 CRDT（Pure CmRDT）是基于操作的 CRDT 的一個(gè)變種，它通過減少所需的元數(shù)據(jù)大小來優(yōu)化性能。

G-Counter

G-Counter 用于實(shí)現(xiàn)分布式環(huán)境中的計(jì)數(shù)器功能，由多個(gè)計(jì)數(shù)器組成的數(shù)據(jù)結(jié)構(gòu)，每個(gè)副本都維護(hù)自己的計(jì)數(shù)器。每當(dāng)副本需要增加計(jì)數(shù)時(shí)，它只會在自己的計(jì)數(shù)器上增加，而不會減少或修改其他副本的計(jì)數(shù)器。當(dāng)需要獲取計(jì)數(shù)時(shí)，副本會將所有計(jì)數(shù)器的值累加起來，以獲得全局的計(jì)數(shù)結(jié)果。G-Counter 是一個(gè)只增長的計(jì)數(shù)器，它滿足如下的性質(zhì)：

每個(gè)副本的計(jì)數(shù)器值只增加，不會減少。
副本之間的計(jì)數(shù)器值可以獨(dú)立增長，不會發(fā)生沖突或合并操作。

PN-Counter

PN-Counter 是一種基于 CRDT 的數(shù)據(jù)類型，用于實(shí)現(xiàn)分布式環(huán)境中的計(jì)數(shù)器功能。由兩個(gè) G-Counter 組成的數(shù)據(jù)結(jié)構(gòu)，分別用于記錄正數(shù)和負(fù)數(shù)的計(jì)數(shù)。每個(gè)副本都維護(hù)自己的兩個(gè)計(jì)數(shù)器，分別用于增加正數(shù)計(jì)數(shù)和增加負(fù)數(shù)計(jì)數(shù)。當(dāng)需要獲取計(jì)數(shù)時(shí)，副本會將正數(shù)計(jì)數(shù)器的值減去負(fù)數(shù)計(jì)數(shù)器的值，以獲得全局的計(jì)數(shù)結(jié)果。PN-Counter 具有以下性質(zhì)：

每個(gè)副本的正數(shù)計(jì)數(shù)器和負(fù)數(shù)計(jì)數(shù)器值只增加，不會減少。
副本之間的計(jì)數(shù)器值可以獨(dú)立增長，不會發(fā)生沖突或合并操作。
全局計(jì)數(shù)結(jié)果是正數(shù)計(jì)數(shù)減去負(fù)數(shù)計(jì)數(shù)的差值。

Sequence CRDT

Sequence CRDT 用于實(shí)現(xiàn)分布式環(huán)境中的有序序列功能，旨在解決在并發(fā)環(huán)境中對有序序列進(jìn)行并發(fā)操作時(shí)可能出現(xiàn)的沖突問題。它允許并發(fā)操作在不同副本之間交換和合并，以達(dá)到最終一致性的狀態(tài)。Sequence CRDT 的實(shí)現(xiàn)方式有多種，其中一種常見的實(shí)現(xiàn)是基于標(biāo)識符（Identifier）的方式。每個(gè)操作都被賦予唯一的標(biāo)識符，用于標(biāo)識操作的順序。常見的操作包括插入元素、刪除元素和移動元素。通過使用標(biāo)識符和一致的合并策略，Sequence CRDT 可以實(shí)現(xiàn)在分布式環(huán)境中對有序序列進(jìn)行并發(fā)操作的正確合并。具體的合并策略可以根據(jù)應(yīng)用需求和具體實(shí)現(xiàn)進(jìn)行定制。Sequence CRDT 具有以下特性：

并發(fā)操作可以獨(dú)立地在不同副本上執(zhí)行，不會發(fā)生沖突。
合并操作時(shí)，可以根據(jù)標(biāo)識符和合并策略將并發(fā)操作正確地合并到最終結(jié)果中。

Sequence CRDT 可以應(yīng)用于許多場景，如協(xié)同編輯、版本控制系統(tǒng)、聊天應(yīng)用等，其中有序的操作是必要的。它提供了在分布式環(huán)境中實(shí)現(xiàn)有序序列的能力，并保持最終一致性。

基于狀態(tài)的 CRDT（CvRDT）

與基于操作的 CRDT（CmRDT）不同，基于狀態(tài)的 CRDT（也稱為收斂復(fù)制數(shù)據(jù)類型，CvRDT）通過將完整的本地狀態(tài)發(fā)送到其他副本來進(jìn)行狀態(tài)傳播。在 CvRDT 中，副本接收到完整的狀態(tài)并將其與自身的狀態(tài)合并。合并函數(shù)必須滿足可交換性、結(jié)合性和冪等性，確保副本之間的合并結(jié)果是相同的。

這意味著合并操作的順序不影響最終結(jié)果，并且即使多次合并相同的狀態(tài)，結(jié)果也不會發(fā)生變化。所有副本的狀態(tài)都可以通過合并來收斂到同一個(gè)最終狀態(tài)。為了確保一致性，更新函數(shù)必須遵循一個(gè)偏序規(guī)則，使得每次合并都能夠單調(diào)地增加內(nèi)部狀態(tài)。

Delta 狀態(tài) CRDT 是基于狀態(tài)的 CRDT 的一種優(yōu)化版本。在 Delta CRDT 中，僅傳播最近對狀態(tài)進(jìn)行的更改（即"delta"），而不是將整個(gè)狀態(tài)傳輸?shù)狡渌北?。這減少了每次更新的網(wǎng)絡(luò)開銷，并提高了效率。只有當(dāng)某個(gè)副本的狀態(tài)發(fā)生變化時(shí)，才會將該變化廣播給其他副本，從而避免了大量不必要的數(shù)據(jù)傳輸。

G-Set

G-Set 是一種基于 CRDT 的數(shù)據(jù)類型，用于實(shí)現(xiàn)分布式環(huán)境中的集合功能，G-Set 是一個(gè)只增長的集合，每個(gè)副本都維護(hù)自己的本地集合。當(dāng)需要添加元素時(shí)，副本只會在自己的集合中添加元素，而不會刪除或修改其他副本的集合。G-Set 的特性包括：

每個(gè)副本維護(hù)自己的本地集合，可以獨(dú)立地增加元素。
全局集合是所有副本的集合的并集，即包含所有副本中添加的元素。

由于 G-Set 是只增長的集合，它滿足最終一致性和合并性質(zhì)。每個(gè)副本的本地集合可以獨(dú)立地增長，不會發(fā)生沖突或合并操作。當(dāng)需要獲取全局集合時(shí)，可以簡單地將所有副本的集合合并。G-Set 適用于需要在分布式環(huán)境中維護(hù)集合，并且可以實(shí)現(xiàn)高可用性和最終一致性的場景。它常用于記錄一組唯一的元素，而不需要刪除或修改元素

2P-Set

2P-Set 用于實(shí)現(xiàn)分布式環(huán)境中的集合功能，維護(hù)兩個(gè)集合：一個(gè)"添加集合"和一個(gè)"移除集合"。每個(gè)元素在添加集合中只能添加一次，在移除集合中只能移除一次。這樣，2P-Set 可以實(shí)現(xiàn)添加和移除元素的操作，并且確保元素不會重復(fù)添加或移除。2P-Set 的操作包括：

添加元素：將元素添加到添加集合中。
移除元素：將元素從添加集合中移除，并將其添加到移除集合中。

2P-Set 的特性包括：

每個(gè)副本維護(hù)自己的本地添加集合和移除集合，可以獨(dú)立地進(jìn)行添加和移除操作。
全局集合是添加集合減去移除集合的結(jié)果。

當(dāng)需要獲取全局集合時(shí)，副本將所有副本的添加集合和移除集合合并，并計(jì)算添加集合減去移除集合的結(jié)果，得到最終的全局集合。2P-Set 可以實(shí)現(xiàn)在分布式環(huán)境中維護(hù)集合，并且具有最終一致性。它適用于需要記錄添加和移除操作，并且不希望元素重復(fù)添加或移除的場景。

LWW-Element-Set

LWW-Element-Set 用于實(shí)現(xiàn)分布式環(huán)境中的集合功能，維護(hù)一個(gè)集合，其中每個(gè)元素都與一個(gè)時(shí)間戳相關(guān)聯(lián)。時(shí)間戳可以是遞增的整數(shù)，邏輯時(shí)鐘，或其他可比較的時(shí)間表示。每當(dāng)需要添加或移除元素時(shí)，副本會將元素與當(dāng)前時(shí)間戳關(guān)聯(lián)，并將操作應(yīng)用到本地集合。LWW-Element-Set 的特性包括：

每個(gè)副本維護(hù)自己的本地集合，可以獨(dú)立地添加或移除元素。
全局集合是根據(jù)時(shí)間戳確定的最新操作的結(jié)果，即最后的寫操作勝出。

當(dāng)需要獲取全局集合時(shí)，副本將所有副本的集合合并，并根據(jù)時(shí)間戳選擇最新的操作。如果存在多個(gè)副本對同一個(gè)元素進(jìn)行了不同的操作，那么具有較新時(shí)間戳的操作將覆蓋較舊時(shí)間戳的操作。LWW-Element-Set 可以實(shí)現(xiàn)在分布式環(huán)境中維護(hù)集合，并且具有最終一致性。它適用于需要記錄元素的添加和移除，并以最后寫操作為準(zhǔn)的場景。然而，由于最后寫操作勝出的特性，可能會導(dǎo)致某些操作的沖突或覆蓋

OR-Set

OR-Set 用于實(shí)現(xiàn)分布式環(huán)境中的集合功能，維護(hù)一個(gè)集合，其中每個(gè)元素都與一個(gè)標(biāo)識符相關(guān)聯(lián)。當(dāng)需要添加元素時(shí)，副本會為元素生成一個(gè)唯一的標(biāo)識符，并將其添加到本地集合中。當(dāng)需要移除元素時(shí)，副本會為要移除的元素生成一個(gè)移除標(biāo)記，并將其關(guān)聯(lián)到原始元素的標(biāo)識符上。OR-Set 的特性包括：

每個(gè)副本維護(hù)自己的本地集合，可以獨(dú)立地添加和移除元素。
全局集合是所有副本的集合的并集，其中移除標(biāo)記會覆蓋對應(yīng)的元素。

當(dāng)需要獲取全局集合時(shí)，副本將所有副本的集合合并，并根據(jù)標(biāo)識符和移除標(biāo)記進(jìn)行操作。如果一個(gè)元素的標(biāo)識符存在于集合中，但它的移除標(biāo)記也存在，則該元素被視為已移除。這樣，移除操作具有優(yōu)先級高于添加操作的效果。OR-Set 可以實(shí)現(xiàn)在分布式環(huán)境中維護(hù)集合，并且具有最終一致性。它適用于需要記錄元素的添加和移除，并且允許移除操作覆蓋添加操作的場景。

CmRDTs 和 CvRDTs

相比于 CvRDTs，CmRDTs 在副本之間傳輸操作的協(xié)議上有更多要求，但當(dāng)事務(wù)數(shù)量相對于內(nèi)部狀態(tài)的大小較小時(shí)，它們使用的帶寬較少。然而，由于 CvRDT 的合并函數(shù)是可結(jié)合的，與某個(gè)副本的狀態(tài)進(jìn)行合并會包含該副本的所有先前更新。在減少網(wǎng)絡(luò)使用和處理拓?fù)渥兓矫?，使?Gossip 協(xié)議可以很好地傳播 CvRDT 狀態(tài)到其他副本。

CRDT 的數(shù)學(xué)基礎(chǔ)

CRDT 的核心在于其合并操作必須滿足一組特定的數(shù)學(xué)性質(zhì)，這些性質(zhì)保證了在分布式系統(tǒng)中數(shù)據(jù)最終能夠達(dá)到一致。合并操作（通常表示為 ∨）必須滿足以下三個(gè)關(guān)鍵性質(zhì)：

1. 交換律（Commutativity）

合并操作的順序不影響最終結(jié)果：

[ A \vee B = B \vee A ]

這意味著無論是節(jié)點(diǎn) A 先將數(shù)據(jù)同步給節(jié)點(diǎn) B，還是節(jié)點(diǎn) B 先將數(shù)據(jù)同步給節(jié)點(diǎn) A，最終的結(jié)果都是一樣的。這個(gè)性質(zhì)對于分布式系統(tǒng)特別重要，因?yàn)樵趯?shí)際環(huán)境中，我們無法保證數(shù)據(jù)同步的順序。

示例：

節(jié)點(diǎn)1的狀態(tài): {a, b}
節(jié)點(diǎn)2的狀態(tài): {b, c}
合并結(jié)果: {a, b, c}  // 無論是1→2還是2→1的同步順序，結(jié)果都相同

2. 結(jié)合律（Associativity）

多個(gè)合并操作的順序不影響最終結(jié)果：

[ (A \vee B) \vee C = A \vee (B \vee C) ]

這個(gè)性質(zhì)確保了在有多個(gè)節(jié)點(diǎn)時(shí)，無論按什么順序進(jìn)行合并，最終結(jié)果都是一致的。這對于大規(guī)模分布式系統(tǒng)尤為重要，因?yàn)閿?shù)據(jù)同步可能涉及多個(gè)節(jié)點(diǎn)的鏈?zhǔn)絺鬟f。

示例：

節(jié)點(diǎn)1的狀態(tài): {a, b}
節(jié)點(diǎn)2的狀態(tài): {b, c}
節(jié)點(diǎn)3的狀態(tài): {c, d}
(節(jié)點(diǎn)1 ∨ 節(jié)點(diǎn)2) ∨ 節(jié)點(diǎn)3 = {a, b, c} ∨ {c, d} = {a, b, c, d}
節(jié)點(diǎn)1 ∨ (節(jié)點(diǎn)2 ∨ 節(jié)點(diǎn)3) = {a, b} ∨ {b, c, d} = {a, b, c, d}

3. 冪等律（Idempotency）

重復(fù)合并不會改變結(jié)果：

[ A \vee A = A ]

這個(gè)性質(zhì)保證了即使同一個(gè)更新被應(yīng)用多次（例如由于網(wǎng)絡(luò)問題導(dǎo)致的重復(fù)傳輸），也不會影響最終狀態(tài)。這對于構(gòu)建容錯的分布式系統(tǒng)至關(guān)重要。

示例：

狀態(tài)A: {a, b, c}
A ∨ A = {a, b, c}  // 重復(fù)合并不會產(chǎn)生新的結(jié)果

實(shí)際意義

這些數(shù)學(xué)性質(zhì)的重要性體現(xiàn)在：

網(wǎng)絡(luò)分區(qū)容忍：由于交換律和結(jié)合律的存在，系統(tǒng)可以在網(wǎng)絡(luò)分區(qū)的情況下繼續(xù)工作，當(dāng)連接恢復(fù)后可以正確合并數(shù)據(jù)。
最終一致性保證：這些性質(zhì)確保了無論數(shù)據(jù)同步的順序如何，所有副本最終都會收斂到相同的狀態(tài)。
去中心化：不需要中央?yún)f(xié)調(diào)器來處理并發(fā)更新，每個(gè)節(jié)點(diǎn)都可以獨(dú)立處理更新并最終達(dá)到一致。
容錯性：冪等性確保了系統(tǒng)能夠優(yōu)雅地處理重復(fù)的消息，這在不可靠的網(wǎng)絡(luò)環(huán)境中特別重要。

在實(shí)際應(yīng)用中，這些性質(zhì)使得 CRDT 特別適合構(gòu)建：

協(xié)同編輯系統(tǒng)
分布式數(shù)據(jù)庫
多設(shè)備數(shù)據(jù)同步
離線優(yōu)先的應(yīng)用

通過確保這些數(shù)學(xué)性質(zhì)，CRDT 能夠在不需要復(fù)雜的協(xié)調(diào)機(jī)制的情況下，保證分布式系統(tǒng)中數(shù)據(jù)的最終一致性。

CRDT 是如何處理沖突的

下圖描述了 Yjs 中處理沖突的算法模型，它是一個(gè)支持點(diǎn)對點(diǎn)傳輸?shù)臎_突處理模型。

首先我們先來解釋一下圖中的元素：

E(1,0)：表示用戶 1 在節(jié)點(diǎn) A 和 B 之間插入了數(shù)據(jù)項(xiàng)。
D(0,1)：表示用戶 0 在節(jié)點(diǎn) B 和 C 之間插入了數(shù)據(jù)項(xiàng)。
C(0,0)：表示用戶 0 在節(jié)點(diǎn) A 和 B 之間插入了數(shù)據(jù)項(xiàng)。

圖示的操作順序：

用戶 0 插入了 C(0,0) 在節(jié)點(diǎn) A 和 B 之間。
用戶 0 在節(jié)點(diǎn) B 和 C 之間插入了 D(0,1)。
用戶 1 插入了 E(1,0) 在節(jié)點(diǎn) A 和 B 之間。

當(dāng)兩個(gè)操作發(fā)生并發(fā)沖突（例如 C(0,0) 和 E(1,0) 都涉及節(jié)點(diǎn) A 和 B 之間的插入），Yjs 會基于操作的用戶標(biāo)識符來決定哪一個(gè)操作先應(yīng)用。

在這個(gè)例子中，用戶 1 的標(biāo)識符（1）大于用戶 0 的標(biāo)識符（0），因此生成的最終文檔順序是 A C D E B。

CRDT 機(jī)制能夠避免傳統(tǒng)操作轉(zhuǎn)發(fā)（OT）所面臨的沖突問題，同時(shí)保證最終一致性，原因在于其設(shè)計(jì)采用了沖突自由的合并規(guī)則，而不依賴于復(fù)雜的操作變換和中央?yún)f(xié)調(diào)。

在 OT 中，當(dāng)多個(gè)用戶并發(fā)地對同一數(shù)據(jù)進(jìn)行操作時(shí)，系統(tǒng)需要通過操作轉(zhuǎn)發(fā)和變換來確保操作順序的一致性。這通常涉及復(fù)雜的變換邏輯，例如在兩個(gè)用戶同時(shí)修改相同數(shù)據(jù)位置時(shí)，OT 會通過變換算法調(diào)整其中一個(gè)操作的位置或內(nèi)容，以確保最終結(jié)果一致。盡管 OT 可以解決許多并發(fā)沖突，但這種變換機(jī)制本身具有高復(fù)雜性，特別是在多個(gè)用戶同時(shí)進(jìn)行操作時(shí)，操作的變換和沖突解決可能導(dǎo)致性能瓶頸、維護(hù)困難，以及在極端情況下可能產(chǎn)生不一致的結(jié)果。

與此不同，CRDT 通過設(shè)計(jì)內(nèi)建的合并規(guī)則來避免這些問題。每個(gè) CRDT 數(shù)據(jù)結(jié)構(gòu)都確保其操作是冪等、交換性強(qiáng)且結(jié)合性好的，這意味著無論操作順序如何或是否發(fā)生并發(fā)操作，所有副本都能夠自動且無沖突地合并，最終收斂到一致的狀態(tài)。CRDT 不依賴于操作的順序或中央?yún)f(xié)調(diào)，而是依靠每個(gè)操作的唯一標(biāo)識符和局部合并規(guī)則來直接解決并發(fā)沖突，從而顯著減少了在處理沖突時(shí)的計(jì)算復(fù)雜度。

此外，CRDT 的這一機(jī)制使得它天然適合高可用性和容錯性要求較高的分布式系統(tǒng)，在面對網(wǎng)絡(luò)分區(qū)、節(jié)點(diǎn)故障等場景時(shí)，系統(tǒng)依然能夠繼續(xù)操作并保證數(shù)據(jù)一致性。因此，CRDT 更加簡潔、易于擴(kuò)展，并能夠在沒有顯式操作轉(zhuǎn)發(fā)和變換的情況下，確保最終一致性，從根本上避免了 OT 中因操作順序和變換導(dǎo)致的復(fù)雜性和潛在沖突。

CRDT 如何解決臟路徑問題

在分布式系統(tǒng)中，臟路徑（Dirty Path）問題通常出現(xiàn)在多個(gè)副本之間進(jìn)行并發(fā)操作時(shí)，導(dǎo)致副本之間的數(shù)據(jù)狀態(tài)不一致。由于不同副本的操作可能由于網(wǎng)絡(luò)延遲、分區(qū)或同步問題而不同步，這使得系統(tǒng)中可能出現(xiàn)不一致的數(shù)據(jù)狀態(tài)。傳統(tǒng)的分布式系統(tǒng)通常依賴中心化的協(xié)調(diào)機(jī)制來同步數(shù)據(jù)，但這也容易引發(fā)性能瓶頸和復(fù)雜的沖突解決問題。CRDT（沖突自由復(fù)制數(shù)據(jù)類型）通過去中心化和無沖突的操作設(shè)計(jì)，避免了臟路徑問題，確保多個(gè)副本能夠在并發(fā)操作后最終收斂到一致的狀態(tài)。

以下是 CRDT 如何通過一系列設(shè)計(jì)原則來解決臟路徑問題的詳細(xì)過程：

1. 唯一標(biāo)識符與操作標(biāo)記

CRDT 使用唯一標(biāo)識符來區(qū)分每個(gè)操作，每個(gè)操作的標(biāo)識符通常由用戶標(biāo)識符（例如用戶 ID）和操作序列號（通常是時(shí)間戳或遞增的操作編號）組成。唯一標(biāo)識符保證了操作的順序，即使這些操作在不同副本上并發(fā)發(fā)生。

操作標(biāo)識符的作用：

用戶標(biāo)識符（例如 A、B）：確保每個(gè)用戶的操作是唯一的，防止不同用戶的操作發(fā)生混淆。
操作序列號（例如 0、1）：確保同一用戶的操作能夠按序列號區(qū)分，確定操作的順序。

這種設(shè)計(jì)避免了因操作沒有明確順序而產(chǎn)生的不一致或沖突，從而有效地避免了臟路徑問題。

示例：

假設(shè)用戶 A 在副本 1 上插入了一個(gè)字符 X，操作標(biāo)識符為 A,0。與此同時(shí)，用戶 B 在副本 2 上插入了字符 Y，操作標(biāo)識符為 B,0。每個(gè)操作都帶有唯一標(biāo)識符，確保它們在后續(xù)合并時(shí)能夠正確排序。

2. 并發(fā)操作的解決

在 CRDT 中，每個(gè)副本都能夠獨(dú)立進(jìn)行操作，當(dāng)多個(gè)副本發(fā)生并發(fā)操作時(shí)，CRDT 使用設(shè)計(jì)的合并規(guī)則來自動解決沖突，確保所有副本最終達(dá)到一致狀態(tài)。

如何處理并發(fā)操作？

當(dāng)用戶 A 在副本 1 上插入字符 X，并且用戶 B 在副本 2 上插入字符 Y 時(shí)，兩個(gè)操作會先在本地副本上執(zhí)行，然后通過網(wǎng)絡(luò)傳播到其他副本。
CRDT 會通過操作標(biāo)識符比較來確定哪個(gè)操作先執(zhí)行。比如，比較 A,0 和 B,0，標(biāo)識符較小的操作會先應(yīng)用。

例如，假設(shè) A,0 小于 B,0，那么操作會按順序執(zhí)行，首先在副本 1 上插入 X，然后在副本 2 上插入 Y。

3. 合并規(guī)則與最終一致性

CRDT 的設(shè)計(jì)關(guān)鍵在于合并規(guī)則，即如何將并發(fā)操作合并為一致的狀態(tài)。這些合并規(guī)則確保了即使副本之間的操作順序不同，最終副本的數(shù)據(jù)會收斂到相同的狀態(tài)。

合并規(guī)則保證一致性：

冪等性（Idempotence）：一個(gè)操作可以多次應(yīng)用，結(jié)果不會改變。如果某個(gè)操作被傳送到一個(gè)副本多次，只會影響一次，避免重復(fù)操作帶來的問題。
交換性（Commutativity）：操作的順序不影響最終結(jié)果。不同副本的操作可能發(fā)生順序不同，但最終合并時(shí)，所有副本的數(shù)據(jù)狀態(tài)將是一致的。
結(jié)合性（Associativity）：多個(gè)操作的合并順序不影響結(jié)果。即使合并操作的順序不同，最終的合并結(jié)果相同。

這些規(guī)則使得 CRDT 在面對并發(fā)更新時(shí)，能夠自動解決沖突并收斂到一致的狀態(tài)。

舉例說明：

假設(shè)兩個(gè)用戶并發(fā)進(jìn)行插入操作，用戶 A 在副本 1 中插入 X，而用戶 B 在副本 2 中插入 Y。無論這兩個(gè)操作的順序如何，CRDT 會根據(jù)合并規(guī)則確定最終的順序，并保證合并后的狀態(tài)一致。即使兩個(gè)副本的操作順序不同，最終的結(jié)果將是文本 "XY" 或 "YX"（具體順序依賴于標(biāo)識符的比較）。

4. 雙向鏈表在 CRDT 中的應(yīng)用

在一些 CRDT 應(yīng)用（例如文本編輯器）中，雙向鏈表被用來存儲數(shù)據(jù)。雙向鏈表的結(jié)構(gòu)非常適合表示具有順序關(guān)系的數(shù)據(jù)，并且支持高效的插入、刪除和更新操作。

雙向鏈表如何解決臟路徑問題：

插入和刪除操作：當(dāng)用戶在文本中插入或刪除字符時(shí)，CRDT 會將這些操作表示為雙向鏈表的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)都包含指向前一個(gè)和后一個(gè)節(jié)點(diǎn)的指針，使得操作能夠在鏈表的任意位置進(jìn)行。
并發(fā)操作：當(dāng)多個(gè)用戶在不同副本上同時(shí)修改文本時(shí)，CRDT 會根據(jù)操作的唯一標(biāo)識符（例如標(biāo)識符的大小）來決定操作的順序。例如，用戶 A 在某位置插入字符，用戶 B 在另一個(gè)位置插入字符，CRDT 會通過合并規(guī)則確保這兩個(gè)操作按正確順序合并，并更新鏈表。

通過這種方式，CRDT 可以處理并發(fā)插入、刪除操作，避免因操作順序不同而引發(fā)臟路徑問題。

5. 最終一致性

CRDT 通過合并規(guī)則確保所有副本最終一致。即使操作在不同副本之間發(fā)生延遲或順序不同，最終的合并結(jié)果會保證一致性。

如何確保最終一致性？

去中心化：CRDT 不依賴中心化的協(xié)調(diào)，所有副本都能獨(dú)立執(zhí)行操作并進(jìn)行合并。每個(gè)副本都維護(hù)自己的操作歷史，并通過合并規(guī)則來自動解決沖突。
同步與傳播：每個(gè)副本定期與其他副本同步，傳播其操作。即使某些副本的更新稍有延遲，最終每個(gè)副本的狀態(tài)都會通過合并收斂到一致。

通過最終一致性，CRDT 確保即使在網(wǎng)絡(luò)分區(qū)或節(jié)點(diǎn)故障的情況下，系統(tǒng)中的所有副本最終都會收斂到相同的數(shù)據(jù)狀態(tài)，避免了臟路徑問題。

6. 避免臟路徑：總結(jié)

CRDT 解決臟路徑問題的關(guān)鍵在于：

唯一標(biāo)識符：每個(gè)操作都有唯一標(biāo)識符，確保并發(fā)操作能夠按照正確順序合并。
去中心化合并：CRDT 不依賴中心節(jié)點(diǎn)，而是通過去中心化的方式進(jìn)行合并，每個(gè)副本根據(jù)合并規(guī)則獨(dú)立解決沖突。
合并規(guī)則的設(shè)計(jì)：CRDT 使用冪等性、交換性和結(jié)合性保證操作的合并無沖突，確保最終一致性。
雙向鏈表：在存儲數(shù)據(jù)時(shí)，雙向鏈表能夠高效支持插入和刪除操作，并保證操作的順序正確，同時(shí)避免復(fù)雜的全局排序。
最終一致性：CRDT 確保每個(gè)副本最終一致，不論操作順序如何，最終所有副本都會達(dá)成一致，避免了因不同步或操作沖突帶來的臟路徑問題。

通過這些機(jī)制，CRDT 確保了分布式系統(tǒng)中的高可用性、容錯性和一致性，避免了臟路徑問題的出現(xiàn)，并且簡化了分布式系統(tǒng)中并發(fā)操作的管理。

CRDT 如何解決 UNDO/REDO 問題

在分布式系統(tǒng)中，UNDO 和 REDO 是常見的操作需求，尤其是在分布式應(yīng)用（如分布式文本編輯器、協(xié)作平臺等）中，這些操作通常需要確保數(shù)據(jù)的一致性和正確的操作回溯。然而，傳統(tǒng)的事務(wù)日志和操作轉(zhuǎn)發(fā)（OT）機(jī)制在處理這些操作時(shí)可能會遇到同步、順序和沖突等問題。而 CRDT（沖突自由復(fù)制數(shù)據(jù)類型）通過其特有的設(shè)計(jì)原則，能夠優(yōu)雅地解決 UNDO 和 REDO 問題，保證分布式系統(tǒng)中操作的回滾與重做能夠在多個(gè)副本間一致地執(zhí)行。

什么是 UNDO 和 REDO？

UNDO：是撤銷上一步操作的功能，即恢復(fù)到操作前的狀態(tài)。在分布式系統(tǒng)中，UNDO 通常需要回滾到某個(gè)特定的歷史狀態(tài)。
REDO：是重新執(zhí)行撤銷操作后的功能，將上一步撤銷的操作重新應(yīng)用于數(shù)據(jù)中。

在分布式系統(tǒng)中，UNDO 和 REDO 需要跨多個(gè)副本同步，以保證每個(gè)副本中的歷史操作可以一致地回滾或重做。此過程可能會受到以下問題的影響：

并發(fā)沖突：不同副本上的操作順序不同，可能會導(dǎo)致狀態(tài)不一致，尤其是在操作順序發(fā)生變化時(shí)。
操作歷史的同步：在沒有中心化控制的情況下，操作歷史的同步可能會變得非常復(fù)雜。
最終一致性：確保在分布式環(huán)境中，UNDO 和 REDO 不會導(dǎo)致不同副本的數(shù)據(jù)不一致。

CRDT 如何解決 UNDO 和 REDO 問題

CRDT 提供了一些特性，使其特別適合解決 UNDO 和 REDO 問題，尤其是在分布式環(huán)境下。這些特性包括沖突自由的操作合并、冪等性、交換性、結(jié)合性、以及最終一致性。通過這些特性，CRDT 可以處理操作回滾和重做時(shí)遇到的挑戰(zhàn)。

1. 操作歷史與逆向操作（Undo/Redo）

CRDT 中的每個(gè)操作（如插入、刪除等）都有一個(gè)唯一標(biāo)識符。通過設(shè)計(jì)合適的操作歷史結(jié)構(gòu)，CRDT 可以存儲每個(gè)操作，并支持操作的回溯和重做。這對于分布式系統(tǒng)中的 UNDO 和 REDO 操作至關(guān)重要。

操作的存儲和標(biāo)識：

每個(gè)操作都有唯一標(biāo)識符，通常由操作的用戶 ID 和時(shí)間戳（或操作序列號）組成。
CRDT 通常維護(hù)一個(gè)操作的日志或歷史記錄，其中記錄了所有歷史操作以及它們的操作標(biāo)識符。由于 CRDT 的操作是冪等的（即重復(fù)執(zhí)行不改變結(jié)果），因此可以安全地記錄和回滾這些操作。

操作回滾（UNDO）：

UNDO 操作需要逆向地應(yīng)用上一個(gè)操作。例如，如果用戶插入了一個(gè)字符，UNDO 就需要撤銷該插入操作。
在 CRDT 中，通過逆向操作來回滾數(shù)據(jù)。例如，如果插入操作是通過一個(gè) 增量計(jì)數(shù)器（例如 PN-Counter）進(jìn)行的，UNDO 操作會通過逆向操作遞減計(jì)數(shù)器的值，從而撤銷上一步的插入。

操作重做（REDO）：

REDO 操作需要將之前撤銷的操作重新應(yīng)用。例如，如果用戶撤銷了插入字符 X，則 REDO 會重新執(zhí)行插入字符 X 的操作。
在 CRDT 中，REDO 操作是重新應(yīng)用已撤銷的操作。這些操作會根據(jù)其標(biāo)識符再次插入或刪除數(shù)據(jù)，并通過合并規(guī)則確保最終一致性。

2. 如何支持并發(fā)和沖突解決

在分布式系統(tǒng)中，UNDO 和 REDO 操作通常是在多個(gè)副本之間執(zhí)行的，可能會遇到并發(fā)沖突的問題。CRDT 的核心特性能夠有效地解決并發(fā)沖突問題，從而確保 UNDO 和 REDO 操作的一致性。

冪等性、交換性和結(jié)合性：

冪等性：確保同一個(gè)操作多次應(yīng)用不會改變最終的結(jié)果。例如，當(dāng)執(zhí)行 UNDO 時(shí)，即使該操作多次傳遞給不同副本，它的效果仍然是相同的。
交換性：多個(gè)操作的順序不會影響最終結(jié)果。即使在不同副本上執(zhí)行 UNDO 和 REDO 操作，操作的順序不會影響最終的數(shù)據(jù)一致性。
結(jié)合性：多個(gè) UNDO 或 REDO 操作的順序不影響結(jié)果。無論如何組合多個(gè)操作，系統(tǒng)最終會達(dá)到一致狀態(tài)。

這些特性使得 CRDT 在多個(gè)副本上執(zhí)行 UNDO 和 REDO 操作時(shí)，可以自動解決并發(fā)沖突，確保不同副本的數(shù)據(jù)始終一致。

解決并發(fā)沖突的方式：

當(dāng)多個(gè)用戶在不同副本上進(jìn)行并發(fā)操作（如同時(shí)執(zhí)行插入、刪除或撤銷操作）時(shí)，CRDT 會根據(jù)每個(gè)操作的標(biāo)識符（例如時(shí)間戳、序列號等）來確定它們的順序。
即使副本之間的操作順序不同，CRDT 通過標(biāo)識符確保每個(gè)操作按正確的順序合并，從而保證 UNDO 和 REDO 操作能夠正確地同步到所有副本。

示例：

假設(shè)兩個(gè)用戶 A 和 B 同時(shí)進(jìn)行文本插入操作，在某個(gè)時(shí)刻用戶 A 撤銷了插入操作，而用戶 B 在該位置再次插入了文本。CRDT 會根據(jù)操作的標(biāo)識符來判斷用戶 A 的撤銷操作和用戶 B 的插入操作的執(zhí)行順序，保證最終文本的一致性。

3. 最終一致性與操作回溯

CRDT 的設(shè)計(jì)目標(biāo)之一是最終一致性。即使操作的執(zhí)行順序不同，所有副本最終都會達(dá)到一致的狀態(tài)。對于 UNDO 和 REDO 操作，CRDT 確保它們的執(zhí)行不會破壞最終一致性。

確保一致性：

合并操作：CRDT 保證所有副本都會根據(jù)合并規(guī)則最終收斂到一致的狀態(tài)。無論是 UNDO 還是 REDO 操作，系統(tǒng)通過合并規(guī)則將操作結(jié)果應(yīng)用到每個(gè)副本，最終所有副本的數(shù)據(jù)會一致。
最終一致性：操作的回溯（如 UNDO 和 REDO）不會導(dǎo)致系統(tǒng)中的副本進(jìn)入不一致的狀態(tài)，因?yàn)槊總€(gè)副本都獨(dú)立地執(zhí)行操作并與其他副本同步，最終收斂到一致的數(shù)據(jù)狀態(tài)。

4. 雙向鏈表的應(yīng)用

在一些具體的 CRDT 實(shí)現(xiàn)中（例如分布式文本編輯器），使用雙向鏈表來存儲數(shù)據(jù)，這使得 UNDO 和 REDO 操作更容易實(shí)現(xiàn)。

雙向鏈表支持操作回溯：

每個(gè)節(jié)點(diǎn)表示一個(gè)操作或數(shù)據(jù)項(xiàng)，操作的順序通過前驅(qū)和后繼指針進(jìn)行連接。通過這個(gè)數(shù)據(jù)結(jié)構(gòu)，撤銷（UNDO）和重做（REDO）可以通過更新鏈表的指針來高效實(shí)現(xiàn)。
UNDO：通過回退指針來撤銷最近的操作，將前驅(qū)指針指向當(dāng)前操作的前一個(gè)節(jié)點(diǎn)。
REDO：通過更新指針來重做撤銷的操作，恢復(fù)后繼指向已撤銷操作的下一個(gè)節(jié)點(diǎn)。

雙向鏈表使得撤銷和重做操作在數(shù)據(jù)結(jié)構(gòu)中非常高效，并且能夠根據(jù)唯一標(biāo)識符和合并規(guī)則來正確解決沖突。

CRDT 通過以下幾個(gè)關(guān)鍵特性解決了 UNDO 和 REDO 問題：

唯一標(biāo)識符：每個(gè)操作有唯一標(biāo)識符，確?；厮莺椭刈鰰r(shí)能按正確順序執(zhí)行。
冪等性、交換性和結(jié)合性：這些特性確保了 UNDO 和 REDO 操作的正確性，并且即使在并發(fā)操作的情況下，也能夠保證一致性。
去中心化合并：每個(gè)副本獨(dú)立處理 UNDO 和 REDO，并通過合并規(guī)則確保最終一致性。
雙向鏈表：為 UNDO 和 REDO 提供高效的操作存儲和回溯機(jī)制，特別適合用于文本編輯等場景。

通過這些機(jī)制，CRDT 在分布式環(huán)境下不僅保證了 UNDO 和 REDO 的一致性，還有效解決了并發(fā)沖突和操作歷史同步的問題。

CRDT 解決并發(fā)沖突

接下來我們將以圖片設(shè)置 align 屬性為例介紹，首先看看 CRDT 如何描述對象屬性及屬性修改：

左邊是圖片數(shù)據(jù)模型，右邊是模擬 CRDT 對應(yīng)的數(shù)據(jù)結(jié)構(gòu)，圖片對象中的每一個(gè)字段都使用結(jié)構(gòu)對象去描述內(nèi)容及內(nèi)容的修改，這里以 align 字段的代表看它的表達(dá)

操作 1??：

圖中最上方的藍(lán)色結(jié)構(gòu)表示 align 屬性的初始值為 "center"，其對應(yīng)的數(shù)據(jù)結(jié)構(gòu)標(biāo)識為 (140,20)，表示該值由某個(gè)用戶在某個(gè)時(shí)刻的操作產(chǎn)生。

隨后，用戶執(zhí)行了操作 ①，將 align 從 "center" 修改為 "left"，從而生成了一個(gè)新的結(jié)構(gòu)對象（圖中橙色部分），其標(biāo)識符為 (141,0)。這個(gè)新對象通過 left 指針指向其前一個(gè)狀態(tài) (140,20)，表示該修改是基于 "center" 狀態(tài)進(jìn)行的。此時(shí)，Map 中的 align 字段被更新為指向這個(gè)新的對象。

?? 值得注意的是：此結(jié)構(gòu)中的 left 和 right 同時(shí)承擔(dān)了兩個(gè)不同含義——

一方面，它們是鏈表結(jié)構(gòu)中的指針字段，用于描述節(jié)點(diǎn)之間的連接關(guān)系；
另一方面，align 的屬性值也恰好是 "left"、"center"、"right" 之一。

為避免混淆，請理解：結(jié)構(gòu)對象中間的那一塊，才是真正表示屬性值的內(nèi)容，而兩側(cè)的 left / right 是鏈表的結(jié)構(gòu)指針。比如在該示例中，中間的 "left" 是修改后的 align 值，而左側(cè)的 left 指針連接了前一個(gè)狀態(tài) (140,20)。

操作 2??：

當(dāng)然！以下是你后續(xù)“并發(fā)修改”部分的潤色版本，緊接在“順序修改”之后，風(fēng)格統(tǒng)一，邏輯清晰，讀起來也更專業(yè)：

與前面的順序修改不同，在并發(fā)場景中，多個(gè)用戶幾乎同時(shí)基于相同的狀態(tài)進(jìn)行修改操作。此時(shí)，CRDT 會采用特定的合并策略來決定各個(gè)操作的插入順序，從而確保所有副本最終達(dá)成一致。

如圖所示，這一次有兩個(gè)用戶同時(shí)基于狀態(tài) (140,20)（即 align = "center"）分別執(zhí)行了修改操作：

用戶 A 將 align 改為 "left"，生成結(jié)構(gòu)對象 (141,0)
用戶 B 將 align 改為 "right"，生成結(jié)構(gòu)對象 (142,0)

由于這兩個(gè)操作是并發(fā)的，它們都指向相同的前置節(jié)點(diǎn) (140,20)，即具有相同的“前提條件”。此時(shí)系統(tǒng)將根據(jù)每個(gè)操作的唯一標(biāo)識符進(jìn)行排序合并——在本例中，(141,0) 的優(yōu)先級低于 (142,0)，因此 "left" 會先插入鏈表，緊接著是 "right"。

最終形成的雙向鏈表結(jié)構(gòu)如下：

center → left → right
         ↑      ↑
     (141,0) (142,0)

系統(tǒng)將 align 字段指向鏈表尾部的最新節(jié)點(diǎn) (142,0)，因此最終的屬性值為 "right"。

這種機(jī)制展現(xiàn)了 CRDT 在面對并發(fā)修改時(shí)的優(yōu)勢：無需沖突檢測，也不丟失任一修改歷史，并能通過一致的排序規(guī)則達(dá)成最終一致性。

下面看看兩個(gè)用戶并發(fā)的執(zhí)行屬性修改時(shí)產(chǎn)生的數(shù)據(jù)結(jié)構(gòu)：

與前面的順序操作不同，此處執(zhí)行的操作 ① 和操作 ② 是并發(fā)修改：它們都是基于同一個(gè)前置狀態(tài)，即 align = "center"（標(biāo)識符為 (140,20)）所發(fā)起的修改操作。

具體來說：

操作 ① 將 align 修改為 "left"，生成新結(jié)構(gòu)對象 (141,0)
操作 ② 將 align 修改為 "right"，生成新結(jié)構(gòu)對象 (142,0)

由于兩個(gè)修改操作的基礎(chǔ)狀態(tài)相同，因此構(gòu)成并發(fā)。在這種情況下，CRDT 會根據(jù)標(biāo)識符的全局有序性來進(jìn)行合并處理。

在本示例中，(141,0) 的標(biāo)識符小于 (142,0)，因此系統(tǒng)會按照如下順序進(jìn)行集成：

先插入 "left"（操作 ①）
再插入 "right"（操作 ②）

最終形成如下鏈表結(jié)構(gòu)：

center → left → right
          ↑       ↑
      (141,0)  (142,0)

因此，最終 align 的屬性值為 "right"，即指向最新插入的節(jié)點(diǎn) (142,0)。

這一過程體現(xiàn)了 CRDT 對并發(fā)操作的自動合并能力：無需人工干預(yù)或沖突解決策略，僅通過標(biāo)識符排序，就能實(shí)現(xiàn)一致性和可預(yù)期的合并結(jié)果。

順序修改 vs 并發(fā)修改：對比總結(jié)

項(xiàng)目	順序修改	并發(fā)修改
操作基礎(chǔ)狀態(tài)	每次操作都基于最新狀態(tài)	多個(gè)操作基于相同的舊狀態(tài)并發(fā)發(fā)生
是否存在沖突	無沖突，順序明確	存在潛在沖突，需合并處理
合并方式	順序串接，每個(gè)結(jié)構(gòu)對象引用上一個(gè)	利用標(biāo)識符排序合并，構(gòu)建多分支鏈表結(jié)構(gòu)
是否保留全部修改	? 是，保留完整歷史	? 是，所有并發(fā)修改都會被表達(dá)
最終結(jié)果決定方式	最后一個(gè)操作決定當(dāng)前值	標(biāo)識符最大的修改贏得當(dāng)前值歸屬
示例回顧	`"center"` → `"left"` → `"right"`	`"center"` → `["left", "right"]`，最終為 `"right"`

在 CRDT 模型下，無論是順序修改還是并發(fā)修改，都能通過結(jié)構(gòu)化的數(shù)據(jù)表示 + 有序標(biāo)識符來安全地整合操作，確保最終狀態(tài)一致，并完整保留修改軌跡。這正是 CRDT 在協(xié)同編輯、離線同步等場景下強(qiáng)大而可靠的基礎(chǔ)。

參考文章

多人協(xié)同編輯技術(shù)的演進(jìn)

總結(jié)

CRDT（無沖突復(fù)制數(shù)據(jù)類型）是一類用于分布式系統(tǒng)中的數(shù)據(jù)結(jié)構(gòu)，它通過內(nèi)建的冪等性、交換性和結(jié)合性操作，支持各副本在無協(xié)調(diào)情況下獨(dú)立更新并自動合并，最終收斂為一致狀態(tài)。它避免了傳統(tǒng)并發(fā)控制中對沖突的顯式處理，適用于離線編輯、多端同步、協(xié)同操作等高可用場景。通過唯一標(biāo)識符和結(jié)構(gòu)化合并策略，CRDT 能在面對并發(fā)修改、網(wǎng)絡(luò)分區(qū)等挑戰(zhàn)時(shí)保持?jǐn)?shù)據(jù)一致性和操作完整性。

轉(zhuǎn)自https://juejin.cn/post/7490425439757664271

該文章在 2025/4/14 9:58:58 編輯過

關(guān)鍵字查詢

多人

協(xié)同

編輯

算法

相關(guān)文章

正在查詢...

點(diǎn)晴ERP是一款針對中小制造業(yè)的專業(yè)生產(chǎn)管理軟件系統(tǒng),系統(tǒng)成熟度和易用性得到了國內(nèi)大量中小企業(yè)的青睞。

點(diǎn)晴PMS碼頭管理系統(tǒng)主要針對港口碼頭集裝箱與散貨日常運(yùn)作、調(diào)度、堆場、車隊(duì)、財(cái)務(wù)費(fèi)用、相關(guān)報(bào)表等業(yè)務(wù)管理，結(jié)合碼頭的業(yè)務(wù)特點(diǎn)，圍繞調(diào)度、堆場作業(yè)而開發(fā)的。集技術(shù)的先進(jìn)性、管理的有效性于一體，是物流碼頭及其他港口類企業(yè)的高效ERP管理信息系統(tǒng)。

點(diǎn)晴WMS倉儲管理系統(tǒng)提供了貨物產(chǎn)品管理,銷售管理,采購管理,倉儲管理,倉庫管理,保質(zhì)期管理,貨位管理,庫位管理,生產(chǎn)管理,WMS管理系統(tǒng),標(biāo)簽打印,條形碼,二維碼管理,批號管理軟件。

點(diǎn)晴免費(fèi)OA是一款軟件和通用服務(wù)都免費(fèi)，不限功能、不限時(shí)間、不限用戶的免費(fèi)OA協(xié)同辦公管理系統(tǒng)。