Logical Transaction Based Pervasync Sync Engine

A traditional replication system is symmetric and each node contains a full-set data, while a synchronization system is asymmetric and the client nodes contain sub-sets of the data on central server. The asymmetry, together with the instability introduced with large number of nodes, calls for a different approach than propagating physical transactions among all nodes, as used in replication.

Instead of using physical transactions, database synchronization can be carried out by exchanging logical transactions between the devices and the central server. Devices do not interact with each other directly. Instead, devices only interact with the server. The logical transaction is the result of the physical transactions. At the heart of a successful sync solution is a sync engine that computes the logical transaction in a fast and scalable way.

Logical Transactions


Figure 3 Synchronization Is Composed Of the Check In And Refresh Of Logical Transactions

In a server centric synchronization system, the server database is the single source of truth. Physical transactions applied on the central database are final. In contrast, device database serves as a cache of a sub-set of central database data. Physical transactions applied on the device database are tentative until they are checked in to the central database. At check in time, the changes committed by all the local physical transactions form a single logical transaction, which is applied directly to only the central database, not directly to other devices. The checking in of logical transactions in the sync system is just like the committing of user physical transactions in a single DB system.

In Fig. 3 we show the synchronization process of the client and server databases. During the initialization, the row-subsetting SQL query is executed on the server and the result set is downloaded to the device. Now the client data and the corresponding server sub-set of data are consistent with each other. In the figure the subset include <PK_2>, <PK_3>, <PK_5> and <PK_6>. <PK_1> and <PK_4> do not exist yet and <PK_7> through <PK_9> are outside of the subset.

Then the device application makes changes to the local database by committing physical transactions. The local changes are recorded in the form of Data Manipulation Language (DML) operations on the table rows, which include inserts, deletes and updates. At check-in time, these DML operations form a client side logical transaction, which has the following properties.

  • State based. It is the result of the one or more local physical transactions. The physical transactions bring the subset data from an old state to a new state so the logical transaction can be seen as computed from the differences between the new and old states.
  • DML merged. The original DML operations in the physical transaction may be merged in the logical transaction. For example, an insert followed by an update will be merged as an insert.
  • DML re-ordered. The order of the DML operations in the logical transaction may be different from the original ones. We arrange the DML order in a way to minimize the chances of database integrity violations at check in time, e.g. referential constraints.
  • Tentative. The logical transaction may fail to apply on server due to conflicts or other reasons. It can be modified by new client local transactions, by conflict resolution rules on server, or by force refreshing it with server changes, so that it can be checked-in successfully and become permanent. Before checked-in, the affected rows are in a temporary (tentative) state.

NOTE: The device application needs to handle not only the success/failure of the local physical transactions, but also that of the logical transactions. For example, if a check-in fails, it should try to modify the logical transaction and retry. A good synchronization infrastructure should give application the access to the logical transaction. Application can in turn expose the logical transaction and check-in process to end-users or handle it using some pre-existing logic.

The server can also generate logical transactions to refresh device data from an old state to a new state so that the whole system will be consistent. The refreshing transactions are logical transactions too, which have the following properties.

  • State based. It is the result of the one or more physical transactions occurred on the server, which can be transactions committed by server side applications or transactions committed by other devices through the “check-in” process. The logical transaction is computed from the differences between the new and old states of the subsets.
  • DML merged. The original DML operations in the physical transaction may be merged or changed in the logical transaction.
  • DML re-ordered. The order of the DML operations in the logical transaction may be different from the original ones.
  • Preemptive. The server side logical transaction should be applied to device database forcefully. That is to say, if there are any conflicts, the changes on device will be overwritten by server side changes.

Conflict Resolution During Check-In

When a device is generating changes to the local subset data, other devices or server side applications may be changing copies of the same data on the server. This could result in conflicts. To help detect conflicts, we assign version numbers to rows. If a server row still has the same version number since last sync, then we know it hasn’t been modified by others and there is no conflict.

If a conflict is detected, there are configurable resolution schemes available to ignore client transaction or ignore the conflict.

Computation of Server Logical Transaction in Refresh

The data exchange between the server and the device is two-way. Check-in is the uploading of changes from client to server and Refresh is the downloading of changes from server to client.

Figuring out the server side changes for a device is a complicated process. It could become a bottleneck for sync performance. We cannot simply log the transactions on the whole table as done in replication schemes. What we need is the changes to the subset of data for a device, which is defined by the subsetting SQL query. Each unique set of the query parameter values corresponds to a subset of records. Changes made to the server side tables bring a subset from an old state to a new state. We need to compute the differences between the new and old states and wrap them into a logical transaction, then send them to the device and refresh the subset data on device to the new state.

In our implementation, for each base table, we create a companion log table to keep the DML operations made to the base table. We also create a companion state table to keep the states of all the data subsets. Each subset is identified by a unique parameter-value combination, and the state table contains the logical DML operations on the data subsets.

A sync engine that runs periodically in the background does the work of updating the state table. In each run, the refresh engine would identify the changed records and the associated DML operations. It then updates the state table with this information and assigns the changed records a new state number. The algorithm is as follows.

For each subset

 

  • Delete: if a record is in the state table subset but not in the current SQL query result set, mark it as “delete” in state table.
  • Insert: if a record is in the current SQL query result set but not in the state table subset, insert it to the state table and mark it as “insert”.
  • Update: if a record is in all of the following three tables: the state table subset, the current SQL query result set and the base table’s new logs, mark it as “update” in state table.

Note that our algorithm produces logical insert and delete operations. For example, suppose we have a TASKS table that has a user column for task owners. We could use user column in the subsetting of the tasks table so that each user only gets the tasks he or she owns. Now, if we update a task record to change the user from user1 to user2, user1 would get a logical delete operation to his subset and user2 would get a logical insert operation to his subset. This re-assignment type of operations is quite common in real-world applications and our algorithm handles it very well. Traditional replication schemes, which use original physical transactions, wouldn’t be able to handle this.

Note that data subsetting is essential to Pervasive Computing, which is based on user, location and device dependent data management. At sync time, device brings in the state number of its subset and downloads the records that have a newer state number. For records marked with a delete operation, we would only download the primary keys.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s