Re: bin/60521: dump(8): mystery of Hanoi

[Taylor R Campbell <riastradh%NetBSD.org@localhost>]

Aha!  Another Google Scholar search with slightly different query
(`hanoi backup tape') turned up a document that is...actually in our
source tree already(!), namely src/share/doc/smm/01.setup (installed
at /usr/share/doc/smm/setup), or the `Installing and Operating 4.4BSD
UNIX' manual, which has this excerpt:

>      Dumping  of  the  filesystems should be done regularly,
> since once the system is going it is easy to become  compla-
> cent.   Complete  and incremental dumps are easily done with
> dump(8).  You should arrange to do  a  towers-of-hanoi  dump
> sequence;  we  tune ours so that almost all files are dumped
> on two tapes and kept for at least  a  week  in  most  every
> case.  We take full dumps every month (and keep these indef-
> initely).  Operators can execute ``dump w''  at  login  that
> will  tell  them  what  needs  to  be  dumped  (based on the
> /etc/fstab information).  Be sure to create a group operator
> in  the  file  /etc/group  so that dump can notify logged-in
> operators when it needs help.
>      More precisely, we have three sets of  dump  tapes:  10
> daily  tapes,  5  weekly  sets of 2 tapes, and fresh sets of
> three tapes monthly.  We do daily dumps  circularly  on  the
> daily tapes with sequence `3 2 5 4 7 6 9 8 9 9 9 ...'.  Each
> weekly is a level  1  and  the  daily  dump  sequence  level
> restarts after each weekly dump.  Full dumps are level 0 and
> the daily sequence restarts after each full dump also.
>      Thus a typical dump sequence would be:
> 
>  tape name   level number       date         opr      size
>  ----------------------------------------------------------
>    FULL           0         Nov 24, 1992   operator   137K
>      D1           3         Nov 28, 1992   operator   29K
>      D2           2         Nov 29, 1992   operator   34K
>      D3           5         Nov 30, 1992   operator   19K
>      D4           4          Dec 1, 1992   operator   22K
>      W1           1          Dec 2, 1992   operator   40K
>      D5           3          Dec 4, 1992   operator   15K
>      D6           2          Dec 5, 1992   operator   25K
>      D7           5          Dec 6, 1992   operator   15K
>      D8           4          Dec 7, 1992   operator   19K
>      W2           1          Dec 9, 1992   operator   118K
>      D9           3         Dec 11, 1992   operator   15K
>     D10           2         Dec 12, 1992   operator   26K
>      D1           5         Dec 15, 1992   operator   14K
>      W3           1         Dec 17, 1992   operator   71K
>      D2           3         Dec 18, 1992   operator   13K
>    FULL           0         Dec 22, 1992   operator   135K
> 
> We do weekly dumps often enough that daily dumps always  fit
> on one tape.

This actually lays out the correspondence between tapes, levels, and
dates, and gives some criteria it is intended to satisfy:
- almost every file is dumped on at least two different tapes, and
- almost every file is kept for at least a week.

The algorithm for dump levels on successive tapes appears to be 0 3 -1
+3 -1 +3 -1 ... (clamped at 9), which is somewhat like the naive 0 +1
+1 +1 +1 ... except that every other day, on the -1 days, we dump all
the same files as were dumped on the previous day, plus whatever else
has changed since then -- that seems to be how almost every file is
dumped on at least two different tapes...well, except for changes done
between a +3 daily and a -1 daily, which only get saved once until the
next weekly or full.

I'm also confused by the omission of various dates in this sequence.
Perhaps Nov 25,26,27 are missing because Nov 26, 1992 was
Thanksgiving, but Nov 28 was a Saturday and Nov 29 was a Sunday, so
why are they included?  Then Dec 3 is missing, a non-holiday Thursday.

The sequence matches a description I found in W. Curtis Preston, _Unix
Backup and Recovery_, O'Reilly, 1999, pp. 40--42, alongside a -1 +2
sequence (which repeats some dump levels as it goes, for reasons
unclear):

> One of the goals of most backup schedules is to get changed files on
> more than one volume, while reducing total volume usage.  The Tower
> of Hanoi (TOH) accomplishes this better than any other schedule.  If
> you use a TOH progression for your backup levels, most changed files
> will get backed up twice---but only twice.
> 
> Here are two different versions of the progression.  (They're
> related to the number of rings on the three pegs, by the way.)
> 
> 0 3 2 5 4 7 6 9 8 9
> 0 3 2 4 3 5 4 6 5 7 6 8 7 9 8
> 
> The mathematical progression is actually pretty easy. It's 0 2 3 4 5
> 6 7 8 9, intermixed with 3 4 5 6 7 8 9.

https://books.google.com/books?id=_i1sO47qNnMC&q=hanoi#v=snippet&q=hanoi&f=false

I don't really see any resemblance to the towers of Hanoi binary
progressions that are described elsewhere like in Wikipedia, though,
where the nth tape is recycled every 2^n days, i.e., on day d starting
at 1, you overwrite tape clz(d).  As a result, for n1 > n0, tape n1
gets overwritten 2^{n1 - n0} times as often as tape n0.  In contrast,
the sequence documented in the SMM overwrites every tape with the same
frequency.

So the term `towers of Hanoi' seems to be being used for two
completely different classes of schedules.  The binary progression
strikes me as a closer analogy: if the tapes correspond to puzzle
discs numbered by size, and if moving a disc from one peg to another
in the standard towers of Hanoi algorithm means taking a backup with
the corresponding disc, the binary progression is what you get.

It also remains unclear what dump levels the intent is for binary
progression `towers of Hanoi' rotation schemes -- if any intent can be
ascribed to this.

One possibility is that you always do a full backup, so that with n
tapes, you can always recover 1, 2, 4, ..., 2^n days ago.  But is that
actually done in practice?

Another possibility is that up to level L, on day d, you overwrite
tape clz(d) with a level-(L - clz(d)) backup.  With five tapes,
labelled A/B/C/D for the incrementals (treated as if numbered 0/1/2/3
for the clz correspondence) and F for the full, that would lead to the
following day/tape/level schedule, corresponding sequences of tapes
needed to restore to the latest backup at each point between backups,
and which days you can roll back to at each point between backups (if
I haven't made any mistakes, which I probably have):

day      0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
tape     F  A  B  A  C  A  B  A  D  A  B  A  C  A  B  A  F
level    0  4  3  4  2  4  3  4  1  4  3  4  2  4  3  4  0
recovery  F  F  F  F  F  F  F  F  F  F  F  F  F  F  F  F  F
             A  B  B  C  C  C  C  D  D  D  D  D  D  D  D
                   A     A  B  B     A  B  B  C  C  C  C
                               A           A     A  B  B
                                                       A
rollback  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
             1  1  2  2  2  4  4  4  4  4  4  8  8  8  8
                2  3  3  4  5  6  6  6  8  8  10 10 12 12
                      4  5  6  7  7  8  9  10 11 12 13 14
                                  8  9  10 11 12 13 14 15

I'm not sure what criteria this optimizes either!  It approximates
being able to roll back 2^k days for each k up to the limit.  One
might intuitively expect that with a clever binary progression
involving n levels, you need only fetch at most lg L tapes in tape
libary to recover at any given time, but this clearly doesn't achieve
that.  Maybe something involving Gray codes reduces that metric.