From: Craig B. <cr...@ar...> - 2001-12-28 23:45:57
|
> Are there plans to implement a prorietary client to minimise network usage > by implementing true incremental/delta backups? a.la rsync algorithm or > equivalent. I am planning on adding tar over ssh and eventually rsync as additional transport layers for unix/linux clients. Rsync might need a few additional features to make it work with BackupPC, but I still need to see if I can make it work with an unmodified rsync. I haven't contemplated doing a custom client, mainly because I don't know a thing about win32 development and I generally like the idea of not needing to install or maintain client-side software. For unix/linux, rsync (or a slight addition to it) should work well. For win32, in addition to reducing network traffic, a custom client might also be able to workaround open-file and file locking issues, and also provide faithful saving of file attributes. > By splitting file data into delta's (compared across and referenced by > complete data set) > I suspect online disk requirements can be reduced much much more. Yes!! I have been thinking about using something like xdelta1 (see http://sourceforge.net/projects/xdelta) to do binary file deltas, but that would only be against the previous file of the same name from the same machine. Better yet (as you suggest), I have also been thinking that there should be a way to change the pool to be a pool of snippets or deltas, rather than complete files. This could improve the overall storage efficiency from the current 6-8x to perhaps 20x or more, which would be really great. The problem is I haven't figured out how to do this. Suggestions and discussion are welcome! > Lastly, should consider the structure of files on disk to > support integration with a HSM backend (for tape storage) > inline with data retention. As opposed to writing your own. These issues are very important. The current hardlink structure is not friendly to many tape backup systems. I'm a novice in the area of tape backup systems, so I'd be very happy to learn more and figure out how to better glue BackupPC into other backend systems (both open source and commercial). > Their my thoughts, happy to code and contribute, however looking for > direction and an > understanding of what is already in the works. If you want to help design and code that would be great!! Here's my current roadmap for v1. Dramatic improvements (like making the pool an rsync-like database of snippets and adding client tools) would probably form the basis of v2: 1. Adding tar over ssh as an alternative to smbclient for unix/linux clients. This will allow symlinks and other special files to be backed up correctly. Later I will add rsync as a third transport layer (in addition to smb and tar/ssh). 2. Providing a utility to copy the pool and all data files. Useful for efficiently migrating the BackupPC data to a new (bigger) filesystem while preserving all the hardlinks. (Perhaps gnu "cp -dR" will be fast enough instead; I'll benchmark both.) 3. Saving attributes (unix owner, group, permissions, mtime, atime etc). I don't know enough about Windows ACLs to know how to save them too (this would need updates to smbclient). 4. Generating zip or tar archives for restore. Currently files can only be restored one at a time, unless you mount the server's disk and drag files from the client. Generating a zip or tar archive will allow the original attributes to be merged and restored too. 5. Ability to split the pool across several file systems. Since I use hardlinks to efficiently store repeated files, everything must currently be on a single file system. New 120GB drives are just becoming available, so you could run BackupPC on two or three 120GB file systems without worrying about merging the physical drives into one big file system. Tools will allow you to resplit the pool if you need to add more drives later. 6. Update the CGI script BackupPC_Admin so it will optionally run under mod_perl. This would require a dedicated httpd, running as the BackupPC user. The advantages are that it would eliminate the current setuid, and it would be much faster (it would have persistent connections to the BackupPC server, and also cache the hosts file). 7. Implementing binary file diffs so that files with small changes are stored in a binary diff form (maybe using xdelta1). I'm planning on implementing 1-3 for the next version (v1.04), hopefully by mid or late January, and maybe the next two or three for the version after that. If you want to pitch in with, say, #4 or #6, or instead look at longer term goals (pool structure, optional client side software, or backend tape integration), then that would be great! Regards, Craig |
From: Craig B. <cr...@ar...> - 2001-12-31 07:32:26
|
Peter & Peter, Thanks for the excellent discussion of rsync, comparisons to commercial software, backend integration and other issues. I'm a little behind on replying to the last few emails, so let me take a crack at a few issues. I agree the rsync algorithm is an excellent way to reduce network traffic. A WinXX client could be developed. The existing rsync client would work fine for unix/linux. I need to look at rsync more to see how little can be changed on the server side (perhaps nothing, or very little). A separate issue is whether binary differencing (using rsync itself, or rsync-like algorithms in xdelta or similar), or something a lot smarter (changing the pool to be fragments or deltas, and using a RDMS for putting the pieces together. We should treat this as a separate issue from whether the deltas arrive directly from the client, or whether the server gets everything and generates the deltas locally. My plans for v1 are currently to support rsync as a transport for unix/linux, and (perhaps) using rsync/xdelta or similar for doing binary differencing on the server. It might seem pedantic (and redundant) to separate these steps, but I want all transport methods (whether smb, tar, rsync, etc) to have equal storage efficiency, peterb> Hmm.... this might be a dumb question, but why not start with peterb> just backing up Unix/Linux clients via an NFS export? The NFS peterb> mount could be brought up at backup time and scanned with peterb> ordinary filesystem tools (find, etc.,) or their equivalent peterb> Perl functions. Disk usage is minimized too since you only peterb> need copy files once you have identified them as non-redundant. peterb> (Note...this approach, while probably simpler, is inferior from peterb> a security perspective to a tar/ssh solution. It is, however, peterb> closer to the smbclient method that BackupPC presently uses for peterb> backup.) This is a good summary of the issues. Tar/ssh won't be hugely different from smbclient, since it already delivers the data in tar format. The main concern with NFS is security: I encourage people to run BackupPC as a user with low privileges. It is likely that not all the data on the NFS mounted file system will be visible to BackupPC. Also, normal users might be able to see the file system too (unless the mount point was below a secure directory). When I get around to doing tar/ssh I'll set it up so that, as an option, you can do tar without ssh on a local file system. You could then use an auto-mounter to mount the file system. So both options will be available. peterm> Dont know if your aware, there is a similar commericial peterm> product that does what BackupPC does but alot more. Its peterm> called Veritas Netbackup Proffesional. Have a look at peterm> http://www.veritas.com/products/category/ProductDetail.jhtml?- peterm> productId=nbupro you may get some ideas. Wow, pretty similar, but much better marketing. Yes, they do have a smart client and binary deltas. But their server doesn't run on linux, and it probably costs more too :). peterb> I think BackupPC is a great step in the right direction peterb> towards filling a gap between the capabilities of open peterb> source backup applications and the commercial applications peterb> presently available. If we put our heads together, I'm peterb> sure we can bring it up to a par with the vendor offerings peterb> already on the table. Strong agreement here. Given some time, we should be able to meet or exceed most of the features. craig> 2. Providing a utility to copy the pool and all data files. craig> Useful for efficiently migrating the BackupPC data to a new craig> (bigger) filesystem while preserving all the hardlinks. craig> (Perhaps gnu "cp -dR" will be fast enough instead; I'll craig> benchmark both.) peterb> How about dump / restore? Those are guaranteed to restore peterb> filesystem structure, including preserving hardlinks. (These peterb> are not available for all filesystem types, however.) That would work for local file systems. GNU "cp -a" works very well: my initial benchmarks are that it is about 30% faster than my perl copy code (which uses 4 children). So I'll probably ditch my code and recommend people either use GNU "cp -a" or dump/restore. craig> 5. Ability to split the pool across several file systems. peterb> This is a tricky one to achieve if you wish to retain the peterb> hardlink structure since hardlinks cannot cross filesystems. peterb> You'd have to switch to symbolic links which might have peterb> unpredictable side-effects. That's right. All the reference counting would still be by hardlinks on the main file system. Some fraction of the pool would be symlinks to the other file system. peterb> Perhaps a better approach would be to leave disk-spanning to a peterb> software raid layer on the server operating system? Most Unix peterb> versions today, as well as Linux, ship with basic software raid peterb> that allows the creation of virtual volumes upon which normal peterb> filesystems can be created. Many even allow dynamic increasing peterb> of such volumes (with the appropriate raid level) as disks are peterb> added to a system peterm> I agree with Peter's previous comments in that this issue can and peterm> probably should be delt with outside of the application. That is, peterm> some form of Logical Volume Manager. I agree with both of you. I agree that commercial systems like solaris and network appliance have excellent solutions. Our experience with rh-linux about 6-9 months ago was pretty poor. We were using reiserfs to create a big raid set (400GB) and found the reliability and performance to be poor (ok, we were using IBM 76GB drives too, which themselves were unreliable). Our experience during this period made me think about adding a split pool feature to BackupPC. I know that reiser and other choices are improving steadily, so a split pool is probably of diminshing utility. I'll move it to the bottom of the v1 list. peterm> I would also consider SpeedyCGI (http://www.cpan.org/module- peterm> s/by-module/CGI/CGI-SpeedyCGI-2.11.tar.gz) as an alternative peterm> if you dont want to enforce the need for Apache. Ok, I'll check it out. peterm> I think it would be a good idea if the current version continues peterm> as is and I will spend some time on producing pilot code to test peterm> long term goal's. In particular: peterm> peterm> 1. Client/Server model that results in the network transfer of peterm> delta's peterm> 2. Server model that stores delta's and references to them. peterm> peterm> I will update the list as it unvails. Sounds great! The correct solutions in these areas could form the foundation of v2. Thanks again for all the discussion and pointers! (At some point we could split off another mail list for development, but, assuming others don't mind, let's keep it on this list. Plus anyone else should feel free to jump in too!) Regards, Craig |
From: Craig B. <cr...@ar...> - 2002-01-03 07:55:54
|
> Rather than trying to explain (im doing a poor job of it) I'll make > some points and get back to writing the proof of concept. Hopefully > then it will all fall in place. > > Thus far i've converted the rsync crc to perl and testing the > application of delta's. This sounds great! Perhaps one thing that would help is some better notation to unify our discussions. Let's assume there's a file f on a client, and this file changes over time. Let's call each version f0, f1, f2 where the numbers refer to each time the backup program inspects it. It's possible that f1==f2, or even (f1!=f2 and f1==f3). Currently BackupPC stores f0, f1, f2 as separate files, and uses hardlinks in the case where any pair of files is identical. We agree that using an rsync-like technique, if the client has a new file, f3, and the server has f2 (or can reconstruct it), then the backup client can compute a delta between the two: d2 = delta(f2, f3) so that f3 can be constructed by knowing f2 and d2: f3 = apply(f2, d2) The clever part of rsync is that delta() can be computed without knowing all of f2: just the block signatures. And the backup server only needs to know f2 and d2. But you know that already. The point of this notation is so we can explicitly discuss what is computed and stored. Example1: store f0, f1, f2, f3, with hardlinks between identical files. That's what currently happens. Example2: store f0, d0, d1, d2. That's the first complete file and the forward deltas. f3 can be recreated by applying, in turn, each of d0, d1, d2 to f0. Example3: store r1, r2, r3, f3, where the r's are reverse deltas. This way the last file is complete, and older files can be rebuild, if needed, by applying one or more reverse deltas. Of course, there are much more complex examples (which you might be getting at): doing everything on a block basis, not a file basis, and somehow doing deltas on blocks, etc. We can add some notation for this too. Also, what happens if another client has the same sequence of files f0, f1, f2, f3 (or if the same sequence appears elsewhere on the same client)? Can the deltas only be stored once? Craig |
From: <ma...@ph...> - 2002-01-03 12:54:54
|
Ok...Simple picture.. File (f) has two backuped up versions f0 and f1. f0 = d0, d1, d2, d3 f1 = d0, d1, d2, d4 Where dX is a delta associated with a file (f) and X uniquely identifies the delta, that is it is different from any other delta. Assume we want to backup the file again. Assume f0 and f1 have not expired on the server (i.e. retention period) and assume the delta's d0 to d4 are still referenced by f0 and f1. Server sends client all delta's checksum's and digests referenced by f1 (last backup). They are d0, d1, d2 and d4 (We dont send d3 because it is not referenced by this files last backup). Client compares checksums/digests received against those generated from current file source. Client sends back two types of messages to server. 1. Between offset X and Y delta dX matched. 2. Between offset X and Y no delta matched use data Z instead. Server creates f2 by: 1. Referencing existing delta's if 1) above 2. Creating new delta's and referencing them if 2) above To restore version f1 one would merely concatenate the delta's referenced by f1 in offset order. Whats important is this.. 1. A file is a collection of delta's. There is no concept of storing a complete file on the server. All backed up versions of a file are treated as a grouping of delta's. 2. The file record contains the offsets at which the delta's are applied to form "the file data". 3. A delta may be associated with more than one version of the file. 4. We may chose to store multiple copies of the same delta only once. That is, before creating a new delta compute the delta's digest and compare the digest with all existing delta's digests (delta digest index). If match, reference existing delta. If no match, create new delta. This answers your question.. Also, what happens if another client has the same sequence of files f0, f1, f2, f3 (or if the same sequence appears elsewhere on the same client)? Can the deltas only be stored once? 5. The recovery of a particular file version does not depend on the prescence of all previous file versions. 6. A reference count will be maintained for each delta in existance. Once a delta is no longer referenced (because file versions are expired (retention)) the disk space associated with it is reclaimed (delta deleted). 7. Delta's may be compressed to conserve even more disk space. Regards Peter Marelas ----- Original Message ----- From: "Craig Barratt" <cr...@ar...> To: <ma...@ph...> Cc: "Peter L. Buschman" <pl...@io...>; <bac...@li...> Sent: Thursday, January 03, 2002 6:55 PM Subject: Re: [BackupPC-users] Reducing Network Requirements > > Rather than trying to explain (im doing a poor job of it) I'll make > > some points and get back to writing the proof of concept. Hopefully > > then it will all fall in place. > > > > Thus far i've converted the rsync crc to perl and testing the > > application of delta's. > > This sounds great! > > Perhaps one thing that would help is some better notation to unify > our discussions. > > Let's assume there's a file f on a client, and this file changes > over time. Let's call each version f0, f1, f2 where the numbers > refer to each time the backup program inspects it. It's possible > that f1==f2, or even (f1!=f2 and f1==f3). > > Currently BackupPC stores f0, f1, f2 as separate files, and uses > hardlinks in the case where any pair of files is identical. > > We agree that using an rsync-like technique, if the client has a new > file, f3, and the server has f2 (or can reconstruct it), then the > backup client can compute a delta between the two: > > d2 = delta(f2, f3) > > so that f3 can be constructed by knowing f2 and d2: > > f3 = apply(f2, d2) > > The clever part of rsync is that delta() can be computed without > knowing all of f2: just the block signatures. And the backup server > only needs to know f2 and d2. But you know that already. > > The point of this notation is so we can explicitly discuss what > is computed and stored. > > Example1: store f0, f1, f2, f3, with hardlinks between identical > files. That's what currently happens. > > Example2: store f0, d0, d1, d2. That's the first complete file > and the forward deltas. f3 can be recreated by applying, in turn, > each of d0, d1, d2 to f0. > > Example3: store r1, r2, r3, f3, where the r's are reverse deltas. > This way the last file is complete, and older files can be rebuild, > if needed, by applying one or more reverse deltas. > > Of course, there are much more complex examples (which you might be > getting at): doing everything on a block basis, not a file basis, > and somehow doing deltas on blocks, etc. We can add some notation > for this too. > > Also, what happens if another client has the same sequence of files > f0, f1, f2, f3 (or if the same sequence appears elsewhere on the > same client)? Can the deltas only be stored once? > > Craig > > _______________________________________________ > BackupPC-users mailing list > Bac...@li... > https://lists.sourceforge.net/lists/listinfo/backuppc-users > |
From: Peter L. B. <pl...@io...> - 2002-01-03 17:22:45
|
Craig: >Perhaps one thing that would help is some better notation to unify >our discussions. Excellent notation. That helps a lot :) >Also, what happens if another client has the same sequence of files >f0, f1, f2, f3 (or if the same sequence appears elsewhere on the >same client)? Can the deltas only be stored once? I don't see why not. It is the same problem in principle as storing redundant files as hardlinks. You'd just have to store a hardlink to the original delta rather than a new delta itself, right? This would require going through the hassle of calculating a checksum on every delta generated, though, and doing the same comparisons on delta files as on "normal" files. --PLB >Craig |
From: Peter L. B. <pl...@io...> - 2002-01-03 18:21:44
|
Peter: I think I see what you're getting at. You are describing an architecture where the blocks are separated from the files that reference them. In the same way that Craig's forest of hardlinks points duplicate files to the same original file, block pointers contained in deltas point duplicate blocks to data blocks in some kind of datastore. What you term a "delta" below is a block of data of fixed size. Blocks (or deltas as you term them) will not be removed from the datastore until the reference count drops to zero. The reference count will not drop to zero until all file versions that use it have expired. Congratulations. You've just invented a filesystem with snapshot capability. :) The difference here is that most snapshot filesystems are limited in the number of snapshots they can present at a single time. This idea is rather more flexible since there are no implicit limits. The underlying technique, however, is the same. Done carefully, too, your concept could also accommodate variable block-sizes (something key to improving efficiency in the differencing algorithm) where snapshot filesystems usually have fixed block sizes. I see some interesting modelling scenarios arising from this. It could be a fascinating thing to implement given all the unique variables and potential areas for tuning (BerkeleyDB anyone?) --PLB At 12:04 AM 01/04/2002 +1100, ma...@ph... wrote: >Ok...Simple picture.. > >File (f) has two backuped up versions f0 and f1. > >f0 = d0, d1, d2, d3 >f1 = d0, d1, d2, d4 > >Where dX is a delta associated with a file (f) and X >uniquely identifies the delta, that is it is different from >any other delta. > >Assume we want to backup the file again. >Assume f0 and f1 have not expired on the server (i.e. retention period) >and assume the delta's d0 to d4 are still referenced by f0 and f1. > >Server sends client all delta's checksum's and digests referenced >by f1 (last backup). They are d0, d1, d2 and d4 (We dont send >d3 because it is not referenced by this files last backup). > >Client compares checksums/digests received against those generated >from current file source. > >Client sends back two types of messages to server. > >1. Between offset X and Y delta dX matched. >2. Between offset X and Y no delta matched use data Z instead. > >Server creates f2 by: > >1. Referencing existing delta's if 1) above >2. Creating new delta's and referencing them if 2) above > >To restore version f1 one would merely concatenate >the delta's referenced by f1 in offset order. > >Whats important is this.. > >1. A file is a collection of delta's. There is no concept of > storing a complete file on the server. All backed up versions > of a file are treated as a grouping of delta's. >2. The file record contains the offsets at which the delta's > are applied to form "the file data". >3. A delta may be associated with more than one version > of the file. >4. We may chose to store multiple copies of the same delta > only once. That is, before creating a new delta compute > the delta's digest and compare the digest with all > existing delta's digests (delta digest index). If match, > reference existing delta. If no match, create new delta. > > This answers your question.. > > Also, what happens if another client has the same sequence of files > f0, f1, f2, f3 (or if the same sequence appears elsewhere on the > same client)? Can the deltas only be stored once? >5. The recovery of a particular file version does not depend on the > prescence of all previous file versions. >6. A reference count will be maintained for each delta in existance. > Once a delta is no longer referenced (because file versions are > expired (retention)) the disk space associated with it is > reclaimed (delta deleted). >7. Delta's may be compressed to conserve even more disk space. > >Regards >Peter Marelas > >----- Original Message ----- >From: "Craig Barratt" <cr...@ar...> >To: <ma...@ph...> >Cc: "Peter L. Buschman" <pl...@io...>; ><bac...@li...> >Sent: Thursday, January 03, 2002 6:55 PM >Subject: Re: [BackupPC-users] Reducing Network Requirements > > > > > Rather than trying to explain (im doing a poor job of it) I'll make > > > some points and get back to writing the proof of concept. Hopefully > > > then it will all fall in place. > > > > > > Thus far i've converted the rsync crc to perl and testing the > > > application of delta's. > > > > This sounds great! > > > > Perhaps one thing that would help is some better notation to unify > > our discussions. > > > > Let's assume there's a file f on a client, and this file changes > > over time. Let's call each version f0, f1, f2 where the numbers > > refer to each time the backup program inspects it. It's possible > > that f1==f2, or even (f1!=f2 and f1==f3). > > > > Currently BackupPC stores f0, f1, f2 as separate files, and uses > > hardlinks in the case where any pair of files is identical. > > > > We agree that using an rsync-like technique, if the client has a new > > file, f3, and the server has f2 (or can reconstruct it), then the > > backup client can compute a delta between the two: > > > > d2 = delta(f2, f3) > > > > so that f3 can be constructed by knowing f2 and d2: > > > > f3 = apply(f2, d2) > > > > The clever part of rsync is that delta() can be computed without > > knowing all of f2: just the block signatures. And the backup server > > only needs to know f2 and d2. But you know that already. > > > > The point of this notation is so we can explicitly discuss what > > is computed and stored. > > > > Example1: store f0, f1, f2, f3, with hardlinks between identical > > files. That's what currently happens. > > > > Example2: store f0, d0, d1, d2. That's the first complete file > > and the forward deltas. f3 can be recreated by applying, in turn, > > each of d0, d1, d2 to f0. > > > > Example3: store r1, r2, r3, f3, where the r's are reverse deltas. > > This way the last file is complete, and older files can be rebuild, > > if needed, by applying one or more reverse deltas. > > > > Of course, there are much more complex examples (which you might be > > getting at): doing everything on a block basis, not a file basis, > > and somehow doing deltas on blocks, etc. We can add some notation > > for this too. > > > > Also, what happens if another client has the same sequence of files > > f0, f1, f2, f3 (or if the same sequence appears elsewhere on the > > same client)? Can the deltas only be stored once? > > > > Craig > > > > _______________________________________________ > > BackupPC-users mailing list > > Bac...@li... > > https://lists.sourceforge.net/lists/listinfo/backuppc-users > > |
From: Peter L. B. <pl...@io...> - 2002-01-04 03:16:05
|
Check. Now the pieces all fall into place. :) I'm not entirely clear though, on how you are storing the blocks. When you first store the blocks for a file, are you splitting it up into fixed blocks and storing each block independently (I'm going to use block when to mean a fixed length data block and delta to mean a file of bytestreams + block pointers) or are you effectively storing the entire file and referencing back to it? Only the former would make sense to me in this architecture since you need to retain the ability to selectively expire blocks from the original file. My point about variable block sizes is that the efficiency of the differencing algorithm for a single file can vary significantly by the block size that rsync uses to divide the source file into fixed-length blocks. For copying purposes, the block size can thus vary from invocation to invocation since the blocks do not need to be stored once the synchronization is complete. For data backup, however, you are fixing the block size at backup time. For a given file, the block size thus needs to stay static to be of any use. However, there is still the possibility of using differing block sizes for other files to improve efficiency. Thus, small, rapidly changing files might use a block size of 16k while large binary databases of infrequently changed data could be more efficiently differenced with a block size of 1024k. The optimum block size will vary significantly depending on the type of file and I consider it unlikely that a one size fits all block size will prove practical in this scenario. --PLB At 01:44 PM 01/04/2002 +1100, ma...@ph... wrote: >Thats the one. > >Conceptually, relationship is a follows in DB table notation. > >FileTable > fileid bigint, > filename text, > hostname text > >FileVersionTable > fileid bigint, > filevid int, > bytes bigint, > backupdate datetime > >DeltaTable > deltaid bigint, > digest char(16), > checksum char(4), > bytes int, > refcount int > >FileVersionToDeltaTable > filevid bigint, > deltaid bigint, > fileoffset bigint > >The data associated with a delta would live in the underlying filesystem not >the database >in some directory hierachy maybe based on the digest + deltaid. >e.g. /AB/CD/EF/GH/IJ/KL/MN/OP/deltaid.file > >Handling variable block size does not become an issue since for any given >file version, the maximum number of variable blocks generated by the source >as a result of comparing against the file version's checksum's can only be >one. > >Rsync (the application) only handles a variable block checksum under two >conditions (from what I have read of the code): > >1. When all fixed block size checksum's have matched and there is a variable > block checksum left over as the remainder. >2. When the algorithm is processing near the end of a file where the given > (file length - file offset) is less than the rsync fixed block size > (700 bytes by default). Only during this range may a variable block >checksum > less than the fixed block size have any chance of matching. > Variable block sizes greater than the fixed block size are not >permitted. > >Other than those conditions a sliding checksum across 700 bytes is applied >over the data stream and implements the rolling characteristics of the >checksum. > >************ 700 bytes >***********+ 700 bytes (shifted left 1 byte) >**********++ 700 bytes (shifted left 1 byte) >*********+++ 700 bytes (shifted left 1 byte) >********++++ 700 bytes (shifted left 1 byte) >*******+++++ 700 bytes (shifted left 1 byte) >******++++++ 700 bytes (shifted left 1 byte) >*****+++++++ 700 bytes (shifted left 1 byte) >****++++++++ 700 bytes (shifted left 1 byte) >***+++++++++ 700 bytes (shifted left 1 byte) >**++++++++++ 700 bytes (shifted left 1 byte) >*+++++++++++ 700 bytes (shifted left 1 byte) >++++++++++++ 700 bytes (shifted left 1 byte) > >etc.. > > >Regards >Peter Marelas > >----- Original Message ----- >From: "Peter L. Buschman" <pl...@io...> >To: <ma...@ph...>; "Craig Barratt" <cr...@ar...> >Cc: "Peter L. Buschman" <pl...@io...>; ><bac...@li...> >Sent: Friday, January 04, 2002 5:21 AM >Subject: Re: [BackupPC-users] Reducing Network Requirements > > > > > > Peter: > > > > I think I see what you're getting at. You are describing an architecture > > where the blocks are separated > > from the files that reference them. > > > > In the same way that Craig's forest of hardlinks points duplicate files to > > the same original file, block pointers > > contained in deltas point duplicate blocks to data blocks in some kind of > > datastore. > > > > What you term a "delta" below is a block of data of fixed size. Blocks >(or > > deltas as you term them) will not > > be removed from the datastore until the reference count drops to zero. >The > > reference count will not drop to > > zero until all file versions that use it have expired. > > > > Congratulations. You've just invented a filesystem with snapshot > > capability. :) The difference here is that > > most snapshot filesystems are limited in the number of snapshots they can > > present at a single time. This > > idea is rather more flexible since there are no implicit limits. The > > underlying technique, however, is the same. > > Done carefully, too, your concept could also accommodate variable > > block-sizes (something key to improving > > efficiency in the differencing algorithm) where snapshot filesystems > > usually have fixed block sizes. > > > > I see some interesting modelling scenarios arising from this. It could >be > > a fascinating thing to implement given > > all the unique variables and potential areas for tuning (BerkeleyDB >anyone?) > > > > --PLB > > > > > > > > > > > > > > At 12:04 AM 01/04/2002 +1100, ma...@ph... wrote: > > >Ok...Simple picture.. > > > > > >File (f) has two backuped up versions f0 and f1. > > > > > >f0 = d0, d1, d2, d3 > > >f1 = d0, d1, d2, d4 > > > > > >Where dX is a delta associated with a file (f) and X > > >uniquely identifies the delta, that is it is different from > > >any other delta. > > > > > >Assume we want to backup the file again. > > >Assume f0 and f1 have not expired on the server (i.e. retention period) > > >and assume the delta's d0 to d4 are still referenced by f0 and f1. > > > > > >Server sends client all delta's checksum's and digests referenced > > >by f1 (last backup). They are d0, d1, d2 and d4 (We dont send > > >d3 because it is not referenced by this files last backup). > > > > > >Client compares checksums/digests received against those generated > > >from current file source. > > > > > >Client sends back two types of messages to server. > > > > > >1. Between offset X and Y delta dX matched. > > >2. Between offset X and Y no delta matched use data Z instead. > > > > > >Server creates f2 by: > > > > > >1. Referencing existing delta's if 1) above > > >2. Creating new delta's and referencing them if 2) above > > > > > >To restore version f1 one would merely concatenate > > >the delta's referenced by f1 in offset order. > > > > > >Whats important is this.. > > > > > >1. A file is a collection of delta's. There is no concept of > > > storing a complete file on the server. All backed up versions > > > of a file are treated as a grouping of delta's. > > >2. The file record contains the offsets at which the delta's > > > are applied to form "the file data". > > >3. A delta may be associated with more than one version > > > of the file. > > >4. We may chose to store multiple copies of the same delta > > > only once. That is, before creating a new delta compute > > > the delta's digest and compare the digest with all > > > existing delta's digests (delta digest index). If match, > > > reference existing delta. If no match, create new delta. > > > > > > This answers your question.. > > > > > > Also, what happens if another client has the same sequence of files > > > f0, f1, f2, f3 (or if the same sequence appears elsewhere on the > > > same client)? Can the deltas only be stored once? > > >5. The recovery of a particular file version does not depend on the > > > prescence of all previous file versions. > > >6. A reference count will be maintained for each delta in existance. > > > Once a delta is no longer referenced (because file versions are > > > expired (retention)) the disk space associated with it is > > > reclaimed (delta deleted). > > >7. Delta's may be compressed to conserve even more disk space. > > > > > >Regards > > >Peter Marelas > > > > > >----- Original Message ----- > > >From: "Craig Barratt" <cr...@ar...> > > >To: <ma...@ph...> > > >Cc: "Peter L. Buschman" <pl...@io...>; > > ><bac...@li...> > > >Sent: Thursday, January 03, 2002 6:55 PM > > >Subject: Re: [BackupPC-users] Reducing Network Requirements > > > > > > > > > > > Rather than trying to explain (im doing a poor job of it) I'll make > > > > > some points and get back to writing the proof of concept. Hopefully > > > > > then it will all fall in place. > > > > > > > > > > Thus far i've converted the rsync crc to perl and testing the > > > > > application of delta's. > > > > > > > > This sounds great! > > > > > > > > Perhaps one thing that would help is some better notation to unify > > > > our discussions. > > > > > > > > Let's assume there's a file f on a client, and this file changes > > > > over time. Let's call each version f0, f1, f2 where the numbers > > > > refer to each time the backup program inspects it. It's possible > > > > that f1==f2, or even (f1!=f2 and f1==f3). > > > > > > > > Currently BackupPC stores f0, f1, f2 as separate files, and uses > > > > hardlinks in the case where any pair of files is identical. > > > > > > > > We agree that using an rsync-like technique, if the client has a new > > > > file, f3, and the server has f2 (or can reconstruct it), then the > > > > backup client can compute a delta between the two: > > > > > > > > d2 = delta(f2, f3) > > > > > > > > so that f3 can be constructed by knowing f2 and d2: > > > > > > > > f3 = apply(f2, d2) > > > > > > > > The clever part of rsync is that delta() can be computed without > > > > knowing all of f2: just the block signatures. And the backup server > > > > only needs to know f2 and d2. But you know that already. > > > > > > > > The point of this notation is so we can explicitly discuss what > > > > is computed and stored. > > > > > > > > Example1: store f0, f1, f2, f3, with hardlinks between identical > > > > files. That's what currently happens. > > > > > > > > Example2: store f0, d0, d1, d2. That's the first complete file > > > > and the forward deltas. f3 can be recreated by applying, in turn, > > > > each of d0, d1, d2 to f0. > > > > > > > > Example3: store r1, r2, r3, f3, where the r's are reverse deltas. > > > > This way the last file is complete, and older files can be rebuild, > > > > if needed, by applying one or more reverse deltas. > > > > > > > > Of course, there are much more complex examples (which you might be > > > > getting at): doing everything on a block basis, not a file basis, > > > > and somehow doing deltas on blocks, etc. We can add some notation > > > > for this too. > > > > > > > > Also, what happens if another client has the same sequence of files > > > > f0, f1, f2, f3 (or if the same sequence appears elsewhere on the > > > > same client)? Can the deltas only be stored once? > > > > > > > > Craig > > > > > > > > _______________________________________________ > > > > BackupPC-users mailing list > > > > Bac...@li... > > > > https://lists.sourceforge.net/lists/listinfo/backuppc-users > > > > > > > > > > _______________________________________________ > > BackupPC-users mailing list > > Bac...@li... > > https://lists.sourceforge.net/lists/listinfo/backuppc-users > > |
From: <ma...@ph...> - 2002-01-04 02:34:37
|
Thats the one. Conceptually, relationship is a follows in DB table notation. FileTable fileid bigint, filename text, hostname text FileVersionTable fileid bigint, filevid int, bytes bigint, backupdate datetime DeltaTable deltaid bigint, digest char(16), checksum char(4), bytes int, refcount int FileVersionToDeltaTable filevid bigint, deltaid bigint, fileoffset bigint The data associated with a delta would live in the underlying filesystem not the database in some directory hierachy maybe based on the digest + deltaid. e.g. /AB/CD/EF/GH/IJ/KL/MN/OP/deltaid.file Handling variable block size does not become an issue since for any given file version, the maximum number of variable blocks generated by the source as a result of comparing against the file version's checksum's can only be one. Rsync (the application) only handles a variable block checksum under two conditions (from what I have read of the code): 1. When all fixed block size checksum's have matched and there is a variable block checksum left over as the remainder. 2. When the algorithm is processing near the end of a file where the given (file length - file offset) is less than the rsync fixed block size (700 bytes by default). Only during this range may a variable block checksum less than the fixed block size have any chance of matching. Variable block sizes greater than the fixed block size are not permitted. Other than those conditions a sliding checksum across 700 bytes is applied over the data stream and implements the rolling characteristics of the checksum. ************ 700 bytes ***********+ 700 bytes (shifted left 1 byte) **********++ 700 bytes (shifted left 1 byte) *********+++ 700 bytes (shifted left 1 byte) ********++++ 700 bytes (shifted left 1 byte) *******+++++ 700 bytes (shifted left 1 byte) ******++++++ 700 bytes (shifted left 1 byte) *****+++++++ 700 bytes (shifted left 1 byte) ****++++++++ 700 bytes (shifted left 1 byte) ***+++++++++ 700 bytes (shifted left 1 byte) **++++++++++ 700 bytes (shifted left 1 byte) *+++++++++++ 700 bytes (shifted left 1 byte) ++++++++++++ 700 bytes (shifted left 1 byte) etc.. Regards Peter Marelas ----- Original Message ----- From: "Peter L. Buschman" <pl...@io...> To: <ma...@ph...>; "Craig Barratt" <cr...@ar...> Cc: "Peter L. Buschman" <pl...@io...>; <bac...@li...> Sent: Friday, January 04, 2002 5:21 AM Subject: Re: [BackupPC-users] Reducing Network Requirements > > Peter: > > I think I see what you're getting at. You are describing an architecture > where the blocks are separated > from the files that reference them. > > In the same way that Craig's forest of hardlinks points duplicate files to > the same original file, block pointers > contained in deltas point duplicate blocks to data blocks in some kind of > datastore. > > What you term a "delta" below is a block of data of fixed size. Blocks (or > deltas as you term them) will not > be removed from the datastore until the reference count drops to zero. The > reference count will not drop to > zero until all file versions that use it have expired. > > Congratulations. You've just invented a filesystem with snapshot > capability. :) The difference here is that > most snapshot filesystems are limited in the number of snapshots they can > present at a single time. This > idea is rather more flexible since there are no implicit limits. The > underlying technique, however, is the same. > Done carefully, too, your concept could also accommodate variable > block-sizes (something key to improving > efficiency in the differencing algorithm) where snapshot filesystems > usually have fixed block sizes. > > I see some interesting modelling scenarios arising from this. It could be > a fascinating thing to implement given > all the unique variables and potential areas for tuning (BerkeleyDB anyone?) > > --PLB > > > > > > > At 12:04 AM 01/04/2002 +1100, ma...@ph... wrote: > >Ok...Simple picture.. > > > >File (f) has two backuped up versions f0 and f1. > > > >f0 = d0, d1, d2, d3 > >f1 = d0, d1, d2, d4 > > > >Where dX is a delta associated with a file (f) and X > >uniquely identifies the delta, that is it is different from > >any other delta. > > > >Assume we want to backup the file again. > >Assume f0 and f1 have not expired on the server (i.e. retention period) > >and assume the delta's d0 to d4 are still referenced by f0 and f1. > > > >Server sends client all delta's checksum's and digests referenced > >by f1 (last backup). They are d0, d1, d2 and d4 (We dont send > >d3 because it is not referenced by this files last backup). > > > >Client compares checksums/digests received against those generated > >from current file source. > > > >Client sends back two types of messages to server. > > > >1. Between offset X and Y delta dX matched. > >2. Between offset X and Y no delta matched use data Z instead. > > > >Server creates f2 by: > > > >1. Referencing existing delta's if 1) above > >2. Creating new delta's and referencing them if 2) above > > > >To restore version f1 one would merely concatenate > >the delta's referenced by f1 in offset order. > > > >Whats important is this.. > > > >1. A file is a collection of delta's. There is no concept of > > storing a complete file on the server. All backed up versions > > of a file are treated as a grouping of delta's. > >2. The file record contains the offsets at which the delta's > > are applied to form "the file data". > >3. A delta may be associated with more than one version > > of the file. > >4. We may chose to store multiple copies of the same delta > > only once. That is, before creating a new delta compute > > the delta's digest and compare the digest with all > > existing delta's digests (delta digest index). If match, > > reference existing delta. If no match, create new delta. > > > > This answers your question.. > > > > Also, what happens if another client has the same sequence of files > > f0, f1, f2, f3 (or if the same sequence appears elsewhere on the > > same client)? Can the deltas only be stored once? > >5. The recovery of a particular file version does not depend on the > > prescence of all previous file versions. > >6. A reference count will be maintained for each delta in existance. > > Once a delta is no longer referenced (because file versions are > > expired (retention)) the disk space associated with it is > > reclaimed (delta deleted). > >7. Delta's may be compressed to conserve even more disk space. > > > >Regards > >Peter Marelas > > > >----- Original Message ----- > >From: "Craig Barratt" <cr...@ar...> > >To: <ma...@ph...> > >Cc: "Peter L. Buschman" <pl...@io...>; > ><bac...@li...> > >Sent: Thursday, January 03, 2002 6:55 PM > >Subject: Re: [BackupPC-users] Reducing Network Requirements > > > > > > > > Rather than trying to explain (im doing a poor job of it) I'll make > > > > some points and get back to writing the proof of concept. Hopefully > > > > then it will all fall in place. > > > > > > > > Thus far i've converted the rsync crc to perl and testing the > > > > application of delta's. > > > > > > This sounds great! > > > > > > Perhaps one thing that would help is some better notation to unify > > > our discussions. > > > > > > Let's assume there's a file f on a client, and this file changes > > > over time. Let's call each version f0, f1, f2 where the numbers > > > refer to each time the backup program inspects it. It's possible > > > that f1==f2, or even (f1!=f2 and f1==f3). > > > > > > Currently BackupPC stores f0, f1, f2 as separate files, and uses > > > hardlinks in the case where any pair of files is identical. > > > > > > We agree that using an rsync-like technique, if the client has a new > > > file, f3, and the server has f2 (or can reconstruct it), then the > > > backup client can compute a delta between the two: > > > > > > d2 = delta(f2, f3) > > > > > > so that f3 can be constructed by knowing f2 and d2: > > > > > > f3 = apply(f2, d2) > > > > > > The clever part of rsync is that delta() can be computed without > > > knowing all of f2: just the block signatures. And the backup server > > > only needs to know f2 and d2. But you know that already. > > > > > > The point of this notation is so we can explicitly discuss what > > > is computed and stored. > > > > > > Example1: store f0, f1, f2, f3, with hardlinks between identical > > > files. That's what currently happens. > > > > > > Example2: store f0, d0, d1, d2. That's the first complete file > > > and the forward deltas. f3 can be recreated by applying, in turn, > > > each of d0, d1, d2 to f0. > > > > > > Example3: store r1, r2, r3, f3, where the r's are reverse deltas. > > > This way the last file is complete, and older files can be rebuild, > > > if needed, by applying one or more reverse deltas. > > > > > > Of course, there are much more complex examples (which you might be > > > getting at): doing everything on a block basis, not a file basis, > > > and somehow doing deltas on blocks, etc. We can add some notation > > > for this too. > > > > > > Also, what happens if another client has the same sequence of files > > > f0, f1, f2, f3 (or if the same sequence appears elsewhere on the > > > same client)? Can the deltas only be stored once? > > > > > > Craig > > > > > > _______________________________________________ > > > BackupPC-users mailing list > > > Bac...@li... > > > https://lists.sourceforge.net/lists/listinfo/backuppc-users > > > > > > _______________________________________________ > BackupPC-users mailing list > Bac...@li... > https://lists.sourceforge.net/lists/listinfo/backuppc-users > |
From: <ma...@ph...> - 2002-01-06 02:07:41
|
Embedded. ----- Original Message ----- From: "Peter L. Buschman" <pl...@io...> To: <ma...@ph...>; "Craig Barratt" <cr...@ar...>; "Peter L. Buschman" <pl...@io...> Cc: <bac...@li...> Sent: Friday, January 04, 2002 2:15 PM Subject: Re: [BackupPC-users] Reducing Network Requirements > > Check. Now the pieces all fall into place. :) > > I'm not entirely clear though, on how you are storing the blocks. When you > first store the blocks for a file, > are you splitting it up into fixed blocks and storing each block > independently (I'm going to use block when > to mean a fixed length data block and delta to mean a file of bytestreams + > block pointers) or are you effectively > storing the entire file and referencing back to it? Only the former would > make sense to me in this architecture > since you need to retain the ability to selectively expire blocks from the > original file. * splitting it up into fixed blocks and storing each block independently > My point about variable block sizes is that the efficiency of the > differencing algorithm for a single file > can vary significantly by the block size that rsync uses to divide the > source file into fixed-length blocks. > For copying purposes, the block size can thus vary from invocation to > invocation since the blocks do > not need to be stored once the synchronization is complete. true. > For data backup, however, you are fixing the block size at backup > time. For a given file, the block size > thus needs to stay static to be of any use. However, there is still the > possibility of using differing block sizes > for other files to improve efficiency. Thus, small, rapidly changing files > might use a block size of 16k while > large binary databases of infrequently changed data could be more > efficiently differenced with a block size of > 1024k. The optimum block size will vary significantly depending on the > type of file and I consider it unlikely > that a one size fits all block size will prove practical in this scenario. rsync the application uses a static block size of 700 bytes by default unless specified in the command line. Im pretty comfortable that a static fixed block size across the board will result in 'a substancial performance gain' overall in comparison to not using the algorithm. Consider a 20GB file at 32K fixed blocks. The server sends the client 6.25MB of data (compressed checksums/digests) for the algorithm to commence. To transfer 6.25MB will take less than 6 seconds over 10 BaseT ethernet. To transfer 20GB will take 4.55 hours. To transfer 50% of 20GB will take 2.27 hours. Long term, there are other things we could do to improve the situation with varying data sets. We could maintain a hierachy of checksums/digests based on different fixed block sizes as follows on a per file basis. ---------------------------------------------------------------------------- ---- 20GB file ****************************** ****************************** 10GB blocks ************** **************** *************** ************** 5GB blocks ******* ****** ******* ******** ******* ******* ******** ******* 2.5GB blocks etc,etc. We would do a first pass starting with 10GB. If any block matches we ignore the start and end offset of the given file from herein. We then do a second pass with 5GB, then third with 2.5GB and so on. This method allows us to formulate a rule which says if file F is a multiple of X SIZE maintain N=F/X checksum/digest hierachies of size Y. Put it into practice if file of size 14GB is a multiple of 1GB maintain 14=14/1 checksum/digest hierachies of size 32K. So we have 32*1=32k, 32*2=64k, 32*3=96k, 32*4=128k, 32*5=160k,...32*14=448k So the first pass (448k) will then only require 0.3125 MB of compressed checksums+digests to be sent from the server to client for a 14GB file. Its important to note we are duplicating the number of checksum's/digests we maintain, however we are not duplicating the actual data stored on the server. The overhead associated with this is multiple reads of the source file and also the destination blocks when they are saved on the server. Regards Peter Marelas |
From: Peter L. B. <pl...@io...> - 2002-01-07 00:22:16
|
Comments below :-) >Im pretty comfortable that a static fixed block size across the board will >result in 'a substancial performance gain' overall in comparison to >not using the algorithm. > >Consider a 20GB file at 32K fixed blocks. The server sends the client >6.25MB of data (compressed checksums/digests) for the algorithm to >commence. To transfer 6.25MB will take less than 6 seconds over 10 BaseT >ethernet. > >To transfer 20GB will take 4.55 hours. >To transfer 50% of 20GB will take 2.27 hours. Agreed, but my point is regarding the efficiency of the long-term storage space going forward, not the bandwidth saved during the transfer. When you fix the block size at the beginning, you eliminate changing the block size (as derived via offsets from zero in the original file) as a valid optimization in the future. Rapidly-changing files are likely to benefit more from variable block sizes in terms of storage space required for the deltas than files that change relatively little. >Long term, there are other things we could do to improve the situation with >varying data sets. We could maintain a hierachy of checksums/digests based >on different fixed block sizes >as follows on a per file basis. > >---------------------------------------------------------------------------- >---- 20GB file >****************************** ****************************** 10GB blocks >************** **************** *************** ************** 5GB blocks >******* ****** ******* ******** ******* ******* ******** ******* 2.5GB >blocks Yes, but you lose the efficiency implicit in the rsync algorithm as traditionally implemented because the boundaries of the blocks are already fixed from the first backup. The block offsets are still derived from the block sizes used the very first time the file and blocks were backed up. Note that I don't have a perfect solution to this problem yet (return to my point about the lack of a cumulative checkpoint in the algorithm) I just happen to believe that the power of the rsync algorithm lies more in being able to generate a delta from one version of a file to another with whatever blocksize makes the most sense at the time, not in the base differencing function. Eliminating the ability to use variable block sizes also eliminates the heart of the algorithm's efficiency and general-purpose capability. Just my $0.02 worth and probably not a universal opinion. Take that for what it's worth ;-) --PLB >etc,etc. > >We would do a first pass starting with 10GB. If any block matches we ignore >the start and end offset >of the given file from herein. We then do a second pass with 5GB, then third >with 2.5GB >and so on. > >This method allows us to formulate a rule which says if file F is a multiple >of X SIZE maintain >N=F/X checksum/digest hierachies of size Y. > >Put it into practice if file of size 14GB is a multiple of 1GB maintain >14=14/1 checksum/digest hierachies >of size 32K. So we have 32*1=32k, 32*2=64k, 32*3=96k, 32*4=128k, >32*5=160k,...32*14=448k > >So the first pass (448k) will then only require 0.3125 MB of compressed >checksums+digests to be sent >from the server to client for a 14GB file. > >Its important to note we are duplicating the number of checksum's/digests we >maintain, however we are >not duplicating the actual data stored on the server. > >The overhead associated with this is multiple reads of the source file and >also the destination blocks when they >are saved on the server. > >Regards >Peter Marelas |
From: Craig B. <cr...@ar...> - 2002-01-06 06:34:59
|
Peter, Thanks for the continuing dialog. With the little time I have I am mostly trying to work on v1.04, so I haven't had too much time to think about this stuff. You get all the fun! > We would do a first pass starting with 10GB. If any block matches > we ignore the start and end offset of the given file from herein. > We then do a second pass with 5GB, then third with 2.5GB and so on. It might be risky to have such large blocks. The 32 bit checksum and 128 bit MD5 digest provide a 160 bit "signature". Rsync depends upon a match of the signature to guarantee that the blocks are the same. For blocks of more than 20 bytes (160 bits) there is a non-zero chance two different blocks will have the same signature. For reasonable-sized blocks the chance is vanishingly small. But for larger and larger blocks the probability increases. On another topic, I did run two benchmarks that might be of interest to you. These are based on a 143GB (compressed) pool with 1.4 million files, resulting from backing up about 1200GB of data from 100 laptops (three fulls plus six incrementals). The first test was dividing each pool file (after uncompressing) into 16k blocks, on 16k boundaries, and counting how many 16k blocks were unique (the last block of each file had size <= 16k). There were 15,973,672 blocks of which 11,415,357 were unique. So breaking files into 16k blocks, in this case, gives maybe a 25-30% saving in storage (ignoring the extra storage required to represent each file as concatenated blocks, and handling reference counts). I haven't tried smaller blocks, nor did I check that the 11 million unique blocks compress as well as the 16 million original ones (they might not). The second test was seeing whether storing reverse deltas between identically named files on the same host would help. The criteria was that a file would only be replaced by a delta if the file was not shared (hardlinked) elsewhere. This yielded about 37,000 files (out of 1.4 million) that would be replaced by deltas, saving about 26GB of storage (out of 143GB). So a simple delta strategy on identically named files might save around 15-20% of pool storage. The results from each of these two tests can't be added together, since there is some overlap in what they are taking advantage of. For example, a user's mail folder (eudora in.mbx or outlook.pst) that is slightly changed each day is current stored each time in its entirity. Splitting it into fixed size blocks will save a good deal (unless an earlier part of the file changed, shifting the data), and doing deltas will also save a good deal. This doesn't exactly correspond to what you are trying, but I thought you might be interested in some results from one real data set. Regards, Craig |
From: <ma...@ph...> - 2002-01-07 11:32:44
|
> > We would do a first pass starting with 10GB. If any block matches > > we ignore the start and end offset of the given file from herein. > > We then do a second pass with 5GB, then third with 2.5GB and so on. > > It might be risky to have such large blocks. The 32 bit checksum and > 128 bit MD5 digest provide a 160 bit "signature". Rsync depends upon > a match of the signature to guarantee that the blocks are the same. For > blocks of more than 20 bytes (160 bits) there is a non-zero chance two > different blocks will have the same signature. For reasonable-sized > blocks the chance is vanishingly small. But for larger and larger > blocks the probability increases. True. Something we need to think through if we cant find an optimal block size. > On another topic, I did run two benchmarks that might be of interest > to you. These are based on a 143GB (compressed) pool with 1.4 million > files, resulting from backing up about 1200GB of data from 100 laptops > (three fulls plus six incrementals). > > The first test was dividing each pool file (after uncompressing) > into 16k blocks, on 16k boundaries, and counting how many 16k blocks > were unique (the last block of each file had size <= 16k). There > were 15,973,672 blocks of which 11,415,357 were unique. So breaking > files into 16k blocks, in this case, gives maybe a 25-30% saving in > storage (ignoring the extra storage required to represent each file > as concatenated blocks, and handling reference counts). I haven't > tried smaller blocks, nor did I check that the 11 million unique > blocks compress as well as the 16 million original ones (they might > not). Well its clear the current regime is doing a good job of minimising storage space already 143GB versus 1200GB. I just want to point out again the benefits of adopting the alforithm will lean more towards network utilisation rather than storage. While I expect storage usage to reduce even further it wont be anywhere near as dramatic as the reduction of network utilisation and ultimately the duration of the backup window. > The second test was seeing whether storing reverse deltas between > identically named files on the same host would help. The criteria > was that a file would only be replaced by a delta if the file was not > shared (hardlinked) elsewhere. This yielded about 37,000 files (out > of 1.4 million) that would be replaced by deltas, saving about 26GB > of storage (out of 143GB). So a simple delta strategy on identically > named files might save around 15-20% of pool storage. > > The results from each of these two tests can't be added together, > since there is some overlap in what they are taking advantage of. > For example, a user's mail folder (eudora in.mbx or outlook.pst) > that is slightly changed each day is current stored each time in > its entirity. Splitting it into fixed size blocks will save a > good deal (unless an earlier part of the file changed, shifting > the data), and doing deltas will also save a good deal. > > This doesn't exactly correspond to what you are trying, but I > thought you might be interested in some results from one real > data set. Its good to have a data set to measure against. I certainly dont have 200GB of disk lying around spare or 100 laptops. I'ld be interested in the same figures using smaller blocks and larger blocks. i.e. 4k, 8k, 32k, 64k. Regards Peter Marelas |
From: Craig B. <cr...@ar...> - 2002-01-08 07:02:39
|
> Its good to have a data set to measure against. I certainly dont have > 200GB of disk lying around spare or 100 laptops. I'ld be interested in the > same figures using smaller blocks and larger blocks. > i.e. 4k, 8k, 32k, 64k. Yes, a data set is very useful for benchmarking. Of course, my data set might be different to other installations. Perhaps in the future people on this list might like to run some well-defined benchmarks on their systems too? Other block sizes is a good idea. It will be a few weeks until I get to this because my current implementation (one perl script that passes over the whole tree and does $Count{MD5(block)}++) needs a huge amount of memory (around 1GB) with 16k blocks. I guess perl ends up needing about 80-100 bytes to store each entry in the hash (it has 11 million entries). 32k and 64k are no problem. I'll do them this weekend with my current script. I'll have to either write it in C or write some scripts that do multiple passes using temporary files which are merged in a later step. I'll probably pick the latter, but I need to work more on v1.04 first. Regards, Craig |
From: Craig B. <cr...@ar...> - 2002-02-11 21:30:47
|
peter> Its good to have a data set to measure against. I certainly peter> dont have 200GB of disk lying around spare or 100 laptops. peter> I'ld be interested in the same figures using smaller blocks peter> and larger blocks. peter> i.e. 4k, 8k, 32k, 64k. craig> I'll have to either write it in C or write some scripts that do multiple craig> passes using temporary files which are merged in a later step. I'll craig> probably pick the latter, but I need to work more on v1.04 first. peter> use Fcntl; peter> use SDBM_File; peter> tie(%Count, 'SDBM_File', '/tmp/md5_hash', O_RDWR|O_CREAT|O_TRUNC, 0644); peter> $Count{MD5(block)}++; peter> untie(%Count); Nice suggestion! I tried this out but the sdbm files got pretty large (over 2GB) for the small block sizes, and for some reason it got quite slow even when less than 10% done. Anyhow, I implemented a two-step solution: computing all the block hashes and different block sizes and writing them to files (almost 6GB for the 1k block size case), then doing the counting in multiple passes to avoid large memory use. Here are the results (counting all the blocks and unique blocks for different block sizes in a pool that is around 240GB uncompressed): Block size Total Count Unique Count Percentage duplicate 1024 248015738 151849516 38.8% 2048 124446044 78608689 36.8% 4096 62693124 41013766 34.6% 8192 31868433 21806649 31.6% 16384 16500899 11627485 29.5% 32768 8853617 6501388 26.6% 65536 5073159 3950319 22.1% Craig |
From: <ma...@ph...> - 2002-02-12 08:04:57
Attachments:
sync
|
Craig Barratt writes: > peter> Its good to have a data set to measure against. I certainly > peter> dont have 200GB of disk lying around spare or 100 laptops. > peter> I'ld be interested in the same figures using smaller blocks > peter> and larger blocks. > peter> i.e. 4k, 8k, 32k, 64k. > > craig> I'll have to either write it in C or write some scripts that do multiple > craig> passes using temporary files which are merged in a later step. I'll > craig> probably pick the latter, but I need to work more on v1.04 first. > > peter> use Fcntl; > peter> use SDBM_File; > peter> tie(%Count, 'SDBM_File', '/tmp/md5_hash', O_RDWR|O_CREAT|O_TRUNC, 0644); > peter> $Count{MD5(block)}++; > peter> untie(%Count); > > Nice suggestion! I tried this out but the sdbm files got pretty large > (over 2GB) for the small block sizes, and for some reason it got quite > slow even when less than 10% done. > > Anyhow, I implemented a two-step solution: computing all the block > hashes and different block sizes and writing them to files (almost > 6GB for the 1k block size case), then doing the counting in multiple > passes to avoid large memory use. > > Here are the results (counting all the blocks and unique blocks for > different block sizes in a pool that is around 240GB uncompressed): > > Block size Total Count Unique Count Percentage duplicate > 1024 248015738 151849516 38.8% > 2048 124446044 78608689 36.8% > 4096 62693124 41013766 34.6% > 8192 31868433 21806649 31.6% > 16384 16500899 11627485 29.5% > 32768 8853617 6501388 26.6% > 65536 5073159 3950319 22.1% Thanks for that. These are based on comparing against fixed block size boundaries correct? i.e. for 1024 block size comparing at offset 0, 1024, 2048 as opposed to 0, 1, 2, 3, 4, 5, 6, etc.. The CRC algorithm has been written in perl for some time now and its surprisingly fast. Ive been experimenting with digest algorithms other than MD4 as I've read collisions have been found with MD4. Ive also experimented with techniques for representing the digests and crcs in a compressed form to the host performing the comparison. Thus far with a 192bit hash and 1024 byte block size (rsync uses 700bytes by default) there is between a 1% to 3% observed overhead per file which in my opinion is optimal considering the savings (> 38.8%). Otherwise if we stick with MD4 (128 bits) the observed overhead is between 1% and 2%. Regards Peter Marelas |
From: Craig B. <cr...@ar...> - 2002-02-15 00:20:42
|
> > Block size Total Count Unique Count Percentage duplicate > > 1024 248015738 151849516 38.8% > > 2048 124446044 78608689 36.8% > > 4096 62693124 41013766 34.6% > > 8192 31868433 21806649 31.6% > > 16384 16500899 11627485 29.5% > > 32768 8853617 6501388 26.6% > > 65536 5073159 3950319 22.1% > > Thanks for that. > > These are based on comparing against fixed block size boundaries correct? > i.e. for 1024 block size comparing at offset 0, 1024, 2048 as opposed to > 0, 1, 2, 3, 4, 5, 6, etc.. That's right: the blocks are on multiples of the block size, so the 1024 block size are the blocks starting at offset 0, 1024, 2048, ... The last block of each file might be partial. Note that the savings are without compression. Adding compression will tend to reduce these numbers somewhat for two reasons: - The most common repeated block is all 0's. In the 1024 case the most common repeated block occurs 8171676 times, accounting for almost 10% of the total number of repeated blocks. These blocks stored in the original files will tend to compress very well, so the gains from block reuse will be lower by a couple of percent. - Because of the granularity of disk storage (eg: 512 byte blocks or often bigger on larger storage devices), storing small blocks as separate files might give no compression. Eg: a 1K block might compress to 600 bytes, but that's still two 512 byte blocks. To estimate the impact of these two issues I would have to add code that actually compresses each unique block to see how well it compresses and then keep track of the compressed savings. Craig |
From: <ma...@ph...> - 2002-02-15 01:25:19
|
Craig Barratt writes: >> > Block size Total Count Unique Count Percentage duplicate >> > 1024 248015738 151849516 38.8% >> > 2048 124446044 78608689 36.8% >> > 4096 62693124 41013766 34.6% >> > 8192 31868433 21806649 31.6% >> > 16384 16500899 11627485 29.5% >> > 32768 8853617 6501388 26.6% >> > 65536 5073159 3950319 22.1% >> >> Thanks for that. >> >> These are based on comparing against fixed block size boundaries correct? >> i.e. for 1024 block size comparing at offset 0, 1024, 2048 as opposed to >> 0, 1, 2, 3, 4, 5, 6, etc.. > > That's right: the blocks are on multiples of the block size, so the > 1024 block size are the blocks starting at offset 0, 1024, 2048, ... > The last block of each file might be partial. > > Note that the savings are without compression. Adding compression will > tend to reduce these numbers somewhat for two reasons: > > - The most common repeated block is all 0's. In the 1024 case the > most common repeated block occurs 8171676 times, accounting for > almost 10% of the total number of repeated blocks. These blocks > stored in the original files will tend to compress very well, so > the gains from block reuse will be lower by a couple of percent. > > - Because of the granularity of disk storage (eg: 512 byte blocks > or often bigger on larger storage devices), storing small blocks > as separate files might give no compression. Eg: a 1K block > might compress to 600 bytes, but that's still two 512 byte > blocks. > > To estimate the impact of these two issues I would have to add > code that actually compresses each unique block to see how well > it compresses and then keep track of the compressed savings. I would hold off on compressing the delta's themselves. Using the algorithm in itself is a form of compression and will ultimately require considerable processing power in the backend to make it all work. Compressing the delta's would only worsen this for what I imagine would be a smaller gain. In regards to blocks full of 0's these would normally be delt with as sparse files by the underlying filesystem in which case storage is not actually allocated for them out of the available free blocks. Regards Peter Marelas |
From: Craig B. <cr...@ar...> - 2002-02-15 02:07:35
|
> I would hold off on compressing the delta's themselves. > Using the algorithm in itself is a form of compression and will > ultimately require considerable processing power in the backend to > make it all work. Compressing the delta's would only worsen this for > what I imagine would be a smaller gain. Ok, but compression of complete files (already supported by BackupPC) yields around a 40% saving in overall storage (YMMV). If you represent everything as uncompressed blocks you will get up to a 40% saving instead. Unless you get some additional benefit (eg: from blocks at all file offsets or something similar), there doesn't seem to be any storage gain for all the added complexity. > In regards to blocks full of 0's these would normally be delt with as > sparse files by the underlying filesystem in which case storage is not > actually allocated for them out of the available free blocks. Agreed. BackupPC already seeks over chunks of initial 0x0 bytes when compression is off, although it doesn't do it in the middle of a file. When compression is on it simply compresses everything, since long streams of repeated bytes compress very well. Regards, Craig |
From: <ma...@ph...> - 2002-02-15 02:29:50
|
Craig Barratt writes: >> I would hold off on compressing the delta's themselves. >> Using the algorithm in itself is a form of compression and will >> ultimately require considerable processing power in the backend to >> make it all work. Compressing the delta's would only worsen this for >> what I imagine would be a smaller gain. > > Ok, but compression of complete files (already supported by BackupPC) > yields around a 40% saving in overall storage (YMMV). If you represent > everything as uncompressed blocks you will get up to a 40% saving > instead. Unless you get some additional benefit (eg: from blocks at all > file offsets or something similar), there doesn't seem to be any storage > gain for all the added complexity. The benefits you get from using delta's are: 1. a major reduction in network utilisation (you dont get that with server side compression) 2. reduced storage without using a compression algorithm 3. I would also suggest backend processor utilisation would be reduced Lastly, the saving of using the algorithm will be much greater than 40% of storage given you've already realised 38% at fixed file offsets. Regards Peter Marelas |
From: Peter L. B. <pl...@io...> - 2001-12-29 02:53:04
|
I've been puzzling over this one for a few days. I've been using rsync from Windows 2000 to a Linux server quite successfully (using the cygwin port of rsync.) I don't see an effective way to use the stock rsync package with the BackupPC file structure unless the server is modified. However, I do believe that _only_ the server side need be modified for this to work. The server process has to be able to read the file delta information from a different location than is actually being written to and also has to be intelligent to substitute hardlinks for identical files. This is seem at first glance to be a trivial modification to rsyncd (really rsync --daemon) but means that only the piece being run on the backup server need be re-compiled. If the result of the rsync process produces the same file/directory/link structure that a normal smbclient-based backup produces, the .cgi interface and other processes should all work un-modified. > > Are there plans to implement a prorietary client to minimise network usage > > by implementing true incremental/delta backups? a.la rsync algorithm or > > equivalent. > >I am planning on adding tar over ssh and eventually rsync as >additional transport layers for unix/linux clients. Rsync might >need a few additional features to make it work with BackupPC, but >I still need to see if I can make it work with an unmodified rsync. > >I haven't contemplated doing a custom client, mainly because I don't >know a thing about win32 development and I generally like the idea >of not needing to install or maintain client-side software. For >unix/linux, rsync (or a slight addition to it) should work well. >For win32, in addition to reducing network traffic, a custom client >might also be able to workaround open-file and file locking issues, >and also provide faithful saving of file attributes. Discovering open files from Win32 Perl is a fairly trivial task. Assuming that the server-side rsync issue can be solved (and I fully believe it is a simple mod), a perl wrapper could generate a list of open files and perform any necessary activities (skipping, shutting down the locking program, ignoring, etc.,) before passing the list to rsync via an include list. Using an environment like cygwin (which has its faults and advantages), both ssh and rsync could be used in combination (ssh to allow server-initiated backups and also for secure tunnelling of rsync if desired) without having a great deal of differences between Unix and Windows as far as the backup server is concerned. > > By splitting file data into delta's (compared across and referenced by > > complete data set) > > I suspect online disk requirements can be reduced much much more. > >Yes!! I have been thinking about using something like xdelta1 >(see http://sourceforge.net/projects/xdelta) to do binary file >deltas, but that would only be against the previous file of the >same name from the same machine. I have to put a plug in here for the rsync algorithm since the tool has already received so much attention. (Appropriate too, since Andrew Tridgell also wrote Samba, which BackupPC already uses.) (There is a nice writeup on the rsync differencing algorithm in chapter 3.) http://samba.org/~tridge/phd_thesis.pdf >Better yet (as you suggest), I have also been thinking that there >should be a way to change the pool to be a pool of snippets or >deltas, rather than complete files. This could improve the overall >storage efficiency from the current 6-8x to perhaps 20x or more, >which would be really great. The problem is I haven't figured out >how to do this. Suggestions and discussion are welcome! This is certainly do-able, but it would require significant changes to the server side daemons to accomplish since the present daemons are only capable of looking to on-disk files for the deltas and checksums that are necessary (at least for rsync which is the only tool I've studied.) Given a differencing library like xdelta or librsync (http://rproxy.samba.org/doxygen/librsync/), having delta metadata queried from a database rather than generated dynamically from the files themselves becomes achievable. > > Lastly, should consider the structure of files on disk to > > support integration with a HSM backend (for tape storage) > > inline with data retention. As opposed to writing your own. > >These issues are very important. The current hardlink structure >is not friendly to many tape backup systems. I'm a novice in the >area of tape backup systems, so I'd be very happy to learn more >and figure out how to better glue BackupPC into other backend >systems (both open source and commercial). Depending on how tight you want the integration to be, no modification may be necessary. Many HSM implementations appear to the host operating system as just an extraordinarily large filesystem. Files are migrated to tape based on access times or other policies, but in all other respects remain visible to the operating system (inode data remains cached.) The only time the presence of tape is detectable occurs when a migrated file is opened because the open() system call takes much longer to complete (perhaps minutes or longer) due to the file needing to be read back from tape and cached. Some systems like ADIC's AMASS tape filesystem make efficient use of disk-space, though, to efficiently cache IO to migrated files so that the tape penalty does not become prohibitive. Given a large-enough tape library, virtual filesystems of many terabytes are quite possible, supported by a much smaller amount of spinning disk. An open source HSM system would be a worthy project in and of itself. ;-) > > Their my thoughts, happy to code and contribute, however looking for > > direction and an > > understanding of what is already in the works. > >If you want to help design and code that would be great!! Here's my >current roadmap for v1. Dramatic improvements (like making the pool >an rsync-like database of snippets and adding client tools) would >probably form the basis of v2: > > 1. Adding tar over ssh as an alternative to smbclient for unix/linux > clients. This will allow symlinks and other special files to be > backed up correctly. Later I will add rsync as a third transport > layer (in addition to smb and tar/ssh). Hmm.... this might be a dumb question, but why not start with just backing up Unix/Linux clients via an NFS export? The NFS mount could be brought up at backup time and scanned with ordinary filesystem tools (find, etc.,) or their equivalent Perl functions. Disk usage is minimized too since you only need copy files once you have identified them as non-redundant. (Note...this approach, while probably simpler, is inferior from a security perspective to a tar/ssh solution. It is, however, closer to the smbclient method that BackupPC presently uses for backup.) > 2. Providing a utility to copy the pool and all data files. Useful for > efficiently migrating the BackupPC data to a new (bigger) filesystem > while preserving all the hardlinks. (Perhaps gnu "cp -dR" will be > fast enough instead; I'll benchmark both.) How about dump / restore? Those are guaranteed to restore filesystem structure, including preserving hardlinks. (These are not available for all filesystem types, however.) > 3. Saving attributes (unix owner, group, permissions, mtime, atime etc). > I don't know enough about Windows ACLs to know how to save them too > (this would need updates to smbclient). > > 4. Generating zip or tar archives for restore. Currently files can > only be restored one at a time, unless you mount the server's disk > and drag files from the client. Generating a zip or tar archive > will allow the original attributes to be merged and restored too. > > 5. Ability to split the pool across several file systems. Since > I use hardlinks to efficiently store repeated files, everything > must currently be on a single file system. New 120GB drives > are just becoming available, so you could run BackupPC on two > or three 120GB file systems without worrying about merging the > physical drives into one big file system. Tools will allow you > to resplit the pool if you need to add more drives later. This is a tricky one to achieve if you wish to retain the hardlink structure since hardlinks cannot cross filesystems. You'd have to switch to symbolic links which might have unpredictable side-effects. Perhaps a better approach would be to leave disk-spanning to a software raid layer on the server operating system? Most Unix versions today, as well as Linux, ship with basic software raid that allows the creation of virtual volumes upon which normal filesystems can be created. Many even allow dynamic increasing of such volumes (with the appropriate raid level) as disks are added to a system. --PLB > 6. Update the CGI script BackupPC_Admin so it will optionally > run under mod_perl. This would require a dedicated httpd, > running as the BackupPC user. The advantages are that it > would eliminate the current setuid, and it would be much > faster (it would have persistent connections to the BackupPC > server, and also cache the hosts file). > > 7. Implementing binary file diffs so that files with small changes are > stored in a binary diff form (maybe using xdelta1). > >I'm planning on implementing 1-3 for the next version (v1.04), hopefully >by mid or late January, and maybe the next two or three for the version >after that. > >If you want to pitch in with, say, #4 or #6, or instead look at longer >term goals (pool structure, optional client side software, or backend >tape integration), then that would be great! > >Regards, >Craig > >_______________________________________________ >BackupPC-users mailing list >Bac...@li... >https://lists.sourceforge.net/lists/listinfo/backuppc-users |
From: <ma...@ph...> - 2001-12-29 06:04:09
|
Comments embedded.. ----- Original Message ----- From: "Craig Barratt" <cr...@ar...> To: <ma...@ph...> Cc: <bac...@li...> Sent: Saturday, December 29, 2001 10:45 AM Subject: Re: [BackupPC-users] Reducing Network Requirements > > Are there plans to implement a prorietary client to minimise network usage > > by implementing true incremental/delta backups? a.la rsync algorithm or > > equivalent. > > I am planning on adding tar over ssh and eventually rsync as > additional transport layers for unix/linux clients. Rsync might > need a few additional features to make it work with BackupPC, but > I still need to see if I can make it work with an unmodified rsync. > > I haven't contemplated doing a custom client, mainly because I don't > know a thing about win32 development and I generally like the idea > of not needing to install or maintain client-side software. For > unix/linux, rsync (or a slight addition to it) should work well. > For win32, in addition to reducing network traffic, a custom client > might also be able to workaround open-file and file locking issues, > and also provide faithful saving of file attributes. Im pretty sure theres enough in ActivePerl to support the required Win32 API calls one would need to write a basic proof of concept client. If its all good converting to an alternative language would be an option. I think its important to move to a custom client to be able to extend the softwares feature set. I do backup and recovery for a living and the most frequent problem I see is slow networks. Dont know if your aware, there is a similar commericial product that does what BackupPC does but alot more. Its called Veritas Netbackup Proffesional. Have a look at http://www.veritas.com/products/category/ProductDetail.jhtml?productId=nbupr o you may get some ideas. > > > By splitting file data into delta's (compared across and referenced by > > complete data set) > > I suspect online disk requirements can be reduced much much more. > > Yes!! I have been thinking about using something like xdelta1 > (see http://sourceforge.net/projects/xdelta) to do binary file > deltas, but that would only be against the previous file of the > same name from the same machine. > > Better yet (as you suggest), I have also been thinking that there > should be a way to change the pool to be a pool of snippets or > deltas, rather than complete files. This could improve the overall > storage efficiency from the current 6-8x to perhaps 20x or more, > which would be really great. The problem is I haven't figured out > how to do this. Suggestions and discussion are welcome! One option is to maintain logical references (pointers) to delta's. The pointers a file points to make up the file itself. The pointers and file attributes would be maintained in some form of a database. Be it an SQL RDBMS (www.postgresql.org) or an inverted index library like Berkeley DB (www.sleepycat.com). I think using rsync itself verbatim is probably not a good idea considering it would need to calculate the checksum's and digest (on the server side) each time a file is considered for backup. My view a better option would be to use the delta algorithm but not the rsync application itself. This way one could keep records of the checksums and digests for all delta's on the server side without having to recalculate them each time. > > Lastly, should consider the structure of files on disk to > > support integration with a HSM backend (for tape storage) > > inline with data retention. As opposed to writing your own. > > These issues are very important. The current hardlink structure > is not friendly to many tape backup systems. I'm a novice in the > area of tape backup systems, so I'd be very happy to learn more > and figure out how to better glue BackupPC into other backend > systems (both open source and commercial). Ive only dealt with commercial HSM solutions and the previous email from Peter explains the concept well. I guess from a long term perspective if BackupPC were to move away from managing files on disk, to managing files in a database and delta's on disk, then the structure of files on disk to support integration with a HSM backend should become irrelevant. > > Their my thoughts, happy to code and contribute, however looking for > > direction and an > > understanding of what is already in the works. > > If you want to help design and code that would be great!! Here's my > current roadmap for v1. Dramatic improvements (like making the pool > an rsync-like database of snippets and adding client tools) would > probably form the basis of v2: > > 1. Adding tar over ssh as an alternative to smbclient for unix/linux > clients. This will allow symlinks and other special files to be > backed up correctly. Later I will add rsync as a third transport > layer (in addition to smb and tar/ssh). > > 2. Providing a utility to copy the pool and all data files. Useful for > efficiently migrating the BackupPC data to a new (bigger) filesystem > while preserving all the hardlinks. (Perhaps gnu "cp -dR" will be > fast enough instead; I'll benchmark both.) > > 3. Saving attributes (unix owner, group, permissions, mtime, atime etc). > I don't know enough about Windows ACLs to know how to save them too > (this would need updates to smbclient). Most commercial Unix systems now provide ACL's as well. Example, Solaris. > 4. Generating zip or tar archives for restore. Currently files can > only be restored one at a time, unless you mount the server's disk > and drag files from the client. Generating a zip or tar archive > will allow the original attributes to be merged and restored too. A popular commercial backup product uses a modified version of GNU tar for backup and recovery (to tape). I think following a similar concept (potentially looking at star http://www.fokus.gmd.de/research/cc/glone/employees/joerg.schilling/private/ star.html) would be ideal. > 5. Ability to split the pool across several file systems. Since > I use hardlinks to efficiently store repeated files, everything > must currently be on a single file system. New 120GB drives > are just becoming available, so you could run BackupPC on two > or three 120GB file systems without worrying about merging the > physical drives into one big file system. Tools will allow you > to resplit the pool if you need to add more drives later. I agree with Peter's previous comments in that this issue can and probably should be delt with outside of the application. That is, some form of Logical Volume Manager. > 6. Update the CGI script BackupPC_Admin so it will optionally > run under mod_perl. This would require a dedicated httpd, > running as the BackupPC user. The advantages are that it > would eliminate the current setuid, and it would be much > faster (it would have persistent connections to the BackupPC > server, and also cache the hosts file). I would also consider SpeedyCGI (http://www.cpan.org/modules/by-module/CGI/CGI-SpeedyCGI-2.11.tar.gz) as an alternative if you dont want to enforce the need for Apache. > 7. Implementing binary file diffs so that files with small changes are > stored in a binary diff form (maybe using xdelta1). > > I'm planning on implementing 1-3 for the next version (v1.04), hopefully > by mid or late January, and maybe the next two or three for the version > after that. > > If you want to pitch in with, say, #4 or #6, or instead look at longer > term goals (pool structure, optional client side software, or backend > tape integration), then that would be great! I think it would be a good idea if the current version continues as is and I will spend some time on producing pilot code to test long term goal's. In particular: 1. Client/Server model that results in the network transfer of delta's 2. Server model that stores delta's and references to them. I will update the list as it unvails. Regards Peter Marelas |
From: Peter L. B. <pl...@io...> - 2001-12-29 20:45:11
|
Responses in thread below: >Im pretty sure theres enough in ActivePerl to support the required >Win32 API calls one would need to write a basic proof of concept >client. There is precious little in the Win32 API that ActivePerl and its assorted modules do not allow access to. Perl on Win32 has, to my own surprise, grown to be as rich and powerful an operating system control mechanism as Perl on Unix has been. The definitive books in this area seem to be by David Roth (http://www.roth.net/) and cover many, many examples (I've only just started expanding to the Win32 world in Perl, having done most of my development on Unix variants.) >If its all good converting to an alternative language >would be an option. > >I think its important to move to a custom client to be able to >extend the softwares feature set. I do backup and recovery >for a living and the most frequent problem I see is slow networks. Some issues worth considering on the custom-client route: 1. Create an open command/response protocol specified in the style of the RFCs. This leaves open the possibility of letting others develop unique clients that will plug seamlessly into the system as long as they implement the protocol properly. I can use a POP3/SMTP compatible mailer with any POP3/SMTP server regardless of whether they are from the save vendor or not. That is something I wish I could do with backup software (I too work with large network backup systems professionally, and the lock-in that the big vendors like Veritas and Legato force on their customers is draconian.) I would love to see a situation where standardized protocols exist between the client-side and server-side in network backup systems (and I consider NDMP to be far too low-level for this purpose.) >Dont know if your aware, there is a similar commericial >product that does what BackupPC does but alot more. >Its called Veritas Netbackup Proffesional. >Have a look at >http://www.veritas.com/products/category/ProductDetail.jhtml?productId=nbupr >o >you may get some ideas. NetBackup Professional shares s a lot of similarities in the basic design with BackupPC. Although NBU Pro (which is a completely different product from NBU BusinessServer or DataCenter editions) has a native-client architecture, it too relies on an on-disk datastore and has no integration with tape libraries. Backup of the datastore is left to the system administrator and some other software package. Legato has a Networker Laptop edition that also has similar features. A centralized on-disk datastore that elilminates redundant files seems to have become the industry norm for pitching "laptop" oriented backup solutions. For some reason, though, these solutions have typically been implemented as point-products rather than being fully integrated with the vendor's enterprise tape backup solutions. As a backup administrator, I hate the idea of having to manage yet another backup package with a completely different set of commands and control interfaces, especially when it comes from the same vendor as one of my other solutions. I think BackupPC is a great step in the right direction towards filling a gap between the capabilities of open source backup applications and the commercial applications presently available. If we put our heads together, I'm sure we can bring it up to a par with the vendor offerings already on the table. >One option is to maintain logical references (pointers) to delta's. >The pointers a file points to make up the file itself. >The pointers and file attributes would be maintained in some form of >a database. Be it an SQL RDBMS (www.postgresql.org) or an inverted index >library like Berkeley DB (www.sleepycat.com). > >I think using rsync itself verbatim is probably not a good idea considering >it would need to calculate the checksum's and digest (on the server side) >each time a file is considered for backup. > >My view a better option would be to use the delta algorithm but not >the rsync application itself. This way one could keep records of the >checksums and digests for all delta's on the server side without having >to recalculate them each time. There is one caveat that I see here. For rsync to be at its most efficient, it has to generate its checksums and digests from the original file contents. The farther beyond the original version you get, the fewer of those calculated checksums remain applicable in a regularly-changing file. Although you can save the checksums generated during an incremental backup, you can't regenerate the digests from scratch based on the byte boundaries of the file without applying the deltas and then scanning the original file again. How badly this affects the efficiency of your deltas depends entirely on the change rate of the file. There should be a method of "catching up" the most recent deltas from the original and subsequent checksums but since rsync calculates those using rolling and not fixed off-sets, the only effective way I can see of doing that is to rebuild the entire file and rescan. >A popular commercial backup product uses a modified version of >GNU tar for backup and recovery (to tape). I think following a >similar concept (potentially looking at star >http://www.fokus.gmd.de/research/cc/glone/employees/joerg.schilling/private/ >star.html) would be ideal. FYI.... that same vendor is also required to publish the source of their modified version under the GPL. I haven't actually read through their modifications though, but I have wondered which elements of GNU tar's behaviour they saw fit to change. There is no reason why their modified version couldn't be used in another system too :) ftp://ftp.support.veritas.com/pub/support/products/NetBackup_DataCenter/tar-1.09.NBU_232072.tar.Z > > 5. Ability to split the pool across several file systems. Since > > I use hardlinks to efficiently store repeated files, everything > > must currently be on a single file system. New 120GB drives > > are just becoming available, so you could run BackupPC on two > > or three 120GB file systems without worrying about merging the > > physical drives into one big file system. Tools will allow you > > to resplit the pool if you need to add more drives later. > >I agree with Peter's previous comments in that this issue can and >probably should be delt with outside of the application. That is, >some form of Logical Volume Manager. I think a single filesystem approach is nice and simple. The techniques for backing up a filesystem are well-understood and the reference count in each inode gives you an easy way to track the number of times a file is referenced in different backups. With filesystem address-spaces reaching into the terabytes now, and lvm systems able to leverage the incredibly cheap and massive disks on the market today, keeping BackupPC supplied with a large pool of addressable space doesn't seem too difficult :) Regards, --PLB |
From: Peter L. B. <pl...@io...> - 2001-12-31 03:32:44
|
Peter: Hopefully I won't stick my foot in my mouth here (so please bear with me if I do ;-) but my understanding, from section 3.2.3 of Tridgell's PHD Thesis is as follows: 1. The destination file is divided up into fixed-length blocks of size blocksize (32k for example.) 2. For each block, a cheap checksum and an expensive checksum are generated. 3. Starting from the beginning of the source file, and continuing until EOF: - A cheap checksum for a block of length blocksize is calculated at each byte boundary. - If the cheap checksum matches a checksum in the table generated in step 1, the expensive checksum is also calculated. - If the expensive checksum also matches, a token is passed indicating that blocksize bytes from the present offset may be substituted with the remote block for which the two checksums matched. - Calculation of cheap checksums will continue from the present offset + blocksize. - All byte boundaries where no checksums matched will result in the transferring of the actual bytes rather than a block token. The key thing here is that while the blocks are calculated on fixed boundaries in the destination file, for the source file there is no concept of a fixed block boundary. Block boundaries are determined dynamically when both a checksum and a digest for blocksize bytes from a given byte boundary in the source file match one of the fixed blocks in the destination file. Thus, the way rsync itself works, the checksums and digests for fixed blocks in the most recent file cannot be calculated until it is fully reconstructed on the remote end, something that requires applying the deltas that are transferred in the process. However, I think I've been looking at this with a certain amount of tunnel vision because I analyzed the issue from the perspective of rsync's client/server process. If the procedure is changed such that the client begins the backup process by calculating checksums and digests on fixed boundaries, then passing them to the server, the server will have a record of the fixed-block checksums and digests for the most recent version of the file (something it cannot generate itself without reconstructing the file.) However, for these checksums and digests to be useful, they have to match blocks that are stored someplace on the backup server. This is where the process breaks down. The actual blocks that are stored are from the destination files only. Deltas from the source files are applied not in full blocks, but in variable length bytestreams. Thus, a "block" in rsync, always refers to an element of blocksize bytes in the destination file. Unique blocks never originate in the source file, they are derived from the destination file and may only be matched by the same pattern in the destination file. The gaps between blocks in the source file that represent new data will always consist of one or more bytes but are not going to be of any fixed size. The worst case we have here, then is that our catalog of checksums and digests contains a lot of references to blocks that do not physically exist in our datastore. This does not stop us from continuing to perform incremental backups as often as we like since we have the fixed block checksums and digests that the client passed us in the previous backup, but it does present a problem when it comes to restore. Restoring is horrendously in-efficient but also magical in a way ;-) To successfully restore a file to a point in time, you start with the original full, and have no other choice but go through the process of applying the deltas for each and every incremental backup and caching a copy of every fixed block that is referenced by a subsequent backup. Incidentally, this is pretty much identical to the concept of rolling forward a database using the last full backup and its transaction logs. The ugly part is that there is no middle ground between a full backup and an incremental. There is no easy way in this process to create a cumulative, or level backup, consisting of all the deltas since a given non-full backup. Regenerating the blocks from deltas always requires going back to the last full. It is getting late though, so my brain may not have fully thought this through. I've just spent the past 2 hours analyzing this issue and I think I've got it right, but I'll be happy to buy a round of beers if I'm wrong. In any case, Peter Marelas is absolutely correct in that the efficiency of the algorithm for each subsequent incremental can be retained simply by having the client-side generate a list of checksums and digests that will be retained on the server (even though this isn't how rsync normally operates.) Subsequent incrementals will be calculated based on the checksums and digests generated in the previous backup. This addresses the efficiency of the checksum/digest portion of the database. However, because blocks on the client-side are not backed up on fixed block boundaries, the efficiency of the datastore gets worse and worse with each generation. Indeed, the spectre of data integrity arises because the integrity of your most recent backup is also dependent on the integrity of your last full and every intervening incremental. This is usually compensated for in commercial systems by having regular cumulative backups that backup all changes since the previous full, skipping the most recent incrementals. To be viable, an rsync-style backup algorithm is going to need some method of providing rergular checkpoints between the full and the most recent incremental such that performing a restore doesn't require applying the deltas for every generation of the file that has been backed up since the last full. My apologies if I've gotten this wrong. ;-) --PLB <Additional comments in-line below> >The thing is (this is my understanding based on reading >up on the algorithm) the checksum does not roll from >START to EOF. It rolls from START OF BLOCK to >END OF BLOCK. Then its computed for the next >block independant of the previous block and so on. I believe that on the source side, the rolling checksum _does_ occur from START to EOF, skipping chunks of blocksize bytes every time a block matches. Thus, there is no concept of a "next block" on the source side since the processing is done one byte at a time. >So, from a rolling perspective, it can roll for ever, but >is not used in this fashion by rsync. > >In theory it would work like this.. > >1. Server saves all checksums/digests at fixed block size boundaries > for a files most recent version (which is made up of delta's in > itself). >2. Client requests incremental backup of the file >3. Server sends client the checksums/digests previously saved and referenced > for the files most recent version (previously computed from last >incremental/full). >4. Client computes checksums for each byte boundary and compares > against those received from server. If it finds a match it computes > digest and compares again. If they match the given block is > considered 'in sync'. The rolling checksum starts again from the next > block (independant of whats already been traversed). > If the checksum's do not match those received from the server the > client sends server the data blocks, offsets and checksums. > If the checksum's match those received from the server up to > EOF client sends server the data blocks, offsets and checksums. Are you referring to fixed-size or variable-size blocks here? My understanding is that rsync deltas consist of variable-length bytestreams interspersed with references to fixed-length blocks on the remote side. >5. Server updates delta references from first fixed block size boundary that > changed and recomputes/verifies checksums for these > blocks only and saves them for future reference. > It then removes old/unreferenced checksums including the > delta's (removal could be done via scheduled batch job > so that throughput is not affected by index updates, etc). > >So, re-scanning the file on the server side is avoided unless >the file changes which you point out. However, depending >where it changed will depend on how much needs to be >recalled (and it need not be recalled or computed to determine what >the client should compare against). > >Limiting file/delta recall is advantageous from a tape backup >perspective. I'm not sure if I've misunderstood what you've written above or not. The method you describe works as far as the checksums and digests are concerned but seems to break down when it gets to the data blocks themselves. Since no fixed-length blocks are generated by the differencing algorithm, those blocks can't be stored on the server, even though we have a record of their checksums and digests provided by the client. This gives us the peculiar situation of having checksums and digests for the blocks, but not the blocks themselves. Even so, we do have the deltas that allow us to regenerate the blocks by recreating successive versions of the file starting from the last full. >ftp://ftp.support.veritas.com/pub/support/products/NetBackup_DataCenter/tar- >1.09.NBU_232072.tar.Z > >I had a quick look.. > >DES Encryption is one. Interesting.... I wonder why they chose to do it that way? To my mind, encryption, compression, and other transformative tasks belong in the backup chain as filters in the same way that Unix uses pipes to allow post-processing of command output. Hmmm... --PLB >Regards >Peter Marelas |
From: <ma...@ph...> - 2001-12-30 16:10:21
|
----- Original Message ----- From: "Peter L. Buschman" <pl...@io...> To: <ma...@ph...>; "Craig Barratt" <cr...@ar...> Cc: <bac...@li...> Sent: Sunday, December 30, 2001 7:45 AM Subject: Re: [BackupPC-users] Reducing Network Requirements > >I think its important to move to a custom client to be able to > >extend the softwares feature set. I do backup and recovery > >for a living and the most frequent problem I see is slow networks. > > Some issues worth considering on the custom-client route: > > 1. Create an open command/response protocol specified in the style of the > RFCs. This leaves open the > possibility of letting others develop unique clients that will plug > seamlessly into the system as long as > they implement the protocol properly. I can use a POP3/SMTP > compatible mailer with any POP3/SMTP > server regardless of whether they are from the save vendor or > not. That is something I wish I could do with > backup software (I too work with large network backup systems > professionally, and the lock-in that the big > vendors like Veritas and Legato force on their customers is > draconian.) I would love to see a situation where > standardized protocols exist between the client-side and server-side > in network backup systems (and I consider > NDMP to be far too low-level for this purpose.) Agreed. > >Dont know if your aware, there is a similar commericial > >product that does what BackupPC does but alot more. > >Its called Veritas Netbackup Proffesional. > >Have a look at > >http://www.veritas.com/products/category/ProductDetail.jhtml?productId=nbup r > >o > >you may get some ideas. > > NetBackup Professional shares s a lot of similarities in the basic design > with BackupPC. Although NBU Pro (which is a completely > different product from NBU BusinessServer or DataCenter editions) has a > native-client architecture, it too relies on an on-disk datastore > and has no integration with tape libraries. Backup of the datastore is > left to the system administrator and some other software package. > > Legato has a Networker Laptop edition that also has similar features. A > centralized on-disk datastore that elilminates redundant files seems > to have become the industry norm for pitching "laptop" oriented backup > solutions. For some reason, though, these solutions have typically > been implemented as point-products rather than being fully integrated with > the vendor's enterprise tape backup solutions. As a backup > administrator, I hate the idea of having to manage yet another backup > package with a completely different set of commands and control > interfaces, especially when it comes from the same vendor as one of my > other solutions. > > I think BackupPC is a great step in the right direction towards filling a > gap between the capabilities of open source backup applications and > the commercial applications presently available. If we put our heads > together, I'm sure we can bring it up to a par with the vendor offerings > already on the table. > > >One option is to maintain logical references (pointers) to delta's. > >The pointers a file points to make up the file itself. > >The pointers and file attributes would be maintained in some form of > >a database. Be it an SQL RDBMS (www.postgresql.org) or an inverted index > >library like Berkeley DB (www.sleepycat.com). > > > >I think using rsync itself verbatim is probably not a good idea considering > >it would need to calculate the checksum's and digest (on the server side) > >each time a file is considered for backup. > > > >My view a better option would be to use the delta algorithm but not > >the rsync application itself. This way one could keep records of the > >checksums and digests for all delta's on the server side without having > >to recalculate them each time. > > There is one caveat that I see here. For rsync to be at its most > efficient, it has to generate its checksums > and digests from the original file contents. The farther beyond the > original version you get, the fewer of those > calculated checksums remain applicable in a regularly-changing > file. Although you can save the checksums > generated during an incremental backup, you can't regenerate the digests > from scratch based on the byte boundaries > of the file without applying the deltas and then scanning the original file > again. How badly this affects the efficiency > of your deltas depends entirely on the change rate of the file. There > should be a method of "catching up" the most > recent deltas from the original and subsequent checksums but since rsync > calculates those using rolling and not > fixed off-sets, the only effective way I can see of doing that is to > rebuild the entire file and rescan. The thing is (this is my understanding based on reading up on the algorithm) the checksum does not roll from START to EOF. It rolls from START OF BLOCK to END OF BLOCK. Then its computed for the next block independant of the previous block and so on. So, from a rolling perspective, it can roll for ever, but is not used in this fashion by rsync. In theory it would work like this.. 1. Server saves all checksums/digests at fixed block size boundaries for a files most recent version (which is made up of delta's in itself). 2. Client requests incremental backup of the file 3. Server sends client the checksums/digests previously saved and referenced for the files most recent version (previously computed from last incremental/full). 4. Client computes checksums for each byte boundary and compares against those received from server. If it finds a match it computes digest and compares again. If they match the given block is considered 'in sync'. The rolling checksum starts again from the next block (independant of whats already been traversed). If the checksum's do not match those received from the server the client sends server the data blocks, offsets and checksums. If the checksum's match those received from the server up to EOF client sends server the data blocks, offsets and checksums. 5. Server updates delta references from first fixed block size boundary that changed and recomputes/verifies checksums for these blocks only and saves them for future reference. It then removes old/unreferenced checksums including the delta's (removal could be done via scheduled batch job so that throughput is not affected by index updates, etc). So, re-scanning the file on the server side is avoided unless the file changes which you point out. However, depending where it changed will depend on how much needs to be recalled (and it need not be recalled or computed to determine what the client should compare against). Limiting file/delta recall is advantageous from a tape backup perspective. > >A popular commercial backup product uses a modified version of > >GNU tar for backup and recovery (to tape). I think following a > >similar concept (potentially looking at star > >http://www.fokus.gmd.de/research/cc/glone/employees/joerg.schilling/private / > >star.html) would be ideal. > > FYI.... that same vendor is also required to publish the source of their > modified version under the GPL. I haven't > actually read through their modifications though, but I have wondered which > elements of GNU tar's behaviour they > saw fit to change. There is no reason why their modified version couldn't > be used in another system too :) > > ftp://ftp.support.veritas.com/pub/support/products/NetBackup_DataCenter/tar- 1.09.NBU_232072.tar.Z I had a quick look.. DES Encryption is one. Regards Peter Marelas |
From: <ma...@ph...> - 2002-01-03 02:02:50
|
Hi Peter, Happy new years.. Rather than trying to explain (im doing a poor job of it) I'll make some points and get back to writing the proof of concept. Hopefully then it will all fall in place. Thus far i've converted the rsync crc to perl and testing the application of delta's. The points I want to make are as follows: 1. Read page 96 or so of andrew's thesis. It clearly states what were attempting is possible. Of particular importance is he mentions that the checksum's and digests can be stored on tape. That means, they remain persistent so long as the source does not change. 2. The backup strategy employed by the delta mechanism I talk of will result in incremental backups. Cumulative backups dont make much sense to me for a disk cache. However, in some ways they can be considered cumulative if old file versions are not expired. 3. There is no concept of a full backup (i.e. whole file). A full is treated the same way as an incremental. It's broken up into fixed block sizes, sumed and stored as a bunch of independant deltas. 4. To restore a particular file version, the delta's referenced by the file pointer will be recalled in index order to reconstruct the file in full. That is, we are not using the rsync algorithm to restore (i.e. the inverse of backup). 5. To perform an incremental backup only the last/latest file version's previously backed up will be used in accordance with the rsync algorithm. The checksum's/digests associated with the delta's that are referenced by this file version will be sent to the source (client). This will follow the same concept of comparing the file timestamp since the last backup. Regards Peter Marelas ----- Original Message ----- From: "Peter L. Buschman" <pl...@io...> To: <ma...@ph...>; "Craig Barratt" <cr...@ar...>; "Peter L. Buschman" <pl...@io...> Cc: <bac...@li...> Sent: Monday, December 31, 2001 2:32 PM Subject: Re: [BackupPC-users] Reducing Network Requirements > > Peter: > > Hopefully I won't stick my foot in my mouth here (so please bear with me if > I do ;-) > but my understanding, from section 3.2.3 of Tridgell's PHD Thesis is as > follows: > > 1. The destination file is divided up into fixed-length blocks of size > blocksize (32k for example.) > 2. For each block, a cheap checksum and an expensive checksum are generated. > 3. Starting from the beginning of the source file, and continuing until EOF: > - A cheap checksum for a block of length blocksize is calculated at > each byte boundary. > - If the cheap checksum matches a checksum in the table generated in > step 1, the expensive checksum is also calculated. > - If the expensive checksum also matches, a token is passed indicating > that blocksize bytes from the present offset may be > substituted with the remote block for which the two checksums matched. > - Calculation of cheap checksums will continue from the present offset > + blocksize. > - All byte boundaries where no checksums matched will result in the > transferring of the actual bytes rather than a block token. > > The key thing here is that while the blocks are calculated on fixed > boundaries in the destination file, for the source file there is > no concept of a fixed block boundary. Block boundaries are determined > dynamically when both a checksum and a digest for > blocksize bytes from a given byte boundary in the source file match one of > the fixed blocks in the destination file. > > Thus, the way rsync itself works, the checksums and digests for fixed > blocks in the most recent file cannot be calculated until > it is fully reconstructed on the remote end, something that requires > applying the deltas that are transferred in the process. > > However, I think I've been looking at this with a certain amount of tunnel > vision because I analyzed the issue from the perspective > of rsync's client/server process. > > If the procedure is changed such that the client begins the backup process > by calculating checksums and digests on fixed boundaries, > then passing them to the server, the server will have a record of the > fixed-block checksums and digests for the most recent version of > the file (something it cannot generate itself without reconstructing the > file.) However, for these checksums and digests to be useful, they > have to match blocks that are stored someplace on the backup server. This > is where the process breaks down. The actual blocks that > are stored are from the destination files only. Deltas from the source > files are applied not in full blocks, but in variable length bytestreams. > Thus, a "block" in rsync, always refers to an element of blocksize bytes in > the destination file. Unique blocks never originate in the source > file, they are derived from the destination file and may only be matched by > the same pattern in the destination file. The gaps between blocks > in the source file that represent new data will always consist of one or > more bytes but are not going to be of any fixed size. > > The worst case we have here, then is that our catalog of checksums and > digests contains a lot of references to blocks that do not physically > exist in our datastore. This does not stop us from continuing to perform > incremental backups as often as we like since we have the > fixed block checksums and digests that the client passed us in the previous > backup, but it does present a problem when it comes to restore. > > Restoring is horrendously in-efficient but also magical in a way ;-) > > To successfully restore a file to a point in time, you start with the > original full, and have no other choice but go through the process of applying > the deltas for each and every incremental backup and caching a copy of > every fixed block that is referenced by a subsequent backup. > > Incidentally, this is pretty much identical to the concept of rolling > forward a database using the last full backup and its transaction logs. > > The ugly part is that there is no middle ground between a full backup and > an incremental. There is no easy way in this process to create > a cumulative, or level backup, consisting of all the deltas since a given > non-full backup. Regenerating the blocks from deltas always requires > going back to the last full. > > It is getting late though, so my brain may not have fully thought this > through. I've just spent the past 2 hours analyzing this issue and I > think I've got it right, but I'll be happy to buy a round of beers if I'm > wrong. > > In any case, Peter Marelas is absolutely correct in that the efficiency of > the algorithm for each subsequent incremental can be retained > simply by having the client-side generate a list of checksums and digests > that will be retained on the server (even though this isn't how > rsync normally operates.) Subsequent incrementals will be calculated based > on the checksums and digests generated in the previous > backup. This addresses the efficiency of the checksum/digest portion of > the database. However, because blocks on the client-side are > not backed up on fixed block boundaries, the efficiency of the datastore > gets worse and worse with each generation. Indeed, the spectre > of data integrity arises because the integrity of your most recent backup > is also dependent on the integrity of your last full and every > intervening incremental. This is usually compensated for in commercial > systems by having regular cumulative backups that backup > all changes since the previous full, skipping the most recent > incrementals. To be viable, an rsync-style backup algorithm is going to > need some method of providing rergular checkpoints between the full and the > most recent incremental such that performing a restore > doesn't require applying the deltas for every generation of the file that > has been backed up since the last full. > > My apologies if I've gotten this wrong. ;-) > > --PLB > > <Additional comments in-line below> > > >The thing is (this is my understanding based on reading > >up on the algorithm) the checksum does not roll from > >START to EOF. It rolls from START OF BLOCK to > >END OF BLOCK. Then its computed for the next > >block independant of the previous block and so on. > > I believe that on the source side, the rolling checksum _does_ occur from > START to EOF, > skipping chunks of blocksize bytes every time a block matches. Thus, there > is no concept > of a "next block" on the source side since the processing is done one byte > at a time. > > >So, from a rolling perspective, it can roll for ever, but > >is not used in this fashion by rsync. > > > >In theory it would work like this.. > > > >1. Server saves all checksums/digests at fixed block size boundaries > > for a files most recent version (which is made up of delta's in > > itself). > >2. Client requests incremental backup of the file > >3. Server sends client the checksums/digests previously saved and referenced > > for the files most recent version (previously computed from last > >incremental/full). > >4. Client computes checksums for each byte boundary and compares > > against those received from server. If it finds a match it computes > > digest and compares again. If they match the given block is > > considered 'in sync'. The rolling checksum starts again from the next > > block (independant of whats already been traversed). > > If the checksum's do not match those received from the server the > > client sends server the data blocks, offsets and checksums. > > If the checksum's match those received from the server up to > > EOF client sends server the data blocks, offsets and checksums. > > Are you referring to fixed-size or variable-size blocks here? My > understanding is that > rsync deltas consist of variable-length bytestreams interspersed with > references to fixed-length > blocks on the remote side. > > >5. Server updates delta references from first fixed block size boundary that > > changed and recomputes/verifies checksums for these > > blocks only and saves them for future reference. > > It then removes old/unreferenced checksums including the > > delta's (removal could be done via scheduled batch job > > so that throughput is not affected by index updates, etc). > > > >So, re-scanning the file on the server side is avoided unless > >the file changes which you point out. However, depending > >where it changed will depend on how much needs to be > >recalled (and it need not be recalled or computed to determine what > >the client should compare against). > > > >Limiting file/delta recall is advantageous from a tape backup > >perspective. > > I'm not sure if I've misunderstood what you've written above or not. The > method you > describe works as far as the checksums and digests are concerned but seems > to break > down when it gets to the data blocks themselves. Since no fixed-length > blocks are generated > by the differencing algorithm, those blocks can't be stored on the server, > even though we have > a record of their checksums and digests provided by the client. > > This gives us the peculiar situation of having checksums and digests for > the blocks, but not the > blocks themselves. Even so, we do have the deltas that allow us to > regenerate the blocks by > recreating successive versions of the file starting from the last full. > > >ftp://ftp.support.veritas.com/pub/support/products/NetBackup_DataCenter/tar - > >1.09.NBU_232072.tar.Z > > > >I had a quick look.. > > > >DES Encryption is one. > > Interesting.... I wonder why they chose to do it that way? To my mind, > encryption, compression, and other transformative > tasks belong in the backup chain as filters in the same way that Unix uses > pipes to allow post-processing of command output. > > Hmmm... > > --PLB > > > >Regards > >Peter Marelas > > > _______________________________________________ > BackupPC-users mailing list > Bac...@li... > https://lists.sourceforge.net/lists/listinfo/backuppc-users > |