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

[Christos Zoulas <christos%zoulas.com@localhost>]

Here is what chatgpt has to say:

The Tower of Hanoi backup scheme is used with tape backups because it provides 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 puzzle.

How it works

Suppose you have five tapes labeled A–E.

Instead of reusing tapes in a simple rotation, each tape is used at different 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 everything 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 the schedule.
- It doesn't align with business reporting periods (month-end, quarter-end, year-end).
- Modern disk-based backup systems with deduplication often make this approach 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 cloud storage allow organizations to keep many recovery points without carefully managing physical media. However, the Tower of Hanoi scheme can still be useful 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 age of recoverable backups while minimizing the number of tapes required.

> On Aug 1, 2026, at 7:30 AM, Taylor R Campbell via gnats <gnats-admin%netbsd.org@localhost> wrote:
> 
> The following reply was made to PR bin/60521; it has been noted by GNATS.
> 
> 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
> 
> 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:
>> =20
>> 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
>> =20
>> 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.
>> =20
>> Here are two different versions of the progression.  (They're
>> related to the number of rings on the three pegs, by the way.)
>> =20
>> 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
>> =20
>> 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=3D_i1sO47qNnMC&q=3Dhanoi#v=3Dsnippet&q=3D=
> hanoi&f=3Dfalse
> 
> 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.
>