郑州阿里巴巴网站建设,网站建设模板网站,自己编程怎么做网站教程,企业邮箱格式怎么注册OT是支持协作软件系统的一种广泛使用的技术。
OT通常使用副本文档储存#xff0c;每个客户端都拥有对文档的副本。客户端在本地副本以无锁非堵塞方式操作#xff0c;并将改变传递到其他客户端。当客户端收到其他客户端传播的改变之后#xff0c;通过转换应用更改#xff0…
OT是支持协作软件系统的一种广泛使用的技术。
OT通常使用副本文档储存每个客户端都拥有对文档的副本。客户端在本地副本以无锁非堵塞方式操作并将改变传递到其他客户端。当客户端收到其他客户端传播的改变之后通过转换应用更改从而保证一致性 初始文档为abc并存在客户端A、B A发起操作O1insert[0, “x”]在位置0插入字符x B发起操作O2delete[2, “c”]在位置2删除字符c
在没有OT之前加入O1发生在O2之前那么执行O1之后字符串变为xabc执行O2之后由于位置2从原来的c变为了b所以最终字符串会变为xac这并不符合预期
而利用OT的协作系统通常使用复制文档存储其中每个客户端都有自己的文档副本。客户端以无锁、非阻塞的方式操作其本地副本然后将更改传播到其他客户端。这确保了客户机在Internet等其他高延迟环境中的高响应性。
当客户端接收到从另一个客户端传播的更改时它通常在执行更改之前对更改进行转换。转换确保所有副本都维护一致性标准(不变量)。这种操作模式产生的系统特别适合在web等高延迟环境中实现协作功能例如同时编辑文档。
一致性模型——CCI
收敛性
所有文档副本在所有操作执行完成之后都要保持一致
意图保持
确保一个操作作用于所有文档副本的状态需与操作意图一致。操作意图定义为在操作者在其副本执行效果
因果关系保持
操作必须根据自然因果顺序执行
结构 transformation control algorithm: 决定什么操作被转换并以什么顺序转换 transformation properties and conditions: 定义算法和函数之间关系并验证算法和函数是否正确 transformation functions: 负责根据操作的影响执行实际的转换。转换函数取决于操作的类型和参数以及OT系统的数据和操作模型。 OT方法
以字符层面的OT方法为例 T({insert c1, p1}, {insert c2, p2}): // 例如插入b到位置4应用插入a到位置3那么转换之后就是插入a到位置3因为插入b到位置4并不影响插入a到位置3
// 如果是插入b到位置1应用插入a到位置3那么转换之后就是插入a到位置4因为插入b之后原来3的位置变成了4
if p1 p2 {return insert(c1, p1)
}else {return insert(c1, p11)
}T({insert c1, p1}, {delete, p2}): if p1 p2 {return insert(c1, p1)
}else{return insert(c1, p1-1)
}T({delete, p1}, {insert c1, p2}): if p1 p2 {return delete(p1)
}else {return delete(p11)
}T({delete, p1}, {delete, p2}): if p1 p2 {return delete(p1)
}else if p1 p2 {return delete(p1-1)
}else{return
}设计基于字符串的转换函数比基于字符的操作更具挑战性因为:
(1)字符串删除包括删除范围该范围可以包括字符串中的字符以及字符之间的间隔位置;
(2)并发的字符串删除操作可能任意重叠甚至可能与并发的插入操作重叠
(3)由前一个插入操作插入的字符串可能会被后面的插入和删除操作所改变。
上述因素使得字符转换函数的简化设计方法不适用于字符串转换函数以获得字符串转换函数的示例)。当字符串转换函数被设计用于组撤销和一致性维护时额外的复杂性就会发挥作用。是否支持字符串转换可能会对OT系统的各个方面(例如正确性、复杂性和效率)产生重大影响。
基本流程
介绍流程之前先展示下client、server各自储存的信息
client
最后同步版本id所有未被发送到服务器的本地改动(pending changes)所有已发送服务器的本地改动但未ack(sent changes)当前文档状态
server
所有收到但未处理的改变(pending changes)所有已处理的改变log(revision log)自上次处理后文档状态
以下便是基本流程
当客户端接收到服务端ack或者接收到操作则版本加一 初始文档为空文本A、B版本均为0 A在本地执行{insert “hello”, 0}并发送给服务器 A本地文本变为hello B在本地执行{insert “!”, 0} B本地文本变为! 随后A在本地执行{insert “world”, 5}但未发送因为前一个条件还未ack A本地文本变为helloworld server处理完A的第一条改动记录到revision log随后发送ack给A并传播改变到B A版本变更为1 B接收到改动后应用transformation函数作为结果。原来pending change中的{insert “!”, 0}变为{insert “!”, 5} B本地文本变为hello!并更新版本为1 A发送第二次改动B也发送改动但A先得到ack 此时A文本为helloworldB文本变为helloworld! A版本更新为2B收到A的改动后也更新为2 server收到B的改动后但由于B操作版本id 2小于实际id 3因此再次应用transformation函数并将其保存为版本3并将最终改动传播给所有客户端 所有客户端最终文本为helloworld!
基本流程中关键在于以服务器确定顺序为准应用transformation函数转换使得最终状态一致
Undo流程 最初文档内容为12 A执行O1 {insert “y”, 2}随后操作传递到B所有文档都更新为12y B执行O2 {insert “x”, 0}随后操作传播到A所有文档都更新为x12y A执行undo(O1)去撤回O1操作 OT会先生成逆操作!O1 {delete, 2}然后会应用转换函数到!O1和O2!O1’ T(!O1, O2) {delete, 3} 最终得到文档x12
压缩
假设最初文本为123连续执行了
O1 {insert “x”, 2}O2 {insert “abc”, 1}O3 {insert “y”, 2}O4 {delete, 7}
那么压缩过程
将最右边的操作O4与相邻的操作O3进行转置:转置(O3, O4) [O’4, O’3]其中O’4 Delete[6] O’3 O3得到L’ [O1, O2, O’4, O3]。将O’4进一步与新的相邻操作O2进行转置:转置(O2, O’4) [O’ 4, O’2]其中O’4 Delete[3] O’2 O2得到L’ [O1, O’4, O2, O3]。用新的相邻操作O1检查O’ 4;并且发现它们相互重叠互补(即对文档没有影响)因此将O’ 4和O’ 1从L中剔除得到L’ [O2, O3]。将L’中相邻重叠的两个操作O2和O3合并为一个操作O’2 Insert[1“aYbc”]得到L’ [O 2]。将L’ [O ’ 2]而不是L [O1, O2, O3, O4]传播到各本地文档进行集成。
批判
在分布式系统世界中操作以有限速度传播参与者状态往往不同因此产生的状态和操作的组合非常难以预测和理解。这使得形式证明非常复杂和容易出错
Ref
https://operational-transformation.github.io/https://en.wikipedia.org/wiki/Operational_transformationhttps://medium.com/coinmonks/operational-transformations-as-an-algorithm-for-automatic-conflict-resolution-3bf8920ea447https://www3.ntu.edu.sg/scse/staff/czsun/projects/otfaq
