没有人会说协作是团队合作的关键部分。在团队中，我们经常需要共享，讨论，委托并最终达到使业务成功的共同目标。如今，我们可以使用各种工具来实现这些目的，并且显然，这些工具在过去5到10年中已经取得了长足的发展：我们可以在企业Messenger（Slack，Skype）中聊天，一起编辑文档（Google Docs，Pages，Dropbox），查看彼此的代码（Github Pull请求，Crucible）等。但是由于某种原因，尽管看起来这种想法浮出水面，但电子邮件中的协作并不那么受欢迎。
让我们想象一下这样一种情况，一家公司的首席执行官向投资者写一封重要的电子邮件，并希望从最新的财务报告中添加一些数字。他要求财务部门提供所需的信息。但是由于该电子邮件应代表首席执行官发送，因此他需要自己编辑电子邮件并将财务信息插入电子邮件中（尽管可能会委派工作）。如果他可以简单地与财务部门的同事共享电子邮件草稿，并且他们可以将所有必需的数字直接添加到电子邮件中怎么办？听起来很完美？但是，我们可以借助任何受欢迎的电子邮件客户端来做到这一点吗？我会回答–没有简单的方法可以做到这一点。
在Readdle，我们决定在电子邮件客户端Spark中为用户引入一种新的协作方式。这样做的目的是为我们的用户提供使用他们在Google文档中使用的协作机制的直观，简便的方法。
技术上如何做？如何让多个人同时进行更改并避免冲突，允许格式化，撤消/重做，嵌入式图像等？这些是我们必须回答的问题。
如果您认为这并不难，那么让我向您展示最基本的示例和可能出现的问题。
假设我们有两个人（爱丽丝和鲍勃）想要编辑文档。为简单起见，他们唯一能做的就是“将字符C插入位置N”。真的很简单！我们需要某种方式将这些命令从一个用户转移到另一个用户，然后就完成了。您能在这里看到问题吗？有一个。假设两个用户的初始状态为“ 123456789”，并且该状态已同步，这意味着两个用户看到的字符串相同。在某些时候，他们注意到序列中缺少“ 0”。爱丽丝决定将其添加到文本的开头，而鲍勃则添加到文本的末尾。现在，爱丽丝看到了“ 0123456789”，而鲍勃看到了他自己的字符串的新版本–“ 1234567890”。由于我们在谈论协作，因此应该在用户之间同步结果，以使他们能够看到彼此之间的更改。爱丽丝向鲍勃发送命令：“在位置0插入’0’”，鲍勃向爱丽丝发送命令：在位置9在插入’0’。现在，每个客户端都从相反的客户端接收命令，并尝试采用此状态。怎么了？鲍勃在“ 0”位置插入“ 0” 并得到“ 01234567890”。但是，爱丽丝使用第9个位置来获得文本“ 01234567809”，这与我们期望看到的不完全相同。这是我们需要解决的基本冲突。
实时文本协作的问题并不新鲜，有几种已知的算法可以解决。最著名的是OT（操作转换）和CRDT（无冲突复制数据类型）。那就是我们开始研究的地方。
OT（运营转型）
我们选择OT作为第一个尝试，因为它更加知名和发现。
OT是一种相当古老的算法，于1989年发布，并在Google Wave和后来的Google Docs中被Google成功采用并扩展了附加功能。
基本思想很简单：用户将更改作为操作发送，并根据现有操作转换传入的操作。让我们看一个在上述情况下OT如何为Alice工作的示例。
她有自己的操作“在位置0插入’0’” = INS（’0’，0），现在收到“在位置9插入’0’” = INS（’0’，9）。
根据OT的思想，我们需要考虑自上一个同步点以来的传出操作来转换传入的操作。换句话说，我们需要以应用于外发操作结果的已校正传入操作的结果与未校正操作的结果相同的方式校正操作参数。这意味着我们需要为每对操作类型制定规则，从而产生N2条规则。例如，在我们的例子中，我们有两个插入操作。我们需要基于另一个插入操作（B）转换插入操作（A）的规则。我们可以使用以下规则：如果B操作中的位置小于A中的位置，我们需要将A的位置增加B中文本的长度。让我们检查一下这种情况是如何工作的。Alice的传入操作是INS（’0’，9），传出操作为INS（’0’，0）。我们考虑INS（’0’，0）转换INS（’0’，9）。位置9大于0，因此此位置应增加插入的字符串的长度，即1，因此INS（’0’，9）将变为INS（’0’，9 + 1）= INS（’ 0’，10），然后应用此操作将得出“ 01234567890”。
鲍勃则相反。INS（’0’，0）应该相对于自己的操作INS（’0’，9）进行转换，但是0小于9；无需修改，我们保留INS（’0’，0）。最后，我们得到与Alice相同的字符串：“ 01234567890”。欢呼！
好吧，这并不困难。但是在扩展方法时，您可能会注意到一个问题：如果客户端A发送了他的操作，我们如何知道客户端B在发送操作时是否已经接收并应用了它？我们是否需要转换B的传入操作？为了解决这个问题，我们需要让每个客户端了解其他客户端的当前状态的方法，如果有多个客户端，这会变得很昂贵。为了避免这些成本，我们可以使用集中式的真理来源服务器来协调所有客户。基本上，客户端仅与服务器同步；他们只需要知道它的状态。这种方法的缺点是执行任务，服务器基本上需要充当客户端，同时接受来自其他客户端的操作。这意味着我们需要在服务器上复制在客户端上实现的所有逻辑，从而使将来的更新，测试和调试更加复杂。记住，我们只是在谈论一种类型的操作，但是现实生活要复杂一些（考虑格式，图像等）。我们需要为所有可能的操作对发明转换并进行编码。当我们需要添加撤消/重做功能时，事情变得更加复杂。
考虑到所有这些，我们决定休息一下，考虑其他可能性– CRDT。
CRDT（无冲突复制数据类型）
CRDT的基本概念非常简单：“可以在网络中的多台计算机之间复制的结构，其中副本可以独立并发地更新，而无需副本之间的协调，并且在数学上始终可以解决不一致问题。这可能会导致。” （维基百科）。或用通俗易懂的话来说，该结构允许我们以任何顺序应用操作，没有任何延迟和重复，而无需任何转换。听起来像伏都教。为了让您了解如何实现，我们可以看一下最简单的CRDT，即“仅增长计数器”。
仅增长计数器
有什么比柜台更简单的？唯一可用的操作是“增加1；增加1”。唯一的结果就是计数器的最终值。但是，如果要允许在具有对等同步功能的多个分布式节点上使用此计数器，事情就从来没有那么简单。最初，CRDT结构应该在连接不稳定的环境中工作，在这种环境中，可能会丢失或重复封装。实际上，我们不需要这种级别的稳定性，因为我们拥有可以保证交付的网络协议。但是我们可以看看最坏的情况。我们如何传输计数器的更新？我们无法广播更新后的值，因为它可能已被其他用户更改并过时。我们无法发送“增量”操作，因为消息可能重复。
节点广播其值，每个节点存储所有节点的值。为了得到结果值，将所有节点的值相加。每个节点都可以随时更改该值并将其广播给其他节点，而不会发生冲突。事件的重复不是问题。我们只广播值，不广播操作；没有重复申请的风险。延迟也不是问题。我们稍后会收到我们的价值。甚至在传输中交换数据包也不成问题，因为我们知道，价值只会增长。我们丢弃值低于当前值的数据包。简洁易用，优雅且适用于任何网络。
这个简单的示例给出了CRDT算法如何解决协作问题的想法。但是，您记得我们的目标不是简单的计数器，而是复杂的文本协作。幸运的是，有针对此问题的CRDT算法。我们决定尝试的第一个叫做Logoot。
徽标
基本思想是为文本的每个字符分配唯一的ID，以使ID仅在文本中增长并在操作中使用它们。无论我们如何执行更改，它都可以使文本保持同步。这是由于静态ID及其严格的顺序而实现的。在下面的示例中，让我们看看它是如何工作的。
两个用户正在尝试写单词“ HELLO”。
爱丽丝想插入第一个字符“ H”。要创建此操作，我们应该为此新字符生成一个id。为了限制我们的选择并从头开始，我们添加了虚拟字符S（用于Start）和E（用于End）。令S的id = 0且E =1000。生成新id的算法是一个有趣的话题，但是现在，为简单起见，让我们选择第一个可用字符，该新字符为1。现在我们有操作INS（’H’，1）。
鲍勃（Bob）收到插入ID为1的’H’的操作。我们在当前文本中搜索最大ID小于1的字符（请注意，因为文本的ID严格增长，我们可以使用二进制搜索来快速完成此操作）。显然，我们找到S作为字符，并在其后插入’H’。成功！现在，所有节点都具有“ H”。
现在，爱丽丝想在“ H”之后插入“ L”。同样，我们在1（’H’）和1000之间选择id。再次，我们使用简单的生成器作为id，并获取下一个可用的ID，即2，然后在其他节点上重复上一步。成功！在所有节点上都有“ HL”。
但是，等等，看来我们的爱丽丝忘了在“ H”和“ L”之间插入“ E”。我们需要一个1 <id <2的ID。嗯…好棘手。但是谁说我们的IDscan只能是整数。我们可以有一个整数数组。我们在第一个级别上选择1并转到第二个级别，该级别当前为空。在这里，我们可以再次使用虚拟0和1000，并在它们之间选择任意数字。例如，我们可以选择1，结果ID为1.1。我们维持严格的顺序，其他节点可以将操作应用于其状态。真好！我们就快到了。
记住，我们正在合作。同时，鲍勃注意到相同的错误，并尝试修复它。但是他似乎是荷兰人，因此决定添加“ A”而不是“ E”（众所周知，“你好”在荷兰语中是“你好”）。
由于他们彼此之间并不了解，因此根据我们当前的算法，两个字符都收到相同的ID，因此我们中断了递增的顺序。
看起来像个问题，但幸运的是，它很容易修复。
首先，让我们为每个协作者分配一些ID（我们称其为站点ID）。（为获得更好的可视化效果，我们将在此处使用“ A”和“ B” ID，但在现实生活中，使用整数序列会更加方便。）将此ID添加到字符ID的每个部分。A创建的1是（1：A）。为了确定两个字符ID的顺序，我们在比较中使用了站点ID，这再次为我们提供了所有客户端的严格统一的顺序。就是这个。问题解决了，即使在发生碰撞的情况下，我们也有严格的命令。
使用这种简单的算法，我们能够以任何顺序添加任意数量的字符，并且始终为所有协作者获得一致的结果。可以想象，删除操作也很简单。我们指定要删除的字符的ID。插入和删除操作使我们可以对纯文本进行全面的操作。
您可能会在这里注意到一件重要的事情：使用这些操作，如果事件顺序错误（例如，插入后删除与删除后插入），则系统将无法工作。有多种方法可以解决此问题，但幸运的是，在我们的情况下，我们使用集中式服务器，并且有协议的保证，我们可以接收所有事件并以正确的顺序接收它们。
回到我们最初的任务，此算法足以开始原型设计。我们很高兴开始编码，很快有了我们的第一个协作引擎概念证明。它像一种魅力一样工作……除了一个问题，但一个讨厌的问题。假设有两个用户离线工作，过了一会儿，他们开始同步文档。第一个事件具有事件H-1：A，E- 2：A，L-3：A，L-4：A，O-5：A，第二个事件具有事件B-1：B，Y- 2：B ，E-3：B。合并的结果是什么？
HBEYLELO看起来一团糟，对不对？两个人的宝贵工作被毁了！绝对没有准备好生产。考虑到这一点，我们回到了董事会以寻找新的算法。
RGA（复制生长阵列）
这是一个非常艰难的时刻，因为我们认为也许我们做出了错误的选择，我们应该回到OT算法。幸运的是，经过一番搜索，我们从CRDT算法集中找到了另一种算法，称为RGA（复制生长阵列）。它没有合并的问题，与Logoot非常相似。看起来很容易快速尝试。我们再次开始编码。
让我们简要地看一下这个算法。每个字符都有一个ID，但是现在我们通过使用序列以以下方式生成ID：new ID =（max_id +1，site_id）。现在，插入操作包含插入点左侧的字符的ID，要插入的符号的新生成的ID和符号本身。如果发生冲突（当两个操作使用与插入点相同的位置时），我们使用以下规则：检查插入点右侧的字符，跳过ID大于新字符ID的所有字符。它允许所有协作者使用相同的严格顺序。
删除呢？这是RGA的第一个缺点。由于所有操作都使用现有字符的ID作为参考，因此我们无法删除其中一个，因为其他客户端的事件可能正在使用它。为了解决这个问题，我们将删除的字符标记为一个逻辑删除，将其从文本中删除，但保留在内部存储器中。似乎我们有所有的难题：我们可以插入，我们可以删除，我们可以编辑纯文本！
我们将Logoot实施转换为RGA，并开始在可能出现的所有情况下进行测试。幸运的是，结果是非常可靠的，这次我们没有发现任何关键问题，只是通过一些优化解决了一些性能问题。
当达到或多或少稳定的算法版本时，我们就开始在生产中实现它。
结果
总而言之，我们已经成功实现了RGA用于文本协作，并且目前将其用于Spark中的共享草稿功能。
让我们快速了解一下该算法的优缺点：
优点
1.简单的算法使测试，调试，添加新功能和寿命变得更容易：-)。
2.所有合并逻辑都在客户端进行了合并，从而使后端保持简单。因此，在进行进一步更新的情况下，我们无需在两侧进行更改。
缺点
1.应存储完整的事件历史记录。没有简单的方法来保存中间快照。
2.当用户打开共享草稿以重建文档的最终状态（导致打开延迟）时，应处理完整的历史记录。
3. ID在文本中随机排列；要查找id的字符索引，我们必须使用慢速线性搜索。
我们并没有停止这个结果。后续步骤将支持嵌入式图像，格式化文本和撤消/重做。我们通过实时更新添加了对当前选择的广播。当然，我们计划在将来添加越来越多的功能。