Re: RSync like diff for incremental stuff

Denis Corbin a écrit :
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Hello,
>
> Cyril Russo wrote:
>   
>> Sterling Windmill a écrit :
>>     
>>> Have you tried rdiff-backup ?
>>>       
>> Yes
>> And, even better, duplicity.
>>
>> However, all thoses software still lack a major technical feature.
>> rdiff-backup doesn't compress (unless you have gzip-rsyncable) nor 
>> encrypt, so it's useless if you don't master/trust the remote host location.
>> duplicity compress and encrypt and use rsync, but it uses TAR 
>> internally, so browsing a backup is a real pain (as there isn't any 
>> catalog in the archive itself it's very very slow).
>> Duplicity comes with a real giant list of backend for accessing remote 
>> storage (from sshfs, imap, webdav, ftp, S3, tahoe, local, etc...).
>>
>> I though about an ultimate backup tool that would use the smartness of 
>> DAR (catalog / compression / encryption / incremental), but with a 
>> optimal disk consumption (thanks to rsync).
>> That way, browsing the backup set would still be very fast.
>>
>> I think the unix philosophy of "One tools does one thing well", I would 
>> let DAR create a local backup archive on a remote mounted filesystem 
>> (like NFS, SSHFS, WebdavFS etc...).
>>
>> Anyway, how complex would it require to implement in DAR ?
>>     
>
> First, to be able to make a binary diff you must have the original
> binary beside the current one to compare them (actually dar relies on
> inode data changes to decide whether to save the whole file again or to
> not save it at all).
>   
Well, this is not exact, and it's one of the main feature of the librsync.
The librsync create a signature file from a binary file, and you 
can(should) use this signature as the first comparand.
The signature itself is very small, compared to the file -usually only 
1% but can be less-
Other the incremental backup, you only have to update the signature.

> Consequences is that this is not compatible with differential backup
> based on catalogue, the feature must thus be an option.
>   
If the signature is stored in the catalog, I think it might be compatible.
> Worse it is will be difficult to base such a backup on a differential
> backup. Suppose the file is already binary diffed ... how to know if the
> part of the file that is not present in the file has changed? Yes, using
>  signatures (or ~ CRC) but still the risk that the file changed and
> signature stays the same thus changed would not be saved.
>   
Signature algorithm use 2 different checksums (strong and rolling).
The rolling checksum is a checksum that can detect byte shift (insertion 
or deletion in the block).
The strong checksum (SHA-256, SHA1, or even MD5) is used when the 
rolling checksum matched.
So, it's pretty unlikely that SHA256 would be the same (probability is 
1/2^128) but it could happen.
It's pretty unlikely that the rolling checksum match for 2 different 
inputs (probablility is 1/2^32 for a 64bit rolling checksum).
However, it's very very uncommon that both would give the same results.
Worst, as the strong checksum is done on a fixed block size, this would 
mean that only that block gone unnotified,
(so no byte was ever added, nor removed, else the other blocks will have 
changed too and will unlikely go unnoticed). 

As RSync is widely used for binary linux distribution (with data > 
100GB), I guess it's not a real issue in our real world.
Gentoo use this, YUM (Fedora, Mandriva, Moblin, OpenSuse) use this, so 
I'm pretty confident that this doesn't happen at all.
> The second point is that at restoration time you must not blindly patch
> an existing binary file with the portion of data that have been saved.
> The use of signature (CRC for example) done on the original file is
> necessary, but will not warranty that the original file is the really
> the same as the one over which the binary diff has been made (there is
> still a little chance that two different files get the same signature)
> and I don't see any mean to be sure that the live file to restore over a
> binary diff is exactly the same suite of byte as the one used at backup
> time, except than comparing byte by byte, thus requiring any previous
> diff backup up to the first where the whole data is present. But now, if
> the user is warned about this risk and wants to take it ... I see no
> problem.
>   
Yes, I agree with you here.
Restoring an incremental backup here requires all the backup chain (from 
the last full backup till the last incremental version).
BTW, this wouldn't be way slower than it is currently, as current code 
store the whole file, so it has to decrypt(decompress(whole file)) for 
the last incremental.
If you get the wrong version (at you must have decompressed the whole 
file to see its content), then you have to reproduce the above procedure 
for each version.
And, unless you exactly know what time you made a mistake, you usually 
check 2 or 3 version before finding what you were looking for.

The new code would 
(undiff(decrypt(decompress(orig_file)))^number_incremental).
This means that, once you've decompressed the original file, going from 
one version to the other is only a diff (which is O(1) operation), so 
it's faster than the current code.
You can even compute the diff with the current file, if it still exist, 
and avoid the first (longer) step, and go backward.
Then going from one version to the other is a O(1) operation, so it's 
faster than the whole decompression again.


> This was for the functional level.
>
> Seen now the implementation, this should be feasable, but at the cost of
> some major change in the way dar stores files. We must now not only
> store a suite of bytes to be copied to a brand new file, but a list of
> blocks with offset, length and data (an probably checksum). Well, there
> is a feature in the pipe that will bring some changes at this level
> which is the possibility to properly store sparse files [
> https://sourceforge.net/tracker/?func=detail&aid=1457710&group_id=65612&atid=511615
> ]. I could extend a little bit this feature to let room for CRC fields
> and the like (re-using the TLV class).
>   
CRC is one thing that get the bad habit of colliding.
Please store the rsync signature in there, as you'll get (for the same 
price) both a rolling checksum, and a strong checksum.
Even better, add a PAR block (see http://en.wikipedia.org/wiki/Parchive 
, so if you ever get a corruption, it can be restored)
> Will lack the algorithm to inspect binary files and decide which way to
> define blocks of changed data. The problem here is that it will cost
> much more disk I/O to compare two binaries: It must first be necessary
> to inspect the whole files (old backup and live filesystem) to find out
> which amount of data has changed and which pattern do changes follow. It
> may well be more costly to systematically do a diff in place of a full
> backup if a byte every N byte has changed for example. Then, we could
> proceed either to full backup or binary diff backup.
>   
Please try to read the rsync algorithm as it's very very clever ( 
http://en.wikipedia.org/wiki/Rsync ). Basicly, the rsync algorithm is 
O(N) to figure out the diff.
Using a signature (as said above), you don't need to read the previous 
file at all, and you only need to read the new file *once*, so it's 
exactly like the current code in fact.
Even better, the system will be faster as you won't be compressing / 
encrypting the unchanged data, so the time you loose reading the small 
signature file (usually 1% of the original file size), is highly 
compensated by *not* compressing the redundant data.
The amount of I/O will be less too (as you store less compressed block 
on the FS), so you'll gain in network or disk bandwidth.

In fact, rsync usually provides a 2x to 16x speedup other gzipping the 
whole file for example (try to run a rsync test, you'll see by yourself).

Sure, if the rsync diff size > input size, then it's better to perform a 
full backup. This never happen in reality.
I guess a better rule of thumb would be: if rsync_diff_size + 
signature_size > input_size, then it might worth the full backup.

Cyril



------------------------------------------------------------------------------
Crystal Reports - New Free Runtime and 30 Day Trial
Check out the new simplified licensing option that enables unlimited
royalty-free distribution of the report engine for externally facing 
server and web deployment.
http://p.sf.net/sfu/businessobjects
_______________________________________________
Dar-discussions mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/dar-discussions