Papers
Google Wave Operational Transformation
David Wang, Alex Mah, Soren Lassen · Google Wave Federation Protocol whitepaper series (version 1.1, July 2010), 2010
The problem: live, concurrent editing without blocking the user
The whitepaper "Google Wave Operational Transformation" (version 1.1, July 2010), by David Wang, Alex Mah, and Soren Lassen, describes how Google Wave achieved live collaborative editing. Here, live and concurrent means that one user sees another's changes as they are made, keystroke by keystroke, and that multiple editors change the same document at the same time. Wave offered this for rich text, with bold, italics, bullets, and headings, and its core technology allowed concurrent modification of structured documents in general, including system data shared between clients and back ends. To do this, Wave uses Operational Transformation (OT), a theoretical concurrency-control framework that had been studied for more than ten years in the context of group editing. The text does not re-explain the basic theory and assumes it is known. In short, the document is replicated at all sites and any user can edit any part at any time. Local operations are executed without delay or blocking, and remote operations are transformed before being executed. Because there are no locks or blocking, local response time does not depend on network latency. This underpins the so-called optimistic interface: the user's action is executed and displayed locally right away, without waiting for the server's response. The starting point for Wave's OT was the paper on the Jupiter system (Nichols et al., 1995), and Wave also adopts an architecture with clients and a server.
Core extension: the client waits for the server's acknowledgment
In basic OT theory, a client can send operations in sequence as fast as it can, and so can the server. As a result, client and server can traverse the state space along different OT paths, depending on when they receive each other's operations, and still reach the same convergent state. The problem is that, with many connected clients, each client-server pair has its own state space. The server would need to maintain one space for each connected client, which can consume a lot of memory, and also convert client operations between those spaces, which complicates the algorithm. Because a simple, efficient server is important to make waves reliable and scalable, Wave changes the basic theory: the client must wait for the server's acknowledgment before sending more operations. Acknowledging means the server transformed the client's operation, applied it to its copy of the wavelet, and broadcast the transformed operation to the other connected clients. While waiting, the client buffers the operations it generates locally and sends them later as a batch. With the acknowledgment, the client can infer the server's OT path, called the server's inferred path, and only sends operations that are already on that path. Result: the server maintains a single state space, the history of applied operations, and it only needs to transform each received operation against that history, apply it, and broadcast it. The cost is that a client sees batches of another client's operations at intervals of about one round-trip time to the other client.
Data model: wavelets, documents and streaming operations
In the Wave model, a wave is a collection of wavelets, and a wavelet contains a collection of documents. A document is made up of a structured document, similar to XML, and annotations. The wavelet is the object on which OT is applied and is where concurrent modification happens. Wavelet operations are divided into document operations, which modify documents, and non-document operations, such as adding or removing a participant from the wavelet. A document operation has a streaming interface, similar to an XMLStreamWriter or a SAX handler, and consists of an ordered sequence of mutations applied as the document is traversed linearly. According to the text, designing it this way makes it easier to write the transform and compose functions. Each character, opening tag, or closing tag is an item, and the gaps between items are positions, with position 0 being before the first item. The retain mutation indicates how many positions to skip before the next mutation. The other mutations are insert characters, insert element start or end, delete characters, delete element start or end, replace attributes, update attributes, and mark an annotation boundary. An example from the text itself: retain 3, insert a p element with the characters "Hi there!", retain 5, delete 4 characters, and retain 2. An entire document can be seen as a single operation applicable to the empty document.
Annotations, transformation and composition of operations
Besides structure, Wave has annotations: metadata associated with a range of items, defined by a start position and an end position. They are useful for describing text formatting and spelling suggestions, without needlessly complicating the underlying structured document format. The streaming design also simplifies two core operations. The first is transformation: the transformer takes two streaming operations, processes them simultaneously in a linear fashion, and produces two streaming operations, which keeps the transformation of a pair of very large operations efficient. The second is composition: document operations were designed so that the composition of any two composable operations is itself a single document operation. The composition B∙A has the property (B∙A)(d) = B(A(d)) for every document d to which A can be applied, that is, applying the composed operation is equivalent to applying A and then B. The composition algorithm also processes the operations as linear streams and is therefore efficient. This property ties into the acknowledgement extension: while waiting for the server, the Wave client composes all of its pending operations, which reduces the number of operations to transform and send. The whitepaper is brief and covers Wave's extensions, not the basic theory of OT, which is pointed to in the whitepaper's two references: the Wikipedia entry on OT and the Jupiter paper.
See the ideas at work
Practice the designs that use this paper in the System Design school.