Thursday, February 18, 2010

Version Synchronization

I wrote a server for my MegaCollection software.
Each member of the family can upload new movies and TV series, and edit, delete and rate existing items. The server is used to store this data and support versions synchronization.

Each item has a quite complex data structure including names of actors, image, IMDB identifier, etc. TV series has Seasons, and they have Episodes, and the list is long...
 I'll ignore all of this and assume the following:
  • The Database is a list of Movies
  • Each Movie has a list of DownloadVersions
  • Movies and DownloadVersions have some data inside
Now we have the serverDatabase and the userDatabase.The user can edit his database offline. Other users can do this too.
So we can't assume anything about the databases apart from their correctness.

How do we produce a synchronized database?

I decided to define an interface that all synchronized objects must implement:


interface ISyncObject
{
    string ID { get; }
    DateTime Timestamp { get; }
}

We also need the following information:

DateTime lastSuccessfulSynchronizationWithServer;

This should be enough information to handle all of the following cases:
  1. User added a new Movie
  2. Other user added a new Movie
  3. User deleted a Movie
  4. Other user deleted a Movie
  5. User modified data inside a Movie
  6. Other user modified data inside a Movie
  7. User added a new DownloadVersion
  8. Other user added a new DownloadVersion
  9. User deleted a DownloadVersion
  10. Other user deleted a DownloadVersion
  11. User modified data inside a DownloadVersion
  12. Other user modified data inside a DownloadVersion
Note that cases 7 to 12 happen only if two Movies has the same ID and Timestamp. This case is referred to as "Merging" of the two Movies.

I wrote a synchronization function that considers all the cases 1 to 6. When a merging is required, this function is called again on the DownloadVersions.

Here is the function signature:

static class SyncHelper<T> where T : class, ISyncObject
{
 public static void SynchronizeLists(
  List<T> serverList,
  List<T> userList,
  DateTime lastSuccessfulSynchronizationWithServer,  
  MergeObjectsDelegate mergeObjectsMethod
  )
 {
   // code
 }
}

Assuming this functions works, we can synchronize the database using the following code:

  

static void SynchronizeDatabase(Database serverDatabase, Database userDatabase)
{
    SyncHelper<Movie>.SynchronizeLists(
        serverDatabase.movies,
        userDatabase.movies,
        userDatabase.lastSuccessfulSynchronizationWithServer,
        MergeMovies
        );
    userDatabase.lastSuccessfulSynchronizationWithServer = DateTime.Now;
}
static Movie MergeMovies(Movie serverMovie, Movie userMovie, DateTime lastSuccessfulSynchronizationWithServer)
{
    SyncHelper<DownloadVersion>.SynchronizeLists(
        serverMovie.DownloadVersions,
        userMovie.DownloadVersions,
        lastSuccessfulSynchronizationWithServer,
        MergeDownloadVersions
        );
    // add code to merge other movie data
    return serverMovie;
}
static DownloadVersion MergeDownloadVersions(DownloadVersion serverDownloadVersion, DownloadVersion userDownloadVersion, DateTime lastSuccessfulSynchronizationWithServer)
{
    // add code to merge download versions data
    return mergedDownloadVersion;
}

The purpose of this was to prove it is a quite handy function. I use it in my server to synchronize several types of classes and it works flawlessly.
Here is the full class:

  


static class SyncHelper where T : class, ISyncObject
{
    public delegate T MergeObjectsDelegate(T serverObject, T userObject, DateTime lastSuccessfulSynchronizationWithServer);
    private static Dictionary<string, T> ListToDictionaryByID(List list)
    {
        Dictionary<string, T> dic = new Dictionary<string, T>();
        foreach (T obj in list)
        {
            dic[obj.ID] = obj;
        }
        return dic;
    }
    public static void SynchronizeLists(List serverList, List userList, DateTime lastSuccessfulSynchronizationWithServer)
    {
        // call original function, on merging always take server's object
        SynchronizeLists(serverList, userList, lastSuccessfulSynchronizationWithServer, delegate(T obj1, T obj2, DateTime timestamp) { return null; });
    }
    public static void SynchronizeLists(List serverList, List userList, DateTime lastSuccessfulSynchronizationWithServer, MergeObjectsDelegate mergeObjectsMethod)
    {
        // note that objects that were added by other user will be
        // updated at current user because we are sending him serverList
        string tname = typeof(T).Name;
        Dictionary<string, T> serverObjectByID = ListToDictionaryByID(serverList);
        Dictionary<string, T> userObjectByID = ListToDictionaryByID(userList);
        // look for objects that user deleted
        for (int i = serverList.Count - 1; i >= 0; --i)
        {
            T serverObject = serverList[i];
            //l.Debug("Checking server's", tname, serverObject);
            if (!userObjectByID.ContainsKey(serverObject.ID) &&
                serverObject.Timestamp < lastSuccessfulSynchronizationWithServer)
            {
                // if user doesn't have this object, but he should have it
                // then he deleted it after previous synchronization
                //l.Debug("User deleted this", tname, ", removing from server:", serverObject);
                serverList.RemoveAt(i);
                serverObjectByID.Remove(serverObject.ID);
            }
        }
        foreach (T userObject in userList)
        {
            //l.Debug("Checking user's", tname, userObject);
            if (!serverObjectByID.ContainsKey(userObject.ID))
            {
                // user has an object which doesn't exist at the server's list
                // check timestamps
                if (userObject.Timestamp > lastSuccessfulSynchronizationWithServer)
                {
                    // user added a new object after previous synchronization
                    //l.Debug("This", tname, "is new. Adding to server's list:", userObject);
                    serverList.Add(userObject);
                }
                else
                {
                    // this movie was deleted by other user
                    // the current user will get the new list without this object
                    //l.Debug("This", tname, "was deleted by other user:", userObject);
                }
            }
            else
            {
                // both server and user has this object
                T serverObject = serverObjectByID[userObject.ID];
                //l.Debug("This", tname, "already exists in server database:", serverObject);
                if (serverObject.Timestamp > userObject.Timestamp)
                {
                    // the object was updated by other user
                    // ignore user's object, he will get the new version
                    //l.Debug("Server", tname, "is newer than user's:", serverObject);
                    if (userObject.Timestamp > lastSuccessfulSynchronizationWithServer)
                    {
                        l.Warn("Possible conflict between server and user objects: Server object is newer, but User object was modified after previous synchronization:", userObject);
                    }
                }
                else if (serverObject.Timestamp < userObject.Timestamp)
                {
                    // user deleted the object and then added it again
                    // remove server's copy and replace it with user's
                    //l.Debug("User", tname, "is newer than server's:", userObject);
                    serverList.Remove(serverObject);
                    serverList.Add(userObject);
                    if (serverObject.Timestamp > lastSuccessfulSynchronizationWithServer)
                    {
                        l.Warn("Possible conflict between server and user objects: User object is newer, but Server object was modified after previous synchronization:", userObject);
                    }
                }
                else
                {
                    // both server and user has this movie and:
                    // serverObject.Timestamp == userObject.Timestamp
                    //l.Debug("Server and user have the same", tname, "and with equal timestamps, merging is required:", userObject);
                    T mergedObject = mergeObjectsMethod(serverObject, userObject, lastSuccessfulSynchronizationWithServer);
                    if (mergedObject != null)
                    {
                        serverList.Remove(serverObject);
                        serverList.Add(mergedObject);
                    }
                }
            }
        }
    }
}

No comments:

Post a Comment