协同编辑环境下基于树型结构的锁操作意愿维护研究

摘要

一致性维护是实时协同编辑系统中的核心问题，长期以来受到本领域研究学者的普遍重视。一致性维护包括句法一致性和语义一致性。已有的主流一致性维护方法：操作转换和地址空间转换可以有效维护实时协同编辑系统的句法一致性。而语义一致性的维护需要由锁操作来实现。锁操作在维护实时协同编辑系统语义一致性的同时，其自身也要满足一致性维护的要求，而其中锁操作的意愿维护是最主要也是最复杂的一部分。因此锁操作的意愿维护对保证实时协同编辑系统的语义一致性是至关重要的。
　　 在分析现有工作的基础上，本文基于操作转换和地址空间转换这两种一致性维护方法对锁操作的意愿维护进行了研究，主要研究内容如下：
　　 提出了基于操作转换的锁操作意愿维护算法TreeLock_GOTO，该算法使用树型结构的文档表示方式，并在文档的不同层级引入可选锁机制。和已有基于线形文档的锁操作转换算法相比，TreeLock_GOTO算法在维护锁操作意愿的同时，大大提高了锁操作的转换效率。
　　 提出了基于地址空间转换的锁操作意愿维护算法TreeLock_AST。地址空间转换是操作转换之外的另一种主流一致性维护方法，可以有效维护实时协同编辑系统的句法一致性。本文进一步研究发现和操作转换一样，地址空间转换可以有效维护锁操作的意愿。和TreeLock_GOTO算法相比，TreeLock_AST算法并不修正锁操作本身，而是将文档的地址空间回溯到锁操作生成时的状态，在这个状态下锁操作可以立即执行。从而避免了操作转换过程中操作问相对位置信息的丢失，而且转换过程更加直观更接近用户的自然编辑场景。
　　 给出了TreeLock_GOTO算法和TreeLock_AST算法的执行实例，详细讨论了这两个算法的执行效率，并设计了支持这两个算法的实时协同编辑系统构架。