The core technical principles behind DingTalk document collaborative editing

Some people say that the most profound change that the Internet has brought to human society is that it has changed the way people collaborate with each other and greatly reduced the cost of information dissemination. Being in the Internet industry, studying the methods and means of information dissemination is our daily homework.
The way of information dissemination can be divided into two categories: synchronous and asynchronous according to the timing effect.

Synchronous transmission of information

Information is consumed as it is produced.

Words come out of my mouth and enter your ears. After this moment, it is very troublesome to restore the scene and feelings. Most of the time, it is not necessary. In synchronous scenarios, the production of information often does not require careful consideration, but through discussions and clarifications, the overall picture of the topic is gradually outlined. The timeliness of expression is more important than the richness of the method. Typical scenarios include instant messaging, voice calls, video conferences, etc. Simple and clear, without too many formats.

Asynchronous transmission of information

The production and consumption of information occur asynchronously.

Typical scenarios include forums, blogs, document libraries, and emails. When I write this document, you can't see it. When you read it, I have already finished writing it. In asynchronous scenarios, the producer of information will carefully consider the wording to ensure that his meaning is accurately conveyed. The richness of expression is very important. In addition to text, paragraph structure, lists, diagrams, and tables are all conducive to the accurate expression of information.

How documents express information

The traditional document information expression method is a typical asynchronous communication. The above-mentioned asynchronous scenarios can all be seen in the shadow of documents.
However, in March 2016, Google launched Google Docs, which overturned this conclusion. The world-changing feature is "multi-person real-time editing", or "co-editing". The introduction of co-edited online documents is like an online whiteboard, allowing people at both ends of the world to iterate on the same content together, and through the feedback of information back and forth, the synchronous dissemination of information is achieved. The results of the editing will be precipitated and become the carrier of asynchronous information dissemination.

With the ability to transmit information both synchronously and asynchronously, the birth of collaborative documents has undoubtedly brought a revolution to Internet-based communication and collaboration.
This revolution broke out in 2006, but its origins began 17 years ago.

In 1989, Microsoft Office, which represents "documents", was first introduced to the world on the Macintosh system, and the operation transformation algorithm, which represents "collaboration", was also first seen in a paper.
It is well known in Microsoft Office, but what is the Operation Transformation Algorithm?

Data consistency problem and operation transformation algorithm

The simplest understanding of collaborative editing is similar to group chat. Each person modifies the document on his or her own computer and sends the operation to other users who have opened the document. When the operation is received from other users, the operation is replayed. For example, the following example:

However, beautiful ideas are inevitably challenged by reality. Because of network latency, operations from different users may be executed in different orders on each end. The same operation, but in different execution orders, will produce different results. For example:

Data consistency is the minimum requirement for collaborative editing. Of course, we can force operations to be sorted by the time they arrive at the server, but this ordering will destroy the context of the user's editing at the time, resulting in editing results that do not meet the user's expectations.
This is where the operation transformation algorithm is introduced.

Operational transformation algorithm is not an algorithm, but a general term for a class of algorithms. They solve the same problem for different document data models:
Based on two operations in the same state, how to adjust the parameters of one operation so that it can be executed after the other operation and express the same user intention.
The above example adds operation transformation to solve the problem of data consistency, as shown in the following figure:

Of course, there is still a lot of depth in collaborative documents and operation transformation algorithms. This article is just a brief introduction to the basic principles. If you want to learn more, you can refer to the following literature:

Operational Transformation Frequently Asked Questions and Answers
Nanyang Technological University Professor Chengzheng Sun's survey covers most of the research results in the OT field

Google Wave Operational Transformation
G-Suite Collaboration Engine Protocol White Paper

Achieving convergence, causality-preservation, and intention-preservation in real-time cooperative editing systems
GOT algorithm and one-dimensional data operation transformation algorithm paper

Context-based Operational Transformation in Distributed Collaborative Editing Systems
COT Algorithm Paper

Conclusion

In March 2006, Google Docs was launched. Its real-time collaborative editing function amazed the world and shocked Microsoft Office, which was firmly in the top position of office suite. Office caught up, but Office 365 with the same function was launched five years later. What kind of strong fortress is collaborative editing that stopped Microsoft, which was so powerful, for five years? What core technologies are needed to make a collaborative editor? What inspiration can collaborative editing technology bring to ordinary front-end application development? In D2, we will share more technical principles and practices with you.