Re: RSync like diff for incremental stuff

On 2009-06-13, Cyril Russo <[email protected]> wrote:

Hi,

>   I'm wondering if DAR could use rsync like system for incremental backup.
> Currently, if I want to backup my mail file (3GB) that changes hourly, 
> it back it up everytime it's run (and the whole 3GB).

a 3 gb mbox file sounds scary. Why don't you use the maildir mailbox
format? With this format each mail is saved into a separate file. Thus
it is well suited for backup purposes.

> With a rsync like algorithm, it would have saved only the difference 
> (which is not that much, something like 10MB).

10 MB for 3 GB?

> Usually rsync requires 2 copies of the file (the "previous file" and the 
> "new file"), in order to find out the difference.
> This is an annoying requirement for an archive format, as the "previous 
> file" is usually compressed / encrypted, and as such, would require too 
> much CPU to uncompress / decrypt for comparing.

> However, librsync has a mechanism to compute a "signature" of a file, 
> and this signature is used in place of the "previous file". The 
> signature itself is very small (compared to the file), so it might be 
> possible to store such signature in the catalog.
> The signature is compared to the "new file", and the diff can be made 
> from this (so in my previous example, only 10MB of data would be stored 
> in the backup).

Computing the diff for each incremental backup is a O(n^2) operation,
where n is the file length.

> Upon restoring however, the whole chain of backup must be read (as the 
> final file is made of original_file + diff(s)).
> As restoring happen very rarely, I don't think it's a problem, as the 
> space gained by using diff worth the extra CPU time.

Plus a lot of extra I/O time, since for big files it is likely, that the
original_file has to be restored to disk and O(n) diffs have to be
applied to this file, i.e. requiring O(nm) IO-Operations, where m is
the number of IO operations used to create original_file.

> That way, the DAR format would really, really fit all the possible 
> requirement for a backup tool, as it would be optimal in size (rsync 
> like algorithm), optimal in speed (binary code), optimal in security 
> (encryption).

> What do you think about this ?

I am rating the fact that dar does not support a rsync like operation as
a feature! If you use a Unix-like operating system then you get reliable
modification times for your files, thus there is no need to do very
costly checksum computations to see which files have to be backed up.

I used rsync for some time to backup a home directory, since the rsync
algorithm sounds attractive. In practice my usage of my home directory
was so 'strange' that one rsync run was like 2 times as long as just
tar-ing everything away! I.e. my usage pattern seemed to confuse the
complex rsync rolling checksum etc. heuristic algorithm.

Best regards
Georg


------------------------------------------------------------------------------
The Planet: dedicated and managed hosting, cloud storage, colocation
Stay online with enterprise data centers and the best network in the business
Choose flexible plans and management services without long-term contracts
Personal 24x7 support from experience hosting pros just a phone call away.
http://p.sf.net/sfu/theplanet-com