在线文档多人编辑时的冲突问题

Youtube视频链接

字幕内容机器翻译 </br>

大家好，我的名字是 Martinclapman，我是剑桥大学的研究员，今天我想谈谈我们在无冲突复制数据类型或CRD T 方面的一些工作，所以我将用一个 关于什么是 CR 职责以及它们为何有用的非常简短的介绍，但本次演讲的大部分内容将是关于我们仅在过去一两年内发现的新结果，因此您可能会从我写的这本书中认识我几年前它被称为设计数据密集型应用程序，它是对数据系统架构以及如何为特定应用程序选择数据库的广泛概述，这不是我们今天要讨论的，所以今天我们要讨论的是协作软件 所以在协作软件中，我对此有一个相当广泛的看法适合此类别的软件示例 Google Docs是一个明显的示例，您可以让多个人同时编辑文档创建文本文档或电子表格 与 Office 365 类似的东西figma是支持多图的图形软件示例 -用户实时协作Trello 是项目管理软件的一个例子，其中几个用户可以更新他们的各种任务的状态分配任务和评论等等，所以所有这些都有一个共同点，即用户现在正在更新某种共享状态 我现在将使用这个示例协作文本编辑，稍后还会有一些来自其他类型的应用程序的示例，因此在协作文本编辑中，您最终可能会遇到类似这样的场景 我们正在查看的时间他们有相同的文档，即你好感叹号，然后红色用户出现并更改此文档 向你好世界，所以通过在感叹号之前插入单词 world 并同时在红色用户同时执行此操作时，蓝色用户更改文档以在感叹号后添加笑脸追逐，因此这两个更改同时发生，而彼此不知道，然后稍后随着网络传达这些更改，因此这些用户通过 Internet 或他们正在使用的任何网络进行通信，并且他们应该收敛到相同的状态，所以我们希望最终两个用户在他们的屏幕上都有相同的文档，并且该文档反映了所有 在所做的更改中，在这种情况下，合并的结果是非常合理的，我们期望在感叹号之前的世界和感叹号之后的笑脸是非常合理的，因此有大致两个算法家族来实现这一点 一种协作文本编辑一种是操作转换或OT，这是一种经典的 多用户协作编辑已经存在了很长时间，例如被Google Docs 使用，然后有一个称为 CID T 的新算法系列，这是我正在研究的，它采用了一些不同的方法来解决一个类似的问题，我们将在一分钟内比较这两个，所以我将首先简要总结运营转型是如何工作的，因为这可以作为 CID T 的比较点，所以对于运营转型，我们必须首先描述变化是如何进行的 对文档进行了更改，因此当用户更改他们插入的文档或删除文档中某个位置的字符时，我们可以通过使用索引来描述这些插入和删除发生的位置，因此我们只需将第一个索引编号为 第一个字符和要老化的文件第二个字符对不起第一个字符为 0 第二个字符为 1 依此类推，所以现在你可以有两个用途 rs更新他们的文档，在左侧，用户通过在位置 3 添加第二个 L 来更改文档 HDL 哦，在右侧，我们让用户紫色用户在字母后添加感叹号，所以现在之后 这两个变化已经发生了这些变化需要通过网络进行沟通，以便一个用户发现另一个用户所做的变化，所以从这里的左侧，我们在位置 3 或位置插入了字母 L本文档中的索引 3，我们在右侧的索引 4 处插入了感叹号，所以首先让我们从左侧插入并将其移到右侧，如果有服务器 例如，将这些消息从一个用户转发到另一个用户，服务器可以将这个在位置 3 处的插入 L操作转发到右侧，在右侧，我们在位置 3 处插入 L，我们最终得到 h 你好，有两个 L 和一个感叹号，就像我们现在想要的那样如果我们朝另一个方向走会发生什么，所以将感叹号插入从右侧到左侧注意，如果我们只是转发此操作插入感叹号 在位置 4，如果我们只是简单地转发该未更改的内容，那么左侧的用户最终会看到文档说地狱感叹号 O，这不是我们想要的，我们希望两个用户最终都处于相同的状态，并且该股权反映用户所写内容的意图，因此必须在第 4 位插入插入感叹号需要在第 5 位插入，原因是之前在第 3 位同时插入了另一个插入的位置，因此位置 4 的插入需要转换为位置 5，因为前面同时插入了 L，所以这就是算法 i 的原因 称为操作转换，我们必须进行这些插入和删除操作，并且根据同时发生的其他操作，我们必须转换索引或这些操作发生的位置，因此该算法确实有效，但它需要一个非常特殊的假设和基本 大多数操作转换系统中的假设是所有通信都通过单个中央服务器进行，因此在 Google Docs 的情况下，服务器由 Google 提供，并且服务器是您知道的，它通过对所有 操作和操作转换的假设是，因为我们有这个中央服务器需要对所有操作进行排序，所以系统中不能有任何其他通信通道，所以即使两个正在协作的用户实际上坐在同一个房间里并且 他们可能只是使用本地 Wi-Fi 甚至蓝牙 不允许使用该本地通信通道在两个设备之间传达他们的更改，因为这会破坏操作转换算法所做的假设，因此Ooty 要求所有通信都由中央服务器进行，即使该服务器位于不同的 大陆，即使两个加热器实际上坐在同一个房间里，所以这就是Co 神在 CR DTS 中的不同之处，它允许这种多用户协作，而不会对网络拓扑做任何假设，所以它不假设任何关于服务器或使用何种网络任何类型的通信通道都可用于将操作或更新从一个用户传递到另一个用户，而我们对 ot 和 Ciardi T 的主要正确性标准就是我们所说的收敛，所以我们 要求是，只要任何两个用户看到相同的一组操作，那么这些用户必须在同一个 st 吃了，即使用户实际上以不同的顺序看到操作也会发生这种情况，所以我们在 CR DT 中所做的是我们使操作可交换，这意味着即使它们围绕它们的顺序交换，也会围绕最终结果进行交换 相同，这就是我们实现融合的方式，它只是确保在每个人都进行通信之后，每个人的屏幕上都有相同的文档，这是有道理的在用户之间，那会很糟糕，因此收敛显然是任何此类协作软件的最低要求，但正如我们将在本次演讲中看到的那样，收敛本身是不够的，因为收敛并没有说明最终状态是什么 大约在节点通信之后，最终合并状态实际上是我们想要的状态，这有点困难 之所以要定义，是因为什么状态是可取的或不可取的，这实际上是人类判断的问题，它是人类的什么，我们对软件的期望是什么，软件应该如何运行，不幸的是，这些 IDI 算法中有几种用于协作编辑 有时会出现一些并非真正可取的行为，在某些方面表现得很奇怪，这是我们人类无法预料到的，我在从事 Co DTS 工作几年后得出的结论是，基本上这些问题非常困难，而且是 C le 的简单版本 T 的实现非常容易实现，但实际上很难以真正满足用户期望的方式正确实现，因此 C 的怪异很容易实现不好，我们将在本次演讲中探讨如何实现 这些奇怪的东西实际上以我们想要的方式表现，所以今天我想看看这四个主题这些都是C 的领域 奇怪在某种程度上是困难的，对于其中大多数我们也有解决方案，所以我将一个一个地讨论这些问题，我想开始的一个是交错，所以交错是一个可能发生的问题 在协作文本编辑器中，如果有几个人在文档中的同一位置插入文本，现在我要解释为什么会发生这种交错，我将首先介绍一下 C 文本编辑的奇怪之处如何工作和我将从一个例子开始，正如我之前所说的，当我们查看操作格式时，我们只需通过从文档开头开始计数来确定我们想要通过索引插入或删除字符的位置，并且需要转换这些索引的问题，因此请参阅 Aditi 避免需要这种操作转换，而是采用不同的方法，而不是查看我们的 DTS 为每个文档中的单个字符并且该唯一标识符保持稳定即使在文档中的其他位置添加和删除内容也保持不变，因此每个字符都保留其自己的永久唯一标识符，并且有几种可能的方式来构建这样的标识我们一种方式是我们可以 选择一个介于 0 和 1 之间的数字，因此它是某种小数，一个有理数，例如，我们说 0 是文档的开头 1 是文档的结尾，对于文本文档中某处的每个字符的每个位置，我们 只会选择一个位于该数字行内的数字，所以在我们的 HDL 示例中，我们可以说好吧，让我们将数字零点二分配给 H，数字零点四分配给空气II，数字零点六分配给 Eldar数字 0 点 8 到 O ，因此我们将字符间隔为 0 到 1 的数字间隔，现在当我们想要插入一个 seco 第一个字母 L 和一个感叹号，我们在间隔之间选择数字，所以我们想在第一个 L 和 O 之间插入第二个 L，所以在零点六和零点八之间好吧，让我们选择零点七作为中点和 同样对于感叹号，我们会选择一个介于 0 点 8 和 1 点 O 之间的数字，例如猪 0 点 9，所以这是一个足够简单的方案，我们可以使用它以非常简单的方式实现 CR DT 所以我们现在可以做的是我们可以将我们的文本文档视为一组元组，这些三元组中的每一个都包含特定位置的字符，它包含告诉我们去向的数值，然后最后在这里帮助 我放入这些三元组只是引用创建此特定插入操作的节点 ID 的一种方式，因此这只是系统中特定用户或特定节点的某种唯一标识符以及我们拥有的原因如果两个不同的节点选择相同的数字，那么我们可以根据节点 ID 定义这些字符的顺序作为决胜局，所以我们现在只有这组三元组代表文档，我们可以进行编辑，我们可以插入只需为它们选择数字然后计算集合 Union 即可将新字符放入此文本文档中，我们会得到一个包含新元组的集合，我们可以通过仅根据它们的数字对这些元组进行排序来准确重建文档的状态 在节点 ID 上，然后我们得到文本文档，一些奇怪的文本基本上采用了这种方法，它们实际上并不使用0 到 1 之间的数字，而是使用诸如穿过树的路径之类的东西，但有效的想法是它仍然相同它们实际上只是在数轴上选择位置，因此当我们以这种方式实现 C 或 D T 时，我们可能会有一些不幸的行为，这是一个例子在某些文本编辑 CR 职责中可能发生的行为，所以这里我们在左侧有两个用户，用户 1 从文本文档开始说 hello 感叹号，用户 1在 hello 和感叹号之间插入单词 Alice，同时在 右侧用户 2在 hello 和感叹号之间插入单词 charlie现在两个用户进行交流，他们合并了他们的更改，我们得到了最后得到的是 hello，然后是一些奇怪的字母混乱，我们可以 ‘不读这甚至意味着什么这是怎么发生的我们从爱丽丝和查理开始，我们最终得到了一些巨大的字母，这里发生了什么，所以我们从一个文本文档开始，每个字符都有一个数字 在数字行上，你好哦，哦有 0.64，感叹我们的卡是 0.95，然后插入爱丽丝或空间爱丽丝只需在间隔 zer 之间选择一些数字 o 点 6 点4 点 0 点 9 点 5 点，同样，查理插入在该区间内独立选择了一些数字，所以很多 CRT T 对这种事情所做的是他们实际上将数字随机化一点，因为这减少了两个不同的节点将选择完全相同的位置 为特定字符选择完全相同的数字，从而减少冲突的风险，因此现在插入的结果是我们已经从代码中的 Alice 那里获取了所有数字这里用红色编码，插入蓝色的查理字母，我们只是根据数字对它们进行排序，不幸的是，结果是我们现在已经交错了来自两个不同用户的这两个字符序列和 不幸的是，结果是一团糟 更糟糕的是，如果两个用户所做的同时将整个段落或整个部分插入到他们的文本文档中，如果您有一个段落或部分中的字符基本上是随机交错的，那么您将无法 要再使用该文本，您只需要删除它并再次重写它，用户不会对此感到高兴，不幸的是，这种行为确实发生在真正的怪事中，我们已经检查了许多不同的 RC OTT算法 文本编辑，我们至少在称为 blue gute 和 LS EQ 的算法中已经证明了这个问题，所以在这些算法中的这些问题中，不幸的是，这个交错问题非常深入地融入了算法构建的基本方式中，我看不到任何方式修复这个问题 修复算法中的这个错误，因为这些数字的分配方式或树所在的服务员路径这个交错的想法只是非常固有地融入了这些算法的工作方式，所以其他算法我们没有发现这个问题，所以在树文档和木头中，例如我们没有发现这个交错问题，这并不能完全保证它永远不会发生，但我们认为它不会发生，因此在某种程度上这些算法是安全的，但不幸的是，这两种算法也是效率最低的算法，例如设计 L seq 算法的全部原因是因为设计者想要一个 CLD T，它比树文档和路由更有效，因为树文档很不幸地为他们的标识符占用了大量空间，所以不幸的是，这种性能优化现在在算法中引入了不良行为，我认为这使得 像 LSEQ 和 la cude 这样的算法基本上不适合在许多文本编辑应用程序中使用，而且还有一个 co 的规范llaborative text editing called astrong here 由 Atia和其他人于 2016 年发布，该规范还允许将交错作为一种民谣行为，尽管我们有一篇论文在其中修复了该规范以排除这种交错行为，最终我们的 GA 是一个有趣的所以我们的 GA 是另一种文本编辑 CR DT算法，它不完全有同样的交错问题它有一点交错问题，所以我会简单地提一下，因为这是一个有趣的案例研究，所以在我们的 GA 中，交错问题可能发生的情况是这样的，所以在这个例子中，在左侧，我们有一个用户，他从文档开始说你好，然后用户在你好和感叹号之间插入单词前导，然后用户向后移动光标 在单词 hello 之后再次键入单词 Dear 所以我们在这里输入单词read 将光标移回然后键入单词 Dear on右侧我们有用户 2，他刚刚在 hello 和感叹号之间输入了 Alice 这个词，现在在 RTA 中可能发生的事情是Alice 可以在单词 Dear 和单词 reader 之间交错，所以即使文本 Dear reader 是由一个用户输入的，而 Alice 是由另一个用户输入的，我们最终可能会将两者混为一谈，因此我们不会像处理其他一些 Co 职责那样逐个字符地交错 但是我们仍然有能力将文本插入到不同用户插入的中间，发生这种情况的原因是RTA 使用的数据结构看起来有点像这样，所以它是一种具有非常深子的树数据结构 树和一个小的分支因子通常在这里发生的是每个节点行业是一个插入的字符，每个节点的父节点是插入时直接前导字符的字符，所以 我们从根处的一个特殊节点开始，它是文档的开头，然后当用户键入h-e-l-l-o 感叹号时，每个字母都以刚刚键入的字符作为其前身，所以你最终得到了这个链 幸运的是，h-e-l-l-o就像一个链表，几乎每个字符的父级只是它在这棵树中的直接前任，然后用户来将他们的光标定位在 hello 和感叹号之间，一个类型的空格阅读器另一个类型的空格 Alice 和第一个用户 键入的阅读器将光标移回并键入亲爱的，因此您可以看到每次移动光标时都会在此处形成一个新的子树，否则此文档中字符的顺序是深度优先遍历树，所以我们可以看到在这里发生的交错中你好亲爱的爱丽丝读者发生了什么是我们访问你好，然后首先访问亲爱的子树t 然后是 Allis 子树，然后是 Winter 子树，然后是感叹号，我们访问这些子树的顺序是由附加到每个节点行业的时间戳定义的，所以如果在这种情况下我们有几个兄弟姐妹，那么我们自己的 ode 有几个孩子，然后我们按时间戳的降序访问这些孩子，因为在并发编辑情况下时间戳是不可预测的，您最终可能会得到这三个可能的结果作为合并结果，因此它不像逐个字符交错那样糟糕 你和其他人在一起我应该准确地说，可以逐个字符地离开 RG 发生这种情况的情况是，如果用户将他们的文档从前输入，那么如果用户从文档末尾开始，并且首先键入最后一个字母然后将光标移回开头键入倒数第二个字母移动到光标类型倒数第三个字母依此类推并键入 en如果他们这样做，那么他们实际上会在 RGA 中逐个字符地交错，因为在这种情况下，在这棵树中，我们所有的角色都是兄弟姐妹，都会有根节点的子节点，而在我们的 如果排序只是由时间戳再次定义，但幸运的是在实践中人们往往不会真正键入这样的文档，并且人们倾向于从头到尾以合理的线性方式键入文档，当然有时人们会回溯一点删除一点副本并粘贴一些部分等等，但由于一般规则键入仍然以一种方式从头到尾发生，因此，交错问题在我们的 GA 中实际上并不像在其他算法中那样糟糕，但我们仍然可以说 我们想要严格，我们想要根本不允许任何交错，我们确实设计了一个算法，所以对于我们的 GA，我们能够找到一个修正对算法进行修改，这样无论光标如何移动，这种并发插入的交错都不会发生 我们在 2019 年发表的名为interleaving anomalies incollaborativetext editors 在本文中准确描述了该算法，所以让我们继续下一个主题我们今天的下一个主题是重新排序列表项，即我们有一个列表项，我们想要移动 一个项目从列表中的一个位置到另一个位置，例如，我们可能想要的示例应用程序是一个待办事项列表，因此在待办事项列表中，您通常可以将项目拖放到您想要的任何顺序中，并且 所以这里发生的例子是你有一个待办事项列表，首先是牛奶，其次是给植物浇水，第三次打电话给Joe，用户正在拖放电话 Joe 项目并将其移动到 列表的顶部，所以它现在位于第一个位置，所以我们如何做到这一点我们可以使用我们之前讨论过的任何 CEO 职责来表示列表，所以所有 CEO的文本编辑职责也是共同职责 列表，因此我们可以使用它们来表示这个有序的项目列表，但是所有这些 CR 职责实际上并不支持移动操作，它们所拥有的只是插入和删除项目的操作，但现在没有移动操作，你可能认为没问题 还不错，因为我们总是可以通过从旧位置删除项目并将其插入新位置来实现移动，这很有效，除非有几个人当前可以移动同一个项目，所以在这个例子中，副本 a 和副本 B 都将电话 Joe 移到列表的顶部，所以如果我们通过删除和重新插入来实现这个移动会发生什么，他们都从位置 3 删除电话 Joe，所以它肯定会从位置消失 3 然后他们都在位置 1 插入电话 Joe 但现在的结果是这两个插入位置 1 他们都发生了所以我们最终在位置 1 和 2 有两个电话乔副本所以我们想要的这个项目只 move在此过程中意外地被重复了，这确实不是用户希望我考虑做列表应用程序的那种行为，因为他们重新排序了列表中的某些项目并不意味着他们肯定想要这些项目的副本看起来很好我们实际上想要什么行为 我们想要什么行为 让我们看一个类似的例子，在这种情况下，我们还有两个复制品正在移动电话乔，但是我们已经将该项目移动到不同的位置，所以复制品 a 将电话 Joe 移动到列表的顶部，而副本B 将电话 Joe 移动到第二个位置，所以在购买牛奶之后，在这种情况下理想的行为是什么，我们可以说现在我们的电话 Joesho 会出现在买牛奶之前和买牛奶之后的两个位置，但是我们又出现了重复，我们不希望重复，所以我们真正想要的是电话乔出现在两个位置之一，我想这可能会显示警告说 嘿，用奇数作为警告，我们选择了两个位置之一，或者只选择两个位置之一并忘记有两个不同的列表位置，所以我只想说现在让我们去 任意但确定地选择两个并发位置中的一个作为获胜者，因此在此示例中，我们将电话乔作为获胜者排在列表的顶部，因此从第一个用户的角度来看，没有任何变化，但从第二个用户的角度来看，他们从 Joe 移动到位置二，然后电话Joe 随后移动到位置一，现在让我们想想这里发生了什么，所以我们有两个同时写入的值 s 对于两个不同的职位，我们希望确定性但任意但确定性地选择其中一个作为结果作为结果，如果你研究过现有的 CEO 职责，这对你来说可能看起来很熟悉，因为这正是在 最后一个写入器在最后一个写入器中用红色缠绕寄存器，除了一个寄存器，它是一个有效的变量，可以同时由不同的用户分配一个值，如果我们有这些并发分配，每个人都合并后的最终结果他们的状态是我们选择了其中一个已被写入的值作为获胜者，我们丢弃了任何其他同时写入的值，因此您可以将此处视为列表项电话乔的位置，因为有最后一个写入器获胜寄存器 它的语义是第一个用户将电话乔的位置分配给列表的头部，另一个用户将蕨类乔的位置分配给牛奶和 d 然后当两个用户交流时，最终结果是获胜者是这两个值之一，要么是列表的头部，要么是牛奶之后，所以让我们让它更正式一点，如果我们想在这里实现它，我们需要需要最后一次写入wins register 好的，其次，我们需要某种模棱两可的方式来引用列表中的位置，但是如果您考虑一下我们刚才在讨论文本文档中字符的唯一标识符时所做的事情 列出了奇怪的东西和这些文本看到的奇怪东西已经在为我们提供了一种稳定且独特的方式来引用列表中的特定位置，因此我们可以只使用这些现有算法之一并使用其唯一标识符来引用列表元素特定项目的位置无止境现在不同的职责有不同的方式来构建这些标识符，就像我们看到的那样，树码头使用通过二叉树日志的路径哦选择了通过具有更高分支因子的树的路径RGA 和因果树使用某种时间戳，但基本思想仍然相同，我们为列表中的特定位置获取唯一标识符，因此我们可以获取这些标识符并将它们作为我们最后一个层中的值第二个是我们现在需要的如果我们有几个列表项，我们现在需要一个单独的寄存器来为每个列表项保存该特定列表项的值，所以我们可以构造一个我们可以的集合例如，使用双组集合 CR DT并且该集合的内容将是我们列表中的所有项目，因此我们将说列表中的每个项目将是由一个值组成的对 例如，这就像待办事项列表项上的文本，他们最后一个写入器将包含该特定列表项的位置的寄存器，所以现在我们可以通过将新项目添加到我们可以移动的添加赢集来将它们添加到列表中从一个位置 t o 另一个通过更新他们最后一个写入器的值来特别是获胜寄存器我们使用列表 C RDT 为我们想要移动特定项目的位置创建一个位置标识符，然后我们获取该位置标识符并将其用作值 最后一次写入获胜寄存器，所以在这里我们构建了一个新的 C R DT操作现在只需使用三个现有 CRD T 即可对列表进行移动操作这一系列不同的列表中的任何一个看看我们的职责加上一个广告获胜集加上最后一个写入者获胜 注册，我们已经构建了一个新的操作，因为我们刚刚组合了这些现有的 C 我们的职责，我们知道最终结果也将是一个 CLE T，所以这非常好，它允许我们执行这些原子移动 一次一个列表项现在，如果我们想一次从多个项目移动，事情会变得有点困难，所以在待办事项列表中，你真的只需要一次移动一个项目，因为它们通常 拖放列表 让您在用户界面中一次选择一个项目，所以这不是真正的问题，但在文本编辑中，您可以想象会出现其他情况，因此在此示例中，我们这次有一个待办事项列表，表示为纯文本 作为项目符号点列表工资项目符号点以项目符号字符开头并以换行符结尾，所以这里复制品 B 正在拿项目牛奶，并希望将其移动到培根前面，这意味着采取所有角色 一个字符项目符号点空间 m IL k 换行 整个字符范围被移动了整个范围以在培根前面同时发生另一个用户正在更新牛奶项目以说豆奶，所以他们通过删除来做到这一点大写 M 并插入文本 soy 和小写 M 好，所以我们期望在这里发生什么所以首先，抱歉从牛奶更改为豆奶的豆奶生效，并且从牛奶移动到前面培根生效，所以我们期望这里的预期结果是我们在培根前面的列表中首先有豆浆，这意味着两个更改已经干净地合并在一起这就是我们想要发生的事情，不幸的是这不是实际发生的事情 因此，如果我们查看我们刚刚构建的用于移动单个列表项的算法，并且如果我们只是根据该算法单独移动每个字符，我们得到的最终结果就是这里，所以我们最终得到牛奶正确地移动到前面 培根完全按照我们的意愿发生，但是从牛奶到豆奶的变化仍然附着在牛奶以前的旧位置，而不是牛奶现在移动到的新位置，所以现在的最终结果是列表显示牛奶新 line bacon new line soy M而那个 soy M 只是站在那里没有任何上下文，因为它的上下文在此期间已被移走，这是一个我不知道该怎么做的问题暂时我已经花了一段时间思考它提出了几个不起作用的半解决方案其他几个人也在考虑它所以如果你对此感兴趣 如果您设法弄清楚，请随意考虑并发布结果，所以这是在列表中移动项目的问题，所以我们已经弄清楚如何一次移动单个列表项目，但这些范围是移动它们的字符 以一种表现良好的方式仍然是一个开放的挑战让我们继续第 3 点，这又是关于移动但现在我们将在树中移动子树而不是移动列表中的元素所以让我们再看一个例子让我们说 我们有一个可以设置文件系统的树结构，就像在列表中移动元素的情况一样，我们可以考虑如果树中的同一个节点同时被两个不同的用户移动到两个不同的位置会发生什么，所以你可以 看到这里我们开始树在两个副本上，其中 A B 和 C是根的子节点，在副本a 上，我们将采用该节点 a并将其移动为 B 的子节点，而在副本 2 上，我们将采用相同的节点 a 并将其移动为 C 的子节点，因此现在 a 已移动到两个不同副本上的两个不同位置，在这种情况下，我们期望结果是什么，这类似于在列表中移动元素的情况所以一个选择是复制它，所以我们可以拥有的是，我们有一个作为 B 的孩子出现，也作为 C 的孩子出现，这意味着进一步的任何孩子也必须被复制，这就是 您在标有 a 的此框中到达此处，即您有 a子树，其中有 1 a 2 a 3 子树，然后是整个子树的另一个完整副本，所以这与列表的情况一样，我认为重复节点 在并发新闻上不是一个好的行为，所以我们不想要那么好的另一个 r 选项是让 a实际上作为 B 和 C 的共同子节点共享，这可行，但它不再是树，所以如果我们期望我们的数据结构是树而不是 dag 或其他类型的图，那么 这不是一个可接受的结果，因为这里 a 有两个父节点，并且在树中没有节点有两个父节点，因此留下 C 和 D 作为 post结果所看到的只是我们将副本一个操作作为我们的结果并忽略了由 副本二或反之亦然，我们可以选择副本二作为赢家并忽略副本一所做的移动，因此在这种情况下，a 管道出现为 B 的子项或 a 出现为 C 的子项，但并非两者都像 在列表中移动原子的情况我们所拥有的是一种最后的作家风行为，我认为现在在树中出现额外的复杂性是合理的，所以树肯定比列表更难，所以另一个棘手的例子可以发生在树上可以用你的文件系统来说明，所以如果你愿意，你可以在你的计算机上尝试这个，只需创建一个名为 a 的目录，然后在名为 B 的内部创建一个子目录，然后尝试将 a 移动到 B 中，因此将 a 移动为 a 的子目录斜线 B 这可能听起来很奇怪你在这里所做的实际上是试图将一个目录移动到自身中我不知道你是否曾经尝试过这个我确实在 Mac OS 上尝试过我从 shell 中得到这个响应说 无效的论点我不允许拍这部电影，这是有道理的，因为如果我们确实执行了移动，将目录移动到自身中，我们就会创建一个循环，然后我们的数据结构将不再是 树这将是某种带有循环的图，这对于文件系统来说会非常混乱，因此如果我们构建看到奇怪的树或树，那么如果我们允许移动子树，我们也可以防止这种循环并防止 有人移动物体insi de 本身，但不幸的是，对于 C 的怪异，我们有并发更改的额外复杂性，因此请考虑这个示例，我们在副本 1 上的两个副本上再次使用同一棵树开始，我们采用节点，抱歉，我们采用节点 B并将其移动到 成为 a 的孩子，所以这里 B显示为一段时间的孩子 C作为 a 的现有孩子在副本 2 上统治我们从同一棵树开始，在这种情况下，我们移动 a 我们移动 a成为 B 的孩子，所以 我们最终将 a 作为B 的子节点，将 C 作为 a 的子节点，如果我们合并这两个，现在会发生什么，所以我们必须在这里移动操作，每个操作本身都很好，移动没有错 B 成为 a 的孩子，将 a移动到 B 的试验并没有错，但是如果我们将这两者结合起来，我们最终会遇到与我们刚刚遇到的完全相同的问题，我们实际上是一个目录被移动到自身内部并且 所以如果我们对这个算法不小心，我们最终会得到一个 和 B 在这种循环中与树的根断开连接，这又不再是一棵树，它是某种更通用的图形数据结构，所以如果我们想保留爷爷树的因素，我们不希望这样和以前一样的工作选项是我们可以复制节点，所以我们可以说我们将 B移动为 a 的子节点，并将 a 移动为 B 的子节点，因此我们有两个选项B 作为 a 的子节点和 a 作为 a这本书的孩子简单地存在于我们树的目录图中，所以我们必须再次复制这些孩子的任何孩子，和以前一样，我认为重复是错误的做法，所以看起来和以前一样，我们真正 want is a last writer在这里赢得语义，这里的这个选项是将 B 移动到 a 并忽略另一个移动的结果，或者我们选择将 a 移动到 B并忽略另一个移动的结果，所以在这种情况下，我们要选择 两个冲突的操作之一，我们想要只需忽略另一个我们必须确保所有副本最终选择与获胜者相同的操作并忽略相同的其他操作，因为当然否则它们不会收敛，那么它就不是 CR DT 那么我们该怎么做 现在实际上实现了这一点，我们希望确保所有这些冲突的操作都被很好地挑选出来我不知道我们可以尝试一些现有的软件我用谷歌驱动器尝试过这个，我在这里收到了这个很棒的错误消息我试过了 只是有两个目录 a和 B 将 a 移动到 B 并将我同时移动到两台不同的计算机上会发生什么我得到某种内部未知错误再试一次但这个错误永远不会消失它只是一直坐下来循环尝试同步是的 所以谷歌云端硬盘也没有解决这个问题好吧我想我们必须自己考虑一下所以我们解决这个问题的方法是考虑得到的操作顺序 应用于每个副本并在每个操作上都有一个时间戳，我们将像往常一样假设一些全局唯一的时间戳，因此您可以使用 Lamport 时间戳，例如工作正常，其中一些操作将被移动 操作，有些可能是其他类型的操作，这里我们在副本一上将 a移到 B 中，将 B 移到副本二上的 a 中，正如我之前所说的，这些操作中的每一个本身都是安全且可以执行的 需要确保我们检测到两个操作相互冲突的情况，因为执行这两个操作会创建一个循环，所以我们必须确保无论我们做什么，我们现在都不会创建一个循环什么可以现在发生如果这两个副本合并有操作序列很好我们从两个副本中获取操作的联合我们可以将它们按时间顺序排列现在如果我们说操作得到执行 d 完全按照时间戳递增的顺序，那么第一次移动就可以了，因为此时还没有发生任何不好的事情，但是当我们进行第二次移动操作时，移动是不安全的，所以如果我们想确保没有循环 在我们的树中，然后我们必须跳过该操作，假装它没有发生这是我们的棘手问题，因为副本 2 已经执行了此操作，因此副本 2将以某种方式出售必须撤消此操作，它确实已执行以确保 它再次与副本 1 收敛，因此我们要使用的基本原则是采用这些操作序列，其中我们对每个操作都有一个时间戳，我们将合并它们，以便我们得到一个单一的操作序列时间戳顺序，例如，在副本 1 上，我们在副本 2 上有时间戳 1 3 4 和5，我们在副本 2 上有时间戳 2 6 7和 8，因此如果我们想象您的副本 1并且您已经执行了 1 3 4 5 和 现在你收到了 带有时间戳的操作 -来自副本 - 您需要做的是您需要获取此时间戳 -操作并将其插入到您已执行的操作序列中较早的某个位置，但您知道时间已经过去了 点，我们确实执行了带有时间戳 3 4 和 5 的操作，所以我们如何处理好这个我们可以采取一种相当简单的方法，即撤消和重做操作，这正是我们在算法中所做的，所以也就是说，如果您是这里想要应用操作的复制品 - 并且带有时间戳 - 您已经获得了您在 xx 1 3 4 & 5 处执行的操作日志，我们首先要撤消操作，直到我们 回到这一点，直到我们撤消所有时间戳大于新操作的操作，所以我们要撤消 5 我们要撤消我们现在要撤消的移动 3 我们只剩下 off 1 所以现在我们可以在此之上申请 带有时间戳- 现在我们执行我们已经撤消的三个操作，最终结果是现在我们有这个我们要处理的操作日志已插入正确的位置，如果我们继续执行这种每个副本上的逻辑，那么这实际上将确保所有副本最终以相同的操作退出 在很早的顺序中，我们必须执行大量撤消操作以执行该操作，然后执行大量减少操作以重播所有已发生的操作，因此您可能想知道这的性能是什么而不是性能 糟糕的是，我们做了一些性能实验，没关系，当然，执行所有这些撤消和重做的顺序肯定是有成本的，你可以在这里看到，所以我们建立了一个系统，在三个不同的C ontinents，因此这些不同的副本之间存在超过一百毫秒的往返时间延迟，然后我们才开始以高速率生成移动操作，并且该系统中移动操作的速率越高，撤消和重做这些操作的需求就越多完成，因此执行每个单独的操作变得越慢，我们能够让这个系统达到每秒至少 600 次操作，你知道它在大数据规模上并不庞大，但另一方面，就像一个 单个用户更新他们的文件系统 我认为我认为单个用户不会在他们自己的本地文件系统上每秒执行超过 600 次移动操作，因此对于许多协作软件来说，实际上这种性能非常好，我们不 不得不担心太多，所以我将更多地解释一下这个算法是如何根据我们使用的数据结构工作的，所以我们必须首先找到一种描述方式 我们要执行的移动操作我们要说移动操作是一个结构，这里首先像我之前所说的那样具有以下字段，并且编织操作具有全局唯一的时间戳，例如LAN 端口时间戳，然后是 移动操作必须有一个子节点，它是我们正在移动的树中的节点，而父节点是树中该子节点的新位置，现在我们不会在此操作中注意什么这个孩子的老父母就是这样，这就像我们可以称之为偷窃行动，我们只是要把孩子从树中的任何地方带走，然后把它移到这里成为这个新父母的父母，然后我们可以进一步 有一些与操作相关联的元数据，例如在文件系统中，您在目录中的一个文件中拥有一个文件，并且该文件在目录中有一个名称，因此可以是与特定文件中的特定文件相关联的元数据目录，然后我们必须构建这个操作日志以执行撤消和重做，为了执行此撤消，我们需要将一些额外的数据与每个条目和日志相关联，因此这里的每个条目都有几个字段直接来自移动操作，因此时间戳来自移动操作，新父级新元数据和子级直接来自移动操作，因此除了这些之外，我们现在还召回了旧的父级和旧的 元数据，所以这是我们执行此移动之前子项的父项，并且是它的旧文件名，例如，如果我们使用元数据作为文件名，所以现在这允许我们执行撤消，因为我们在 为了撤消这个操作只是将孩子的父母和元数据设置回它的旧父母和它的旧元数据，并且给定这个移动操作的日志条目的日志，我们现在可以构造树的当前状态树只是当前元数据的三元组和试验三元组，只要孩子是树中的父母或父母，所以我们现在可以在这里定义这个祖先关系，所以如果 a 是直接父母，我们说 a 是 B 的祖先树中存在逗号 M逗号 B 三元组存在于树中，或者如果存在某个树节点 C 使得a 是 C 的父节点，C 是我的祖先，好吧，所以这仅定义了父节点的传递闭包- 子关系，因此给定祖先的定义，现在我们可以定义移动操作的安全性，因此对于移动操作，如果我们要执行此移动，我们查看正在移动的子节点和父节点孩子被移动到的目的地，如果孩子当前已经是它被移动到的目的地的祖先，那么这将是不安全的，我们将创建一个循环，因此如果孩子和父母实际上是，我们不做类似的事情 这 同样的节点也将是不安全的，所以我们什么也不做，但在所有其他情况下都很好，所以我们可以通过从树中删除节点来更新树C 的现有位置，这正是我所说的我们窃取子节点 从它当前在树中的任何位置获取迈阿密的任何峰值，然后我们将这个新的父元数据子关系添加到树中，这定义了树的更新状态，因此在这里给出这个函数来执行移动操作并给出我之前解释过的撤消/重做过程我们现在有一个算法可以在树 C R DT 上安全地执行移动操作，并且我们证明了关于这个算法的几个定理，所以特别是我们证明了这个算法确实保留了树结构以便保留树 我们需要的结构是每个节点都有一个唯一的父节点，并且树不包含循环，这是树的定义，因此我们证明这些东西适用于执行数据结构的任何操作序列仍然是一棵树，然后显然我们必须证明它是一个 CR DT，这意味着它会收敛，因此如果一个操作序列是 其他操作序列然后应用这些操作序列导致相同的状态，换句话说，操作是可交换的，所以这个算法有效，我们已经实现并证明了这些关于执行移动歌剧Shinzon 树的属性，可以从移动子树继续 NCR 职责让我们谈谈 关于效率和使 co DTS 更高效，因此许多 CDT 算法尤其是文本编辑 CR DTS 出现的一个特殊问题是 CR DT 元数据所产生的元数据开销，所以如果您考虑一个文本文档，我们所说的是我们 给每一个字符和一个文本文档一个唯一的标识符，所以你最终得到的是每个字符英文文本将是ASCII 字符的一口，该字符的 unicode utf-8编码，但是你有额外的元数据，所以你可能有例如一些穿过树的路径，它可能需要几十个字节来编码，然后你可能有插入特定字符的节点的一些标识符，如果这是一个UID，如果你用十六进制编码它，它将至少是另外 16 个字节，它会像 36 个字节或类似的东西，所以很快你就会得到这个真的 不成比例的情况，您需要一个字节用于您想要的实际数据，以及类似一百字节的元数据，甚至超过 CR DT 元数据，以便使 CDT 工作，这不是一个特别好的情况所以我现在想谈的是我们一直在做的一些工作，作为 Auto merge 项目的一部分，这是一个 CR DT 实现，我致力于降低元数据开销，通过使用一些精心设计的算法和数据结构，我们已经取得了一些非常好的成功结果，所以让我从我们这里的结果开始，所以旧版本的 Otto Emerge 使用 JSON编码来编码所有的元数据并通过网络发送并将其写入磁盘，这种 JSON编码非常冗长，因此我们在这里所做的只是作为一个特定案例研究的示例，该案例研究是论文乳胶源的编辑历史为了生成这个编辑历史，我和一位同事实际上是用一个本土的文本编辑器写了这篇论文，所以我们能够捕捉到写这篇论文的每一个按键，所以最终的文件是大约 100 KB 的纯文本，所以这个 只是包含乳胶标记的 ASCII 文本，我们捕获了超过 300,000 次操作，这是编辑历史的 300,000 次单独击键，因此包括所有为创建此文档而输入的单个字符所有为添加或删除的内容或已更正的拼写错误等而删除的所有字符，我们还记录了所有光标移动，因此每次光标 被从一个位置和文档移动到另一个也被记录的位置，因此，如果您获取大约30 万次更改的历史记录并将其编码为当前或以这种 JSON 数据格式合并数据格式，则文件大小约为150 兆字节所以我们在这里每次更改使用近 500 字节，这非常糟糕，所以你现在可以看到我们设计的新二进制数据格式，以便降低它 元数据开销我们实际上已经做了一些非常大的改进，所以我们所做的首先是设计了一种二进制格式，可以编码完整的编辑历史，包括每一个插入 打开和删除，包括何时发生，并以紧凑的形式对其进行编码，因此它根本不会丢失任何信息这是一种完全无损的编码，我们设法做的是将此文件大小减少超过 200 倍 低至大约 700 KB，包含完全相同的信息，只是编码不同，所以我应该强调，如果您只是获取 JSON 历史记录并使用 Jason 的二进制等价物之一对其进行编码，那么如果您使用协议缓冲区或消息，您将不会接近这个 pack 或类似的东西，您知道您最多可以将其减少 2 或 3 倍，但为了获得 200 倍的改进，您必须设计特定于查看怪异和特定标题模式的数据格式剂量 这往往会发生在这类应用程序中 与我们以二进制格式未压缩的 700 KB 相比，6 MB 仍然是巨大的，而且 gzip 仍然可以进一步缩小到大约 300 KB，而不会丢失任何信息，所以请注意，到目前为止，我们已经能够 Inc 对更改历史进行编码更改历史包含超过 300,000 个更改，我们已将其编码为 300KB，因此我们现在实际上每次更改使用不到一个字节来编码完整的更改历史，因此我们可以回顾任何过去本文档周的版本，如果任何两个版本在任何时间点以及所有这些数据仍然以这种非常紧凑的形式编码，我现在觉得非常令人兴奋，当然我们仍然可以通过丢弃一些来进一步压缩它历史，所以我们可能选择丢弃的第一件事就是光标移动，因为老实说，谁关心光标在编辑历史中的确切位置，所以我们可以 n 通过丢弃两个光标移动节省了大约 22%，我们可以通过丢弃文本的所有更改历史记录来降低到大约 230 KB，所以到这里我们仍然有 230KB包括所有墓碑的 CR DT 元数据，因此这意味着此时我们仍然能够在此数据的不同副本之间执行任意合并，但我们只减少了大约两倍的数据集大小，因此大约 100KB 完全没有 CR DT 元数据的原始文本文档，这只是文本文档的最终状态，所有 CR DT 元数据在没有 gzip 的情况下只增加了 100% 以上的开销，如果我们实际应用 gzip那么文件大小 几乎相同，因此包含 2 个 CR DT元数据 gzip 的文件与非 gzip 的纯文本文件大小相同，现在我们可以通过删除墓碑来进一步降低墓碑是已删除 ch 的标记 文档中的字符，如果我们这样做，那么我们会为墓碑保存另外 70 KB 或类似的内容，是否要这样做取决于因为如果你扔掉他们的墓碑，这意味着你不能再与编辑合并 这是同时发生的，因此在此之前发生的任何对石头移除或与墓碑移除同时发生的编辑现在都不能再合并，但是如果您确实删除了墓碑，那么只有原始 CR DT 元数据只是唯一标识符那时的字符只需要 50KB，因此使用我们的数据格式在原始文本文档之上只有 48% 的开销非常令人兴奋为了实现如此好的压缩，基本的想法是，正如我所说，我们希望尽可能多地保持所有的更改历史，所以我们将存储所有的完整集 插入操作 所有删除操作和所有自定义移动（如有必要） 每个操作都被赋予一个唯一 ID，它只是灯或时间戳，我很差时间戳只是一对计数器，节点的 ID生成它 或者我们在自动模式下将其称为演员 ID，我们用于文本编辑的算法基于 CRDT，因此它基于每当您执行插入时，您在标识符中引用 就在插入位置之前，我们保留这组所有操作并按文档顺序存储，它按照字符在文档中出现的顺序排列，我们在这里得到的是这种表格，所以你可以想到这个 几乎就像关系数据库中的一个表，其中每一行都是一个操作，所以你可以看到它正在输入 h-e-l-l-o所以你好是三个 L 然后有人出现并删除了三个 L 中的一个 o 最终结果只是你好，所以编码的方式是这里的每一行是一个插入到这个文档中的操作，你可以看到每一行都有一个操作 ID，它包含或者是一个灯或时间戳，所以它 由一个只会递增的计数器和我刚刚在这里写的演员 ID 组成，但实际上我们的演员 ID 实际上是新ID，因此它们实际上像 16 个字节甚至 32 个字节长，因此我们为每个对象都有这个唯一标识符 在这里插入的每个字符分配器我们都有作为前身字符的参考元素，前身字符的想法，所以这里只是说 e 在 H 之后，所以 H 的 ID 为 1a，e 的 ID 为 2a，在 1a 之后 因此我们可以通过这种方式对所有操作进行编码，此外，如果一个操作被标记为已删除，我们可以通过这些额外的删除列来实现这一点，我们可以重新组合这些额外的删除列，抱歉记录删除操作的操作 ID实际上，如果多个用户删除了同一个字符，可能会发生对同一个字符的多个删除操作，现在我们可以使用这个表并使用一些相当简单的技巧将它包含在一个非常紧凑的形式中，所以我们将转到首先单独编码该表的每一列，例如，我们可以查看第一列计数器调用，它由两个数字组成一二三四五六我们如何有效地编码首先我们Delta编码 这意味着对于每个数字，我们计算该数字与其前一个数字之间的差异，因此一二三四五六任意两个后续数字之间的差异为一，因此此增量编码 2 11 1 1 1 1，然后我们可以对其进行长度编码 到数字 1 的 6 倍，然后我们可以在整数的二进制编码中使用可变长度来将 6 个逗号1 编码为 2 个字节，因此这种可变长度编码只是确保 smal l数字用 1 个字节表示稍大的数字用 2 个字节表示 更大的数字仍然用 3 个字节表示列，所以对于这个演员列，首先，如果我们制作一个查找表，我们不需要继续重复巨大的 ID，所以我们只需将 a 映射到 0 B 到 1，所以现在这转换为 0 0 0 0 0 0我们可以运行长度编码 使用可变长度二进制编码 再次运行我们已经将整个列编码为 2个字节继续前进 让我们看看这个实际的文本列在这里 我所做的实际上是在两个单独的列中表示文本所以在这里 这是正在插入的特定字符的 utf-8 字节字符串，在此长度列中，我们有该特定 Unicode 字符的字节数，所以如果我们正在做的只是输入英文文本，那么每个单个字符将在utf-8 的 1 字节编码范围内，因此这里的这一列将由许多字符组成，只是所有字符的长度都为 1，因此再次超级紧凑地编码，现在就像我们一样对实际字符的长度列进行编码，我们可以将它们连接起来，因为稍后我们仍然可以通过查看长度列来拆分字符之间的边界，因此我们只需连接所有字节 utf-8 列 hello 带有三重 L，它被编码为六个字节，所以我们在这里所做的只是通过单独编码每一列，我们可以在几口中非常紧凑地表示每一列，结果证明是因为编辑您倾向于使用文本获得的模式 您倾向于获得这些递增的序列，因为人们只是倾向于按顺序输入字母，这意味着您可以使用递增的计数器序列 每次总是增加一个，所以整个数据有一个结构可以很好地压缩，我们可以利用我们对这个结构的知识来非常紧凑地对其进行编码，所以这给了我们现在的一组操作，以便拥有完整的更改历史我们需要一些额外的元数据，这些元数据是针对在某个时间点进行的每组更改的 即使使用非常少量的额外存储空间，文档在每个经过的时间点看起来都像，所以如果人们告诉你使用 CRD T，你知道你必须努力收集墓碑，因为墓碑浪费了大量空间，你知道只是想回到这张桌子，墓碑实际上只花费了我们 48% 的空间，在选择差异的同时维护这里的成本是相当小的 在简单的JSON 格式和优化的二进制格式之间产生了 200 倍的差异，所以我认为这意味着我们有能力存储完整的更改历史记录，并让我们知道下降和有趣的可视化或更改历史记录 对于我们的文档，成本非常低，成本非常低，我们实际上不必丢弃我们拥有的所有这些额外的元数据，所以这让我到了最后，正如我在开始时所说的，我认为 C 的奇怪之处很容易实现 非常糟糕，因此它们很容易以一种低效的方式实现，并且具有各种奇怪的行为，例如我们看到的交错异常，它们都是我们如何在列表和列表上执行移动操作的所有这些问题以一种安全且最近对我们的用户来说很直观的方式创建树，但正如您从本次演讲中看到的那样，我们在过去几年中在这些主题上取得了很大进展，我认为它正朝着我们的方向发展 重新看到奇怪的东西开始成为非常大的应用程序集的基础，所以我们可以开始构建真正的实际用户软件，而不仅仅是在这些基本原则之上研究原型，所以我希望你能加入我的行列 发现这非常有趣，并探索它在未来的发展方向，所以我将以一些参考资料作为结尾，首先是我在交错的上下文中谈到的各种文本编辑 CRD T 的列表，最后是出版物 我一直致力于解决我们在本次演讲中谈到的各种算法、异常和问题所有幻灯片都在线所以你可以在那里找到它们非常感谢你的聆听我希望你喜欢这次演讲 很快再见”