（翻译）《黑客》2010年08月第三期之理解和应用操作转换(二)

这是理解和应用操作转换的第二部分

第一部分地址在此http://linux.cn/home/space.php?uid=6600&do=thread&id=4943

After applying a’, the server broadcasts the operation to all clients, including the one which originated the operation. This is a very important design feature: whenever the server applies a transformed operation, it sends that operation off to all of its clients without delay. As long as we can guarantee strong ordering in the communication channels between the client and the server (and often we can), the clients will be able to count on the fact that they will receive operations from the server in exactly the order in which the server applied them. Thus, they will be able to maintain a locally-inferred copy of the server’s history.

在应用操作a’后，服务器广播该操作给所有客户端，包括发起该操作的客户端。这是一个非常重要的设计特点：每当服务器应用一个转换操作，就立即把它发送给所有客户端。只要我们能保证强客户端和服务器之间通信渠道的严格定序（通常我们可以），客户端就能够指望按照服务器应用顺序依次收到操作。因此，客户端就能够保留一份本地推衍的服务器历史记录副本。

This also means that our client is going to receive a’ from the server just like any other operation. In order to avoid treating our own transformed operations as if they were new server operations, we need some way of identifying our own operations and treating them specially. To do this, we add another bit of metadata to the operation: a locally-synthesized unique ID. This unique ID will be attached to the operation when we send it to the server and preserved by the server through the application of OT. Thus, operation a’ will have the same ID as operation a, but a very different ID from operations c and d.

这也意味着我们客户端会收到来自服务器的操作a’，就像其他操作一样。为了避免把我们自己转换的操作当作新的服务器操作，我们需要某种方法来确定我们自己的操作，并特殊处理它们。要做到这一点，我们又给操作增加另一位元数据：本地合成的唯一的ID。这个唯一的ID将被附加到操作上当我们将其发送到服务器时，并且在服务器执行OT时被保留。因此，操作a’会拥有和操作a一样的ID，区分操作c和d不同的ID。

With this extra bit of metadata in place, clients are able to distinguish their own operations from others sent by the server. Non-self-initiated operations (like c and d) must be translated into client state space and applied to the local document. Self-initiated operations (like a’) are actually server acknowledgements of our currently-pending operation. Once we receive this acknowledgement, we can flush the client buffer and send the pending operations up to the server.

有了这一位额外的元数据，客户端就能够区分自己的操作，不会和来自服务器的其他操作混淆。非自发操作（如c和d）必须转换到客户端状态空间，才能应用到本地文档。自发起操作（如a’）实际上是等待服务器确认我们的目前挂起的操作。一旦我们收到此确认，我们可以刷新客户端的缓冲区，并发送挂起的操作到服务器。

Moving forward with our example, let’s say that the client receives operation c from the server. Since c is already parented on a version in our local history, we can apply simple OT to transform it against the composition of a and b and apply the resulting operation to our local document:

向前推进我们的例子，假如客户端收到来自服务器的操作c。由于 c源自我们本地记录中的一个版本，因此我们可以运用简单的OT技术，对应a和b的组合转换它，然后在我们本地文档上应用该结果操作：

Of course, as we always need to keep in mind, the client is a live editor which presumably has a real person typing madly away, changing the document state. There’s nothing to prevent the client from creating another operation, parented off of c’ which pushes it even further out of sync with the server:

当然，我们始终要记住，客户端是一个活生生的编辑器，很可能会人疯狂打字改变者文档的状态。没有什么可以防止客户端在c’之后创建另一个操作，进一步扩大了和服务器的不同步：

This is really getting to be a bit of a mess! We’ve only sent one of our operations to the server, we’re trying to buffer the rest, but the server is trickling in more operations to confuse things and we still haven’t received the acknowledgement for our very first operation! As it turns out, this is the most complicated case which can ever arise in a Wave-style collaborative editor. If we can nail this one, we’re good to go.

这实在是越来越混乱了！我们才只发送了一个操作到服务器，正试图缓冲剩余的，但服务器传来更多的操作越发混淆事情，而且我们仍然没有收到第一次操作的确认！事实证明，这是Wave式的协作编辑能出现的最复杂的情况。如果我们解决了这个，其他的就好办了。

The first thing we need to do is figure out what to do with d. We’re going to receive that operation before we receive a’, and so we really need to figure out how to apply it to our local document. Once again, the problem is that the incoming operation (d) is not parented off of any point in our state space, so OT can’t help us directly. Just as with b in our fundamental compound OT example from earlier, we need to infer a “bridge” between server state space and client state space. We can then use this bridge to transform d and slide it all the way down into position at the end of our history.

我们首先需要做的是想出如何处理d。在接受a’前我们将会接受到操作d，所以我们迫切需要想出如何将它应用到我们的本地文档。再者，还有一个问题是，即将引入的操作(d)不是我们状态空间中任何一点派生的，所以OT不能直接帮助我们。就像在我们早先基本复合型OT例子中的b一样，我们需要推得一座“桥梁”连接服务器和客户端的状态空间。然后我们可以利用这座桥转换d，并移动到我们历史记录的尽头位置。

To do this, we need to identify conceptually what operation(s) would take us from the parent of d to the the most recent point in our history (after applying e). Specifically, we need to infer the green dashed line in the diagram below. Once we have this operation (whatever it is), we can compose it with e and get a single operation against which we can transform d.

要做到这一点，我们需要概念性确定什么样操作能让我们从d父节点到我们历史记录的最近一个点（应用e之后）。具体来说，我们需要推定下图所示的绿色许仙。一旦我们拥有这个操作（不管它是什么），我们可以集合它和e，得到单一一个操作，对应它我们可以转换d。

The first thing to recognize is that the inferred bridge (the green dashed line) is going to be composed exclusively of client operations. This is logical as we are attempting to translate a server operation, so there’s no need to transform it against something which the server already has. The second thing to realize is that this bridge is traversing a line parallel to the composition of a and b, just “shifted down” exactly one step. To be precise, the bridge is what we would get if we composed a and b and then transformed the result against c.

首先要知道的是，推得的桥（绿色虚线）会由客户端操作专门组成。这是合乎逻辑的，因为我们正试图转换服务器的操作，因此没有必要对应某些服务器已经有的东西转换它。第二个需要知道的是，这座桥横贯一条平行于a和b集合的直线，只是“向下减了一档”。确切地说，我们可以通过组合a和b，然后对应c转换得到这座桥。

Now, we could try to detect this case specifically and write some code which would fish out a and b, compose them together, transform the result against c, compose the result of that with e and finally transform d against the final product, but as you can imagine, it would be a mess. More than that, it would be dreadfully inefficient. No, what we want to do is proactively maintain a bridge which will always take us from the absolute latest point in server state space (that we know of) to the absolute latest point in client state space. Thus, whenever we receive a new operation from the server, we can directly transform it against this bridge without any extra effort.

现在，我们可以来专门尝试检测下这种情况，编写代码找出a和b，把它们组合到一起，并对应c进行转换，得到的结果集合e，最后对应这最终产物转换d，但你可以想象，这将会一团糟。更重要的是，这样会非常低效。我们所要做的是积极维护一座总是会把我们从服务器状态空间上时间上绝对最近的一点（就我们所知的）带到客户端状态空间上同样点的桥梁。因此，当我们从服务器接收新的操作时，我们就可以直接对应这座桥进行转换，而不需要额外的工作。

Building the Bridge

架设桥梁

We can maintain this bridge by composing together all operations which have been synthesized locally since the point where we diverged from the server. Thus, at first, the bridge consists only of a. Soon afterward, the client applies its next operation, b, which we compose into the bridge. Of course, we inevitably receive an operation from the server, in this case, c. At this point, we use our bridge to transform c immediately to the correct point in client state space, resulting in c’. Remember that OT derives both bottom sides of the diamond. Thus, we not only receive c’, but we also receive a new bridge which has been transformed against c. This new bridge is precisely the green dashed line in our diagram above.

同服务器分歧点开始，我们可以通过把所有本地合成的操作组合到一起来维持这座桥梁。因此，这座桥开始只包含a。接着，客户端应用了下一个操作b，我们也用它来搭桥。当然，在这种情况下我们不可避免地收到来自服务器的操作c。这一点上，我们利用我们的桥梁立即转换c到客户端状态空间中正确一点，结果得到c’。应该记得OT作用会同时得到菱形的两个底边。因此，我们不仅得到c'，我们也得到了新的桥梁，这是对应c转化而来的。这座新的桥梁正是我们上图中的绿色虚线部分。

Meanwhile, the client has performed another operation, e. Just as before, we immediately compose this operation onto the bridge. Thanks to our bit of trickery when transforming c into c’, we can rest assured that this composition will be successful. In other words, we know that the result of applying the bridge to the document resulting from c will be precisely the document state before applying e, thus we can cleanly compose e with the bridge.

这是，客户端已执行了另一项操作e。正如前面一样，我们立即把该操作组合到桥梁中。由于转换c到c’时的很小的技巧，我们可以确信这次组合将获得成功。换句话说，我们知道对操作c作用之后的文档应用该桥梁所得的结果恰好就是应用e之前的文档状态，因此，我们可以简洁清楚的组合e和桥。

Finally, we receive d from the server. Just as with c, we can immediately transform d against the bridge, deriving both d’ (which we apply to our local document) as well as the new bridge, which we hold onto for future server translations.

最后，我们从服务器收到d。正如和c一样，我们可以立即对应所得桥梁转化d，获得了d’（适用于本地的文档），以及新的桥梁，我们保留着可以用于未来服务器操作转换。

With d’ now in hand, the next operation we will receive from the server will be a’, the transformed version of our a operation from earlier. As soon as we receive this operation, we need to compose together any operations which have been held in the buffer and send them off to the server. However, before we send this buffer, we need to make sure that it is parented off of some point in server state space. And as you can see by the diagram above, we’re going to have troubles both in composing b and e (since e does not descend directly from b) and in guaranteeing server parentage (since b is parented off of a point in client state space not shared with the server).

得到了d’，我们会从服务器得到的下一个操作就是a’，我们早先操作a的转换后的版本。当我们收到此操作，我们需要把保存在缓冲区的所有操作组合到一起，然后发送给服务器。不过，在我们发送此缓冲区前，我们需要确保它的父节点是服务器的状态空间中的某点。正如上图所示，我们存在两个问题，一是组合b和e（因为e不是直接延续b的），二是服务器父子关系的确定（因为b是源自于客户端状态空间中的a点，不与服务器共享）。

To solve this problem, we need to play the same trick with our buffer as we previously played with the translation bridge: any time the client or the server does anything, we adjust the buffer accordingly. With the bridge, our invariant was that the bridge would always be parented off of a point in server state space and would be the one operation needed to transform incoming server operations. With the buffer, the invariant must be that the buffer is always parented off of a point in server state space and will be the one operation required to bring the server into perfect sync with the client (given the operations we have received from the server thus far).

为了解决这个问题，我们需要针对缓冲部分玩些和我们先前用于转换桥梁一样的伎俩：任何时候客户端或服务器做任何事情，我们都相应调整缓冲部分。架设桥梁时候，我们的不变地方是桥梁始终以服务器状态空间中某点为父节点，并且是用来转换引入的服务器操作需要的这样一个操作。而调整缓冲区，不变地方是缓冲部分始终以服务器状态空间中某点为父节点，并且是服务器和客户端完美同步必需的这样一个操作（根据目前为止从服务器收到的操作）。

The one wrinkle in this plan is the fact that the buffer cannot contain the operation which we have already sent to the server (in this case, a). Thus, the buffer isn’t really going to be parented off of server state space until we receive a’, at which point we should have adjusted the buffer so that it is parented precisely on a’, which we now know to be in server state space.

在这一计划中有一点点曲折，缓冲区不能包含我们已经发送给服务器的操作（例子中的a）。因此，缓冲部分在我们收到a’之前是不可能变为源自于服务器状态空间中某点的，在收到a’之后，我们就应该调整缓冲部分，使之精确的以a’（我们知道它存在于服务器状态空间中）为父节点。

Building the buffer is a fairly straightforward matter. Once the client sends a to the server, it goes into a state where any further local operations will be composed into the buffer (which is initially empty). After a, the next client operation which is performed is b, which becomes the first operation composed into the buffer. The next operation is c, which comes from the server. At this point, we must somehow transform the buffer with respect to the incoming server operation. However, obviously the server operation (c) is not parented off of the same point as our buffer (currently b). Thus, we must first transform c against a to derive an intermediary operation, c”, which is parented off of the parent of the buffer (b):

建设缓冲部分是一个相当简单的事。一旦客户端发送a到服务器，就进入到编辑下一步本地操作到缓冲区的状态。A之后，下一个客户端操作是b，它成为缓冲区第一个的操作成员。接下来的操作是来自服务器的c。这时候，我们必须针对引入的服务器操作以某种方式转换缓冲部分。然而，很明显的服务器操作(c)和我们缓冲部分（现在是b）不是源自于同一点。因此，我们必须首先对应a转换c以得到中间操作c”，该操作和缓冲部分(b)有着相同的父节点：

Once we have this inferred operation, c”, we can use it to transform the buffer (b) “down” one step. When we derive c”, we also derive a transformed version of a, which is a”. In essence, we are anticipating the operation which the server will derive when it transforms a against its local history. The idea is that when we finally do receive the real a’, it should be exactly equivalent to our inferred a”.

推得这步操作c”，我们可以利用它来转换缓冲部分(b)向“下”一步。当我们获得c”时候 ，我们也得到了操作a的转换版本，a”。从本质上讲，我们期望能使用当服务器对应其历史记录转换a时获得的这个操作。这个想法是我们最终收到的真正的a’应该完全等同于我们的推得的a”。

At this point, the client performs another operation, e, which we immediately compose into the buffer (remember, we also composed it into the bridge, so we’ve got several things going on here). This composition works because we already transformed the buffer (b) against the intervening server operation (c). So e is parented off of c’, which is the same state as we get were we to apply a” and then the buffer to the server state resulting from c. This should sound familiar. By a strange coincidence, a” composed with the buffer is precisely equivalent to the bridge. In practice, we use this fact to only maintain one set of data, but the process is a little easier to explain when we keep them separate.

这时，客户端又执行了另一个操作e，我们立即把它集成到缓冲部分（请记住，我们还把它也集合到桥梁中，所以我们需要在这里做好几件事）。这个组合能做到，因为我们已经对应介入的服务器操作(c)转换了缓冲部分(b)。因此e的父节点c’，和我们在c产生的服务器状态之上应用a”和缓冲部分后得到的结果一样。这应该听上去很熟悉吧。由于某种奇怪的巧合，a”结合缓冲部分，刚好相当于我们的桥梁。在实践中，我们利用这个事实只用维持一组数据，但分开保存的话解释这一过程会变得更加容易些。

Checkpoint time! The client has performed operation a, which it sent to the server. It then performed operation b, received operation c and finally performed operation e. We have an operation, a” which will be equivalent to a’ if the server has no other intervening operations. We also have a buffer which is the composition of a transformed b and e. This buffer, composed with a”, serves as a bridge from the very latest point in server state space (that we know of) to the very latest point in client state space.

查核时刻！客户端的执行操作a，并把它发送到服务器。然后，它执行操作b，接受操作c，然后最终执行操作e。我们还有一个操作a”， 如果服务器没有其他介入操作这会等同于a'。我们也有一个缓冲部分，由转换后的b和e组合而成。此缓冲部分和a”组合就可以起到连接服务器状态空间上的最新点（就我们所知的）和客户端状态空间最新点的桥梁作用。

Now is when we receive the next operation from the server, d. Just as when we received c, we start by transforming it against a” (our “in flight” operation). The resulting transformation of a” becomes our new in flight operation, while the resulting transformation of d is in turn used to transform our buffer down another step. At this point, we have a new a” which is parented off of d and a newly-transformed buffer which is parented off of a”.

现在我们收到了来自服务器的下一个操作d。当我们收到c后，开始对应a”（我们“飞行”操作）转换它。a”的转换结果成为我们新的飞行操作，而由此产生的转换后的d现在转而用于转换我们的缓冲部分向下更进一步。在这个时候，我们拥有一个新的a”，由d派生而来，和新转换的派生自a”的缓冲部分。

Finally, we receive a’ from the server. We could do a bit of verification now to ensure that a” really is equivalent to a’, but it’s not necessary. What we do need to do is take our buffer and send it up to the server. Remember, the buffer is parented off of a”, which happens to be equivalent to a’. Thus, when we send the buffer, we know that it is parented off of a point in server state space. The server will eventually acknowledge the receipt of our buffer operation, and we will (finally) converge to a shared document state:

最后，我们从服务器收到a’。我们可以做少许验证以确保a”等同于a’，但这是没必要的。我们确实需要做的就是获取我们的缓冲区并将其发送到服务器。应该记得，缓冲区的父节点就是恰好是等同于a’的a”。因此，当我们发送缓冲部分，我们知道了它的父节点就是在服务器状态空间的一点。服务器将最终确认收到我们的缓冲部分操作，并且我们会（最终）收敛到一个共享文档的状态：

The good news is that, as I mentioned before, this was the most complicated case that a collaborative editor client ever needs to handle. It should be clear that no matter how many additional server operations we receive, or how many more client operations are performed, we can simply handle them within this general framework of buffering and bridging. And, as when we sent the a operation, sending the buffer puts the client back into buffer mode with any new client operations being composed into this buffer. In practice, an actively-editing client will spend most of its time in this state: very much out of sync with the server, but maintaining the inferred operations required to get things back together again.

好消息是正如我前面提到的，这是协作编辑处理客户端会需要去处理的最复杂的情况。应该清楚，无论接受多少额外的服务器操作，或有执行更多的客户操作，我们都可以在这个缓冲和桥接的一般框架范围内进行简单的处理操作。而且，当我们发送了操作a，这个缓冲部分后会迫使客户端回置到缓冲模式，新的客户端操作会被集成到缓冲区。在实际使用中，积极编辑的客户端会花费其大部分时间处于这种状态：与服务器非常的不同步，但维持着再次统一需要的推断出的操作。

Conclusion

结论

The OT scheme presented in this article is precisely what we use on Novell Pulse. And while I’ve never seen Wave’s client code, numerous little hints in the waveprotocol.org whitepapers as well as discussions with the Wave API team cause me to strongly suspect that this is how Google does it as well. What’s more, Google Docs recently revamped their word processing application with a new editor based on operational transformation. While there hasn’t been any word from Google on how exactly they handle “compound OT” cases within Docs, it looks like they followed the same route as Wave and Pulse (the tell-tale sign is a perceptible “chunking” of incoming remote operations during connection lag).

这篇文章中提出的OT框架正是我们在Novell Pulse使用的。虽然我从来没有见过Wave的客户端代码，但在waveprotocol.org白皮书上无数的小提示以及与Wave的API小组讨论使我强烈怀疑Google可能也是这样做的。更重要的是，Google Docs最近更新修订其文字处理程序，使用了新的基于操作转换的编辑器。虽然还没有来自Google任何就它们的Docs如何处理“复杂型OT”情况的信息，但它看起来像和Wave和Pulse一样遵循相同的路线（在连接延迟情况下位移指示器符号是引入远程操作可察觉的组块）。

None of the information presented in this article on “compound OT” is available within Google’s documentation on waveprotocol.org (unfortunately). Anyone attempting to implement a collaborative editor based on Wave’s OT would have to rediscover all of these steps on their own. My hope is that this article rectifies that situation. To the best of my knowledge, the information presented here should be everything you need to build your own client/server collaborative editor based on operational transformation. So, no more excuses for second-rate collaboration!

这篇文章中提到的关于“复合型OT”的任何信息在waveprotocol.org的Google文档中都不存在（不幸啊）。任何企图实现基于Wave OT的协同编辑器都必须依靠自己重现这些步骤。我的希望是这篇文章能改变这种状况。据我所知，文章提到的信息应该是你建立自己的基于操作转换的客户端/服务器协同编辑器需要的所有东西。因此，没有更多理由还使用二流协同机制了！

========================================

请大家支持黑客中文 谢谢大家 传送门