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

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=
[email protected]> 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 <[email protected]>
> To: [email protected], [email protected]
> 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