（计算机应用技术专业论文）一个协同编辑器中并发控制算法的研究与实现.pdf

一个协刚编辑器中并发控制算法的研究与实现摘要 摘要 实时协同编辑系统作为c s c w 的一个重要应用，近年来得到了广 泛研究。本文介绍了一种实时协同编辑算法及其在协同编辑器z o f f i c e 中的设计与实现。 本文首先对现有多种协同编辑并发控制算法g o t 、d o p t 、a d o p t 、 s o c i c 2 、s o c k 3 、s o c k 4 等进行了比较和分析，并介绍了当前一些实 验性的原型系统。接着，给出了根据z o f f i c e 实际应用需求而改进并设 计的g o t 3 算法，重点介绍了其中的子函数、上下文一致性算法、焦点 维护算法和历史缓存清洗算法。然后，详细阐述了协同编辑器z o f f i c e 中协同编辑处理模块的设计与实现。最后给出了协同编辑处理模块的功 能演示与测试结果。 本文分析研究了协同编辑器需要解决的一些关键问题，设计和实现 了z o f f i c e 中协同编辑处理模块的并发控制算法，使协同编辑器具备了 有效稳定的实时协同处理能力，并且提高了协同编辑器的灵活性、实用 性和通用性。 关键字：协同编辑、操作变换、焦点维护、历史缓存 作者：景栋盛 指导老师：杨季文 a b s t r a c t t h e r e s e a r c ha n d i m p l e m e n t a t i o no f a c o n c u r r e n c y c o n t r o l a l g o r i t h m i na c o o p e r a t i v ee d i t i n gs y s t e m t h er e s e a r c ha n d i m p l e m e n t a t i o no fac o n c u r r e n c y c o n t r o la l g o r i t h mi na c o o p e r a t i v ee d i t i n gs y s t e m a b s t r a c t t h er e s e a r c ht o p i co fr 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 ，w h i c hi s o n eo ft h ec l a s s i ca p p l i c a t i o n s0fc s c w , i sg r e a t l ye m p h a s i z e di nr e c e n t y e a r s t h i sp a p e r i n t r o d u c e sa l le n h a n c e dr e a l t i m ec o o p e r a t i v ee d i t i n g a l g o r i t h ma n dg i v e st h ed e s i g na n di m p l e m e n t a t i o no fg o t 3i n ar e a l c o o p e r a t i v ee d i t i n gs y s t e m ，z - o f f i c e t h er e c e n tr e s e a r c hst a m so fc o o p e r a t i v ee d i t i n ga l g o r i t h m s ，s u c has g ot ，d o p t , a d o p t , s o c k 2 ，s o c k 3 ，s o c k 4a n ds oo n ，a r es t u d i e di nt h i s p a p e r a n dt h ee x p e r i m e n t a lp r o t o t y p es y s t e m si n r e s e n ty e a r sa r ea l s o d i s c u s s e d t h e n ，a c c o r d i n gt ot h er e a la p p l i c a t i o nd e m a n d s ，g o t 3e n h a n c e s s e v e r a l p o i n t s s u c ha sc o n t e x t c o n s i s t e n c y , f o c u s m a i n t e n a n c ea n d h i s t o r y b u f f e r - c l e a n i n g t h e d e t a i l e d d e s i g n a n d i m p l e m e n t a t i o n o f c o o p e r a t i v ee n g i n e i nz o f f i c ea r e d e s c r i b e d f i n a l l y , t h e f u n c t i o n a l d e m o n s t r a t i o na n dt e s tr e s u l to fc o o p e r a t i v ee d i t i n gm o d u l ea r ep r e s e n t e d t h i sp a p e ra n a l y z e ss o m ek e yi s s u e so fc o o p e r a t i v ee d i t i n gs y s t e m a n dac o n c u r r e n c yc o n t r o la l g o r i t h mi nac o o p e r a t i v ee d i t i n gi si n t r o d u c e d ， w h i c hp r o v i d e st h es t a b l ea n de f f e c t i v es u p p o r tf o rt h ec o o p e r a t i v ee d i t i n g s y s t e m i te n h a n c e sf l e x i b i l i t y , p r a c t i c a l i t ya n dc o m p a t i b i l i t yo f t h eo r i g i n a l c o o p e r a t i v ee d i t i n gs y s t e m k e y w o r d s ：c o o p e r a t i v ee d i t ，o p e r a t i o nt r a n s f o r m a t i o n ，f o c u s - m a i n t e n a n c e ， h i s t o r yb u f f e r w r i n e nb yj i n gd o n g s h e n g s u p e r v i s e db yy a n gj i w e n i i y9 5 g s g o 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不含其他个人或集体已 经发表或撰写过的研究成果，也不含为获得苏州大学或其它教育机构的学位证书 而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中以明确 方式标明。本人承担本声明的法律赏任。 研究生签名：邋日期j 、岁2 9 学位论文使用授权声明 苏州火学、中国科学技术信息研究所、国家图书馆、清华大学论文合作部、 中幽社科院文献信息情报中，l l , 有权保留本人所送交学位论文的复印件和电子文 档，j 以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相，一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以 公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括干嶝e ) 授权苏州大 学学位办办理。 研究生签名 导师签名： 躲盈f 1 期 2 0 0 s 5 。返 一个协同编辑器中并发控制算法的研究与实现 第一章绪论 1 1 引言 i i i 背景 第一章绪论 随着网络技术的发展和分布式系统的日益普及，计算机应用正从传 统的单用户工作模式向多用户协同工作的方向发展。在信息化社会中， 各种工作变得越来越复杂，人们工作的特点是群体性、交互性、分布性 和协作性。以前完成一项工作可能只要一个人或几个人就能胜任，现在 就大不相同了，许多工作的完成都是众人智慧的结晶。因此，如何方便 多人合作，更规范、有序、高效地解决问题显得越来越重要。 计算机支持的协同工作( c o m p u t e rs u p p o r t e dc o o p e r a t i v ew o r k c s c w ) 是利用计算机和通信技术建立一个协同工作环境。c s c w 是1 9 8 4 年由美国m i t 的艾琳骼雷夫( i r e ng r i e f ) 和d e c 的保罗卡什曼( p a u l c a s h m a n ) 在一个专题讨论会上首次提出，目的是利用多媒体技术和通信 技术建立一个协同工作的环境。在此环境中人们可以相互合作，共同工 作于一个产品、一个研究领域、个项目或求解学术上的同一难题。计 算机支持的协同工作的发展正是适应了信息社会中人们工作方式中的 上述特点。因此，它被认为是未来社会中将被广泛采用的技术。随着计 算机通信、分布式计算机、多媒体技术等的发展，c s c w 目前正从概念 逐步走向应用，在军事、工业、医疗、科研等许多领域发挥越来越重要 的作用。 实时协同编辑系统( c o m p u t e r s u p p o r t e dr e a l t i m ec o o p e r a t i v e e d i t i n gs y s t e m ) 是c s c w 系统的一类重要应用，它支持地理上分散的 用户通过网络在同一时间浏览和编辑一个共享的文档、图形或者多媒体 文件，可以消除人们在时空上分隔的障碍，节省工作人员的时间和精力， 并且可以大大提高群体的工作效率。它允许多用户对协作文档进行操 作，能够最大限度地发挥群体工作效率。实时协同编辑系统主要有以下 三个特点心1 ：一、实时性( 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 ) ，为了使信息在协同用户之间自由和自然地流动， 若干协同用户可以在任何时间并发，自由地编辑共享文档的任意部分。 实时协同编辑系统与传统应用系统相比，增加了新的内容，发生了 质的变化。实时协同编辑系统是继承传统应用的相关技术和内容，并在 其上发展起来的。例如协同编辑系统的系统结构与分布式系统相似，包 括集中式、复制式和混合式结构；以及协同编辑系统中的并发控制算法 的状态向量、加锁等。通过建立协同工作的环境，改善人们信息交流的 方式，减少人们在空间上相互分割的障碍，可节省编辑人员的时间和精 力，提高群体工作效率和质量，实时协同编辑系统向人们提供了一种全 新的工作环境和交流方式。计算机网络技术、软件技术等的飞速发展推 动了实时协同编辑系统的发展，使之应用于越来越多的领域。 目前各种实时协同编辑系统由于多种原因仍存在不足啡1 ，对于各种 并发控制算法的改进和论证仍然是研究的热点。这些协同编辑并发控制 算法，大部分是基于完全复制式结构，通过操作变换实现共享文档的一 致性维护。 本文根据实际开发的协同编辑器z - o f f i c e 应用需求，在g o t “1 算法 的基础上改进并设计了焦点维护方法、历史缓存清洗方法以及一些子函 数的扩展，并且将其应用到协同编辑器中。 1 1 2 协同编辑体系结构 协同编辑系统的体系结构可以划分为如图卜1 所示的三种基本类 型。 一个协i 卅编辑器中并发控制算法的研究与实现第一章绪论 ( i ) 集中式结构( ) 分布式结构c ) 混合式结构 函1 - 1 三种体系结构 集中式体系结构 这种系统结构采用c l i e n t s e r v e r 结构，如图1 - 1 ( i ) 所示。优点 是：一、系统实现简单( 一般采用先来先服务的原则) ；二、文档只有 一个版本，加锁法实现简便。缺点是：默许了悲观思想，当站点的规模 很大时，系统运行非常迟缓，缺乏灵活性，可靠性较差，而且不易扩展。 完全复制式体系结构 完全复制式( 分布式) 系统结构与集中式结构不同的地方在于，当 多个用户同时对一个文档进行编辑时，每个用户站点分别保存该文档的 一个副本，并且这些文档副本保持实时的数据一致，如图卜1 ( i i ) 所示。 分布式系统具有较好的灵活性、可靠性、可扩展性。但是实现复杂，难 以集中管理，必须由专门算法来实现并发控制，以维护各站点的数据一 致性。在实时协同编辑系统中，由于网络带宽和传输速率的限制，为了 提高系统的响应速度，特别是保证尽量快的本地站点响应速度，一般都 是把共享文档复制到本地站点，即完全复制式结构。 混合式体系结构 集中式结构和分布式结构各有优缺点，单纯地采用某种结构都不能 很好地实现一个协同编辑系统。在已经开发的协同编辑系统中，大多数 是将集中式结构和分布式结构结合在一起，采用混合式体系结构，如图 1 - 1 ( 1 1 1 ) 所示。 第一章绪论一个协同编辑器中并发控制算法的研究与实现 i i 3 传统方法 实时协同编辑系统有三种不一致情况，分别是数据不一致 ( 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 ) 三个方面。1 。上下文不一致不同于上述三种不一致情况， 它涉及到文档的比较、语法的检测和内容判断，完全解决具有相当的难 度，目前只能利用加锁方法解决这个问题陆“。 令牌( 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 ) 并发操作在每一个站点都以同样的次序执行，从而产生完全一致的 一个协同编辑器中并发控制算法的研究与实现第一章绪论 文档。通常由两种方法实现：一、一个操作的执行悲观延迟，直到所有 排列在前的操作执行完毕；二、一个操作乐观执行，然后采用u n d o r e d o 策略消除操作超前执行的影响。串行化可以解决数据不一致；通过调整 操作之间的次序，串行化不能解决操作意愿违背；如果悲观延迟一个操 作的执行，虽然保证了本地站点操作之间的因果关系，但是所有操作的 因果次序是不一致的；如果乐观执行一个操作也不能保证操作的因果关 系；一些操作的执行经过悲观延迟以后可能造成响应缓慢。 因果次序( c a u s a lo r d e r i n g ) 并发操作在自然的因果关系约束下执行，依靠逻辑时钟向量 ( v e c t o rl o g i c a lc l o c k ) 或者状态向量( s t a t ev e c t o r ) 来实现，它 是一种被许多分布式计算系统所采用的典型技术。本地站点生成的操作 立即执行，符合实时性要求；接收的远程操作必须等待所有的原因操作 执行完毕，才能执行。状态向量解决了因果关系违背，但不能解决数据 不一致和操作意愿违背问题。 基于操作交换的算法 由于传统的并发控制方法没有取得理想效果，e l l i s 和g i b b s 于 1 9 8 9 年发表文章晗3 提出了操作变换思想，他们的基本思想是并发操作执 行前先变换，然后在各站点以不同的次序执行，最后各站点的文档状态 保持一致。显然，操作变换方法可以解决操作意愿违背的问题，这是传 统的并发控制方法所无法做到的。所以，操作变换具有划时代的意义， 它使得实时协同编辑系统的设计和实现真正成为可能。实际的算法设计 中，操作变换方法和状态向量一起使用，以此来解决数据不一致和因果 关系违背问题。本文2 1 节中将概述各种基于操作变换的协同编辑算法。 1 1 4 一个协同编辑问题情景描述 本文假设每次协同编辑会话共有n 个站点( s i t e ) 参与，为完全复 制式结构，每个站点有一个用户参与，唯一标识为0 ，1 ，2 ，n l 。 编辑操作有插入i n s e r t 、删除d e l e t e 、加锁l o c k 、解锁u n l o c k ，定义如 下： 5 一 第一章绪论 一个协同编辑器中并发控制算法的研究与实现 i n s e r t s ，p ，在位置p 处插入字符串s ； d e l e t e n ，p ，从位置p 开始删除n 个字符； l o c k n ，p 】，从位置p 开始n 个字符加锁； u n l o c k n , p ，从位置p 开始1 1 个字符解锁； p ( o ) ，操作0 的位置参数； t ( 0 ) ，操作0 的操作类型； l ( o ) ，操作0 的长度，当0 为插入操作时，表示插入的字符串长度； 当0 为删除操作时，表示删除的字符数； s ( 0 ) ，插入的字符串。 一个n 等于3 的协同编辑系统有三个站点，分别是站点0 、站点l 和站点2 。各站点生成的操作立即在本地执行，然后发送到其他所有站 点保持原来的形式执行。三种不一致情况将在以下情景中发生，如1 2 所示。 e i t e o舶1 酶e 2 图卜2 个协同编辑问题的情景描述 数据不一致 系列操作在不同的站点可能以不同的顺序抵达并且执行，导致不同 的结果。如图卜2 ，操作0 l 、0 2 、0 4 和0 3 在站点0 依次执行，操作0 2 、 一个悱同编辑器中并发控制算法的研究与实现第一章绪论 0 1 、0 3 和0 4 在站点1 依次执行，操作0 2 、0 4 、0 3 、和0 l 在站点2 依 次执行，三个站点上的操作的执行次序完全不同。数据不一致可以通过 串行化方法解决，从而保证所有操作以相同的顺序在各个站点执行。 因果关系违背 由于网络延迟的不确定性，操作可能违背之前的因果顺序到达且执 行。图卜2 中，站点1 在操作o l 到达以后生成操作0 3 。当生成操作0 3 的时候，站点l 的用户看到了操作o ，对文档的编辑效果。所以，操作 0 3 依赖于( d e p e n d e n t ) 操作0 1 。然而，当操作0 3 和操作o 。在站点2 先后执行时，站点2 的用户会陷入一片混淆。比如：操作0 ，插入一个 字符串“a b c d e ”，操作0 3 删除字符串中的“b c d ”，那么当操作0 ，在站 点2 执行的时候出现矛盾。因果关系违背可以推迟一些操作的执行，利 用状态向量来保证操作按照因果顺序执行。 操作意愿违背 由于并发操作的产生，一个操作执行后的实际效果( 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 生成操作 0 ，此时站点0 的用户没有意识到站点1 生成了操作0 2 ，所以操作o 。 独立( i n d e p e n d e n c e ) 于操作0 2 。操作o l 在站点o 执行，文档状态随 之发生改变，然后操作0 2 到达站点0 ，执行。操作0 2 在站点0 执行时 的文档状态与它在站点1 生成时的文档状态不同，导致操作o ：的实际 效果和它生成时的意愿不一致。比如，文档的初始状态为“a b c d e ”， 0 l = i n s e t “1 2 ”，1 】，意愿是在“a ”和“b c d e ”之间插入“1 2 ”；o z = d e l e t e 2 ，2 ， 意愿是删除“c d ”。两个操作执行后，在操作意愿得到维护的情况下， 三个站点的文档结果都应该是“a 1 2 b e ”。然而，站点0 在操作0 1 和0 2 先后执行以后的结果是“a i c d e ”，它同时违背了操作0 1 和0 2 的意愿。 即使采用串行化的方法来处理，三个站点的结果都是“a i c d e ”，还是违 背了操作0 1 和0 2 的意愿。 数据不一致和操作意愿违背的本质区别是前者可以利用串行化解 决，后者如果不改变操作本身就执行，那么串行化方法不能解决。此时， 必须引入操作变换才能解决。 第一章绪论一个协同编辑器中并发控弗4 算法的研究与实现 上下文不一致 除了上述三种一般的不一致情况，还有一种特殊的不一致情况：上 下文不一致。比如，当前共享文档为“t h e r ew i l lb es t u d e n th e r e ”， 由于存在语法错误，所以站点0 生成操作0 ，意愿是在“s t u d e n t ”前 面插入一个“a ”，站点l 生成操作0 2 ，意愿是在“s t u d e n t ”后面加上 “s ”。假设给出一种算法解决了操作意愿违背的问题，那么两个站点的 文档结果应该都是“t h e r ew i i ib eas t u d e n e sh e r e ”。虽然操作意 愿违背和数据不一致都得到了解决，但是文档结果还是存在着语法错 误，或者说上下文不一致。由此说明，上下文不一致不能简单地用串行 化、状态向量和操作变换等方法来处理，必须由用户亲自干涉或者其他 技术手段支撑才能解决。加锁是目前一个十分有效的解决上下文不一致 的手段，它限制不同用户同时并发地编辑同一段区域僻。 1 2 协同编辑器z - o f f i c e 概述 图1 - 3 协同编辑器z 一0 伍c e 启动界面 协同编辑器z o f f i c e 项目系苏州大学2 1 1 重点建设子项目：z o f f i c e 重点攻克了实时协同问题，增强了相关特色，是面向办公文档的协同工 作的基础核心。同时，苏州大学计算机科学与技术学院于2 0 0 5 年8 月 获准成立“国家l i n u x 培训与推广中心”，该中心当时申报时明确提出 要以自主知识产权的l i n u x 办公环境任务为特色，本项目是实现这一目 一个协问编辑器中并发控制算法的研究与实现第一章绪论 标的重要基础。 协同编辑器z o f f i c e 将工作流与协同编辑技术有机结合，从而保证 文档编辑过程的规范、有序、稳定和便捷，从而明显提高工作效率。协 同编辑器z o f f i c e 的总体研究目标是设计一个运行在广域网中、基于工 作流的实时协同编辑器，支持工作流的定义、编辑，使得分布在不同地 域的人员在工作流引擎的流转下可以方便、高效、有序地进行文档实时 协同编辑，z o f f i c e 启动界面如图1 3 所示。 1 3 课题内容与意义 1 3 1 课题内容 实时协同编辑算法的分析与研究。分别比较了d o p t 、a d o p t 叭、 s o c k 2 1 0 】、s o c k 3 11 1 、s o c k 4 1 等算法的优劣，并对g o t 、g o t 2 1 2 】 算法进行了较为深入的研究。 g o t 3 算法的提出。针对协同编辑器z o f f i c e 的需求，对于g o t 协 同算法进行了改进和扩展，分别实现了基于字符串的实时协同、焦点维 护、历史缓存清洗等子算法，本文将这些改进统称为g o t 3 算法。 协同编辑引擎的设计与实现。以g o t 3 算法为基础设计了一个能够 处理协同编辑常用功能的引擎，并为协同编辑系统提供通用接口，上层 应用程序可以调用内核算法实现操作保存、操作变换、操作清洗及登入、 登出等功能。 在协同编辑器z o f f i c e 中的应用。以g o t 3 算法为基础的协同编辑 引擎为苏州大学2 1 l 重点建设子项目一协同编辑器z 。o f f i c e 提供了有 效、稳定的协同编辑能力。 1 3 2 课题意义 为基于操作变换的协同编辑算法研究作出了探索与实践。 为满足实际应用的需求，扩展了g o t ，g o t 2 算法。g o t 2 算法在 一定程度上扩展了g o t 算法，用加锁的方法实现了上下文一致性维护。 第一章绪论一个涛同编辑器中并发控制算法的研究与实现 g o t 3 则针对协同编辑器z o f f i c e 的需求，较之g o t 2 算法提出了焦点 维护和历史缓存清洗等策略，同时，g o t 3 算法通过实践验证了其正确 性。 为协同编辑器z o f f i c e 提供了有效稳定的实时协同处理能力。维护 共享文档的一致性是在完全复制式环境下设计和应用协作编辑系统的 一个最有意义的问题，本文在协同编辑器中完全实现了一致性的维护， 还提供了焦点维护、历史缓存清洗、加锁解锁等功能。 有助于实时协同编辑系统研究的普及和应用。就目前的状况而言， 协同编辑系统方面的相关研究仍然处于未成熟阶段，只是产生了一些基 本的原型系统，并且由于实现环境和重视程度等各种约速条件，成型、 可应用的协同编辑系统仍然较少。随着j a v a 技术的不断成熟以及本身 合理化、便捷化的发展，j a v a 技术所特有的跨平台性、面向对象性非常 适于协同编辑系统的开发。在充分利用j a v a 技术面向网络程序设计的 基础上，研究并开发协同编辑系统，将是一项具有广泛应用前景并且十 分有意义的工作。 1 4 本文结构 本文其余部分： 第二章叙述了一些传统的并发控制方法，概述了基于操作变换思想 的d o p t 、a d 0 p t e d 、g o t 、g o t 2 、s o c t 3 、s o c t 4 等算法。 第三章给出一种协同编辑算法- g o t 3 算法，并从子函数，焦点维 护、上下文一致维护和历史缓存清洗等方面做了介绍。 第四章首先介绍协同编辑器z o f f i c e ，概述了它的功能和特点；然 后，详细叙述了g o t 3 算法在z o f f i c e 的协同编辑处理模块中的设计与 实现。 篇五章给出了z o f f i c e 的应用演示，并在协同编辑器中对于一些实 时协同典型情景进行了测试并列出了结果。 第六章是总结和展望。对所研究的协同编辑器的特点与不足作了分 析和说明，并提出了进一步的研究方向。 一个协i 司编辑器中并发控制算法的研究与实现第二章研究现状 第二章研究现状 本章对多种协同编辑并发控制算法，包括传统的令牌环和加锁方 法、d o p t 、a d o p t 、s o c k 2 、s o c k 3 、s o c k 4 、d a r b 、g o t 、g o t 0 和g o t 2 进行了比较和分析，说明了当前协同编辑算法的现状。然后介 绍了当前一些实验性的原型系统。最后总结了实时协同编辑的需求、特 点和难点。 2 1 协同算法比较 2 1 1 令牌环，加锁方法 加锁是传统分布式计算和分布式数据库中的一种标准技术，它禁止 用户对共享数据并发操作，以此保证数据的一致性。加锁应用于协同编 辑系统就是一个操作对象( 单词、句子或者段落) 在编辑之前必须先被 锁定，限制多个用户对该对象进行编辑，以此支持多用户的并发操作， 解决文档上下文不一致问题。当加锁的粒度是整个文档时，退化为令牌 策略，此时一致性维护可以得到实现，但无法实现多用户并发操作。在 分布式环境下，加锁操作本身也需要一致性维护。 2 1 2d o p t 算法 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 ) ，从而解决了因果关系违背，但是d o p t 算法由于保持数 据致性的站点优先权策略过于简单( 优先权数和站点标识相关，站点 标识越大，优先权越高) ，并没有解决“偏并发”时的数据不一致性问 题。 第二= 章研究现状一个执同编辑器中并发控制算法的研究与实现 2 1 3a 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 在19 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 算法保证了因果关系维护和操作意愿维护，似乎完全解决了数据不一致 问题。但事实上，在文献【5 】中就用一个反例证明了单纯依靠l 变换和多 维图不能完全解决数据的不一致问题，如图2 1 所示。 b co 斛l 嘲 窘l c 图2 1a d o p t e d 算法不能完全解决数据不一致问题 2 1 4s o c k 2 ，s o c k 3 ，s o c k 4 算法 m i c h e l l ec a r t 等人于1 9 9 7 年首次提出s o c k 2 算法，2 0 0 0 年文献 【】中提出了s o c k 3 和s o c k 4 算法。s o c k 2 第一次提出了向前置换 ( t r a n s p o s ef d ) 、向后置换( t r a n s p o s eb k ) ，号称解决了并发算法的“偏 并发”问题。在s o c k 2 算法中，各个站点历史缓存中的操作全局序是 不一致的，如两个不同站点同时并发的两个操作，通过向前置换在h b 中的排列次序( 若不受其他操作影响) 是相反的。s o c k 2 算法的基本 思想是利用向后置换调整历史缓存，然后利用向前置换去除其它并发操 作的影响，以使操作的执行效果在各个站点都可以保持与定义时致。 s o c k 3 ，s o c k 4 算法排除了对于c 2 9 】的依赖，而且不需要对已执行的 一个协吲编辑器中并发控制算法的研究与实现第二章研究现状 操作进行u n d o 、r e d o 操作。s o c k 3 算法的基本思想是利用一个全局计 数器( s e q u e n c e r ) ，使得所有站点通过向前置换本地操作后，远程操作 能通过向后置换历史缓存获得一个唯一的全局次序，保证了所有站点的 最终结果唯一性。其缺点是实现依赖于这个中心全局计数器的稳定连 接，在分布式环境下运行的稳定性受影响。s o c k 4 简化了s o c k 3 算法， 各个协同站点无需使用向后置换就可以维持所有站点的最终一致性，但 是对于全局计数器的依赖更加明显，使得算法只适用于局域网，无法在 网络延迟明显的网络( 如i n t e m e t ) 中使用。 2 1 5d a r b 算法 d a r b 【l 叫算法的主要优点是能简化使用和具有较好的响应时间。算 法可以被应用在一般的协作系统中，唯一的限制是数据层必须应用树型 结构。每个站点口以树型结构保存本地的共享文档a 。每个节点都存 在一个唯一辅助i d 。节点同样保存着这个站点已成功执行的操作的数 目，以用来决定操作的全局序c o u n t ( v e r t e x i d ) 用来获得这个数目。事 件三元组可以表示成为8 - ，其中口表示事件产生站点的i d ，d 记录包括操作类型等各种关于操作的基本信息以及其他一些参数，p 表 示从根节点到目标节点的路径，优先权策略被包含在d 中，p 中仍然保 存着对应于节点的操作数量。 在该算法中，当多个操作同时存取某个相同的站点时，如多个用户 并发修改同一个词，树型结构的一致性将无法得到维护，d a r b 算法使 用p e r f o r m a r b i t r a t i o n 来处理冲突的结果。在操作非重叠时，由偏序关系 来维护树型结构的一致性；如果操作重叠但存取不同的节点，这样的操 作在逻辑上不冲突，偏序关系仍然可以维护共享文档的一致性；当两个 或更多的操作重叠且存取同一节点时，a r b i t r a t i o n 步骤被激活，这时候 每个站点都会产生一个特别的消息以防止其他站点在此时改变这个对 象。如图2 2 所示，三个站点对于相同节点的操作分别在乙，z ，z ， 所有站点通过全局序通道向所有用户广播，所有站点都以相同的全局序 接收包含优先权的消息m 。优先权最高的站点消息被首先广播，接收后 第二章研究现状 一个协同编辑器中并发控制算法的研究与实现 就获得选择处理冲突的权利，并通过u 向其他站点发送更新消息。其他 站点接收更新消息u 后，更新本地共享文档并恢复到实时协同状态。这 个算法可以被使用在所有文档结构为树型的应用中，作为一种独立的模 型，算法还可以在具体实际应用中扩展。 s i t e a s i t e l 3s i t e7 图2 2 三个站点的冲突裁决处理 2 1 6g o t g o t o 算法 g o t 算法是c h e n g z h e n gs u n 等人在文献【4 】中第一次提出的，算法 的目的是通过i t ( i n c l u t i o nt r a n s f o r m a t i o n ) 和e t ( e x c l u t i o nt r a n s f o r m a t i o n ) 实现“操作定义时的文档对象状态与操作执行时的文档对象状态一致”， 在保证一致性的同时维护了用户操作意愿。g o t 算法的核心是通过 g o tc o n t r o ls c h e m e 和u n d o t r a n s f o r m - d o t r a n s f o r m - r e d os c h e m e ，当 执行远程站点满足因果关系的操作o 时，o 的所有并发操作对于本地文 档对象的影响都已经被u n d o ，在执行o 后再r e d o 所有u n d o 的操作。文 献 5 】中，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 o 算法。它借鉴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 策略或者多维图就可解决操作意愿违背和数据不一致。 一个协刚编辑器中并发控制算法的研究i j 实现第二章研究现状 g o t o 算法减少了包含变换i t 和剔除变换e t 的使用频率，一定程度上 优化了g o t 算法。 2 1 7g o t 2 算法 2 0 0 5 年，g o t 2 算法将上下文一致维护引入c c i 模型】，扩展为 c c i c 模型，扩展后整体一致性模型( c c i c ) 如下： ( 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 ) 如果操作0 。一o b ，那么在任意一个站点，操作o 。必须在0 b 之前执 行。 ( 3 ) 操作意愿维护( i n t e n t i o np r e s e r v a t i o n ) 在所有站点执行操作0 的效果和操作0 的操作意愿一致，操作o 的执行不能影响到其他并发操作的执行。 ( 4 ) 上下文一致维护( c o n t e x t s p e c i f i cp r e s e r v a t i o n ) 每个站点上的文档都保持上下文一致，即时态语态的一致和代词、 名词、单复数的一致( 英语语法) ，针对这个模型给出了g o t 2 算法， 它解决了实时协同编辑系统的数据不一致、因果关系违背、操作意愿违 背和上下文不一致四种不一致情况，满足了实时协同编辑系统的三个特 点：实时性、分布性和无约束性，弥补了之前的协同编辑算法的不足。 2 2 一些实时编辑系统 由于多种原因，目前各种实时协同系统还不够完善，所以对于各种 并发控制算法的改进和正确性探讨仍然需要更广泛和深入的研究。分布 式系统没有统一的物理时间，即使是达到了几十毫秒精确度的i n t e m e t 网络时间协议也不足以获取分布式系统中的因果关系。因此，g r o v e 、 r e d u c e 等实时协同系统中应用的基于操作变换思想并发控制算法( 如 第一二章研究现状一个悱同编辑器中并发控制算法的研究与实现 d o p t 、a d o p t e d 、g o t 等) 是目前的主流研究方向。在a d o p t e d 、s o c k 2 中置换函数必须满足前提c 2 ，由于算法的多维性，c 2 常常难以被保证， 而且很难验证，如表2 1 所示。g o t 算法摆脱了对于c 2 的依赖，使得 算法可以得到比较容易的验证。本文提出的g o t 3 算法在从多方面扩展 了g o t 算法，一致性维护可以得到保证，具体将在3 2 节中证明。 表2 - 1 各种实时协同系统的正确性测试 2 3 小结 g r o u pe d i t 。r s c 1c 2 g r o v e 违背 违背 j o i m 违背违背 r e d u c e 正确 违背 s a m s 正确 违背 s 5正确违背 在c s c w 系统中，并发控制是其关键技术之一，基于操作变换的 协同编辑算法的一致性维护、因果关系维护、操作意愿维护和上下文一 致维护是实时协同编辑系统中的重要问题。然而，由于操作变换算法的 复杂性，算法本身以及基于算法实现的协同编辑系统常常被发现没有完 全实现预期的目标。一些基于树型结构文档 1 5 】【17 】的算法也存在问题： ( 1 ) 要求操作本身要包含语义( 如何定义语义是一个问题) ； ( 2 ) 树型文档算法基于字符串的算法必须是在词内部，被语义单 元限制，即一次输入只可以是一个语义单元( 段，旬，词，字符等) ； ( 3 ) 语义单元的合并分解等情况的处理方法解释含糊，解决方案 不完善。 本文希望在满足实时协同编辑系统的三个特点：实时性、分布性和 无约束性的同时，能够有一种算法既解决一致性维护、因果关系维护、 操作意愿维护和上下文一致维护，且算法的复杂度没有明显提高。实时 编辑系统的操作单元应该不仅可以是字符、字符串，还可以是其他语义 一个挑到编辑器中并发拄制算法的研究与实现 单元词、句子或段落；删除和插入一个段落可以通过一个操作实现，用 户选择更加丰富。 改善效率是协同算法的一个重要难点。现存的算法为使一个新操作 获得相应的变换，需要一个记载所有历史操作的缓存，这可能造成运行 效率低下，使协同系统的反应时间明显降低。设计一种历史缓存清洗策 略改善系统性能，加快系统的反应速度，是实时协同编辑系统的现实需 要。 第三章g o t 3 算法 一个协同编辑器中并发控制算法的研究与实现 第三章g o t 3 算法 协同编辑器并发控制过程较为复杂，数据一致性的维护必须由一个 高效、完备的并发控制算法支撑。本章首先介绍了整体一致性模型 ( c c i ) ，它是协同编辑算法实现数据一致性维护的前提和基础。接着， 详细介绍了g o t 3 算法的内容，包括算法的定义、描述等，并着重介绍 了g o t 3 算法的特色：子函数扩展、焦点维护、历史缓存清洗和上下文 一致性维护。然后对于给出的算法做出分析。最后，将g o t 3 算法同其 它一些算法进行了比较。 3 1 整体一致性模型( c c l ) 定义：因果关系“一” 给出两个操作o 。和0 b ，0 。生成于站点i ，0 b 生成于站点j ，那么 0 。一0 b 当且仅当：( 1 ) i = j ，0 。在0 b 之前生成；( 2 ) i j ，在站点j ，0 。先 执行，0 b 后生成：( 3 ) 存在操作0 。，使得0 。一0 。，0 。一o b 。 定义：独立性和依赖性 给出两个操作0 。和o b ，( 1 ) o b 依赖于0 。，当且仅当0 。一o b ；( 2 ) 0 。 和0 b 相互独立，记为0 。i | 0 b ，当且仅当o 。一o b 和0 b 一0 。都不成立。 定义：操作意愿 操作o 的操作意