Acronis Backup & Recovery

Tower of Hanoi backup scheme

The need to have frequent backups always conflicts with the cost of keeping such backups for a long time. The Tower of Hanoi (ToH) backup scheme is a useful compromise.

  Tower of Hanoi overview  

The Tower of Hanoi scheme is based on a mathematical puzzle of the same name. In the puzzle a series of rings are stacked in size order, the largest on the bottom, on one of three pegs. The goal is to move the ring series to the third peg. You are only allowed to move one ring at a time, and are prohibited from placing a larger ring above a smaller ring. The solution is to shift the first ring every other move (moves 1, 3, 5, 7, 9, 11…), the second ring at intervals of four moves (moves 2, 6, 10…), the third ring at intervals of eight moves (moves 4, 12…), and so on.

For example, if there are five rings labeled A, B, C, D, and E in the puzzle, the solution gives the following order of moves:

The Tower of Hanoi backup scheme is based on the same patterns. It operates with Sessions instead of Moves and with Backup levels instead of Rings. Commonly an N-level scheme pattern contains (N-th power of two) sessions.

So, the five-level Tower of Hanoi backup scheme cycles the pattern that consists of 16 sessions (moves from 1 to 16 in the above figure).

The table shows the pattern for the five-level backup scheme. The pattern consists of 16 sessions.

The Tower of Hanoi backup scheme implies keeping only one backup per level. All the outdated backups have to be deleted. So the scheme allows for efficient data storage: more backups accumulate toward the present time. Having four backups, you can recover data as of today, yesterday, half a week ago, or a week ago. For the five-level scheme you can also recover data backed up two weeks ago. So every additional backup level doubles the maximal roll-back period for your data.

  Tower of Hanoi by Acronis  

The Tower of Hanoi backup scheme is generally too complex to mentally calculate the next media to be used. But Acronis Backup & Recovery 10 provides you with automation of the scheme usage. You can set up the backup scheme while creating a backup plan.

Acronis implementation for the scheme has the following features:

• up to 16 backup levels
• incremental backups on first level (A) – to gain time and storage savings for the most frequent backup operations; but data recovery from such backups takes longer because it generally requires access to three backups
• full backups on the last level (E for five-level pattern) – the rarest backups in the scheme, take more time and occupy more space in storage
• differential backups on all intermediate levels (B, C and D for five-level pattern)
• the pattern starts with a full backup since the very first backup cannot be incremental
• the scheme forces every backup level to keep only the most recent backup, other backups from the level have to be deleted; however backup deletion is postponed in cases where the backup is a base for another incremental or differential one
• an old backup on a level is kept until a new backup has been successfully created on the level.

The table shows the pattern for the five-level backup scheme. The pattern consists of 16 sessions.

As a result of using incremental and differential backups the situation may arise when an old backup deletion must be postponed as it still is a base for other backups. The table below indicates the case when deletion of full backup (E) created at session 1 is postponed at session 17 until session 25 because the differential backup (D) created at session 9 is still actual. In the table all cells with deleted backups are grayed out:

Differential backup (D) created at session 9 will be deleted at session 25 after creation of a new differential backup is completed. This way, a backup archive created in accordance with the Tower of Hanoi scheme by Acronis sometimes includes up to two additional backups over the classical implementation of the scheme.

For information about using Tower of Hanoi for tape libraries, see Using the Tower of Hanoi tape rotation scheme.