Re: diff compression

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

On 02/05/2015 20:38, gulikoza wrote:
> Hi,

Hi,

> 
>> 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.
> 
> This is how librsync works. It builds a binary diff/delta not 
> against the original file, but a "signature" file (I'm sorry if I 
> wasn't clear earlier, but when I wrote signature, I meant librsync 
> signature that is a file made of 32-bit crc + 256-bit blake2 block 
> hashes created from the original file; only this "signature" file 
> is needed when creating a diff).

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

> Librsync has a pretty simple C interface that can be used in a
> loop with a memory buffer to create signature, binary diff or the 
> resulting file (with the diff and original file as inputs).

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 ability to check a path applied to the correct (but not
available file) would result in the file currently living in the
filesystem.

> 
>> More precisely, rather at the same level of the sparse file 
>> datastructure which is inlined withing data of files.
> 
> I don't like that very much :)

now, seen the API, I understand this was a wrong idea! :)

> It modifies original data with escape sequences and requires
> entire file data to be decompressed and checked for escape
> sequences (I wrote my handler for that just a few days ago, so I
> don't like it very much at the moment :)). While this may be
> necessary for sparse files, there is no need to inline file data
> with crc blocks, they are better stored outside...

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.

> 

[...]

> 
> As I mentioned later, preferably there would be a "third" archive 
> format: - archive with data (either full or incremental itself) + 
> all the signatures - isolated catalog (the same as now) - archive 
> with isolated catalog + signatures

Yes, why not, that's not difficult to implement, while I would not
make the first flavor, always the second. If the user has generated
signatures, this is for using them so if signature are present they
are kept beside the catalogue into the so called "isolated catalogue".

> 
> This can easily be achieved in the header. A header flag can 
> indicate if the catalogue contains signature offsets or not. Much 
> like EA.

Correct, this avoid manipulating the catalogue itself and keep having
it usable as backup of the internal catalogue of the archive of
origin. The header should have a flag to tell whether the catalogue is
alone in the archive or with signatures (or with signature and the
rest, thus a normal archive).

> 
> There needs to be an additional option to -C, that will allow dar 
> to strip the file data, but leave the signatures or (default)
> strip everything and leave only the catalog (as it is now).
> 
>> - - For full backup, nothing changes except that data of each 
>> file is split in block (of user defined size) which is appended
>> a signature.
> 
> My preference (I am somewhat aware of how dar stores data) would
> be to not to split original data (in the sense of "block of data"
> + crc, "block of data" + crc...) and having crcs interleaved with
> the original data, but instead write the block of signatures after
> the data in a separate entity.

yes, I agree.

> This way, this entity can be retained when isolating it from a
> full archive without having to decompress everything...If the
> catalog is extended to provide the offset of such entity, then the
> entire original archive does not need to be read, but instead it
> can be quickly isolated.

absolutely,

> 
> That would be similar to how EA's are stored, correct?

correct, having a pointer (the offset withing the archive) in each
entry of the catalogue (setting it to zero if no signature has to be
found in the archive for that entry).

> EA is dumped after the file data, with the offset and size stored 
> in the catalogue. So the signatures themselves would be more on
> the EA level, rather than on the "sparse" level.

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

[...]

> 
>> - - 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).
> 
> No, there is no need to complicate. That's why I suggested a new 
> layer in the first place. Imagine this as a new compression. When 
> you feed data to libbz2, you get bz2 compressed data and store
> that in dar. A flag is added that data is bz2 compressed. On 
> uncompressing, you read the flag, feed the data to libbz2 and get 
> uncompressed contents back.

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


[...]

> 
>> 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.
> 
> This is true, that's why I proposed an isolated "catalog + 
> signatures" archive. Any full archive that spans several slices 
> could be "isolated" into smaller catalog + signatures archive that 
> can be stored somewhere near the backup operation and reused for 
> the next incremental. After the need to create differential
> backups no longer exists, the signatures could be stripped and
> only isolated catalog can remain for the reference.

yes, that makes a lot of sens to your proposition to have two types of
isolated catalogues :)

> 
>> 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.
> 
> This is not how librsync works. Librsync creates a new file from 
> the old file and a binary delta. A binary delta is a binary file 
> with "instructions" how to create the final file.

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?

> 
> As it uses rolling crc, it cannot just restore individual blocks, 
> as these blocks might not be aligned between old and new file. 
> Imagine 1 byte has been inserted into new file, everything moves 
> down 1 byte. While this might be extremely expensive operation, it 
> happens (imap server will insert uid into message header, thus 
> rewriting entire mbox file). When restoring, you cannot simply 
> replace one block with the new contents as it will not match. A 
> binary delta might have the following ops stored for such a file:
> - copy contents 0 - 524 - insert literal string: "message uid: xxx"
> - copy contents 525 - end
> 
> This delta might be very small (3 ops, 5 offsets and the length of 
> a literal string).

OK

> 
> As this is already done (librsync) there's no need to reinvent the
>  wheel...only a new layer compression added, feed the data to 
> librsync, get it back, compress it (with existing bz2/lzma...) and 
> store it in dar :) On decompression, when dar flag indicates
> "delta compression" feed the data from the archive and the
> filesystem to librsync and write the resulting data to the
> destination directory :) A final crc check indicates if the file
> data was good or not. Which blocks failed or why (archive
> corruption or wrong reference file) cannot be determined.

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...
- - archive difference: how to compare a signature with a existing file
to see whether the resulting patch of signature would match that file?

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

> 
> Regards, gulikoza
> 
> 
> 


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

iQIVAwUBVUX9owgxsL0D2LGCAQLg1hAAhuhpQtbAdRZ4BAuEug1HhtXkFQGdmbln
VLtpwroY6uqf5+bNVBAFWgtB4mAgeFfEUKOKKwOQ1yxb04gaGY+cme+r9Jnt3bel
EQ7tbUod+vHnCiD4Zzcm0Rh4O9O4OknAB37rLvGMC/2v7SDQuq3EjaZeyaEMEllT
Wr86vr+cVYVcUd+dgFX++D/hgrbGeALbKflZp5LuWSoDJcQPlfDJ/97bzggOsFaw
ygpXSoNWva5Yy2QRrkBetE2pJSte7UwaR7vqzwIqAPjR3gfZi4BuUtm0RqI62EsF
ftrzxznnl3X7oELhCxajyPOBWxRlk2/D8mkLGSo99wISa4Rf5Ol+pSJYNZdX3UfS
ytmq01q1wqTYs8WyGgtjHCCIMQC53WbA8oOgR6tttqXSWFCycIGmd5pp0eeDNzV0
xWIPF5SKhqoOlaaxBB3PgJlggJ3nUIHrp9CXANfnKnUZQBvMPiTCeSNjZf65RrCr
mjcWlLMa9BJVYDGSzzS8W4+ib8y/Tv7tX+0zSqkaW+sbxscWaBf7/8eDwSk/nXTx
AHugIoGX3e3QDMgqLF1PKIYA+2PVRlgsbV0DLaFKs60hECzE7HKMBRniPkchTyfj
P1vSUKZok0CrGlmbOFjlHX0n92wTrQo7c7FKlAORNiHWU12N62QW4fYvcVL5+UBw
LXOIIqWJkeQ=
=uYje
-----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