Re: RSync like diff for incremental stuff

Denis Corbin a écrit :
> 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.
To be honest, it's the signature of the whole file, *including* the 
signature of many "blocks" in the file.
In fact the rolling checksum mechanism allows you to have the "instant" 
signature of any possible block in the file -for almost nothing-.

>>>>>     
>>>>>           
>> 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.
>   
In fact, you could use librsync to compute such things for you (it's 
compatible with the license).
>   
>> 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.
>   
Yes. Less data means more dependance on data safety. It's a choice that 
every user could do.
Either be a Mac user with a time machine (this is what Dar do actually, 
storing every modified file as complete), or be a Unix user with a 
remote ssh/ftp machine (à la rsync-backup / duplicity).
Local storage is cheap, but isn't safe at all (robbery / fire / flood / 
electrical shock, etc...).
Remote storage is more expensive, but it's supposed to be safer.
>   
>>> 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.
>
>   
I think Rsync is now quite stable and used almost everywhere it can be 
used, because it has proved suitable for most situation.
rsync with its rolling checksum algorithm can compute the minimum block 
size quite well, is fast, and is "de-facto" standard.
Data are quite safe when handled to rsync.

I don't know how easy it would be to plug rsync like algorithm in Dar, 
but I think it'll be safer and simpler than re-writing a similar 
algorithm (with all the risk to the data themselves).
>>> 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.
>
>   
Yes this is a big issue.
What about adding a file rsync signature as meta data as a TLV block, 
and index this in the catalog ?
That would only add 4 bytes per file, as signatures would only be loaded 
on demand.

> 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.
>
>   
I don't know how old Dar version could handle such modification.
In duplicity, the system produce 3 file per backup, 1 archive contains 
the signatures, the other contains the manifest (ie the diff of file 
listing, so it's possible to recompute the dir hierarchy), and the 
'real' data diff archive.
Duplicity on the other hand, use TAR, meaning that restoring a file on 
the 7-th incremental backup need reading the whole 7 previous archives 
(as tar isn't indexed).

This is why I really like Dar.
If only it was so space efficient as duplicity it would be my perfect tool.

>>> 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.
>   
I misunderstood that part too.
>   
>>> 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).
>
>   
Ok, it's quite smart in fact.

So my advice, for what it's worth, is to add a dependency on librsync (a 
configure time switch).
When present, Dar get a new option like (--rsynced).
When the option is used, librsync is called in the code to produce the 
signature (rsync signature, with hash + rolling checksum) of the file.
This is stored in a TLV, (after, before ?) the file data, but it's not 
compressed, to avoid loading it in memory while comparing (speed up 
advice here).
The index of the signature is added in the catalog.

Then, whenever the option is used, and an incremental backup is 
requested, Dar read the catalog like it already did.
If it finds the signature TLV's index, it can seek to the signature 
itself, and read it.
 From that signature, it can compute the theorical best diff (thanks to 
librsync again), and store this (this is new format, as the file isn't 
complete anymore) compressed / encrypted.
The new signature is also stored in the inc backup, and the catalog in 
the backup also contains the index to this new signature (so  the 
procedure can start again).

There is no additional memory requirement in the procedure above, as the 
catalog doesn't store the signature (that can be too big for large 
file), but only the index to the signature file.
The index could be a single 32 bit integer, or a infin_int as I guess 
archive with more than 2^32 files will be rare anyway.

Best regards,
Cyril




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