Changeset 134

Timestamp:

05/23/07 01:24:54 (3 years ago)

Author:

bradfitz

Message:

support for merging little files together into big chunks
on the backup target. aka "tail packing". requires no changes
to target drivers. this should speed backups, as less network
round-trips. will also be cheaper, once Amazon starts charging
per number of HTTP requests in June.

Location:

trunk

Files:

• Changes (modified) (1 diff)
• MANIFEST (modified) (3 diffs)
• lib/Brackup/Backup.pm (modified) (8 diffs)
• lib/Brackup/CompositeChunk.pm (added)
• lib/Brackup/InventoryDatabase.pm (modified) (1 diff)
• lib/Brackup/Restore.pm (modified) (1 diff)
• lib/Brackup/Root.pm (modified) (3 diffs)
• lib/Brackup/StoredChunk.pm (modified) (5 diffs)
• lib/Brackup/Target.pm (modified) (2 diffs)
• lib/Brackup/Target/Amazon.pm (modified) (1 diff)
• lib/Brackup/Target/Filesystem.pm (modified) (1 diff)
• lib/Brackup/Test.pm (modified) (1 diff)
• t/03-combine-little-files.t (added)
• t/data/000-dup1.txt (added)
• t/data/000-dup2.txt (added)

trunk/Changes

@@ +1 @@
+  - support for merging little files together into big chunks
+    on the backup target.  aka "tail packing".  requires no changes
+    to target drivers.  this should speed backups, as less network
+    round-trips.  will also be cheaper, once Amazon starts charging
+    per number of HTTP requests in June.
+
+  - improved docs
+
 1.01 (may 21, 2007)
 

trunk/MANIFEST

@@ -13 +13 @@
 lib/Brackup/BackupStats.pm
 lib/Brackup/ChunkIterator.pm
+lib/Brackup/CompositeChunk.pm
 lib/Brackup/Config.pm
 lib/Brackup/ConfigSection.pm
@@ -33 +34 @@
 MANIFEST                        This list of files
 MANIFEST.SKIP
+META.yml                        Module meta-data (added by MakeMaker)
 t/00-use.t
 t/01-backup.t
 t/02-gpg.t
+t/03-combine-little-files.t
+t/data/000-dup1.txt
+t/data/000-dup2.txt
 t/data/huge-file.txt
 t/data/my-link.txt
@@ -44 +49 @@
 t/data/test-file.txt
 TODO
-META.yml                                 Module meta-data (added by MakeMaker)

trunk/lib/Brackup/Backup.pm

@@ -4 +4 @@
 use Carp qw(croak);
 use Brackup::ChunkIterator;
+use Brackup::CompositeChunk;
 use Brackup::GPGProcManager;
 use Brackup::GPGProcess;
@@ -125 +126 @@
     };
 
+    my $merge_under = $root->merge_files_under;
+    my $comp_chunk  = undef;
+    
     # records are either Brackup::File (for symlinks, directories, etc), or
     # PositionedChunks, in which case the file can asked of the chunk
@@ -137 +141 @@
         }
 
+        # have we already stored this chunk before?  (iterative backup)
         my $schunk;
         if ($schunk = $target->stored_chunk_from_inventory($pchunk)) {
@@ -144 +149 @@
         }
 
+        # weird case... have we stored this same pchunk digest in the
+        # current comp_chunk we're building?  these aren't caught by
+        # the above inventory check, because chunks in a composite
+        # chunk aren't added to the inventory until after the the composite
+        # chunk has fully grown (because it's not until it's fully grown
+        # that we know the handle for it, its digest)
+        if ($comp_chunk && ($schunk = $comp_chunk->stored_chunk_from_dup_internal_raw($pchunk))) {
+            $pchunk->forget_chunkref;
+            push @stored_chunks, $schunk;
+            next;
+        }
+
         $show_status->() unless $file_has_shown_status++;
         $self->debug("  * storing chunk: ", $pchunk->as_string, "\n");
 
-        my $handle;
         unless ($self->{dryrun}) {
             $schunk = Brackup::StoredChunk->new($pchunk);
@@ -154 +170 @@
             if ($gpg_rcpt) {
                 $schunk->set_encrypted_chunkref($gpg_pm->enc_chunkref_of($pchunk));
+            }
+
+            # see if we should pack it into a bigger blob
+            my $chunk_size = $schunk->backup_length;
+            if ($merge_under && $chunk_size < $merge_under) {
+                if ($comp_chunk && ! $comp_chunk->can_fit($chunk_size)) {
+                    $self->debug("Finalizing composite chunk $comp_chunk...");
+                    $comp_chunk->finalize;
+                    $comp_chunk = undef;
+                }
+                $comp_chunk ||= Brackup::CompositeChunk->new($root, $target);
+                $comp_chunk->append_little_chunk($schunk);
+            } else {
+                # store it regularly, as its own chunk on the target
+                $target->store_chunk($schunk)
+                    or die "Chunk storage failed.\n";
+                $target->add_to_inventory($pchunk => $schunk);
             }
 
@@ -163 +196 @@
             #};
 
-            $target->store_chunk($schunk)
-                or die "Chunk storage failed.\n";
-            $target->add_to_inventory($pchunk => $schunk);
+
             $n_kb_up += $pchunk->length / 1024;
             push @stored_chunks, $schunk;
@@ -173 +204 @@
 
         # DEBUG: verify it got written correctly
-        if ($ENV{BRACKUP_PARANOID} && $handle) {
+        if ($ENV{BRACKUP_PARANOID}) {
             die "FIX UP TO NEW API";
             #my $saved_ref = $target->load_chunk($handle);
@@ -187 +218 @@
     }
     $end_file->();
+    $comp_chunk->finalize if $comp_chunk;
 
     unless ($self->{dryrun}) {

trunk/lib/Brackup/InventoryDatabase.pm

@@ -119 +119 @@
 B<Keys>
 
-The key is the digest of the "raw" (pre-compression/encryption) file/chunk, and the value is
-the digest of the file/chunk post-compression/encryption, along with its length.
+The key is the digest of the "raw" (pre-compression/encryption)
+file/chunk (with GPG recipient, if using encryption), and the value is
+the digest of the chunk stored on the target, which contains the raw
+chunk.  The chunk stored on the target may contain other chunks, may
+be compressed, encrypted, etc.
+
+ <raw_digest>               --> <stored_digest> <stored_length>
+ <raw_digest>;to=<gpg_rcpt> --> <stored_digest> <stored_length>
 
 For example:
 
-  sha1:e23c4b5f685e046e7cc50e30e378ab11391e528e =>
+  sha1:e23c4b5f685e046e7cc50e30e378ab11391e528e;to=6BAFF35F =>
      sha1:d7257184899c9e6c4e26506f1c46f8b6562d9ee7 71223
 
-Means that the chunk with sha1 contents "e23c4...", after being
-compressed/encrypted, is stored on the target with digest
-"d72571848...", with length 71,223 bytes.
+Means that the chunk with sha1 contents "e23c4...", intended to be
+en/de-crypted for 6BAFF35F, can be got by asking the target for the
+chunk with digest "d72571848...", with length 71,223 bytes.
+
+When using the Brackup feature which combines small files into larger
+blobs, the inventory database instead stores values like:
+
+  <raw_digest>[;to=<gpg_rcpt>] -->
+     <stored_digest> <stored_length> <from_offset>-<to_offset>
+
+Which is the same thing, but after fetching the composite chunk using
+the stored digest provided, only the range provided from C<from_offset> to 
+C<to_offset> should be used.
 
 =head1 SEE ALSO

trunk/lib/Brackup/Restore.pm

@@ -188 +188 @@
 
         my $len_chunk = length $$dataref;
-        unless ($len_chunk == $enc_len) {
-            die "Backup chunk $dig isn't of expected length: got $len_chunk, expecting $enc_len\n";
+
+        # using just a range of the file
+        # TODO: inefficient!  we don't want to download the chunk from the
+        # target multiple times.  better to cache it locally, or at least
+        # only fetch a region from the target (but that's still kinda inefficient
+        # and pushes complexity into the Target interface)
+        if ($enc_len =~ /^(\d+)-(\d+)$/) {
+            my ($from, $to) = ($1, $2);
+            # file range.  gotta be at least as big as bigger number
+            unless ($len_chunk >= $to) {
+                die "Backup chunk $dig isn't at least as big as range: got $len_chunk, needing $to\n";
+            }
+            my $region = substr($$dataref, $from, $to-$from);
+            $dataref = \$region;
+        } else {
+            # using the whole chunk, so make sure fetched size matches
+            # expected size
+            unless ($len_chunk == $enc_len) {
+                die "Backup chunk $dig isn't of expected length: got $len_chunk, expecting $enc_len\n";
+            }
         }
 

trunk/lib/Brackup/Root.pm

@@ -20 +20 @@
     $self->{gpg_path}   = $conf->value('gpg_path') || "/usr/bin/gpg";
     $self->{gpg_rcpt}   = $conf->value('gpg_recipient');
-    $self->{chunk_size} = $conf->byte_value('chunk_size'),
+    $self->{chunk_size} = $conf->byte_value('chunk_size');
     $self->{ignore}     = [];
+
+    $self->{merge_files_under}  = $conf->byte_value('merge_files_under');
+    $self->{max_composite_size} = $conf->byte_value('max_composite_chunk_size') || 2**20;
+
+    die "'max_composite_chunk_size' must be greater than 'merge_files_under'\n" unless
+        $self->{max_composite_size} > $self->{merge_files_under};
 
     $self->{gpg_args}   = [];  # TODO: let user set this.  for now, not possible
@@ -31 +37 @@
     return $self;
 }
+
+sub merge_files_under  { $_[0]{merge_files_under}  }
+sub max_composite_size { $_[0]{max_composite_size} }
 
 sub gpg_path {
@@ -279 +288 @@
 just make the *.brackup metafiles larger.
 
+=item B<merge_files_under>
+
+In units of bytes, kB, MB, etc.  If files are under this size.  By
+default this feature is off (value 0), purely because it's new, but 1
+kB is a recommended size, and will probably be the default in the
+future.  Set it to 0 to explicitly disable.
+
+=item B<max_composite_chunk_size>
+
+In units of bytes, kB, MB, etc.  The maximum size of a composite
+chunk, holding lots of little files.  If this is too big, you'll waste
+more space with future iterative backups updating files locked into
+this chunk with unchanged chunks.
+
+Recommended, and default value, is 1 MB.
+
 =back

trunk/lib/Brackup/StoredChunk.pm

@@ -11 +11 @@
 #   backdigest - memoized
 #   _chunkref  - memoized
+#   compchunk  - composite chunk, if we were added to a composite chunk
+#   compfrom   - offset in composite chunk where we start
+#   compto     - offset in composite chunk where we end
 
 sub new {
@@ -19 +22 @@
 }
 
+sub pchunk { $_[0]{pchunk} }
+
 # create the 'lite' or 'handle' version of a storedchunk.  can't get to
 # the chunkref from this, but callers aren't won't.  and we'll DIE if they
 # try to access the chunkref.
-sub new_from_inventory {
-    my ($class, $pchunk, $dig, $len) = @_;
-    return bless {
+sub new_from_inventory_value {
+    my ($class, $pchunk, $invval) = @_;
+
+    my ($dig, $len, $range) = split /\s+/, $invval;
+    
+    my $sc = bless {
         pchunk     => $pchunk,
         backdigest => $dig,
         backlength => $len,
     }, $class;
+
+    # normal
+    return $sc unless $range;
+
+    # in case of little file in a composite chunk,
+    # we gotta be a range.
+    my ($from, $to) = $range =~ /^(\d+)-(\d+)$/
+        or die "bogus range: $range";
+    $sc->{compfrom} = $from;
+    $sc->{compto}   = $to;
+    return $sc;
+}
+
+sub clone_but_for_pchunk {
+    my ($self, $pchunk) = @_;
+    my $copy = bless {}, ref $self;
+    foreach my $f (qw(backlength backdigest compchunk compfrom compto)) {
+        $copy->{$f} = $self->{$f};
+    }
+    $copy->{pchunk} = $pchunk;
+    return $copy;
+}
+
+sub set_composite_chunk {
+    my ($self, $cchunk, $from, $to) = @_;
+    $self->{compchunk} = $cchunk;
+
+    # forget our backup length/digest.  this handle information
+    # to the stored chunk should be asked of our composite
+    # chunk in the future, when it's done populating.
+    $self->{backdigest} = undef;
+    $self->{backlength} = undef;
+    $self->forget_chunkref;
+
+    $self->{compfrom}  = $from;
+    $self->{compto}    = $to;
+}
+
+sub range_in_composite {
+    my $self = shift;
+    return undef unless $self->{compfrom} || $self->{compto};
+    return "$self->{compfrom}-$self->{compto}";
 }
 
@@ -78 +128 @@
 sub _populate_lengthdigest {
     my $self = shift;
+    if (my $cchunk = $self->{compchunk}) {
+        $self->{backlength} = $cchunk->backup_length;
+        $self->{backdigest} = $cchunk->digest;
+        return 1;
+    }
+
     my $dataref = $self->chunkref;
     $self->{backlength} = CORE::length($$dataref);
@@ -121 +177 @@
     my $self = shift;
     my @parts = ($self->{pchunk}->offset,
-                 $self->{pchunk}->length,
-                 $self->backup_length,
-                 $self->backup_digest,
-                 );
+                 $self->{pchunk}->length);
+
+    if (my $range = $self->range_in_composite) {
+        push @parts, (
+                      $range,
+                      $self->backup_digest,
+                      );
+    } else {
+        push @parts, (
+                      $self->backup_length,
+                      $self->backup_digest,
+                      );
+    }
 
     # if the inventory database is lost, it should be possible to
@@ -142 +207 @@
 }
 
+# aka "instructions to attach to a pchunk, on how to recover the pchunk from a target"
+sub inventory_value {
+    my $self = shift;
+
+    # when this chunk was stored as part of a composite chunk, the instructions
+    # are of form:
+    #    sha1:deadbeef 0-50
+    # which means download "sha1:deadbeef", then the contents will be in from
+    # byte offset 0 to byte offset 50 (length of 50).
+    if (my $range = $self->range_in_composite) {
+        return join(" ",
+                    $self->backup_digest,
+                    $self->backup_length,
+                    $range);
+    }
+
+    # else, the historical format:
+    #   sha1:deadbeef <length>
+    return join(" ", $self->backup_digest, $self->backup_length);
+}
+
 1;

trunk/lib/Brackup/Target.pm

@@ -46 +46 @@
     my $key  = $pchunk->inventory_key;
     my $db = $self->inventory_db;
-    $db->set($key => join(" ", $schunk->backup_digest, $schunk->backup_length));
+    $db->set($key => $schunk->inventory_value);
 }
 
@@ -55 +55 @@
     my $key    = $pchunk->inventory_key;
     my $db     = $self->inventory_db;
-    my $diglen = $db->get($key)
+    my $invval = $db->get($key)
         or return undef;
-    my ($digest, $length) = split /\s+/, $diglen;
-    return Brackup::StoredChunk->new_from_inventory($pchunk, $digest, $length);
+    return Brackup::StoredChunk->new_from_inventory_value($pchunk, $invval);
 }
 

trunk/lib/Brackup/Target/Amazon.pm

@@ -99 +99 @@
     my $dig = $chunk->backup_digest;
     my $blen = $chunk->backup_length;
-    my $len = $chunk->length;
     my $chunkref = $chunk->chunkref;
 

trunk/lib/Brackup/Target/Filesystem.pm

@@ -74 +74 @@
     my $dig = $chunk->backup_digest;
     my $blen = $chunk->backup_length;
-    my $len = $chunk->length;
 
     my $path = $self->chunkpath($dig);

trunk/lib/Brackup/Test.pm

@@ -75 +75 @@
     }
     ok(-s $meta_filename, "backup file has size");
-    return $meta_filename;
+    return wantarray ? ($meta_filename, $backup) : $meta_filename;
 }