介绍
操作转换(OT)是一种解决协作编辑系统中各种冲突的技术,包括读写冲突,合并冲突和写入写冲突。它通过转换一个用户的操作来使其与另一个用户的操作兼容。这使用户可以同时处理同一文档而不会引起冲突。
在多用户并发系统中处理所有用户的更新可能是一项艰巨的任务。这是因为多个用户可能试图同时更新相同的数据。这可能会导致冲突,系统必须决定要保留的更改。
每次更改后,使用一些同步策略来保持用户的本地副本。
- 事件通过是一种同步策略,一旦制造了所有用户的更改。
- 差分同步是一种同步策略,在该策略中,只有自上次同步以来所做的更改传播给所有用户。
,但即使那样,问题仍然存在。如果用户2更改用户1副本中不存在的事物怎么办?
即使使用同步策略,冲突仍然可能发生。这是因为同步策略只能解决已经进行的更改之间发生的冲突。如果用户2对用户1副本中不存在的事物进行了更改,那么同步策略就无法解决冲突。
这是运营转换开始的地方。稍后再详细介绍。
并发系统中的冲突。
如果您使用git/github,您可能会熟悉冲突以及它们的刺激性。当两个或多个用户同时更改同一文件时,就会发生冲突。这可能导致诸如数据损坏或丢失更改。
等问题。在并发系统中,可能会在原子层面发生冲突,因为每个变化都会立即在整个系统中传播。
并发系统中可能发生三种主要冲突类型:
- 阅读 - 写冲突:当两个用户尝试同时读写并写入相同的数据时,就会发生这种冲突。这可能会导致系统向不同用户显示不同版本的数据。
- 写入 - - - >:当两个用户尝试同时写入相同数据时,就会发生这种冲突。这可能会导致系统覆盖一个用户的变化,而另一个用户的更改。
- 合并冲突:当两个用户对同一数据做出不同的更改时,就会发生这种冲突。这可能导致系统显示合并冲突的系统,这是一条消息,要求用户手动解决冲突。
解决冲突的运营转型
操作转型的工作原理
操作转换的基本思想是将每个操作表示为以文档状态为输入的函数,并产生文档的新状态作为输出。例如,将单词“ boink”插入文档中的操作可以表示为函数f(state)= state +“ boink”。
当两个用户对文档进行矛盾的更改时,可以使用OT来改变一个用户的操作,以使其与其他用户的操作兼容。这是通过将两个函数的组成应用于文档状态来完成的。例如,如果一个用户将单词“ boink”插入doc,而另一个用户删除了单词“ sudo”,则可以使用doc =“ sudo”,则可以使用ot来转换第一个用户的操作来生成文本“ boink”
OT的一般公式如下:
OT(f, g, state) = f(g(state))
其中:
- f是代表第一个用户操作的功能。
- g是代表第二用户操作的功能。
- 状态是文档的状态。
操作函数:
操作函数是一个通用函数,可用于表示文档上的单个操作。该功能需要三个参数:
- 操作的类型,可以是“插入”,“删除”等。
- 如果适用,正在插入或删除的文本。
- 如果适用,则插入或删除文本的索引。
该功能还可以采用其他参数,例如操作的时间戳或制作操作的用户。
操作函数返回一个代表操作的新对象。
这可用于表示文档上的各种操作。例如,该函数可用于表示新文本的插入,现有文本的删除,现有文本的修改以及文档中文本的移动。
这是一个强大的工具,可用于简化和优化文档上的操作序列。通过将操作表示为对象,转换函数可以轻松比较两个操作并返回一个代表组合效果的新对象
type Operation struct {
operation_type string
text string
index int
}
func operation(operation_type string, text string, index int) Operation {
return Operation{
operation_type: operation_type,
text: text,
index: index,
}
}
这是操作功能的非常基本的实现。
转换功能:
转换功能以两个操作对象为输入,然后返回一个新操作对象,这是针对第二个操作转换第一个操作的结果。转换功能负责确保转换的操作具有正确的效果并保持文档一致性。
转换函数首先检查两个操作是否是矛盾的。如果是,则该功能将返回一个新操作,代表两个操作的否定。
例如,如果两个操作是插入文本“ a”和文本删除“ a”的插入P>
如果两个操作不是矛盾的,则该函数仅返回一个新操作,代表了两个操作的组合效果。
例如,如果两个操作是文本“ a”和文本“ b”的插入的插入,则转换函数将返回一个新操作,代表插入文本“ ab”。 P>
以下是这些转换的两种情况 - >
- 在相同的索引上应用插入和删除操作时。
func transform_insertion_against_deletion(op1, op2 Operation) Operation {
if op1.text == op2.text {
return Operation{"delete", ""}
} else {
return op1
}
}
针对删除的插入是用于简化和优化文档上操作序列的操作。该功能将两个操作作为输入,一个插入操作和一个删除操作。然后,该函数返回一个新操作,该操作代表两个操作的组合效果。
- 当两个并发用户以相同索引插入
func transform_insertion_against_insertion(op1, op2 Operation) Operation {
if op1.text == op2.text {
return Operation{"insert", op1.text, op1.index}
} else {
return Operation{"insert", op1.text + op2.text, op1.index}
}
}
插入插入的插入是将两个插入合并到一个插入中的操作。
两个插入的综合效果取决于正在插入的文本。如果两个插入是相同的文本,则组合效果是文本在第一个插入的索引处插入一次。如果两个插入的文本不同,则组合效果是两个文本在第一个插入的索引处加入。
转型涉及的策略
基于时间和优先级的转换
-
基于时间的转换是解决基于运营时间的冲突的策略。在基于时间的转换中,早期应用的操作比以后应用的操作优先。这意味着,如果两个用户对文档进行了冲突的更改,则将保留以前应用的更改,并将稍后应用的更改丢弃。
-
基于优先级的转换是解决基于开展操作的用户优先级的冲突的策略。在基于优先级的转换中,优先级较高的用户进行的操作优先于优先级较低的用户进行的操作。这意味着,如果两个用户对文档进行了冲突的更改,则将保留具有较高优先级的用户的更改,并且将丢弃优先级较低的用户所做的更改。
解决冲突的其他策略
-
基于合并的转换是解决冲突的策略,将冲突的操作合并为单个操作。这可以通过组合由两个操作插入的文本,或通过将两个操作对文档进行的更改组合在一起来完成。
-
基于撤消的转型是解决消除冲突的冲突的策略。这可以通过撤消第一个操作所做的更改,也可以消除第二个操作所做的更改来完成。
客户服务器在操作转换中拆分
在操作转换中,可以在客户端和服务器方面发生操作和转换。此的具体实现取决于特定的应用程序。
通常,在客户端创建操作并发送到服务器。然后,服务器将操作应用于文档,并将转换的文档发送回客户端。然后,客户将转换的文档应用于其文档本地副本。
转换也可能发生在客户端。 例如,如果客户端收到其不了解的操作,则可能需要在将操作应用于文档之前将其转换为。
选择执行操作和转换方面的选择取决于许多因素,包括:
-
操作的类型:可以在客户端和服务器侧面执行某些操作,例如插入和删除。其他操作(例如合并或分裂)可能需要在服务器端执行。
-
应用程序的安全要求:如果应用程序需要高安全性,则可能希望在服务器端执行操作和转换。这可以防止用户以不允许的方式修改文档。
-
资源的性能和可用性:资源的性能和可用性是实施操作转换时要考虑的重要因素。必须仔细实现客户端服务器拆分以避免性能问题。
如果在服务器端执行了太多操作,则可以超载服务器并为所有用户造成性能问题。同样,如果在客户端处理转换,并且客户端没有足够的可用资源,则用户可能会遇到性能问题。客户必须有足够的资源来及时执行转换,或者数据可能不一致。
结论
在这篇博客文章中,我们讨论了操作转型的基础知识。我们已经看到了如何使用操作转换来解决协作编辑应用程序中的冲突。我们还讨论了可用于解决冲突的不同策略,以及实施操作转型时要考虑的因素。
我希望这是有益的。如果您有任何疑问,请随时在下面发表评论。
谢谢您的阅读!