S-Rsync: An Efficient Differencing Algorithm with Locally Chunk Digests Generating for File Synchronization Services

摘要

Data synchronization among different clients is common place in the information era. Ideally, we expect that the synchronization process transmits less data and achieves lower response time. To meet these requirements, synchronization systems usually employ differencing algorithms to reduce the volume of data to be synchronized. Rsync is a typical algorithm of this type, which is used widely. However, for the file synchronization services adopting Rsync, the server may always busy for generating chunk digests, which probably will be the bottleneck. We propose an improved differencing algorithm called S-Rsync. S-Rsync migrates a portion of computation from server to client by taking use of the duplication mechanism. This optimization not only eases the server, but also reduces the amount of data to transmit. As a result, synchronization system using S-Rsync algorithm achieves lower response time. Based on the rationale described above, we further improve S-Rsync in term of both spatial and time complexities. Correspondingly, we propose a dynamical selection scheme, which selects a proper algorithm between S-Rsync and Rsync depending on maintaining the versions of files. We construct a prototype to evaluate our proposed algorithm. The experimental results show that our algorithm outperforms Rsync constantly abstract environment.