The paper address: www.researchgate.net/publication…

Open source implementation warehouse: github.com.cnpmjs.org/yjs/yjs.git

Yjs is an implementation of CRDT. This paper translated part of the supporting papers of YJS to understand the implementation principle of YJS. The quoted part of the article is the original expression, some of the formats have not been adjusted, only used as an aid to understand the content of the article.

Abstract

Near real-time collaboration using Web browsers is becoming rapidly more and more popular for many applications such as text editing, coding, sketching and others. These applications require reliable algorithms to ensure consistency among the participating Web clients. Operational Transformation (OT) and more recently Commutative Replicated Data Types (CRDT) have become widely adopted solutions for this kind of problem. However, most existing approaches are non-trivial and require trade-offs between expressiveness, suitable infrastructure, performance and simplicity. The ever growing number of potential use cases, the new possibilities of cutting-edge messaging protocols that shaped the near real-time Web, and the use of N-way communication between clients (e.g. WebRTC), create a need for peer-to-peer algorithms that perform well and are not restricted to only a few supported data types. In this paper, we present YATA, an approach for peer-to-peer shared editing applications that ensures convergence, preserves user intentions, allows offline editing and can be utilized for arbitrary data types in the Web browser. Using Yjs, its open-source JavaScript library implementation, we have evaluated the performance and multiple usage of YATA in Web and mobile browsers, both on test and real-world data. The promising evaluation results as well as the uptake by many commercial vendors and open-source projects indicate a wide applicability of YATA.

Near-real-time collaboration applications are becoming increasingly popular in Web browsers, such as text editing, code collaboration, sketching, and more. These applications require robust algorithms to ensure consistency between participating clients. Operational transformation algorithms (OT) and the recently popular Exchange Replicable Data type (CRDT) are widely used for near real time collaboration. However, most existing methods do not address all issues, requiring trade-offs between Expressiveness, infrastructure, performance, and simplicity. The increasing number of potential use cases for near-real-time Web messaging protocols and the use of N-way communication between clients, such as WebRTC, have increased the demand for P2P algorithms with good performance and support for most data types. In this article, we introduced YATA, an approach for P2P collaborative editing that ensures convergence, preserves user intent, allows offline editing, and can be used with any data type in a Web browser. The open source JavaScript library implementation of the YATA algorithm is Yjs. We evaluated YATA performance and multiple uses in both Web and mobile browsers, including test data and real-world data. These evaluations, as well as the use of Yjs in many commercial applications and open source projects, indicate that YATA can be widely used.

Keywords: Near real-time collaborative editing; commutative replicateddata types; operational transformation; peer-to-peer information systems

Key words: near real-time collaborative editing; Exchange replication data type (CRDT); Operation transformation (OT) algorithm; P2P information system

3 THE YATA APPROACH

The YATA approach is created to provide a scalable solution for P2P optimistic concurrency control on the Web. The main goals are to allow the P2P collaborative editing of Webpages (DOM elements), graphs, lists, objects and arbitrary types in the Web browser, using cutting-edge protocols for message propagation. Therefore, the algorithm proposes a basic structure using a linked list, which can be extended to achieve collaboration on new shareable data types. YATA’s linked list internal representation and a collection of predefined rules limit the number of possible conflicts and ensure intention preservation and convergence. The core idea is enforcing a total order on the shared data types. YATA also supports offline editing, being meant to cope with requirements coming from both Web and mobile clients, such as small operation updates for low band width, on and off connections, random message order at receive time, etc.

The YATA approach is designed to provide an extensible solution for P2P optimistic concurrency control on the Web. The main goal is to enable P2P collaborative editing of any type in Webpages(DOM Elements), Graphs, Lists, Objects and Web browsers using an advanced message propagation protocol (webRTC/ WebSocket). Therefore, this algorithm proposes a basic structure based on linked lists, which can be extended to achieve collaboration on new shareable data types. YATA’s internal design of linked lists and a set of predefined rules limit the number of possible conflicts and ensure intent retention and convergence. The core idea is to ensure full order relationship on shared data types. YATA also supports offline editing to address the needs of Web and mobile clients.

YATA currently supports collaboration on linear data,trees, associative arrays and graphs. Using those types, it is possible to create more complex data types.

YATA currently supports collaboration in linear Data, Trees, Associative Arrays and Graphs. Using these types, you can create more complex data types.

In the following we formalize our approach and exemplify YATA’s behavior on text (Linear data) assumptions, definitions and describing how convergence achieved, we extend the linear representation to more data types and explain how those are further realized us-ing YATA.

In the following sections, we will show YATA and apply YATA’s behavior to Text (Linear Data). With assumptions, definitions, and descriptions of how to achieve convergence, we extend linear types to more data types and explain how to further implement these data types using YATA.

3.1 Requirements

Unique identifiers. Each user is represented by an unique identifier (userId). Additionally, each user gets an operation counter which gets incremented every time a user creates an operation. Upon its creation, the operation thus gets as-signed a unique identifier which is composed of the userId and the current operation counter.

Unique identifier. Each user is represented by a unique userId and gets an operation counter, count, that increments each time the user creates an operation. When an operation is created, it gets a unique identifier (userId, count) that consists of the userId and the current operation counter count.

Operations. YATA represents linear data (e.g. text) as a doubly linked list. We define only two types of changes on this representation:insert and delete. As it is shown inFigure 1, every element in the linked list is represented by an insert operation (also named insertion). When an insertion is deleted, it is just marked as such and not removed from the list (i.e. tombstone approach). Therefore, Delete operations do not have an effect on our insert algorithm. In Section 3.5 we define a garbage collection mechanism That, in combination with our insert algorithm 3.4, can remove deleted insertions.

Operation. YATA represents linear data, such as text, as double-linked lists. We define only two types of operations in linear data: insert and delete. As figure 1 shows, each element in the linked list is produced by an insert operation, that is, the element corresponds to the insert operation. The delete operation uses the tombstone mechanism, which is to make a mark without actually removing it from the list. Therefore, the delete operation has no effect on our insert algorithm. In Section 3.5, we define a garbage collection mechanism that, combined with our insert algorithm 3.4, removes nodes marked for deletion.

We denote an insert operation as oko_kok( idkid_kidk, originkorigin_korigink, leftkleft_kleftk, rightkright_krightk, IsDeletedkisDeleted_kisDeletedk, contentkcontent_kcontentk) where idkid_kidkis Oko_kok’s unique identifier, contentkcontent_kcontentkis the content (e.g. a character), flag that marks an insertion as deleted, and originkorigin_korigink, leftkleft_kleftk, rightkright_krightkare references to other already existing insertions. We represent linear data as a doubly linked list SSSof insertions. Therefore, leftkleft_kleftk, and rightkright_krightkreference to the previous node, respectively next node in the list. originkorigin_korigink denotes the direct predecessor at creation time (i.e., the node after which it was originally integrated to).

We represent an insert operation as ok=(idk,origink,leftk,rightk,isDeletedk,contentk)o_k=(id_k,origin_k,left_k,right_k,isDeleted_k,content_k)ok=(idk,origink , leftk rightk isDeletedk contentk), including idkid_kidk oko_kok is a unique identifier, contentkcontent_kcontentk is the content of the operation (e.g., characters), IsDeletedkisDeleted_kisDeletedk marks the insert as deleted or not, and originKorigin_korigink, leftKleft_kleftk, Rightkright_krightk is a reference to other existing inserts. We represent linear data as bidirectional linked list SSS, leftKlefT_klefTK and Rightkright_krightk refer to the previous and next node in the list respectively, and Originkorigin_korigink represents the immediate precursor node at creation time.

We define
$<$as the natural predecessor relation on
$S$.

We define <<< as a natural preposition on SSS. O1 < O2O_1 < O_2O1 < O2 indicates that O1O_1O1 is the precursor node of O2O_2O2. O1 ≤ O2O1 ≤ O2O1 ≤ O2 refers to O1 < O2O_1 < O_2O1 < O2, and O1O_1O1 may equal o2O_2O2

Example. When a user creates a new insertion at a local site, this is integrated between two insertions
$o_i$, and
$o_j$. The newly created insertion is therefore defined as:
$o_new(id_k, o_i, o_i, o_j, false, content_new)$. Note that
$left_new$,and
$right_new$ are defined when an insertion has been applied to the list and may change when new insertions are integrated into S, but
$origin_new$, defined at insertion creation time is never modified. After the user integrates a new insertion at his local site he sends it (via broadcast), as is, to all users.

Let me give you an example. When a user creates a new insert at the local site, the insert is integrated between the two inserts. Assuming the two inserts are oio_ioi and ojo_joj, the newly created insert will be defined as: onew(idk,oi,oi,oj,false,contentnew)o_{new}(id_k, o_i, o_i, o_j, false, Onew content_ {new}) (idk, oi, oi, oj, false, contentnew). Where LeftNewLeft_ {new} LeftNew and RightNewright_ {new} RightNew are defined when an insert operation is placed in the linked list. When another new insert operation is integrated into the SSS, Leftnewleft_ {new} LeftNew and RightNewright_ {new} RightNew may be changed. But the originneworigin_{new} defined at insert creation time is never changed. When a user integrates a new insert locally, the local site sends it to all users.

A special case occurs when an insertion is performed at the beginning or at the end of S, because there is no insertion to refer to as
$left_∗$, respectively
$right_∗$. This can be fixed by using special delimiters, which denote the beginning and the end of S, respectively. Therefore, we assume without loss of generality that an insertion always defines
$origin_k$,
$left_k$, and
$right_k$

A special case occurs when an insert is performed at the beginning or end of an SSS where there is no left or right insert. This can be solved by using special delimiters that indicate the beginning and end of SSS, respectively. Therefore, we can assume that an insert operation can always define OriginKorigin_kOrigink, LeftKlefT_klefTK, and RightKright_krightk.

3.2 YATA algorithm

The example in Figure 1 shows how a received operation onewo_newonew is integrated in S. Here, the red connections reference the intention of the insertion, which is defined through leftnewleft_{new}leftnew and rightnewright_{new}rightnew – i.e. insert the letter between these two letters. When the insertion is integrated, YATA assures that it will be placed some where between these letters. Convergence is therefore ensured, unless one or more remote operations were already inserted between leftnewleft_{new}leftnew and rightnewright_{new}rightnew, which then leads to a conflict that needs to be solved.

The example in Figure 1 shows how to integrate the received operation oneWO_ {new}onew into SSS. Here, the red join refers to the insert intent, which is defined by LeftNewLeft_ {new} LeftNew and RightNewright_ {new} RightNew, That is, between the two letters (YYY at position o1o_1o1 and AAA at position o4o_4o4). When the insert is integrated, YATA ensures that it will be placed somewhere between these letters. Convergence can therefore be ensured unless one or more remote operations have been inserted between LeftNewLeft_ {new} leftNew and RightNewright_ {new} RightNew, which would result in the need to resolve conflicts.

Intention PreservationThe intention of an insertion oio_ioi is preserved if and only if the insertion is integrated some where between leftileft_ilefti and rightiright_irighti. This notion of intention preservation conforms to the natural perception for the intention of text insertions and it is similar to other definitions found in the literature. In [2], the intention preservation is defined when each character inserted by a user between two other characters in a document keeps its relative position between its neighbors during the editing process.

Intent reserved: The intent to insert oio_ioi is retained if and only if the insert is integrated somewhere between leftileft_ilefti and Rightiright_irighti. This notion of intent retention is consistent with actual text insertion.

The concurrent insertion problem: In the example in Figure 1, Inserted between the characters “Y” and the “A” – At creation time, “T” sees only “YA”. Inserted between these two letters. In the example, O2O_2O2, and o3o_3o3conflict onewo_newonewwith .

Concurrent insertion problem: In the example in Figure 1, TTT is inserted with the intention of inserting it between the characters YYY and AAA, such that TTT sees only YAYAYA at creation time. But in this case, the letter sequence ATATAT has been inserted between the letters YAYAYA, causing o2O_2O2 and O3O_3O3 to conflict with OneWO_ {new}onew.

12. Conflicting insertions: Keeping the above notations, assuming S=leftnew⋅ C1 ⋅c2.. ⋅ CN rightnewS = left_new · c_1 · c_2 ·.. , c_n, right_newS = leftnew ⋅ c1 ⋅ ⋅ serie c2.. ⋅ CN ⋅ rightNew, then we say that oneWO_newonew conflicts with C1.. cnc_1.. c_nc1.. cn.

Inserting collisions: To use the notation above, assume S= leftNew ⋅ C1 ⋅.. ⋅ CN rightnewS = left_{new} · c_1 · c_2 ·.. C_n right_, {new} S = leftnew ⋅ c1 ⋅ ⋅ serie c2.. ⋅ CN ⋅ RightNew, so onewo_{new}onew and C1.. cnc_1.. c_nc1.. Cn conflict.

In the following we define a function

Next we will define the function

In the following we will frequently refer to the graphical representation of insertions as it is shown in Figure 1. The insertion
$o_new$ has three references/connections. On the left hand site of
$o_new$ there is a
$origin_new$ connection, and a
$left_new$ connection to
$o_1$. On the right hand site of
$o_new$ there is a
$right_new$ connection to
$o_4$. While
$left_new$, and
$right_new$ define the usual predecessor/successor relation in a linked list. The
$origin_new$ connection will never change and is employed to find the strict total order function
$<_c$.

We will refer to the inserted representation in Figure 1 frequently throughout the rest of the article. Insert oneWO_ {new}onew has three connections. To the left of onewo_{new}onew there is a connection between originNeworigin_ {new} OriginNew and LeftNewLeft_ {new} LeftNew to o1O_1o1. To the right of onewo_{new}onew there is a rightNewright_ {new} RightNew connection to o4O_4O4. Leftnewleft_ {new} LeftNew and RightNewright_ {new} RightNew define the pre/follow relationships that are common in lists. Originneworigin_ {new} The originNew connection is never changed and is used to find strictly fully ordered functions

We compose the following three rules in order to find a strict total order
$<_c$ on conflicting operations.

To find a strictly fully ordered function

Rule 1 We forbid crossing of origin connections (red lines in the graphical representation) between conflicting insertions. This rule is easily explained using the graphical representation of insertions in the linked list. As we stated before, every insertion has an origin connection to an insertion to the left (to a predecessor). Only when two operations are concurrently inserted after the same insertion, they will have the same origin.

Rule 1: We disallow origin connections that are inserted in conflict from crossing. This rule is easily explained using graphical representations inserted in linked lists. As mentioned earlier, each insert has an Origin connection to the left/front insert. Only if two insert operations are inserted in parallel after the same insert will they have the same Origin.

Figure 2 illustrates the two cases that are allowed when line crossing is forbidden. Either, one operation is between the other operation and its origin, or the origin of the one operation is a successor of the other operation. Therefore, the following formula must hold for conflicting insertions
$o_1$ and
$o_2$:

Figure 2 illustrates two situations that are allowed when a red line crossing is prohibited. Either an operation lies between another operation and its Origin, or the origin of one operation is a subsequent operation of another operation. Therefore, in the case of conflicts between o1O_1O1 and O2O_2O2 inserted, the following formula must hold:

$O_1 <_{rule1} O_2 < ORIGIN_2 ∨ ORIGIN_2 ≤ ORIGIN_1$

Rule 2Specifies transitivity on
$<_c$. Let
$o_1 <_c o_2$. Then following rule ensures, that there is no
$o$ that is greater than
$o_2$, but smaller than
$o_1$, with respect to
$<_c$

Rule 2: Specify transitivity on

$O1 <_{rule2} O2 stripped O: O_2 < _C O → O_1 ≤ O \not\exist O: O_2 < _C O < O_1$

Rule 3When two conflicting insertions have the same origin, the insertion with the smaller creator id is to the left. We borrow this rule from the OT approach. But in OT this rule is applied when the position parameters are equal.

Rule 3: When two conflicting inserts have the same origin, the insert with the smaller creator ID is on the left. We borrowed this rule from the OT algorithm.

$O_1 <_{rule3} O_2 ≡ ORIGIN_2 → Creator_1 < CREator_2$

We get retrieve the total order function
$<_c$ by enforcing all three rules:

By enforcing these three rules, we get the definition of the fully ordered function

3.3 Correctness

The specific proof process is too mathematical, please move the reader to the original paper.

Insert Algorithm

Previously, we proved that there exists a total order relation on conflicting insertions. In this section we show how we can compute the new position for an insertion, when we already have an ordered list of insertions.

Previously, we proved that the conflicting insert operations have a full order relationship. In this section, we will present an algorithm to calculate the position of new inserts when we already have an ordered list of inserts.

Listing 3.4 shows how the exercise can be balanced algorithmically. The algorithm Property (3) (No line crossing) as a breaking condition. Therefore, we stop computing when origin connections definitely will cross.

The following figure shows how conflicting inserts are resolved by the algorithm. The algorithm uses non-existent cross-origin links as interrupt conditions. Therefore, stop the calculation when the connections will cross.

The worst case time complexity of the algorithm is O(|C|2) where |C| is the number of conflicting operations. In the case that the breaking condition is reached in the first iteration, no positions are compared. This is why the best case time complexity is O(1). A complexity analysis is presented in Section 3.7.

Time complexity of this algorithm under the worst case for O (2) ∣ C ∣ O (| | C ^ 2) O (2) ∣ ∣ C, including ∣ ∣ C | | C ∣ ∣ C is the number of insert conflict. No position is compared in the first iteration if the breaking condition is met. That’s why the best-case time complexity is O(1)O(1)O(1).

Garbage Collection

In the literature, Garbage collection has also been proposed in [21] where “cold” areas of a document are identified or in Logoot [31], which uses a graveyard for removed operations. Conceptually, an insertion marked for deletion can be garbage collected when all sites received the remove operation and have in their internal representation the operation that is to be garbage collected. However, it is hard to determine if all collaborators know simultaneously that a content was deleted. Ideally, using classic methods such as state vectors, a mechanism where YATA ensures that all sites have applied a removal can be a candidate solution. As a downside, such a mechanism would require more network resources and leads to a decrease in performance, especially in P2P settings. An optimal solution to this issue is still being considered.

Conceptually, an operation can be garbage collected when all sites have received the deletion and marked in their internal storage that the deletion should be collected by the garbage collection mechanism. However, it is difficult to determine whether all sites can simultaneously know that something has been removed.

In the current approach, the problem is simplified by assuming that all users retrieved a certain remove operation after a fixed time period t which can be set according to the expected protocol and network characteristics (e.g., 30 s). In practice, YATA uses two buffers for garbage collection, to ensure that list elements are not directly removed. As such, once ok can be garbage collected, it will be moved into the first buffer. If nothing changes, after t seconds it will be copied into the second array and from here will be re- moved by the garbage collector (i.e., can be safely removed from the list and the buffer). From our practical experiences and the use in production, such a delay is sufficient to ensure that content will be removed safely, without any losses that may lead to inconsistencies. This is in line with experiments performed for assessing the NRT criteria and measuring the time in which operations are being applied. These experiments (cf. Figure 9, Section 6) show that the average time for receiving and applying a remove operation using text (with a length under 103 characters) at a remote site is approx. 12 ms. Under the same conditions, receiving and applying a single remove operation with a length of 105 characters at a remote site is done within an Average time of 39.3ms (SD 2.45ms), from a pool of ten measurements.

In the current approach, the above problem can be simplified by assuming that all users can receive a delete operation after a fixed period t (the parameter t can be set according to the expected protocol and network characteristics, such as t=30s). In fact, YATA uses two buffers for garbage collection to ensure that list elements are not deleted directly. Therefore, if oko_kok can be garbage collected, it will be moved to the first buffer. If nothing changes, t seconds later it will be copied to the second buffer and removed from there by the garbage collector (that is, it can be safely removed from the list and buffer). In our experience and in production environments, this delay is sufficient to ensure that content is safely removed without causing inconsistencies across sites.

As a consequence of YATA’s rules, in some cases it is not possible to remove insert operations. The reason is that for an operation that is inserted between two undeleted insert-type operations, this could lead to a deleted predecessor or successor (cf. Figure 4).

According to YATA’s rules, you cannot delete an insert operation in some cases. The reason is that an insert between two undeleted inserts can result in a precursor or subsequent node being deleted (see Figure 4).

In order to ensure consistency, YATA demands that a new insertion is always inserted between the most left non- deleted character and its direct successor. Only then, the garbage collector can remove all operations that are to the right of the first deleted insertion.

To ensure consistency, in the YATA algorithm, the position of the new insert operation must be between the leftmost undeleted character and its immediate successor. Only then can the garbage collection mechanism delete all operations to the right of the first deleted insert.

Furthermore, due to its design, the garbage collector in YATA may break late join mechanisms. This is because when a user is offline for a period longer than t seconds, it will still hold references to deleted operations, while online users who already performed certain removals do not. Therefore, YATA does not support garbage collection for a site while it is offline.

In addition, the garbage collector in YATA can break the delayed join mechanism. This is because when a user is offline for more than t seconds, it still retains references to deleted actions, whereas an online user who has performed some deletion does not. Therefore, YATA does not support garbage collection when the site is offline.

3.6 Offline Editing Support

YATA supports offline editing using the internal data representation which is maintained at each client. Once clients are online, YATA performs a check for diverged states of the shared data and synchronizes it.

YATA maintains a state vector on each client to support offline editing. After the client connects to the network, YATA checks and synchronizes the different states of the shared data.

Every site holds a state vector. It saves the next expected operation id per user. As an example, consider user1 with userId 1 is in a session with user2 with userId 2. Both users created two operations. As we explained above, the operation id is defined as a tuple of userId and operation counter. Therefore, the state vector is expressed as: [(1, 2), (2, 2)] (assuming we start counting with 0).

Each site has a state vector. It holds the ID of each user’s next expected action. For example, assume that user1 with ID 1 is in a session with user2 with ID 2. Both users have created two operations. As we explained earlier, the operation ID is defined (userId, count). Therefore, the state vector is expressed as: [(1, 2), (2)] [(1, 2), (2, 2)] [(1, 2), (2)] (assuming starting from 0).

For synchronization, the state vector is not sent with each operation, but it is sent only once to all clients. A user that receives a state vector compares it with the local state vector and sends all remaining operations to the synchronizing client. In order to make operations integrable on the remote instances, Operations are sent in the order and the form in which they were created. Our YATA’s implementation can transform integrated operations to their original form.

When synchronization occurs, the state vector is not sent with each operation, but only once to all clients. The user receiving the state vector compares it to the local state vector and sends all remaining operations to the synchronization client. In order for operations to be integrated on remote instances, they are sent in the order and form in which they were created. YATA can convert these operations into their original form.