Conflict Management in the SMSyncServer

5/11/16

The last main remaining feature, before I’m willing to call the SMSyncServer “beta”, is conflict management. Conflicts occur in systems that synchronize data across devices when a user on one device makes a change to one file or data object, call that object X, and at around the same time another user on a different device also changes X. For example, Fred might delete file X on his iPhone, while Sonia makes a change to file X on her iPhone. Because of the distributed nature of the system, there is now a conflict between versions of the file. Should the deletion be accepted or should the update be accepted?

In general, in the SMSyncServer, we are going to delegate the decision for how to resolve conflicts up out of the SMSyncServer client to the app using the SMSyncServer. The SMSyncServer itself will provide management tools for dealing with conflicts. The client app will have the responsibility for resolving the conflicts. We consider conflict resolution to be an application-level problem because strategies for dealing with specific conflicts seem likely to need knowledge from the specifics of the app. In the case of Sonia and Fred, if Sonia’s upload occurs first should Fred’s app accept Sonia’s change and disregard Fred’s deletion? Or should the deletion take priority? These do not seem like general policy decisions that can be made at the level of the SMSyncServer framework.

Let’s suppose that Fred and Sonia make these changes to file X at roughly the same time, and consider the situation before the changes are propagated up to the SMSyncServer server (just sync server in the following). The following figure illustrates this situation:

Blog6-Slide1-Final

In SMSyncServer, we assume that the server holds the truth or highest priority version of the data, and that synchronization takes place by uploading changed files on a mobile device to the sync server, and subsequently downloading those updates to other devices. The actual final state of data on the system is determined by a competition  or race between devices to have their version become the highest priority– to reach the server. So, what happens in the more specific case of the race between Sonia’s and Fred’s devices after Time 1? There are two main alternatives: A) Sonia’s change makes it to the server first, or B) Fred’s change makes it to the server first.

Let’s look at A) first: Sonia wins

Blog6-Slide2-Final

With file X, version N+1 uploaded to the sync server and cloud storage, when Fred’s device downloads this update from the sync server, there is now a conflict. In the internal jargon of SMSyncServer, and with respect to Fred’s device, there is a file-download (file X, version N+1), and a pending upload-deletion. One issue to notice immediately is that Fred’s device is attempting to delete version N, while the download is for version N+1. This difference in versions is a fact of the way the SMSyncServer is structured. While typically when an app is doing an upload-deletion, the version number of the file being deleted will match that on the server, in the case of a conflict, the version number of the file on the server may be higher.

The app on Fred’s device has the choice to (i) disregard the local change (i.e., the deletion) and accept the download of version N+1 of file X, or (ii) to disregard version N+1 and continue with the upload of its deletion. Suppose that Fred’s app (perhaps by virtue of asking Fred, perhaps by virtue of some policy within the app) decides to continue with its upload-deletion. In the current implementation of the SMSyncServer, the upload-deletion will operate as if it was a newly initiated upload-deletion. That is, the upload-deletion on Fred’s device has to compete with uploads being processed by other devices. This occurs because currently the server lock is not held past the inbound transfer phase of downloads and so a server lock for the upload-deletion must again be obtained– and some other device may, in the meantime, have obtained the lock.

Let’s also look at case B) where Fred wins:

Blog6-Slide3-Final

With file X now marked as deleted in the meta data on the sync server (and actually deleted from the cloud storage), when Sonia’s device downloads this update from the sync server, there is now a conflict. In the internal jargon of SMSyncServer, and with respect to Sonia’s device, there is a download-deletion for file X, and a pending file-upload. Sonia’s device has the choice to (i) disregard the local change (i.e., its file update) and accept the deletion of file X, or (ii) to disregard the deletion and continue with the upload of its update.

If Sonia’s app decides to continue with its file update, in the current implementation of the SMSyncServer, the file-upload will operate as if it was a newly initiated file-upload. There is one problem with this, however. Prior to the upload, Sonia’s app will need to undelete file X in the meta data on the sync server. Undeletion of a file will be new functionality on the part of the sync server: Currently attempts to upload files marked as deleted on the sync server fail.

Different types of conflicts
In the SMSyncServer, downloads are prioritized over uploads which causes conflicts to be detected during download operations. Conflicts can arise during file-downloads or download-deletions, and overall there are three types of possible conflicts:

File-download from server Download-deletion from server
Local file was modified DownloadFileLocalUpload DownloadDeletionLocalUpload
Local file was deleted DownloadFileLocalUploadDeletion (Not a conflict)

I considered adding a facility to mark a file as locally “locked”– to indicate that the client app is currently in the process of modifying the file. The sole implication of having a local lock on a file was to be that the SMSyncServer would report a conflict should an attempt be made to download (or download-delete) a change to that file. Locks would be transient in that they would not persist across launches of the app. I decided against this locking mechanism for two reasons: 1) It seems likely that the need for the lock would stem from a UI issue– the client app would typically have a user in the process of directly or indirectly making a modification to a file, and  2) There would always be a race condition in reporting such a modification conflict back to the client app: E.g., The client app could have stopped modifying the file between the time the conflict report was generated and the delegate callback was made to report the conflict. As a consequence of this choice of not providing local locks, the client app will need to keep track of the files it is in the process of modifying, and deal with that at the same time conflicts reported from SMSyncServer are managed.

Client API for managing conflicts
Originally, I was planning to have a separate delegate callback to the client app to tell the client about conflicts. However, specific conflicts occur within the context of specific file downloads and download deletions, so it seems to make sense to make conflicts part of the existing delegate callbacks for downloads and download deletions. An additional change to the client API, as mentioned above, is that the upload methods have to be modified to allow for undeletion of server files.

The bulk of the changes to the client API are in the following (see the file SMSyncServer.swift):

public enum SMSyncServerFileDownloadConflict : String {
    // Has a local pending upload-deletion.
    case LocalUploadDeletion
    
    // Has been modified (not deleted) locally
    case LocalUpload
}

public enum SMSyncServerDownloadDeletionConflict : String {
    // Has been modified (not deleted) locally
    case LocalUpload
}

// These delegate methods are called on the main thread.
public protocol SMSyncServerDelegate : class {
    // "class" to make the delegate weak.

    // Called at the end of all downloads, on non-error conditions. Only called when there was at least one download.
    // The callee owns the files referenced by the NSURL's after this call completes. These files are temporary in the sense that they will not be backed up to iCloud, could be removed when the device or app is restarted, and should be moved to a more permanent location. See [1] for a design note about this delegate method. This is received/called in an atomic manner: This reflects the current state of files on the server.
    // With no conflict, the recommended action is for the client to replace their existing data with that from the files. With a conflict, the client has to decide how to manage the conflict.
    // The callee must call the acknowledgement callback when it has finished dealing with (e.g., persisting) the list of downloaded files, and any conflicts.
    // It is up to the callee to check to determine if any modification conflict is occuring for a particular downloaded file.
    func syncServerDownloadsComplete(downloadedFiles:[(NSURL, SMSyncAttributes, SMSyncServerFileDownloadConflict?)], acknowledgement:()->())
    
    // Called when deletion indications have been received from the server. I.e., these files have been deleted on the server. This is received/called in an atomic manner: This reflects the current state of files on the server. With no conflict, the recommended action is for the client to delete the files represented by the UUID's. With a conflict, the client has to decide how to manage the conflict.
    // The callee must call the acknowledgement callback when it has finished dealing with (e.g., carrying out deletions for) the list of deleted files, and any conflicts.
    // It is up to the callee to check to determine if any modification conflict is occuring for a particular deleted file.
    func syncServerClientShouldDeleteFiles(deletions:[(NSUUID, SMSyncServerDownloadDeletionConflict?)], acknowledgement:()->())
    
    // Reports mode changes including errors. Can be useful for presenting a graphical user-interface which indicates ongoing server/networking operations. E.g., so that the user doesn't close or otherwise the dismiss the app until server operations have completed.
    func syncServerModeChange(newMode:SMSyncServerMode)
    
    // Reports events. Useful for testing and debugging.
    func syncServerEventOccurred(event:SMSyncServerEvent)
}

About the author: Christopher G. Prince has his B.Sc. in computer science (University of Victoria, B.C., Canada), an M.A. in animal psychology (University of Hawaii, Manoa), an M.S. in computer science (University of Louisiana, Lafayette, USA), and a Ph.D. in computer science (University of Louisiana, Lafayette, USA). His M.S. and Ph.D., while officially in computer science, were unofficially in cognitive science, split between animal psychology and computer science. Chris is a dedicated animal person, and has also developed: Catsy Caty Toy, a customizable and shareable iPhone and iPad app for your cats (http://GetCatsy.com)Petunia, an app for recording and sharing pet health information (http://GetPetunia.com), and WhatDidILike, an iPhone app to keep track of restaurants and food that you like (http://WhatDidILike.com).

Creative Commons License
“Conflict Management in the SMSyncServer” by Christopher G. Prince is licensed under a Creative Commons Attribution 4.0 International License. Permissions beyond the scope of this license may be available at chris@SpasticMuffin.biz.