]> arthur.barton.de Git - bup.git/blobdiff - DESIGN
Extend README for NetBSD.
[bup.git] / DESIGN
diff --git a/DESIGN b/DESIGN
index 00a56e4647338d16db34c3e9f5ddc2b12fd264d4..dfe30f36062ffbf8cc2fb623792ef1b87271cf8a 100644 (file)
--- a/DESIGN
+++ b/DESIGN
@@ -55,15 +55,9 @@ Essentially, copying data from the filesystem to your repository is called
 a backup using the 'bup save' command, but that's getting ahead of
 ourselves.
 
-As most backup experts know, backing stuff up is normally about 100x more
-common than restoring stuff, ie.  copying from the repository to your
-filesystem.  For that reason, and also because bup is so new, there is no
-actual 'bup restore' command that does the obvious inverse operation to 'bup
-save'.  There are 'bup ftp' and 'bup fuse', which let you access your
-backed-up data, but they aren't as efficient as a fully optimized restore
-tool intended for high-volume restores.  There's nothing stopping us from
-writing one; we just haven't written it yet.  Feel free to pester us about
-it on the bup mailing list (see the README to find out about the list).
+For the inverse operation, ie. copying from the repository to your
+filesystem, you have several choices; the main ones are 'bup restore', 'bup
+ftp', 'bup fuse', and 'bup web'.
 
 Now, those are the basics of backups.  In other words, we just spent about
 half a page telling you that bup backs up and restores data.  Are we having
@@ -125,28 +119,35 @@ anything over a few megabytes in size, bup's compression will actually
 *work*, which is a bit 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 32
-bytes.  (Why 32?  No reason.  Literally.  We picked it out of the air. 
+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. 
 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.)
+stolen from rsync and xdelta, although we use it differently.  And they use
+some kind of variable window size based on a formula we don't totally
+understand.)
 
-The particular rolling checksum algorithm we use is called "stupidsum,"
-because it's based on the only checksum Avery remembered how to calculate at
+The original rolling checksum algorithm we used was called "stupidsum,"
+because it was based on the only checksum Avery remembered how to calculate at
 the time.  He also remembered that it was the introductory checksum
 algorithm in a whole article about how to make good checksums that he read
 about 15 years ago, and it was thoroughly discredited in that article for
 being very stupid.  But, as so often happens, Avery couldn't remember any
-better algorithms from the article.  So what we get is stupidsum.  (If
-you're a computer scientist and can demonstrate that some other rolling
+better algorithms from the article.  So what we got is stupidsum.
+
+Since then, we have replaced the stupidsum algorithm with what we call
+"rollsum," based on code in librsync.  It's essentially the same as what
+rsync does, except we use a fixed window size.
+
+(If you're a computer scientist and can demonstrate that some other rolling
 checksum would be faster and/or better and/or have fewer screwy edge cases,
 we need your help!  Avery's out of control!  Join our mailing list!  Please! 
 Save us! ...  oh boy, I sure hope he doesn't read this)
 
-In any case, stupidsum, although stupid, seems to do pretty well at its job. 
-You can find it in _hashsplit.c.  Basically, it converts the last 32 bytes
-of the file into a 32-bit integer.  What we then do is take the lowest 13
-bits of the checksum, and if they're all 1's, we consider that to be the end
+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
+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
 average chunk size is 8192 bytes.
 
@@ -181,7 +182,7 @@ file, all the chunks *before* and *after* the affected chunk are absolutely
 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 stupidsum, about one in 8192 possible 32-byte sequences is a
+because of rollsum, about one in 8192 possible 128-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.
@@ -280,7 +281,7 @@ they're written.
 But that leads us to our next problem.
 
 
-Huge numbers of huge packfiles (git.PackMidx, cmd/midx)
+Huge numbers of huge packfiles (midx.py, bloom.py, cmd/midx, cmd/bloom)
 ------------------------------
 
 Git isn't actually designed to handle super-huge repositories.  Most git
@@ -353,9 +354,13 @@ You generate midx files with 'bup midx'.  The downside of midx files is that
 generating one takes a while, and you have to regenerate it every time you
 add a few packs.
 
-(Computer Sciency observers will note that there are some interesting data
-structures out there that could help make things even better.  A very
-promising sounding one is called a "bloom filter." Look it up in Wikipedia.)
+UPDATE: Brandon Low contributed an implementation of "bloom filters", which
+have even better characteristics than midx for certain uses.  Look it up in
+Wikipedia.  He also massively sped up both midx and bloom by rewriting the
+key parts in C.  The nicest thing about bloom filters is we can update them
+incrementally every time we get a new idx, without regenerating from
+scratch.  That makes the update phase much faster, and means we can also get
+away with generating midxes less often.
 
 midx files are a bup-specific optimization and git doesn't know what to do
 with them.  However, since they're stored as separate files, they don't
@@ -561,8 +566,9 @@ compare the files in the index against the ones in the backup set, and
 update only the ones that have changed.  (Even more interesting things
 happen if people are using the files on the restored system and you haven't
 updated the index yet; the net result would be an automated merge of all
-non-conflicting files.)  This would be a poor man's distributed filesystem. 
-The only catch is that nobody has written 'bup restore' yet.  Someday!
+non-conflicting files.) This would be a poor man's distributed filesystem. 
+The only catch is that nobody has written this feature for 'bup restore'
+yet.  Someday!
 
 
 How 'bup save' works (cmd/save)