实时协同编辑的实现

标签: 实时 协同编辑 | 发表时间:2014-04-21 15:00 | 作者:
出处:http://fex.baidu.com
作者:nwind

在最近某个项目中打算使用协同编辑来解决冲突问题,因此抽空调研了现有的实现方案,结果发现要想做完美是很难的,但我们可以低成本地做到不错的效果,本文将介绍几种实现方法,大家在项目中如果有需要可以参考。

什么是实时协同编辑

这里所说的实时协同编辑,是指多人同时编辑一个文档,最典型的例子是 Google Docs,你可以实时看到别人做出的修改,不用手动刷新页面。

要实现实时编辑,我们需要解决两个技术点:实时通信问题、编辑冲突问题,其中实时通信问题比较好解决,可以通过 long pull 和 WebSocket 技术,所以这里就不过多讨论了,重点将放在如何解决编辑冲突问题上。

可选方案

接下来将从易至难的顺序来介绍几种可行的方案,分别是:「编辑锁」、「GNU diff-patch」、「Myer's diff-patch」、「Operational Transformation」和「分布式 Operational Transformation」。

编辑锁

编辑锁这是实现协同编辑最简单的方法,简单来说就是当有人在编辑某个文档时,系统会将这个文档锁定,避免其他人同时编辑,因为实现简单,所以这个方案是应用最广的,比如公司内部常用的 TWiki 系统,采用这种方式虽然可以在一定程度上避免覆盖问题,但它的使用体验不好,也做不到「实时」,所以这里就不讨论了。

GNU diff-patch

Git 等版本管理软件其实也是一种协同编辑工具,因为每个人都可以并行编辑,遇到编辑同一个文件时可以自动合并,因此我们也能使用类似的原理来实现协同编辑,具体可以有两种方法:diff-patch 和 merge。

先说 diff-patch,这里的 diff 和 patch 是指两个 unix 下的命令,diff 能输出两个文本的不同之处,然后用 patch 来更新其它文件,我们只要在 JS 中实现这两个算法,就能通过如下流程来实现协同编辑:

  1. 每个用户进来时都建立长连接(最好是基于 WebSocket),保存好当前文档副本
  2. 有人编辑时,如果停顿 5 秒(具体要根据产品策略),就将现有文档和之前的副本进行 diff,将结果传给服务端,更新副本
  3. 服务端更新文档,然后通过长连接将这个 diff 结果发给同时在编辑的其它用户,这些用户使用 patch 方法来更新 ta 们文档

但 GNU diff 有个问题,因为基于行匹配的,所以很容易冲突,让我们测试一下「百度 Web」和「百度 Web 前端」这两段文本的 diff 结果

   [nwind@fex ~]$ diff old.txt other-new.txt > old-to-other-new.patch
[nwind@fex ~]$ cat old-to-other-new.patch
1c1
< 百度 Web
---
> 百度 Web 前端

在这个 diff 结果中, 1c1 的第一个「1」代表修改前的第一行,后面的「c」代表「修改」,第二个「1」代表修改后的行,也就是说将第一行的「百度 Web」改成「百度 Web 前端」,修改后的内容放第一行。也就意味着如果两人同时修改一行就会冲突,可以通过下面的测试来确认:

   [nwind@fex ~]$ cat my-new.txt
Web

[nwind@fex ~]$ patch my-new.txt < old-to-other-new.patch
patching file b-new.txt
Hunk #1 FAILED at 1.
1 out of 1 hunk FAILED -- saving rejects to file my-new.txt.rej

[nwind@fex ~]$ cat my-new.txt.rej
***************
*** 1
- 百度 Web--- 1 -----
+ 百度 Web 前端

其中 my-new.txt 是我修改的版本,我去掉了前面的「百度 」,只留下「Web」,其实这两处修改是不冲突的,它们可以合并成「Web 前端」,如下图所示

merge

但使用 patch 命令部下,它在冲突后会生成一个新文件 my-new.txt.rej 来描述失败原因,这种展现方式不直观,需要打开两个文件比对,我们使用另一种方式来更好地展现,那就是接下来介绍的 merge 命令,它的使用方法如下:

   [nwind@fex ~]$ merge my-new.txt old.txt other-new.txt
merge: warning: conflicts during merge

[nwind@fex ~]$ cat my-new.txt
<<<<<<< my-new.txt
Web=======
百度 Web 前端>>>>>>> other-new.txt

可以看到它直接将冲突的地方写到 my-new.txt 里了,这点比 patch 看起来要方便些,对于这个结果估计大部分同学都会眼熟,因为 merge 命令和 Git 等工具 中的合并算法是一样的

通过使用我们可以发现 merge 命令有个缺点,那就是需要使用 3 份完整的文本来进行比较,为了避免每次传递所有文本内容,我们可以结合使用 diff 来减小传输体积,在后端 patch 成新的文本。

无论是 diff 还是 merge,由于它们的算法都是基于行进行比较,导致对同一行的编辑必然冲突,为了解决这个问题,我们可以尝试基于字符粒度的 diff 算法,那就是接下来将介绍的 Myer's diff-patch。

Myer's diff-patch

Myer 算法是另一种 diff-patch 算法,它有很多 语言的开源实现,这里我们就不介绍细节算法了,直接用之前的例子来测试它的效果,首先看一下它的 diff 结果,调用代码如下:

   var old_text = "百度 Web";
var new_text = "百度 Web 前端";

var dmp = new diff_match_patch();
var patch_list = dmp.patch_make(old_text, new_text);
patch_text = dmp.patch_toText(patch_list);

console.log(decodeURI(patch_text))

输出结果为

   @@ -1,6 +1,9 @@
 百度 Web
+ 前端

其中第一行的 -+ 两个符号没有什么意义,这句话表示修改处之前的起始位置为 1(由于数组是从 0 开始的,所以内部计算时会先减一),长度为 6,后面的 1,9,表示修改后的起始位置为 1,长度为 9。在接下来的两段文本代表修改的地方,注意「百度 Web」前面有空格,这代表相等,也就是直接添加这个字符串,而后面的 + 代表添加文本,具体细节可以通过它的 实现源码了解。

因此确定它的 diff 策略是基于字符匹配的,这样能否解决我们之前遇到的冲突问题呢?接下来来测试一下,源码如下:

   //相关代码同上
var patches = dmp.patch_fromText(patch_text);
var results = dmp.patch_apply(patches, "Web");

console.log(results[0]); //Web 前端

这个输出结果是正确的,也就是说它能很好地解决之前的问题,但如果是同一个位置的修改会怎样?我继续做了几个实验:

   var old_text = "百度 Web";
var other_new_text = "百度 Web 后端";
var my_new_text = "百度 Web 前端";
...
//结果为「百度 Web 前端 后端」

===
var old_text = "百度 Web 前端";
var other_new_text = "百度 Web 后端";
var my_new_text = "百度 Web 全端";
...
//结果为「百度 Web 后端」

===
var old_text = "百度 Web";
var other_new_text = "Web 前端";
var my_new_text = "百度 FE";
//结果为「FE 前」 

第一个例子是在后面添加不同的字符,它的结果是两个添加都生效,第二个例子是在同一处修改成不同的字符,它的结果是别人的修改生效,但最后一个例子出错了,丢失了「端」字,这里看起来还好,但如果内容是富文本就有问题了,比如 <b> 少了 > 是不行的。

整体来看 Myer 算法可以低成本地解决大部分问题,所以有些在线编辑器选择它来实现协同编辑功能,比如 codebox,它的客户端代码 在这,服务端代码 在这

不过 Myer 在某些情况下会丢字符,是否还有更好的方法?答案是有,那就是接下来介绍的 Operational Transformation 技术。

Operational Transformation

Operational Transformation(下面简称 OT)技术正是 Google Docs 中所采用的方案,因此是经过验证的,值得研究。

最开始我一直觉得 OT 会很复杂,因为它的相关介绍文章都写得很长,比如 这篇及维基百科上的 介绍,不过看了之后才后发现它的原理并不复杂,我将在这里进行简单的说明。

首先,我们可以将文本内容修改转成以下 3 种类型的操作(Operational):

  • retain(n):保持 n 个字符,也就是说这 n 个字符不变
  • insert(str):插入字符 str
  • delete(str):删除字符 str

举个例子,假设 A 用户将「百度 Web」变成「Web 前端」,相当于产生了如下 3 个操作:

   delete('百度 '),  //删掉「百度 」
retain(3),       //跳过 3 个字符(也就是「Web」)
insert(' 前端')   //插入「 前端」

提取这些操作可以通过 Levenshtein distance(编辑距离)算法来实现。那它如何解决冲突问题了?比如这时如果 B 用户将「百度 Web」改成了「百度 FE」,B 所生产的操作步骤将会是如下:

   retain(3),       //跳过 3 个字符(也就是「百度 」)
delete('Web'),
insert('FE')

如果我们先应用 A 的操作,将字符串变为「Web 前端」,然后再应用 B 的操作时就会失效,因为在执行 B 的第二个操作 delete('Web') 时并没有「Web」,这时从第四个字符开始已经变成了「 前端」。

因此我们需要转换 B 的操作来适应新的字符串,比如调成如下操作:

   delete('Web'),
insert('FE'),
retain(3)

这个转换算法就是 OT 的核心,实际上 OT 指的是一类技术,而不是具体的算法,这个思路就是首先将编辑转成操作(Operational),如果多人操作同时进行,需要对这些操作进行转换(Transformation),这就是为什么叫 Operational Transformation,而具体应该拆分成哪些操作以及转换算法都是可以自定义的,因此 OT 可以灵活地支持各种协同编辑应用,比如非文本类的编辑。

回到之前 Myer 算法导致丢字符的那个例子,我们看看 OT 是否能解决,这里我使用了一个开源库 changesets,以下是基于它实现合并的例子:

   var Changeset = require('changesets').Changeset;

var text = "百度 Web"
  , textA = "Web 前端"
  , textB = "百度 FE";

var csA = Changeset.fromDiff(text, textA);
var csB = Changeset.fromDiff(text, textB);

var csB_new = csB.transformAgainst(csA); //这里这就是操作转换

var textA_new = csA.apply(text);
console.log(csB_new.apply(textA_new)); //结果是「 前端FE」

结果并不正确,正确的应该是「FE 前端」,查看一下 csB_new 的内容,发现它实际上是转换成了如下操作:

   delete(3),   //注意 changesets 在这里的参数不是字符串而是数字,它会直接删掉 3 个字符,不够内容是什么
retain(3),
insert('FE')

需要注意这并不是 OT 技术本身的问题,而是 changesets 所实现的转换算法问题,虽然不够完美,但和之前的 Myer 算法相比,至少没丢字符,后来我又做了几个测试,发现 OT 技术的准确率比 Myer 高,因此它是最适合用于协同编辑的技术。

分布式 Operational Transformation

如果看完上面的文章你觉得实现实时协同编辑似乎不难,那你就错了,因为我们之前都没有考虑分布式的问题,OT 技术在学术界都研究 20 多年了,至今也没人总结出一个最好的方法,前 Google Wave 工程师在 ShareJS 首页上这样写道:

Unfortunately, implementing OT sucks. There's a million algorithms with different tradeoffs, mostly trapped in academic papers. The algorithms are really hard and time consuming to implement correctly. I am an ex Google Wave engineer. Wave took 2 years to write and if we rewrote it today, it would take almost as long to write a second time.

所以其实要做好是很难的,这里面最麻烦的就是分布式导致的问题,接下来将介绍 3 个我能想到的问题及解决方法。

1. 顺序问题

首先第一个问题是顺序问题,因为 OT 等算法都是依赖顺序的,不同顺序会导致结果不同,我们通过下面这张图来说明:

order-problem

假设 Client A 在做两次修改时发了两个异步请求,可能因为网络延迟导致第二个请求反而先到了,导致最终服务器版本和 Client A 所看到的不一致,同样在服务器发往其它客户端的请求时也会出现乱序的问题,如图中 Client B 也有问题。

这个问题的解决方法很简单,我们可以在客户端和服务器端都加上队列来保证请求顺序,等前一个请求结束后再发下一个请求。

2. 存储的原子操作

如果有多台服务器,或者有多个线程/进程在同时处理请求时就会遇到覆盖问题,因为读写数据库并不是原子操作,比如下面的例子:

data-atomic

Web Server AWeb Server B 同时访问数据库,结果导致 Web Server A 的修改被覆盖了。

好在这种问题还算比较常见,解决办法可以有 3 种:

  • 保证操作只在一个线程中执行,比如某个文档的更新只在某个固定的机器,使用 Node 这样的单线程模型提供服务,这样就不可能并行修改了
  • 如果数据库支持事务(transaction),可以通过事务来解决
  • 如果数据库不支持事务,就只能用分布式锁了,如 ZooKeeper

从实现角度来看,第一和第二种方法都比较简单,而第三种方法会带来很多问题,比如可能导致文档被锁死,假如上锁后由于种种原因没有执行解锁操作,这个文档就会永远被锁住,所以还得加上超时限制等策略。

然而在解决了原子操作后,我们将发现一个新的问题,那就是版本管理问题。

3. 版本管理问题

在前面的例子中,两段新文本的修改都是基于同一个旧版本的,如果旧版本不一样,就有可能出错,具体可以通过下面这张图来解释:

version-problem

在这个例子中,Web Server A 接收到操作命令是将「a」文本改成「aa」,Web Server B 接收到操作命令是将「a」文本改成「ab」,这里我们加上了锁机制来避免同时读写数据,Web Server A 首先得到了锁,然后修改并更新数据,而 Web Server B 需要先等待数据解锁,等 Web Server B 拿到数据后它已经从「a」变成了「aa」,如果还按照 retain(1), insert('b') 进行修改,数据将变成「ab」,而不是正确的「aab」,引起这个问题的原因就是旧版本不一致,Web Server B 需要根据 Web Server A 的操作进行操作转换,变成 retain(2), insert('b'),然后才能对数据进行修改。

因此想要解决这个问题,就必须引入版本,每次修改后都需要存储下新版本,有了版本我们就能使用 diff 功能来计算不同版本的差异,得到其它人修改的内容,然后通过 OT 合并算法合并两个操作,如下所示:

version-problem

Web Server A 操作前数据版本是 v=1,操作后变成了 v=2,等到 Web Server B 处理的时候,它通过版本比较发现不一致,所以就首先通过编辑距离算法算出 Web Server A 所做的操作,然后用这个操作来对自己的操作进行转换,得到正确的新操作,从而避免了覆盖问题。

如果保存所有版本会导致数据量大大增加,所以还需要再优化,比如每个服务器保存一个数据副本,但这里就不再展开了,可以看要支持分布式 还是挺麻烦的,不过目前出现了一些前后端整合的方案,如 ShareJSOpenCoweb Framework,可以参考。

另外之前提到的 Myer's diff 算法也有分布式解决方案,具体细节可以参考 这篇文档

初步结论

  • 如果你只是一个内部小项目,实时性要求不高,但对准确性要求比较高
    • 推荐用 merge 或 diff3 工具,出现同一行冲突时由用户来解决,这样能避免自动合并有可能出错的问题
  • 如果想具备一定的实时性,流量不大,不想实现太复杂,且对少量的冲突可以忍受
    • 推荐用 Myer's diff,后端只开一个 Node 进程
  • 如果想具备实时性,且有多台后端服务同时处理
    • 可以用 Operational Transformation 或 Myer's diff,但需要注意分布式带来的问题
  • 如果需要很精细的控制,如支持富文本编辑等非单纯文本格式
    • 只能使用 Operational Transformation,但要自己实现操作合并算法,比如 XML 可以参考 这篇文章

后续

除了文本合并,真正要做在线编辑还有很多细节处理,感兴趣的同学可以继续研究:

  • 支持选区,看到其他人选择的文本段,当然,这也有合并问题
  • 指针要更随文本变化移动到正确的位置
  • 支持 undo

相关 [实时 协同编辑] 推荐:

实时协同编辑的实现

- - FEX 百度 Web 前端研发部
在最近某个项目中打算使用协同编辑来解决冲突问题,因此抽空调研了现有的实现方案,结果发现要想做完美是很难的,但我们可以低成本地做到不错的效果,本文将介绍几种实现方法,大家在项目中如果有需要可以参考. 这里所说的实时协同编辑,是指多人同时编辑一个文档,最典型的例子是 Google Docs,你可以实时看到别人做出的修改,不用手动刷新页面.

Facebook的实时Hadoop系统

- wangjia - Solrex Shuffling
Facebook 在今年六月 SIGMOD 2011 上发表了一篇名为“Apache Hadoop Goes Realtime at Facebook”的会议论文 (pdf),介绍了 Facebook 为了打造一个实时的 HBase 系统使用到的独门秘技. 由于该论文提到的应用场景与小弟负责的系统要解决的问题域有相似之处,因而抽时间仔细阅读了这篇论文.

Storm 实时性分析

- - CSDN博客架构设计推荐文章
都说Storm是一个实时流处理系统,但Storm的实时性体现在什么方面呢. 首先有一个前提:这里的实时性和我们通常所说的实时系统(芯片+汇编或C编写的实时处理软件)的实时性肯定是没法比的,也不是同一个概念. 这里的实时性应该是一个相对的实时性(相对于Hadoop之类 ). 总结一下,Storm的实时性可能主要体现在:.

storm准实时应用

- - CSDN博客推荐文章
1 应用背景: 需要实时统计用户的登陆数,在线人数,活跃时间,下载等指标的数据,或者清洗后移到hdfs上.         1) 客户端产生数据---.         2) kafka-生产者实时采集数据(保留7天)-----.         3) storm实时消费数据,处理数据.         4)把实时数据统计结果缓存到memcached 中.

实时传输协议(RTP)和实时控制协议(RTCP)

- - CSDN博客推荐文章
RTP是一种提供端对端传输服务的实时传输. 协议,用来支持在单目标广播和多目标广播网络服务中传输实时数据,而实时数据的传输则由RTCP. 使用RTP协议的应用程序运行在RTP之上,而执行RTP的程序运行在UDP的上层,目的是为了使用UDP的端口号 和检查和. 如图16-12所示,RTP可以看成是传输层的子层.

实时流计算、Spark Streaming、Kafka、Redis、Exactly-once、实时去重

- - lxw的大数据田地
本文想记录和表达的东西挺多的,一时想不到什么好的标题,所以就用上面的关键字作为标题了. 在实时流式计算中,最重要的是在任何情况下,消息不重复、不丢失,即Exactly-once. 本文以Kafka–>Spark Streaming–>Redis为例,一方面说明一下如何做到Exactly-once,另一方面说明一下我是如何计算实时去重指标的.

快速构建实时抓取集群

- 狗尾草 - 搜索技术博客-淘宝
首先,我们定义一下定向抓取,定向抓取是一种特定的抓取需求,目标站点是已知的,站点的页面是已知的. 本文的介绍里面,主要是侧重于如何快速构建一个实时的抓取系统,并不包含通用意义上的比如链接分析,站点发现等等特性. 在本文提到的实例系统里面,主要用到linux+mysql+redis+django+scrapy+webkit,其中scrapy+webkit作为抓取端,redis作为链接库存储,mysql作为网页信息存储,django作为爬虫管理界面,快速实现分布式抓取系统的原型.

论文:Hadoop在Facebook的实时应用

- Adam - NoSQLFan
Facebook在其最新的消息系统中使用了HBase,这已经不是什么新闻了,而HBase与其基础设施HDFS也因此越来越受追捧,下面是Facebook在SIGMOD 2011大会上发表的论文,描述了Hadoop系列工具在Facebook中的应用情况. Facebook为何选择了Hadoop和HBase.

快速构建实时抓取集群

- Wang Dong - NoSQLFan
本文转载自搜淘宝索技术博客,描述了实时抓取集群的架构. 其架构中使用Redis作为核心的LinkBase存储,包括了使用List结构来存储抓取队列,使用Hash结构来存储链接表及使用Sorted Sets结构来存储已抓取集合. 注:原文中描述的已抓取集合是使用Set结构来存储,应该是不正确的,NoSQLFan进行了修改,如果修改有问题,欢迎指正.

inotify-rsync实时同步脚本

- lostsnow - 无网不剩
rsync是linux下一款非常强大的同步工具,采用差异同步的方法,只上传文件/文件夹的不同部分,同时可以对上传部分先进行压缩,所以rsync的传输效率是很高的. 但rsync也有缺点,最大的问题就是每次执行rsync命令都会遍历目标目录,当文件不多时,这没什么问题,一旦文件数到了一定规模,那么每次遍历都会消耗很多资源.