preface

What technology does it take for the front end to develop an online document? Consider the problems we might have to solve to develop an online document:

  • Basic text editing (oh? Textarea seems to work, but what about rich text? We need a document model to describe the document;
  • Rich text editor, providing rich text editing and rendering capabilities;
  • Collaborative features, different users of the same document editing needs to keep everyone see the same;
  • Collaborative network model to ensure the consistency of document model between server and client;

Noun explanation

OT: an algorithm for solving collaborative problems;

OP: short for operation. In OT, an operation.

Etherpad: An open source library for document collaboration;

Easysync: The core algorithm for document collaboration in EtherPad, which is a kind of OT algorithm, mainly used to deal with text collaboration;

Ot-json: A type of OT algorithm. As the name implies, it is mainly used to process structured data.

Changeset: A data format that describes changes to a document, used to represent a change to the entire document;

ClientVars: Represents initialization data for a document, typically composed of consecutive Changesets;

Symbol explanation

| : move the cursor;

· : Superposition;

The body of the

OT algorithm

What is the OT algorithm? Let’s start at the beginning. What’s the simplest and most violent thing we can do if we want to implement a multi-person document editing feature?

Edit lock

As the name implies, if user A edits A document, the server locks the document directly. If user B edits A document at this time, the server will discard the document because of the lock. As you can see, this way of the realization of the edit lock is very rough, the experience is extremely bad, of course, in many companies, such as one of our rival companies) some wiki system is in this way, because this implementation is simple, and experience terrible loss (content & unable to real-time), we don’t do is discussed here.

In Linux diff – patch

Linux has two commands: diff and patch; If we can implement this algorithm in JS, then we can do something like this:

  1. After opening the document, the user establishes a long link with the server to save the copy of the document.
  1. If there is a pause during user editing (such as 3S), the existing document is diff compared with the copy, and the result is sent to the server to update the copy.
  1. The server updates the document, notifies other users of the diff result through a long link, and other users update the local document using the patch method.

Let’s test it out:

$echo 'Avengers: Iron Man, Hulk' > test-usera.txt # diff $diff $diff $echo 'Avengers: Iron Man, Hulk' > test-usera.txt # diff $diff Patch $cat diff-test.patch $cat diff-test.patch 3c3 < Captain America -- > The Incredible ManCopy the code

From the diff-test.patch content, we can see that the differences between the two documents have been found, and then we can simulate the behavior of user B:

$echo 'Captain America' > test-userb. TXT # patch $patch test-userb. TXT < ff test.patch # $cat test-userb. TXT $cat test-userb. TXTCopy the code

As you can see, the third line of user B’s document has been updated to user A’s modified “Hulk.”

  1. The problem with this implementation is that it is based on rows, which can lead to conflicts, such as:
$diff $diff local.txt $diff $diff local.txt $diff $diff local.txt $diff $diff local.txt $diff diff.patchCopy the code

Diff. Patch:

Avengers -- Iron ManCopy the code

This means that if two people modify the same line at the same time, there must be a conflict. Let’s test:

$echo 'Avengers captain America' > userb.txt # patch $patch userb.txt < diff.patchCopy the code

Above, we found that if the original document is “the avengers alliance”, the user is amended as “iron man” avengers alliance, A diff result to the server, the server to the user B, and user B just change the document in order to “captain America” avengers alliance, intuitively we can see that the two are not conflict, It could have merged into the Avengers, Iron Man and Captain America, but the actual patch turned out like this:

$cat userB. TXT. Rej * * * * * * * * * * * * * * * * * * 1 - the avengers alliance -- -- -- -- -- -- -- -- 1 + the avengers alliance iron manCopy the code

Therefore, this kind of line-based algorithm is still relatively rough, although it is better than editing lock, but the actual disadvantages are still relatively large, since the line-based implementation cannot meet the requirements, is it possible to diff character based?

The diff – patch algorithm

Diff-match-patch is another implementation of diff-patch algorithm, it is based on characters to diff, here does not introduce the details of the algorithm, its algorithm in this: DIFF-match-patch JS implementation source code. Let’s test it directly

// example 1 const localText = 'Avengers '; Const userAText = 'Avengers Iron Man '; Const userBText = 'Avengers Captain America '; // Result: Avengers, Iron Man, Captain America // example 2 const localText = 'Avengers '; Const userAText = 'Avengers Captain America '; Const userBText = 'Avengers Iron Man '; // Result: Avengers, Iron Man, Captain America // example 3 const localText = 'Avengers '; Const userAText = 'Avengers Captain America '; Const userBText = 'Avengers Iron Man '; // The result is: Avengers captain America Iron ManCopy the code

The above example has solved the problem of Linux’s diff-patch based diff, but there are still problems. Examples 1 and 2 above have the same results without sign splitting.

Const localText = 'Avenger Iron Man'; Const userAText = 'Iron Man '; Const userBText = 'Avenger Caption'; // SelectCopy the code

User A changed the Caption to “Iron Man Iron Man” and user B changed the Caption to “Avengers Iron Man.” If the Caption is followed by a space, then Iron Man is missing, then diff-match-patch will lose characters. This is a fatal problem in rich text documents. If you lose a >, the whole document will fall apart. Is there a solution that solves both the row matching conflict and the character loss problem? The answer is the focus of this article — the OT algorithm

operation transformation

The sample

Ot.js is a javascript implementation for plain text. Let’s take a look at its implementation. For the same example:

Const STR = 'Avenger Iron Man'; Const operation0 = new ot.textOperation ().delete(' Nemesis ').retain(8).insert(' Iron Man '); const operation1 = new ot.TextOperation().retain(4).delete('Iron Man').insert('Captain'); const op = ot.TextOperation.transform(operation0, operation1); // Result: Captain Iron ManCopy the code

You can see that this is exactly what we expected.

The principle of

I have read a lot of documents about OT, and almost every one of them is very long and cloudy, but in fact its core principle is very simple. In OT, we divide the operations on the document into three types, and edit the entire document by combining these three atomic operations:

  • Insert (insert character);
  • Delete (delete character)
  • Retain (retain n characters, i.e. move the cursor);

Note: In fact, the diff-match-patch algorithm also divides operations into three categories: Insert, delete, equal(invariant characters), insert, delete, and OT have similar meanings. Equal refers to those characters that did not change during diff. The corresponding logical processing will be performed according to different types of characters during patch later.

insert

|

The avengers alliance |

As above | represent the location of the cursor, from top to bottom and simulate the behavior of the user operations, the above operation ot. Js to describe:

const str = ''; Const operation = new ot.textOperation ().insert(' Avengers '); const result = operation.apply(str); console.log(result); // The AvengersCopy the code

At the end of an op, the cursor must be at the end of the string. Insert moves the cursor automatically, so we don’t need to move the cursor manually.

retain

| the avengers alliance

The avengers alliance |

Iron man | the avengers alliance

The above process is described by using ot.js:

Const STR = 'Avengers '; Const operation = new ot.textOperation ().retain(5).insert(' Iron Man '); const result = operation.apply(str); console.log(result); // Avengers Iron ManCopy the code
delete

Iron man | the avengers alliance

The avengers alliance | iron man

The avengers alliance |

The above process is described with ot.js:

Const STR = 'Avengers Iron Man '; Const operation = new ot.textOperation ().retain(5).delete(' Iron Man '); const result = operation.apply(str); console.log(result); // The AvengersCopy the code

Delete (‘123’); delete(‘123’); delete(‘123’);

transform

Transform is the core method in OT. Js that implements the problem of missing characters in diff-match-patch. Instead of listing his source code, let’s take a look at a few examples:

Example 1

The original document content (blank document) : |

The content of the document edited by user A is Iron Man

Content of the document edited by user B: Thor

Corresponding code implementation:

const str = ' '; Const operation0 = new ot.textOperation ().insert(' Iron Man '); Const operation1 = new ot.textOperation ().insert(' thor '); const op = ot.TextOperation.transform(operation0, operation1); The console. The log (' op operation: after the transform, the op [0]. The toString (), '|', op [1]. The toString ()); / / after the transform op operation: insert 'iron man', retain 2 | retain 3, insert 'thor' console. The log (' operation after the transform of string: ', op[0].apply(operation1.apply(str)), ' | ', op[1].apply(operation0.apply(str))); / / the transform operation after string: iron man thor | iron man thorCopy the code

The end result was iron Man and Thor;

Operation process of transform:

cycles op1 op2 operation1prime operation2prime
1 3 2 Insert (‘ Iron Man ‘) retain(3)
2 undefined 2 retain(2) Insert (‘ thor ‘)

Example 2

Original documentation: The Avengers

User A: Avengers iron Man Alliance

User B: Captain America from the Avengers

Corresponding code implementation:

Const STR = 'Avengers '; Const operation0 = new ot.textOperation ().retain(3).insert(' Iron Man ').retain(2); Const operation1 = new ot.textOperation ().retain(5).insert(' Captain America '); const op = ot.TextOperation.transform(operation0, operation1); The console. The log (' op operation: after the transform, the op [0]. The toString (), '|', op [1]. The toString ()); / / op operation: after the transform retain 3, insert 'iron man', retain 6 | retain 8, insert 'captain America' console. The log (' operation after the transform of string: ', op[0].apply(operation1.apply(str)), ' | ', op[1].apply(operation0.apply(str))); / / operation after the transform string: avenger iron man union captain America captain America | iron man avengers allianceCopy the code

The result was “Captain America, Avengers, Iron Man alliance”;

Operation process of transform:

cycles op1 op2 operation1prime operation2prime
1 3 5 retain(3) retain(3)
2 ‘Iron Man’ 2 Insert (‘ Iron Man ‘) retain(3)
3 2 2 retain(2) retain(2)
4 undefined Captain America retain(4) Insert (‘ Captain America ‘)

Example 3

Original documentation: Avengers, Iron Man, Captain America

User A: Avengers Iron Man

User B: Captain America from the Avengers

Corresponding code implementation:

Const STR = 'Avengers, Iron Man, Captain America '; Const operation0 = new ot.textOperation ().retain(5).delete(' Iron Man ').retain(4); Const operation1 = new ot.textOperation ().retain(8).delete(' Captain America '); const op = ot.TextOperation.transform(operation0, operation1); The console. The log (' op operation: after the transform, the op [0]. The toString (), '|', op [1]. The toString ()); / / op operation: after the transform retain 5, delete 3 | retain 5, delete 4 console. The log (' operation after the transform of string: ', op[0].apply(operation1.apply(str)), ' | ', op[1].apply(operation0.apply(str))); / / the transform operation after string: the avengers alliance | the avengers allianceCopy the code

The result was “The Avengers”;

Operation process:

cycles op1 op2 operation1prime operation2prime
1 5 8 retain(5) retain(5)
2 – 3 3 delete(3) –
3 4 4 – – delete(4)

The result was “The Avengers”;

Example 4

Original documentation: Avengers, Iron Man, Captain America ‘

User A: Avengers

User B: Captain America from the Avengers

Corresponding code implementation:

Const STR = 'Avengers, Iron Man, Captain America '; Const operation0 = new ot.textOperation ().retain(5).delete(' Iron Man captain America '); Const operation1 = new ot.textOperation ().retain(5).delete(' Iron Man ').retain(4); const op = ot.TextOperation.transform(operation0, operation1); The console. The log (' op operation: after the transform, the op [0]. The toString (), '|', op [1]. The toString ()); / / op operation: after the transform retain 5, 4 | delete retain 5 console. The log (' operation after the transform of string: ', op[0].apply(operation1.apply(str)), ' | ', op[1].apply(operation0.apply(str))); / / the transform operation after string: the avengers alliance | the avengers allianceCopy the code

The result was “The Avengers”;

Operation process:

cycles op1 op2 operation1prime operation2prime
1 5 5 retain(5) retain(5)
2 7 – – 3 – –
3 4 – 4 delete(4) –

Ot.js transform source code:

TextOperation.transform = function (operation1, operation2) { // ... 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) { //... If (isInsert(op1)) {operation1prim.insert (op1); operation1Prim.insert (op1); operation2prime.retain(op1.length); op1 = ops1[i1++]; continue; } // Operation logic for the second loop of example 1 if (isInsert(op2)) {operation1prime.retain(op2.length); operation2prime.insert(op2); op2 = ops2[i2++]; continue; } / /... var minl; If (isRetain(op1) && isRetain(op2)) {if (op1 > op2) {minl = op2; op1 = op1 - op2; op2 = ops2[i2++]; } else if (op1 === op2) {minl = op2; op1 = ops1[i1++]; op2 = ops2[i2++]; // First loop logic for example 2} else {minl = op1; op2 = op2 - op1; op1 = ops1[i1++]; } operation1prime.retain(minl); operation2prime.retain(minl); Else if (isDelete(op1) &&isdelete (op2)) {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 (-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 "'delete'"); Else if (isRetain(op1) &&isdelete (op2)) {if (op1 > -op2) {minl = -op2;} else if (isRetain(op1) &&isdelete (op2)) {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 "'delete'"); } else { throw new Error( The two operations aren't compatible ); } } return [operation1prime, operation2prime]; };Copy the code

The four examples above cover all branches of transform. The core principle is actually very simple. It is to rearrange and combine the two operations through a loop and make different logical processing according to the operation type. This is the core method in OT, in addition to compose, apply and other methods, which are not listed here.

The transform process is often represented by a diamond:

transform(a, b) = (a’, b’);

compose

As the name implies, this method is used to merge two OP operations, such as:

Const STR = 'Avengers '; Const operation0 = new ot.textOperation ().retain(5).insert(' Iron Man '); Const operation1 = new ot.textOperation ().retain(8).insert(' black widow '); const op = operation0.compose(operation1); Console. log('compose after op: ', op.tostring ()); Console. log(' result: ', op.apply(STR)); // Avengers Iron Man Black WidowCopy the code

Compose’s implementation is similar to transform’s, listing all the combination possibilities of the two OP’s and making corresponding logical processing respectively. The source code can be viewed at Github. Of course, ot.js has a lot more than these two apis. For example, the undo/redo method on the client is used to undo/redo documents

Sequential control

Based on the above examples and code believe that everybody should be the core principles of OT clearer, but OT algorithm to transform based on the order, if A user operating the document twice, but because the network reasons, the second time before the first time arrived at the server, the server to distribute to other users based on the received order so inevitable problems. The flow chart is as follows:

Therefore, we need to carry out a version control for each operation, and add a version identifier to each submission, similar to Git commitID. Each submission version increases by 1 to identify each OP operation. The client side and the server side maintain a version;

Client: local version +1 after the outgoing request is returned for confirmation;

Server: version +1 upon completion of an OP;

Therefore, the version of the client must be less than or equal to that of the server.

The correlation transformation process is shown in figure, which is not detailed here, but is actually an extension of the diamond shape above. Interested can go to the operational – the transformation. The dead simple. IO/index HTML this…

State control

OT will operate in three states:

  • Synchronized: does not submit an OP and waits for a new OP
  • AwaitingConfirm: a new OP has been submitted, waiting for background confirmation, during which no new editing action is generated;

At this stage, a transform will be performed after receiving the new OP in the background

Transform (OP1, OP) = (OP1′, OP’); Where OP’ is applied locally

  • OP1 is the local submitted but not confirmed OP;
  • AwaitingWithBuffer: there is a new OP submitted, waiting for background confirmation, during which time there is a new edit action product new OP;

The new OP generated in this phase will compose with the last local OP and merge into a new OP

In this phase, when the new OP is received in the background, two transform and one compose will be performed:

OP3 = OP1.compose(OP2);

transform(OP1, OP) = (OP1', OP');

transform(OP3 , OP') = (OP3', OP'');

Finally OP “” will be applied locally and then update OP1 = OP1 and OP3 = OP3′

  • OP: the new OP pushed by the server;
  • OP1: unconfirmed OP after local submission;
  • OP2: New edit operations generated at this stage;
  • OP3: OP1 and OP2 compose compose

OT algorithm is very suitable for dealing with text collaboration. It was first proposed in 1989 and has been implemented in various languages, which is relatively mature. At present, OT algorithm is used in Google Docs, Tencent documents and our company’s Feishu documents. With the development of Web communication protocols (such as WebRTC), point-to-point communication has become an alternative to C/S architecture. CRDT algorithm is also a collaborative algorithm, which was proposed in 2006 and is currently used in Atom, Figma and other products. CRDT supports THE C/S architecture model and also supports point-to-point transmission, but at present, various documents are mainly using OT. The following video explains that CRDT will be much more complex than OT with the increase of text content. The specific reasons are still unknown, and interested students can study together.

youtu.be/PWzrbg9qqK8

CRDT related papers: www.researchgate.net/publication…

CRDT tech/ Resources

CRDT open source implementation: github.com/yjs/yjs

Easysync

The OT algorithm in the collaborative processing algorithm is introduced above. Our examples are all plain text, but in fact online documents can not be so simple, such as a variety of blocks, rich text support, comments, selection and so on. If you simply use ot.js to do it, you are digging a hole. Easysync is also an implementation of the OT algorithm, which is used in EtherPad.

About the Etherpad

Easysync this algorithm is the author applies for a patent, patent address: www.freepatentsonline.com/y2012/01104… “Etherpad-lite “), there is no need to maintain jar packages. Etherpad is simply a Rich text editor (demo address) from Google (Apache protocol), and the collaborative algorithm uses easySync, one of the OT algorithms.

Description Document (clientVars)

A data structure is used in EasySync to describe the entire document.

The description of the document in the screenshot above:

{attribs: * 5 | 0 + 1 + 1 * 1 * 2 * 3 * 4 * 5 + 1 * 6 + 3 * 2 | 1 + 1, text: the avengers alliance iron man \ n \ n *}Copy the code

The above object describes the content and format of the entire document, text stores the content of the entire document including newline characters and other symbols, attribs stores the description of the content and format of the document, the attribute in the figure above is not the multiplication and addition in our impression, the number in this object only represents the serial number. Translate the meaning of specific symbols:

  • *n: NTH attribute;
  • | n: n lines;
  • +n: N characters are retrieved.

Note: Most of the numbers in easySync are in base 36, the main purpose is to shorten the length of transmission characters;

The specific attributes (bold, italic, etc.) are described in another attribute, apool. The corresponding attributes in the above document are described as follows:

{ apool :{ numToAttrib :{ 0 :[ lineguid , HwV9Nr ], 1 :[ align , left ], 2 :[ author , 52000000000000025 ], 3 :[ fragmentguid , 1981193224752831644 ], 4 :[ insertorder , first ], 5 :[ lmkr , 1 ], 6 :[ lineguid , sQgJ38 ], 7: [store, {\ contentConfig \ : {\ \ 0: [1, 2, 3], and \ \ 1: [1, 2, 3], and \ \ 2: [1, 2, 3, 4, 5], and \ \ 3:].enlighened by \ \ 4: []}}]}. nextNum :8 } }Copy the code

The numToAttrib property above stores the ordinal number as shown above. Combined with apool attribute values, we can put inside * 5 | 0 + 1 + 1 * 1 * 2 * 3 * 4 * 5 + 1 * 6 + 3 * 2 | 1 + 1 * * * * let out of the translation:

  • Attribute 0, applied to the first 5 characters (Avengers), affect a row;
  • Take a character and apply attributes 1, 2, 3, 4, 5 (attribute 2 is author, i.e. the user currently editing this part of the text);
  • Take 1 character and apply attribute 6;
  • Extract 3 characters (Iron man) applies attribute 2 to affect a row;
  • Extract 1 character (newline);

It can be seen that this is actually a data structure to describe the document. Theoretically, as long as we implement the renderer of the corresponding platform, we can not only render it into HTML, but also apply it in Native. However, this format is described in terms of text lines and columns, which is difficult to do in the case of a table such as the need for a row of compartments.

Describe document changes (Changeset)

Easysync above defines a set of data structures to describe the entire document content, but how to handle changes in a collaborative scenario can also be a tricky problem. A concept called Changeset is defined in EasySync to describe changes to a document. Documents generate an initial content structure when they are created or imported, and all changes thereafter are represented in Changeset. Making a change to the document produces a Changeset:

Z: > 3 c | 0 + 1 = 7 = 4 * 3 $black widowCopy the code

If the communication protocol is used to understand Changeset, it can be divided into packet header and packet body. The packet header is mainly used to describe the character length, and the above Z seems to be a Magicnumber. Every Changeset will start with Z. Packages are used to describe specific operations (such as adding characters, deleting characters, etc.). The characters after the $are called charbank, and all new characters in this change are extracted from charbank. Symbols represent the following meanings in Changeset:

  • Z: Magicnumber.
  • :n: the length of the previous document (easysNC usually uses base 36 to represent numbers);
  • >n: new bytes;
  • | n: influence n lines;
  • *n: application attribute n.
  • +n: N characters are retrieved.
  • -n: Deletes three characters from the current position.
  • =n: bytes remain unchanged;

The above changeset translation reads as follows:

The previous text length was C (12 in decimal), affecting line 1, reserving 7 characters, reserving 4 characters, and inserting 3 characters to apply the attribute 0.

The +, -, and = operations correspond to the insert,delete, and retain operations in Ot.js.

Let’s look at another example of deleting a character (with black widow removed) :

Z:f<3|1=7=4-3$
Copy the code

The previous text length was F (15 in decimal), affecting the first line, reserving 7 characters, reserving 4 characters, and removing 3 characters from this position;

In the deleted Changeset, charbank is empty, because it is deleted, there is no new character; Official documentation: github.com/ether/ether…

synergy

In the actual operation, Changeset will be very many and frequent. For example, I am crazy about code words now. Therefore, it is very important to compose Changeset, which can greatly shorten the length of transmission characters. The transform method in ot.js we mentioned above is called follow in easySync. If we go back to ot.js, we’ll see

  • An OP in ot.js => Changeset in easySync;
  • Tranform in ot.js => Follow in easySync;
compose

User B’s local operation: Insert the character captain America, which corresponds to Changeset:

Z: c > 4 | 0 + 1 = 7 = 4 * 4 $captain AmericaCopy the code

User B next operations: insert character “Thor”, corresponding to changeset:

Z: 2 g > | 0 + 1 = 7 = 8 * 2 $for RaytheonCopy the code

The two operations can be merged into a single changeset, assuming they are very short apart:

Const cs1 = 'Z: c > 4 | 0 + 1 = 7 = 4 * 4 $captain America'; Const cs2 = 'Z: 2 g > | 0 + 1 = 7 = 8 * 2 $thor'; console.log(Changeset.compose(cs1, cs2, false, null)); / / Z: c > 6 | 0 + 1 = 7 = 4 * 6 $captain America thorCopy the code

Note that compose has a merge order, and parameter 1 must precede parameter 2. We omit the compose method below. State A and state B are merged into state C (state A precedes state B), denoted as C = AB;

merge

For example, user A and user B edit A document at the same time. For example, user A and user B edit A document at the same time:

User A inserts black Widow:

Z: > 3 c | 0 + 1 = 7 = 4 * 3 $black widowCopy the code

User B inserts Captain America:

Z: c > 4 | 0 + 1 = 7 = 4 * 4 $captain AmericaCopy the code

Merge operations A and B. The merged state is called C, that is, C = m(A, B);

Constraints on m: the order of A and B can be arbitrary, that is, m(A, B) = m(B, A);

follow

The above example generates state C = m(B, A), which is actually applied to the server, assuming that the server state X => X’. So X prime is equal to Xm of B, A. X’ is obtained by the combination of X and m(B, A), but it is impossible for the client to directly operate in this way, because for user A, state C is not the front of A, so it cannot be directly merged. We need an algorithm to do the conversion, and this implementation is the follow method, as shown in the above example:

Const A = 'Z: b > 3 | 0 + 1 = 4 * 3 $black widow'; Const B = 'Z: B > 4 | 0 + 1 = 4 * 4 $captain America'; const A1 = follow(B, A, false, null); const B1 = follow(A, B, true, null); console.log(A1, B1); / / Z: f > 3 | 1 = = 4 * 4 0 + 3 $black widow Z: e > 4 | 0 + 1 = 4 * 4 $captain America const A2 = compose (A, B1); const B2 = compose(B, A1); console.log(A2, B2); / / Z: b > 7 | 0 + 1 = 4 * 7 $captain America black widow Z: b > 7 | 0 + 1 = 4 * 7 $captain America black widowCopy the code

You can see that the final changeset of users A and B is A2 and B2 respectively, A2 and B2 are exactly the same. Here, we will follow the method to f, when the server receives the user A and user B concurrent operation of the process, assuming that current status of the service side is X, and received the operation of the user A A, then apply to the string into the XA, at this time received the operation of the user B B again, obviously, this can’t be directly applied XAB, Because both A and B are based on X, A is not A precursor of B, so we need AB’ to implement XAB’, with XAB’ = XBA’. B’ = f(A, B), A’ = f(B, A) XAf(A, B) = XBf(B, A). That is, Af(A, B) = B f(B, A); This formula is the core of the Follow algorithm.

C/S model

As mentioned earlier, the OT algorithm necessarily requires a Server to transfer, and does not support point-to-point. Let’s take a look at how the client and server work separately:

The client

As mentioned earlier, in OT, the client can divide the user’s operation into three states. In EasySync, there are also three states:

A: The latest content of the server has not been modified;

X: Changeset has been submitted and has not been confirmed yet;

Y: the change set generated by the client that has not been committed to the server;

There is also a special changeset, which is that during X, a new Changeset is created, and we use E instead.

E: **** New edits generated during changeset submission;

Etherpad’s official documentation is extremely complex, so I’ll briefly review the client state changes and operations here (note: the = and ≠ in the following are both traditional mathematical symbols, which are merged directly using compose/merge) :

  1. Pull the latest document, not edited

So X = Y = A = In

  1. Start generating edit behavior

When the user generates a new edit E, Y has two states, one is the initial state Y = In, the other is the previous edit, Y ≠ In. But whether Y is equal to In or not, operation E is merged into Y, where Y = Y · E; In this way, Y can be continuously updated, so as not to lose user data;

  1. Commit changeset to server (no ACK received)

At this point, change set Y becomes committed and the state of Y is reset, X = Y, Y = In;

  1. Received server ACK confirmation;

At this point, X becomes the confirmed state, A state changes to the latest X, and X state is reset, i.e., A = X; X = In;

  1. Received change set B from user B;
  • Prerequisites:The constraint on B is that A must precede B, i.e. the operation A · B is operable (You can think about why we have this constraint.)At this time, the changes are complicated, and the previous AXY change rules can no longer adapt to this scenario, so adjustments need to be made. User A needs to assimilate B to generate, A’, X’, Y’ to revert to the previous transition behavior. Since the AXY is the state already presented to the user, we use V to represent the final document change state.
    • A absorbs B into A’:A' = AB;
    • X absorbs B and becomes X’: B and X have the same front A, which can be merged using the follow method.X' = f(B, X).B' = f(X, B); Can be inferredABX’ = AXB ‘
    • Y absorbs B into Y’ :

    • B’ = f(X, B), Y’ = f(B’, Y), Y’ = f(B’, Y); That is, Y’ = f(f(X, B), Y);

    • Generate final state V:

    • V = A’X’Y’

      = AB times f(B, X) times f(f(X, B), Y)

      = A times Bf(B, X) times f(f(X, B), Y)

      = A times Xf(X, B) times f(f(X, B), Y)

      = AX times f of X, B times f of f of X, B, Y.

      Is equal to AX dot Y dot f of Y, f of X,B.

      = AXY times f of Y, f of X, B.

Now I’m going to assign the new A’, X’, and Y’ to AXY

The service side

Here, the processing logic of the server side is much simpler than that of the front-end, mainly doing two things:

  1. Respond to client requests, establish links, and return the latest status of the document;
  1. Process the change set submitted by the client and return the confirmation message.

The logic for handling change sets is worth mentioning. When a server receives a change set C, it does five things:

  1. Obtained from the client version recordCA pre-release ofSc(Initial version of the client);
  1. Note the last Changeset recorded by the serverSh 与 ScThere may also be multiple Changeset records (at this point there may be other users who have pushed a new version but have not yet delivered it to the current client). And then you have to figure outCThe relativeShThe rear ofC'. In order to”The superposition“To the current document;
  1. sendC'To other clients;
  1. Send an ACK to the current client;
  1. willC'Add to record list while updating version;

Afterword.

I have a superficial understanding of the above technologies related to online documents, some of which are full of challenges in the implementation of some details and problems. This direction is indeed obstructed and long. Behind many seemingly simple functions are full of efforts of engineers (such as text selection in collaboration).

The above.

Reference documentation

  • OT Synergy
  • Overview of Etherpad Collaboration
  • zhuanlan.zhihu.com/p/37635124
  • Github.com/google/diff…
  • www.zhihu.com/question/27…
  • www.manongjc.com/detail/24-r…
  • www.icode9.com/content-1-1…
  • Github.com/Operational…
  • Github.com/ether/ether…
  • Github.com/google/diff…
  • Objcer.com/2018/03/05/…
  • Juejin. Cn/post / 706423…
  • www.manongjc.com/detail/24-r…
  • www.icode9.com/content-1-1…
  • Github.com/Operational…
  • Github.com/ether/ether…
  • Github.com/google/diff…
  • Objcer.com/2018/03/05/…
  • Juejin. Cn/post / 706423…