Merging Changes

One of the challenges when syncing objects is merging changes. The ZeroDark framework comes with a set of tools to make this surprisingly easy.

 

Motivation

Merge conflicts happen. If you've ever used git before, you know it well.

Imagine that Alice & Bob are collaborating on a project. They both start with the same node. And they both make separate changes to that node:

   (a)     <= original version
   / \
(b1) (b2)  <= but now: Alice is at 'b1', Bob is at 'b2'

Both Alice & Bob will attempt to upload their changes to the server. Let's say that Alice wins this race. Meaning that Bob's request will get rejected with a conflict error.

There are 2 options to resolve the conflict:

• Bob's device can discard his changes, OR
• Bob's device can merge his changes with the changes made by Alice

If we can merge Bob's changes, then the app will work more smoothly and create a better user experience:

   (a)       <= original version
   / \
(b1) (b2)    <= but now: Alice is at 'b1', Bob is at 'b2'
 | \   |
 |   (b1&b2) <= Bob downloads 'b1', and merges it with 'b2'
 |  /
(c)          <= Bob pushes the merged version 'c' to the cloud

 

History

Solving a merge conflict requires knowing what was changed. Just as this is true with git, so is it true with your data model.

Consider the simple case of syncing a humble dictionary. Say we're notified of a conflict, and this is all we know:

{
  "local version": { // Bob's version which is in conflict
    "size": "30.5",
    "widescreen": "true"
  },
  "remote version": { // Alice's version & current cloud value
    "size": "30",
    "hdmi inputs": "2"
  }
}

What should the merged value be?

If we use only the above information, we're unable to make an informed decision:

• who changed the size property? local? remote? both? who wins?
• was widescreen deleted by remote? or was it added locally?
• was hdmi inputs added by remote? or was it deleted locally?

The solution requires only knowing what changes were made on the local device:

{
  "local version": { // Bob's version which is in conflict
    "size": "30.5",
    "widescreen": "true"
  },
  "remote version": { // Alice's version & current cloud value
    "size": "30",
    "hdmi inputs": "2"
  },
  "local changeset": { // Bob's changes since last successful push
    "size": {
      "type": "changed", // Bob changed this property
      "previous": "30"   // and the original value was "30"
    },
    "widescreen": {
      "type": "added" // Bob added this property
    }
  }
}

With this information in hand, the merge becomes obvious:

• the size property was changed locally, and was not changed by remote. Local wins
• the widescreen property was added locally
• the hdmi inputs property was added by remote

{
  "merged version": {
    "size": "30.5",
    "widescreen": "true",
    "hdmi inputs": "2"
  }
}

 

Tracking Changes

We recommend you use the ZDCSyncable open-source framework. It's a Swift project that automatically tracks changes made to your data model, and supports performing merges too.

Important: You do NOT have to use ZDCSyncable. You can also build your own system, or use an alternative open-source project. The choice is completely up to you.

If you choose to use ZDCSyncable, here's how easy it is to use:

import ZDCSyncable

struct Person: ZDCSyncable { // Just add ZDCSyncable protocol

  @Syncable var name: String // Add @Syncable property wrappers.
  @Syncable var age: Int = 1 // And that's it.
}

// And now you get:
// - change tracking
// - undo & redo support

var person = Person(name: "alice")
// ^ starting point

person.name = "bob"
person.age = 2

let changeset = person.changeset() // changes since starting point
do {
  let redo = try person.undo(changeset!) // revert to starting point

  // Current state:
  // person.name == "alice"
  // person.age == 1

  let _ = try person.undo(redo) // redo == (undo an undo)

  // Current state:
  // person.name == "bob"
  // person.age == 2

} catch _ {}

ZDCSyncable also supports classes:

import ZDCSyncable

class Animal: ZDCRecord { // <- Just extend ZDCRecord

  @Syncable var species: String // Add @Syncable property wrappers.
  @Syncable var age: Int        // And that's it.
}

The @Syncable property wrappers work for primitive types.

And the framework comes with additional solutions for replacing collection types:

• ZDCArray
• ZDCDictionary
• ZDCOrderedDictionary
• ZDCSet
• ZDCOrderedSet

These collections types mirror the API of their native Swift counterparts. And they're all implemented as structs, so you get the same value semantics you're used to.

import ZDCSyncable

struct Television: ZDCSyncable { // Add ZDCSyncable protocol

  @Syncable var brand: String // Add @Syncable property wrapper.

  // Or use syncable collection:
  var specs = ZDCDictionary<String, String>()

  // ZDCDictionary has almost the exact same API as Swift's Dictionary.
  // And ZDCDictionary is a struct, so you get the same value semantics.
}

var tv = Television(brand: "Samsung")
tv.specs["size"] = "30"
tv.clearChangeTracking() // set starting point

tv.brand = "Sony"
tv.specs["size"] = "40"
tv.specs["widescreen"] = "true"

let changeset = tv.changeset() // changes since starting point
do {
  let redo = try tv.undo(changeset!) // revert to starting point

  // Current state:
  // tv.brand == "Samsung"
  // tv.specs["size"] == "30"
  // tv.specs["widescreen"] = nil

  let _ = try tv.undo(redo) // redo == (undo an undo)

  // Current state:
  // tv.brand == "Sony"
  // tv.specs["size"] == "40"
  // tv.specs["widescreen"] = "true"

} catch _ {}

 

Storing changes

Once you're able to create a changeset, the goal is to store the changeset persistently until the node has been successfully pushed to the cloud. Once uploaded, we're free to discard the changeset.

The ZeroDark framework provides exactly this changeset storage for you. It's integrated with the API you use to push changes to the cloud:

cloudTransaction.queueDataUpload(forNodeID: node.uuid, withChangeset: changeset)

ZeroDark stores the changeset in the database. And automatically deletes the changeset once the corresponding upload has completed.

Should a merge conflict arise, there's an API to fetch the list of changesets that are queued for the node (but which haven't been pushed to the cloud yet):

let pendingChangesets = cloudTransaction.pendingChangesets(forNodeID: nodeID)

 

Performing the merge

If you're using ZDCSyncable, then you get standard merging algorithms for free.

You only need 3 pieces of information:

• current local version
• current cloud version
• list of pending local changesets (those that haven't been pushed to the cloud yet)

With this information, ZDCSyncable can perform the merge for you:

let pendingChangesets = cloudTransaction.pendingChangesets(forNodeID: nodeID)

do {
  try localVersion.merge(cloudVersion: cloudVersion, pendingChangesets: pendingChangesets)

  // That's all there is to it :)

} catch _ {}

For example:

// Imagine we start with a Television item that looks like this:

var localTV = Television(brand: "Samsung")
localTV.specs["size"] = "30"
localTV.clearChangeTracking()

var cloudTV = localTV // reminder: Television is a struct
var changesets: [ZDCChangeset] = []

// Some other device performs the following modification(s):

cloudTV.specs["hdmi inputs"] = "2"

// And we perform the following local modifications:

localTV.specs["size"] = "30.5"
localTV.specs["widescreen"] = "true"

changesets.append(localTV.changeset() ?? ZDCChangeset())

// We get a merge conflict when pushing to the cloud.
// So now we have to merge our local version with the cloud version.
// 
// The only things we need to perform this task:
// - current local version
// - current cloud version
// - list of pending changesets
// 
// And ZDCSyncable can do the boilerplate merge stuff for us:

do {
  try localTV.merge(cloudVersion: cloudTV, pendingChangesets: changesets)

  // Merged state:
  // localTV.brand == "Samsung"
  // localTV.specs["size"] == "30.5"
  // localTV.specs["widescreen"] == "true"
  // localTV.specs["hdmi inputs"] = "2"
} catch _ {}

 

Putting it all together

/**
 * STEP 1 of 4:
 * 
 * Figure out a way to track changes to your data models.
 * We recommend ZDCSyncable, but you're free to use whatever you want.
 * 
 * If you use ZDCSyncable, the process looks like this:
 */

import ZDCSyncable

struct Television: ZDCSyncable { // Add ZDCSyncable protocol

  @Syncable var brand: String // Add @Syncable property wrappers

  // Or use syncable collection
  var specs = ZDCDictionary<String, String>()

  /// Implement this function if you have syncable collections
  /// such as ZDCDictionary, ZDCArray, etc
  mutating func setSyncableValue(_ value: Any?, for key: String) -> Bool {

    switch key {
    case "specs":
      if let value = value as? ZDCDictionary<String, String> {
        specs = value
        return true
      }

    default: break
    }

    return false
  }
}

/**
 * STEP 2 of 4:
 * 
 * Store your changeset when you queue uploads.
 */

var tv = self.fetchTelevision(id: tvid)
tv.specs["size"] = "30.5"
tv.specs["widescreen"] = "true"

let changeset = tv.changeset()
// 
// Our changeset contains a dictionary that includes:
// - which properties were changed
// - what the original values were (prior to change)

cloudTransaction.queueDataUpload(forNodeID: node.uuid, withChangeset: changeset)

/**
 * STEP 3 of 4:
 * 
 * When you are notified of a merge conflict,
 * you'll want to download the latest cloud version
 * in order to perform the merge.
 * 
 * You're notified via your ZeroDarkCloudDelegate:
 */

func didDiscoverConflict(_ conflict: ZDCNodeConflict, forNode node: ZDCNode, atPath path: ZDCTreesystemPath, transaction: YapDatabaseReadWriteTransaction) {

  if conflict == .data {

    guard let cloudTransaction = zdc.cloudTransaction(transaction, forLocalUserID: node.localUserID) else {
      return
    }

    cloudTransaction.markNodeAsNeedsDownload(node.uuid, components: .all)
    self.downloadNode(node, at: path)
  }
}


/**
 * STEP 4 of 4:
 * 
 * Perform the merge.
 * 
 * In fact, you'll perform a similar operation whenever
 * you download the cloud version of an object.
 */

func processDownload(_ cloudTV: Television, nodeID: String, eTag: String) {

  self.rwDatabaseConnection.asyncReadWrite {(transaction) in

    guard
      let node = transaction.node(id: nodeID),
      let cloudTransaction = zdc.cloudTransaction(transaction, forLocalUserID: node.localUserID)
    else {
      return
    }

    if var localTV = cloudTransaction.linkedObject(forNodeID: nodeID) as? Television {

      // Fetch queued changesets (may or may not be empty)
      let pendingChangesets = cloudTransaction.pendingChangesets(forNodeID: nodeID)

      do {
        // Perform merge
        let _ = try localTV.merge(cloudVersion: cloudTV, pendingChangesets: pendingChangesets)

        // Notify framework that conflicts have been resolved.
        cloudTransaction.didMergeData(withETag: eTag, forNodeID: nodeID)

      } catch () {
        // If merge fails, fallback to using cloud version here
      }

    } else {

      // Nothing to merge - we don't have a localTV.
    }
  }
}

To see this code in action, check out one of the sample projects included with the repository:

• ZeroDarkTodo
• WhatsZapp