CRDTs:难点解析

CRDTs: The Hard Parts

频道:Martin Kleppmann · 时长:1:10:09 · 发布:2020-07-06 · 播放:90832

在 YouTube 观看

简介

Martin Kleppmann 综述了当前关于 CRDT 的研究,这是一种用于合并离线副本间并发编辑的算法。他涵盖了诸如富文本、移动操作以及技术上正确但效果不佳的合并结果等难点。

HN 为什么推荐

被推荐为关于 CRDT 及其局限性的极佳入门教育。

我发现他的这个视频是对 CRDT 的极佳入门教育 — HN, 2021

分布式系统 · 算法与数据结构

中文字幕节选

大家好,我叫 Martin Kleppmann,我是剑桥大学的研究员, 今天我想谈谈我们在无冲突复制数据类型(CRDT)方面的一些工作。 所以我会先非常简要地介绍一下 CRDT 是什么以及它们为什么有用, 但这次演讲的大部分内容将是我们过去一两年内才得出的新成果。 你们可能通过这本书认识我,这是我几年前写的, 书名叫《设计数据密集型应用》,它广泛概述了数据系统的架构, 以及如何为你的特定应用选择数据库。 这不是我们今天要讨论的内容。 今天我们要讨论的是协作软件。 对于协作软件,我采取一个相当宽泛的视角: 这是指任何允许多个用户更新文档、数据库或某种共享状态的软件。 符合这一类的软件有很多例子, Google Docs 是一个明显的例子,你可以让多个人同时编辑一个文档, 创建文本文档或电子表格,类似的东西还有 Office 365。 Figma 是一个支持多用户实时协作的图形软件例子。 Trello 是一个项目管理软件的例子,多个用户可以更新各种任务的状态, 分配任务、评论等等。 所有这些的共同点是用户正在更新某种共享状态。 现在我将使用协作文本编辑这个例子, 稍后也会有一些其他类型应用的例子。 所以在协作文本编辑中,你可能会遇到这样的场景: 有两个用户,在我们观察的时间开始时,他们拥有相同的文档,内容是“hello!”, 然后红色用户将文档改为“hello world”, 在感叹号前插入单词“world”。 与此同时,蓝色用户同时将文档改为在感叹号后添加一个笑脸符号。 这两个更改是并发发生的,彼此不知道对方的存在。 然后当网络通信时,这些更改被传播, 这些用户通过互联网或其他网络进行通信, 他们应该收敛到相同的状态。 所以我们希望最终两个用户拥有 屏幕上显示相同的文档,并且该文档反映了所有 所做的更改,在这种情况下,合并结果相当合理,符合我们的预期 预期单词 world 在感叹号之前,笑脸在 感叹号之后。好了,所以大致有两类算法可以 实现这种协作文本编辑,一种是操作转换 或 OT,这是多用户协作编辑的经典方法,已经 存在很长时间了,例如 Google Docs 就使用了它,然后 还有一类较新的算法叫做 CRDT,这是我研究的领域,它 采用稍微不同的方法来解决类似的问题,我们将在 稍后比较这两者。所以我先简要总结一下操作 转换的工作原理,因为这对于与 CRDT 进行比较很有用 所以在操作转换中,我们首先必须描述如何对文档 进行更改,因此当用户更改文档时,他们在文档的某个位置插入或删除 一个字符,所以我们可以通过使用索引来描述这些插入和删除 发生的位置,我们只需对第一个字符编号,文档中的第一个字符 为 0,第二个字符为 1,以此类推。现在 抱歉,第一个字符为 0,第二个字符为 1,以此类推。现在 你可以有两个用户更新他们的文档,在左侧 用户通过在第 3 个位置添加第二个 L 来更改文档 HDL Oh,

HN 上的讨论

作者是一位分布式系统研究员。我发现他的这个视频是对 CRDT 的极好入门教育,介绍了它们如何工作、擅长什么以及(目前)不擅长什么:[VIDEO] — rkangel, 2021-01
他们声称的是,如果所有编辑都停止,那么在一段时间后,每个人都会看到相同的文档。这就是“最终一致性”的含义。一般来说,实现这一点确实是一个难题,但(其中一些)算法确实解决了它,尽管正确证明它们做到了可能很棘手。我同意,无法确保每个人看到的文档就是他们真正想要的。然而,对于会发生什么有一些选择,其中一些结果可能在技术上是正确的——我们都看到相同的东西——但显然非常糟糕。这个精彩的演讲有一些例子:[VIDEO] — williamstein, 2024-12
啊,我会在开头把它作为注释加入。你可以在我之前写的一篇文章中看到更基础的介绍:[LINK] [LINK] 以下是我觉得有帮助的一些入门材料:- [CRDT 互动入门]( [LINK] ) - [基于状态的 CRDT 介绍]( [LINK] ) - [面向非学术人士的 CRDT]( [LINK] ) - [CRDT: The Hard Parts]( [VIDEO] ) - [CRDT 阅读材料]( [LINK] ) - [crdt.tech]( [LINK] ) — iamwil, 2024-01
我们几乎做到了,对于列表和结构体有 CRDT,但缺少跨数据结构的移动操作。Martin Kleppman(来自 automerge)在他的演讲“CRDTs: the hard parts”[0] 中谈到了这一点。我还认为许多这些算法缺少范围移动或范围删除。HN 上的一篇投稿确实在富文本上实现了范围删除(但我忘了名字)。[0]: [VIDEO] 编辑:啊,实际上 Peritext(你链接到的)就是我想的那篇文章。我认为范围删除对普通列表也很有用。 — thomasikzelf, 2021-12
披露:我在一个相关项目(Fluid Framework)上工作,该项目使与应用程序无关的 CRDT 易于使用。CKEditor 团队在构建开源文本编辑器方面做得非常出色,他们在构建与协作良好配合的文本编辑器方面尤其出色。我让几个开源富文本编辑器(大部分)与 Fluid 配合工作 [0, 1],文本编辑器的设计确实会极大地影响添加协作的难易程度。幸运的是,文本编辑器接受远程更改,集成 OT 或 CRDT 解决方案大致相同。他们也很好地解释了这个问题。我的经验是,人们并不直观地理解为什么实时协作是一个棘手的问题。我也不理解。首先,对于许多用例来说,websockets + redis + 最后写入胜出的冲突解决(或类似的解决方案)完全足够。其次,富文本编辑为什么需要更复杂的冲突解决并不是显而易见的。第三,解决 RTE 问题为什么不能立即适用于其他问题也不是显而易见的 [2]。因为我们从 20… — sambroner, 2020-12

相关视频