Tower of Hanoi pattern for backup

Regular backups are vital to protect ourselves and our data against failures of the software, the hardware, or even of the users themselves. There is always a conflict between the need to have frequent backups and the cost of keeping the media for these 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 have three pegs on a piece of board with a pile of discs on one of them. The object of the game is to move the discs from one peg to another by moving one disc at a time and always following the rule that you never put a larger disc on top of a smaller one. The game in turn comes from 19th century myth about an Eastern temple where the priests were supposed to be 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. Just repeat the following two steps until the entire pile has moved:

• Move the smallest disc clockwise
• Make the only other legal move not involving the smallest disc

These rules generate the following pattern of moves on a tower of three discs labelled 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 will be

ABACABADABACABA.

It's easy to extend this to any number of discs. For five discs the solution is to use the four-disk pattern and clear all four off of the fifth disc, then move the fifth disc and move the four back on top of it again:

ABACABADABACABAEABACABADABACABA

We can also go the other way. The original three-disc pattern of moves is made up of an "ABA" pattern which moves two discs off of the largest disc, "C" so that that largest disc can be moved, and 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:

1. One day old
2. Two days old
3. Four days old
4. Eight days old
5. 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. We don't bother going that far. We back up once a week to a box of five DVDs and the fifth DVD only gets used twice a year.

How do I do lay out a schedule?

The easiest way to lay out a month's Tower of Hanoi pattern is to take a grid of days (or weeks) 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"

Generating the schedule in code

This FoxPro procedure will print the sequence for five disks:

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.