本文主要是介绍easysync 协同算法详解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、从场景出发

• 假如设计一个博客网站的编辑功能

作为研发人员，大家或多或少可能都在博客网站上编辑过博客。也可能大家会使用一些笔记应用，记录一些事情。无论是博客网站，还是笔记 APP，大家都会编辑内容，然后这些内容会同步到云端。这样，只要有网络，你就可以随时随地，在任何设备上查看这些内容。
如果我们要设计这个博客网站的编辑功能，我们会有哪些方案呢？

1. 最简单的方案，我们在页面编辑完成后，点击一个保存按钮，然后前端会将页面上所有的内容发送到服务端，作为这篇博客最新的版本 。
2. 但是这个方案会有一些不太好的体验，比如我编辑到一半，还没有点保存呢，网站崩溃了，那我编辑的内容就都丢失了。为了优化这个体验，我们可以设计成定时就把页面上的内容同步到服务端，这样即便编辑到一半，网页崩溃了，已经同步到服务端的内容就不会丢失了。
3. 当然，如果定时把整个网页的内容都同步到服务端，可能对于网络的消耗很大。我们还可以这样优化，每次编辑时，我们只提交在下标 X 处，增加（删除）了 N 个字类似的变更信息，这样就不需要把整个文档的内容发送给服务端。

• 多人协作，同时编辑一篇文档的高级体验

上述的几个设计，基本上可以比较好的解决一个普通博客网站，或者是笔记类产品的编辑需求。但是如果考虑一些更高级的场景，比如大家一起编写一篇周会文档的情况。在这个场景下，会有不止一个操作者，对着同一篇文档几乎同时进行编辑。这种情况下，上述的几个设计，都会有一些很严重的问题。
首先(1)和(2)本质上都是进行覆盖的操作。在这种设计下的问题是，我这边刚粘贴进一句话进来，转眼别人打了一个换行，就把我这一句话给覆盖掉了，然后我就需要重新输入这句话。这样的情况如果在周会上一直重复出现，肯定是无法被使用者所容忍的。
(3)这种根据下标的处理方式，看起来可行性会更高一些，但是仍然会有如下一些问题。

1. 第一个问题，假如目前，文档最新的内容是easysync is good. 这时用户 A 和用户 B 都想对这段话进行修改。
   A 想将这句话修改为 The easysync is good. 如果使用下标来表示用户 A 的操作，那就是：在下标0处，增加4个字，内容是 The和一个空格。
   B 想将这句话修改为easysync is very good. 那 B 的操作就是在下标12处，增加5个字，内容是 very 和一个空格。
   两者几乎同时做了修改，但是用户 A 的网络更好一些，服务端先收到了 A 的提交。这时，文档最新的内容变成了 The easysync is good. 随后，服务端收到了 B 的提交：在下标12处，增加5个字。这时，服务端存储的内容就会变成 The easysyncvery is good. 很明显，服务端最终存储的这段话的内容完全不符合用户 B 对 good 这一形容词添加副词very 进行修饰的预期。
2. 第二个问题，仍假如目前，文档最新的内容是easysync is good. 用户 A 和用户 B 都想对这段话进行修改。
   B 想将这句话修改为easysync is very good. 那 B 的操作就是：在下标12处，增加5个字，内容是 very 和一个空格。而且 B 的操作先达到了服务端，服务端将文档内容正确地进行了更新。
   这时，我们再看 A的页面，如果 A 的页面，不将 B 的编辑操作展示出来，那 A 基于过期的信息，很有可能提交一些不符合预期的数据，比如 A 也想将内容修改为 easysync is very good. 同样提交了：在下标12处，增加5个字，内容是 very 和一个空格，这样的一个变更记录。那最终，文档的最新内容会变成 easysync is very very good. 很明显，这并不符合用户 A 的预期。
   那如果我们选择，在 A 的页面，将 B 的编辑信息给展示出来呢。这样又会有新的问题，比如 A 希望将内容修改为 The easysync is good. 但是由于还没有到定时提交的时间，用户 A 增加的 The 几个字还在本地，这时用户 A 的页面收到了服务端发送的消息，说用户 B 对文档内容做了变更：在下标12处，增加5个字，内容是 very 和一个空格。如果客户端直接应用这个变更的话，那用户A 的页面就会展示成The easysyncvery is good. 显然，再次产生不符合预期的内容。

所以如果使用基于下标进行编辑的设计，会有如上的两个问题，这两个问题我们可以概括一下：

1. 服务端在收到不同客户端的提交时，如何处理才能确保最终得到的内容是尽可能符合所有客户端预期的
2. 客户端在收到服务端发送的文档变更数据，且本地有未提交的内容时，如何处理才能确保向用户展示的内容是尽可能符合用户预期和服务端预期的。

二、协同算法的分类

协同处理算法，就是处理上述场景中，编辑冲突问题的一类算法。
OT算法是协同处理算法中常见的一种，OT是operation transform的简写，中文可理解为操作转换。这类算法的主要思想是，将用户提交的编辑数据基于一些规则进行转换，使其从不符合语义的提交，变为符合语义的提交。比如上述的问题(1)：服务端通过既定的规则，将用户B提交的数据进行一些转换，而后服务端应用转换后的编辑数据，得到相对更加符合语义的文档内容。
CRDT算法是另一种协同处理算法，全称是Conflict-free Replicated Data Types ，直译的话即冲突避免可复制数据类型。这种算法的主要是为了实现分布式系统下数据最终一致的问题，所以其可以广泛的用于其他系统中，而不仅仅是文档协同处理。关于 CRDT 的具体内容大家可自行了解。
而本文主要讲述的easysync协同算法是OT算法的一种。同样属于OT算法这一类的还有ot-json算法。这两种算法都是基于OT的思想处理编辑冲突，只是具体描述文档和编辑信息的数据结构有所不同。一般而言，easysync算法适合处理文本类内容，比如传统WPS文档。而ot-json更适合处理结构化数据，比如json数据。

三、easysync的算法思想

这部分，我们会讲解 easysync 的算法思想，是如何解决如上的两个协同冲突问题的。首先，我们需要简单定义一些关键的数据结构。请注意easysync 算法并不给定这些数据结构的详细格式，只是给定了这些数据结构的一些限制，只要满足限制都是可以用作 easysync 的数据结构。

Document（文档）：

• 一个文档是一个字符列表，或者一个字符串
• 一个文档也可以被一系列 changeset 表示

Changesets：

• 一个 changeset 表示了对文档的一个改动，是满足一些限制的特定的数据结构。Changeset最基本的含义是对一篇字数为N0的文档 X，增加或删除了字数 a，使其文档字数变为了 N1. 习惯上会将changeset简称为 CS。
• 一个 changeset 可以应用至一个文档来产生一个新的文档
• 当一个文档用一系列的 changesets 来表示时，我们认为第一个 changeset 应用在一个空文档上

Changesets需要满足的限制:

• Changeset 是可比较的。当在计算机内存中表示 changeset 时，我们永远会用相同的表示方式来表示两个相同的 changeset，如果内存两个 changeset 的表示方式不一致，那说明这一定是两个不同的 changeset。
• Changeset 是简洁的，因此如果有两种方式来表示内存中一个相同的 changeset，那么我们永远会采用占据最少字节的表示方式。

Apply:

• 我们将在一篇文档上应用一个 changeset 称为 apply 操作，用代数中的乘号 • 表示，且可省略。X•A和 XA 均表示在文档 X 上应用 changeset A这一操作。
• 一条Changeset只能作用于特定状态的文档。Changeset会在其结构中声明文档的原字数，其所增加（删除）的字数等信息，很明显，若一条Changeset声明的文档原字数与当前文档的字数不同，那这条 changeset 是不能作用于这篇文档的。

Compose：

• 假设有文档 X，其当前状态为N0，changeset A 应用到文档 X的 N0 状态，使其变为状态N1，changeset B 应用到文档 X 的 N1状态使其变为状态N2，而 changeset C 应用到文档 X 的 N0状态，可直接使其变为状态 N2。于是定义：由changeset A和 B，得到changeset C的操作为 compose，记为：Compose(A,B) = C。
• 由于文档是一系列的changeset表示，而这一系列的changeset可以通过 compose 操作转化为一条ChangeSet，所以可以将文档认为是一条特殊的 ChangeSet, 而对文档的 apply 操作，同样可以被认为是一种特殊的 Compose 操作。
• 由于一条 changeSet 必须是基于文档一个特定状态的操作。 所以Compose 满足结合律，即：(AB)C = A(BC); 而不满足交换律：AB != BA 。

Follow

• 在第一部分，我们有两个协同算法的问题无法解决，而Follow 算法就是用来解决者两个问题的工具。
• 由于我们在上述叙述中给定了一些定义，所以我们可以用这些定义重新表述最开始的两个问题。比如服务端的问题可以这样抽象：当前服务端文档状态为 X，当服务端收到了基于 X 的 changeset A，并成功apply 变成了 XA 之后，又收到了基于 X 的 changeset B，服务端要如何处理。
• 很明显，直接使用(XA)B 的计算方式是不行的，因为 B 是基于 X 的changeset，无法直接作用于于 XA。所以，我们希望如果有一个 B'，B'能够直接作用于(XA)上得到 A 和 B 的信息都被处理后的文档内容 (XA)B'. 反之，如果服务端先收到了 B，后收到了 A，那服务端的处理顺序应该是 (XB)A',且有(XA)B'=(XB)A'。
• 我们将得到 B'或 A'的算法称之为 follow 算法，记为 f，即：f(A,B) = B' , f(B,A) = A'。且由于(XA)B'=(XB)A'，可得到，XAf(A,B)=XBf(B,A)， 即：Af(A,B)=Bf(B,A)
• follow 算法的定义，是解决最初提出的协同的两个问题的关键。无论是服务端，还是客户端，在对协同冲突进行处理时，只需要使用包含 Follow 算法在内的一些转换，就能实现在 easysync 这个框架下处理协同的冲突。但是需要注意的是，easysync 算法并没有强制规定 follow 算法的实现是怎样的，easysync 算法只是设计了 Follow 算法这个概念，或者说提供了Follow 算法这个工具，使得整个 easysync 的协同处理变得完整且具有可行性。而 Follow 算法的具体实现，是由业务在研发过程中自己去设计的。当然，follow 算法实现的逻辑不同，其冲突处理的效果也不同。不仅如此，业务研发过程中，还可以在 Follow 算法中设计一些与业务相关的逻辑，以更好的处理业务上的一些展示。
• Follow 算法并不能解决全部的协同冲突处理的场景。目前的 Follow 算法在处理上，往往是对那些最常出现，影响较大的一些冲突进行转换，而忽略一些比较少出现的场景。对此，easysync 算法的论文中，给出了 Follow 算法三个建议的实现逻辑：
  1. A 中的插入在 f(A, B) 中变成保留
  2. B 中的插入在 f(A, B) 中变成插入
  3. 保留 A, B 中都保留的字符(可以理解为保留字符的交集)

这部分只是简单阐述了其中的一些逻辑，详细的 Follow 算法的实现，我们将会在后续定义了具体的数据结构后在进行描述。

服务端的处理

在协同处理上，服务端需要处理的最核心的两件事情如下：

1. 响应客户端的首次链接并返回文档的初始状态，一般而言，我们会设计一个版本号的概念来表示文档状态的变更。每次文档发生编辑，版本号就会加一。
2. 响应客户端，请求缺失的changeset列表的请求。由于种种原因，客户端可能收不到服务端广播的changeset数据，需要提供额外的接口供客户端拉取。
3. 响应客户端提交的 changeset 并进行处理，更新文档的状态并保存数据。

对于3这一操作，会遇到最开始我们提出的问题：

• 服务端在收到不同客户端的提交时，如何处理才能确保最终得到的内容是尽可能符合所有客户端预期的

我们在引入 Follow 算法时，曾经拿这一问题进行举例，我们这里再次阐述这个问题的解决方式：
当前服务端文档状态为 X，当服务端收到了基于 X 的 changeset A，并成功apply 变成了 XA 之后，又收到了基于 X 的 B，这时服务端应该首先计算 f(A,B)，然后在 XA 上 apply 得到的 f(A,B)，即：XAf(A,B)的计算方式，得到最新的文档状态。
在基于这个方案的基础之上，服务端的操作3又可以细化为这样几个步骤：

1. 接受客户端提交的 changeset 数据
2. 使用 follow 算法处理产生冲突的 changeset 数据，并保存处理后的 changeset
3. 向提交这个 changeset 的客户端发送 ACK 请求，告知处理成功及成功后的 changeset 版本号
4. 向其他客户端广播这次提交的 changeset 数据

客户端的处理

客户端的处理相较于服务端会更加复杂一些。服务端的问题在于处理不同客户端提交的 changeset。而客户端，不止需要处理收到的不同客户端已提交的 changeset 数据，还需要处理本地环境新的输入，并将其转换为 changeset 提交到服务端。
客户端需要进行的操作可以归类为如下几种：

1. 连接到服务器并请求初始文档
2. 收集新的本地输入并生成 changeset
3. 提交一个 changeset 给服务器
4. 等待服务器的 ack，并进行后续处理
5. 接受服务端广播的其他客户端的提交的changeset并进行处理

而我们先前概括的那个问题：

• 客户端在收到服务端发送的文档变更数据，且本地有未提交的内容时，如何处理才能确保向用户展示的内容是尽可能符合用户预期和服务端预期的。

其实就是2、3、5这些操作依次处理时，应该采取何种处理方式的一个问题。
我们用先前的定义重新描述这个问题，并从操作1开始，推导客户端的变化。

客户端本地状态的维护（ AXY 模型）：
客户端链接服务端并请求初始文档，我们定义初始文档状态为 A
这时用户可能会输入一些内容，并生成 changeset，我们将这些内容定义为 Y
间隔一段时间后，客户端需要将changeset提交到服务端，我们将其定义为 X，其中 X <- Y ,即 X 为用户刚刚输入的内容。然后将 Y 置空，重新接受用户的输入，即 Y <- In .
所以客户端可以用三种类型的 changeset 来维持自身的状态，即 AXY

• A: 服务端最新版本，所有提交到服务端的 cs 的合并
• X: 所有客户端提交给服务器但是没有 ack 回来的 cs 的合并
• Y: 所有客户端产生还没提交给服务器的 cs 的合并

新的本地编辑：
当用户进行本地编辑生成了 changeset E 的时候，客户端会计算 Y 与 E 的合并，并将 Y 更新为 YE，即：Y <- YE。

向服务器提交 changeset:
当客户端向服务器提交本地变更时，它会传送 Y 的一个副本，并将 Y 赋值给 X，重新以初值初始化 Y。

1. 把 Y 发送给服务器
2. X <- Y
3. Y <- In

注意，客户端提交 changeset 的操作是一个阻塞的操作，也就是在没有收到服务端对 X 的 ACK 之前，Y 永远不会成为新的 X。

接受来自服务器的 ack：
当客户端接收到来自服务器的 ACK 信息时，会做如下处理。

1. A <- AX

接受并处理其他客户端提交的 changesets：
在 AXY 的状态下，客户端除了自身提交 changeset 和接受服务端的 ACK 之外，还有可能收到其他客户端提交的 changeset，我们称之为 B。由于 B 一定是服务端落盘的数据，所以我们需要更新 AXY 的内容，假设新的内容为A'X'Y'。另外，由于 AXY 是已经展示给用户的状态了，所以无法直接用 A'X'Y'替换展示，需要重新计算一个新的 changeset，我们称之为 D，将其直接应用到AXY 上，使其展示的内容与 A'X'Y'一致，即：AXYD = A'X'Y'。
对于 A'X'Y' 和 D 的计算，可以按照如下的方式进行推导：

1. 计算 A' = AB。很明显，B 是应用于服务端的版本的，而 A 正是所有CS 提交到服务端后的版本，所以 A' = AB。
2. 计算 X' = f(B, X)。
   证：由于X 和 B 都是基于 A 的修改， 按照 Follow 算法的定义，X'应当为 B 基于 A Follow 后的结果，有ABX' = AXB'，故 X' = f(B, X)，B' = f(X, B)
3. 计算 Y' = f(f(X, B), Y)。
   证：
   1. 由1、2可知，A'X' = ABX' = AXB'，
   2. 由于文档原内容为 AXY，可知Y和 B'都是基于 AX的修改，故按照 Follow 算法的定义， Y' 应为 B' 基于 AX Follow 后的结果，即 AXYB'' = AXB' Y' ，Y' = f(B', Y)。
   3. 由2中可知 B' = f(X, B)，故 Y' = f(f(X,B), Y)。
4. 计算D = f(Y, f(X, B))。
   证：
   1. 因为 AXYD = A'X'Y' 。将1、2、3计算的结果代入，可得 AXYD = A • B• f(B,X) • f(f(X,B),Y)
   2. 按照 Follow 算法的定义，应有ABf(B,X) = AXf(X,B)。故上式可划为，A • X• f(X,B) • f(f(X,B),Y)
   3. 设 S = f(X,B)， 则上式可化为 AXSf(S,Y)，继续按照 Follow 算法的定义，则有 AXSf(S,Y) = AXYf(Y,S)。将 S 代回，可得 A • X • Y • f(Y, f(X,B)).
   4. 故 AXYD = A • B• f(B,X) • f(f(X,B),Y)
      = A • X• f(X,B) • f(f(X,B),Y)
      = A • X • Y • f(Y, f(X,B))
      可得 D = f(Y, f(X,B))

当收到其他客户端提交的 changeset B 时，客户端按照如上的计算公式，分布计算出 A'X'Y'和 D，将 D 作用于当前展示的数据，得到新的展示。将A'X'Y'替换 AXY 作为新的 AXY 模型。

接收changeset发现本地版本过低：
在上述处理接收的其他客户端的 changeset B 的时，我们定义本地状态为 AXY。但是上述过程的推导，基于的一个前提是 B 和 X 都是基于 A 的变更。如果客户端收到了一个 B，发现B 是基于比 A 更新的版本的变更（中间的变更数据可能因为网络原因没有收到），这时客户端可以按照如下的步骤进行处理：

1. 通过服务端的 FetchMiss 接口，将缺失的的 changeset 拉回来。
2. 从低到高版本，挨个按照上述接收其他客户端提交的 changesets的流程处理，直到 A 被更新到最新的状态，即：X 和 B 都是基于 A 进行变更的状态。

四、easysync的数据结构

文档结构的描述信息

一般而言，easysync 中文档的数据结构主要就是由 apool，text，attribs 组成的。

Apool

apool的全称为attribute pool，属性池的意思，它有个numToAttrib的字段，是个map对象。 其中，这个 map 的 value 代表属性，用来描述一段文字，key 是属性的序号，用来找到某个属性。而属性一般是由一个两项的字符串数组组成。第一项代表属性的 key，第二项代表属性的具体的值。除此之外 apool 中还有nextNum字段，代表下一个属性的序号，增加属性时使用。

 {
    "numToAttrib": {
        "0": ["author", "001"],
        "1": ["color", "red"],
    },
    "nextNum": 2
}

Text

text 代表文档中的纯文本内容。在文档结构中，有一个单独的字段描述 text。在changesets 中，可以看到文本一般是跟在一个 $ 符号后面。

Attribs

attribs是将apool和text关联起来的桥，它是个字符串，以行的形式描述了整篇文档的构成，是 easysync 的数据结构中理解成本比较高的一种定义。
这里我们举个例子:

{
  "apool": {
    "nextNum": 3,
    "numToAttrib": {
      "0": [
        "author",
        "001"
      ],
      "1": [
        "color",
        "red"
      ],
      "2": [
        "font",
        "Source Han Sans"
      ]
    }
  },
  "text": "easysync 算法详解\n一、从场景出发\n",
  "attribs": "*0*1+8*0*2|2+d"
}

1. 我们从 attribs 字段开始分析。*0表示从apool里面取第0个属性，也就是["author", "001" ]这个属性，这个属性会被应用到其后标识的字符中，*1代表表示从apool里面取第1个属性["color", "red" ]，同样被应用到其后标识的文字中，所以这段文字是同时使用了0和1两个属性。+8表示从text里面取8个字符插入文档，也就是easysync这几个字符。这8个字符会被应用apool 中的0号和1号属性，0号代表是被一个叫做001的人编写的，1号则代表了字体的颜色是红色。
2. 接下来0*2|2+d代表从 apool 中取出0号属性和2号属性，应用到其后的字符中。"|"表示影响的行数，或者说添加的文字中包含的换行符，|2表示影响两行，也就是包含了两行。注意 | 代表是影响(包含)的含义，如果是|1+2，则代表增加了 两个字符，其中一个是换行符。很明显，|2+1是不存在的，因为不可能只增加了一个字符，却包含了两个换行符。+d代表增加了13个文字，其中 d 是36进制，这13个文字应用了0号和2号属性。

Changeset 结构的描述信息

changeset 的主要内容也是由apool 和类似 attribs 和 text 的结构组成，

增加字符的 changeset

这里我们举一个增加字符的 changeset 的例子：

"Z:go>2|m=dz=4*0+2$fd"

通过观察可以发现和文档的描述相比，changeset 中没有 text 字段和attribs字段。这两个字段相当于组合到了一起，而attribs的含义其实是和文档的是一样的，但是 changeset 又多了一些特殊的字符，其中：

1. "Z:"是changeset的一个魔法数，没有特殊含义。
2. "go"表示文档应用changeset之前的长度(36进制表示，一般 eastsync 都使用36进制表示字符长度)。
3. ">2"表示应用changeset之后文档总长度增加2。
4. "|m=dz=4*0+2"表示changest对文档的具体操作序列，其含义和attribs类似。"|m=dz" 表示接下来的操作影响了第m行，保留了dz个字符，”=4”表示保留4个字符，"*0+2"表示插入2个字符，这2个字符带有属性0。
5. "$"插入数据的开始标识。
6. "fd"插入的字符具体字符。

删除字符的changeset

上面的是一个增加字符的 changeset，相对的，还会有删除字符的 changeset

"Z:q<3|2=e=5-3$"

和增加字符的 changeset相比，有这样几处不同：

1. q<3，代表原字符数是q，减小了3 个字符。
2. |2=e=5和之前的含义一样，保留了e 个字符，其中又2个换行，然后又保留了5个字符
3. -3，代表从这个位置开始，删除3个字符
4. 删除的 changeset 中，"$"后是空的，因为是删除，并没有新增的字符。

五、easysync的详细实现

Follow 算法

在上边，我们提到过，easysync 的论文中给出了 Follow 算法三个建议的实现逻辑：

1. A 中的插入在 f(A, B) 中变成保留
2. B 中的插入在 f(A, B) 中变成插入
3. 保留 A, B 中都保留的字符(可以理解为保留字符的交集)

当然实际上，具体的逻辑还不止这三种情况。观察 changeset 的数据结构我们可以发现，一般而言，changeset 包括了 '+'， '=' ，'-' 这三种操作。算法处理时，我们可以认为是对两个 changeset 种的 ops 数组进行按位的比较与运算，其中每一位的操作符就是 '+'， '=' ，'-' 。 ，所以实际的处理逻辑可以认为有9种组合（有些组合是相同的处理逻辑）。

• 我们可以将这9种按位处理的逻辑做一下简述，其理解的核心在于follow(A,B)函数是作用于XA的。

1. 如果A有插入操作，那么对于XA来说已经有插入了，此时应该变为保留操作。而且无论B 是 插入删除还是保留，A 都转换为保留操作即可。因为 B 的插入和删除和保留都是基于 X 的操作，是感知不到 A 中插入的数据的。
2. 如果B有插入操作，那么对于XA来说也是新元素还是插入操作。同样地，由于 A 操作时的删除和保留都是基于 X 的操作，是感知不到 B 中插入的数据的。 所以无论 A 这两种操作符不会影响 B 插入的数据。而由于A是先执行的 changeset，所以 A的插入要早于 B 的插入进行转换。
3. 如果 A 有删除操作，首先 A 的删除操作不影响 B 的插入操作。但是对于 XA 而言，相当于字符数变少了，所以如果 B是删除或者是保留操作，其影响的字符数应该减去 A 的删除操作的字符数，而后作为新的操作符。
4. 如果 A 有保留操作，首先A 的保留操作也不应当影响 B 的插入操作。而且如果B也有保留操作，那么对于XA来说保留共同部分就行。但是如果 B 是删除操作，由于A是保留，所以这部分要删除的数据在 XA 中仍然存在，所以 B 的删除操作仍要进行处理。
5. 除此之外，还有一个很关键的逻辑是，如果 changeset A 中的 ops 已经处理完了，很明显B 中剩余的 ops 直接追加到 follow 后的结果即可。反之，如果 B 中的 ops 已经处理完了，则不需要继续处理 A 中的 ops，因为其已经在 XA 中应用过了。

我们可以将上述处理逻辑简单整理为一份伪代码。这份伪代码刚好涵盖了9种组合情况。需要注意的是，为了着重表现9种组合情况的处理逻辑，这份伪代码没有表现：A 的 ops 处理完，将剩余的B 直接追加到结果中的这块逻辑，也就是上述序号5的逻辑。同时这份伪代码也没有关注 changeset 的每一个 OP的属性在 Follow 过程中的处理。

var res
for i, j := 0, 0; i < len(A) || j < len(B); {
   if A[i].Op == '+' { // 覆盖 ++ +- += 的组合
      A[i].Op = '=' // A 为 '+'，则将 A 的操作修改为 '='，追加到结果中，按位操作下一个 A
      res = append(res, A[i])
      i++
   } else if B[j].Op == '+' { // 覆盖 -+ =+ 的组合
      res = append(res, B[j]) // B 为 '+'，则直接将 B 追加到结果中，按位操作下一个 B
      j++
   } else if A[i].Op == '-' { // 覆盖 -= -- 的组合
      if A[i].CharNum < B[j].CharNum { // 如果 A 的字符数更少
         B[j].CharNum -= A[i].CharNum // 则将 B 的字符数相应减小，相当于覆盖了 A 的操作，然后操作下一个 A
         i++
      } else if A[i].CharNum > B[j].CharNum { // 反之，如果 B 的字符数更少
         A[i].CharNum -= B[j].CharNum // 则将 A 的字符数相应减小，相当于覆盖了 B 的操作，然后操作下一个 B
         j++
      } else { // 如果两者字符数相等，相当于刚好抵消，全部跳到下一个处理
         i++
         j++
      }
   } else if B[j].Op == '-' { // 覆盖 =- 的组合
      if A[i].CharNum < B[j].CharNum { // 如果 A 的字符数更少，那 B 将这些字符删除后，有可能会继续删除一些字符
         newOp := {CharNum: A[i].CharNum, Op: '-'} // 先构造一个新的'-' op，相当于删除 A 的保留的数据
         res = append(res, newOp)                    // 新的 Op 追加到结果中
         B[j].CharNum -= A[i].CharNum                // 而 B 则相应减去删除的 A 的字符数
         i++                                         // 然后操作下一个 A
      } else if A[i].CharNum > B[j].CharNum { // 反之，如果 B 的字符数更少
         A[i].CharNum -= B[j].CharNum // 则将 A 的字符数相应减小，相当于覆盖了 B 的操作，然后操作下一个 B
         j++
      } else { // 如果两者字符数相等，相当于刚好抵消，全部跳到下一个处理
         i++
         j++
      }
   } else {                             // 覆盖 == 的组合
      if A[i].CharNum < B[j].CharNum { // 如果 A 的字符数更少，则 A 为共同部分，将 A 追加到结果中
         B[j].CharNum -= A[i].CharNum // 同时将 B 的字符数相应减小，继续操作下一个 A
         res = append(res, A[i])
         i++
      } else if A[i].CharNum > B[j].CharNum { // 如果 B 的字符数更少，则 B 为共同部分，将 B 追加到结果中
         A[i].CharNum -= B[j].CharNum // 同时将 A 的字符数相应减小，继续操作下一个 B
         res = append(res, B[j])
         j++
      } else { // 如果字符数相同，说明两者一致，追加任意一个，全部跳到下一个处理
         res = append(res, B[j])
         i++
         j++
      }
   }
}
return res

Apply 算法

Apply算法也是 easysync 中比较重要的一个算法。相比于 Follow 算法而言，apply 算法可能会相对简单一些，因为 apply 算法是将一条 CS 作用于一篇文档上，而文档的操作符只有 '+'。而且 apply 的概念上，也是比 follow 更直观的。
apply 一般要包括两部分的操作，一部分是 text 的apply，一部分是 attribs 的 apply。
text 的 apply 操作比较简单，我们假设游标处于文档原 text 的0处，然后开始按位处理 changeset 的 op。遇到 '=' 操作，就将游标后移 '=' 操作影响的字符数长度，并将这部分字符追加到结果中，相当于保留。如果遇到 '-' 操作，就只将游标 '-' 操作符影响的字符数长度，但是不追加这部分字符到结果中，相当于删除。如果遇到 '+' 操作符，则游标不变，直接将 op 中的字符追加到结果中。
如果使用伪代码简单描述，则是如下这样：

var res
textIndex := 0 // 初始化游标
for i := 0; i < len(CS); i++ {
   if CS[i].Op == '+' { // 如果是 '+' 操作符，游标不变，将 CS 中的字符追加到结果中
      res = append(res, CS[i].CharBank)
   } else if CS[i].Op == '=' { // 如果是 '=' 操作符，将原 Text 中相应位置的字符追加到结果中，并移动游标
      res = append(res, oldText[textIndex:textIndex+CS[i].CharNum]...)
      textIndex += CS[i].CharNum
   } else if CS[i].Op == '-' { // 如果是 '-' 操作符，则只移动游标，跳过原 text 这部分字符
      textIndex += CS[i].CharNum
   }
}

return res

attribs 部分的 apply 操作，我们可以像处理 follow 算法那样，对于文档和 changeset 的 ops数组进行逐个按位的处理。
由于文档的 attribs 解析之后只有 '+' 操作符，而changeset 包括了 '+'， '=' ，'-' 这三种操作，所以组合起来相当于一共有3种操作。我们从changeset 不同 Op 的操作简述这3种组合的处理逻辑。

1. 如果 CS 是插入操作，则直接将 CS 的 op 追加到结果中，因为插入操作是在文档中新增数据，不受文档原数据的影响，直接追加就好。
2. 如果CS 是删除操作，则需要判断 CS 删除操作影响的字符数和文档当前 Op 影响的字符数大小。如果删除的字符数多，则将删除操作影响的字符数减去文档当前 Op 影响的字符数，然后继续按位判断下一个文档的 OP。反之如果是删除的字符数较小，则将文档当前 Op 影响的字符数减去 CS 删除操作影响的字符数，然后继续按位判断下一个 CS 的 OP。
3. 如果 CS 是保留操作，仍需要判断CS 保留操作影响的字符数和文档当前 Op 影响的字符数大小。如果保留的字符数多，则将保留操作影响的字符数减去文档当前 Op 影响的字符数，并将文档的 Op追加到结果中，然后继续按位判断下一个文档的 OP。如果保留的字符数少，则将文档当前 Op 进行拆分，和CS 保留字符数长度相同的一部分追加到结果中，剩余部分保留进行进行下一次判断处理，然后继续按位判断下一个 CS 的 OP。
4. 除此之外，如果 changeset 中的 ops 已经处理完了，则直接将文档剩余的 ops 追加到结果即可。反之，如果文档中的 ops 已经处理完了， 也需要将 changeset 中的 ops 追加到结果中，注意这时候 changeset 剩余的 ops 中，操作符应该会只有 '+' 。

将上述逻辑简单整理成一份伪代码。注意这份伪代码同样没有表现上述序号4的逻辑，也没有关注 changeset 的每一个 OP的属性在 Apply 过程中的处理。

var res
for i, j := 0, 0; i < len(CS) || j < len(Doc); {
   if CS[i].Op == '+' { // CS 是插入，则直接将 CS 的 op 追加到结果中
      res = append(res, CS[i])
      i++
   } else if CS[i].Op == '-' { //  CS 是删除
      if CS[i].CharNum < Doc[j].CharNum { // 如果删除的字符数更少
         Doc[j].CharNum -= CS[i].CharNum // 则将文档该 OP 的字符数相应减小，然后操作CS 下一个 OP
         i++
      } else if CS[i].CharNum > Doc[j].CharNum { // 反之，如果文档该 OP的字符数更少
         CS[i].CharNum -= Doc[j].CharNum // 则将删除OP的字符数相应减小，相当于文档的这个 OP 被完全删除掉
         j++                             // 然后操作下一个文档的 OP
      } else { // 如果两者字符数相等，说明删除操作刚好删除了文档这个 OP，全部跳到下一个处理
         i++
         j++
      }
   } else if CS[i].Op == '=' { // CS 是保留操作
      if CS[i].CharNum < Doc[j].CharNum { // 如果 CS 的字符数更少，则需要将文档的 Op 进行拆分
         newOp := new{CharNum: CS[i].CharNum, Op: Doc[j].Op} // 构造一个新 Op，新 Op 的其他内容都和文档这个 Op 相同，只有字符数是 CS Op 的字符数
         Doc[j].CharNum -= CS[i].CharNum                     // 原先文档的 Op 字符数响应减小，然后开始操作 CS 下一个 OP
         res = append(res, newOp)                            // 新 Op 追加到结果中
         i++
      } else if CS[i].CharNum > Doc[j].CharNum { // 如果文档 Op 的字符数更少，则文档的这个 Op 全部保留，追加到结果中
         CS[i].CharNum -= Doc[j].CharNum // 同时将CS OP 的字符数相应减小，继续操作文档下一个 OP
         res = append(res, Doc[j])
         j++
      } else { // 如果字符数相同，说明 Doc 的这个Op 刚好被全部保留下来，追加到结果中
         res = append(res, Doc[j])
         i++
         j++
      }
   } else { // CS 中出现其他操作符，则是异常情况了
      error
   }
}
return res

这篇关于easysync 协同算法详解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！