Re: RSync like diff for incremental stuff

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

rCyril Russo wrote:
> Denis Corbin a écrit :
> Cyril Russo wrote:
> 
> [...]
> 
>  
>>>>>> Anyway, how complex would it require to implement in DAR ?
>>>>>>             
>>>>> First, to be able to make a binary diff you must have the original
>>>>> binary beside the current one to compare them (actually dar relies on
>>>>> inode data changes to decide whether to save the whole file again or to
>>>>> not save it at all).
>>>>>         
>>>> Well, this is not exact, and it's one of the main feature of the
>>>> librsync.
>>>> The librsync create a signature file from a binary file, and you
>>>> can(should) use this signature as the first comparand.
>>>>     
> 
> OK, but if the signature is different, you cannot make binary diff
> without the original file, to know where is located the change.
>   
>> I'll try to take an example here:
>> Let's say I have a 1/2GB file.
>> The signature is set to use 512kb block (something crazy as it's very big).
>> In my signature, I'll get 1000 block, each of 32 bytes, so a 32k file.
> 
>> Then, let's say I've modified the file, and I'm running an incremental
>> backup
>> The signature is compared to the new file (and only the new file).
>> Block number 234, 235, and 636 are modified (thanks to the signature), so:
>>  1) The block number 234, 235 and 636 are saved in the the incremental
>> backup (and only those blocks)
>>  2) The new signature is updated from the new_file
> 
>> In the process, I've never read the initial file again.

OK, I see. This is not a signature of a given file but many signature of
the file, one for each block of a given size.

[...]

>>>>     
> 
> If there was a change instead, without the original copy you have to
> backup the whole file (which is the current situation). And, if now you
> have a partially saved file, there is much chance you have to backup the
> whole file again... unless you ask the user to provide former backup up
> to the full backup ... this for each file that cast this situation...
> 
>   
>> This is wrong. The aim of the signature is to never use the original
>> file again.

Yes, I was considering "signature" as an overall hash of the file, not
as you explained before, a by-block hash.


[not reproduced text but fully agreed]

> However it would be more painful for the user to restore of a small set
> of files, as you would have to access to more archive and slices for the
> same set of files to restore.
>   
>> Yes. This is the drawback of such algorithm. You have to have all steps
>> from full to last incremental.
>> At the same time, the saving in disk space / bandwidth might worth the
>> extra effort on restoring.
> 
>> I rarely restore my backup (only on failure, once a year ? once a month
>> ?), but I'm more concerned by not sending my 3GB mail file
>> every day to my remote server.
> 

:-) that's a good argument.


[...]

>>>> The new code would
>>>> (undiff(decrypt(decompress(orig_file)))^number_incremental).
>>>> This means that, once you've decompressed the original file, going
>>>> from one version to the other is only a diff (which is O(1)
>>>> operation), so it's faster than the current code.
>>>>     
> 
> a diff is not a constant operation it depends on the amount of data to
> compare, isn't it rather an O(n) operation?
>   
>> Producing a diff is O(n*m).
>> Hopefully the diff store the position of difference before the
>> difference itself, so patching (using the diff) is O(1), as you'll only
>> touch the modified part, and won't read the other part of the file.
> 
>> You're right that most of filesystem don't allow inserting / removing
>> from arbitrary position, so once you are on a modified size block,
>> you'll have to rewrite the other blocks too (thus O(n) operation).
>> But this is a filesystem limit, not a mathematical limit.
> 
>> And as you'll only write the file once, if you have 10 diff from the
>> full to last incremental, you'll have 9x O(1) operation (producing the
>> difference in memory), and 1x O(n) operation (writing the final file on
>> disk).


OK

>  

[...]

>>>> Please try to read the rsync algorithm as it's very very clever (
>>>> http://en.wikipedia.org/wiki/Rsync ). Basicly, the rsync algorithm is
>>>> O(N) to figure out the diff.
>>>>     
> 
> I just did, this is an interesting article. But note that the rolling
> checksum needs the whole data of the file to be possible to compute.
> Having differential backup based on other differential backups needs
> another algorithm for binary diff.
>   
>> The smart algorithm does this:
>> 1) Initial file => compute the rolling checksum + hash per block, this
>> gives the signature
>> 2) For each incremental step:
>>    2.1) From the last signature find out the modified block
>>    2.2) save the modified block
>>    2.3) From the new file, compute the rolling checksum + hash per
>> block, this gives the new signature
>>    2.4) Back to 2.1
> 
>> BTW, librsync even accelerate the signature making when there is a diff,
>> so 2.3 can be even faster by computing the rolling checksum + hash only
>> for the modified blocks and updating the signature.
>  
>>>> Using a signature (as said above), you don't need to read the
>>>> previous file at all, and you only need to read the new file *once*,
>>>> so it's exactly like the current code in fact.
>>>>     
> 
> Maybe I do not understand what you mean here above.
>   
>> Current code use inode to find out if a file was modified.
>> If it was, then it has to go through the whole file to compress &
>> encrypt it, so you're reading the new file once.
> 
>> With a rsync like algorithm, you'll also have to read the whole file
>> once (if inode changed), but instead of compressing & encrypting, you'll
>> compute the rolling checksum and hash, and compare this to the previous
>> file *signature*.
>> For each difference, you'll have to compress & encrypt the difference
>> blocks, and only save those.
>> At the end, you'll store the updated signature in the catalog too.
>> There is still only one file read operation, and less compression &
>> encryption, so it'll be probably faster (as compression & encryption is
>> slower than hashing).

OK, I now understand what you meant.

> 
>  
>>>> Even better, the system will be faster as you won't be compressing /
>>>> encrypting the unchanged data, so the time you loose reading the
>>>> small signature file (usually 1% of the original file size), is
>>>> highly compensated by *not* compressing the redundant data.
>>>> The amount of I/O will be less too (as you store less compressed
>>>> block on the FS), so you'll gain in network or disk bandwidth.
>>>>     
> 
> Actually if a file has not changed (see its last modification time),
> there is no need to compress / encrypt it. I probably do not understand
> what you mean.
>   
>> I meant, let's say you have a mail file. usually, new mail are appended
>> in the file.
>> With current code, when a mail is appended, you'll compress & encrypt
>> the whole file again (so it gets pretty large)

Yes, you are right.

> 
>> With rsync, you'll compress & encrypt only the appended data (as the
>> rest of the file won't change).
>> So it's faster than the whole file compression and encrypt, even if it
>> has to compute checksum & hash for the whole file.
> 
>>>> In fact, rsync usually provides a 2x to 16x speedup other gzipping
>>>> the whole file for example (try to run a rsync test, you'll see by
>>>> yourself).
>>>>     
> 
> I use rsync dayly (through fcron), while I never made the effort to look
> at the way it works. Thanks for having let me know that. ;-)
> 
>  
>>>> Sure, if the rsync diff size > input size, then it's better to
>>>> perform a full backup. This never happen in reality.
>>>> I guess a better rule of thumb would be: if rsync_diff_size +
>>>> signature_size > input_size, then it might worth the full backup.
>>>>
>>>> Cyril
>>>>
>>>>
>>>>
>>>>     
> 
> Back to dar, I see this possibility:
> 
> # is saved data
> - is unsaved data
> 
> assuming there is only one file in the backup:
> 
> full backup  : ###########################
> diff1 backup : --------####-------###-----
> diff2 backup : --------###----------#-----
> but if some data changed at a place in the file which is unsaved (for
> example at the beginning), the whole data block as to be saved again,
> diff2 would have then been:
> diff2 bacup  : ###########----------#-----
>   
>> Thanks to rsync (with rolling checksum), it will probably be only:
> 
>> diff2 bacup  : #-------###----------#-----
> 

Yes, as we saw previously with the hash per block you can know which
block to only save. I must review the algorithm. What I liked here is
that there was not a block size of arbitrary size to define. But it is
not efficient. This I have to keep from the differential backup the list
of hash by block and copy it to the new backup.

> 
> restoration would need "full" then "diff1", then "diff2". 
>> You're speaking the truth.
> Restoration would fail for diff backup if no file exist on filesystem
> or if its
> global data signature does not match the expected one.
>   
>> I disagree here.
>> Restoration fail if full backup or diff1 backup, or diff2 are missing.
>> Signature are useless for restoration (unless going backward, see below).
> 
>> BTW, let's say you have:
> 
>> full backup  : ###########################
>> diff1 backup : --------###----------#-----
>> diff2 backup : --------####-------###-----
> 

OK, you are right, using by block hash you can restore even if diff1 is
missing (assuming you have either 'full' backup or the corresponding
file present in the filesystem). What I meant is that if you have *only*
diff1 or diff2 and no file in the filesystem, or a file that is not the
one you could find in "full", then restoration fails. In current status
you can restore from a diff1 backup all files that have changed since
the archive of reference was made.

> 
>> Then diff1 can be missing, it'll still work (as diff2 is more complete
>> than diff1, and rsync store whole blocks).
> 
>> [backward restoration] Also, in your example, let's say you want to
>> restore up to step diff2.
>> If you have the signature in diff2 backup set (as you should), AND the
>> new_file is still here on the filesystem, then it'll be faster to go
>> from new_file to diff2 than doing full + diff1 + diff2.
>> In order to achieve this, you'll compute the "hypothetical" diff3 from
>> diff2 to new_file (thanks to the signature) and revert new_file to diff2
>> by applying the reverse diff.
>> It's dichotomy here, nothing special but the speed up might really worth
>> the effort..
> 
> 
> Dar would also store signature for each block. By block I mean the
> sequence of unsaved data, or the sequence of saved data.
>   
>> I'm sorry I didn't understand, so I might say bullshit here.

That's not totally bullshit. My original Idea was to not have fixed
length block size, but instead a "block" is either a continuous portion
of a file that have not changed since the reference or a continuous
portion a file that have changed. Each one is associated with its own hash.

So in the file :

we have 5 blocks. 1, 3 and 5 only have hash value to detect any change
in them, while 2 and 4 have hash and data.

diff1 backup : --------###----------#-----
               111111112223333333333455555

As you have showed, this has the drawback to force the backup of a
larger amount of data than what rsync can do, if for example the first
part of the file is modified it leads to be saved more data:

diff2 backup : ########-------------------
               111111112223333333333455555

where rsync would have only saved this :
diff2 backup : #--------------------------

Thus my algorithm is not good. I have to deal with fixed block size and
with the decision of what arbitrary size to use.

>> From the other use I've seen, signature are per-file information, they
>> must be saved per-file (so the catalog seems the right place to store
>> them).

Well, here the problem is that the catalogue is loaded into memory (for
 the reference catalogue of diff backup), built in memory (for the
catalogue of the archive under construction) and only at then end of
process, is dump to the archive. Having many hash values per file would
explode the virtual memory requirement, which some do find already a bit
huge, probably with reason. To avoid this I have to possibility to store
the block hashes of a file all along the file beside the file data.

The drawback, is that an isolated catalogue (which is only a container
with a catalogue), cannot be used for binary diff backup, only for
normal diff backup (as today). Else, I have to extend the isolated
catalogue format to also store the list of hash for each plain file.
Yes, that could worth it.

> 
>> The signature of a block list is useless if not dangerous, as the block
>> themselves might change, and the signature won't match anymore.
>> Why I'm saying it's per file, then, it's simple,
>> Let's say you insert a byte 0xEA to a 2MB file at the 3rd position.

I don't remember having thought about a signature of block list. At most
a global signature of a file, beside the signature of each block of that
file. But, it does not bring any use, so please forget it.

> 
>> Then, if you have block based signature, then you'll have to sign all
>> the block again (as there is no limit from one block to the other).
>> If you have a file based signature, the first block won't match (as it's
>> modified), but the next blocks will match with an offset of +1, so
>> you'll only save the modified block with a the header saying:
>> block 0 changed at byte: 3, 1 byte inserted = 0xEA
>> Each latter block aren't changed, so there aren't saved again (as
>> producing the final file, simply imply changing the block 0 by inserting
>> 0xEA at 3rd position, offseting all other blocks by 1).
> 
>> If you had a stream of block, then it would be impossible to find the
>> limit where it's modified.
>> So you must have "fence" to get usuable limits, and such obvious fence
>> are the files start and end position.
> 
> 
> See
> http://sourceforge.net/tracker/?func=detail&aid=2803478&group_id=65612&atid=511615
> 
> for implementation detail seen so far.
>   
>> What are TLV ?

TLV stands for Type Length Value. This is a common data structure that
has the advantage to be possible to enhance while older implementation
can ignore theses new feature. Radius protocol for example uses this
data structure, many others do (like OSPF, RSVP, LDP network protocols).
In other words:
Type : Data / Hash / hole (part of a file full of zeros)
Length: is the overall length to skip to reach the next TLV
Value : is either the Data, the hash or the number of zeroed bytes
depending of the type of the TLV.

You can thus easily add new features without breaking much things in
your implementation. Dar uses this structure in slices headers (since
2.4.0), and it is planned to be used for sparse files to hold holes vs
data of a file. (Thus adding hash is easy withing that structure, just a
new Type for TLV is required, old implementation would just ignore (and
warn) that new Type of TLV).

> Regards,
> Denis.
>>

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

iD8DBQFKPQiqpC5CI8gYGlIRAkzmAJ48lUriXmKEPQDP+/0LFWApjrPY0ACeLmTb
Zixs+i6jITCamTpQBt/dzNE=
=qOpI
-----END PGP SIGNATURE-----

------------------------------------------------------------------------------
Are you an open source citizen? Join us for the Open Source Bridge conference!
Portland, OR, June 17-19. Two days of sessions, one day of unconference: $250.
Need another reason to go? 24-hour hacker lounge. Register today!
http://ad.doubleclick.net/clk;215844324;13503038;v?http://opensourcebridge.org