问题标签 [operational-transform]

我正在尝试对sharedb我的前端代码实施操作。我目前拥有它，以便它提交操作（https://github.com/ottypes/json0），特别text0是当我的react组件触发其onChange事件时。例如：

如果我的文字是： Hello World

我删除l了它 Hello Word

然后我s在最后添加使它 Hello Words

我想要它，以便我的 OT 文本差异应该具有提交给其他客户的操作（除非这是错误的）

[{p: 9, d: 'l'}, {p: 10, i: 's'}]

使用库或手动生成这些操作的最佳方法是什么？我研究了可能使用diff库，但它没有给出操作发生位置的任何索引，尽管给出了插入和删除操作是什么。

我正在研究离线优先数据库和中央服务器之间的同步过程。举个简单的例子，有项目和部门，一个项目属于一个部门。每个客户端都可以修改任何实体。

我知道对于文本文档，有一些算法/技术可以处理 OT 和 CRDT 等冲突：

• https://en.wikipedia.org/wiki/Operational_transformation
• https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type
• OT 和 CRDT 的区别

但是我想知道您是否可以将这些用于更复杂的结构，例如数据库中的结构。就我而言，让我们保持简单并说您有：

• 项目 - id、名称、department_id
• 部门 - id，名称

单个元素中的“名称”等属性的更改是可管理的（可能使用版本、增量、时间戳）。删除有点小技巧，但您可能会丢弃名称更改，因为元素已被删除。

当有关系时，它就更加棘手了。当一个客户将项目移动到一个部门而另一个客户删除该部门时会发生什么。

在一定程度上，其中一些冲突类似于使用 OT 的文本中可能发生的冲突。有人更改标题，其他人将其删除。或者有人将一个元素添加到项目符号列表中，而其他人将该列表移动到文档的不同部分。

我的问题是，您可以将 OT 或 CRDT 用于关系数据吗？如果可以，您会怎么做？如果没有，是否还有其他类似的算法或技术来处理关系数据中的冲突？

If I read the documentation correctly, one needs to create "JSON0 OT Type" records for any change in the target data-model and send these to the ShareDB backend for transformation and forwarding to other clients. There also seems to be a newer "JSON1 OT Type".

Since I have a libray which already produces JSON-Patch records, I was wondering if it is possible to use this JSON-Patch (CRF-6902) standard to specify the changes to the ShareDB backend.

一般信息
在我自己的操作转换算法的实现上工作。对于那些不知道这是什么的人：当多个用户同时处理同一个文档时，此算法会尝试保留每个用户的意图并确保所有用户最终得到同一个文档。

问题
首先，我需要一种检测文本操作的正确方法。就像插入和删除一样。显然，我需要确切知道发生在哪个位置，以便服务器可以正确转换每个操作以保留其他用户的意图。

到目前为止，我的代码在这方面做得相当不错。但是在选择一个文本范围并用另一个替换它时会遇到麻烦。我依靠这个input事件，它似乎无法同时检测到删除和插入操作。执行此操作时，它会检测对所选文本的删除操作。但它没有检测到从剪贴板粘贴的文本的插入操作。

我的问题是：我该如何解决这个问题？

我的代码（到目前为止）

我目前正在使用 sharedb ( https://share.github.io/sharedb/ ) 和操作转换类型 json0 ( https://github.com/ottypes/json0 )。之后我需要向 JSON 对象添加一个键（路径），它应该通过 sharedb 共享。

例如，应将键“key2”添加到以下 JSON 对象：

不幸的是，根据json0的文档（https://github.com/ottypes/json0），并没有对此进行操作，这让我很惊讶。如何添加将由 sharedb 识别的新密钥？只需在本地添加密钥（路径），sharedb 就无法识别它！

我想构建一个乐观的 ui，我可以在其中执行所有 CRUD 操作。例如，用户可以在其中添加、更新和删除待办事项的待办事项应用程序。

但是，我找不到任何讨论不仅仅是添加项目的资源。例如：

• https://redux-toolkit.js.org/rtk-query/usage/optimistic-updates
• https://www.apollographql.com/docs/react/v2/performance/optimistic-ui/

如果服务器响应有两个以上的状态（例如成功、失败），其他文章甚至建议不要使用乐观更新。

有人可以指出我处理以下一些事情的任何文档、教程或论文吗？或者一个已经成功实施的网站？

排队请求时遇到的一些问题：

1. 回滚

• 用户添加待办事项 1
• POST 请求 1 已发送
• 用户做了很多改变
• 以下http请求排队等待第一个完成
• 请求 1 失败
• 我们回滚到原来的状态

用户丢失了所有更改

2. 浪费的带宽

• 用户添加待办事项 1
• POST 请求 1 已发送
• 用户添加待办事项 2
• POST 请求 2 已排队
• 用户删除待办事项 2
• DELETE 请求 3 已排队
• POST 请求 1 完成
• 发出 POST 请求 2
• 发出删除请求 3

我们不必发送请求 2 和 3

除了对请求进行排队，我还可以对请求进行去抖动并将事务日志或仅当前状态发送到后端。然后后端可以计算出所需的最少数据库更新。

也许已经有一些这些不同的算法？

场景 - 两个人（P1、P2）在 Google Docs 中编辑同一个 word 文档。在他们开始编辑之前，该文档包含一个词——“ADAM”。P1 决定删除第一个字符“A”，P2 决定在现有第一个字符前面添加另一个字符“A”。P1 和 P2 在完全相同的时间执行它们的操作（同时被定义为 Google Docs 服务器识别的时钟的最大精度）。我了解服务器和客户端在应用它们之前都会对其传入操作进行操作转换。
但是 Google Doc 服务器如何决定先执行哪个操作呢？注意 - 我对文档/全局真相的最终状态不感兴趣，但更重要的是，考虑到用户操作的相似时间戳，Google Docs 服务器将首先处理哪个用户的操作。

我正在尝试了解实时协作编辑器的架构和正确的数据库。我找不到关于数据库要求的合适文章或研究论文，所以我在这里发布我的问题。

如果有人可以帮助我理解，那将非常有帮助。或者可以提供文档或博客链接。

免责声明：这不是作业问题:)