超碰人人人人人,亚洲AV午夜福利精品一区二区,亚洲欧美综合区丁香五月1区,日韩欧美亚洲系列

什么是 CRDT

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

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

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

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

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

CRDT 的種類

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

基于操作的 CRDT（CmRDT）

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

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

由于操作是以獨立的方式廣播的，通信基礎設施必須保證所有操作都被傳輸?shù)剿懈北荆也僮鞑粫G失或重復。在此過程中，操作的順序是靈活的，可以按照任何順序傳輸。

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

G-Counter

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

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

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

PN-Counter

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

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

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

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

Sequence CRDT

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

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

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

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

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

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

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

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

G-Set

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

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

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

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

2P-Set

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

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

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

2P-Set 的特性包括：

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

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

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

LWW-Element-Set

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

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

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

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

OR-Set

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

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

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

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

CmRDTs 和 CvRDTs

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

CRDT 的數(shù)學基礎

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

1. 交換律（Commutativity）

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

[ A \vee B = B \vee A ]

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

示例：

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

2. 結合律（Associativity）

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

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

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

示例：

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

3. 冪等律（Idempotency）

重復合并不會改變結果：

[ A \vee A = A ]

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

示例：

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

實際意義

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

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

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

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

4. 容錯性： 冪等性確保了系統(tǒng)能夠優(yōu)雅地處理重復的消息，這在不可靠的網絡環(huán)境中特別重要。

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

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

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

CRDT 是如何處理沖突的

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

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

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

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

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

圖示的操作順序：

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

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

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

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

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

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

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

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

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

CRDT 如何解決臟路徑問題

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

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

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

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

操作標識符的作用：

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

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

示例：

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

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

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

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

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

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

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

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

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

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

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

舉例說明：

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

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

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

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

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

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

5. 最終一致性

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

如何確保最終一致性？

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

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

6. 避免臟路徑：總結

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

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

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

CRDT 如何解決 UNDO/REDO 問題

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

什么是 UNDO 和 REDO？

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

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

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

CRDT 如何解決 UNDO 和 REDO 問題

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

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

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

操作的存儲和標識：

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

操作回滾（UNDO）：

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

操作重做（REDO）：

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

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

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

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

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

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

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

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

示例：

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

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

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

確保一致性：

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

4. 雙向鏈表的應用

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

雙向鏈表支持操作回溯：

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

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

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

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

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

CRDT 解決并發(fā)沖突

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

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

操作 1??：

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

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

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

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

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

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

操作 2??：

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

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

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

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

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

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

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

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

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

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

下面看看兩個用戶并發(fā)的執(zhí)行屬性修改時產生的數(shù)據(jù)結構：

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

具體來說：

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

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

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

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

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

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

最終形成如下鏈表結構：

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

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

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

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

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

參考文章

• 多人協(xié)同編輯技術的演進

總結

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

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