This article is translated by @Kuaishou Docs team

1 document

  • A document is a list of characters or a string.

  • A document can also be represented as a changeset list

2 change sets

  • A changeset represents a change to a document

  • A changeset can be applied to a document to produce a new document

  • When a document is represented as a list of change sets, we consider the first change set to be applied to the empty document [].

3 Change set representation

(l, l ‘)/c1, c2, c3,…

L is the length of the document before it changes,

L ‘represents the changed length of the document,

[c1, c2, c3,…] Is an array of characters (l ‘in length) describing the changed document.

Any CI satisfying 0 ≤ I ≤ L ‘is a numeric integer (int) or a character

  • Numbers represent characters retained in the original document

  • Character means insert

4 Change set constraints

  • Change sets are normative and therefore comparable. In computer memory, we always have the same representation for the same changeset. If the memory representation of two change sets is different, they must be different change sets.

  • Change sets are concise. Therefore, if there are two ways to represent a changeset in computer memory, we always use the one that consumes the least bytes.

We’ll talk about optimizing change set representations (using Strips and other similar techniques) later. Any changeset representation must satisfy these two constraints.

5 symbol representation

  • We use algebraic multiplication notation to represent the application of change sets

  • When a changeset is defined as an operation on a document, the document itself is represented as a list of changesets initialized with an empty document

Example A = (0→5)[” hello “] B = (5→11)[0−4, “world”]

We can write the document “Hello World” as A·B or AB. Note that the initial document can be represented as a change set (0→N)[” < document contents > “].

We can also call (AB) A combination of A and B when A and B are changesets, and the changeset is closed after the combination.

6 Change set combination

For any two change sets, similarly

A = (n1 and n2) […]

B = (n2 and n3) […]

It is clear that there is A third change set C = (n1→n3)[···] applied to document X that yields the same result as applying A first and then B. In this case, let’s write AB is equal to C.

With the presentation in Section 3, it is easy to calculate a combination of two changesets.

7 Change set merge

Now let’s move on to the real world of document editing. Suppose two different users make two different changes to the same document at the same time. They cannot be combined directly. For example, if we have A document X of length N, we might have change set A = (n→na)[…na characters], B = (n→nb)[…nb characters], and n≠ Na ≠ Nb.

It is not possible to calculate (XA)B directly, because B can only be applied to documents of length N, and (XA) has length NA. Similarly, A can’t be applied to delta XB because delta XB has length nb.

That’s why merging was introduced. Merge is based on two changesets applied to the same original document (which cannot be combined), calculating a new changeset while preserving changes from both. The combination of A and B is written as m(A, B). In order for the system to work, we need m(A, B) =m(B, A).

In order to build a workable system, there are many different implementations besides the merge mechanism we have talked about so far. We have given an implementation for text that follows the following constraints.

8. Follow

When users A and B have the same document X in front of their screens, they start to change A and B, respectively. It is useless to calculate M (A, B) because M (A, B) applies to document X, but the user is already looking at documents XA and XB. What we really want is to compute B prime and A prime, such that XAB prime is equal to XBA prime is equal to Xm of A, B.

“Catch up” computes the change set B’ and A’, whose function f is defined as, when we compute f(A, B) such that Af(A, B) =Bf(B, A) =m(A, B) =m(B, A).

  • Insertions in A become reserved characters in f(A, B)

  • An insert in B becomes an insert in F (A, B)

  • Reserve any characters that are reserved in both A and B

For example, suppose we have an initial document X=(0→8)[” baseball “]. User A changes it to “basil” and user B changes it to “below”

X = (0 to 8) [” baseball “]

A = (8 – > 5) [7] 0-1, “si”,

B = (8 – > 5) [0, “e”, 6, and “ow”]

First, we calculate the combination m(A, B) =m(B, A) according to the constraint conditions.

M (A, B) = (8-6) [0, “e”, “si”, “ow”] = (8-6) [0, “esiow]” (note: besiow)

Follow B’ = f(A, B) and A’ = f(B, A).

B ‘= f(A, B) = (5→6)[0, “e”,2,3, “ow”]

Note that the numbers 0, 2, and 3 are indexes in A A = (8→5)[0,1, “si”,7]

0, 1, 2, 3, 4

0 1 s i 7

A ‘= f (B, A) = (5, 6) [0, 1, “si”, 3, 4]

We can now check that AB ‘=BA’ =m(A, B) = (8→6)[0, “esiow”]

Now that we’ve worked out the math once and for all, we can build a client/server system to support real-time editing by multiple users.

9 System Overview

A server saves the current state of the document. The client (user) can connect to the server from their Web browser. The client and server keep state and can send messages to each other in real time. But since we are in a Web browser scenario, clients cannot send messages directly to each other, and must always go through the server (which might be different from the previous technique?).

Another key design feature of the system is that clients must always be able to edit local copies of documents so that users are not blocked from entering while waiting for data to be sent or received.

10 Client status

At any given time, the client maintains its state in the form of three change sets. The client document looks like A·X·Y.

Where A is the latest server version, which is A combination of all the change sets that have been submitted to the server from this and other clients, and that the server has notified the relevant clients. Initialize to A =(0→N)[< document initial content >].

X is the combination of all change sets that the client has committed to the server but has not yet been validated. Initialize to X =(N→N)[0,1,2…N−1]. Represents the invariant change set identity, which we will later call IN,

Y is the combination of all change sets that the client has completed but not yet committed to the server. Initialize to Y =(N→N)[0,1,2…N−1].

11 Client operations

The client does five things.

1. Merge the new input to the local state

2. Submit the change set to the server

3. Listen for validation of committed changesets

4. Listen for change sets from other clients from the server

5. Connect to the server and request initialization of the document

When these five events occur, the client updates its A·X·Y representation according to the relationship below. Over time, changes “move left” : they change to Y when the user types, X when the changeset is submitted to the server, and A when the server confirms the changeset

11.1 New local key

When a user makes an edit operation E to the document, the client computes the combination of (Y·E) and updates its local state, Y←Y·E. That is, if Y is the variable holding locally uncommitted changes, it will be assigned the new value (Y·E).

11.2 Submitting a Change Set to the Server

When the client commits its local changes to the server, it transfers a copy of Y and assigns Y to X and IN to Y. That is to say:

  1. Send Y to the server

  2. X please Y

  3. Please IN Y

This happens every 500 milliseconds as soon as an acknowledgement message is received. Confirmation must be received before resubmission. Note that X is always equal to IN until the second step occurs, so no information is lost.

11.3 Listening for ACK Messages on the Server

When the client receives an ACK message from the server

A. please a. X

X please IN

11.4 Listening for Change Sets on Other Clients

When one client listens to another client’s changeset B, it evaluates A new A, X, and Y, which we call A’, X’, and Y’, respectively. It also computes a changeset D to be applied to the client’s current text view V. Because AXY must be equal to the current view, AXY =V before the client listens on B, and A’X’Y’ =VD after the calculation.

Complete the following steps

  1. Let’s calculate A prime is equal to AB

  2. Calculate X’ = f(B, X).

  3. Calculate Y’ = f(f(X, B), Y)

  4. Calculate D = f(Y, f(X, B))

  5. Assign A please A ‘, please X X, Y, please Y ‘

  6. Apply D to the current view displayed on the user’s screen.

F in steps 2, 3, and 4 is the chase operation described in Section 8

A’X’Y’ (X ‘X’ X’Y’)(f(X (X, B), Y)).

m(P, Q) =m(Q, P) =Qf(Q, P) =Pf(P, Q)

Applied to the relationship above, we get

A ‘X’ Y ‘= ABf (B, X) f (f (X, B), Y) / /, Bf (B, X) = Xf (X, B)

= AXf(X, B)f(f(X, B), Y) // f(X, B)f(f(X, B), Y) = Yf(Y,f(X,B))

= AXYf(Y, f(X, B)) // D = f(Y, f(X, B))

= AXYD

= VD

Just like we said

11.5 Connecting to the Server

When the client first connects to the server, it first generates a random unique ID and sends it to the server. The client remembers this ID and carries it with it when sending each changeset to the server.

The client receives the latest version of the document from the server, called HEADTEXT. Then the client set:

A. please HEADTEXT

X please IN

Please IN Y

Finally, the client displays HEADTEXT on the screen.

12 Server Overview

Like the client, the server is stateful and performs operations. The action is only performed when a message is replied from the client.

13 Status of the server

The server maintains the document as an ordered list of version records. A release record is a data structure that contains a change set and author information

RevisionRecord = {

ChangeSet, // ChangeSet

Source (unique ID), //

Revision Number // Version Number, consecutive order, starting from 0

}

For efficiency, the server can also store a variable called HEADTEXT, which is a combination of all the change sets in the version record list. This is an optimization because it can obviously be calculated from a set of release records.

14 Server Operations Overview

In addition to maintaining the state of the collection of connected clients and remembering the latest version numbers in each client, the server does two things:

  1. The client connection that responds to the request for the initial document.

  2. Respond to a new changeset submitted by the client.

14.1 Responding to Client Connections

When a server receives a connection request from a client, it receives the client’s unique ID and stores it in a set of connected clients on the server. It then sends the contents of HEADTEXT and the corresponding version number to the client. Finally, the server indicates that the version number of the client is the latest.

14.2 Responding to Client Change Sets

When a server receives information about client changeset C from a client, it does five things:

1. Indicates that the change applies to the version number rC (the latest version of the client).

2. Create a new changeset C ‘relative to the most recent version number of the server (we call it rH, where H stands for HEAD). C’ can be calculated using catch-up (Section 8, p. Keep in mind that the server side has a set of change sets

S0→S1→.. Src→Src+1→.. →SrH

C ‘is relative to Src, but we need to calculate relative to SrH. We can compute the new C relative to Src+1 by computing f(Src+1, C). Similarly, we can compute Src+2 repeatedly, and so on, until C ‘represents relative SrH.

3. Send C ‘to all other clients

4. Send an ACK to the original client

5. Create a new version record based on C ‘and the client ID, and add it to the version record list on the server.

Additional topics

(A) Optimization (Strips, More Caching, etc.)

(b) Pseudo-code for combination, merge, and chase

(c) How can author information be used to color tag documents based on who typed what

(d) How to maintain a persistent connection between the client and the server