Collaborative document edition

December 16, 2014 btellier Uncategorized, 0

This short article is the result of one of my reflexions, and the way I would attack this problem, points of attention to have and algorithms that might be usefull.

Definition of what we want to do

First of all, we have to describe the solution we want to design…

In this article, I want to describe how I would implement collaborative text edition.

We want that one, two, or more clients, connected threw internet to be able to edit at the same time the same document. We want that they see what the others are doing on the document. We want to have a normal behavior for the document.

Why text edition ? Simply because text is the simplest form of document. Once you have solved the problem of collaborative edition for text, it is quitte easy o do it for other types of documents. In fact, we want to perform “atomic” operations on a document. An atomic operation is, in the example of text edition, a text addition, a text deletion, and a cursor move. For tables, it will be the same but partitionned into cells. We have 4 other operations : columns and lines deletion or addition. Whatever these atomic operations we will perform, it will have no impact on our algorithm.

Global architecture

The first thing we have to notice is that the client have to be transmitted to other clients in an atomic order ( it means each client receive the operations in the same order ).

To do that, our clients can simply send their operations to the server, that aggregates them and send it to the clients. We now have atomic order.

One big problem…

Now, what makes collaborative edition that difficult ?

Imagine the following scenario :

Peter and Paul are working on their homeworks. It is a text document of 128 lines. Peter works on the introduction, Paul on the conclusion.

• Paul makes an operation line 10, that add one line.

• Peter types on letter ‘a’ on line 123.

• Server receive Paul operation, and broadcast it to clients. A line is added between line 10 and line 11.

• Server sends Peter operation. Line 123 is affected. But this is not the line Peter wanted to modify. Peter is not happy at all and now know that we still not have implemented collaborative edition.

Operation transformation

The idea is that Peter was not aware of Paul operation, so its operation data became outdated. The server need to detect what operations Peter was not aware of while making his request, to deduce what he has done in Peter context, and modify Peter operations in the view of the already accepted operations he was not aware of. Here, might want something like “Oh peter was not aware Paul added one line. So its operation must be applied on line 124 and not on line 123.”. We call that operation transformation.

Solution I don’t like : timestamps

I read about a solution I do not like at all.

This solutions is based on timestamps. Here are the first point I don’t like :

• Clients might not have the same hour so we have to calculate the difference of time for each client
• We are the slaves of latency : we can only have an average, but no precise measure of it
• A client can attack us ( ie have strange results on the document edition ) by simply changing his hiour on his computer…

Well, the global idea is to timestamp each operation, and given the “time to apply an operation” we can deduce who have applied which operation.

For me, given the reason above, this is a terrible idea. The problem comes from the fact we are evaluating time in an absolute manner, but having it in a relative manner would be enough. Even more, we do not need a measure of time, we only need to have know what operation were performed.

Solution I like : vectorial clock

We can use a vectorial clock. Each operation have a vectorial clock transmitted with it.

But what is a vectorial clock ? It is simply the number of operation performed by each client that we are aware of.

A vectorial clock like this :

Means : I want to perform this operation. Paul made 15 operations before me this is Peter’s 17th operation.

Having that, the server just need to find theoperations Peter was not aware of :

Hum … Oh here an operation with Paul at 16 and Peter at 16? I already accepted it. Paul score is higher that it was in Peter operation so Peter was not aware of it. Hop, as paul added one line in this operation, we need to keep that in mind to modify Peter’s request.

Hum … The previous is an operation performed by Paul… He has 15, Peter has 16. Well so Peter was aware of it. As we uses atomic order, I can stop here, I have now the all list of operations Peter was not aware of.

Very simple, no ?

And you know what is really wonderfull? You can very easily add clients ( not mentionning a client in the vectorial clock is equivalent with having a vectorial clock set to 0 for this client ), and remove clients ( having a client setted in the vectorial clock when this client is disconnected is not taken into account ; the server notifies clients upon client disconection by simply removing them from the vectorial clock ). And you know what ? By generating an UUID upon client connection to identify its entry in the vectorial clock, we can manage easily reconnection.

One other point : it might be interresting to keep a track of who knows what so that we can free memory. We can have a count of aware clients by operation. We update it upon each operation and remove operation when the number of aware client is equal to the number of client.

With this approch, we can simply implement collaborative edition. Vectorial clock and Operation transformation is for me the simplest way to do it.

Well well well and now I want to distribute it…

It’s your right… It means that clients connected on different servers might edit at the same time the same document… The property the need is atomicity ( in the distributed way ie : each server should notify its connected client of operations in the same order ).

The simplest way to do it is to rely on a middleware. I propose Kafka with topic limited at one partition. Why ? because Kafka assure us that the messages are transmitted in an atomic manner in each partition of each topic.

One document one topic.

So in this approch, each server sends received Operation on a fistr Kafka topic. A master server reads this topic, makes operation transformation on operations and sends them to a second topic. Each servers reads the second topic, and notifies clients about operations they have to perform.

To determine the master server, you can rely on Zookeeper. The document can be stored in a database to be easily retrieved for future edition.

We can identify several limits :
– does Kafka likes to have a very high number of open topic at the same time ?
– limitation due to Zookeeper : it means that only a given number of server can be added to documents by second…

We can ask ourself several questions :

• what happens upon slave server disconnection ?

Clients connected to this server are now offline and needs to reconnect to an other server.

• Upon master failure ?

We loose the pending operations. The safest way might be to close the document, accept to loose the pending opertions, and reelect a new master. Once a master is elected, we can restart document edition.

Native vs Hybrid App James at Linagora