Reading time: 10 minutes

One of the difficulties in real-time collaborative editing of online documents mainly lies in collaborative conflict handling. OT algorithm is the main scheme to solve cooperative conflict processing

I. Conflict management

Conflict resolution

1. Edit lock

When someone is editing a document, the system locks the document to prevent others from editing it at the same time. The implementation of edit locks is simple and crude, but directly affects the user experience.

2.diff-patch

Based on the idea of Git and other similar version management, the content is compared and merged, including GNU Diff-patch, Myer’s diff-Patch and other schemes. Diff-patch can merge conflicts by itself or hand over to users when conflicts occur.

3. Final consistency is achieved

These include Operational Transformation (OT), conflict-free Replicated Data Type (CRDT). The OT algorithm is the solution used in Graphite documents, Newsletter documents, Flybook documents, Google Docs, and CRDT for Atom.

OT and CRDT

The OT and CRDT approaches are similar in that they provide ultimate consistency. The difference is how they operate:

  • OT does this by changing operations
  • OT will split and convert editing operations to achieve the effect of conflict handling
  • OT does not include specific implementation, so it needs to be implemented by the project itself, but it can carry out high-precision conflict handling according to the needs of the project
  • CRDT does this by changing state
  • Basically, CRDT is a data structure that, when updated with the same set of operations, will always converge to the same representation, even if the operations are applied in a different order
  • CRDT comes in two ways: operation-based and state-based

OT is primarily used for text, which is often complex and not extensible. The CRDT implementation is simple, but there is a reason why Google, Microsoft, Tencent Documents, Graphite documents, and many others rely on OT. The current state of CRDT research supports collaboration on two main types of data: plain text, arbitrary JSON structures.

For more advanced structures, such as rich text editing, OT trades complexity for user expectations, while CRDT focuses more on data structures. As data structure complexity increases, the time and space complexity of the algorithm increases exponentially, resulting in performance challenges. Therefore, most real-time collaborative editing is now implemented based on OT algorithm.

Take a chestnut

Let’s say user A sees some initial text that says “ABC”, and then he wants to insert “D” => “ABcd” after the third position, and then he wants to insert “e” => “ABCE”

If we do not do lock processing or throw processing, we will keep the maximum content (A, B), should be “abcde”.

If the operation is separate and there is no OT algorithm processing, then A will see “abced” (A after the third position, and THEN B wants to insert “e” after the third position => “abce”), for user B, he actually gets A sequential execution, If B wants to insert “e” after the third position => “abce “, then A wants to insert “d” after the third position, the result is “abcde”, B’s result is exactly the same, in which case B is right, A is wrong, So what A ends up seeing is not the original B operation, but the transformed B’ operation. He should get “B wants to insert E after position 4 “. Therefore, we introduce an OT algorithm.

Follow (A,B) = B A' = B x follow(B, B) = B A' = B x follow(B,A)Copy the code

The first argument to the Follow function represents the first action, and the second argument represents the subsequent action

Merge represents the largest available collection after a Merge

Second, about the server design

A series of historical revisions are maintained in the server, such as R1, R2, R3… R100,… r110

NewC = follow(R101,C),newC = follow(R102,newC), Finally, you get the newC changes for the R110 version and push them to each client

The core implementation of ot.js

// Call this method whenever you receive an operation from a client. 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 ... [0,1,2,3,4,5]// 1,operstion => [2,3,4,5]var concurrentOperations = this.operations. / /... and transform the operation against all these operations ... var transform = operation.constructor.transform; for (var i = 0; i < concurrentOperations.length; I ++) {// operation, [2,3,4,5][index] operation = transform(operation, concurrentOperations[I])[0]; / / the realization of the transform of https://github.com/Operational-Transformation/ot.js/blob/master/lib/text-operation.js} / /... and apply that on the document.this.document = operation.apply(this.document); // Store operation in history.this.operations.push(operation); // It's the caller's responsibility to send the operation to all connected// clients and an acknowledgement to the creator.return operation; };Copy the code

Three, OT algorithm visualization

The operational – the transformation. The dead simple. IO/visualizati…

More references:

EasySync Synergy Technical Guide

operational-transformation.github.io