Underlying Philosophy

CRDT is a merge of two models, one designed with mobile computing in mind while the other was thought to fix the shortcoming of the Operational Transformation approaches for collaborative editing (broadly by removing the hard work on the transformation part and replacing it by hard work on the operation part, but we'll come back to that later).

Research papers are typically focused on the collaborative editing context, the point being to improve over Operational Transformation previous approach.

“CRDT algorithms initially designed for peer-to-peer asynchronous collaboration are suitable for real-time collaboration. Moreover, they outperform some representative operational transformation approaches that were well established for real-time collaboration in terms of local generation time and remote integration time.”

Evaluating CRDTs for Real-time Document Editing by Mehdi Ahmed-Nacer, Claudia-Lavinia Ignat, G´erald Oster, Hyun-Gul Roh, Pascal Urso

But if you ask a seasoned developper like Vaugh Vernon why CRDT are important, you’re more likely to read something like this:

“Think of having a Shopping Cart persisted by a multi-node replicated store, and then having one of the nodes become unavailable. If you have at least 3 nodes in the store, which of the remaining nodes contains the most recent version of a given user’s Shopping Cart? You need to display the most recent one. How would you know? What can you do to resolve this problem when the user is just ready to check out and pay?”

As we can see we’re far away from collaborative editing here. What matters here instead is that CRDT solves a popular need of our times: guaranteeing data availability even when the network is partitioned, while still providing eventual consistency. That is the certainty that down the line, the same data will be replicated on every node of the network.

Indeed we’ll see CRDT used in chat that need distributed hosting (League of Legense), massively used betting system (Bet 365) or any other service that has to deal with large amount of users like Soundcloud. Peter Bourgon who is one of the key developers there sums it up nicely from a developer perspective :

“CRDTs are this thing that I would argue came out of the CAP theorem which was first published in 1999 or 2000; they are a distributed data structure similar to a linked list, or it can also include maps or sets and I guess I would argue they were discovered rather than invented, but the CRDTs are really a collection of properties, properties of operations and if your data type or data structure abides by these properties then interesting things fall out of it.[...]you can picture a network of connected devices all with their own view or portal on the world as indeed a large scale CRDT [...] the key win for CRDT is that you get to ignore all the problems that are inherent in distributed systems, so network failures, message duplication, out of order arrival, this sort of things.”

The principle behind CRDT:

Raphaël Dingé CRDT introduction @3DS campus

CRDT considers that transforming operation (as in Operational Transformation) is too complex and establishes a new model to handle RTC. In this model, objects can’t be destroyed but disabled. Moreover operations that impact the model must follow 3 constraints: they can be applied in any order (commutative and associative) and as many times as needed (idempotent, meaning that you can apply an operation twice and still have the same result as if you apply it once).

As a result conflicts are then impossible: if you move an object that has just been “destroyed”, you’ll in fact move a “hidden” object. But this implies in turn that your model will be monotonically growing. You probably can immediately spot some of the trade off involved: CRDTs properties means that not all operations, even some classic ones have gone through a CRDT compliant redesign yet, and that a lot of them simply will never be able to work in a way that’s always commutative, associative and idempotent.

Now a clarification: C in CRDT can mean different things as explained at RICON West by Jeremy ONG. C means:

• Convergent Replicated Data Type is for State Based RDTs
• Commutative Replicated Data Type is for Operation Based RDTs.

In the former kind of CRDT, updates contain the full object state (or in optimized version, the difference with previous state). In the later, the updates contain the operation to be applied to the object. Depending of the typical size of an object and amount of operation, one is more suited than the other. In the word of Nezih Yigitbasi

“CRDTs are addressing an interesting and a fundamental problem in distributed systems, but they have some important limitations which Shapiro et al. acknowledged: “Since, by design, a CRDT does not use consensus, the approach has strong limitations; nonetheless, some interesting and non-trivial CRDTs are known to exist.”. The limitation is CRDTs address only a part of the problem space as not all of the possible update operations are commutative, and so not all problems can be cast to CRDTs. On the other hand, for some types of applications CRDTs can definitely be useful as they provide a nice abstraction to implement replicated distributed systems while at the same time giving theoretical consistency guarantees.”

A few CRDT libraries and Framewok exemples

League of Legend chat is powered by Riak

• Yjs handles arbitrary data types (RichText, Array, Hash Maps, .. extendable). It supports offlin and P2P communication protocols.
• SwarmJS Client server shared database with offline support.
• Riak KV, a noSQL database supporting CRDT data types with clients in many languages

CRDT in production

bet365 mobile app

There are plenty of large scale example of CRDT implementation that are not related to real time collaborative editing:

• League of Legends chat deals with 11K messages per second.
• Bet365 betting system uses CRDT to achieve scalability and performance whilst maintaining data correctness
• Tom tom driving application (here detailed at Lambda Days 2016 by Dmitry Ivanov & Nami Naserazad)
• Soundcloud, as seen above.

… and many more, but here we are focused on Collaborative Editing and on that front the situation is very different.

We’ve found a demo of a CRDT based text editor

http://demo-ritzy.rhcloud.com/

Demo of CRDT based text editor

There are a few more ongoing project on github, but it seems to be it. No commercial collaborative real time editor made with CRDT whatsoever (if we’re mistaken, please comment! )

The Trend

Still CRDT scene is very active with a lot of news about libraries, workshops, blog posts happening on a weekly basis. So why is CRDT for collaborative editing close to nonexistent? While it’s any one guess we can make two observations:

• CRDT, like Operational Transformation, has been designed originally with text editing in mind. Text editing is efficiently covered by a lot of OT based .js libraries. With Apple joining Microsoft, Dropbox, Google and many more, nearly all text editors are already collaborative editing ready. While CRDT is supposed to bring some advantages in term of performances, it may not be value enough to justify a complete reworking. Of course, it may be that some of the above actually use CRDT and we don’t know.
• CRDT on the other hand is not better suited than OT to solve the need of UI intensive editing applications, such as the one used in CAD, PLM, BIM, Simulation, Video, Audio, Game Engines etc. Those, especially the happy few leading the market, deal with level of complexities that require a lot of different operations to be performed. In CRDT those imply not only an amount of R&D that’s generally not compatible with any agile approach:  it’s actually very likely to be a dead end, as not all operations are prone to be made in a way that validate the needed properties to be CRDT compliant.

Bottomline

If you’re in for now classic collaborative editing of text with nothing more than what has become the standard in 2016, you already have plenty of options with OT. The only real reasons to opt to CRDT instead would be scalability but how many users can edit one document simultaneously in a workable way to start with ?

If your collaborative editor isn’t text related, keep in mind that whether you’re using an Operational Transformation or CRDT approach your code is likely to become exponentially more complex while your amount of features rises linearly - or that you can even face impossibilities in development. If that’s your situation we’re glad to be able to direct you to our Flip framework, which relies on a completely different approach. Not only is Flip designed in a way that doesn’t need you to rethink your development habits, it brings flexibility, performances, undo redo, versioning, copy paste to the table and has even been successfully implemented on industry landmark apps with decades of legacy code. Learn more about it here or directly