無衝突複製資料類型 (CRDT) 是一類資料結構，可在分散式系統中實現無縫協作和資料同步，從而實現無衝突的協作更新。 CRDT 旨在實現跨多個資料副本的最終一致性，確保即使更新獨立發生，所有副本也能收斂到相同狀態，而不需要複雜的衝突解決機制。

在這篇文章中，我們將深入研究 CRDT 是什麼，探索它們的用途和類型，了解它們的工作原理，並學習如何實現它們，重點關注 JavaScript 和強大的 Yjs 庫。

CRDT 的用例

CRDT 在即時協作和離線支援至關重要的場景中特別有用：

1. 協作文字編輯器：Google Docs、Notion 和 Etherpad 使用類似 CRDT 的結構進行即時編輯。
2. 協作設計工具：Figma 是一種流行的基於 Web 的設計工具，它使用 CRDT 來實現設計專案的即時協作。多個設計人員可以同時處理同一個文件，所有使用者之間的變更可以無縫同步。
3. 分散式資料庫：RxDB 和 Riak 使用 CRDT 進行無衝突複製。
4. 多人遊戲：用來維持玩家之間一致的遊戲狀態。

CRDT 的類型

CRDT 主要有兩種：

1. 基於狀態的 CRDT：它們複製資料結構的整個狀態。合併是透過比較和協調不同副本的狀態來完成的。
2. 基於操作的 CRDT：它們複製對資料結構執行的操作。合併是透過以交換方式應用來自不同副本的操作來完成的。

CRDT 的工作原理

CRDT（無衝突複製資料類型）的運作原理可確保所有資料副本的最終一致性，即使是同時進行更新或發生網路分割區時也是如此。讓我們更深入地研究一下機制：

主要特性

1. 交換性：此屬性確保運算順序不會影響最終結果。例如，在計數器 CRDT 中，先遞增 2，然後再遞增 3，與先遞增 3，然後再遞增 2 產生的結果相同。
2. 關聯性：這意味著操作的分組並不重要。再次使用計數器範例，(1 2) 3 與 1 (2 3) 相同。
3. 冪等性：多次應用相同的操作與應用一次效果相同。這對於處理分散式系統中的重複訊息至關重要。

衝突解決

CRDT 透過設計自動解決衝突：

• 對於基於狀態的 CRDT (CvRDT)，這是透過組合兩個副本的狀態的合併函數來實現的。此合併函數必須是可交換的、關聯的和冪等的。
• 對於基於操作的 CRDT (CmRDT)，操作被設計為可交換的，確保以任何順序應用它們都會導致相同的最終狀態。

邏輯時鐘

許多 CRDT 實作使用邏輯時鐘（例如版本向量或點分版本向量）來追蹤操作的因果歷史。這有助於確定並發操作的順序以及確定副本已經看到哪些更新。

在 JavaScript 中使用 CRDT 和 Yjs

從頭開始實施 CRDT 可能很複雜。但是，有一些庫可以簡化該過程。對於 JavaScript，最受歡迎的 CRDT 函式庫之一是 Yjs。它是一個高效能的CRDT實現，支援各種資料類型。讓我們使用 Yjs 創建一個簡單的待辦事項清單應用程序，模擬多個使用者處理記憶體中的相同文件。

以下是如何使用 Yjs 實作共享待辦事項清單的範例：

讓我們使用已建立的 ydocs ：

在此範例中，我們建立兩個 Yjs 文件（ydoc1 和 ydoc2）來模擬兩個使用者處理相同待辦事項清單。每個文件都有自己的待辦事項共享地圖。

我們定義了新增、更新和刪除待辦事項的函數，以及用於手動同步兩個文件之間的狀態的syncDocs函數。這模擬了在客戶端之間交換更新的網路環境中會發生的情況。

結論

CRDT 為建立可在線上和離線無縫工作的協作分散式應用程式提供了強大的解決方案。雖然底層概念可能很複雜，但像 Yjs 這樣的程式庫使開發人員可以更輕鬆地在其應用程式中利用 CRDT 的強大功能。隨著分散式系統變得越來越普遍，理解和利用 CRDT 將成為開發人員越來越有價值的技能。

有用的連結

1. Yjs
2. CRDT
3. Tiptap - 協作文字編輯器