Re: diff compression

> From: Denis Corbin
> Sent: Sunday, May 03, 2015 12:51 PM

Hi,

> OK, sorry for my misunderstanding.  This is also because I do not have
> much time left to dig myself this technology in order to better
> understand how it works. So I took some time today to partially reduce
> my ignorance :)

Thanks for taking the time to review my proposal in detail.

> Yes, that's a well designed API. However I see two routines that are
> missing for my need:
> - - the ability before applying a patch to check that the file can
> receive that patch. I would avoid having bother renaming a file to a
> temporary name (with the conflict of name to resolve) and/or also
> avoid wasting space in particular for huge file when comes the time to
> duplicate it to patch it and be able to return to the original state
> in case the file does not match the patch.

The file needs to be renamed. You cannot overwrite the original file because
some blocks might be moved down towards the end of the file and needed later
when already overwritten by the destination process...
The API currently expects a seekable read handle for the source file so that
it can properly arrange the blocks in the destination file.

The last time I looked at the librsync code, it held a list of matching
block hashes in a linked list or some similar structure.
Take for example a file, that has the same block no. 5 and block 200. When
building a delta, the algorithm will take the first matching block, so both
blocks 5 and 200 will be built from the same source (block 5 or 200,
depending on the order of the list), even when they're both the same as the
source file (no change). I think (I'd have to check my code) I have made
some improvements to the algorithm so that it directly checks the matching
block first and then searches the list of matching hashes. This also
optimizes the delta, as copy operations can be joined together (for
instance, have copy blocks 199-202, instead of: copy 199, copy 5, copy
201-202). But then again, this is implementation detail that I should
discuss with upstream :)
I found this little detail when building a delta of the file itself. I
expected a small delta (copy 0-end), but instead found a quite large list of
operations and was trying to determine why that has happened.

Also doing any kind of checking on the source file would undoubtedly extend
the extract operation as this huge file would need to be read entirely and
checksummed.
Unless running on some kind of cow snapshot filesystem, I believe renaming
and building a new file is the best course of action...it's a one shot deal
I'm afraid, either we get the file we want in the end or not :)

> - - the ability to check a path applied to the correct (but not
> available file) would result in the file currently living in the
> filesystem.

I'm not sure I fully understand this requirement. A delta only stores
differences. If the source file is not available, then information is lost
and destination file cannot be recovered.
However, dar knows the crc of the destination file...if this is infact the
file currently residing on  the filesystem, dar would know (but this would
again mean checksumming the file before applying the delta....). Perhaps...
if dar stores crcs of both, the original file (that crc can be retrieved
from the reference catalog and stored in the incremental) and the
destination file (the crc which is already stored), then dar can both know
if the file on the filesystem is the correct file to apply the delta to, or
by some weird chance, already the correct destination file. If neither, then
restoring the delta won't help. Or the other way around...if restoring delta
fails, then dar can check if by some chance, it already had the correct
file.

> right, delta signature dropped in memory buffer while the file is
> being saved / compressed / encrypted / sliced into dar archive, then
> drop the signature from memory into the archive. The corresponding
> entry of the catalogue would have a new entry to point to the offset
> of the delta signature, which could be set to zero indicating it does
> not have delta signature.

A flag, similar to stored EA might be a better solution than zero offset, as
that would not inflate catalogues without the signatures.
You would have to take into account, that out of many files in a dar
archive, only a few larger ones could have stored checksums. This way, the
catalogue is not needlessly enlarged by zero offsets. The EA flag itself has
many bits left unused.... :)

> 
> Right. Also a new tape mark type would be necessary to be inserted
> before signature to allow sequential reading of the archive...

Yup :)

> Well, there is a difference however, the bzip2 data is standalone it
> does not need to read from the filesystem to recreate the
> "uncompressed" data based what's also stored inside the archive
> (signature). But OK, I agree that there is no need to complicate :)

Yes, this is exactly why dar needs to be modified :)
If it was just another compression method, it would have been easy...

There are 3 operations that need to be considered:

1. creating a new full archive:
 - needs 1 input (the file in question) and produces 2 outputs (file data -
which should then be compressed normally, and signature data)

2. creating an incremental archive:
 - needs 2 inputs (the file in question and the signature from the reference
archive) and produces 2 outputs (delta data - which should then be
compressed, and signature data)

3. "extracting" the archive
 - needs 2 inputs (the delta, and the original filesystem file) and produces
1 output (the destination file, hopefully)

Steps 1 & 2 are variations, depending if a full or an incremental backup is
in effect.

[...]

> Yes, but how to prevent loosing the live file at restoration time if
> the path cannot be applied to it? Can it be reverted? Can it be
> checked before applied?

That's why the old file is renamed.
If the delta cannot be restored, it is renamed back to the original name.

> There is points that still has to be addressed in regard to other
> features:
> - - dar_manager: has to be modified to consider not only the last
> version of a file to remove but all the previous one to be applied the
> delta to one after the other... this is a significative work seen the
> current implementation... and can be done at a later time, right
> dar_manager would just refuse to be fed with archive having rsync
> signatures...

I would be happy if not all features are available at the beginning.
The requirement of having the destination file seekable (in order to arrange
blocks that have changed), this also means that the file can't be
chain-restored (in the sense of restoring multiple chain of dars, with the
first having the first revision of the file and all the later ones stored
deltas). Each dar file needs to be restored individually with the applying
delta before continuing. Yes, this would sacrifice some extraction speed
with a more efficient storage requirements.

> - - archive difference: how to compare a signature with a existing file
> to see whether the resulting patch of signature would match that file?

I'm not sure I fully understand where this would be needed?
If another signature is made out of an existing file, and that file would be
the same as a stored file, then the signatures would by definition be the
same. But so would the CRCs...

> Last, some more general interrogations:
> - - Has the signature to be compressed or is it a waste of CPU cycle?
> (already compressed or poorly compressable data?)

Any file reasonably filled with data will have blocks with pretty random
distribution of hashes. The signature is therefore poorly compressable.
There might be some exceptions, like blocks of same (same, not similar) data
that would produce the same hashes. Sparse files would be one case...but, if
they're handled before the delta compression on the sparse layer, then the
signature is both smaller and again more random :)

So I don't see much sense in compressing the signatures. There might be some
reason to store crc of the signatures, but then again, if the signature is
corrupted in the reference archive, that means that the delta will be larger
(since block signature won't match), I highly doubt that the signature hash
could randomly corrupt in such a way that it would find a valid block in the
source file... The only advantage I see is if compressing signatures would
also implicitly store the crc, without the need to handle it separately.

Regards, gulikoza



------------------------------------------------------------------------------
One dashboard for servers and applications across Physical-Virtual-Cloud 
Widest out-of-the-box monitoring support with 50+ applications
Performance metrics, stats and reports that give you Actionable Insights
Deep dive visibility with transaction tracing using APM Insight.
http://ad.doubleclick.net/ddm/clk/290420510;117567292;y