Re: diff compression

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

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

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

When I wrote signature, I meant librsync signature file, which are block
hashes.

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

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

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

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

That would be similar to how EA's are stored, correct? 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.

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

Optionally. Retrieve the signatures or not, it's up to the user if he needs
the signatures or not...

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

This is similar:
 - read the file on the filesystem and feed the data (and the signature from
the reference archive) to librsync
 - at the same time, compute the new signature blocks (from the same buffer
that reads filesystem data) - I actually wrote a patch for librsync that in
one operation, returns both a binary diff and the new signature of the file
 - you get binary diff back from librsync, store that in dar, along with the
flag that indicates "rsync compression"
 - dump the new signature block (of the new file) after the data

There is no need to store previous signature blocks from the current
reference archive.
A file that has been saved in a full backup A, not saved in an incremental
backup B, will get saved again in backup C (referencing backup B) in current
versions now. A block that has been reverted to the same contents as was
stored in backup A, needs to be saved again in backup C. A delta can only go
from B to C, not reuse data from A.

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

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

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

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.

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