From the application scenarios we can derive a set of requirements for a synchronization solution.
The listed requirements resemble the goals set for the Bayou architecture back in 1994 [30]. Bayou had already proposed a distributed architecture with multiple devices acting as servers. At that time the computational capabilities of mobile devices were very limited. Today even smartphones have more storage and stronger CPUs than most servers in 1994. Therefore pairwise synchronization should not only be possible between servers but also between mobile devices directly.
We will go into detail on each of our requirements and conclude the chapter with a short summary of these.
A synchronization engine that is useful for a broad range of applications has to be able to deal with different data models. There is no magic algorithm that produces a perfect solution for an existing application. Synchronization can happen with increasing levels of sophistication depending on the level of structural awareness of an application’s data. A “dumb” engine would have no awareness of an app’s data model at all - it simply sees the entire application data as one binary chunk.
A more clever solution would maybe have an understanding of entities like Projects, Tasks or Comments and would see the entity instances as binary data.
It could get even finer grained and break up each entity instance into attributes, which it recognizes as different pieces of data.
We see that synchronization granularity is one key aspect when defining require- ments. The smallest pieces of information a synchronization engine cannot break up further we call atoms. Atoms are usually aggregated into larger structures we call objects. A Task instance could be treated as an object, which is composed of the title and due date attributes as atoms.
In order to be useful a synchronization engine does not need perfect understanding of the data to be synchronized. Popular applications like Dropbox can provide useful synchronization of files without having any semantic understanding of their content. For Dropbox each file is an atom - if a user adds a paragraph to a Word document, Dropbox only recognizes a change of the entire file. This means if two users concurrently modify the same document at different places, Dropbox has no way to merge the changes correctly and will trigger a conflict.
Version control systems like git are usually more sophisticated - Section 2.5 explains git’s hierarchical merge strategy in more detail. By treating each line in a file as an atom git can often successfully merge concurrent changes. Git still does not have any syntactic or even semantic awareness of the code that is written in the files it synchronizes. So if there are concurrent edits, git cannot guarantee that merges are syntactically or semantically correct. Despite this seemingly low level of structural awareness, git is used very successfully in large software projects.
The data model of our application scenario is relatively simple but covers most of the modeling aspects the average mobile application needs:
- Entities and Instances
- (Ordered) Collections
- Attributes
- Relationships (one to one, one to many, many to many)
This set of modeling elements is represented in many client-side application frameworks like Ember.js, Backbone or Angular. If we can support synchronizing data with this type of schema it will make integration with existing frameworks fairly trivial.
We therefore require that the synchronization engine needs to have a structural awareness of at least the listed modeling components.
As we have seen in the application scenario it is necessary that objects are editable on multiple devices even if they are not connected to a network. Edits should be allowed concurrently to not block users from doing their work. This implies that there can not be a central locking mechanism that controls when users can synchronize their data for offline usage. We therefore trade strong consistency for availability of the data.
Synchronization happens in an optimistic manner, which means that we assume that temporarily inconsistent data will rarely lead to problems. Most mobile applications do not require strong consistency - the offline availability of data is usually a more important factor when judging the user experience.
Our goal is to guarantee that after a finite number of synchronization events all objects will eventually converge to the same state across all devices. This property is referred to as eventual consistency and explained in Section 2.2.
If an object diverges into multiple branches it will have to be reconciled during the synchronization process. When we receive states from a remote device we need to reason about how we can apply them to our own edit history.
The happens-before relationship defined by Lamport in [31] helps to solve this problem in an intuitive way. A state A that happened before state B refers to the fact that the edits that led to B could have been affected by A. The order of states defined through the happens-before relationship is called the causal order. The causal order of states is not necessarily related to the actual time of the edits that led to A and B as we can see in the following example:
Lets assume Rita and Allen work on the same object with their respective devices. The object has the initial state A.
- 9:00 AM: Rita makes an edit to the object, which leads to state B.
- 9:30 AM: Allen synchronizes with Rita and edits, which leads to state C.
- 10:00 AM: Rita is offline and can not synchronize. She edits the object at state B leading to state D.
As Allen has seen state B when making his edit, state B happened before state C. Rita has not seen state C when making her edit. Although the time of her edit is after Allen’s edit there is no happened-before relationship between state C and D.
On the next synchronization between Allen and Rita the system needs to identify this lack of causality as a conflict.
While this example is simple, the identification of conflicts among a large group of collaborators can be non-trivial.
Depending on the level of understanding the synchronization engine has on the data there are strategies to resolve conflicts automatically. The engine should be designed in a way that conflict resolution strategies can be “plugged-in”. If no automatic resolution is possible the application should be able to present the conflict to the user and let him manually resolve it.
Merging of updates and conflict resolution should be based on three-way merging. This means each client has to keep previous versions of edited objects. The concept of three- way merging is explained in Section 2.5.
A traveling user who works with multiple mobile devices needs to be able to sychronize data without requiring Internet access. The synchronization engine should therefore be designed to handle peer-to-peer connections.
Even in an office environment where users exchange large amounts of data a direct connection can be significantly faster than doing a round-trip through a server on the Internet. For this setting a hybrid architecture with local servers in the company network could be an interesting alternative. The local servers could provide fast synchronization among users inside the office while a remote server on the Internet provides synchronization with users working from home.
The local and remote servers are synchronizing in a peer-to-peer topology while the users interact with them in a client-server setup. This gives us a hierarchical architecture, which is both able to exploit the different levels of network speed and guarantee a higher state of robustness through the centralized servers. A hierachical architecture can counter the higher risks of failure on clients like notebooks or smartphones. The more durable and always connected server nodes should be able to recover data loss on client nodes.
The protocol used for synchronization should be generic enough to adapt to these different network setups.
Most popular operating systems for mobile devices impose restrictions on the kind of software that can be installed. Even if these limitations can be circumvented it provides a huge barrier to the install process of an app if external software is required.
For mobile applications it is therefore crucial that they can embed all their dependencies in the binary. The synchronization engine should therefore be designed as an embeddable library.
Further it is important that the interfaces are designed to be as unintrusive into the application logic as possible.
A state based synchronization strategy is required to ease the integration process. The low-level aspects of update detection, update propagation and reconciliation should be abstracted away from the application developer as much as possible.
At the same time the developer needs to be able to supply the logic for aspects of the synchronization that can not be solved generically. These include data model definition, conflict handling and technical aspects of messaging.
The application described in our scenario has to run on a multitude of devices and platforms.
Notable platforms that should be supported are:
- Desktop Operating Systems: Microsoft Windows, OSX and Linux distributions
- Mobile Operating Systems: Android, iOS
- Server Operating Systems: Linux distributions
With such a broad range of platforms it is important to target a cross-platform environment to avoid having to maintain separate implementations for each platform.
The ideal synchronization framework would support an even broader range of requirements.
We intentionally leave out the technical aspects of data transmission between nodes. There is a broad range of protocols available to transfer data on the Internet and directly between devices. A generic synchronization solution should be agnostic to the data transmission protocol. Important is only the exposure of a data transmission interface so that adapters can be implemented for specific protocols.
Peer discovery is another important technical aspect that needs to be solved for any real application. There already exist solutions for this problems, examples being the various implementations of zeroconf [32] including Apple’s Bonjour service or the competing Universal Plug n’ Play (UPnP) [33] standard by Microsoft.
Security related aspects like peer authenticating and encrypted data transmission are other important requirements. Some applications need granular control on which parts of the data are transferred to which nodes, which parts are editable etc. In this thesis we assume that all collaborating users keep an entire data store in sync. Synchronizing only subsets of data with selected nodes can possibly be modeled through multiple stores each having different collaborators.
We can summary the defined requirements as the following:
- Flexible Data Models: be able to synchronize data models including entities with attributes and relationships, entity instances and instance collections.
- Optimistic Synchronization: no locking of data while ensuring eventual consistency.
- Causality Preservation and Conflicts: preserve causality defined by the happened-before relationship and expose conflicts.
- Three-Way Merging: base reconciliation on three-way merging concepts.
- Flexible Network Topologies: design a protocol that is able to synchronize data in a peer-to-peer, client-server or hierarchical architecture.
- Integration: be as unobtrusive to an application as possible.
- Cross-Platform: be able to run on modern desktop and mobile platforms.