1

I need to synchronize tables of data between two different systems. This is a multi-master setup; data can get changed in either system. After a synchronization runs I'd like the data in each table to be the same.

I'm having a tough time coming up with an algorithm for sending only incremental changes from one system to another. Here's my current algorithm:

  1. In the local system make a list of the ids of the records that have changed since the last run.
  2. Import all changed records from the remote system, and update the "modified" timestamp of each record locally.
  3. Export to the remote system the list of records with the ids from step 1.

This works, but gets cumbersome when there are potentially millions of records to exchange. The list of ids can't be stored in memory without possible out-of-memory errors.

The reason I have to make the list of ids is that if I run an import first, the "modified" timestamp column will get updated locally, and then I'll lose the knowledge of which records have been changed since the last run and need to be exported.

Another way to do it would be to mark all of the records that need to be exported before the run starts. The problem with that is that it means setting a flag in millions of records, which is going to be very slow. (I'm using Postgres, which does not support in-place updates.)

Yet another way to do it would be to refrain from updating the modified timestamp when you do the import in step #2. The problem there is that I really need that timestamp updated if the record has changed, because I am synchronizing the local table against potentially more than one remote system.

Obviously, the best way to do this would be to use some kind of Change Data Capture stream that produces a log of the changes each table has seen, but that is not available in this situation.

(Let's leave aside conflict resolution for the moment. For each column in the table I can designate the "owner" of the column, either system A or system B, so that the owner can always overwrite the column without a conflict.)

Question: is there a better algorithm for this? What are the common solutions to this problem?

Update

In response to the comments: I'm synchronizing a local CRM, with a list of contacts, with various external apps that have APIs. For example, my local list of sales leads needs to get exported to Mailchimp, and any leads that come in through Mailchimp (say, through a web form) need to get added back to the CRM. Incremental changes in the CRM (say, a change to name, address, or email) would need to get pushed to Mailchimp, and incremental email status changes (say, bounces or unsubscribes) would need to get sync'd back to the CRM.

Also -- the CRM will have to get sync'd with more than one external service. Contacts will have to get sent to Facebook for advertising, or potentially some call center app.

I can make the simplifying assumption that certain apps "own" certain fields. For example, the CRM can own name and address, and Mailchimp can own email_unsubscribed or email_bounced. Field-level conflicts can be resolved by letting the owning app get its way.

Yes, I understand that multi-master setups are difficult, but for this application it's really not optional.

21
  • What's your research on Event Sourcing and CQRS, and how/whether would those fit into your design? May 26, 2021 at 0:52
  • 2
    "multi-master setup" - well there's your problem. From what you describe, rather than the whole table having one machine as master, it is the rows themselves that have a master (an "owner"), and each machine's local table consists firstly of the rows over which it is master, and secondly the rows for which it provides a local cache for a variety of other masters, and which all has an eventual-consistency style setup. Have you considered whether this reflects a fundamental design error? The chances of this kind of design operating reliably are effectively zero.
    – Steve
    May 26, 2021 at 8:04
  • @Steve well, database clusters do exactly this. Though, i agree that its extremly hard to get right. And why reinvent the wheel?
    – marstato
    May 26, 2021 at 9:30
  • 1
    @marstato, and NASA goes exactly to the moon. It's not just the fiendish subtlety of the synchronisation algorithm, it's the ability of developers and users to reason about how the machine works, in order that they can control it sensibly to achieve their purpose. Explaining to a user that edits on some records are guaranteed to apply (when it's a local master), whereas other edits can be pre-empted later (where an edit on a slave is overwritten by an earlier edit on the master, which hadn't propagated to the slave)... (1/2)
    – Steve
    May 26, 2021 at 18:44
  • 1
    @marstato, is such sharding employing eventual consistency and resolving conflicts, or does it just hold the user waiting whilst a so-called "distributed transaction" is concluded (and which requires the shard-master to be online and fully available, or else the transaction would abort)? In the latter case, even thought it would seem there are multiple machines involved, they are actually yoked into one fully-cooperative system (and everything is designed as such), and it is the assembled system as a whole which is the only real master.
    – Steve
    May 27, 2021 at 13:20

1 Answer 1

1

I'm working on a similar problem with only 2 data stores. I believe for each distinct master data store you need (# master stores - 1) intermediary stores to track "last known state" for consistency checks. In my case this means a single additional store.

The sync process then runs an export from A to B and an import from B to A. Order shouldn't matter I don't think, but there may be edge cases where doing one before the other would result in slightly different results. During the sync it utilizes the intermediary store to determine if properties were changed in A or B or both.

Determining individual property changes per record looks something like:

finalValue = sourceValue != intermediaryValue && intermediaryValue == targetValue ? sourceValue : targetValue

Update Target with finalValue
Update Intermediary Store with same updates made to target

So far that's how I'm approaching the problem. It assumes the "target wins" in cases where both sides have changed. So you could handle that differently depending which source you consider the winner in conflicts. Or throw an error for manual resolution. Or handle different properties conditionally depending on the source.

EDIT:

    public static string GetMediatedValue(string sourceValue,
string intermediaryValue,
string targetValue,
SyncConflictResolution resolution = SyncConflictResolution.SourceWins)
    {
        string finalTargetValue;

        if (sourceValue == intermediaryValue)
        {
            // no change or change in target
            finalTargetValue = targetValue;
        }
        else if (intermediaryValue == targetValue)
        {
            // no change or change in source
            finalTargetValue = sourceValue;
        }
        else
        {
            // change in both
            switch (resolution)
            {
                case SyncConflictResolution.SourceWins:
                    finalTargetValue = sourceValue;
                    break;
                case SyncConflictResolution.TargetWins:
                    finalTargetValue = targetValue;
                    break;
                default:
                    throw new Exception($"Unable to resolve sync conflict: Source: {sourceValue} - Target: {targetValue}");
            }
        }


        return finalTargetValue;
    }

Example usage:

var source = GetSourceValue(id);
var target = GetTargetValue(otherId);
var intermediary = GetIntermediaryValue(id, otherId);// or whatever
var finalValue = GetMediatedValue(source, intermediary, target);

if(finalValue != source)
{
     // update source
}

if(finalValue != target)
{
     // update target
}
3
  • I'm not seeing the benefit of the intermediate table. Wouldn't it be identical to A at all times?
    – ccleve
    Aug 25, 2021 at 17:18
  • 1
    If you want to support changes in both A and B, the intermediate table captures a snapshot of the last known values. Then if property X is changed in both A and B within the same window, the intermediate table allows you to determine this and choose the outcome (A wins or B wins, or throw error for manual resolution, etc.) Without the intermediate table you have no way of knowing if property X is being overwritten by whichever sync runs "first", rather than the more deterministic "A wins/B wins" style resolution.
    – Chad
    Aug 26, 2021 at 16:40
  • @Chad could you please elaborate on this solution? Perhaps a diagram for the flow or maybe you have source code? Sounds interesting, but I can't fully understand the picture Nov 5, 2021 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.