efficiently store only the changes to that tarball from one day to the next.
For small files, bup's compression won't be as good as xdelta's, but for
anything over a few megabytes in size, bup's compression will actually
-*work*, which is a bit advantage over xdelta.
+*work*, which is a big advantage over xdelta.
How does hashsplitting work? It's deceptively simple. We read through the
-file one byte at a time, calculating a rolling checksum of the last 128
-bytes. (Why 128? No reason. Literally. We picked it out of the air.
+file one byte at a time, calculating a rolling checksum of the last 64
+bytes. (Why 64? No reason. Literally. We picked it out of the air.
Probably some other number is better. Feel free to join the mailing list
and tell us which one and why.) (The rolling checksum idea is actually
stolen from rsync and xdelta, although we use it differently. And they use
Save us! ... oh boy, I sure hope he doesn't read this)
In any case, rollsum seems to do pretty well at its job.
-You can find it in bupsplit.c. Basically, it converts the last 128 bytes
+You can find it in bupsplit.c. Basically, it converts the last 64 bytes
read into a 32-bit integer. What we then do is take the lowest 13
bits of the rollsum, and if they're all 1's, we consider that to be the end
of a chunk. This happens on average once every 2^13 = 8192 bytes, so the
the same. All that matters to the hashsplitting algorithm is the 32-byte
"separator" sequence, and a single change can only affect, at most, one
separator sequence or the bytes between two separator sequences. And
-because of rollsum, about one in 8192 possible 128-byte sequences is a
+because of rollsum, about one in 8192 possible 64-byte sequences is a
separator sequence. Like magic, the hashsplit chunking algorithm will chunk
your file the same way every time, even without knowing how it had chunked
it previously.
Imagine you had a midx file for your 200 packs. midx files are a lot like
idx files; they have a lookup table at the beginning that narrows down the
-initial search, followed by a binary search. The unlike idx files (which
+initial search, followed by a binary search. Then unlike idx files (which
have a fixed-size 256-entry lookup table) midx tables have a variably-sized
table that makes sure the entire binary search can be contained to a single
page of the midx file. Basically, the lookup table tells you which page to
containing the metadata for the corresponding path. Each record
records one type of metadata. Current types include a common record
type (containing the normal stat information), a symlink target type,
-a POSIX1e ACL type, etc. See metadata.py for the complete list.
+a hardlink target type, a POSIX1e ACL type, etc. See metadata.py for
+the complete list.
The .bupm file is optional, and when it's missing, bup will behave as
it did before the addition of metadata, and restore files using the
tree information.
The nice thing about this design is that you can walk through each
-file in a tree just by opening the tree and the .bupmeta contents, and
+file in a tree just by opening the tree and the .bupm contents, and
iterating through both at the same time.
+Since the contents of any .bupm file should match the state of the
+filesystem when it was *indexed*, bup must record the detailed
+metadata in the index. To do this, bup records four values in the
+index, the atime, mtime, and ctime (as timespecs), and an integer
+offset into a secondary "metadata store" which has the same name as
+the index, but with ".meta" appended. This secondary store contains
+the encoded Metadata object corresponding to each path in the index.
+
+Currently, in order to decrease the storage required for the metadata
+store, bup only writes unique values there, reusing offsets when
+appropriate across the index. The effectiveness of this approach
+relies on the expectation that there will be many duplicate metadata
+records. Storing the full timestamps in the index is intended to make
+that more likely, because it makes it unnecessary to record those
+values in the secondary store. So bup clears them before encoding the
+Metadata objects destined for the index, and timestamp differences
+don't contribute to the uniqueness of the metadata.
+
+Bup supports recording and restoring hardlinks, and it does so by
+tracking sets of paths that correspond to the same dev/inode pair when
+indexing. This information is stored in an optional file with the
+same name as the index, but ending with ".hlink".
+
+If there are multiple index runs, and the hardlinks change, bup will
+notice this (within whatever subtree it is asked to reindex) and
+update the .hlink information accordingly.
+
+The current hardlink implementation will refuse to link to any file
+that resides outside the restore tree, and if the restore tree spans a
+different set of filesystems than the save tree, complete sets of
+hardlinks may not be restored.
+
Filesystem Interaction
======================
projects / bup.git / blobdiff