差分同步

Differential Synchronization

频道:Google TechTalks · 时长:54:43 · 发布:2009-01-10 · 播放:52090

在 YouTube 观看

简介

Google 的 Neil Fraser 介绍了差分同步,这是 MobWrite 背后的算法,用于实时保持文档的多个副本同步。演讲认为该方法稳健、收敛且高效。

HN 为什么推荐

HN指出它是协作编辑中操作转换和CRDT的简单差异与补丁替代方案。

真正好的地方在于,它是一个简单的算法 — HN, 2014

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

中文字幕节选

谢谢大家来,呃,这次演讲主要会在白板上进行,所以请原谅我 如果我背对着大家,呃,随时打断我问问题,请越多 越好,呃,问题意味着你不理解某些东西,但也意味着 你仍然关心,所以这很好,呃,这次演讲会发到YouTube上,所以呃,把 机密问题留到最后,呃,好的,差分 同步,它的目的是 如果我们有多个 用户都在查看和编辑同一个文档,比如说呃 文档内容是 cat,我们有三个用户,一、二和三 如果我们有实时同步,那么如果用户一添加了一个S 变成cats,用户二把这个改成my cats,然后S 被推送到这里,my被传回去并合并,S 传到这里,my传下来,所以每个人 总是看到几乎相同的文本,现在总会有一些延迟 所以不,所以两个人可能在屏幕上有不同的内容,在任何给定时间,呃,我的意思是 光速决定了至少会有 一些差异,呃,但想法是它应该很快自我解决,现在 这个图明显是点对点的,呃,不幸的是点对点 在互联网上不太有效,除非你要么让所有人都在本地 环境中,呃,要么让所有人都高度积极,我会让你自己弄清楚什么 是高度积极,呃,因为那不是我们感兴趣的,呃,我们 希望普通用户能够在互联网上使用这个,我们不是在探索 点对点,呃,所以这是第一个分叉,第一条未走的路,也许点对点 对于某种同步是正确的解决方案,但不是我们的,所以这 不是这次演讲要讲的内容,所以这让我们来到客户端 服务器,不出所料,所以如果我们这里有一个服务器,服务器会有它 自己的文本副本,呃,连接,现在 这实际上从算法角度大大简化了事情,呃 因为如果我们能让一个神奇的同步系统在一个 客户端和服务器文本之间发生,那么我们就完成了,因为如果这个 用户添加了S,对这个文档做了更改,同步 会将更改移动过来并对这个文档做更改,因此这个文档 已经改变,因此它应该进一步传播,呃,所以我们所要做的就是 弄清楚如何做这部分,网络的其余部分会自己处理 唯一的警告是,当更改发生时,它不能被镜像 回去,否则你会进入这个美妙的状态,我添加一个s,s,哦,s已经被 添加了,SS,作为开发者,我无法告诉你有多少次我打开 系统,它立即被第一个按键填满,呃,那些 总是很有趣,所以让我们来看看如何 在客户端和服务器之间同步 呃,最简单的方法 是这里放一把椅子 是的,看起来我把这个房间的大小估计得差不多,最简单的 同步方法就是简单地观察键 击,所以如果客户端,现在这是客户端,如果 客户端输入一个S,你会有一个事件,呃,按键事件,所以你可以 检测字符的键码,你可以查看光标在哪里,呃,你可以 获取关于这个文档刚刚改变的所有信息, 然后你可以发送一条消息说我们在位置三添加一个S 或类似的东西,服务器添加它,同样如果服务器改变 某些东西,它只会发送,呃,发回一条关于那个的消息,相当直接 呃,真的很容易设置,问题是它是发散的,呃,如果有 问题,它永远不会从那个问题中恢复,让我给你一个例子

HN 上的讨论

我正在做一个有一些离线数据同步需求的项目,但还没有开始实现。我一直饶有兴趣地关注 CRDT。我也看到了原文中提到的许多相同的缺点,例如膨胀(显然这些问题正在得到非常好的解决)。除了 OT,我还遇到了另一种看起来非常有前途的方法,即 Neil Fraser 的差分同步[1]。虽然它也依赖于集中式服务器,但它允许以某种方式链接服务器,这似乎解决了 OT 的许多缺点。我想知道为什么我在 HN 上很少看到差分同步被提及?是因为缺乏了解,还是因为用例匹配问题,或者是我没有看到的某个致命缺陷?还是其他原因?[1] [VIDEO] — mhale, 2020-09
我没有尝试过,但你可能也会对一种称为差分同步[1]的方法感兴趣。基本上,它只是一种传递差异以保证收敛的特定方式,尽管(据我所知)它并不保证其他什么(比如如果补丁无法应用,你会丢失数据吗?)。不过,真正好的地方在于,它是一个简单的算法,并且可以应用于任何你有差异/补丁算法的地方。[1] [VIDEO] — dahjelle, 2014-06
一个现实世界的用例是差分同步。这里有一个关于该主题的Google Tech Talk:[VIDEO] 这是用于实时协作编辑或结构化数据的复制(不同于为文本优化的操作转换)。来回发送补丁是协议的核心。 — raganwald, 2012-09
差分同步不需要固定的轮询间隔。你可以在每一方输入时实时更新,事实上算法更喜欢这种设置,因为这样可以更容易地快速处理大量小改动。Neil 在这个谷歌演讲中详细解释了为什么是这样:[VIDEO] 。诀窍是在有人更改文档后同步,同时加入短暂的防抖,以免用多余的编辑使系统过载。 — pg_bot, 2018-07

相关视频