rsync - Jan 2005 - PROPOSAL: --link-hash-dest, additional linking of files to their HASH values

I'm using a few utilities to accomplish the same thing in a second pass
after rsync runs.  The utils all use a two-layer hash (256 directories of
256 subdirectories), which with our current backups puts a little over 100
files per directory.  Anywhere from hundreds of thousands to tens of
millions of files shouldn't waste too many inodes or put a gross number of
files into each directory.  The code to generate the hash directory name is
parameterized though, and could easily generate 1-4 layers.

static char hex_char[16] = "0123456789abcdef";

int prefixdirs = 2;
...

  int digestlength;
digestlength = MD4_DIGEST_LENGTH;

...
const char *hashdir

...
  hashdirlen = strlen(hashdir);
  hashpath = malloc(hashdirlen+digestlength*3+1);
  strcpy(hashpath,hashdir);
  hashpath[hashdirlen]='/';

  for (i=0;i<prefixdirs;i++) {
    hashpath[hashdirlen+i*3+1] = hex_char[md[i] >> 4];
    hashpath[hashdirlen+i*3+2] = hex_char[md[i] & 0xf];
    hashpath[hashdirlen+i*3+3] = '/';
  }
  for (i=prefixdirs;i<digestlength;i++) {
    hashpath[hashdirlen+i*2+prefixdirs+1] = hex_char[md[i] >> 4];
    hashpath[hashdirlen+i*2+prefixdirs+2] = hex_char[md[i] & 0xf];
  }
  hashpath[hashdirlen+prefixdirs+digestlength*2+1] = '\0';

 ...



   The three utilities (hashimplode, hashdelete, hashpurge) are at
http://www.cmb.usc.edu/people/dld/backuputils/.  hashimplode calculates the
hashes and hardlinks files.  hashdelete removes a snapshot, removing
orphaned hash files as it goes, and hashpurge is roughly "find /hashdir
-nlinks 1 | xargs rm", in case you haven't always used hasdelete.  All
three
use rename() to avoid races on files so they can be interleaved and run in
parallel while sharing the same hash directory (which we're doing to utilize
the parallel seek capacity of RAIDs and to back up multiple smaller
fileservers at once).  hashimplode has an option to skip files that are
already hardlinked (basically the ones rsync already hardlinked to the
previous backup - assumes users aren't hardlinking their own files).

   Using this patch would save a pass through the inodes and be a big win
(30-50% faster?  Almost the same as upgrading to 10K RPM disks, keeping the
250G+ size of 7200s) The utilities may prove useful migrating existing
backups to this hash structure, recovering lost hash directories, and
pruning the hash directory.  I'd like to make these utilities use the same
hash structure and race-avoidance an rsync hashdir-patch uses.

-Drake <diedrich@usc.edu>

On Wed, Jan 19, 2005 at 02:45:22PM -0800, Drake Diedrich
wrote:
> I'd like to make these utilities use the same hash structure and
> race-avoidance an rsync hashdir-patch uses.
That patch still needs work as it doesn't do a proper job of maintaining
differing file attributes for files with otherwise identical content.
Some folks have expressed an interest in improving it, but I haven't
seen anything yet.  There's also a backup project called BackupPC that
maintains its own database of attributes for hard-linked files (and even
allows compression).  There's a link to the project on the resources
page of the web site (or just google for it).

..wayne..