Efficient Synchronization of Distributed
Directories with nsync

Data Management

Data management plays an important role in efficient cluster and grid computing. One of its aspects is the distribution and synchronization of collections of files.

Sample Configuration File:

<nsync_config>
   <repositorysystem name="Repo" pattern="^.*\.c$">
     <node host="Host_A" path="/home/username/test/"/>
     <node host="Host_B" path="/home/username/test/"/>
   </repositorysystem>
</nsync_config>

In nsync the synchronization of a repository system is based on pairwise synchronization, composed to a synchronization of the whole system. Updates can be performed concurrently on any repository.

Optimized Pairwise Synchronisation

rsync allows to synchronize two files on different hosts without transmitting an entire file. This algorithm is used by nsync in case of low bandwidth connections. For new files nsync uses copy or compressed copy.

Algorithm of Rsync

Performance Comparision

	network bandwidth
	160KBits	864KBits	100MBits
copy	-	699.7s	13.6s
rsync	252.8s	111.1s	26.8s
copy + compression	1021.9s	218.4s	20.6
rsync + compression	150.4s	73.8s	25.2s

Host_B: 70MB Source
copy: Host_A is empty
rsync: Host_A 70MB Source; Host_B + 2MB Patch

Compositions based on Gossip

Compositions of pairwise synchronizations for basic topologies can be derived from the gossip problem. The solutions of the gossip problem are all-to-all communica- tions with minimal number of steps (parallel communication rounds). For complete graphs with n nodes it takes log n steps.

Topology Adaptive Compositions

The pairwise synchronizations are composed to a synchronization of the whole system. The quality of this composition determines directly the runtime of the synchronization.

Example: Low Bandwidth

normal gossip	improved strategy
Total Sync Time:	Total Sync Time:
1280s + 1280s	1280s + 0.8s + 0.8s
	use low bandwidth link as less as possible

Example: High Bandwidth

Total Sync Time: 2.4s (normal) +4.8s +4.8s --------- 12.0s
Total Sync Time: 2.4s +2.4s start local distr. as +2.4s soon as possible +2.4s --------- 9.6s

References

More Details on nsync

General

Current developments in high energy physics show that the management of large datasets plays an important role. For the DataGrid project it is necessary to distribute large datasets over several computing centers all over Europe and to synchronize these datasets. Within clusters tools for efficient synchronization and distribution of data become more important, too.

For nsync, a method to synchronize distributed directory structures was developed and implemented which makes it possible to perform independent changes to arbitrary repositories simultaneously. This method needs no central instance and therefore the system achieves a better scalability than many existing systems. Knowledge from graph theory was used and improved to take the network topology and the network bandwidth between the computers into account. By using offline synchronization, changes will only be propagated when the user initiates it. This can be reasonable after a completed transaction which consists of changes on several files.

nsync is written in C++.

Papers

T. Schütt, F. Schintke, A. Reinefeld:

Efficient Synchronization of Replicated Data in Distributed Systems.

Intl. Conf. on Computational Science ICCS 2003, Springer LNCS 2657, pp. 274-283, June 2003. © Springer-Verlag.

(bib, pdf)

Thorsten Schütt (Diploma-Thesis):

Synchronisation von verteilten Verzeichnisstrukturen March 2002.

Related Work