Intermittently Synchronized Databases

Architectural Description

Many modern mobile database systems operate while disconnected from the server. In such systems, clients must explictly synchronize their states. One way to do this is by asynchronously exchanging updates packaged in update files. Clients occasionally package accumulated updates into update files, which are transmitted to a file server when a network connection is established. The server regularly checks the file server for update files, and installs their contents into the database. The server subsequently prepares more update files containing these changes for clients to download. Figure 1 summarizes the cycle of data through the mobile database architecture.

Mobile Database Architecture.

Problem Description

Among the performance problems with the architecture described above is its inability to scale. In generating the update files for N clients, the server must consider O(N) updates (because the volume of updates is proportional to the number of clients) for each of the N clients. It therefore must do O(N²) work to generate update files.

Second, as the client population grows, so does the load on the file server. As single-server queuing theory suggests, the server will not be able to keep up with demand. In fact, the per-client performance of the file server will decrease with demand. The file server, therefore, cannot scale.

Third, the way that update files are installed into the primary database in inefficient. It is currently done on a first-come-first-serve (FCFS) basis. This is inefficient for many reasons. First of all, FCFS likely leads to random accesses of the database, which results in low-level inefficiencies. The disk arm has to do many seeks, and the system cache in underutilized. Second of all, many of the updates performed on the database are likely to be undone or overwritten by subsequent operations.

Recent Publications*

Scalable Synchronization of Intermittently Connected Database Clients, 2005 Mobile Data Management Conference [PDF]

*For more related publications, please see my CV.