Re: Asking for comments on a dar's future implementation

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


Hello Cyril,

Thanks for your contribution. Yesterday I have been searching the
archive for past discussions in dar mailing-lists, but could not find
the one we had about which I still have some souvenirs, [now I remember
it was about binary diff, while I simply looked for checksum/CRC/data
protection]. Thanks for signaling this solution again.

Yes, this is a very interesting idea. Looking at wikipedia and other
sources on the web, I found some interesting keys about this algorithm,
however still remains some points I probably don't clearly understand:

In the following I mean by X1, X2, ..., Xn the bytes to protect, where n
is a strict positive integer. By w (where 1 < w < n) I mean the number
of bytes a checksum is calculated on. And for any i where 0 < i < n,
s(i) is the rolling checksum of bytes Xi, X(i+1), ... X(i+w-1)

What I understand in the "rolling" checksum is that for any i where 0 <
i < n, knowing the checksum s(i), and the byte X(i+w) it is very easy to
get s(i+1) [byte out of the sequence (which index is greater than 'n')
being given the value zero]

But, is is correct to say that, for any consecutive block of w bytes I
have to keep a rolling checksum? Else I am not able to detect anything
corruption passed this block of w bytes?

However I see no very CPU gain at backup time in calculating the rolling
checksum slided byte by byte, rather than calculating a single checksum
for each block of w bytes. Is that correct too?

Is it also correct to say that: at the opposite, for data verification,
it is important to calculate the rolling checksum sliding it byte by
byte and comparing it, each w bytes, to the stored checksums?

If all these statements are true, the amount of information to keep for
a file is proportional to the file size (a checksum for each w bytes for
example), right?

Thanks for validating theses points.

Kind Regards,
Denis.


Cyril Russo wrote:
> >
>> >> Hi,
> >
>> >>    What about using a rolling checksum algorithm here ?
>> >> It doesn't have to be dependent on file size, and would allow very
fast
>> >> file difference computation (I highly advise you to read about rolling
>> >> checksum).
>> >> The basic idea of the rolling checksum is that for every file you're
>> >> checksuming, the file is analysed as a sliding windows (for every new
>> >> byte read, it changes the checksum, and the new checksum contains the
>> >> signature of all the previous bytes, so it's possible to locate
where a
>> >> byte was corrupted/changed, while with a classical checksum you
can't).
>> >> By the way, using rolling checksum would allow rsync-like difference
>> >> computing and this would really reduce the file size to the exact
>> >> modified bytes in incremental archiving.
> >
>> >> I don't think there is a plausible relation between error rate and
hash
>> >> size. Whatever the size, hash collision are very rare.
>> >> However the probability of collision can't be related to the media
error
>> >> rate.
> >
>> >> Best regards,



-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFLcUuMpC5CI8gYGlIRAp20AKC3RRknhMdQDJhWeuEB2mWpBdvJ3gCfQ5Hc
2bn85d3kKcHtsGfM61or8GY=
=1hqV
-----END PGP SIGNATURE-----

------------------------------------------------------------------------------
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