有人可以简单解释一下Operational Transform和CRDT之间的主要区别吗？

据我所知,这两种算法都允许数据在分布式系统的不同节点上收敛而不会发生冲突.

在哪个用例中你会使用哪种算法？据我所知,OT主要用于文本,CRDT更通用,可以处理更高级的结构吗？

CRDT比OT更强大吗？

我问这个问题是因为我试图了解如何为HTML文档实现协作编辑器,并且不确定首先查看哪个方向.我看到了ShareJS项目,以及他们尝试在contenteditables元素上的浏览器上支持富文本协作.在ShareJS中我没有看到任何使用CRDT的尝试.

我们也知道Google Docs正在使用OT,它在富文档的实时版本中运行良好.谷歌是否选择使用OT,因为CRDT当时并不为人所知？或者它今天也是一个不错的选择？

我也有兴趣了解其他用例,比如在数据库上使用这些算法.Riak似乎使用CRDT.OT也可用于同步数据库的节点,是Paxos/Zab/Raft的替代品吗？

我一直在编写自己的Javascript编辑器,其功能类似于Google Docs(允许多人同时处理它).有一点我不明白:

假设您已将用户A和用户B直接相互连接,网络延迟为10毫秒.我假设编辑器使用diff系统(据我理解Docs),其中编辑表示为"在索引3处插入'文本',并且差异被加时间戳并强制按时间顺序应用于所有客户端.

让我们从包含文本的文档开始:"xyz123"

用户A在时间戳001ms处在文档的开头键入"abc",而用户B在时间戳005ms处在"xyz"和"123"之间键入"hello".

两个用户都希望结果是:"abcxyzhello123",但考虑到网络延迟:

• 用户B将在时间011ms接收用户A对"在索引0处插入'abc'的编辑.为了保持按时间顺序排列,用户B将在索引3处撤消用户B的插入,在索引0处插入用户A的"abc",然后在索引3处重新插入用户B的插入,该索引现在位于"abc"和"xyz之间" ,"因此给"abchelloxyz123"
• 用户A将在时间015ms接收用户B对"在索引3处插入'hello'的编辑.它会认识到用户B的插入是在用户A之后完成的,只需在索引3处插入"hello"(现在在"abc"和"xyz"之间),给出"abchelloxyz123"

当然," abchello xyz123"与" abc xyz hello 123"不一样

除了字面上为每个角色分配自己的唯一ID之外,我无法想象Google将如何有效地解决这个问题.

我想到的一些可能性:

• 跟踪插入点而不是使用差异发送索引将起作用,但如果用户B在编辑之前移动了1ms的插入点,则会遇到完全相同的问题.
• 您可以让用户B使用他的差异发送一些信息,例如"在'xyz'之后插入'",这样用户A就可以智能地识别出这种情况,但是如果用户A插入文本"xyz？"该怎么办？
• 用户B可以识别出这种情况发生了(当它收到用户A的差异并发现它是冲突时),然后发出一个diff撤消用户B的编辑和一个新的差异,它进一步插入用户B的"你好""abc".length索引对.这个问题是(1)用户A会在文本中看到"跳跃",(2)如果用户A继续编辑,则用户B必须不断修复其差异 - 即使"修复者"差异也会关闭并需要修复,指数增加复杂性.
• 用户B可以发送一个属性,它接收到的最后一个时间戳差异是-005ms或者其他东西,然后A可以识别B不知道它的变化(因为A的差异在001ms)然后进行冲突解决.问题是(1)所有用户的时间戳都会稍微偏离,因为大多数计算机时钟都不准确到ms;(2)如果第三个用户C的用户A延迟25ms,但用户B滞后2ms,用户C在-003ms之间在"x"和"y"之间添加一些文本,然后用户B将用户C的编辑作为参考点,但是用户A不会知道用户C的编辑(以及用户B的参考点)直到22ms.我相信如果您使用通用服务器为所有编辑加时间戳,这可以解决,但这似乎相当复杂.
• 你可以给每个角色一个唯一的ID,然后处理那些ID而不是索引,但这似乎有点过分......

我正在阅读http://www.waveprotocol.org/whitepapers/operational-transform,但很想听到解决这个问题的所有方法.

谷歌波浪协议的常见问题解答说[HTML]"没有理想的属性",并且"HTML使OT(操作变换)变得困难,如果不是不可能的"[1].为什么会这样？如果将HTML简单地视为纯文本然后应用OT,会出现什么问题？

1. http://www.waveprotocol.org/faq#TOC-What-s-the-XML-schema-for-waves-Why

Meteor.js是否支持运营转型？

我正在开发一个与Etherpad有关的项目,我想到了使用Meteor.js(我认为它非常适合这种项目).如果我想让它可扩展,那么操作转换对我的项目非常重要.我目前的知识表明流星不支持开箱即用的操作转换(如果我错了,请纠正我).所以基本上我的问题是如何在meteor.js中实现操作转换？

我尝试使用Neil Fraser的这个库google-diff-match-patch,但在应用补丁时遇到了问题(虽然它很容易在meteor.js之外工作).

那有什么建议吗？

TL; DR:我想破解CKEditor的内部,以便它为富文本(而不是HTML)生成一种替代格式,我希望专家对这个想法的可行性提出意见.

我正在开发一个需要协作富文本编辑器(如Google Docs)的项目,我正在计划使用操作转换库(ShareJS)来实现它.但由于标记嵌套规则,使用HTML很难实现操作转换.例如,一个天真的OT实现很容易产生这种垃圾:

<b>overlapping bold <i>and</b> italic text.</i>

在HTML中表示此类文本的正确方法更像是这样的:

<b>overlapping bold </b>
<b><i>and</i></b>
<i> italic text.</i>

或者更好的是,像这样:

<span class="bold">overlapping bold </span>
<span class="bold italic">and</span>
<span class="italic"> italic text.</span>

但是,为了获得这些类型的表示,OT实现需要知道HTML标记嵌套的所有规则以及如何纠正错误的合并.

我一直在考虑使用替代形式的标记的可能解决方案,该标记根本不强制执行标记嵌套规则.像这样的东西:

BOLD (start: 0, length: 20)
ITALIC (start: 17, length: 16)
TEXT:overlapping bold and italic text.

使用这样的格式,我可以使用普通的OT库来管理正在进行的diff/rebase/merge操作,然后在更新协作两侧的GUI之前将结果文档转换为HTML.

实现这一点的最简单方法是向CKEditor询问其HTML输出,然后在事后重新构建新格式的文档.但OT会要求我在每个按键上执行转换,这似乎有点太重量级了.出于性能原因,我想知道是否有可能覆盖CKEditor中的默认HTML编写器,要求它在遍历DOM时生成备用格式.

你怎么看？

今天尝试了这个实验:为Google文档打开了两个离线编辑器.在其中一个,我加粗了第一个字.在第二个,我删除了它.无论我先打开哪个客户端,该字总是会被删除.

首先,为什么会这样 - 我对运营转型的理解是订购问题？在两个人分别输入"a"和"b"的简单例子中,如果服务器首先接收"a",它将通过将第二个人的"b"事件转换为"通过一个空格"来强制执行"ab"的输出. ,然后添加b"事件,反之亦然.

其次,如果排序无关紧要,是否存在技术原因导致Google Docs选择在删除方面犯错？或者用户的原因很简单？

阅读基座演示文稿(并阅读示例源代码) - 我看到了一个基于变换和操作的模型.

Pedestal是否真的使用类似于Google Wave中使用的操作转换(在这里和这里看)？

我可以为etherpad或etherpad lite中使用的具体ot算法提供提示或来源吗？它是基于学术论文吗？此外,还欢迎提供转换部分的源代码部分的提示或链接.