Protocol‎ > ‎Design Documents‎ > ‎

OT insertion order design proposal

    2010-01

    Alex North (anorth@google.com), Alex Mah, David Hearnden (hearnden@google.com)

    Objective

    This design proposes changing the way concurrent insertions at the same offset are treated by operational transform, with the objective of simplifying development of data models embedded in wave documents.

    Background

    Two clients may concurrently submit operations to insert content at the same point in a document. These operations reach the server in some order, where the operational transform algorithm determines in which order the insertions appear in the resulting document.

    For example, with an initial document state "xy", two clients A and B may concurrently attempt to insert a character at position 1.

    Client A: retain 1, insert "a", retain 1 -> "xay"

    Client B: retain 1, insert "b", retain 1 -> "xby"

    With the current algorithm, the insertion point is not pushed by the first operation. If client A's operation reaches the server before client B's, the resulting document state will be

    "xbay"

    Thus the order of items in the document is reversed from the order they arrived at the server. This is unnatural for developers:

    • The last-is-first interpretation means data structures need to be represented "backwards" in the document to have desired transform. To create a list, appending to the list would be implemented as inserting at position zero, like a stack. This is awkward for humans to examine and debug. The textual representation doesn't match the interpretation.
    • Currently, when offline or flaky clients come back online, their new content is inserted before content that online clients already submitted to the server. With a change, the content comes after content which reached the server first.
    • With a change, other people's carets, as seen in your editor, are more representative of where in-flight characters will actually arrive.
    • The conversation manifest is implemented incorrectly (an example of the subtleness), and needs migration without a change.

    Reasons we might wish to keep the existing behaviour:

    • Changing the OT behaviour means consequent changes to some ADT classes, the DocumentBased*Map types in particular. Therefore, the meaning of data that is exposed via those classes can change.
    • For typing, the existing behaviour means that your characters will never interleave with another user's characters. Interleaving is theoretically possible after the change, but our restricted OT means this is unlikely to be a problem. If the cursor and selection boundaries, under the control of the editor, are not pushed by insertions then interleaving adjacently-typed characters won't occur.

    Design

    We change the transform function so that content from multiple participants being concurrently inserted at the same point will be ordered in the final document in the same order in which they arrived at the server. In the example above, with Client A's operation reaching the server before Client B's, the resulting document state will be

    "xaby"

    Changing OT code in this way will require all clients and servers to update simultaneously. A protocol version number will be added to the relevant transports, details of which are beyond the scope of this design.

    Stored wave snapshots remain valid after this change.