This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

In this paper, we mainly introduce the OT algorithm in online document system, which is used to merge the operation of multiple people on the document simultaneously. This paper is mainly divided into four parts: what is OT algorithm, why multi-person editing need OT algorithm, important ideas of document OT algorithm, document OT algorithm actual case.

What is the OT algorithm

The OT algorithm, Operation Transformation, is a common Operation combination algorithm used in online collaboration systems. At the beginning, it was only used to solve the merging problem of online document operation. Later, with the improvement of its theoretical knowledge, it was applied to more fields. However, online document is still one of the typical scenarios.

The OT algorithm is a kind of algorithm, which can be implemented differently in different application scenarios.

Why do multiplayer editors need OT algorithms

Let’s assume that Jia and Wang edit a document at the same time. The initial content of the document is “123”. At this time, Xiao Jia first adds a 4 after 123, and Xiao Wang empress adds a 5 after 123. If there is no merge algorithm, the content change process of Jia’s local document is as follows:

Xiao Jia changed “123” to “1234”.
Receiving the message, wang added a 5 after the 3.
Jia’s local string becomes “12354”.

The content change process of Xiao Wang’s local document is as follows:

Xiao Wang changed “123” into “1235”.
After receiving the message, Jia added a 4 after the 3.
Wang’s local string becomes “12345”.

At this point, wang sees the correct string, jia sees the wrong string. So we need a merger algorithm to ensure that jia and Wang see the final result is correct. When more people edit the document at the same time, the local operation results of all people need to be correct, and the OT algorithm is just right for solving this problem.

Important idea of OT algorithm

The following three sample reference: www3.ntu.edu.sg/scse/staff/…

The basic idea of keeping content consistent

In the image above, two users open the same online document in their browsers with the initial content of “123.”

User 1 and user 2 perform the same operationO1=Insert(0,"X"), insert string X at position 0; User 2 doesO2 = Delete (2, 1), indicating that the element is removed from the second position and the length of deletion is 1.
The string in user 1’s browser is changed to X123. After the O2 operation reaches user 1’s browser, the operation is converted to O1O2 '= Transform (O2, O1) = Delete (3, 1)O2′ is also deleted, but because O1 has already inserted the X string, the deletion position +1, O2′ becomes the deletion of the element starting at position 3, and the deletion length is 1. Perform the O2′ operation on X123. The local string of user 1 becomes X12.
The string in user 2’s browser is changed to “12”. After O1 reaches user 2’s browser, the operation is converted to O2O1'=Transform(O1,O2)=Insert(0,"X"), because the element removed by O2 starts from the second position, it has no effect on the element added by O1′, soO1'=O1. Perform O1′ on “12”, the local string of user 2 becomes “X12”.

In summary, OT generates a new operation through the conversion method that makes the content of the current string consistent between the two browsers after the conversion algorithm is applied.

The basic idea of undo operations

As shown above, two users open the same online document in their browsers, starting with the content “12.”

User 2 performs the operationO1=Insert(2,"Y")Insert string Y in position 2. The local string for user 2 becomes “12Y”.
User 2’s operation reaches user 1’s browser. User 1 does not perform any operation, so O1 executes as it is, and the string in user 1’s browser becomes 12Y.
User 1 performs the operationO2=Insert(0,"X")Insert the string “X” at position 0. The local string for user 1 becomes “X12Y”.
User 1’s operation is displayed in user 2’s browser. User 2 does not perform other operations. Therefore, USER O2 performs the same operation.
Then user 2 performs the undo operation, and the undo operation is denoted asUndo(O1)=T(! O1,O2) = Delete(3). ! O1 is the reverse operation of O1, which should have been Delete(2). Because O2 added a character to the string, the undo operation is Delete(3), and the element at position 3 is deleted, so the local string of user 2 becomes “X12”.
User 2’s operation reaches user 1’s browser, and user 1 executes Delete(3) and the local string becomes “X12”.

In summary, an undo operation requires that the reverse of its own operation be performed correctly, while preserving the execution results from other clients.

The basic idea of operational compression

As shown above, the initial string seen by users 1 and 2 is “123”. User 1 performs four operations in sequence:

O1=Insert(2,"X")
O2=Insert(1,"abc")
O3=Insert(2,"Y")
O4=Delete(7)

We compress the four operations before transmission, and we use L=(O1,O2,O3,O4) to represent the compression of the four operations. The steps of compression are from right to left, and transpose is carried out successively for the two adjacent operations. The specific steps are as follows:

O4 and O3 transpose,transpose(O3,O4) = (O4',O3')At this time,M1: '= Delete (6).O3' = O3.L '= (O1, O2, m1, O3). How do you calculate O4 ‘and O3′? Because O4 is deleting the element at position 7, which is the “X” in “1aYbc2X3”, O3 is inserting the string “Y” at position 2. O4′ and O3′ are exchanged. To ensure consistency, O4’ needs to delete the element at position 6, because the string “X” to be deleted is at position 6. O3 is the string “Y” inserted in position 2, which is not affected after the execution sequence is exchanged with O4, soO3'=O3.
Go ahead, O4′ and O2 transposition,transpose(O2,O4') = (O4'',O2')In order to keep the result consistent, that is, O4′ “should still delete the string” Y “, at this pointO4''=Delete(3),O2′ inserts the string “ABC” again at position 1, meaning unchanged,O2'=O2. At this timeL'=(O1,O4'',O2,O3).
O4 “and O1 are mutually exclusive. O1 adds the string” X “after position 2 and O4” removes the string, so the two operations cancel each other outL'=(O2,O3) 。
O2 adds string “ABC” to position 1, O3 adds string “Y” to position 2. The two insertions can be combined to add “aYbc” to position 1O2'=Insert(1,"aYbc")Said,L'=(O2').
And then the combined operation becomes O2 prime. During data transmission, sending O2′ directly to user 2 is equivalent to sending O1, O2, O3, O4.

In short, the basic idea of data combination is to find the operation that can be combined or eliminated by transpose from right to left, so as to achieve the purpose of compose.

Above is based on the document, for example, OT algorithm is illustrated in three important thoughts, more OT algorithm design ideas you can consult: www3.ntu.edu.sg/scse/staff/…

This document provides practical examples of the OT algorithm

We analyze a document OT algorithm example, source address: github.com/Operational… We classify user actions to documents into three categories:

reatinRemain the same
insertInsert string
deleteDelete string

Operation object: TextOperation

function TextOperation () {
    if (!this || this.constructor ! == TextOperation) {// => function was called without 'new'
      return new TextOperation();
    }

    // this.ops indicates the specific operation, with a positive number indicating that it remains the same, a negative number indicating the length of characters to be deleted, and a string indicating the string to be inserted.
    // For example, [10,"-3",abcd"] means the first 10 characters remain unchanged, then three characters are deleted, and then the "abcd" string is inserted.
    this.ops = [];

    // Indicates the length of the string before the operation
    this.baseLength = 0;
    // Indicates the length of the completion string
    this.targetLength = 0;
  }
Copy the code

This.ops indicates the specific operation, the positive number indicates the unchanged, the negative number indicates the length of the character to be deleted, and the string indicates the string to be inserted. For example, [10,”-3″,abcd”] means that the first 10 characters remain unchanged, then three characters are deleted, and then the “abcd” string is inserted.

This. baseLength indicates the length of the string before the operation.

This.targetlength indicates the length of the operation completion string.

The core method of TextOperation: Transform. Apply (apply(S, A), B’) = apply(apply(S, B), A’)

// Convert two simultaneous conflicting operations A and B to A' and B' with 'apply(apply(S, A), B') = apply(apply(S, B), A')
// This is the core of the OT algorithm
// Operation1, operation2, representing operations A and B;
Operation1prime, operation2Prime denotes operations A' and B', respectively.
TextOperation.transform = function (operation1, operation2) {
    if(operation1.baseLength ! == operation2.baseLength) {throw new Error("Both operations have to have the same base length");
    }

    var operation1prime = new TextOperation();
    var operation2prime = new TextOperation();
    var ops1 = operation1.ops, ops2 = operation2.ops;
    var i1 = 0, i2 = 0;
    var op1 = ops1[i1++], op2 = ops2[i2++];
    while (true) {
        Each iteration ensures that operation1 and OPERATION2 are at the same position in the operation string so that the conversion operation makes sense.
        
        if (typeof op1 === 'undefined' && typeof op2 === 'undefined') {
            // end condition: both ops1 and ops2 have been processed
            break;
        }

        // If one or both of A and B are insert operations.
        // Inserts the string in the corresponding operation, then skips the length of the insert string.
        // retain the length of the string from 'A';
        // retain A and B are insert operations. Retain A and B are insert operations.
        
        if (isInsert(op1)) {
            operation1prime.insert(op1);
            operation2prime.retain(op1.length);
            op1 = ops1[i1++];
            continue;
        }
        if (isInsert(op2)) {
            operation1prime.retain(op2.length);
            operation2prime.insert(op2);
            op2 = ops2[i2++];
            continue;
        }

        if (typeof op1 === 'undefined') {
            throw new Error("Cannot compose operations: first operation is too short.");
        }
        if (typeof op2 === 'undefined') {
            throw new Error("Cannot compose operations: first operation is too long.");
        }

        var minl;
        
        if (isRetain(op1) && isRetain(op2)) {
            // If A and B are retain operations:
            // Compare the length of A and B. After the merge, both A' and B' become the smaller retain operation.
            // when A>B, A' becomes the size of retain B, operation A becomes retain(b-a),
            // Wait for the next cycle to loop with B
            // String merge operations in the same position.
            // If B>A, the same is true.
            if (op1 > op2) {
                minl = op2;
                op1 = op1 - op2;
                op2 = ops2[i2++];
            } else if (op1 === op2) {
                minl = op2;
                op1 = ops1[i1++];
                op2 = ops2[i2++];
            } else {
                minl = op1;
                op2 = op2 - op1;
                op1 = ops1[i1++];
            }
            operation1prime.retain(minl);
            operation2prime.retain(minl);
        } else if (isDelete(op1) && isDelete(op2)) {
            // If A and B are both delete operations, when we merge,
            / / do not need to record the delete (actually remember also can, but if A and B are the delete is not necessary).
            // What we need to do is to ignore the delete with less content and keep the delete with more content in the next iteration,
            // Same as the above retain.
            if (-op1 > -op2) {
                op1 = op1 - op2;
                op2 = ops2[i2++];
            } else if (op1 === op2) {
                op1 = ops1[i1++];
                op2 = ops2[i2++];
            } else{ op2 = op2 - op1; op1 = ops1[i1++]; }}else if (isDelete(op1) && isRetain(op2)) {
            // If A is delete and B is retain, compare the absolute values of A and B.
            // If the delete value is larger than the retain value, then the delete value of A' is the value of B, and the delete length of A becomes A+B,
            // The length of the deleted content is reduced;
            // If B' deletes as much as B';
            // If delete is less than retain, delete of A' is the value of A, retain of B is A+B,
            // The amount of content kept is reduced.
            if (-op1 > op2) {
                minl = op2;
                op1 = op1 + op2;
                op2 = ops2[i2++];
            } else if (-op1 === op2) {
                minl = op2;
                op1 = ops1[i1++];
                op2 = ops2[i2++];
            } else {
                minl = -op1;
                op2 = op2 + op1;
                op1 = ops1[i1++];
            }
            operation1prime['delete'](minl);
        } else if (isRetain(op1) && isDelete(op2)) {
            // If A is retain and B is delete, ditto.
            if (op1 > -op2) {
                minl = -op2;
                op1 = op1 + op2;
                op2 = ops2[i2++];
            } else if (op1 === -op2) {
                minl = op1;
                op1 = ops1[i1++];
                op2 = ops2[i2++];
            } else {
                minl = op1;
                op2 = op2 + op1;
                op1 = ops1[i1++];
            }
            operation2prime['delete'](minl);
        } else {
            throw new Error("The two operations aren't compatible"); }}return [operation1prime, operation2prime];
};
Copy the code

Invert: Invert to restore the operation. Invert is used to undo the operation.

// Calculate the inverse operation, by performing the inverse operation can restore the effect of the operation, the inverse operation is mainly used to implement the undo function.
TextOperation.prototype.invert = function (str) {
    var strIndex = 0;
    var inverse = new TextOperation();
    var ops = this.ops;
    for (var i = 0, l = ops.length; i < l; i++) {
        var op = ops[i];
        if (isRetain(op)) {
            // The reverse operation of retain is still retain,
            // Since the purpose of the reverse operation is to restore the effect of the operation, retain is equivalent to no operation so the reverse operation will remain unchanged.
            inverse.retain(op);
            strIndex += op;
        } else if (isInsert(op)) {
            // The inverse of insert is delete
            inverse['delete'](op.length);
        } else { // delete op
            // The inverse of delete is insertinverse.insert(str.slice(strIndex, strIndex - op)); strIndex -= op; }}return inverse;
};
Copy the code

The compose method should be easy to understand by taking the idea from the transform method above.

Compose (S, compose(A, B)) = compose(S, compose(A, B)
TextOperation.prototype.compose = function (operation2) {
    var operation1 = this;
    if(operation1.targetLength ! == operation2.baseLength) {throw new Error("The base length of the second operation has to be the target length of the first operation");
    }

    // The operation returned after the merge
    var operation = new TextOperation(); 
    var ops1 = operation1.ops, ops2 = operation2.ops; // for fast access
    var i1 = 0, i2 = 0; // current index into ops1 respectively ops2
    var op1 = ops1[i1++], op2 = ops2[i2++]; // current ops
    while (true) {
        // Each iteration ensures that operation1 and OPERATION2 are at the same position in the operation string so that the merge operation makes sense.
        
        // Select how to merge op1 and op2 according to the operation type.
       
        if (typeof op1 === 'undefined' && typeof op2 === 'undefined') {
            Ops1 and OPs2 have been traversed.
            break;
        }
        
        // The following content can be understood by using the transform method.

        if (isDelete(op1)) {
            operation['delete'](op1);
            op1 = ops1[i1++];
            continue;
        }
        if (isInsert(op2)) {
            operation.insert(op2);
            op2 = ops2[i2++];
            continue;
        }

        if (typeof op1 === 'undefined') {
            throw new Error("Cannot compose operations: first operation is too short.");
        }
        if (typeof op2 === 'undefined') {
            throw new Error("Cannot compose operations: first operation is too long.");
        }

        if (isRetain(op1) && isRetain(op2)) {
            if (op1 > op2) {
                operation.retain(op2);
                op1 = op1 - op2;
                op2 = ops2[i2++];
            } else if (op1 === op2) {
                operation.retain(op1);
                op1 = ops1[i1++];
                op2 = ops2[i2++];
            } else{ operation.retain(op1); op2 = op2 - op1; op1 = ops1[i1++]; }}else if (isInsert(op1) && isDelete(op2)) {
            if (op1.length > -op2) {
                op1 = op1.slice(-op2);
                op2 = ops2[i2++];
            } else if (op1.length === -op2) {
                op1 = ops1[i1++];
                op2 = ops2[i2++];
            } else{ op2 = op2 + op1.length; op1 = ops1[i1++]; }}else if (isInsert(op1) && isRetain(op2)) {
            if (op1.length > op2) {
                operation.insert(op1.slice(0, op2));
                op1 = op1.slice(op2);
                op2 = ops2[i2++];
            } else if (op1.length === op2) {
                operation.insert(op1);
                op1 = ops1[i1++];
                op2 = ops2[i2++];
            } else{ operation.insert(op1); op2 = op2 - op1.length; op1 = ops1[i1++]; }}else if (isRetain(op1) && isDelete(op2)) {
            if (op1 > -op2) {
                operation['delete'](op2);
                op1 = op1 + op2;
                op2 = ops2[i2++];
            } else if (op1 === -op2) {
                operation['delete'](op2);
                op1 = ops1[i1++];
                op2 = ops2[i2++];
            } else {
                operation['delete'](op1); op2 = op2 + op1; op1 = ops1[i1++]; }}else {
            throw new Error(
                "This shouldn't happen: op1: " +
                JSON.stringify(op1) + ", op2: " +
                JSON.stringify(op2) ); }}return operation;
};
Copy the code

Operation to string: apply, which applies operations to a string to get a new string.

// Returns a new string based on the original string and operation
TextOperation.prototype.apply = function (str) {
    var operation = this;
    if(str.length ! == operation.baseLength) {throw new Error("The operation's base length must be equal to the string's length.");
    }
    var newStr = [], j = 0;
    var strIndex = 0;
    var ops = this.ops;
    for (var i = 0, l = ops.length; i < l; i++) {
        var op = ops[i];
        if (isRetain(op)) {
            if (strIndex + op > str.length) {
                throw new Error("Operation can't retain more characters than are left in the string.");
            }
            // Copy the retained part of the old string
            newStr[j++] = str.slice(strIndex, strIndex + op);
            strIndex += op;
        } else if (isInsert(op)) {
            // Add the insert string
            newStr[j++] = op;
        } else { // Delete operationstrIndex -= op; }}if(strIndex ! == str.length) {throw new Error("The operation didn't operate on the whole string.");
    }
    return newStr.join(' ');
};
Copy the code

Difficult to understand the code with more detailed comments, you can clearly understand the code logic through reading comments.

The service side

Server stands for Server object:

// Store the current document in document and all operations in operations.
  function Server (document, operations) {
    this.document = document;
    this.operations = operations || [];
  }

  // Call this method whenever you receive an operation from a client.
  // Call this method when a client action is received.
  Server.prototype.receiveOperation = function (revision, operation) {
      
    if (revision < 0 || this.operations.length < revision) {
      throw new Error("operation revision not in history");
    }
    // Find all operations that the client didn't know of when it sent the
    // operation ...
    // Find all operations unknown to the current client by version number...
    var concurrentOperations = this.operations.slice(revision);

    // ... and transform the operation against all these operations ...
    / /... And enter transform for all unknown operations
    var transform = operation.constructor.transform;
    for (var i = 0; i < concurrentOperations.length; i++) {
      operation = transform(operation, concurrentOperations[i])[0];
    }

    // ... and apply that on the document.
    / /... And apply the action to the document.
    this.document = operation.apply(this.document);
    // Store operation in history.
    // Record user operations.
    this.operations.push(operation);

    // It's the caller's responsibility to send the operation to all connected
    // clients and an acknowledgement to the creator.
    // Returns the operation and broadcasts it to other users from where this method was called.
    return operation;
  };
Copy the code

The client

Client stands for Client object:

function Client (revision) {
    this.revision = revision; // Next expected version number
    this.state = synchronized_; // Current status
}
Copy the code

The client has three states: Synchronized, AwaitingConfirm and AwaitingWithBuffer:

// Synchronized status indicates that the client does not need to send operations to the server.
function Synchronized () {} Client.Synchronized = Synchronized; . Method to omit the Synchronize binding.// AwaitingConfirm indicates that an operation has been sent to the server.
function AwaitingConfirm (outstanding) {
    // Records operations that have been sent waiting to be returned
    this.outstanding = outstanding; } Client.AwaitingConfirm = AwaitingConfirm; . Omit the AwaitingConfirm binding method.The AwaitingWithBuffer state indicates that the client has sent an operation to the server, waiting for a response from the server, and that more operations are waiting to be sent locally
function AwaitingWithBuffer (outstanding, buffer) {
    // Records operations that have been sent waiting to be returned
    this.outstanding = outstanding;
    // Records unsent operations on the client
    this.buffer = buffer; } Client.AwaitingWithBuffer = AwaitingWithBuffer; . Omit the AwaitingWithBuffer binding method.Copy the code

The three states correspond to their respective operation methods. Synchronized:

 Synchronized.prototype.applyClient = function (client, operation) {
    // When the user edits the document, the action is sent to the server and the state is changed to AwaitingConfirm
    client.sendOperation(client.revision, operation);
    return new AwaitingConfirm(operation);
  };

  Synchronized.prototype.applyServer = function (client, operation) {
    // When a new action is received from the server, the action is applied to the current document.
    client.applyOperation(operation);
    return this;
  };
Copy the code

AwaitingConfirm:

AwaitingConfirm.prototype.applyClient = function (client, operation) {
    // When the user edits the document, the action is not immediately sent to the server, and the state is changed to AwaitingWithBuffer.
    return new AwaitingWithBuffer(this.outstanding, operation);
  };

  AwaitingConfirm.prototype.applyServer = function (client, operation) {
    // The server returns the operation and the local operation combined diamond graph:
    //
    / / / /
    // this.outstanding / \ operation
    / / / /
    / / / /
    // pair[1] \ / pair[0] (new outstanding)
    // (can be applied \/
    // to the client's
    // current document)
    // Pair [1] can be applied to the local client.
    var pair = operation.constructor.transform(this.outstanding, operation);
    client.applyOperation(pair[1]);
    return new AwaitingConfirm(pair[0]);
  };

  AwaitingConfirm.prototype.serverAck = function (client) {
    // The server confirms the client's actions and then switches to Synchronized.
    return synchronized_;
  };

  AwaitingConfirm.prototype.transformSelection = function (selection) {
    return selection.transform(this.outstanding);
  };

  AwaitingConfirm.prototype.resend = function (client) {
    // The confirm didn't come because the client was disconnected.
    // Now that it has reconnected, we resend the outstanding operation.
    // Continue sending operation after the client disconnects and reconnects.
    client.sendOperation(client.revision, this.outstanding);
  };
Copy the code

AwaitingWithBuffer:

AwaitingWithBuffer.prototype.applyClient = function (client, operation) {
    // Merge user operations.
    var newBuffer = this.buffer.compose(operation);
    return new AwaitingWithBuffer(this.outstanding, newBuffer);
  };

  AwaitingWithBuffer.prototype.applyServer = function (client, operation) {
    // Operation comes from another client
    //
    / / / /
    // this.outstanding / \ operation
    / / / /
    / / / / /
    // this.buffer / \* / pair1[0] (new outstanding)
    / / / / /
    / / / /
    // pair2[1] \ / pair2[0] (new buffer)
    // the transformed \/
    // operation -- can
    // be applied to the
    // client's current
    // document
    //
    // * pair1[1]
    var transform = operation.constructor.transform;
    var pair1 = transform(this.outstanding, operation);
    var pair2 = transform(this.buffer, pair1[1]);
    client.applyOperation(pair2[1]);
    return new AwaitingWithBuffer(pair1[0], pair2[0]);
  };

  AwaitingWithBuffer.prototype.serverAck = function (client) {
    // Operration has been confirmed by the server, sends a buffer operation, and switches the state to AwaitingConfirm.
    client.sendOperation(client.revision, this.buffer);
    return new AwaitingConfirm(this.buffer);
  };

  AwaitingWithBuffer.prototype.transformSelection = function (selection) {
    return selection.transform(this.outstanding).transform(this.buffer);
  };

  AwaitingWithBuffer.prototype.resend = function (client) {
    // The confirm didn't come because the client was disconnected.
    // Now that it has reconnected, we resend the outstanding operation.
    // Continue sending operation after the client disconnects and reconnects.
    client.sendOperation(client.revision, this.outstanding);
  };

Copy the code

After each state completes, the local version number is incremented by one.

Limited to space reasons, editor scheduling part and undo implementation will not be source analysis, interested students can directly read the source code. Source code contents are respectively in edit-client.js and undo-manager.js.

Depend on the warehouse implementation OT operation process step demonstration: the operational – transformation. Making. IO/index. HTML.

We can see the merging steps of the operations by modifying the contents of the input boxes below Alice and Bob and then clicking the arrow icon.

conclusion

Different systems have different OT algorithms. How to ensure the accuracy of the OT algorithm is a challenge that requires constant exploration. OT algorithm also has its own limitations, and can not guarantee that the result of the merger is completely in line with the user’s expectation.

There’s also a merging algorithm called CRDT, and I’ll talk about CRDT later.

If there is something you disagree with in the article, please point it out. I hope to communicate and learn with students who are interested in OT algorithm and CRDT.

A link to the

[1] en.wikipedia.org/wiki/Operat… [2] www3.ntu.edu.sg/scse/staff/… [3] github.com/share/share… [4] www.shangmayuan.com/a/eaa92ee4d… [5] github.com/Operational…

Invite attention to the public number: a row of weekly update technical articles, and we progress together.

OT algorithm