日韩欧美国产精品免费一二-日韩欧美国产精品亚洲二区-日韩欧美国产精品专区-日韩欧美国产另-日韩欧美国产免费看-日韩欧美国产免费看清风阁

什么是 CRDT

無沖突復制數據類型（CRDT，Conflict-free Replicated Data Types）是一類在分布式系統中用于數據復制的數據結構，旨在解決多副本并發更新時的數據一致性問題。CRDT 允許各個副本獨立且并發地進行更新，而無需協調，且能夠在最終自動解決可能出現的不一致性。

CRDT 的關鍵特性主要有以下三個方面：

1. 獨立更新： 每個副本可以獨立地進行更新，無需與其他副本進行通信。

2. 自動合并： 當副本之間交換數據時，CRDT 會自動合并更新，確保所有副本最終達到一致狀態。

3. 最終一致性： 盡管副本可能在某些時刻處于不同狀態，但通過合并操作，所有副本最終會收斂到相同的狀態。

CRDT 的種類

CRDT 有兩種方法，都可以提供強最終一致性：基于操作的 CRDT 和基于狀態的 CRDT。

基于操作的 CRDT（CmRDT）

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

操作是可交換的，這意味著操作的順序不影響最終結果。也就是說，即使操作以不同的順序應用，最終的結果也會是一樣的。然而，這些操作不一定是冪等的，即重復應用相同操作可能會產生不同的結果。

由于操作是以獨立的方式廣播的，通信基礎設施必須保證所有操作都被傳輸到所有副本，而且操作不會丟失或重復。在此過程中，操作的順序是靈活的，可以按照任何順序傳輸。

純基于操作的 CRDT（Pure CmRDT） 是基于操作的 CRDT 的一個變種，它通過減少所需的元數據大小來優化性能。

G-Counter

G-Counter 用于實現分布式環境中的計數器功能，由多個計數器組成的數據結構，每個副本都維護自己的計數器。每當副本需要增加計數時，它只會在自己的計數器上增加，而不會減少或修改其他副本的計數器。當需要獲取計數時，副本會將所有計數器的值累加起來，以獲得全局的計數結果。G-Counter 是一個只增長的計數器，它滿足如下的性質：

1. 每個副本的計數器值只增加，不會減少。

2. 副本之間的計數器值可以獨立增長，不會發生沖突或合并操作。

PN-Counter

PN-Counter 是一種基于 CRDT 的數據類型，用于實現分布式環境中的計數器功能。由兩個 G-Counter 組成的數據結構，分別用于記錄正數和負數的計數。每個副本都維護自己的兩個計數器，分別用于增加正數計數和增加負數計數。當需要獲取計數時，副本會將正數計數器的值減去負數計數器的值，以獲得全局的計數結果。PN-Counter 具有以下性質：

1. 每個副本的正數計數器和負數計數器值只增加，不會減少。

2. 副本之間的計數器值可以獨立增長，不會發生沖突或合并操作。

3. 全局計數結果是正數計數減去負數計數的差值。

Sequence CRDT

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

1. 并發操作可以獨立地在不同副本上執行，不會發生沖突。

2. 合并操作時，可以根據標識符和合并策略將并發操作正確地合并到最終結果中。

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

基于狀態的 CRDT（CvRDT）

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

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

Delta 狀態 CRDT 是基于狀態的 CRDT 的一種優化版本。在 Delta CRDT 中，僅傳播最近對狀態進行的更改（即"delta"），而不是將整個狀態傳輸到其他副本。這減少了每次更新的網絡開銷，并提高了效率。只有當某個副本的狀態發生變化時，才會將該變化廣播給其他副本，從而避免了大量不必要的數據傳輸。

G-Set

G-Set 是一種基于 CRDT 的數據類型，用于實現分布式環境中的集合功能，G-Set 是一個只增長的集合，每個副本都維護自己的本地集合。當需要添加元素時，副本只會在自己的集合中添加元素，而不會刪除或修改其他副本的集合。G-Set 的特性包括：

1. 每個副本維護自己的本地集合，可以獨立地增加元素。

2. 全局集合是所有副本的集合的并集，即包含所有副本中添加的元素。

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

2P-Set

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

1. 添加元素：將元素添加到添加集合中。

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

2P-Set 的特性包括：

1. 每個副本維護自己的本地添加集合和移除集合，可以獨立地進行添加和移除操作。

2. 全局集合是添加集合減去移除集合的結果。

當需要獲取全局集合時，副本將所有副本的添加集合和移除集合合并，并計算添加集合減去移除集合的結果，得到最終的全局集合。2P-Set 可以實現在分布式環境中維護集合，并且具有最終一致性。它適用于需要記錄添加和移除操作，并且不希望元素重復添加或移除的場景。

LWW-Element-Set

LWW-Element-Set 用于實現分布式環境中的集合功能，維護一個集合，其中每個元素都與一個時間戳相關聯。時間戳可以是遞增的整數，邏輯時鐘，或其他可比較的時間表示。每當需要添加或移除元素時，副本會將元素與當前時間戳關聯，并將操作應用到本地集合。LWW-Element-Set 的特性包括：

1. 每個副本維護自己的本地集合，可以獨立地添加或移除元素。

2. 全局集合是根據時間戳確定的最新操作的結果，即最后的寫操作勝出。

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

OR-Set

OR-Set 用于實現分布式環境中的集合功能，維護一個集合，其中每個元素都與一個標識符相關聯。當需要添加元素時，副本會為元素生成一個唯一的標識符，并將其添加到本地集合中。當需要移除元素時，副本會為要移除的元素生成一個移除標記，并將其關聯到原始元素的標識符上。OR-Set 的特性包括：

1. 每個副本維護自己的本地集合，可以獨立地添加和移除元素。

2. 全局集合是所有副本的集合的并集，其中移除標記會覆蓋對應的元素。

當需要獲取全局集合時，副本將所有副本的集合合并，并根據標識符和移除標記進行操作。如果一個元素的標識符存在于集合中，但它的移除標記也存在，則該元素被視為已移除。這樣，移除操作具有優先級高于添加操作的效果。OR-Set 可以實現在分布式環境中維護集合，并且具有最終一致性。它適用于需要記錄元素的添加和移除，并且允許移除操作覆蓋添加操作的場景。

CmRDTs 和 CvRDTs

相比于 CvRDTs，CmRDTs 在副本之間傳輸操作的協議上有更多要求，但當事務數量相對于內部狀態的大小較小時，它們使用的帶寬較少。然而，由于 CvRDT 的合并函數是可結合的，與某個副本的狀態進行合并會包含該副本的所有先前更新。在減少網絡使用和處理拓撲變化方面，使用 Gossip 協議可以很好地傳播 CvRDT 狀態到其他副本。

CRDT 的數學基礎

CRDT 的核心在于其合并操作必須滿足一組特定的數學性質，這些性質保證了在分布式系統中數據最終能夠達到一致。合并操作（通常表示為 ∨）必須滿足以下三個關鍵性質：

1. 交換律（Commutativity）

合并操作的順序不影響最終結果：

[ A \vee B = B \vee A ]

這意味著無論是節點 A 先將數據同步給節點 B，還是節點 B 先將數據同步給節點 A，最終的結果都是一樣的。這個性質對于分布式系統特別重要，因為在實際環境中，我們無法保證數據同步的順序。

示例：

節點1的狀態: {a, b}
節點2的狀態: {b, c}
合并結果: {a, b, c}  // 無論是1→2還是2→1的同步順序，結果都相同

2. 結合律（Associativity）

多個合并操作的順序不影響最終結果：

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

這個性質確保了在有多個節點時，無論按什么順序進行合并，最終結果都是一致的。這對于大規模分布式系統尤為重要，因為數據同步可能涉及多個節點的鏈式傳遞。

示例：

節點1的狀態: {a, b}
節點2的狀態: {b, c}
節點3的狀態: {c, d}
(節點1 ∨ 節點2) ∨ 節點3 = {a, b, c} ∨ {c, d} = {a, b, c, d}
節點1 ∨ (節點2 ∨ 節點3) = {a, b} ∨ {b, c, d} = {a, b, c, d}

3. 冪等律（Idempotency）

重復合并不會改變結果：

[ A \vee A = A ]

這個性質保證了即使同一個更新被應用多次（例如由于網絡問題導致的重復傳輸），也不會影響最終狀態。這對于構建容錯的分布式系統至關重要。

示例：

狀態A: {a, b, c}
A ∨ A = {a, b, c}  // 重復合并不會產生新的結果

實際意義

這些數學性質的重要性體現在：

1. 網絡分區容忍： 由于交換律和結合律的存在，系統可以在網絡分區的情況下繼續工作，當連接恢復后可以正確合并數據。

2. 最終一致性保證： 這些性質確保了無論數據同步的順序如何，所有副本最終都會收斂到相同的狀態。

3. 去中心化： 不需要中央協調器來處理并發更新，每個節點都可以獨立處理更新并最終達到一致。

4. 容錯性： 冪等性確保了系統能夠優雅地處理重復的消息，這在不可靠的網絡環境中特別重要。

在實際應用中，這些性質使得 CRDT 特別適合構建：

• 協同編輯系統
• 分布式數據庫
• 多設備數據同步
• 離線優先的應用

通過確保這些數學性質，CRDT 能夠在不需要復雜的協調機制的情況下，保證分布式系統中數據的最終一致性。

CRDT 是如何處理沖突的

下圖描述了 Yjs 中處理沖突的算法模型，它是一個支持點對點傳輸的沖突處理模型。

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

1. E(1,0)：表示用戶 1 在節點 A 和 B 之間插入了數據項。

2. D(0,1)：表示用戶 0 在節點 B 和 C 之間插入了數據項。

3. C(0,0)：表示用戶 0 在節點 A 和 B 之間插入了數據項。

圖示的操作順序：

1. 用戶 0 插入了 C(0,0) 在節點 A 和 B 之間。

2. 用戶 0 在節點 B 和 C 之間插入了 D(0,1)。

3. 用戶 1 插入了 E(1,0) 在節點 A 和 B 之間。

當兩個操作發生并發沖突（例如 C(0,0) 和 E(1,0) 都涉及節點 A 和 B 之間的插入），Yjs 會基于操作的用戶標識符來決定哪一個操作先應用。

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

CRDT 機制能夠避免傳統操作轉發（OT）所面臨的沖突問題，同時保證最終一致性，原因在于其設計采用了沖突自由的合并規則，而不依賴于復雜的操作變換和中央協調。

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

與此不同，CRDT 通過設計內建的合并規則來避免這些問題。每個 CRDT 數據結構都確保其操作是冪等、交換性強且結合性好的，這意味著無論操作順序如何或是否發生并發操作，所有副本都能夠自動且無沖突地合并，最終收斂到一致的狀態。CRDT 不依賴于操作的順序或中央協調，而是依靠每個操作的唯一標識符和局部合并規則來直接解決并發沖突，從而顯著減少了在處理沖突時的計算復雜度。

此外，CRDT 的這一機制使得它天然適合高可用性和容錯性要求較高的分布式系統，在面對網絡分區、節點故障等場景時，系統依然能夠繼續操作并保證數據一致性。因此，CRDT 更加簡潔、易于擴展，并能夠在沒有顯式操作轉發和變換的情況下，確保最終一致性，從根本上避免了 OT 中因操作順序和變換導致的復雜性和潛在沖突。

CRDT 如何解決臟路徑問題

在分布式系統中，臟路徑（Dirty Path）問題通常出現在多個副本之間進行并發操作時，導致副本之間的數據狀態不一致。由于不同副本的操作可能由于網絡延遲、分區或同步問題而不同步，這使得系統中可能出現不一致的數據狀態。傳統的分布式系統通常依賴中心化的協調機制來同步數據，但這也容易引發性能瓶頸和復雜的沖突解決問題。CRDT（沖突自由復制數據類型）通過去中心化和無沖突的操作設計，避免了臟路徑問題，確保多個副本能夠在并發操作后最終收斂到一致的狀態。

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

1. 唯一標識符與操作標記

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

操作標識符的作用：

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

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

示例：

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

2. 并發操作的解決

在 CRDT 中，每個副本都能夠獨立進行操作，當多個副本發生并發操作時，CRDT 使用設計的 合并規則 來自動解決沖突，確保所有副本最終達到一致狀態。

如何處理并發操作？

• 當用戶 A 在副本 1 上插入字符 X，并且用戶 B 在副本 2 上插入字符 Y 時，兩個操作會先在本地副本上執行，然后通過網絡傳播到其他副本。
• CRDT 會通過 操作標識符 比較來確定哪個操作先執行。比如，比較 A,0 和 B,0，標識符較小的操作會先應用。

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

3. 合并規則與最終一致性

CRDT 的設計關鍵在于 合并規則，即如何將并發操作合并為一致的狀態。這些合并規則確保了即使副本之間的操作順序不同，最終副本的數據會收斂到相同的狀態。

合并規則保證一致性：

1. 冪等性（Idempotence）：一個操作可以多次應用，結果不會改變。如果某個操作被傳送到一個副本多次，只會影響一次，避免重復操作帶來的問題。
2. 交換性（Commutativity）：操作的順序不影響最終結果。不同副本的操作可能發生順序不同，但最終合并時，所有副本的數據狀態將是一致的。
3. 結合性（Associativity）：多個操作的合并順序不影響結果。即使合并操作的順序不同，最終的合并結果相同。

這些規則使得 CRDT 在面對并發更新時，能夠自動解決沖突并收斂到一致的狀態。

舉例說明：

假設兩個用戶并發進行插入操作，用戶 A 在副本 1 中插入 X，而用戶 B 在副本 2 中插入 Y。無論這兩個操作的順序如何，CRDT 會根據合并規則確定最終的順序，并保證合并后的狀態一致。即使兩個副本的操作順序不同，最終的結果將是文本 "XY" 或 "YX"（具體順序依賴于標識符的比較）。

4. 雙向鏈表在 CRDT 中的應用

在一些 CRDT 應用（例如文本編輯器）中，雙向鏈表 被用來存儲數據。雙向鏈表的結構非常適合表示具有順序關系的數據，并且支持高效的插入、刪除和更新操作。

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

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

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

5. 最終一致性

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

如何確保最終一致性？

• 去中心化：CRDT 不依賴中心化的協調，所有副本都能獨立執行操作并進行合并。每個副本都維護自己的操作歷史，并通過合并規則來自動解決沖突。
• 同步與傳播：每個副本定期與其他副本同步，傳播其操作。即使某些副本的更新稍有延遲，最終每個副本的狀態都會通過合并收斂到一致。

通過最終一致性，CRDT 確保即使在網絡分區或節點故障的情況下，系統中的所有副本最終都會收斂到相同的數據狀態，避免了臟路徑問題。

6. 避免臟路徑：總結

CRDT 解決臟路徑問題的關鍵在于：

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

通過這些機制，CRDT 確保了分布式系統中的高可用性、容錯性和一致性，避免了臟路徑問題的出現，并且簡化了分布式系統中并發操作的管理。

CRDT 如何解決 UNDO/REDO 問題

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

什么是 UNDO 和 REDO？

• UNDO：是撤銷上一步操作的功能，即恢復到操作前的狀態。在分布式系統中，UNDO 通常需要回滾到某個特定的歷史狀態。
• REDO：是重新執行撤銷操作后的功能，將上一步撤銷的操作重新應用于數據中。

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

• 并發沖突：不同副本上的操作順序不同，可能會導致狀態不一致，尤其是在操作順序發生變化時。
• 操作歷史的同步：在沒有中心化控制的情況下，操作歷史的同步可能會變得非常復雜。
• 最終一致性：確保在分布式環境中，UNDO 和 REDO 不會導致不同副本的數據不一致。

CRDT 如何解決 UNDO 和 REDO 問題

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

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

CRDT 中的每個操作（如插入、刪除等）都有一個唯一標識符。通過設計合適的操作歷史結構，CRDT 可以存儲每個操作，并支持操作的回溯和重做。這對于分布式系統中的 UNDO 和 REDO 操作至關重要。

操作的存儲和標識：

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

操作回滾（UNDO）：

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

操作重做（REDO）：

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

2. 如何支持并發和沖突解決

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

冪等性、交換性和結合性：

• 冪等性：確保同一個操作多次應用不會改變最終的結果。例如，當執行 UNDO 時，即使該操作多次傳遞給不同副本，它的效果仍然是相同的。
• 交換性：多個操作的順序不會影響最終結果。即使在不同副本上執行 UNDO 和 REDO 操作，操作的順序不會影響最終的數據一致性。
• 結合性：多個 UNDO 或 REDO 操作的順序不影響結果。無論如何組合多個操作，系統最終會達到一致狀態。

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

解決并發沖突的方式：

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

示例：

• 假設兩個用戶 A 和 B 同時進行文本插入操作，在某個時刻用戶 A 撤銷了插入操作，而用戶 B 在該位置再次插入了文本。CRDT 會根據操作的標識符來判斷用戶 A 的撤銷操作和用戶 B 的插入操作的執行順序，保證最終文本的一致性。

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

CRDT 的設計目標之一是 最終一致性。即使操作的執行順序不同，所有副本最終都會達到一致的狀態。對于 UNDO 和 REDO 操作，CRDT 確保它們的執行不會破壞最終一致性。

確保一致性：

• 合并操作：CRDT 保證所有副本都會根據合并規則最終收斂到一致的狀態。無論是 UNDO 還是 REDO 操作，系統通過合并規則將操作結果應用到每個副本，最終所有副本的數據會一致。
• 最終一致性：操作的回溯（如 UNDO 和 REDO）不會導致系統中的副本進入不一致的狀態，因為每個副本都獨立地執行操作并與其他副本同步，最終收斂到一致的數據狀態。

4. 雙向鏈表的應用

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

雙向鏈表支持操作回溯：

• 每個節點表示一個操作或數據項，操作的順序通過前驅和后繼指針進行連接。通過這個數據結構，撤銷（UNDO）和重做（REDO）可以通過更新鏈表的指針來高效實現。
• UNDO：通過回退指針來撤銷最近的操作，將前驅指針指向當前操作的前一個節點。
• REDO：通過更新指針來重做撤銷的操作，恢復后繼指向已撤銷操作的下一個節點。

雙向鏈表使得撤銷和重做操作在數據結構中非常高效，并且能夠根據唯一標識符和合并規則來正確解決沖突。

CRDT 通過以下幾個關鍵特性解決了 UNDO 和 REDO 問題：

1. 唯一標識符：每個操作有唯一標識符，確保回溯和重做時能按正確順序執行。
2. 冪等性、交換性和結合性：這些特性確保了 UNDO 和 REDO 操作的正確性，并且即使在并發操作的情況下，也能夠保證一致性。
3. 去中心化合并：每個副本獨立處理 UNDO 和 REDO，并通過合并規則確保最終一致性。
4. 雙向鏈表：為 UNDO 和 REDO 提供高效的操作存儲和回溯機制，特別適合用于文本編輯等場景。

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

CRDT 解決并發沖突

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

左邊是圖片數據模型，右邊是模擬 CRDT 對應的數據結構，圖片對象中的每一個字段都使用結構對象去描述內容及內容的修改，這里以 align 字段的代表看它的表達

操作 1??：

左邊是圖片數據模型，右邊是模擬 CRDT 對應的數據結構，圖片對象中的每一個字段都使用結構對象去描述內容及內容的修改，這里以 align 字段的代表看它的表達

圖中最上方的藍色結構表示 align 屬性的初始值為 "center"，其對應的數據結構標識為 (140,20)，表示該值由某個用戶在某個時刻的操作產生。

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

?? 值得注意的是：此結構中的 left 和 right 同時承擔了兩個不同含義——

• 一方面，它們是鏈表結構中的指針字段，用于描述節點之間的連接關系；
• 另一方面，align 的屬性值也恰好是 "left"、"center"、"right" 之一。

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

操作 2??：

當然！以下是你后續“并發修改”部分的潤色版本，緊接在“順序修改”之后，風格統一，邏輯清晰，讀起來也更專業：

與前面的順序修改不同，在并發場景中，多個用戶幾乎同時基于相同的狀態進行修改操作。此時，CRDT 會采用特定的合并策略來決定各個操作的插入順序，從而確保所有副本最終達成一致。

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

• 用戶 A 將 align 改為 "left"，生成結構對象 (141,0)

• 用戶 B 將 align 改為 "right"，生成結構對象 (142,0)

由于這兩個操作是并發的，它們都指向相同的前置節點 (140,20)，即具有相同的“前提條件”。此時系統將根據每個操作的唯一標識符進行排序合并——在本例中，(141,0) 的優先級低于 (142,0)，因此 "left" 會先插入鏈表，緊接著是 "right"。

最終形成的雙向鏈表結構如下：

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

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

這種機制展現了 CRDT 在面對并發修改時的優勢：無需沖突檢測，也不丟失任一修改歷史，并能通過一致的排序規則達成最終一致性。

下面看看兩個用戶并發的執行屬性修改時產生的數據結構：

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

具體來說：

• 操作 ① 將 align 修改為 "left"，生成新結構對象 (141,0)

• 操作 ② 將 align 修改為 "right"，生成新結構對象 (142,0)

由于兩個修改操作的基礎狀態相同，因此構成并發。在這種情況下，CRDT 會根據標識符的全局有序性來進行合并處理。

在本示例中，(141,0) 的標識符小于 (142,0)，因此系統會按照如下順序進行集成：

1. 先插入 "left"（操作 ①）

2. 再插入 "right"（操作 ②）

最終形成如下鏈表結構：

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

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

這一過程體現了 CRDT 對并發操作的自動合并能力：無需人工干預或沖突解決策略，僅通過標識符排序，就能實現一致性和可預期的合并結果。

順序修改 vs 并發修改：對比總結

在 CRDT 模型下，無論是順序修改還是并發修改，都能通過結構化的數據表示 + 有序標識符來安全地整合操作，確保最終狀態一致，并完整保留修改軌跡。這正是 CRDT 在協同編輯、離線同步等場景下強大而可靠的基礎。

參考文章

• 多人協同編輯技術的演進

總結

CRDT（無沖突復制數據類型）是一類用于分布式系統中的數據結構，它通過內建的冪等性、交換性和結合性操作，支持各副本在無協調情況下獨立更新并自動合并，最終收斂為一致狀態。它避免了傳統并發控制中對沖突的顯式處理，適用于離線編輯、多端同步、協同操作等高可用場景。通過唯一標識符和結構化合并策略，CRDT 能在面對并發修改、網絡分區等挑戰時保持數據一致性和操作完整性。

轉自https://juejin.cn/post/7490425439757664271