How to deal with the conflict of multi-user operation when multiple people edit an online document at the same time has always been a hot topic of discussion. The two most commonly used ideas to resolve collaboration conflicts in the industry are document merger algorithm based on Operation Transformation (OT) and document merger algorithm based on CRDT. The OT algorithm has been introduced in detail before and will not be discussed in this article. In this paper, we mainly introduce a document merging algorithm based on CRDT -YATA. It has its own open source implementation, Yjs

Near real-time peer-to-peer Shared Editing on Extensible Data Types.

Introduction to the

Over the last three decades, the CSCW community has conducted in-depth research on “near real time” collaboration technologies. Among them, the research results of OT algorithm in the field of online editing have been widely used, such as in Google Docs. This type of document merging algorithm has the great advantage of not relying on locking, but by merging multiple conflicting operations to ensure consistency of document content. In this way, the operation efficiency of the system can be improved and more people can cooperate in real time on the premise of retaining the user’s operation intention. However, there are some disadvantages: each document must rely on a server instance for merge collision calculation, which increases server-side stress and requires redundant copies and retries for high availability.

With the development of Web communication protocol, WebRTC, Websockets, XMPP over Websockets, server-sent Events and other communication technologies have also been adopted by industry and academia. Peer-to-peer transport becomes an alternative to the client-server approach in multi-party collaboration scenarios, but most of the OT algorithms available in the industry are designed for client-server architectures. CRDT algorithm supports both client-server architecture and point-to-point transport protocol.

In order to reduce the cost for users to use collaboration frameworks, especially to provide programs that can run directly in the browser, the authors of the paper propose “YATA” (collaboration algorithm based on CRDT ideas) and provide an open source implementation of Yjs.

YATA method

YATA was created to provide an extensible solution for P2P concurrency control on the Web. The main goal is to allow P2P collaborative editing of Web pages (DOM elements), graphs, lists, objects, and arbitrary types of data in a Web browser, using state-of-the-art network protocols for message propagation. Therefore, the algorithm proposes a basic structure using linked lists, which can be extended to achieve more complex shared data types that support collaboration. YATA’s linked list representation and set of predefined rules limit the number of possible conflicts and ensure correctness of user intentions and convergence of operations. The core idea is to enforce full sorting of shared data types. YATA also supports offline editing, which is designed to address the needs of Web and mobile clients, such as operating updates when loans are low, opening and closing connections, and random message order when receiving.

YATA currently supports collaborative data types for linear data, trees, associative arrays, and graphs, while using these types to create more complex data types.

The premise that

Each user is assigned a unique identifier and an operation counter that increments each time an operation is performed by the user, so that an operation can be uniquely identified by the identifier and counter.

YATA uses bidirectional linked lists to represent linear data (such as text). We define only two types of operations: insert and delete. When the insert is deleted, the element is not deleted directly, but marked as deleted, so the deletion operation does not directly affect the insert logic. We actually delete the content that users delete through a specially designed garbage collection mechanism (described later).

We use Ok (IDk, Origin(k), Left(k), Right(k), IsDeleted(k), Content(k)) to indicate an insertion. In the command, IDk is the unique identifier of the user, IsDeleted(k) indicates whether the user IsDeleted, and Content(k) indicates the actual operation Content. Origin(k), Left(k), and Right(k) are existing insert operations. Linear data is represented by bidirectional linked list S, where Left(k) and Right(k) represent the front and rear nodes of the bidirectional linked list, and Origin(k) is the direct predecessor of creating nodes.

We use < to represent the leading node on the list S. O1<O2 indicates that O1 is the leading node of O2. O1<=O2 indicates that O1 is the front node of O2 or O1 and O2 are the same operation. For example, when the user creates a new insert at a local location, the new insert will be between Oi and Oj, which can be expressed by the formula Onew (IDk, Oi, Oi, Oj, f alse, Content(new)). The first and last sides of the S-list are represented by special delimiters. When the user finishes the insert operation locally, it broadcasts it to other clients.

YATA

Graph one:In Figure 1, a client receives that the operation Onew is being inserted into the bidirectional linked list S. The red line represents the left and right nodes, and Onew is eventually inserted between the two nodes of the red line after calculation. If a new insert operation occurs during the insert, a conflict may occur. In this case, the conflict must be resolved and the insert position allocated properly.

Intent preservation: The user’s intent is preserved if and only if Onew is inserted between the Left(I) and Right(I) operations. Because the position of each character inserted by the user relative to its adjacent characters in the document can effectively preserve the user’s intention, which is consistent with the definition of intention reservation in other materials.

Concurrent inserts: In Figure 1, the string T inserted by Onew should have been inserted directly between Y and A(the last A), but the string AT inserted by O2 and O3 has been inserted between the string YA, and Onew, O2, and O3 are concurrent inserts.

S = Left(new) ·C1 ·C2 ·… ·Cn ·Right(new), we think Onew and C1.. Cn conflict.

To find strict full order operations in conflicts, we define the following three rules:

Rule 1: Do not allow cross-join origins between conflicting operations. Two cases are allowed: insert between another operation and its original operation; The origin of one operation is the subsequent of another. We can understand this sentence by referring to the following figure, which shows the two situations that are allowed.Rule 2: When O1<O2 is specified, there can be no other operation greater than O2 and smaller than O1.

Rule 3: When two conflicting insert operations have the same Origin, the operation with the smallest user ID is on the left. This rule is based on the OT algorithm.

Then we prove the strict complete order of conflict operation according to three rules. The proof process is complicated by the derivation of mathematical formulas, which is omitted in this paper. Interested students can refer to the paper.

Insert algorithm

We have already shown that conflicting operations have a full order relationship, so how do we calculate the position of a new insert operation when we have an ordered list of inserts? Pseudo code:

// Insert 'I' in a list of // conflicting operations' ops'. ops){ i . position = ops [0]. position for o in ops do // Rule 2: // Search for the last operation // that is to the left of i. if(o<i.origin OR i.origin <= o.origin) AND (o. origin ! = i . origin OR o.creator < i.creator) do // rule 1 and 3: // If this formula is fulfilled , // i is a successor of o. i . position = o. position + 1 else do if i.origin > o.origin do // Breaking condition , // Rule 1 is no longer satisfied // since otherwise origin // connections break }Copy the code

The garbage collection

Theoretically, if all clients receive the delete operation, the operation can actually be deleted. However, determining whether all clients have successfully processed the deletion consumes too many network resources and deteriorates the synchronization performance.

The current approach is to simplify the problem by assuming that after a fixed time period T all clients are checked for deletion.

Yata uses a two-tier cache to handle garbage collection. Once O is available for garbage collection, it is moved to the first-tier buffer. If it is not recovered, T seconds later it is moved to the second buffer to wait for actual removal.

Because of YATA’s three rules, you cannot delete an insert operation in some cases. Because there is a new insert between the two insert operations that need to be deleted, deleting the preceding or subsequent operations can cause problems with this insert, as shown in the example below.

To ensure consistency, YATA requires that new insertions always occur between the leftmost undeleted character and its immediate successors. Only then can the garbage collector remove all operations to the right of the first deleted insert operation. In addition, the garbage collector in YATA is unfriendly to lazy connection support. This is because it retains references to deleted actions when the user is offline for more than T seconds, but not for online users who perform some deletions. Therefore, YATA does not support garbage collection of web sites while they are offline.

Support for offline editing

YATA supports offline editing for each client and records the operation locally. After the client is connected to the Internet, YATA checks the difference between local data and shared data and completes data synchronization.

Each site holds a state vector. Assume that user 1 with ID 1 and user 2 with ID 2 in a session, each user has two insert operations, and the state vector is expressed as: [(1,2), (2,2)] the state vector is sent to all clients only once, a user receives the state vector, compares it to the local state vector, and sends all remaining operations to the other clients. To make operations integrable on remote instances, operations are sent in the order and form in which they were created. YATA can transform an integration operation into its original form.

Algorithm complexity

The time complexity analysis of several CRDT merging algorithms is shown as follows:

Extension type

This section describes the basic types of operations and common data structures supported by YATA. On top of the basic data structure, you can implement some abstract data types that allow common data formats such as JSON and XML to be co-edited. Currently supported types include linear data types (for example, arrays, linked lists, sorted arrays, bitmaps), trees, graphs, and associative arrays.

List Manager Operation

The List Manager Operation is an abstract data type that manages the insert Operation. The new insert operation is placed somewhere between the two delimiters according to YATA’s rules.The List Manager Operation also deals with how to address the elements in an associative List and how to convert them to specific data types (such as strings). It represents linear data structures, such as lists and arrays, as well as tree-like data structures.

Replace Manager Operation

YATA supports only insert and delete operations, but updates are needed to simplify development when dealing with more complex types, so YATA supports updates to existing content by providing specialized types that support content replacement. As an example, consider the case where two users (with user ids 1 and 2) simultaneously replace the number 0 in the text with their respective user ids. For consistency, each site should perform the substitution and agree on the end result, where 1 or 2 will replace the old number 0. Yata converts it to a solved problem by using data types that ensure consistency.The Replace Manage inherits The List Manager Operation. The first actual insert (not a delimiter) of The Replace Manager, which is added as The first insert of The Replace Manager in order to Replace it after The user performs a new insert. The red line in the figure above refers to the current contents of Replace Manager. Because YATA guarantees that all sites will eventually have the same content, all sites will eventually reference the same insert content as Replace Manager content.

Map Manager Operation

The figure above shows YATA’s representation of a Map Manager, which assigns a Replace Manager Manager to each key of a Map in order to support concurrent operations on a shared Map.

More data type representations

YATA implements data formats such as JSON or XML as shared data types by combining the simple types described above.

The second part of the paper mainly describes the performance of Yjs and the current use of Yjs some products, this paper will not be detailed.

conclusion

The content of this article is mainly the translation of the paper and a little personal understanding. Interested students are advised to read the paper in its entirety after reading it.

In this paper, we mainly introduce the basic idea of implementing YATA. As a CRDT type collaborative algorithm, YATA and its implementation library Yjs have good performance and support point-to-point transmission, providing theoretical basis and practical scheme for us to implement non-client-server mode. We will also implement yJs-based collaboration schemes in the following projects.

Finally, I am also learning and using Yjs, welcome you to discuss YATA and Yjs related technologies.

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