The birth of collaborative editing

I believe that we have used Office, so for example, after you make a Word, another person wants to modify what to do. The current practice is to save the file and then open it for modification, because once you open the file, it will only show read-only mode anywhere else. This model can be understood as: one person occupies a pit, you get in, others can’t get in…

There is no way in the world, but when many people walk, it becomes a way. Always save, open, save, open, still can only two people put there dolls, someone put forward can edit together, the answer is affirmative, the blogger found weboffice in baidu search, in the test, the effect can also. So what is the purpose of this paper? Of course, it is not to explain the whole set of Office collaborative editing, but to focus on the difficulties of collaborative editing and how to achieve it.

Difficulties in collaboration

The start to the difficulties of data changes, the data conflict, data update, but think, personally think that the data change doesn’t seem to be difficult, began to think of is that if there are three letters ABC, inserts a D in ABC AB letters, then became a ADBC, can consider to text wrapping, flip, but think carefully, It doesn’t matter how the data is saved for collaborative editing.

Then the difficulty comes to deal with data conflict in this way. For the same ABC, Xiaoming changed it to A Xiaoming BC when editing it, and Xiaoming changed it to A Xiaoming BC when editing it. Then what data will be saved to the database at last? This is where online editing comes into conflict.

Case analysis

Take the case of Xiao Ming and Xiao Hong as an example. Let’s see what happens when two children edit at the same time. We assume that xiao Ming students skills, ahead, hand speed faster, to submit to the data, then according to the theory, finally the right data should be A xiao Ming little red BC, because small red after editing, the local has been A little red BC, but after A while, the background tell little red client xiaoming also edit, leaving A trail of xiaoming is AB, So red does this, so it ends up being A, Ming and red BC.

In fact, in the real scene, xiao Ming, Xiao Hong, Xiao Li and Xiao Wang may be many children editing together, so how to solve these complicated logic?

The solution

  • First, violent rejection

When the uploaded data is edited by multiple users at the same time, the server accepts so much data in a certain period of time, and prompts the client: Currently, the data is being edited by multiple users. Please process it later and exit the editing state. , so that people will not directly use your products, ruthless persuasion.

  • B: Check In and Check Out

This mode is the so-called “one person one pit” mode, Xiao Ming and Xiao Hong are editing at the same time, Xiao Ming and Xiao Hong are editing and modifying at the time of editing and submitting, please deal with it later, the current state is read-only! “, so there is no help for the coordination of many people, still ruthless persuasion.

  • Three, OT algorithm

Operation Transformation, Operation Transformation, sounds like touch your head, think of your head buzzing. In short, it is to inform an action that is acceptable to many parties. Take Xiao Ming and Xiao Hong for example:

Xiao Ming:

Xiao Ming finished editing local is already A Xiao Ming BC, after A while, the background told Xiao Ming xiao Hong also edited, editing behavior is in the back of xiao Ming add little red, so the final xiao Ming local display results for A Xiao Ming Xiao Hong BC.

Little red:

After editing the local is already A little red BC, after A while, the background told the little red Xiao Ming also edited, editing behavior is to add xiao Ming in front of the little red, so the final local display of the little red result is A little red Xiao Ming BC.

All in all, it is to make the two schemes consistent in the background and then pass to the client.

So what happens in the background, how can it be processed into the same, let’s open the blind box, OT algorithm is currently the scheme adopted by Yozo Weboffice, so it is verified and worth studying. At first, the source code on Github looks very complicated, but after some big value points, it is still very complicated…… “, so the blogger simply explained.

First, we change the text content into the following three types of operations:

  • Retain (number): Retain the n characters
  • Insert (string): Inserts a character string
  • Delete (string): Deletes the string

Suppose Xiao Ming edited AB to become Xiao Ming B, and performed the following steps:

detele("A"); retain(1); Insert (" Ming ");Copy the code

These operations can be extracted by Levenshtein Distance algorithm. If red edits AB to become red A at the same time, the steps generated by red execution are as follows:

retain(1); detele("B"); Insert (" little red ");Copy the code

If we change the string to B, and then we change the string to B, and we find that we cannot detele(“B”) after holding the first character, we need to convert the string to fit the new string, for example:

detele("B"); Insert (" little red "); retain(1);Copy the code

OT algorithm is the core of also is actually transform algorithm, the idea is to edit into operation, if there is a bunch of kids at the same time of operation, need to convert a bunch of operations, specific how to switch can be set by several levels of logic to, such as data to submit to the server first, or you can submit to the server after the operation.

As if so said only a few hundred words, OT algorithm sounds very simple, in fact, is the small frog, I also used to be that foreign big guy said he worked for N years, no one summed up a best method. Because the above example is the interaction between Xiao Hong and Xiao Ming. What about Xiao Li and Lao Wang? What about the network delay during the editing process if each person edits several times? These are distributed OT algorithms, do you think these situations sound complicated…

Crash bible

Above said others set a lifetime of research OT algorithm may not be perfect, so if such a small chicken like the blogger how to quickly read to make a collaborative editor out of it, a word: bring it to you! , we don’t need to study algorithms too deeply, just like there are so many plug-ins on the market, do you want to personally implement each. For a simple demo of our own, the blogger recommends an open source library called Changesets, so we just need to play the role of the little red and little red, throw the conversion operation to it, and get the final result.

Rome wasn’t built in a day, collaborative editing has many details and small difficulties, such as the information between clients to receive editing operations, whether to use a long connection or websocket, how to predict the future, please listen to the next decomposition………