Merge Helper

Tiny conflict resolution algorithm

About

Merge helper is an implementation of gunDB's deterministic conflict resolution system, implemented as a microservice.

Merge helper does not merge for you. It tells you

• which fields should be updated
• which fields are outdated
• which fields should be deferred

leaving the rest up to you. That way, you can alert the user if their changes are being overwritten, you can add middleware that emits changefeeds, or you can add past states to a journal. The point is it gives you more control and flexibility.

The algorithm is deterministically eventually consistent. No matter what order the updates arrive in, so long as each has an author-relative timestamp, each computer will reach the exact same conclusion every time without syncing to a remote authority.

Usage

The library itself is lightweight, and can be downloaded via npm.

npm:

$ npm install merge-helper --save

Once downloaded, you can require it from your project. It exports a function.

const merge = require('merge-helper')
 
const current = {
    hello: {
        state: Date.now() - 100,
        value: 'potato',
    },
}
 
const update = {
    hello: {
        state: Date.now(),
        value: 'world!',
    },
}
 
const result = merge(current, update)
 
console.log('Result:', result)
/*
    Result: {
        updates: {
            hello: {
                state: 1467567468878,
                value: 'world!',
            },
        },
        historical: {},
        deferred: {},
    }
*/

There was a lot in that example. Let's break it down...

Current State vs Update

When a value is changed, a timestamp must be attached relative to it's author, otherwise a merge will be only as effective as Object.assign. This is the format merge helper is expecting:

{
    "hello": {
        "value": "world",
        "state": 1467567468878
    },
    "temperature": {
        "value": 78,
        "state": 1467567468123
    }
}

You pass two of those formatted objects:

• the first is the object you're merging into
• the second object is the update.

Merge helper returns an object with merge instructions. This includes the fields that need to be updated, and the fields that should be updated at a later point in time.

Let's take a look at an example:

// Our current state
const current = {
    hello: {
        value: 'world',
        state: new Date('2012').getTime(),
    },
    answer: {
        value: 42,
        state: Date.now(),
    }
}
 
// An incoming update
const update = {
    hello: {
        value: 'cool person',
        state: Date.now(),
    },
    answer: {
        value: 'message from the future',
        state: new Date('2050').getTime(),
    },
}
 
const result = merge(current, update)
 
console.log('Result:', result)
/*
    // Here's what merge helper gives us:
    Result: {
        historical: {},
 
        // Safe to merge this one.
        updates: {
            hello: {
                value: 'cool person',
                state: 1467567468878,
            }
        },
 
        // Don't merge this one yet...
        deferred: {
            // The year 2050!
            answer: 2524608000000
        }
    }
*/

If one of your values is an object, you'll need to pass it a unique ID. Since every feature of an object can change, there needs to be something constant to measure against. It can be any primitive, so long as it's consistent.

Warning: if two separate objects share a unique ID and state, no winner can be decided, so one is picked arbitrarily. If this matters in your program, make sure no two objects share a UID (a case where this wouldn't matter is Date objects, whose ID might be their timestamp. It doesn't matter which wins since they both convey the same information.)

{
    "value": { "data": true },
    "state": 1467567468878,
    "UID": "The object's unique id"
}

If an object is passed without a UID, a TypeError will be thrown.

Deferred Updates

This is a feature of HAM, gunDB's conflict resolution engine.

Your users' computer clocks are not always accurate. Some are slow, some are fast, and others are changed maliciously. Algorithms that say "the most recent update wins" are susceptible to time traveler attacks. Try setting your clock 10 years in the future, now your updates will win for the next 10 years. That's not a good thing.

Our solution is to embrace updates from the future, not by merging them, but normalizing them. If an update says it's 10 years ahead of your time, wait 10 years to merge it. This has some interesting and useful side effects, but they're beyond the scope of this section.

Important note:
Never persist deferred updates to disk. Instead, keep them volatile, keep them in memory. The further into the future an update is, the more likely it is to be malicious, and the less you want it anywhere near your database. If an update is 5 minutes into the future, it'll probably make it to your database. But as that number grows, the more volatile the update, and the less likely it is to ever merge. If real-time is a concern, you can use client-server time sync to normalize your users' clocks.

Bonus feature! If your attackers are persistent, and want to schedule millions of updates a year in the future that hit you all at once, you're using up memory, and your server is more likely to crash, losing all their malicious updates. Nobody wants their server going down, but you've just eliminated an obscure database vulnerability and moved it into DDoS territory, which has far more tooling, support, and broader application benefits.

When using client-server time sync, attackers and users are brought to a middle ground, eliminating the notion of "future". This is generally a good idea.

Support

If you have questions about merge helper, feel free to ask on our gitter channel (ask for me as @PsychoLlama).