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

["Christos Zoulas via gnats" <gnats-admin%NetBSD.org@localhost>]

The following reply was made to PR bin/60521; it has been noted by GNATS.

From: Christos Zoulas <christos%zoulas.com@localhost>
To: gnats-bugs%netbsd.org@localhost
Cc: gnats-admin%netbsd.org@localhost, netbsd-bugs%netbsd.org@localhost,
 campbell+netbsd%mumble.net@localhost
Subject: Re: bin/60521: dump(8): mystery of Hanoi
Date: Sat, 1 Aug 2026 14:40:53 +0300

 Here is what chatgpt has to say:
 
 The Tower of Hanoi backup scheme is used with tape backups because it provid=
 es a good balance between three competing goals:
 
 - Keeping many historical backup versions.
 - Using a relatively small number of tapes.
 - Ensuring older backups are retained for progressively longer periods.
 
 It is based on the same mathematical pattern as the classic Tower of Hanoi p=
 uzzle.
 
 How it works
 
 Suppose you have five tapes labeled A=E2=80=93E.
 
 Instead of reusing tapes in a simple rotation, each tape is used at differen=
 t intervals:
 
 Tape A: every 2 backups
 Tape B: every 4 backups
 Tape C: every 8 backups
 Tape D: every 16 backups
 Tape E: every 32 backups
 
 For daily backups, the schedule might look like this:
 
 Day  1: Tape A
 Day  2: Tape B
 Day  3: Tape A
 Day  4: Tape C
 Day  5: Tape A
 Day  6: Tape B
 Day  7: Tape A
 Day  8: Tape D
 Day  9: Tape A
 Day 10: Tape B
 Day 11: Tape A
 Day 12: Tape C
 Day 13: Tape A
 Day 14: Tape B
 Day 15: Tape A
 Day 16: Tape E
 
 Notice that:
 - Tape A is overwritten frequently.
 - Tape E isn't overwritten until day 32.
 - Some backups naturally become long-term recovery points.
 
 Why this is useful
 
 Imagine someone accidentally deletes a file.
 
 - If they notice tomorrow, yesterday's backup (Tape A) is available.
 - If they notice two weeks later, Tape D may still contain the data.
 - If they notice a month later, Tape E may still have it.
 
 A simple five-tape rotation would only let you go back five days before ever=
 ything had been overwritten.
 
 Advantages
 
 - Excellent history with few tapes.
 - Automatic aging. Older backups are naturally retained longer.
 - No calendar required. The schedule is purely mathematical.
 - Efficient for incremental backups.
 
 Disadvantages
 
 - The schedule is harder to understand than daily/weekly/monthly rotations.
 - Finding the newest backup before a particular date can require consulting t=
 he schedule.
 - It doesn't align with business reporting periods (month-end, quarter-end, y=
 ear-end).
 - Modern disk-based backup systems with deduplication often make this approa=
 ch unnecessary.
 
 Comparison with Grandfather-Father-Son (GFS)
 
 Tower of Hanoi
 - Mathematical schedule
 - Very tape-efficient
 - Automatic exponential retention
 - Best when tape count is limited
 
 Grandfather-Father-Son
 - Calendar schedule
 - Easier to understand
 - Explicit daily/weekly/monthly backups
 - Better for compliance and auditing
 
 Is it still used?
 
 Today it's relatively uncommon because disk-based backup appliances and clou=
 d storage allow organizations to keep many recovery points without carefully=
  managing physical media. However, the Tower of Hanoi scheme can still be us=
 eful when:
 - using physical tapes,
 - tape inventory is limited,
 - and long retention is desired without purchasing many additional tapes.
 
 It remains an elegant example of using exponential spacing to maximize the a=
 ge of recoverable backups while minimizing the number of tapes required.
 
 > On Aug 1, 2026, at 7:30=E2=80=AFAM, Taylor R Campbell via gnats <gnats-adm=
 in%netbsd.org@localhost> wrote:
 >=20
 > =EF=BB=BFThe following reply was made to PR bin/60521; it has been noted b=
 y GNATS.
 >=20
 > From: Taylor R Campbell <riastradh%NetBSD.org@localhost>
 > To: gnats-bugs%NetBSD.org@localhost, netbsd-bugs%NetBSD.org@localhost
 > Cc:
 > Subject: Re: bin/60521: dump(8): mystery of Hanoi
 > Date: Sat, 1 Aug 2026 04:28:14 +0000
 >=20
 > 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:
 >=20
 >>     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:
 >> =3D20
 >> 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
 >> =3D20
 >> We do weekly dumps often enough that daily dumps always  fit
 >> on one tape.
 >=20
 > 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.
 >=20
 > 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.
 >=20
 > 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.
 >=20
 > 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):
 >=20
 >> 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.
 >> =3D20
 >> Here are two different versions of the progression.  (They're
 >> related to the number of rings on the three pegs, by the way.)
 >> =3D20
 >> 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
 >> =3D20
 >> 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.
 >=20
 > https://books.google.com/books?id=3D3D_i1sO47qNnMC&q=3D3Dhanoi#v=3D3Dsnipp=
 et&q=3D3D=3D
 > hanoi&f=3D3Dfalse
 >=20
 > 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.
 >=20
 > 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.
 >=20
 > 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.
 >=20
 > 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?
 >=20
 > 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):
 >=20
 > 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
 >=20
 > 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.
 >=20