As businesses face the reality of the world being a global village, they are increasingly looking at multiple data centers for high availability, expanded reach and the best possible user experience. The re-imagining of their applications is fueling the growing demand for distributed active-active, multi-master databases. While most popular databases support multi-master deployment, different databases employ different techniques. 

Approaches to multi-master support include two-phase commit, quorum-based multi-master, LWW (last writer wins conflict resolution), MVCC (multi-version concurrency control), merge replication, Conflict-free Replicated Data Type (CRDT) -based consistency, and so on. Per the CAP theorem, two-phase commit and quorum-based multi-master models deliver strong consistency. However, systems that rely on these techniques are typically not available during network partitions. Additionally, these techniques are chatty and add significant latency to database operations. Other techniques, namely LWW, MVCC, merge replication and CRDTs mentioned above, deliver eventual consistency, offering read and write access with local latency and remaining available during network partitions.

In this article, we examine the basic differences between two multi-master data replication techniques based on eventual consistency -- 1.Merge Replication, a traditional technique for delivering eventual consistency by relational databases, and 2.CRDT, a more recent breakthrough technique that builds the foundations for intelligent conflict resolution with strong eventual consistency and causal consistency. CRDT databases provide a mathematically proven model for resolving conflicts, ensuring all datasets converge to the same correct state. 

Merge Replication

Merge replication is a common technique employed by relational databases. This technique allows you to deploy a distributed database solution in which each database server has its own copy of data. An external agent then collects changes to the local copies and merges them in an effort to force all of the database servers to contain the same copy of data.

How it works

The topology of typical merge replication has database servers in multiple regions and follows the publisher/subscriber model. One of the servers is identified as a primary server or a publisher, while the rest of the servers are subscribers. In a normal flow, all changes to the publisher trickle down to the subscribers. However, in merge replication, subscribers can make database changes too, and merge all their local changes with the publisher. These changes will eventually go to all subscriber servers. Assuming no conflict occurs during the merge, all changes made to either the publisher or the subscribers will eventually converge as the same copy.

Figure. 1 Sample Merge Replication Topology at Sites A, B, C

The “Merge Agent” is an external service responsible for gathering all the changes to the local database servers and merging them into a single data set. When a conflict occurs, the merge agent follows a predefined set of rules to resolve the conflict. If the default conflict resolution technique doesn’t agree with your solution, then you can override it by having your own “conflict resolver.” However, this flexibility comes at the cost of performance and latency. It’s also possible that your custom conflict resolver will break the consistency between your publisher and subscriber.

Conflict resolution is the core piece of merge replication, which follows a hierarchical model. Each database server is assigned a priority number, with the publisher as the highest priority. If two database servers modify the same copy of the data, then the merge agent decides who wins and who loses depending on priority numbers. The agent maintains a separate conflicts table that records all the loser changes, and the administrator can resolve conflicts manually.

CRDT-based Replication

In a CRDT-based distributed database platform, the topology may include two or more database nodes in every region, with a local copy of data in each region. CRDT rules force any changes to the local data to be merged across all other regions, making them strongly eventually consistent. Developers build their apps to adhere to preset data type rules, and conflict resolution techniques in CRDT databases are optimized for specific data types, so they are many times faster than merge replication. Redis Enterprise and Azure Cosmos DB support CRDT-based multi-master distributed databases, but only Redis Enterprise supports complex data types in this topology.

Figure 2. Sample CRDT-based Redis Enterprise Topology at Sites A, B, C

How it works

In addition to exchanging data, the CRDT technique also exchanges operations, including their order and causality. Therefore, merge techniques don’t just merge data, they follow preset mathematical rules to merge operations on the data per data type. There’s no hierarchy built into the system (as in merge replication), so all nodes have the same priority. CRDT databases also don’t require quorum-based consensus between regions. Explore Redis Enterprise’s technology site to learn how CRDTs work in more detail.

Comparing Merge Replication and CRDT-based Distributed Databases

Merge replication and CRDT are two very different techniques for data replication and conflict resolution- their differences are summarized in the table below:

Example: How Merge Replication and CRDT-based conflict resolution handle counters

In this example, we use a social media app, which collects the number of likes on an image from the three different data centers where its database servers are deployed. Let’s see how the counter works in a distributed database that supports merge replication as compared with CRDT-based Redis Enterprise.

Merge replication

As shown in the picture below, site A updates the counter to 30, B to 40 and C to 50. The sites A, B and C are assigned priorities of 100, 75 and 50.

Figure 3. Sample Counter Example using Merge Replication

When the merge agent receives updates from A, B and C, it detects conflict and calls its conflict resolver to resolve the conflict. If you go by the default conflict resolver, the data with the highest priority is chosen as the winner and data from the other two nodes goes to the conflicts table. As you may see, the default conflict resolver results in a faulty implementation of the counter, so you’d need to implement your own conflict resolver to override the default method.

CRDT-based conflict resolution

Using Redis Enterprise, the counter is a CRDT and has built-in logic to merge changes. As shown below, site A increments the counter by 30, B by 40 and C by 50.

Figure 4. Sample Counter Example using CRDT

Because of the CRDT rules, each node updates the other node with the operation it performed on the counter, and they all converge at the final value of 120.

Use Cases

Merge Replication

Merge replication has been in the market for many years. It has evolved as a standard technique to replicate data in distributed relational databases. Some of the popular use cases for merge replication include:

• Disaster recovery: Merge replication facilitates business continuity to the applications using relational database in case of network disconnects or natural disasters.
• Geo-distributed data warehousing: Solutions that go through timely data synchronization use this technique for conflict resolution.
• Enable seamless growth: When enterprises add more applications to their portfolio, the database management solutions face the pressure of supporting more operations per second. With merge replication, the enterprises can overcome the physical limitations by replicating the data and maintaining a copy closer to the application.

CRDT-based distributed databases

Thanks to their support for local latency queries and transactions, CRDT-based distributed databases power highly engaging applications. Some of their popular use cases fall under:

• Global counters for voting, leaderboards and metering solutions: CRDT counters are a special data type that only support incrementing or decrementing the associated values. In other words, this data type doesn’t let you set a value. Distributed databases with CRDT based counters, are simple to implement and all views will converge to the same final value, with the datatype automatically handling conflict through a rules-based methodology to achieve the correct final value.
• Session stores for geographically distributed applications: CRDTs allow applications to switch seamlessly between datacenters. For example, suppose you are shopping on an e-commerce site and adding items to the shopping cart. If the application’s local database fails, it can switch to one of the remote databases with all your items in the shopping cart intact. You can continue to add items, and have it fail back without them being overwritten, because CRDTs correctly handle updates in every region.
• Data consolidation across microservices: In a microservices architecture, each microservice has its own local copy of the database. Suppose multiple microservices share the same data, you could either synchronize the data at the application layer, or let the database synchronize the data for you. The latter technique ensures data integrity between microservices. CRDT-based databases make the data consolidation fast, simple, easy and efficient.
• Collaboration: The ability to deliver causal consistency makes CRDT-based database ideal for developing collaboration, gaming, and social applications. Causal consistency promises to merge the data in the right order at all times, thus giving a consistent view to all the collaborators. As an example, chat applications can ensure that messages get ordered correctly to minimize misunderstandings!

Conclusion

In conclusion, merge replication is a legacy technique that comes with built-in conflict resolution for relational databases. The technique offers flexibility via supporting custom conflict resolution. However, one should take utmost care to ensure the conflict resolution does not break any rules governing data consistency. From an operational point of view, merge replication is slow in performance and the merge agent is a single point of failure.

CRDT-based conflict resolution implements mathematically proven rules to ensure consistent correct data views, without sacrificing response times. CRDTs, unlike the traditional conflict resolution methods, deliver causal consistency and strong eventual consistency in distributed databases. This technique is ideal for real-time and engaging applications that require sub-millisecond latency data access.

About the Author

Roshan Kumar is a Senior Product Manager at Redis Labs, Inc. He has extensive experience in software development and product management in the technology sector. In the past, Roshan has worked at Hewlett-Packard, and a few successful Silicon Valley startups. He holds a bachelor’s degree in Computer Science, and MBA from Santa Clara University, California, USA.