Conflicts and Transform

In collaborative editing, a conflict refers to a situation where multiple users simultaneously edit the same or related parts of a document, causing their editing operations to affect or interfere with each other, potentially undermining the consistency of the document or the users' intentions.

In the case of concurrent editing by users, the system needs to ensure:

• Consistency of data across all copies: Ensure that the data in each copy remains consistent in the end.

• Preservation of user intent as much as possible: The final data should align with users' expectations, but this can only be achieved to the best extent possible. In some conflict scenarios, it is difficult to satisfy all users' intentions.

Example Conflict Scenario

type=warning

The operations (Ops) in the following examples are simplified for demonstration purposes. In real-world scenarios, the structure and content of Ops may vary depending on the document type, operation complexity, and implementation.

Consider a shared document with an initial text of "xyz," edited simultaneously by two clients (Client A and Client B):

• Client A: Inserts "a" at position 1 (between "x" and "y"), expecting the result to be "xayz."

• Client B: Inserts "b" at position 2 (between "y" and "z"), expecting the result to be "xybz."

If the server simply applies and broadcasts operations (ops) in the order they are received, the following figure illustrates an inconsistent scenario.

type=note

Due to factors such as network latency, messages sent and broadcasted are not delivered instantly. The following figure simplifies this aspect.

Explanation

1. Initial State: The text on all clients and the server is "xyz."

2. Local Operations:

   1. Client A executes { pos: 1, text: 'a' }, inserting "a" at position 1, resulting in "xayz."

   2. Client B executes { pos: 2, text: 'b' }, inserting "b" at position 2, resulting in "xybz."

3. Submission and Server Processing:

   1. The server applies and broadcasts a in order ("xyz" → "xayz") and then b ("xayz" → "xaybz").

4. Client Acceptance and Application:

   1. Client A receives b ({ pos: 2, text: 'b' }), inserting "b" at position 2 in "xayz" (between "a" and "y"), resulting in "xabyz."

   2. Client B receives a ({ pos: 1, text: 'a' }), inserting "a" at position 1 in "xybz" (between "x" and "y"), resulting in "xaybz."

5. Result: Client A has "xabyz," Client B has "xaybz," leading to inconsistency.

How OT Technology Resolves Conflicts

Operational Transformation (OT) resolves conflicts by adjusting operations to ensure that the final state is consistent across all clients and the server. Both the server and clients transform received operations to accommodate operations that have already been executed.

For the example above, the following Transform rules can be established:

// side indicates which op arrived at the server later. If side === 'left', it means op1 arrived at the server later than op2.
function transform(op1, op2, side: 'left' | 'right') { 
    if (op1.pos > op2.pos || (op1.pos === op2.pos && side === 'left')) {
        return { pos: op1.pos + op2.text.length, text: op1.text };
    }
    return op1;
}

Diagram: Process Using OT Transform

Explanation:

1. Initial State: The text on all clients and the server is "xyz."

2. Local Operations:

   1. Client A executes { pos: 1, text: 'a' }, resulting in "xayz."

   2. Client B executes { pos: 2, text: 'b' }, resulting in "xybz."

3. Submission and Server Processing:

   1. The server accepts and applies a, resulting in "xayz."

   2. The server accepts b and transforms b: b_transformed = Transform(b, a, 'left').

      1. b.pos (2) > a.pos (1), so pos is increased by 1 (the length of "a"), resulting in { pos: 3, text: 'b' }.

   3. The server applies b_transformed, inserting "b" at position 3 in "xayz" (between "y" and "z"), resulting in "xaybz."

4. Broadcast and Application:

   1. Client A receives b_transformed ({ pos: 3, text: 'b' }), inserting "b" at position 3 in "xayz," resulting in "xaybz."

   2. Client B receives a and transforms a: a_transformed = Transform(a, b, 'right').

      1. a.pos (1) < b.pos (2), so pos remains unchanged, resulting in { pos: 1, text: 'a' }.

   3. Client B inserts "a" at position 1 in "xybz," resulting in "xaybz."

5. Result: All clients and the server have "xaybz," the final state is consistency.

Summary

The core of Operational Transformation lies in dynamically adjusting operations to adapt to the effects of other concurrent operations. This approach does not require locking the document, allowing users to edit freely while ensuring consistency, making it highly suitable for real-time collaborative editing scenarios.

Next Steps

OT_Types