Thank you very much for your suggestions. I was more after help on replacing rsync than my application. It was only ment to serve as background. Simplified I want to do something like:

rsync-copy --source /path/file --template remote:/pool/<old_checksum> --target remote:/pool/`md5sum /path/file`

for many files. The goal is to create a centralized smart backup application (e. g. for home use). Think of a full backup as fast as "updatedb" on Linux/Unix. It has to work across low bandwith links, e. g. analog phone lines. I want to exploit the fact that many clients share most data in different locations. That's mostly operating system and applications. Clients are too dissimilar for simple imaging. They share 90% of data across the same OS distribution.

I don't have many details about file count on server (1e6 different checksums?), number of clients (1e3 ?) or distribution of file sizes. Despite the large numbers, server DB scalability, performance and disk space should not be a major issue. One DB on the client scales well. Of course the client needs to do 99% of the work.