Eventually Consistent: How to Make a Mobile-First Distributed System

For a long time, no one but backend engineers had much to say (or much reason to care) about the pains of building distributed systems. Building backends for thin web clients or highly available desktops, they could focus on a fairly narrow problem space, but they would still confront the reality of the CAP theorem: your system can be consistent, available, or partition-tolerant, and you can only pick two. These engineers chose consistency and partition-tolerance — we call it the CP system. Clients receive the most recent write (the system is consistent), and messages sent across the network can drop without taking down the system (it’s partition tolerant).

Sometime in the recent past, however, people really started using smartphones, and the “thin client” became pretty thick. It had to maintain state and persist data, even as it went on- and offline due to connectivity problems. Companies started taking advantage of the fact that nearly everyone has a powerful computer in their pocket, and we all began to expect a lot from our phones. And our phones, in turn, expected a lot from the servers and networks they’re connected to. Consistency’s promise of the most recent data falls flat when our smartphones may be unable to send the most recent data due to poor signal.

A lot of the pain of building CP systems in this new mobile world is shouldered by our backend engineers, and their struggles contribute to the ever increasing cost of mobile development. But it doesn’t have to be this way. We can revisit how we build distributed systems. And by changing our model of consistency, we may be able to save our apps.

In this article, we’ll discuss popular approaches to data consistency in a smartphone world, explain the AP system alternative that we’ve developed, and we’ll finish by showing how we overcame core problems in conflict resolution to create the Realm Mobile Platform.

Consistency in Distributed Systems

Before we delve too deep into how the Realm Mobile Platform works, it’s worth breaking out how people ensure consistency today. Many distributed systems are modeled on the semantics of a key-value store, where users store records or “documents” associated with a particular key, and if multiple users update the same record at the same time, there is a conflict that must be resolved. Depending on the record type, the conflict could be resolved by simply letting one user’s data overwrite the other (Redis), cancelling one user’s transaction (RDBMSes), or by notifying the users that a conflict has occurred and let them choose a course of action (Dropbox).

All of these systems manage consistency by granting exclusive, fully serialized write access to the master record, which implies that other writers may have to wait to gain access, or ultimately abort the operation. Various techniques are used to reduce the impact of unavailability and allow concurrent writes, but ultimately a gatekeeper must exist somewhere in the system to ensure consistency, and you’re likely to still confront unpredictable tradeoffs in the form of read phenomena.

For example, in an app using a relational database, the app must be prepared to handle the fact that certain transactions can fail, or deliberately design their schema with fewer invariants and looser integrity in mind to prevent failures resulting from integrity check. In schemaless databases, there is no guarantee of integrity across records, so the application using the database must be written on the assumption that the high-level data model may become inconsistent, perhaps in unexpected ways. In both cases, the result is that the application logic must be littered with error handling code to handle potential lack of integrity or invariant failures.

Failure handling, and especially the insufficiency thereof, is a notorious source of problems in software development, and in a mobile environment with spontaneous connectivity this is even more true. We wanted to make a world where we didn’t have to think about it anymore.

Moving Towards Automatic Conflict Resolution

Overcoming these limitations requires a radical departure from the status quo of the CP system. In a centralized database system with good connectivity this makes sense, but in a mobile world where the best availability is still bounded by limited connectivity, the results are not as impressive.

As a thought experiment, let’s examine the properties of a system that selects availability and partition tolerance over consistency (called an AP system, for short). Availability means that writes never fail, but the data written by a write transaction may not be available to all readers at the point when the write is committed (which is what we’d expect by giving up consistency). Obviously, the data must eventually become available to readers for a database to be useful in the first place, so instead of consistency, our new distributed system has strong eventual consistency. It’s the same sort of tradeoff that CP systems make — they need to at least be eventually available, too, even though they don’t guarantee availability.

These choices have some interesting side-effects. If a participant can write to the database without coordinating with other participants, the system must also be able to achieve integrity without active cooperation from writers, as the originating writer may simply no longer be reachable at the point in time when the data is seen by other participants. The traditional ways to handle conflicts break down: write transactions cannot be aborted, because that would break the promise of availability, and they may have already happened while the system was “partitioned” (the writer was offline while writing).

The challenge is to ensure that consistency is eventual; i.e. that every participant converges on the same idea of what’s in the database.

For document-based key-value databases that only provide weak integrity guarantees, a popular strategy is last writer wins, where a conflict between two writers updating the same document is always resolved by picking the one that came last, at the risk of inconsistency between documents. This is often acceptable in applications with weak data models, but quickly breaks down when stronger models are needed. For example, the application logic may rely on a schema property of the data model such as the presence of particular fields, uniqueness of certain field values, or update objects in other ways than overwriting the entire document, for instance by making fine-grained edits to a text field or incrementing a counter.

The problem of eventual consistency can be solved with a particular flavor of Conflict-free Replicated Data Types, where participants exchange logs of operations they have carried out (CmRDTs). In a partition-tolerant system with strong eventual consistency, it must be possible to apply these logs in any order and still have all participants arrive at the same result (they must be commutative).

Luckily for us, there is an old technique in the literature that can help us model complex data model semantics while retaining commutativity of operations: the operational transformation. The general idea is that as participants receive operation logs from other participants, they reconcile the changes with the changes that have happened locally and rewrite the incoming operation log in a way that guarantees that when both participants apply the operation log to their local state, the state will end up the same on both ends, and no more conflicts exist.

Here lies an important difference between traditional CP systems, where there is a central system that makes a decision about how to resolve a conflict: all participants must be able to resolve any conflicts in isolation, and still arrive at the same result. This makes it a little harder to get features such as user-driven conflict resolution (user interaction would be required not just once but for each client, and the system would have to rely on the user of each client resolving the conflict in exactly the same way), but on the other hand the application developer gets a stronger data model that is much easier to work with under questionable connectivity conditions.

Operational Transformation with the Realm Mobile Platform

Realm Mobile Platform uses operational transformation to ensure that all mobile clients subscribed to a Realm file eventually agree on the contents, each being able to make modifications while the network is down or unstable. Several conflict-free replicated data types are provided as part of Realm, including objects, lists, counters – and the normal referential integrity guarantees are still maintained. And being strongly eventually consistent means the Realm Mobile Platform can be an AP system: it is always available, and it is partition-tolerant.

The Realm Mobile Platform fits the shape of the world we’re all building today: one where more and more devices are connected together in myriad ways. It gives you what you need as a mobile developer in terms of workflow and performance, and then it makes sure that you’re building a system that won’t make undue assumptions about how your users will work.

These tradeoffs in design manifest themselves in ways that users notice. Instead of handcuffing an app whenever a constant connection can’t be maintained, you can now easily build offline features. And rather than confronting your users with dialog boxes to adjudicate each conflict (while also spending countless hours of development to try to avoid their reaching conflicts in the first place), conflicts automatically and seamlessly resolve.

Today, the Realm Mobile Platform has reached 1.0, so you can start building with it right away. We recommend you start with our Developer Edition to see exactly how conflict resolution works — especially when you throw some offline states in there. Just download the bundle, run the Tasks demo app, and start thinking of what you’ll make on the Realm Mobile Platform.