Mobile Network Computing Reference Specification
Data Synchronization Work Group

Roger Riggs (Roger.Riggs@Sun.COM), Sun Microsystems Inc., JavaSoftTM, editor

Version 1.1

March 1999


Data Synchronization Architecture Document


This document specifies a framework for data synchronization between an MNCRS platform and its servers or peers. It specifies the application programming interfaces for data objects to be synchronized, persistent object stores to hold these objects, and mechanisms that control the synchronization process. It is jointly developed by members of the Data Synchronization Work Group in the MNCRS team.

Comments and feedback should be sent to mncrs-comments@eng.sun.com.

Table of Contents

Preface
System Architecture
Object Update Model
Synchronization Interfaces
        Synchronizable
        Reconcilable
        SyncStore
        StoreManager
        Synchronizer
Security
Concurrency
Working-Group Members

Preface

Mobile applications require access to persistent information regardless of whether or not the mobile device is connected to a network. When a disconnected device reconnects, any application information that was modified while the device was disconnected needs to be propagated to the network server and any updates on the server need to be sent to the device.

The MNCRS data-synchronization framework fills this need by providing a reliable persistent storage mechanism that can automatically replicate JavaTM objects between devices and servers using available communication mechanisms.

System Architecture

The MNCRS data-synchronization architecture comprises a set of cooperating components that provide an end-to-end mechanism to replicate, transport, and update application JavaTM objects between clients and servers or between peers.

The major components include the following:
Each component has a specific function in the architecture. Components communicate with other components through specified interfaces. The implementations of these functional blocks can be designed to accommodate a wide range of device capabilities, sizes, and communication parameters.

The following illustration shows the data synchronization components.

Data Synchronization Architecture

Figure 1: Components of Data Synchronization

A Synchronizable object is an application object that can be stored in and retrieved from a SyncStore. The Reconcilable interface extends the Synchronizable interface and declares methods that allow the object itself to manage the merging of updates. When changes occur to an object on different replicas, the object itself can then be invoked to reconcile potential conflicts. (Future versions of the framework may include additional interfaces, besides Reconcilable, that extend Synchronizable.)

A SyncStore is a lightweight replicable persistent store for objects that need to be synchronized between clients and servers. It supports disconnected client application operations by providing a reliable and efficient mechanism for accessing and updating information that changed during the time that the client application was disconnected. Objects stored in a SyncStore are Synchronizable objects, which can participate in accepting updates and detecting and resolving conflicts. A SyncStore can produce a sequence of updates that can be transported and applied to one or more of the SyncStore's replicas. A SyncStore identifies its replicas and the status relative to each replica.

A Synchronizer is the main worker of the synchronization process. A Synchronizer cooperates with a corresponding Synchronizer on another system and the two exchange updates that bring two SyncStore objects up-to-date (so that the two stores contain equivalent sets of objects). Typically, a Synchronizer keeps track of which updates have been exchanged with another SyncStore and only exchanges newer updates. A variety of protocols can be created to maximize the efficient utilization of the available communication channel. Details of the protocol need only be known and shared between cooperating Synchronizer instances.

A StoreManager is a locator component. It keeps track of SyncStore implementation classes, making them available to the application and the Synchronizer. SyncStore instances, which are named by local URLs, can be created, listed, and opened.

Object Update Model

The object update model is designed to minimize dependencies among components and clearly define their interactions. Applications store objects in a SyncStore. The SyncStore produces a sequence of updates that can be applied to a replica of the SyncStore to propagate changes in objects. Synchronizer instances transmit updates from a SyncStore to its replicas in a manner that depends on the available transports and the protocol used by the replica.

Applications create Reconcilable objects and insert them into the SyncStore. These application objects will be replicated and kept up-to-date in each replica. As an application updates a Reconcilable object, it notifies the SyncStore that the object has changed. Changes are recorded in sequence, so the sequence of updates can be reliably reproduced. No two changes are recorded as having occurred at the same logical "time."

The SyncStore records which objects are inserted, updated, and deleted along with the logical time of those events. The SyncStore keeps track of which replica has modified the object, thereby allowing a SyncStore to detect when an object has been modified in parallel on multiple stores. The combined information about the update history of the object is kept internally in a SyncVersion object. A SyncVersion implemented as a version vector will support arbitrary patterns of pairwise synchronization among peer platforms. There is no need for an application to be aware of SyncVersion objects.

A Synchronizer may ask a SyncStore to produce a sequence of updates for a range of versions. Each update generated by a SyncStore is self-contained, having all of the necessary version and object information that needs to be applied to a replica of the SyncStore. The version information allows each SyncStore to keep track of updates that have already been applied, thereby enabling the SyncStore to ignore duplicates.

Each SyncStore has its own logical clock, which need not be coordinated in any way with the logical clock of any other SyncStore. A SyncStore records the times of updates according to its own logical clock. A Synchronizer uses this logical clock to keep track of which updates have been transported and which have not yet been propagated. The protocol used by a Synchronizer can rely on the ordering of updates from a SyncStore. A simple Synchronizer transmits updates in order and acknowledges them in the same order.

Synchronization Interfaces

Synchronizable

A Synchronizable object is an application object that can be stored in a SyncStore. The SyncStore holds the application state that is to be replicated in mirror stores. The Synchronizable interface has two methods, writeRemote and readRemote, that generate a byte-stream representation for the state of a Synchronizable object and set a Synchronizable object to the state specified by such a byte-stream representation, respectively. In the current version of the data-synchronization framework, all objects implementing the Synchronizable interface also implement the Reconcilable interface, which is an extension of Synchronizable. In future versions of the framework, a SyncStore might include different objects implementing different extensions of the Synchronizable interface.

When an application updates the state of the object, it must deal with the potential for concurrency between the application and synchronization with another SyncStore. Updates to a Synchronizable object by an application must use normal thread-safe synchronization primitives. For more details see the section "Concurrency." Since a Synchronizable object is its own lock, the object itself is involved in every update action.

Reconcilable

The Reconcilable interface extends the Synchronizable interface with methods that allow an application object to participate in the replication process, applying updates and reconciling conflicting changes. When updates are made, the store must be called to make the change persistent and to propagate the change to other stores. The SyncStore method markAsUpdated (or, in special circumstances, the SyncStore method markForFlushing or markForSynchronization) should be called for each change to be recorded.

Replication of a Reconcilable object entails generating a byte-stream representation of the object's state (encapsulating the identity of the object and its version information). transmitting this representation to another store, extracting the identity of the object, its version information, and the updated object state at the other store, and applying the update to that store.

The version of the object in the receiving store and the version information in the update are used to decide when to invoke the object's setTo, reconcile, or reconcileWithDelete method. These methods allow the object to handle the different cases that occur when the object can be modified in parallel in different stores, and to perform whatever actions needed to resolve the conflict. The cases are: For the convenience of the application programmer, the data-synchronization framework includes a class DefaultReconcilable that provides a partial implementation of the Reconcilable interface, implementing the writeRemote and readRemote methods inherited from Synchronizable in terms of JavaTM serialization. An application writer who wishes to implement the writeRemote and readRemote methods in this way need only declare a class extending DefaultReconcilable and define its setTo, reconcile, and reconcileWithDelete methods.

SyncStore

A SyncStore is a lightweight replicable persistent store for objects that are to be synchronized. In a client-server application, it supports disconnected client application operations by providing a reliable and efficient mechanism for accessing and updating information that changed during the time that the client application was disconnected. The objects stored are Synchronizable objects, which can participate in accepting updates and handling conflicts.

SyncStore functions include the following: Different SyncStore implementations may produce and consume different types of updates. For example, a transaction-based SyncStore might group updates that are meant to be applied together as part of a single transaction in a single update object. At a minimum, every SyncStore implementation must be able to produce and consume a basic type of update object representing the creation, modification, or deletion of a single object.

SyncStore implementations can be characterized by the additional functions they provide and by the form in which they send updates. These differences could be visible in the API of that type of SyncStore (for example, by the presence of additional methods to begin, commit, and abort transactions). Although there can be multiple types of SyncStore, each SyncStore instance can synchronize only with instances that produce and consume at least one common type of update object.

As Synchronizable objects are inserted, marked as updated, and deleted -- either by an application or by the synchronization mechanism -- the store generates event notifications. To receive notifications, a client registers a listener with the store. A SyncStore also generates an event when it is opened, when its contents are flushed to persistent storage, and when it is closed.

A SyncStore can be opened for either exclusive or shared use, and must be closed when the application is complete. When the same store is opened multiple times for shared use, all openers share the contents of the store and the registry of event listeners, and all registered listeners are notified of each change to some object in the store. However, each opener of the shared store obtains a reference to a distinct SyncStore object. These SyncStore objects act as event sources in the event notification mechanism, allowing a listener to determine which opener of the store caused the event. When opening a SyncStore, an application may request a particular type of SyncStore implementation.

A SyncStore keeps track of each object as it is inserted, modified, or deleted. These updates are ordered by the value of a clock that is advanced whenever the SyncStore is updated. When the SyncStore operates on objects in the store, it records the current clock value in an entry associated with that object, and advances the clock. Assigned clock values provide an ordering for changes and can be used to find all objects updated after a specific previous clock value.

These clock values are included in version information that a SyncStore maintains for each object it stores. Each store also maintains a summary version indicating how recent the information incorporated in the store is. In general, version information is used to detect when conflicting updates have been performed on the same object in multiple replicas. An internal interface named SyncVersion (with which the application writer need not be concerned) provides an abstraction of the semantics of versions. This abstraction can compare a version with another version and report that the first version is: SyncVersion objects are passed between SyncStore instances as part of the synchronization process and are used to determine how to apply updates.

StoreManager

The StoreManager keeps track of stores on the local device and makes them available to the application as SyncStore objects.

The StoreManager has the following functions:

Synchronizer

A Synchronizer cooperates with a corresponding Synchronizer on another host to exchange updates that will bring two stores up to date (so that they contain equivalent sets of objects). Typically, the Synchronizer keeps track of which updates of a SyncStore have not been propagated and sends those updates to its peer. The peer, in turn, sends updates for objects in its local SyncStore. Details of the protocol need only be known and shared between cooperating Synchronizer instances.

The functions of a Synchronizer include the following: A particular Synchronizer implementation executes a synchronization protocol that accommodates the attributes of a particular device and communication link. For example, high-latency, low-bandwidth links may work better with an asynchronous messaging protocol. Different Synchronizer implementations will be appropriate for different devices or transports (for example, IrDA, TCP/IP, serial link, packet modem, etc.). A basic universal synchronization protocol (not optimized for any particular transport) will be specified as a baseline implementation ensuring compatibility and interoperability among MNCRS platforms. This protocol will entail the exchange of Java objects, and will be designed on the assumption that the underlying transport guarantees eventual in-order once-only delivery of each Java object transmitted. See the discussion of the Java Message Service (JMS) in Network Model and Protocol.

Synchronization Phases, Synchronization Status, and Synchronization Events

A synchronization may consist of one or more phases, each of which entails the transmission of updates in one direction. A typical synchronization consists of two phases, with the Synchronizer that sends updates in the first phase receiving updates in the second phase, and vice versa. A Synchronizer generates an event each time it begins a phase, each time a phase makes some amount of progress (dependent on the implementation of the Synchronizer), and each time a phase ends, either successfully or unsuccessfully. A Synchronizer maintains an object recording the status of each phase it is scheduled to perform, and this object is updated upon each event. This object implements an interface called SyncStatus, through which an application may track the progress of a synchronization. The Synchronizer interface includes a method that returns the SyncStatus object associated with a given Synchronizer. In addition, a snapshot of the SyncStatus object is included in each event object generated by a Synchronizer. Listeners for events generated by a particular Synchronizer can be registered with that Synchronizer. Listeners for events generated by any Synchronizer can be registered with the Synchronizer class, described below under "Starting, Stopping, and Waiting for Synchronizers".

Starting, Stopping, and Waiting for Synchronizers

An application may invoke synchronization in either an asynchronous style (in which synchronization proceeds concurrently with the thread that started it) or a synchronous style (in which the thread starting synchronization is blocked until synchronization completes). In the asynchronous style, the invoking thread can poll SyncStatus objects or install listeners for synchronization events to track the status of the synchronization. In the synchronous style, a method that blocks until synchronization is complete returns a SyncStatus object reporting the final status of the synchronization attempt. Each blocking method allows the caller to specify a time-out interval after which the calling thread becomes unblocked, even if synchronization has not completed. A Synchronizer can be requested to stop, but a Synchronizer implementation is free to defer this request, or to ignore it. If a request to stop is honored, it causes the currently active synchronization phase to fail.

Included in the information that a SyncStore maintains about its registered remote replicas is the sequence of sending and receiving phases to be used by default when synchronizing with that replica. This information is kept in an object of class SyncReplicaInfo, which has a method to modify the default sequence. Every Synchronizer instance is constructed to synchronize a specified open SyncStore with the replica described a specified SyncReplicaInfo object. The Synchronizer interface includes methods with the following functions:

Each instance of the class SynchronizerGroup class corresponds to a set of one or more Synchronizer objects that are to be started, requested to stop, or waited for together. There are SynchronizerGroup methods with the following functions: SynchronizerGroup instances are created by the SyncManager class. A SynchronizerGroup may be created to synchronize a single specified SyncStore instance or a set of specified SyncStore instances; in either case, for each SyncStore instance to be synchronized, the SynchronizerGroup may contain a single Synchronizer to synchronize the instance with a specified replica, or several Synchronizer instances, one to synchronize the SyncStore instance with each of its registered remote replicas.

There is one SyncManager class on an MNCRS device. Besides creating SynchronizerGroup instances, a SyncManager maintains a registry of listeners that are to be notified of any event generated by any Synchronizer. (Each Synchronizer also maintains its own registry of listeners that are to be notified only of events generated by that Synchronizer.)

For convenience, the SyncStore interface includes two blocking synchronization methods. One method attempts to synchronize the SyncStore with a specified remote replica, and to return a SyncStatus object reporting the status of the synchronization attempt after the attempt completes or, optionally, after a specified time-out interval has expired. The other method is similar, but attempts to synchronize the SyncStore with each of its registered replicas, and returns an array of SyncStatus objects, one for the attempted synchronization with each replica.

On a device that is capable of responding to synchronization requests from other devices, there will be one or more classes implementing the SyncRequestHandler interface. This interface provides methods to start listening for synchronization requests, typically at some well-known TCP/IP port, and to stop listening. While listening, a SyncRequestHandler implementation responds to an incoming request by opening the store with which synchronization is requested, constructing a Synchronizer appropriate to handle the request, and activating the Synchronizer to operate asynchronously.

When SyncManager creates a Synchronizer to populate a SynchronizerGroup it is constructing, or when a SyncRequestHandler creates a Synchronizer to handle a remote synchronization request, the Synchronizer is constructed by a synchronizer factory. There may be several synchronizer-factory classes installed on a device, each implementing the SynchronizerFactory interface and each typically constructing instances of a different Synchronizer implementation class. Each installed factory is invoked, in some preconfigured order, to attempt to construct a Synchronizer appropriate for the available transports and the SyncStore and replica to be synchronized, until one of the factories succeeds in constructing a Synchronizer instance.

Security

Security of information in mobile devices is of critical importance to users and organizations that entrust their data to the device. Data synchronization needs secure access, secure storage, and secure communication.

The security requirements are specified in the MNCRS Security Specification.

Concurrency

With any distributed system, the behavior of concurrent processes must be understood and appropriate measures must be taken to prevent simultaneous modification by one thread of data that is being examined or modified by another thread. Concurrent accesses can arise as follows in the data-synchronization framework: The framework provides a straightforward mechanism for coarse-grained concurrency control and allows for fine-grained concurrency control through careful use of the concurrency-control primitives of the JavaTM language.

Coarse-grained concurrency control is obtained by opening a store for exclusive access. Once an application has obtained an exclusive SyncStore object, it is guaranteed that no other application, including a system synchronization utility, can access the store. Neither can a SyncRequestHandler access the store; any remote synchronization request received while the store is held exclusively will fail. If the application executes multiple threads, it is responsible for coordinating those threads. In particular, an application starts a concurrent thread every time it activates a Synchronizer, but use of the blocking style of synchronization can avoid the danger of concurrent accesses.

In many contexts, particularly on a server, it is unacceptable to reserve a store for exclusive access -- and thus to lock out remote synchronization requests -- for as long as the application needs the store. A SyncStore implementation is expected to coordinate concurrent access to the information it maintains about the objects it stores. The SyncStore methods must manipulate this information multi-thread-safe manner. However, a SyncStore implementation does not coordinate concurrent access to the Synchronizable objects it stores; that is the responsibility of the application classes implementing the Synchronizable interface. Application classes can prevent concurrent access to their data by the use of JavaTM synchronized methods and synchronized blocks. Both the methods invoked by the application and the Reconcilable methods invoked by a Synchronizer should guard against simultaneous access to an individual object by more than one thread. The same precautions that make it safe for an application to open a store nonexclusively make it safe for an application that opens a store exclusively to create multiple threads accessing the store.

Working-Group Members

Lonnie Hansen

Arkona

Henry Kings Ericsson
Yoshifumi Miyata Fujitsu
Yoshinori Kishimoto Hitachi Ltd.
Maria Butrico
Henry Chang
Norman Cohen (chair)
Apratim Purakayastha
IBM
Shinsuke Mitsuma
Hiroki Murata
IBM Japan
Jeremy Jones Lotus
Tetsuo Maeda Matsushita
Seiji Fujii
John Howard
Masahiro Kuroda
Hideaki Okada
Rioji Ono
Luosheng Peng
Mariko Yoshida
Mitsubishi
Ken Chan Nortel
Rafiul Ahad
Jiader Day
Oracle
Takao Ikoma Sharp
Teck Yang Lee
Brian Raymor
Roger Riggs (editor)
Sun Microsystems Inc.
Hidekazu Izumi
Satoshi Hoshina
Tetsuro Muranaga
Toshiba