Tower of Hanoi scheme

  At a glance
  • Up to 16 levels of full, differential, and incremental backups
  • Next-level backups are twice as rare as previous-level backups
  • One backup of each level is stored at a time
  • Higher density of more recent backups 
  Parameters

You can set up the following parameters of a Tower of Hanoi scheme.

Schedule

Set up a daily, weekly, or monthly schedule. Setting up schedule parameters allows creating simple schedules (example of a simple daily schedule: a backup task will be run every 1 day at 10 AM) as well as more complex schedules (example of a complex daily schedule: a task will be run every 3 days, starting from January 15. During the specified days the task will be repeated every 2 hours from 10 AM to 10 PM). Thus, complex schedules specify the sessions on which the scheme should run. In the discussion below, “days” can be replaced with “scheduled sessions”.

Number of levels

Select from 2 to 16 backup levels. See the example stated below for details.

Roll-back period

The guaranteed number of sessions that one can go back in the archive at any time. Calculated automatically, depending on the schedule parameters and the numbers of levels you select. See the example below for details. 

  Example

Schedule parameters are set as follows

  • Recur: Every 1 day
  • Frequency: Once at 6 PM

Number of levels: 4

This is how the first 14 days (or 14 sessions) of this scheme’s schedule look. Shaded numbers denote backup levels.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

4

1

2

1

3

1

2

1

4

1

2

1

3

1

Backups of different levels have different types:

  • Last-level (in this case, level 4) backups are full;
  • Backups of intermediate levels (2, 3) are differential;
  • First-level (1) backups are incremental.

A cleanup mechanism ensures that only the most recent backups of each level are kept. Here is how the archive looks on day 8, a day before creating a new full backup.

1

2

3

4

5

6

7

8

4

1

2

1

3

1

2

1

The scheme allows for efficient data storage: more backups accumulate toward the current time. Having four backups, we could recover data as of today, yesterday, half a week, or a week ago. 

  Roll-back period

The number of days we can go back in the archive is different on different days. The minimum number of days we are guaranteed to have is called the roll-back period.

The following table shows full backup and roll-back periods for schemes of various levels.

Number of levels

Full backup every

On different days, can go back

Roll-back period

2

2 days

1 to 2 days

1 day

3

4 days

2 to 5 days

2 days

4

8 days

4 to 11 days

4 days

5

16 days

8 to 23 days

8 days

6

32 days

16 to 47 days

16 days

Adding a level doubles the full backup and roll-back periods.

To see why the number of recovery days varies, let us return to the previous example.

Here are the backups we have on day 12 (numbers in gray denote deleted backups).

1

2

3

4

5

6

7

8

9

10

11

12

4

1

2

1

3

1

2

1

4

1

2

1

A new level 3 differential backup has not yet been created, so the backup of day five is still stored. Since it depends on the full backup of day one, that backup is available as well. This enables us to go as far back as 11 days, which is the best-case scenario.

The following day, however, a new third-level differential backup is created, and the old full backup is deleted.

1

2

3

4

5

6

7

8

9

10

11

12

13

4

1

2

1

3

1

2

1

4

1

2

1

3

This gives us only a four day recovery interval, which turns out to be the worst-case scenario.

On day 14, the interval is five days. It increases on subsequent days before decreasing again, and so on.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

4

1

2

1

3

1

2

1

4

1

2

1

3

1

The roll-back period shows how many days we are guaranteed to have even in the worst case. For a four-level scheme, it is four days.

Tower of Hanoi scheme