Learn how conflict-free replicated data types can help distributed systems handle consistency challenges.
Join the DZone community and get the full member experience. This is an article about the complexity of maintaining data consistency in distributed environments. It introduces conflict-free replicated data types (CRDTs) as a way to resolve concurrent data changes. Consider a situation where there are several distributed entities that each hold a copy of the same data. Data consistency is maintained if those copies continue to match each other, even when one or more of them are updated. If a single entity updates its copy of the data, there is no dispute about the latest ‘source of truth’ for that data, but there may be temporal differences in the state of each distributed entity. Network latency will affect the rate that each peer receives updates; network or system failures mean that some peers may never receive updates. Aside from simply causing some updates to fail to reach some peers, those failures result in a data consistency challenge. For example, the distribution of some updates can fail, but others succeed; this causes consistency and ordering problems. A system design needs to accommodate such cases to ensure consistency. There are further challenges if multiple entities make independent updates concurrently to the data. Now, there isn’t necessarily a single, canonically « correct » version of any data. Updates created by one peer in one state might conflict, or not make sense, to other peers that have visibility of other updates. Strong consistency is the propagation of any update to all copies of data. In the most simple case, a series of updates to the data come from a single source, and all other entities that hold a replica of the data are guaranteed to receive those updates in the same order. When multiple copies of the data can be updated at the same time, there needs to be a way to agree upon the correct version of the data. With strong consistency, once one entity makes any updates, all other replicas are locked until they’ve been updated to the same new version. The source of truth pushes updates to all entities in the same order to keep them ‘in step’. The design constraints imposed by strong consistency are unacceptable in an increasing number of use cases. Consider realtime collaboration (as seen in online productivity tools that permit users to make concurrent edits). Every entity can potentially make and receive updates, so there is no way to ensure that each replica receives the same sequence of updates. Eventual consistency is the property where the state of the data is eventually reconciled, regardless of the order of update events that reach each replica. Replication conflict occurs when it is not clear how to reconcile changes to reach data consistency. For example, which update takes precedence? There needs to be a common agreement on how to resolve the conflicts. Consider the simple case where Alice and Bob are using a collaborative coloring application. Both select the same area of the image to fill with color: Alice chooses to fill it with yellow; Bob fills it with blue. Should the area be colored yellow or blue (or green: a combination of both updates)? The most common solution is to have a single arbitration policy that resolves such conflicts using a set of rules, like the « last write wins, » which uses the timestamp of each update to apply changes in the order in which they occurred. In the above case, if Bob made his edits after Alice, they’ll trump hers, and the color of the section stays blue for Bob and changes to blue for Alice, or vice versa if Alice made the last edit. When timestamps are equivalent and cannot be used to resolve the conflicts, the resolution policy could be a rule such as, « Which account has the lowest ID number? » or, « Which username comes first in the alphabet? », resulting in one update taking precedence. The policy can be somewhat arbitrary as long as it is applied consistently by all peers.
