Synchronizing client-server databases

I’m looking for some general strategies for synchronizing data on a central server with client applications that are not always online.

In my particular case, I have an android phone application with an sqlite database and a PHP web application with a MySQL database.

Users will be able to add and edit information on the phone application and on the web application. I need to make sure that changes made one place are reflected everywhere even when the phone is not able to immediately communicate with the server.

I am not concerned with how to transfer data from the phone to the server or vice versa. I’m mentioning my particular technologies only because I cannot use, for example, the replication features available to MySQL.

I know that the client-server data synchronization problem has been around for a long, long time and would like information – articles, books, advice, etc – about patterns for handling the problem. I’d like to know about general strategies for dealing with synchronization to compare strengths, weaknesses and trade-offs.

Answer

The first thing you have to decide is a general policy about which side is considered “authoritative” in case of conflicting changes.

I.e.: suppose Record #125 is changed on the server on January 5th at 10pm and the same record is changed on one of the phones (let’s call it Client A) on January 5th at 11pm. Last synch was on Jan 3rd. Then the user reconnects on, say, January 8th.

Identifying what needs to be changed is “easy” in the sense that both the client and the server know the date of the last synch, so anything created or updated (see below for more on this) since the last synch needs to be reconciled.

So, suppose that the only changed record is #125. You either decide that one of the two automatically “wins” and overwrites the other, or you need to support a reconcile phase where a user can decide which version (server or client) is the correct one, overwriting the other.

This decision is extremely important and you must weight the “role” of the clients. Especially if there is a potential conflict not only between client and server, but in case different clients can change the same record(s).

[Assuming that #125 can be modified by a second client (Client B) there is a chance that Client B, which hasn’t synched yet, will provide yet another version of the same record, making the previous conflict resolution moot]

Regarding the “created or updated” point above… how can you properly identify a record if it has been originated on one of the clients (assuming this makes sense in your problem domain)? Let’s suppose your app manages a list of business contacts. If Client A says you have to add a newly created John Smith, and the server has a John Smith created yesterday by Client D… do you create two records because you cannot be certain that they aren’t different persons? Will you ask the user to reconcile this conflict too?

Do clients have “ownership” of a subset of data? I.e. if Client B is setup to be the “authority” on data for Area #5 can Client A modify/create records for Area #5 or not? (This would make some conflict resolution easier, but may prove unfeasible for your situation).

To sum it up the main problems are:

• How to define “identity” considering that detached clients may not have accessed the server before creating a new record.
• The previous situation, no matter how sophisticated the solution, may result in data duplication, so you must foresee how to periodically solve these and how to inform the clients that what they considered as “Record #675” has actually been merged with/superseded by Record #543
• Decide if conflicts will be resolved by fiat (e.g. “The server version always trumps the client’s if the former has been updated since the last synch”) or by manual intervention
• In case of fiat, especially if you decide that the client takes precedence, you must also take care of how to deal with other, not-yet-synched clients that may have some more changes coming.
• The previous items don’t take in account the granularity of your data (in order to make things simpler to describe). Suffice to say that instead of reasoning at the “Record” level, as in my example, you may find more appropriate to record change at the field level, instead. Or to work on a set of records (e.g. Person record + Address record + Contacts record) at a time treating their aggregate as a sort of “Meta Record”.

Bibliography:

• More on this, of course, on Wikipedia.

• A simple synchronization algorithm by the author of Vdirsyncer

• OBJC article on data synch

• SyncML®: Synchronizing and Managing Your Mobile Data (Book on O’Reilly Safari)

• Conflict-free Replicated Data Types

• Optimistic Replication YASUSHI SAITO (HP Laboratories) and MARC SHAPIRO (Microsoft Research Ltd.) – ACM Computing Surveys, Vol. V, No. N, 3 2005.

• Alexander Traud, Juergen Nagler-Ihlein, Frank Kargl, and Michael Weber. 2008. Cyclic Data Synchronization through Reusing SyncML. In Proceedings of the The Ninth International Conference on Mobile Data Management (MDM ’08). IEEE Computer Society, Washington, DC, USA, 165-172. DOI=10.1109/MDM.2008.10 http://dx.doi.org/10.1109/MDM.2008.10

• Lam, F., Lam, N., and Wong, R. 2002. Efficient synchronization for mobile XML data. In Proceedings of the Eleventh international Conference on information and Knowledge Management (McLean, Virginia, USA, November 04 – 09, 2002). CIKM ’02. ACM, New York, NY, 153-160. DOI= http://doi.acm.org/10.1145/584792.584820

• Cunha, P. R. and Maibaum, T. S. 1981. Resource &equil; abstract data type + synchronization – A methodology for message oriented programming -. In Proceedings of the 5th international Conference on Software Engineering (San Diego, California, United States, March 09 – 12, 1981). International Conference on Software Engineering. IEEE Press, Piscataway, NJ, 263-272.

(The last three are from the ACM digital library, no idea if you are a member or if you can get those through other channels).

From the Dr.Dobbs site:

• Creating Apps with SQL Server CE and SQL RDA by Bill Wagner May 19, 2004 (Best practices for designing an application for both the desktop and mobile PC – Windows/.NET)

From arxiv.org:

• A Conflict-Free Replicated JSON Datatype – the paper describes a JSON CRDT implementation (Conflict-free replicated datatypes – CRDTs – are a family of data structures that support concurrent modification and that guarantee convergence of such concurrent updates).