Re: diff compression

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

On 30/04/2015 08:09, gulikoza wrote:
> Hello,

Hello,

> 
> I love dar, but it has become increasingly difficult to manage
> backups with it as filesize grows. Doing an incremental backup of a
> moderately busy imap server will create the same size backup as a
> full backup although in reality, probably not that much has
> changed.
> 
> I have read the existing discussions about xdelta usage (and
> sourceforge req. 138 and 122) and understand some of the concerns. 
> I have done some research last year with librsync 
> (https://github.com/librsync/librsync) and modified it a bit to
> create delta backups of PST Outlook files on my Windows machines. I
> believe the same concept could be used with dar, with a rather
> simple extension.

A difference between rsync and dar is that rsync always has access to
the original file when it remote syncs, while dar has not, it only
relies on the catalogue, which in brief is the inode information plus
a CRC. Even if it can be expanded by additional data, like many CRC,
one per block, this is not the same as having the original *and* the
modified data to proceed to binary diff or rolling checksum.

> 
> A new layer 'delta' compression would be added. When creating
> archives, dar would also store signatures (block checksums) of the
> files sufficiently large (new option: min-size to store signature
> along with the file). Now, the exact location of the signatures
> would need to be determined. They are too big to store in the
> catalog,

absolutely,

> but there would be a need to create an isolated 'catalog +
> signatures' dar from the full archive. Perhaps they could be
> escaped and stored after the file data,

that's probably the best place, after or beside each block of data.

> much like the escape catalog, along with the sig offset stored in
> the catalog?

More precisely, rather at the same level of the sparse file
datastructure which is inlined withing data of files.

> 
> So when dar is creating a backup, it stores file data (or the diff
> already!) in the backup and is creating the signature in RAM. After
> the file data, the signature is dumped into dar.

having a single signature per file is not much change to what is
actually done (a variable sized CRC per file).

> Doing an incremental backup, dar reads signatures from the
> reference archive, computes and stores the delta (instead of full
> data) along with the signature of the file currently on the
> filesystem.

from a single signature, I cannot see how you can detect something
else that the file has changed, you cannot determine which
bytes/blocks have changed, right? I suspect you mean a set of
signatures one per block of the file and this has a proportionnal
memory requirement to the size of the current file and inversary
proportionnal to the size used for the blocks.

> No incremental backup needs original file data, only the signature
> stored in the reference archive. If the signature is not present,
> it stores full data the
same as
> now ('null' delta compression :-)).

So If I understand well your idea:
- - this set of signature would be stored outside the catalog and beside
the data for normal backup (full or differential backup). For isolated
catalogue, the resulting archive would contain not only the catalogue
as of today but also the set of signatures for each saved file.

- - For full backup, nothing changes except that data of each file is
split in block (of user defined size) which is appended a signature.

- - when isolating a catalogue, dar gather the signatures of each file
and the catalogue into a new archive (today only the catalogue is
retrieved).

- - When doing a incremental backup, for each file, dar compaires the
signatures of each blocks with what it can find on filesystem and
saved only the data of the block that changed. it also keeps the
signature of blocks that have not changed as well as the previous
signature of blocks that changed and computes the new signatures of
the blocks that changed. (block that have changed have two signature,
the signature of the block they replace plus their own digest).

First remark: this operation requires reading possibly all slices of
the archive of reference all along the differential backup operation
(we have to fetch the signatures of each file we consider for backup).
This is anoying compared to today when once the catalogue of the
archive of reference has been loaded into memory, dar workflow is
simple read filesystem, compress, write down to archive.
Second remark: isolated catalogue would have their size increasing by
several magnitude, well I guess the increase in size here worth the
gain in space in archive of reference.


> 
> When extracting, if the catalog data indicates 'delta' compression,
> dar renames the original file present on the filesystem and begins
> building the

I would not say "dar rename" but "dar copies" (now it has to be chosen
a new filename that must not collid with another existing file...)

It could also be possible instead to check that the signatures of the
reference file match those of the one in filesystem and if so, restore
the modified blocks only.

> extracted file from the renamed file and stored delta (librsync
> requires random access to 'reference file', so it cannot be stored
> inside reference dar anyway). When finished, the crc is compared to
> the stored crc. If it doesn't match (either corrupted archive of
> wrong file present on the filesystem), inform the user, delete the
> 'garbage created' and rename back the original file that was
> present on the system. I don't see much need to further complicate
> this process. Delta compression would not be turned on by default
> and restoring an incremental backup already requires some
> knowledge from the user about the current state of filesystem and
> which incremental archive to start restoring (because of deleted
> files...). 'I'm sorry, but crc error has occurred while restoring
> your file, because you have used delta compression and not provided
> the right reference file' seems perfectly ok by me :-)

Ok, for that too.

> 
[...]
> 
> What do you think? Is it doable for 2.5 :-)

Well, the problem here is time, I've finished improving gnupg
signature (was a security issue that would weaken archive signature).
Now I have very low performance gain in the current multi-threaded
libdar so I have to work on that before release 2.5.0.

The dead line is having dar 2.5.0 released before the end of this year
with a pre-release phase that usually takes several months... and this
multi-threading feature that already eat a lot of time last year...

> 
> Regards, gulikoza
> 
> 

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

iQIVAwUBVUT+IggxsL0D2LGCAQLk8w//Xb9FrP1DsdKpGugnsF5wJB+3F9Zb2X/5
4rHkH+Ofaqg72sxpzo4RghZ1Y0MJKnutZhNtYRDj4+nwHUaJZI6dqtKo1Fmuh5Xt
4SZ5k1rmG38QfxeWEGzR+vKsDWHThaKOGVrjcvBbFIfMagrHWfJy+WDYLWeM95Da
XFaD1OqQuwQcJVB4lQBcU3MhaQ/hjCi7b5DbCvMWM2O5QfhWfLhaWCVyPyYiIt2h
P0mXRml2qKG0L0CnJjGuYq4C1/rWOe72anC2R6IZYx1Uzjk2ae/U/fLRb3H4u/xY
ZNgGpNmU3TAGkCsZ9Rw/BNjK+qnUSGD2LTrwQg0angD0DCqszOYHiA/ghGJ+Y9B6
stvPJLigUGbxK79bF6jLH5K11sIlDkgt2pYVPQIIxWQk9klcdLLe+hVCLVI2wwbd
RlBiDuHkjcd/ig1yeun4yhy0jqG6SeH+OuxL494Oq2ofBYJfVlJ9632DunqJhRuU
HbEk3Kf7Db1sLrrNmVj2oac4saKtdBr+yaNLrAfCLpLSfgs+yMZRjsLlaicJIBsz
vewjLX+AMjLNpnNs4wM/kXRXFVgMZGQBWGSI46DKNYctMoKY+f5tf14OlpK5faGN
poEfhtln2gW6O18Nx2BNiBnGc13ptvq89Jdhv8dX5xklXZkwEDpu0PGq3MwiiaR9
0tRIAGQC/2A=
=w5Ev
-----END PGP SIGNATURE-----

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