Building a Real-time Collaborative Code Editor

Dinamo Team — Mon, 28 Sep 2020 01:25:25 GMT

Using Conflict-free Replicated Data types

A demo of Code Spot — a real-time collaborative code editor

“This piece of code hurts my eyes”.

That was my first reaction after my friend sent me some Python source code through Messenger. In Python, indentation is important because you cannot write an if-else block or loop without it. And here, Messenger has removed all indentations from the code.

At the time, I wished there was a tool that allowed for quick collaboration and didn’t require an account so I could easily help my friend with her code.

A few weeks later, I was fortunate to talk to a friend of mine, who was also passionate about software engineering. At first, he thought it was an easy problem but after some research, the problem turned out to be much more challenging.

Since we both love challenging problems and working in a team, we have teamed up and created Code Spot, a synchronized code editor with the power of Visual Studio Code. You can check it out at https://code-spot.net, or look at the source code on our GitHub repo.

In this article, we will show you why synchronizing text (or code) in real-time is a non-trivial problem, and how we can solve that problem by using Conflict-free Replicated Data type (CRDT).

But first, let’s understand what a code editor is under the hood.

I/ What is a code editor?

A code editor is just a plain text editor that has extra functionalities such as code suggestion and syntax highlighting. Under the hood, a text editor associates with each character a number that determines the position of that character.

For example, in the text “Code” below, ‘C’ is at position 0, ‘o’ is at position 1, ‘d’ is at position 2 and ‘e’ is at position 3

An illustration of text editor indices

When you type a character ‘r’ at the end of the text, you are executing the operation insert(‘r’, 4). And when you delete ‘C’, you are executing delete(0). Notice that when you delete a character, everything to the right of it gets shifted 1 position to the left.

Simple operations on a text editor

I know “oder” is not a word, but that’s ok 😊

II/ Problem with synchronizing real-time editing

Ok. Now you know how a code editor works. You are probably wondering: “What is so difficult about synchronizing text/code in real-time? After inserting/deleting, just send the request to other users so they can update their text. Simple enough.”

That was exactly what my friend thought too, but the problem turned out to be much more difficult, remember? Let’s attempt to sync text/code and see why it fails.

1/ Problem #1: Commutativity

Suppose User 1 and 2 are editing the same document in real-time.

On the screen, they have the text “BCD”. U1 inserts “A” at position 0 and simultaneously, U2 inserts “E” at position 3 and then they send each other these requests (probably through a server).

2 users went out of sync after simple insertions

As you can see, after 2 simple operations, U1 and U2’s screens are now different. This is because inserting at index 0 and then 3 will give a different result from inserting at index 3 and then 0. Order matters. Insertion (and deletion) operations by index alone are not commutative.

To give you a sense of commutativity, adding integers is commutative: 5 + 2 + 3 = 3 + 5 + 2. Applying ‘+’ operations in a different order gives the same result. However, adding and dividing is not: 1 + 2 / 3 not equals 1 / 3+ 2. Apply ‘+’ and ‘/’ operations in a different order gives different results.

2/ Problem #2: Idempotency

Now suppose U1 and U2 have the text “ABCDE” on their screens and they delete the character ‘A’ at the same time. We expect they both have “BCDE” on the screen in the end. But…

Position 0 was deleted twice

because each user receives an extra delete operation, 2 characters are deleted instead of 1. This is not good because this is not what they intended to do. Deleting the same character twice should be the same as deleting it once. In other words, deletion should be Idempotent.

An example of an idempotent operation is adding by 0: a + 0 = a + 0 + 0 = a + 0 + 0 + 0.

After just a few changes, 2 users’ screens have gone out of sync. Can you imagine what would happen if they type more text or have more people editing at the same time? 😨

We hope we convinced you that synchronizing text in real-time is pretty hard.

The 2 problems above are the main challenges of synchronizing text in real-time. Luckily, if somehow we can make our 2 operations (deletion, insertion) commutative and idempotent, synchronization will happen automatically.

Seriously! Imagine if these operations commute, 2 users can make any kind of changes to the text and send these changes later in the future to the other person. Because the order in which the operations are applied doesn’t matter, each person can apply their operations and the other person’s operations in a different order, and they’ll both get the same final result.

Also, because operations are idempotent, 2 users deleting the same character will only result in that particular character being deleted instead of two characters get deleted.

And this applies to any number of users, not just two users.

So, synchronizing any operation which has these 2 properties is trivial. To give you one more example, consider the ‘add’ operation in an add-only Set. Because of its commutativity and idempotency, you can add items to a set in any order and will get the same set in the end. If you need to synchronize an add-only Set, do you see how easy this is? :)

Conclusion: Real-time editing synchronization is hard because insertions and deletions don’t have commutativity and idempotency properties. If they do, however, synchronous editing becomes trivial.

In the next section, we’ll discuss how to achieve these 2 properties.

Note: All operations you see in a code editor, whether it is undo / redo, drag and drop or even code autocompletion, are just a series of insertions and deletions. Therefore, if we can sync insertion and deletion, we can make a fully-featured Real-time Collaborative Code Editor!

III/ Conflict-free replicated Data type (CRDT)

Let’s bring back the previous example:

2 characters were deleted instead of 1

Position 0 is deleted twice because a position alone does not contain enough information.

This triggers an interesting question: What if we have extra information in the request? What if, instead of deleting a character at position 0, we add something to the character to make it unique so now we’re deleting that specific character at position 0?

This is exactly the idea behind the CRDT used in Code Spot.

The CRDT we used in Code Spot is nothing more than a normal character added by a unique ID object so that insertion and deletion on that CRDT are commutative and idempotent. The complete design of this ID object is quite involved and deserves its own article. For now, let’s assume this ID is just a number, and see how it gets very close at enabling commutativity and idempotency.

Let’s add a unique number to each character

U1: A¹ B⁷ C⁸ D²⁴ E⁵¹

U2: A¹ B⁷ C⁸ D²⁴ E⁵¹

First, idempotency: If User 1 and User 2 deletes ‘A’ at the same time:

U1: B⁷ C⁸ D²⁴ E⁵¹

U2: B⁷ C⁸ D²⁴ E⁵¹

They will send each other the request “Delete that particular character with Id = 3” (notice position is no longer needed).

When User 1 receives User 2’s request and vice versa, the character with Id = 3 no longer exists in their texts. So, these requests will be discarded. The final states of the texts:

U1: B⁷ C⁸ D²⁴ E⁵¹

U2: B⁷ C⁸ D²⁴ E⁵¹

=> Great! Idempotency is achieved 😊

Second, commutativity:

This needs a bit more discussion, as we haven’t even told you how to pick an ID. Deletion is easy because the ID is already present. What if we want to insert a new character?

If we pick a random number, let’s say 40, the request will look like Insert ‘a’ with ID = 40. User 2 receives this request from User 1, and he has no clue where to insert ‘a’ at! After all, if we send the position together, we will get hit by Problem #1 again.

So, the ID needs to not only identify a unique character but also tell the user where that character should be! How can we contain that much information in a simple ID?

Hmm… Wouldn’t it be neat if our IDs are always in sorted order? (If you look at our Ids in the previous example, they are sorted). That way, if User 2 receives “Insert ‘a’ with id = 40” request from User 1, he will know exactly where ‘a’ should go:

U2: B⁷ C⁸ D²⁴ *a⁴⁰* E⁵¹

In other words, if the sorted order of the characters according to their IDs always matches exactly the order of the characters on the screen, knowing the ID alone is enough to insert (or remove) any character!

If User 2 now wants to insert a character ‘w’ between ‘a’ and ‘E’, he simply needs to find an ID between 40 and 51 to attach to this character ‘w’ (Let’s say he picked 45):

U2: B⁷ C⁸ D²⁴ a⁴⁰ *w⁴⁵* E⁵¹

U1: B⁷ C⁸ D²⁴ a⁴⁰ E⁵¹

When User 2 sends the request to User 1: “Insert character w with id = 45”, User 1 knows exactly where to insert this character ‘w’ because the Ids need to remain sorted:

U1: B⁷ C⁸ D²⁴ a⁴⁰ *w⁴⁵* E⁵¹

Even if someone inserts something between ‘B’ and ‘C’, we can pick 7.5 to be the ID between 7 and 8 (Yes! ID can be a decimal number).

B⁷ *x⁷⁵* C⁸ D²⁴ a⁴⁰ w⁴⁵ E⁵¹ (Medium doesn’t allow decimal superscript)

Neat!

Because of these ‘unique’ IDs (We’ll talk about the ‘’ later), insertions and deletions can be applied in any order, and you will still get the same text in the end (well, unless you do something silly such as delete a character before it is even created… It can happen if you use UDP protocol!).

To convince you that these IDs work quite well, let’s look at our current CRDT in action:

CRDT in action! (2 users initially have “BCD” on their screens)

It works quite well doesn’t it 😊

Now, you might notice that we put ‘unique’ in a quotation. We also mentioned that the actual CRDT is more complex than what we currently have.

Yeah… the current design of ID is not good enough.

In fact, they are not even unique! If 2 users insert a character simultaneously between ‘B’ and ‘x’, they’ll probably produce 2 CRDTs with the same ID 7.25!

Because they have the same ID, we don’t know which one should come first!

Even worse, if now someone tries to insert something between ‘b’ and ‘a’, we are totally busted! How do you find an ID between 7.25 and… 7.25?!

Well, you can’t!

Problem with our current design of CRDT

This CRDT is not good enough. A better CRDT is needed. For now, here are 3 requirements any valid CRDT (for our application) must have:

3 requirements for CRDT:

· Requirement 1: The ID must be unique (globally unique to be exact), so that there is no confusion about which one is which.

· Requirement 2: The sorted order of our CRDTs according to its ID must match exactly the order of the text on the screen. (This also implies that we must have a way to compare 2 CRDTs)

· Requirement 3: Since users can insert anywhere, with however large a number of characters they want, we must be able to generate an unlimited number of CRDTs between any given 2 CRDTs.

Ok. That’s the topic of another day. If you want us to write another article about that, please give us a clap so we know people are interested 😁. For now, let’s sum up what we’ve learned in this article:

· Synchronizing text in real-time is pretty hard!

· We need to make insertions and deletions commutative and idempotent to enable synchronous editing

· How to do that perfectly is still a mystery

That’s it for this article. Please leave a comment below if you have any questions/feedback. Again, if you want us to write the next article to unlock this ‘mystery’, please give us a clap, that will really boost our motivation 🤗🤗🤗.

Thank you all 😄