使用 CRDT（Yjs）时，当 2 个更改同时发生时，如何处理不同的路径？

Question

我目前正在尝试使用 Yjs 构建协作拖放 HTML 编辑器。我将 Node.js 与 JavaScript 和 jQuery 结合使用。节点服务器 (y-websocket) 处理向其他连接的用户分发事件。

数据结构

我将 HTML 表示为 YArray 和 YMap 的混合，它们是 Yjs 提供的数据结构。

它只是一个包含地图的数组。这些地图有另一个名为“children”的属性，它是另一个包含地图的数组。

Yjs 使用 LSEQ CRDT 来合并并发更改。

在下面的示例中，我们有一个“h1”标签，后跟一个包含“p”标签作为其子标签的 div：

示例：

[
0:    {
      attributes: {class: "canvas-cmp-heading", contenteditable: "true"}
      children: []
      content: "This is a h1"
      dataID: "bga8npswu"
      parent: "canvas"
      tag: "h1"
      }

1:    {
      attributes: {class: "canvas-cmp-div", data-container: "true"}
      children: [
            0:    {
                  attributes: {class: "canvas-cmp sortable ", contenteditable: "true"}
                  children: []
                  content: "This is a paragraph"
                  dataID: "xtytr071u"
                  parent: "ozvmok37w"
                  }
                ]
       }
]

问题

插入和删除效果很好。然而，当两个用户同时移动彼此相关（或将要）的不同元素时，就会出现问题。由于Yjs没有移动功能，所以我们将移动表示为“复制、删除、插入”

考虑以下事项：

用户 1 将段落移动到 div2 中。同时，用户 2 将 div2 移动到 div1 中。

这是一个简单的图片解释我的意思。

并发移动

结果如下：

[
     0: {
          attributes: {class: "canvas-cmp-div", data-container: "true"}
          dataID: "t4dyxn8oc"
          parent: "drd1og7yq"
          tag: "div"
          children: [
                      0: {
                           attributes: {class: "canvas-cmp-div", data-container:"true"}
                           children: []
                           dataID: "t6od980jf"
                           parent: "t4dyxn8oc"
                           tag: "div"
                         }
                          
                    ]
         }
]

上面的结果显示了一个 div 包含另一个 div。这是例外，因为 LSEQ 使用 Last-Writer-Wins。这意味着段落将丢失。

期望的结果应该如下：

[
     0: {
          attributes: {class: "canvas-cmp-div", data-container: "true"}
          dataID: "t4dyxn8oc"
          parent: "drd1og7yq"
          tag: "div"
          children: [
                      0: {
                           attributes: {class: "canvas-cmp-div", data-container:"true"}
                           dataID: "t6od980jf"
                           parent: "t4dyxn8oc"
                           tag: "div"
                           children: [
                                       0: {
                                       attributes: {class: "canvas-cmp-p", data-container:"true"}
                                       dataID: "d2edyhg42"
                                       parent: "t6od980jf"
                                       tag: "p"
                                       children: []
                                           }
                                     ]
                         }

                     ]
         }
]

问题在于额外的深度。该算法不知道必须为“p”标签添加额外的深度。

这是我的嵌套函数的样子：

 move_nested(el, event)
    {
        let dataID = el.attr('data-id')
        let index = el.index()

        let oldPath = this.getPathFromElement(el) // The path to the currently dragged element

        if (el.parent()[0] == event.target)
            return

        let newPath = this.getPathFromElement($(event.target)) // Path to where we want to drop it

        this.doc.transact(() =>
        {
            let sourceMap = this.mainArray
            let targetMap = this.mainArray.get(newPath.shift())

            while (oldPath.length - 1 > 0) //Get the parent-map of the dragged element
            {
                sourceMap = sourceMap.get(oldPath.shift()).get('children')
            }
            while (newPath.length > 0) //Get the target-map we drop the element into
            {
                targetMap = targetMap.get('children').get(newPath.shift())
            }

            let clone = sourceMap.get(oldPath[0]).clone() //Clone the map
            clone.set('parent', $(event.target).attr('data-id'))
            sourceMap.delete(oldPath.shift()) //Remove the old map from the old location
            targetMap.get('children').push([clone]) //Insert the cloned map to the target location
        })
    }

任何传入的更新都由 Yjs 提供的observeDeep 函数处理。

 let docLoaded = false
 this.mainArray.observeDeep(events =>
 {
    if (!docLoaded)
    {
        const changes = events[0].changes.delta[0] ?? null
        if (changes)
           this.renderDoc(events[0].target, changes)

        docLoaded = true
    }
    else
    {
       for (const event of events)
       {
          const changes = event.changes
          this.renderChanges(changes)
       }
    }
})

我的想法

我想出了使用完全扁平的层次结构而不是嵌套数组的想法。

例如：

[

0: { "p1", "parent":"div1" }

1: { "div1", "parent": null, "children": ["p1"] }

2: { "div2", "parent": null, "children": [] }
    
]   

div2 将其父级更新为 div1，p 将其父级更新为 div2。理论上，当在不同深度同时发生 2 个更改时，这可以起作用，因为同时移动物体时不需要创建新的深度。

这里的问题是，当我们将完整的数组转换回 HTML 时，我如何知道必须首先创建哪些元素。 （我们不能将“p”标签附加到尚不存在的 div 上）。我不想在数组中运行 n 次以获得正确的顺序。当有很多元素时，这似乎效率很低。

我该如何解决这个问题？

Answer 1

Yjs 支持专用移动操作 - 很少有公司使用。它不是主分支/发布的一部分，因此您需要从 move 分支 获取它。

示例：

import * as Y from 'yjs'

const doc = new Y.Doc()
const array = doc.getArray('array')
array.insert(0, [3, 2, 1]) // [3,2,1]
array.move(0, 3) // [2,1,3]

当前的限制是：

• 它仅适用于数组和 XML 节点。
• 它只能在同一个集合中工作（因此改变 YArray 内部元素的顺序，但不能跨不同的 YArray）。
• 虽然可以移动元素范围，但尚未经过充分测试，无法建议在生产中使用它。

PS：Yjs 不使用 LSeq。它使用YATA算法来解决冲突。您可以在此处和此处阅读更多相关信息。