（计算机应用技术专业论文）一种协同编辑算法的研究和设计.pdf

一种协两编辑算法的研究和设计蔫要 摘要 实时协同编辑系统是一类重要的c s c w 应用系统，具有实时性、分布 性和无约束性三个特点。一致性维护是设计和实现此类系统最具挑战性 的一个世界级难题。传统的令牌、加锁、串行化和状态向量方法不能实 现一致性维护。十多年来，若干协同编辑算法先后尝试着实现一致性维 护。 本文首先综述了若干协同编辑算法，重点讨论它们一致性维护的实 现。其次，本文给出了一种协同编辑算法g o t 2 算法。g o t 2 算法基于 的文档结构是线性结构，它完全实现了一致性维护。此外，本文还给出 了g o t 2 算法的一种改进算法一t r e e g o t 2 算法，它基于的文档结构是树 型结构。最后，本文通过一个原型系统验证了g o t 2 t r e e g o t 2 算法的正 确性。 关键词：协同编辑操作变换操作意愿 作者：杜大刚 导师：吕强 t h er e s e a r c ha n dd e s i g no fac o o p e r a t i v ee d i t i n ga l g o r i t h m t h er e s e a r c ha n dd e s i g no f ac o o p e r a t i v ee d i t i n g a l g o r i t h m a b s t r a c t t h er e a l t i m ec o o p e r a t i v ee d i t i n gs y s t e m si sa l li m p o r t a n ta p p l i c a t i o ni n t h ef i e l do fc s c w i th a st h r e ec h a r a c t e r i s t i c s ：r e a l - t i m e ，d i s t r i b u t e da n d u n c o n s t r a i n e d c o n s i s t e n c ym a i n t e n a n c ei s o n eo ft h em o s ts i g n i f i c a n t c h a l l e n g e s i n d e s i g n i n g a n di m p l e m e n t i n gr e a l - t i m e c o o p e r a t i v ee d i t i n g s y s t e m s s u c ht r a d i t i o n a la p p r o a c h e sa st u r n - t a k i n g ，l o c k i n g , s e r i a l i z a t i o na n d c a u s a lo r d e r i n g ，c a nn o ta c h i e v ec o n s i s t e n c ym a i n t e n a n c e v a r i o u sa l g o r i t h m s a t t e m p tt oa c h i e v ec o n s i s t e n c ym a i n t e n a n c ei nr e c e n tt e ny e a r s i nt h i sp a p e r , f i r s t l y , w er e v i e ws o m ec o o p e r a t i v ee d i t i n ga l g o r i t h m si n t e r m so fa c h i e v i n gc o n s i s t e n c ym a i n t e n a n c e t h e r e a f t e rw ep r o p o s eg o t 2 a l g o r i t h mt oa c h i e v ec o n s i s t e n c ym a i n t e n a n c ea n de n s u l 屯t h ec o n t e x t - s p e c i f i c c o n s i s t e n c y , w h i c hr e l i e so nal i n e a rr e p r e s e n t a t i o no f t h ed o c u m e n t a l s ow e p u tf o r w a r dav a r i e t yv e r s i o n ，t r e e g o t 2 ，w h i c hr e l i e so na t r e er e p r e s e n t a t i o n o ft h ed o c u m e n t w ev a l i d a t et h ec o l t e c t n e s so ft h e s ea l g o r i t h m sb ya p r o t o t y p es y s t e ma tt h el a s tp a r to f t h i sp a p e r k e y w o r d s ： c o o p e r a t i v ee d i t i n go p e r a t i o n a lt r a n s f o r m a t i o n i n t e n t i o np r e s e r v a t i o n i i w r i t t e nb yd ud a g a n g s u p e r v i s e db y l vq i n g 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作所 取得的成果。除文中已经注明引用的内容外，本论文不含其他个人或集体已经发表或 撰写过的研究成果，也不含为获得苏州大学或其它教育机构的学位证书而使用过的材 料。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人承 担本声明的法律责任。 研究生签名：连盥j 日期：幺兰 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文合作部、中国 社科院文献信息情报中心有权保留本人所送交学位论文的复印件和电子文档，可以采 用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论 文的全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名 导师签名 日期： 日期 一种协同辅辑算法的研究和设计 第一章绪论 1 1 引言 第一章绪论 实时协同编辑系统( r e a l - t i m eg r o u pe d i t o r s ) 支持地理上分布的 用户通过网络在同一时间浏览和编辑一个共享的文档、图形或者多媒体 文件埘呻3 ，是一类重要的c s c w 应用系统。实时协同编辑系统主要有以下 三个特削”：一、实时性( r e a l - t i m e ) ，本地用户的响应迅速，远程站点 的传输延迟低；二、分布性( d i s t r i b u t e d ) ，协同用户使用不同的机器， 这些机器通过各种网络连接并且存在不确定的网络延迟；三、无约束性 ( u n c o n s t r a i n e d ) ，为了使信息在协同用户之间自由和自然的流动，若 干协同用户可以在任何时间并发的，自由的编辑共享文档的任意部分。 实时协同编辑系统有三种不一致情况，分别是数据不一致 ( d i v e r g e n c e ) 、因果关系违背( c a u s a l i t yv i o l a t i o n ) 和操作意愿违 背( i n t e n t i o nv i o l a t i o n ) 。相对于上述三种不一致情况，一致性维护 ( c o n s i s t e n c ym a i n t e n a n c e ) 可以分为数据收敛( c o n v e r g e n c e ) 、因果 关系维护( c a u s a l i t yp r e s e r v a t i o n ) 和操作意愿维护( i n t e n t i o n p r e s e r v a t i o n ) 三个方面婿。 历史上试图采用一些传统的方法来实现一致性维护，最具代表性的 是令牌( t u r n - t a k i n g ) 、加锁( 1 0 c k i n g ) 、串行化( s e r i a l i z a t i o n ) 和 因果次序( c a u s a lo r d e r i n g ) 方法，可是它们并没有取得理想的效果。 虽然此类方法是传统的分布式数据库、分布式计算和分布式操作系统采 用的经典方法，但是实时协同编辑系统毕竟不同于上述分布式系统，它 是提供给人使用的，而不是没有思维的进程。后来，操作变换和文档标 注方法纷纷涌现，各种算法跚嘲州9 m m 0 3 层出不穷，它们在不断的尝试 实现一致性维护。 上下文不一致不同于上述三种不一致情况，它涉及到文档的比较， 语法的检测和内容判断，完全解决具有相当的难度，而目前只能利用加 锁方法解决这个问题1 。 苎二兰! 坠一一 = 苎堡旦塑塑竺堡竺堡壅塑塑生 本文给出了一种协同编辑算法g o t 2 算法，它解决了数据不一致、 因果关系违背、操作意愿违背和上下文不一致四个问题。 本文还给出了t r e e c 抑t 2 算法，它基于的文档结构是树型结构。 1 2 协同编辑的系统结构 组群系统( g r o u p w a r e ) 通常有集中式和完全复制式两种结构“1 ，集 中式是所有站点的输入和输出都由服务器控制，文档只有一个版本，放 在服务器上。优点是：一、系统实现简单( 一般采用先来先服务的原则) ； 二、文档只有一个版本，加锁法实现简便。缺点是：默许了悲观思想， 当站点的规模很大时，系统运行非常迟缓。 完全复制式是每个站点有自己的个复制文档。优点是：默许了乐 观思想，各站点可以进行并发操作。缺点是：一、必须由一个算法来实 现并发控制，以维护各站点的数据一致性：= 、乐观思想下无用操作的 撤销将耗费一定的资源。 在实时协同编辑系统中，由于网络带宽和传输速率的限制，为了提 高系统的响应速度，特另i j 是保证尽量快的本地站点响应速度，一般都是 把共享文档复制到本地站点，即完全复制式结构。 本文的完全复制式结构定义如下：一共有n 个站点( s i t e ) ，每个站 点有一个用户参与，唯一标识为0 ，1 ，2 ，n 一1 。 本文假设编辑操作只有插入i n s e r t 和删除d e l e t e ，定义如下： i n s e r t i s ，p ，在位置p 处插入字符串s ； d e l e t e n ，p ，从位置p 开始删除n 个字符； p ( o p ) ：操作印的位置参数； l ( o p ) ：操作。p 的长度，当0 1 ) 为插入操作时，表示插入的字符串长 度；当印为删除操作时，表示删除的字符数： s ( o p ) ：插入的字符串。 1 3 一个协同编辑问题的情景描述嘲 一个n 等于3 的协同编辑系统有三个站点，分别是站点0 、站点l 和 ， 一种协同螭辑算法的研究和设计第一章绪论 站点2 。各站点生成的操作立即在本地执行，然后发送到其他所有站点保 持原来形式执行。三种不一致情况将在以下情景中发生，如图l 一1 。 时间 o p l 站点0站点1 站点2 图卜1 一个协同编辑同愿的情景描述 ( 1 ) 数据不一致( d i v e r g e n c e ) 一系列操作在不同的站点可能以不同的顺序抵达并且执行，导致不 同的结果。如图，操作o p l 、纰、叻和o p 3 在站点o 依次执行，操作o p 2 , o p l 、鼢和叻在站点1 依次执行，操作o p t , o p 4 、o p 3 、和o p l 在站点2 依次执行，三个站点上的操作的执行次序完全不同。数据不一致可以由 串行化方法解决，所有操作以相同的顺序在各个站点执行。 ( 2 ) 因果关系违背( c a u s a l i t yv i o l a t i o n ) 由于网络延迟的不确定性，操作可能违背之前的因果顺序到达且执 行。如图，站点1 在操作0 1 ) 1 到达以后生成操作o p 3 。当生成搡作蚴的时 候，站点1 的用户看到了操作o p l 对文档的编辑效果。所以，操作鼢依 赖于( d e p e n d e n t ) 操作0 1 ) 1 。然而，当操作卿和操作o , o l 在站点2 先后 执行，站点2 的用户会陷入一片混淆。比如：操作p 研插入一个字符串 “a b c d e ”，操作9 肼删除字符串中的“b c d ”，那么当操作，在站点2 执 行的时候出现矛盾。因果关系违背可以推迟一些操作的执行，利用状态 向量来保证操作按照因果顺序执行。 1 第一章绪论 一种协同编辑算法的研究和设计 ( 3 ) 操作意愿违背( i n t e n t i o nv i o l a t i o n ) 由于并发操作的产生，一个操作执行后的实际效果( a c t u a le f f e c t ) 可能和它生成时的意愿( i n t e n d e de f f e c t ) 不一致。站点0 生成操作o p l ， 此时站点o 的用户没有意识到站点1 生成了操作o p t , 所以操作m 独立 ( i n d e p e n d e n c e ) 于操作毗。操作o p l 在站点0 执行，文档状态随之发 生改变，然后操作o m 至：u 达站点0 ，执行。操作o p 2 在站点0 执行时的文 档状态与它在站点1 生成时的文档状态不同，导致操作o p 2 的实际效果和 它生成时的意愿不一致。比如，文档的初始状态“a b c d e ”， o p t = i n s e r t “1 2 ”，1 ，意愿是在“a ”和“b c d e ”之间插入“1 2 ”； o p t = d e l e t e 2 ，2 ，意愿是删除“c d ”。两个操作执行后，在操作意愿得到 维护的情况下，三个站点的文档结果都应该是“a 1 2 b e ”。然而，站点0 在操作o p j 和o p t , 先后执行以后的结果是“a i c d e ”，它同时违背了操作o p j 和嘞的意愿。即使采用串行化的方法来处理，三个站点的结果都是 “a i c d e ”，还是违背了操作o p l 和卿的意愿。 数据不一致和操作意愿违背的本质区别是前者可以利用串行化解 决，后者如果不改变操作本身就执行，那么任何串行化方法都不能解决。 此时，操作变换的引入成为了一种必然。 除了上述三种一般的不一致情况，还有一种特殊的不一致情况：上 下文不一致。比如，当前共享文档为“t h e r ew i l lb es t u d e n th e r e ”， 由于存在语法错误，所以站点o 生成操作印。意愿是在“s t u d e n t ”前 面插入一个“a ”，站点1 生成操作，意愿是在“s t u d e n t ”后面加上 “s n o 假设给出一种算法解决了操作意愿违背的问题，那么两个站点的 文档结果应该都是“t h e r ew il1b eas t u d e n e sh e r e ”。虽然操作意愿 违背和数据不一致都得到了解决，但是文档结果还是存在着语法错误， 或者说上下文不一致。我们意识到上下文不一致不能简单的用串行化、 状态向量和操作变换等方法来处理，必需用户亲自干涉或者其他技术手 段支撑才能解决。加锁是到目前为止一个十分有效的解决上下文不一致 的手段，它限制不同用户同时并发的编辑同一段区域”。 一种协同犏辑算法的研究和设计 第一章绪论 1 4 整体一致性模型吲 因果关系“一”定义： 给出两个操作哪和o p h ，0 1 9 生成于站点i ，o p , 生成于站点j ，那么 o p - - o p b 当且仅当：( 1 ) i = j ，o p 在o p b 之前生成：( 2 ) i j ，在站点j ， o p 先执行，o p , 后生成；( 3 ) 存在操作o p x ，使得口岛一瓣，o p , - o p h 。 独立性和依赖性定义： 给出两个操作o p 和叩一，( 1 ) 口陆依赖于。当且仅当o p - * o p b ；( 2 ) o p 和o p b 相互独立，记为o p i l 鼢，当且仅当m 一。和o p b 一0 1 0 都不成 立。 操作意愿定义： 操作印的意愿是指在操作印生成时的文档状态下执行操作d p 产生 的效果。在操作产生时的文档状态下，执行操作印得到的结果显然 满足操作意愿。 整体一致性模型( c c i ) ： ( 1 ) 数据收敛( c o n v e r g e n c e ) 当同一批操作在所有站点都执行过以后，每个站点上的文本是相同 的。 ( 2 ) 因果关系维护( c a u s a l i t y p r e s e r v a t i o n ) 如果操作o p , , - - - o p h ，那么在任意一个站点，操作o p 必须在o p , 之前 执行。 ( 3 ) 操作意愿维护( i n t e n t i o n p r e s e r v a t i o n ) 在所有站点执行操作印的效果和操作印的操作意愿一致；操作印 的执行不能影响到其他并发操作的执行。 数据收敛保证协同编辑的最终结果一致。因果关系维护保证协同编 辑过程中的依赖操作执行顺序的一致。操作意愿维护保证：一、在远程 站点执行一个操作的效果和在本地站点生成该操作时执行它的效果一 致，二、并发操作的执行不相互干涉。 整体一致性模型限制了依赖操作的执行顺序，对于并发操作的执行 不加干预，只要数据收敛和操作意愿维护都得到实现。 第一章绪论 一种协同编辑算法的研究和设计 1 5 本文结构 本文的第二章叙述了一些传统的并发控制方法，概述了基于操作变 换思想的d o p t “、a d o p t e d ”、g o t h 瑚1 、g o t o 、s o c t 3 s o c t 4 9 1 算法和基 于文档标注思想的文档标注盯m 0 1 算法：第三章给出一种协同编辑算法一 g o t 2 算法，它基于的文档结构是线性结构；第四章给出一种协同编辑算 法t r e e g o t 2 算法，它是对g o t 2 算法的改进，它基于的文档结构是树 型结构；第五章我们通过一个原型系统来验证算法的正确性；第六章是 总结和展望。 一种协同辅辑算法的研究和设计 第二章协同壤辑算法的概述 第二章协同编辑算法的概述 2 1 若干并发控制方法8 3 传统的并发控制方法没有从根本上解决一致性维护问题，我们重点 讨论它们在实时性、分布性和无约束性条件的限制下解决数据不一致、 因果关系违背和操作意愿违背的能力。 2 1 1 令牌( t u r n t a k i n g ) 任意时刻，只有一个用户享有权限编辑共享文档，这是令牌的定义。 权限的分配可以利用软件或者用户之间的约定来实现。 由于任意时刻只有一个用户编辑文档，所以三种不一致情况都不会 出现，也就是说，在不支持并发编辑的情况下实现了一致性维护。 2 1 2 加锁( 1 0 c k i n g ) 加锁是传统分布式计算和分布式数据库中的一种标准技术，它禁止 用户对共享数据并发操作，以此保证数据的一致性。加锁应用于协同编 辑系统就是一个操作对象( 单词、句子或者段落) 在编辑之前必须先被 锁定，限制多个用户对该对象进行编辑，以此支持多用户的并发操作。 当加锁的粒度是整个文档( 退化为令牌策略) 时，一致性维护可以 得到实现；当加锁的粒度是个句子( 或者段落) 时，一致性维护不能 得到实现，因为三种不一致情况的发生和编辑操作是否指向同一个目标 无关( 至少对文本文件而言) 。其实，加锁操作本身也需要一致性维护。 在分布式环境下，申请加锁和释放锁的动作还增加了系统的响应时间。 加锁虽然不能实现一致性维护，但是可以解决文档的上下文不一致 问题。 2 1 3 串行化( s e r i a l i z a t i o n ) 并发操作在每一个站点都以同样的次序执行，从而产生完全一致的 7 蔓二章协同编辑算法的概述 一种协同编辑算法的研究和设计 文档。通常由两种方法实现：一、一个操作的执行悲观延迟，直到所有 排序在前的操作执行完毕；二、一个操作乐观执行，然后采用u n d o r e d o 策略消除操作超前执行的影响。 显然，串行化可以解决数据不一致；通过调整操作之间的次序，串 行化不能解决操作意愿违背；悲观延迟一个操作的执行，虽然保证了本 地站点操作之间的因果关系，但是所有操作的因果次序是不一致的；乐 观执行一个操作也不能保证操作的因果关系；一些操作的执行经过悲观 延迟以后可能响应丢失。 2 1 4 因果次序( c a u s a lo r d e r i n g ) 并发操作在自然的因果关系约束下执行，依靠逻辑时钟向量( v e c t o r l o g i c a lc l o c k ) 或者状态向量( s t a t ev e c t o r ) 来实现，它是一种许多 分布式计算系统都采用的典型技术。本地站点生成的操作立即执行，符 合实时性要求；接收的远程操作必须等待所有的原因操作执行完毕，才 能执行。 状态向量解决了因果关系违背，不能解决数据不一致和操作意愿违 背。 2 2 基于操作变换的算法 由于传统的并发控制方法没有取得理想效果，e l l i s 和g i b b s 于1 9 8 9 年发表文章n ，提出了操作变换思想，基本思想是并发操作执行前先变换， 然后在各站点以不同的次序执行，最后各站点的文档状态保持一致。显 然，操作变换方法可以解决操作意愿违背的问题，这是传统的并发控制 方法所无法做到的。所以，操作变换具有划时代的意义，它使得实时协 同编辑系统的设计和实现真正成为可能。实际的算法设计中，操作变换 方法和状态向量一起使用，以此来解决数据不一致和因果关系违背问题。 下面我们概述各种基于操作变换的协同编辑算法。 一种协同编辑算法的研究和设计 第二章协同臻辑算法的概述 2 2 1d o p $ 算法1 1 d o p t 算法由e l l i s 和g i b b s 于1 9 8 9 年撰文提出，它第一次运用操作 变换思想尝试解决操作意愿违背问题。d o p t 算法还引入了状态向量 ( s t a t ev e c t o r ) ，从而解决了因果关系违背，但是它并没有解决数据 不一致这个问题。 状态向量：每个站点拥有一个n 维的向量，例如，站点i 的状态向量 s v ；的第j 个分量s v i j = k ，表示所有从站点j 生成并且发送到站点i 执行的 操作数目为k 。 操作请求 ：d p 是站点i 生成的操作，s v 是站点i 执行 操作溯寸的状态向量，p 是操作口p 的优先权( 优先权数和站点标识相关， 站点标识越大，优先权越高) 。 操作队列：q 。表示站点i 将从其他站点接受到的操作和本地生成的操 作放入队列，等候执行( 不是严格意义上的先进先出) 。 探作日志：l 。表示第i 个站点记录的所有在该站点执行过的操作( 包 括本地生成的操作和其他站点发送过来的操作) ，例如，l t 中记录的一个 操作请求 表示当站点i 的状态向量为s v 时执行产生于站点 j 的操作印。 算法简述： 站点j 生成一个操作印，先在本地执行，然后生成一个关于操作o p 的优先权数p ，最后将操作印本身和优先权数p 及状态向量s v 一起发送 到其他所有站点。 站点i 接收到操作印，比较印的状态向量s v ，和本地站点的状态向 量s v j ： s v 。 s v ，那么存在操作在站点j 执行过而没有在站点i 执行，将操 作印放入操作队列q ；，等候执行。 s v 。- - s v ；，执行操作印，存入操作日志l ；。 s v 。 s v ，从操作日志l ；中检索出已经在站点i 执行过但没有在站点 j 执行( 在操作0 p 生成之前) 的操作，变换操作o p ，执行操作o p ，存入 操作日志l 。 第二章协同编辑算法的概述 一种协同蝙辑算法的研究和设计 从本质上看，d o p t 算法采用了包含变换( i n c l u s i o nt r a n s f o r m a t i o n ) ， 即变换操作o p l ，将它的并发操作蚴对文档的影响包含进来。变换函数考 虑四种情况：( 插入，插入) 、( 插入，删除) 、( 删除，插入) 和( 删除， 删除) 。 时间 站点3 站点1 站点2 o p 3 o p 2 图2 1d o g r 算法的一个反例 如图2 - 1 ，文档初始状态为空。站点3 生成操作o p s = i n s e r t “c ”，0 ； 操作o p t = i n s e r t “a ”，0 到达后文档状态为“a c ”；操作 o p t = i n s e r t “b ”，0 到达，因为操作州0 1 ) 3 ，操作0 1 ) 2i io p l ，所以操作 p 函先变换为o p t = i n s e r t “b ”，1 ( 操作p 功的优先权比o p z 高) ，然后变 换为o p t = i n s e r t “b ”，2 ；站点3 的文档结果为“a c b ”。 站点1 上操作的执行次序和文档结果与站点3 相同。 站点2 生成操作o p 2 ；操作蛳到达，虽然川o p z ，但是操作，的 优先权比o p 2 高，所以，不需要进行变换，操作o p 3 执行以后，文档状态 为“c b ”；操作印，到达，因为操作i i 。操作o p l 的优先权比，低， 所以操作m 变换为o p ：= i n s e r t “a ”，1 ，操作o p ：不用再一次变换( 瓣 一o p ，) ，文档结果为“c a b ”。我们可以看到站点2 的结果与站点3 、站点 1 不一致。 一种协同犏辑算法的研究和设计 第二章协同糖辑算法的概述 d o p t 算法不能保持数据致性的根源在于简单的站点优先权策略 ( 优先权数和站点标识相关，站点标识越大，优先权越高) 。事实上， 当发生一个操作和多个操作并发的情形时，d o p t 算法就无法解决它们的 一致性了。 2 2 2a d o p t e d 算法 a d o p t e d 算法由m r e s s e l 和r g u n z e n b a u s e r 在1 9 9 6 年的c s c w 年 会上撰文提出。a d o p t e d 算法引入l 变换( l - t r a n s f o r m a t i o n ) 以取代 d o p t 算法的包含变换，这是a d o p t e d 算法与d o p t 算法的唯一区别。 a d o p t e d 算法保证了因果关系维护和操作意愿维护，基本解决了数据不一 致问题。 a d o p t e d 算法采用一个n 维( n 是站点数) 的交互图保存所有操作可 能的形式( 生成、中间和执行) 和一个线性日志保存操作的生成形式。 站点3 和站点l 的路径 幽2 - 2a d o p t e d 算法的解决过程 如图2 2 ，我们以d o p t 算法的一个反例为对象，给出a d o p t e d 算法 的解决过程。在站点3 和站点1 ，操作按以下同一路径进行变换和执行： 操作叩，和印，先后执行，操作吼依次变换为o p ；= i n s e r t “b ”，1 和 o p ：= i n s e r t “b ”，2 ( 其间，a d o p t e d 算法产生o p ：= i n s e r t “c ”，0 和 o p ：= i n s e r t “a ”，0 ，只是没有在站点3 和站点1 使用而己) ，操作，、 第二章协同编辑算法的概述 一种协同蝙辑算法的研究和设计 o p l 和印；执行以后的文档结果为“a c b ”。 在站点2 ，路径则完全不同，操作o p e 先执行，操作，到达后，变 换为叫= i n s e r t “c ”，o ，与此同时，o p 2 = i n s e r t “b ”，1 ；操作o p l 到达，a d o p t e d 算法以操作碱为基础( d o p t 算法以o p ：为基础) 变换操 作印，为o p ：= i n s e r t “a ”，0 ( 其间，a d o p t e d 算法产生 o p t = i n s e r t “b ”，2 ，只是没有在站点2 使用而已) ，操作o p 2 、叫和o p ： 执行以后的文档结果为“a c b ”。 三个站点的文档结果一致，a d o p t e d 算法好像完全解决了数据不一致 问题。事实上，我们找到了一个反例证明单纯依靠l 变换和多维图不能 完全解决数据不一致问题。 朗虻o p l ：h 嚷。j - 2 l a i 良i c 图2 - 3a d o p t e d 算法不能完全解决数据不一致问憩 如图2 - 3 ，文档初始状态是“a b c ”，站点l 生成操作 o p t = i n s e r t “l ”，2 ，站点2 生成操作o p t = i n s e r t “2 ”，1 ，站点3 生 成d e l e t e 1 ，1 。我们注意到沿着不同的路径变换和执行三个并发操作得 到了不同的文档结果“a 2 1 c ”和“a 1 2 c ”。当两个插入操作指向同一个位 置时，a d o p t e d 算法约定对站点标识稍大的那个进行变换，这样问题表面 上解决了。此例中，我们将站点1 和站点2 的标识互换，那么数据不一 一种协同编辑算法的研究和设计 第二章协同墒辑算法的概述 致还是没有解决! 所以我们只能说a d o p t e d 算法基本解决了数据不一致 问题。 2 2 3g o t g o t o 算法朝6 1 1 9 9 7 年，c h e n g z h e n gs u n 等人在总结d o p t 算法和a d o p t e d 算法的 基础上提出了一种基于操作变换的g o t 算法。数据不一致问题由操作的 全局次序和u n d o d o r e d o 策略解决，因果关系违背由状态向量解决，操 作意愿违背由包含变换( i n c l u s i o nt r a n s f o r m a t i o n ) 和剔除变换 ( e x c l u s i o nt r a n s f o r m a t i o n ) 一起解决。 c o p ：操作印的执行形式，日厕i 一定总是等于d p 。 历史缓存曲( h i s t o r yb u f f e r ) ：每个站点用来保留所有在该站点 执行过的操作( 执行形式) 。 操作的全局排序“等。：给出两个操作瘌。，印0 虹生于站点i ， 晒产生于站点j ，状态向量分别为和，那么纰j o p b ，当且仅当 ( 1 ) s u m ( s v ，) s u m ( ) ，或者( 2 ) s u m ( 6 y o ) = s u m ( ) ，i j ；其中 s u m ( s v ) = ：州司( 特别注意：此定义默认站点之间有序) 。 u n d o d o r e d o 策略： 一个新操作础过状态向量比较后可以执行，则分以下三步保持数 据收敛： 1 u n d o 历史缓存皿中所有全局排序在响。之后的操作，将文档恢复到 它们执行之前的状态： 2 执行操作啪。，存入历史缓存： 3 r e d o 所有刚才从历史缓存中u n d o 的操作。 比较g o t 算法和a d o p t e d 算法。一、g o t 算法采用线性的历史缓存 h b 来保存操作的执行形式，a d o p t e d 算法采用一个n 维的交互图保存所 有操作可能的形式( 生成、中间和执行) 和一个线性日志保存操作的生 成形式。二、保证数据收敛的方法不同。g o t 算法将数据收敛问题用操作 的全局排序和u n d o d o r e d o 方法处理，而操作意愿违背问题用包含变换 和剔除变换来解决。u n d o d o r e d o 方法从本质上看也是种变换，它以 第二苹协同编辑算法的概述 一种协同编辑算法的研究和设计 文档状态为对象，而不是操作本身。a d o p t e d 算法使用l 变换和多维图解 决了操作意愿违背问题，基本解决了数据不一致。三、g o t 算法的包含变 换和剔除变换除了可以解决操作意愿违背问题之外还支持在实时协同编 辑系统中的操作取消( u n d o ) 。 1 9 9 8 年，c h e n g z h e n gs u n 和c a e 1 l i s 在g o t 算法的基础上提出 一种优化算法g o t 0 算法。它借鉴d o p t 算法中的包含变换和a d o p t e d 算法中的l 变换的属性，扩展了g o t 算法中的i t 和e t 变换，无需 u n d o d o r e d o 策略或者多维图就解决了操作意愿违背和数据不一致。 g o t o 算法减少了包含变换i t 和剔除变换e t 的使用频率，一定程度上优 化了g o t 算法。 2 2 4s o c t 3 s o c t 4 算法蜘 2 0 0 0 年n i c o l a sv i d o t 等人在比较了d o p t 、a d o p t e d 、g o t 和g o t 0 算法的基础上给出了s o c t 3 和s o c t 4 算法。 从一致性维护的角度考察，我们有以下结果： 操作意愿维护：d o p t 和s o c t 4 算法采用包含变换，a d o p t e d 算法采 用l 变换，g o t 、g o t o 和s o c t 3 算法采用包含变换和剔除变换。 数据收敛：g o t 算法采用非连续的( 默许站点之间有序) 操作全局排 序和u n d o d o r e d o 策略，g o t o 算法采用改进的包含变换和剔除变换， s o c t 3 和s o c t 4 算法采用连续的操作全局排序和包含变换。 因果关系维护：d o p t 、a d o p t e d 、g o t 和g o t o 算法都采用了状态向量 ( s t a t ev e c t o r ) ，s o c t 3 和s o c t 4 算法采用了时间戳( t i m e s t a m p s ) 。 2 3 基于文档标注的算法“ 一致性维护是协同编辑算法必须解决的问题，其中的数据一致性和 因果关系维护可以通过一些传统的并发控制方法( 串行化和状态向量) 来解决，但是操作意愿维护只能由操作变换实现。操作变换思想主要研 究的对象是并发操作本身，后来，文档标注方法的研究对象是文档。下 面，我们简述文档标注算法。 一种锛同编辑算法的研宄和设计 第二章拼同编辑算法的概述 1 9 9 9 年，何鸿君等人提出了文档标注算法，它以文档本身为研究对 象。文档标注算法立足于共享文档本身。无论某一操作执行前发生了多 少并发操作，通过对共享文档加标注的手段，把并发操作执行所引起的 文档变化部分屏蔽起来，使该操作执行时的文档状态仍然与该操作产生 前瞬间的文档状态一致，从而实现操作意愿的维护。 站点i 的状态n s 。：在站点i 上已经执行过的操作序列。 操作卵的上下文c 如操作印产生时本地站点已经执行过的操作序 列。 算法简述： ( 1 ) 站点j 生成操作印，立即在本地执行；然后将操作印的上下文 c 和操作本身一起发送到所有其他站点。 ( 2 ) 站点i 比较c 乙和n s ；： ( i ) 存在操作o p 是c 的元素，并且不是n s ；的元素，表明操作o p 在站点j 执行过而没有在站点i 执行，延迟执行操作o p o ( i i ) c t 矿n s ；，执行操作。 ( i i i ) 检索n s 。，存在操作o p 是n s 。的元素，并且不是c 如的元素，表 明操作o p r 是操作印的并发操作，屏蔽操作对文档的影响；执行操作 印；显示操作o p 对文档的影响。 2 0 0 2 年，有人发表文章对文档标注算法进行了一些改进，引入了状 态向量以代替操作的上下文，站点产生操作以后，传送的状态向量的长 度是固定的。原有的文档标注方法当操作传送时必须将该操作的上下文 一起传送，它会随着操作的不断增加呈线性增长，这样做的代价太大。 文档标注算法解决了因果关系违背和操作意愿违背，但是没有给出 解决数据不一致问题的方案。 本章我们概述了各种协同编辑算法，它们基本维护了整体一致性模 型( c c i ) 。操作意愿违背由操作变换和文档标注方法解决，操作变换具 体可以分为包含变换、剔除变换和l 变换。因果关系违背由状态向量解 一种协同编辑算法的研究和设计 决，数据不一致由操作的全局排序、u n d o d o r e d o 策略解决。 一、如果我们将上下文一致维护引入c c i 模型，也就是说，扩展c c i 模型，那么必须对上述算法加以改进。二、无论是基于操作变换还是文 档标注，上述算法均没有对历史缓存进行有效管理。随着运行时间的延 长，系统的网络流量、操作的变换次数和比较次数都严格单调递增，系 统效率持续偏低。三、上述算法所基于的文档结构都是线性结构。 出于以上三点考虑，我们在下文给出g o t 2 t r e e g o t 2 算法，其中第 三章阐述g o t 2 算法，第四章阐述t r e e g o t 2 算法，第五章我们通过一个 原型系统进行算法正确性验证。 一种协同桷辑算法的研究和设计 第三章g f f f 2 算法 3 1 一些定义 3 1 1 系统结构 第三章g o t 2 算法 完全复制式结构：一共有n 个站点( s i t e ) ，每个站点有一个用户参 与，唯一标识为0 ，1 ，2 ，n - l 。每个站点保存一个编辑文本。 状态向量s v ( s t a t ev e c t o r ) ：生成操作站点的状态向量，每个站点 拥有一个n 维的向量，例如，站点i 的状态向量s v 。的第j 个分量s v 。 j = k ， 表示所有从站点j 生成并且发送到站点i 执行的操作数目为k ，站点i 执 行过一个从站点j 发送的操作以后，s v ； j = s v 。 j + 1 。 状态向量表s v t ( s t a t ev e c t o rt a b l e ) ：每一个站点拥有一个状态向 量表，它保存了n 个状态向量。s v t 。是站点i 的状态向量表，站点i 接收 到从站点j 发送的操作o p , o p 的状态向量是s v ，s v t 。的第j 个状态向 量s v t i j k = s v “k ( 0 k n - 1 ) 。s v t i 1 ( ( o k n - 1 ) 表示站点i 上保 存的站点k 的状态向量，当s v t 。 i = s v 。成立时，表示站点i 的状态向量 表s v t 。的第i 个状态向量是本地状态向量。 最小状态向量m s v ( m i n i m u ms t a t ev e c t o r ) ：每一个站点拥有一个n 维的最小状态向量，m s v ；是站点i 的最小状态向量。 m s v j k = m i n s v t i 0 k ，s v t i n 一1 k ，0 _ k _ n - 1 。 锁表l t ( 1 0 c k i n gt a b l e ) ：保存每一个站点执行过的加锁操作。锁 表的每一个表项代表一个用户拥有的一段加锁区域，所有表项代表文档 的加锁状态。一个加锁操作执行成功就是在锁表中加入一个表项，合并 同一个用户的几个表项，更新其他用户的表项；一个解锁操作执行成功 就是从锁表中删除一个表项或者切分一个表项。 3 1 2 基本操作 g o t 2 算法的基本操作有i n s e r t 、d e l e t e 、l o c k 和u n l o c k 四种，分 别如下： 1 7 苎三童曼塑! 苎堡一种协同编辑算法的研究和设计 i n s e r t s ，p ，在位置西处插入字符串s ； d e l e t e i n ，p ，从位置p 开始删除n 个字符； l o c k n ，p ，从位置p 开始锁定n 个字符； u n l o c k n ，p ，从位置p 开始解除n 个字符的锁定： p ( o p ) ：操作印的位置参数： l ( o p ) ：操作叩的长度，当印为插入操作时，表示插入的字符串长 度；当0 p 为删除操作时，表示删除的字符数；当印为加锁或者解锁操 作时，表示锁定或者解除锁定的字符长度； s ( o p ) ：插入的字符串。 3 1 3 操作关系 因果关系“一”定义： 给出两个操作蛳和o p b ，鲴。生成于站点i ，o p , 生成于站点j ，那么 o p , - * o p 。当且仅当：( 1 ) i = j ，o p 在蚴之前生成；( 2 ) i j ，在站点j ， o p 先执行，b 后生成：( 3 ) 存在操作0 1 9 , ，使得o p - o p x ，o p ；* o p b 。 独立性和依赖性定义： 给出两个操作o p 和o p h ，( 1 ) o p b 依赖于0 1 9 ，当且仅当q 品一吼：( 2 ) 9 风和o p h 相互独立( 它们是并发操作) ，记为o p 1 i 嘞，当且仅当蚴一 o p h 和鼢一0 1 9 都不成立。 操作意愿定义： 操作0 1 9 的