Yjs——一個基於 CRDT 的數據協同框架

目前，解決分佈式數據一致性問題有兩大主流的方案：OT 與 CRDT。OT 算法由於提出時間早，方案成熟，被各大在線編輯產品使用。但因爲需要定義與業務強相關的 Operation，通過操作轉換實現衝突處理，在應用上存在一定的限制。本文介紹一個新的基於 CRDT 的開源數據協同框架。

目前，解決分佈式數據一致性問題有兩大主流的方案：Operational transformation（簡稱 OT）與 Conflict-free Replicated Data Type（簡稱 CRDT）。

本文主要介紹一個新的基於 CRDT 的開源數據協同框架——Yjs，從源碼分析 Yjs 的協同實現。

Yjs 是基於論文《Near Real-Time Peer-to-Peer Shared Editing on Extensible Data Types》 的改進，是一個 CRDT 的實例，目前在 GitHub 上有 3.2k 🌟。

目前，基於 Yjs 框架開發的應用有以下：

  1. 整體架構

  1. 數據結構說明

Yjs 的數據元素使用的是雙向鏈表的存儲結構，每個元素包含左右結點，分別指向前一個 struct 及接下來一個 struct 數據。

ID：每個 struct 有一個唯一的 ID，包括一個 client 及 clock。client 是每個註冊進來的協同用戶的 id，具有全局唯一性。clock 是一個遞增的時鐘標誌，根據 struct 的內容長度進行遞增。

比如，某個 struct 記爲 s = {client: '123456', clock: 3, len: 4, ...}, 在 s 後新插入一個新的 struct s', s'_ID = createID('123456', s.clock + s.len)。

爲什麼不使用 clock+1 的遞增方式來實現全局唯一性，這裏涉及到後續 “衝突處理” 的一個小技巧。

整個數據結構如下：

yjs 數據結構示意圖

數據內容存儲在 content 中，從當前文段的 start 位置開始，依次讀取節點 right 上的數據，直至結束（right 爲空）。

整個 structs 數據通過雙向鏈表連接，對內容的修改可以通過鏈表操作來實現。因此，Yjs 支持任意數據類型，且與業務無關。如 String、Format、Json，Binary 等。

  1. 衝突處理過程

1）遠端 peer 數據協同

websocket 數據

2）解析 struct

核心數據轉換邏輯包含在 UpdateDecoder.js 、 UpdateEncoder.js 中。decoder 將 uint8Array 解析成 structs（ Array），readClientsStructRefs 處理 struct 插入邏輯。

協同數據描述

decoder 解析過程：

const readStructs = (decoder, transaction, store) => {
  const clientsStructRefs = new Map();
  readClientsStructRefs(decoder, clientsStructRefs, transaction.doc);
  mergeReadStructsIntoPendingReads(store, clientsStructRefs);
  resumeStructIntegration(transaction, store);
  cleanupPendingStructs(store.pendingClientsStructRefs);
  tryResumePendingDeleteReaders(transaction, store);
};

3）變更應用

定義兩種操作類型：insert & delete，在 resumeStructIntegration 中處理數據的變更。

4）衝突處理

因此， insert 與 delete 之間不會產生衝突。

具體實現步驟：

（1）將變更的 structs 入棧， const stack = store.pendingStack；

（2）對比待插入的 struct 的 origin、rightOrigin 字段與 structStore 中對應位置 Struct' 的 origin、rightOrigin 字段， 判斷哪些是存在衝突的數據，記入 conflictingItems 中；

（3）然後根據 ID 的大小，決定衝突數據的應用位置。

5) 處理刪除

找到刪除的 struct 位置，標記爲 deleted 即可。詳見 readAndApplyDeleteSet

6) 遍歷及生成 delta

構造 ItemTextListPosition 結構，迭代 right 節點，對 content 內容進行 insertText/formatText/insertAttributes 操作。

7) 創建 node 節點

通過 YElement 創建編輯器數據節點，調用 createNodeFromYElement 接口。

8) 更新 structs

調用 writeStructs 進行 structs 更新。

  1. 示例：一次插入操作
  1. TextNode 根據 mapping 找到對應的 YText，生成 delta

  1. applyDelta

應用 delta，修改 transaction：

  applyDelta (delta, { sanitize = true } = {}) {
    if (this.doc !== null) {
      transact(this.doc, transaction => {
        const currPos = new ItemTextListPosition(null, this._start, 0, new Map())
        for (let i = 0; i < delta.length; i++) {
          const op = delta[i]
          if (op.insert !== undefined) {
            const ins = (!sanitize && typeof op.insert === 'string' && i === delta.length - 1 && currPos.right === null && op.insert.slice(-1) === '\n') ? op.insert.slice(0, -1) : op.insert
            if (typeof ins !== 'string' || ins.length > 0) {
              insertText(transaction, this, currPos, ins, op.attributes || {})
            }
          } else if (op.retain !== undefined) {
            formatText(transaction, this, currPos, op.retain, op.attributes || {})
          } else if (op.delete !== undefined) {
            deleteText(transaction, currPos, op.delete)
          }
        }
      })
    } else {
      /** @type {Array<function>} */ (this._pending).push(() => this.applyDelta(delta))
    }
  }
  1. structStore 更新過程

  1. 優缺點分析

優點：

不足：

本文主要是基於 Yjs 源碼與論文的閱讀，重點對 Yjs 的數據結構、處理邏輯等進行分析。Yjs 採用合理等數據結構，巧妙的規避了複雜的衝突處理，是區別於 OT 的一套全新的數據一致性解決方案。源碼中還有一些比較巧妙的點，覺得比較有意思，此處就不擴展開了，有興趣的同學可以私下交流學習。因時間比較倉促，文章內容如有疏漏或錯誤，望不吝賜教！

參考文獻

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/cHqXWL54TKSQjL33JSGQ_w

猜你喜歡