Wednesday, March 30, 2011

Slouching towards Multi-Master Conflict Resolution

This title is not nearly as snappy as Yeats' line from "The Second Coming," but it will have to do.  Conflict resolution has been a holy grail for us on Tungsten--we had people asking for it when MySQL was still MySQL AB, lo these many years ago.   Well, it's finally starting to happen after about a year of work.  

Let's start with a simple multi-master configuration.  To replicate bi-directionally between two masters, you typically run Tungsten replicator on each master with two replication services on each master.  The first local service reads the master log.  The second remote service is a slave of the other master.  It looks like the following picture:

One of the big problems in multi-master replication is to avoid loops.  Let's say you update something in the SJC master.  The transaction replicates to NYC and appears in the log.  Then it wants to replicate back to SJC and appear in the log there.  If we don't do anything, the poor transaction will loop forever.

Tungsten solves this problem using a filter named BidiRemoteSlaveFilter that runs on slave pipelines  It has a simple job, which is to identify where transactions originated and keep local transactions that are returning from the other master from being applied again.  We use a variety of tricks to "tag" SQL in a way that allows us to deduce the origin--the most common are comments added to SQL statements or specially formatted row updates that we add to user transactions.  As long as you set things up properly and don't break some simple rules you can now replicate bi-directionally between 2 or more masters.

This brings us to conflict resolution.  Conflict resolution prevents incompatible transactions from colliding with each other.  The BidiRemoteSlaveFilter does a simple form of conflict resolution by preventing transactions from the local service from looping back and being applied again.  However, it's a very short hop to filters that that address application conflicts.

Here's a simple example that is next on my list to implement.  It is not unusual to split customers in multi-tenant applications across sites so that they have active updates on only one site and backup copies on the others.  You could imagine a filter that works off a simple file like the following:
This tells the filter that transactions with shard ID sharks and athletics are allowed on the sjc master from local application.  However, if the nyc master updates these, we will reject the updates when the nyc remote service tries to apply them and generate an error message in the log, or perhaps put them in a special log file for later inspection.  You could even generate a dummy update on the local master that would result in the sjc data being sent back over to correct the nyc DBMS information via replication.

What we have just done is implemented conflict resolution for a system-of-record approach to multi-site data management.   There are many types of conflicts as well as ways to manage them.  Tungsten Replicator filters have a lot of potential to implement other schemes as well.  Filters are pluggable, so there is a convenient escape hatch if you need to do specialized rules of your own.  Meanwhile, there is plenty of scope for Tungsten development to provide useful conflict resolution mechanisms.

The Yeats poem I referred to at the beginning of the article is one of my all-time favorites.  Here are the last two lines:
And what rough beast, its hour come round at last,
Slouches towards Bethlehem to be born?
This could certainly describe a lot of software projects.   However, Tungsten is not like that at all.  We Tungsten engineers wear white lab jackets with pocket protectors and have shiny clipboards to take notes on our breakthroughs.  We rarely slouch.

P.s. Speaking of Tungsten engineers my colleague Giuseppe Maxia and I will be doing a webinar on multi-master replication on Thursday March 31st.  It will be mostly technical with only a small amount of marketing fluff.  As usual Giuseppe has cooked up a cool demo.  Sign up at if you would like to find out more.


Baron said...

I saw both you and Giuseppe this week. No slouch detected. Sorry I didn't stop you to say hi, after all that!

Robert Hodges said...

Hi Baron! Thanks for the greetings and scientific confirmation of our posture. I was afraid somebody would think it was just marketing. Excellent Ignite talk, BTW.

Scaling Databases Using Commodity Hardware and Shared-Nothing Design