找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 11498|回复: 3
收起左侧

系统设计题: 如何设计一个简单的 Collaberative Editor (Google doc)

[复制链接]

7

主题

6

精华

105

积分

资深会员

Rank: 2

积分
105
发表于 9-6-2016 01:49 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 9-9-2016 08:23 AM 编辑

类似google doc,协同编辑就是能够让多人同时编辑同一份文档。用过版本控制的童鞋都知道,用版本控制的一个好处就是,可以方便的多人共同去做一个项目,但有时大家会对同一个文件的同一行进行了修改,这时merge代码的时候,就需要你去手工去解决冲突,而协同编辑同样也面临冲突的问题,这时候就是程序实时的自动去解决冲突了。
现在做协同编辑的已经有很多了,比如google doc,比如facebook面试喜欢用的collabedit,还有最近开源的towtruck这个东西,所以协同编辑还是深受大家欢迎的阿。这里有个英文的协同编辑的实现原理可以作参考。

协同编辑主要来说需要这么几个步骤
1、计算出当前用户的对文档作出的修改发送到服务器
2、对于所有用户对文档进行的修改进行合并以及冲突处理
3、将合并之后结果返回到前段
4、将光标移动到需要的位置


对于第一个步骤而言,就是类似于linux中的diff操作,去比较当前的文档内容和之前的文档内容,来得到用户对于文档的修改。可以对两篇文档,用动态规划的方法,找到最长公共子序列,然后除去公共部分,剩下的就可以得到差异部分了,用动态规划的方法的时间复杂度为O(n^2),网上还有些针对一些情况加速的论文比如《An Algorithm for Differential File Comparison》和《An O(ND) Difference Algorithm and Its Variations》。然后我发现google提供了很好的各种语言的实现,可以去很方便的调用。

得到差异发送到服务器我们就需要进行冲突的合并了,这个步骤叫做operational transformation。

比如用户A在文档字符数3的位置插入了test,用户B删掉了文档字符数5-7的位置,合并之后就变成了用户A在3的位置插入了test,用户B删掉了文档9-11的位置,这样对于所有用户的修改进行合并,再把所有修改告知所有的用户,来确保所有用户显示的内容始终是一样的。

最后就是移动光标的位置到相应的位置上,其实就是判断光标之前的操作都进行了什么,相应的去把光标前后移动就可以了。

基本上按照这个思路,利用comet技术等,多注意一些细节问题,就可以去自己实现一个类似google doc的在线协同编辑器了,我按照这个想法,实现放到了sae上,源代码在这里,有兴趣的可以看看。

https://github.com/isnowfy/collaborative-editor


评分

参与人数 1金钱 +3 收起 理由
Sophia + 3 给您点个赞!大米满满送上!

查看全部评分

0

主题

0

精华

6

积分

新米人

Rank: 1

积分
6
发表于 9-6-2016 02:39 PM 来自美国米群网手机版 | 显示全部楼层
感谢mobilict分享~~~好人一生平安~~~
回复 支持 反对

使用道具 举报

0

主题

0

精华

0

积分

新米人

Rank: 1

积分
0
发表于 9-8-2016 02:04 PM | 显示全部楼层
感谢mobilict分享~~~好人一生平安~~~
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表