Tower of Hanoi backup (original) (raw)
Tower of Hanoi pattern for backup
Regular backups are vital to protect ourselves against failures of the software, the hardware, or even of the users. There is always a conflict between the need to have frequent backups and the cost of keeping such backups for a long time. The Tower of Hanoi pattern is a useful compromise.
Where does the name come from?
The name comes from the children's game where you start with three pegs on a piece of board. The object is to move a pile of discs from one peg to another by moving one disc at a time and never putting a larger disc on a smaller one. The game in turn comes from 19th century myth about an Eastern temple where the priests are engaged in moving 64 gold disks from one diamond needle to another. They have been doing this day and night since the beginning of time. When they complete their task the temple will crumble and the universe will end.
What's the connection?
This algorithm is the fastest solution to the Tower of Hanoi game:
- Move the smallest disc clockwise
- Make the only other legal move not involving the smallest disc
It generates the following pattern of moves on a tower of three discs A, B & C:
- Move A
- Move B
- Move A
- Move C
- Move A
- Move B
- Move A
The solution is recursive and can easily be extended. If there were four discs then you would use the three-disc solution to move the top three discs off of disc D, move disc D, then use the three-disc solution again to put the three discs back onto disc D. The three-disc solution is:
ABACABA
so the four-disc solution is
ABACABADABACABA.
If there are five discs then the solution is to use this pattern to move the top four, then move the bottom one, and then move the four back again:
ABACABADABACABAEABACABADABACABA
We can also go the other way. The original three-disc pattern of moves is made up of an "ABA" pattern to move two discs off of the largest disc, "C" to move that largest disc, then "ABA" to move the two discs back onto the largest one. And you can analyse the "ABA" pattern in the same way - Move "A", then move "B", then move "A" back again.
How does this help with backups?
The five-disc solution above is a string of 31 characters which consists of five different letters. You could use it as a schedule to give you a month of backups by using five tapes labelled "A" to "E". It won't give you a backup for every day of the month but at the end of the month you would have a very good spread of data on your five tapes:
- One day old
- Two days old
- Four days old
- Eight days old
- Sixteen days old
This binary pattern extends very quickly. A sixth tape would be used every 64 days, a seventh every 128 days, and the eight, ninth and tenth tapes would come up every 256, 512, and 1024 days. A box of ten tapes (or CDs or DVDs) would last for nearly three years. In practice we make a full backup every week and use six CDs.
How do I do it in practice?
The easiest way to lay out a month's Tower of Hanoi pattern is like this:
- Mark every alternate day as "A"
- Mark every alternate blank day as "B"
- Mark every alternate blank day as "C"
- Mark every alternate blank day as "D"
- Mark every alternate blank day as "E"
| 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| A | A | A | A | A | A | A | A | ||||||||
| B | B | B | B | ||||||||||||
| C | C | ||||||||||||||
| D | |||||||||||||||
| E |
Generating the schedule in code
This FoxPro procedure will print the sequence for five disks:
lnNumDisks = 5
lnLen = (2 ^ lnNumDisks) - 1
For lnDay = 1 To lnLen
For n = 0 To lnNumDisks
If Bittest (lnDay, n)
?n + 1
Exit
Endif
Next lnPos
Next lnDay
The code relies on the link between the Tower of Hanoi and the digits of binary numbers. If you write the binary numbers from 1 to 31 you'll see that the final digit is '1' on every alternate row. Looking at the remaining rows you'll see that the penultimate digit is '1' on every alternate row.