Enhanced Towers of Hanoi

Vincent Cordrey and Jordan Schwartz

http://etoh.wopr.net/prelim.discussion.html

Abstract

Standard Towers of Hanoi implementations are typically weekly in scope. By virtue of making sure that any changed file appears on at least two backup images, a Towers of Hanoi scheme provides a more robust backup schedule. At the same time, the number of times a changed file is backed up is limited and therefore the tape utilization is reduced as compared to other schemes. The standard pattern can be described as weekly fulls followed by daily incrementals.

The enhancement described here extends the scope of the Towers of Hanoi pattern to an entire month. The enhanced pattern can be thought of as a monthly full, weekly deltas, and daily incrementals. This paper briefly presents the pattern and describes how it might be implemented in on a standard 12 month calendar. Additionally, extending the concept to a yearly or quarterly baseline based pattern is presented as an option for some sites.

Standard Implementation

The usual pattern for Towers of Hanoi looks something like this:

Standard Towers of Hanoi Schedule

0 2 1 3 2 5 4

This is discussed extensively in Curtis Preston's O'Riley and Associates Book. Basically, this pattern is repeated each week, and changed files end up on at least two incremental runs during any given week.

Standard Towers of Hanoi Schedule
0	2	1	3	2	5	4

Enhanced Pattern

The goal was to have a monthly full, weekly deltas and daily incrementals. To accomplish this, two Towers of Hanoi patterns are created; one for the week, and one for the beginning of each week.

Enhanced Towers of Hanoi Schedule

0 ^F 5 ^I 4 ^I 7 ^I 6 ^I 9 ^I 8 ^I

2 ^W 5 ^I 4 ^I 7 ^I 6 ^I 9 ^I 8 ^I

1 ^W 5 ^I 4 ^I 7 ^I 6 ^I 9 ^I 8 ^I

3 ^W 5 ^I 4 ^I 7 ^I 6 ^I 9 ^I 8 ^I

2 ^W 5 ^I 4 ^I 7 ^I 6 ^I 9 ^I 8 ^I

Enhanced Towers of Hanoi Schedule
0 ^F	5 ^I	4 ^I	7 ^I	6 ^I	9 ^I	8 ^I
2 ^W	5 ^I	4 ^I	7 ^I	6 ^I	9 ^I	8 ^I
1 ^W	5 ^I	4 ^I	7 ^I	6 ^I	9 ^I	8 ^I
3 ^W	5 ^I	4 ^I	7 ^I	6 ^I	9 ^I	8 ^I
2 ^W	5 ^I	4 ^I	7 ^I	6 ^I	9 ^I	8 ^I

Retention Policies

The "Enhanced Towers of Hanoi" table above has magenta ^F, green ^W, and blue ^I backgrounds to show visually the three logical groups which can have different retention periods. Those groups are:

Tape Group Color Scheme

Magenta ^F

Full backup (level 0)

Green ^W

Weekly deltas (levels 1-3)

Blue ^I

Daily incrementals (levels 4-9)

Red ^B

Baseline (level 0)

Tape Group Color Scheme
Magenta ^F Full backup (level 0) Green ^W Weekly deltas (levels 1-3) Blue ^I Daily incrementals (levels 4-9) Red ^B Baseline (level 0)

A typical retention policy could look like this:

Typical Retention Policy

Full backup (level 0) ^F 1 Year

Weekly deltas (levels 1-3) ^W 1 Quarter

Daily incrementals (levels 4-9) ^I 1 Month

Typical Retention Policy
Full backup (level 0) ^F	1 Year
Weekly deltas (levels 1-3) ^W	1 Quarter
Daily incrementals (levels 4-9) ^I	1 Month

A simplified retention policy could look like this:

Simplified Retention Policy

Full backup (level 0) ^F 1 Year

Weekly deltas (levels 1-3) ^W 1 Quarter

Daily incrementals (levels 4-9) ^I

Simplified Retention Policy
Full backup (level 0) ^F	1 Year
Weekly deltas (levels 1-3) ^W	1 Quarter
Daily incrementals (levels 4-9) ^I

Baselined Schedules

The Towers of Hanoi schedule can be further enhanced to provide yearly or quarterly base lines. In this implementation, only files changed after the baseline are backed up.

For robustness, it is strongly suggested that any base-line be run twice. To guarantee the consistency of a base-line, the filesystem must be quiescent or static. This can be done with any one of the following techniques:

a scheduled system outage window
remounting the filesystem read-only
using a snapshot utility

Off-site copies of both Baseline images, are a good idea, but at least two copies of the Baseline must be kept on site for recovery purposes since more recently created tapes will not contain a full filesystem.

The schedule tables are modified to pull in one more incremental level into the weekly deltas:

Baselined Towers of Hanoi Schedule

Baseline 0 ^B run twice

0 ^B

Monthly 1 ^F 6 ^I 5 ^I 8 ^I 7 ^I 9 ^I 8 ^I

3 ^W 6 ^I 5 ^I 8 ^I 7 ^I 9 ^I 8 ^I

2 ^W 6 ^I 5 ^I 8 ^I 7 ^I 9 ^I 8 ^I

4 ^W 6 ^I 5 ^I 8 ^I 7 ^I 9 ^I 8 ^I

3 ^W 6 ^I 5 ^I 8 ^I 7 ^I 9 ^I 8 ^I

The monthly portion is repeated each month until the next quarterly or yearly baseline baseline is run.

Baselined Towers of Hanoi Schedule
Baseline	0 ^B	run twice
0 ^B
Monthly	1 ^F	6 ^I	5 ^I	8 ^I	7 ^I	9 ^I	8 ^I
3 ^W	6 ^I	5 ^I	8 ^I	7 ^I	9 ^I	8 ^I
2 ^W	6 ^I	5 ^I	8 ^I	7 ^I	9 ^I	8 ^I
4 ^W	6 ^I	5 ^I	8 ^I	7 ^I	9 ^I	8 ^I
3 ^W	6 ^I	5 ^I	8 ^I	7 ^I	9 ^I	8 ^I

Implementation

A careful reader will observe that the monthly schedule includes 35 days (5 weeks of 7 days). This is intentional because the length of a month with the exception of about three out of four Februaries is not an even number of weeks. So, the tables do require some interpretation.

An additional anomaly is that the monthly schedule starts at the left edge where the calendar would have Sunday. This will work fine for sites which can perform a full backup starting on Sunday without running significantly into the production day, but it may not be realistic for some large sites where the benefit of backup media economies of the Towers of Hanoi scheme has the greatest benefit. Typically, these sites are large enough that they require the entire weekend window to perform a full backup or at least a significant portion of it that may start as early as Friday.

Thus, the backup schedule may have to start running fulls on Saturday or Friday night. In this case, the mapping of days looks something like this:

Enhanced Towers of Hanoi Schedule
Sat-Sun	Mon	Tue	Wed	Thu	Fri	not used
0 ^F	5 ^I	4 ^I	7 ^I	6 ^I	9 ^I	8
2 ^W	5 ^I	4 ^I	7 ^I	6 ^I	9 ^I	8
1 ^W	5 ^I	4 ^I	7 ^I	6 ^I	9 ^I	8
3 ^W	5 ^I	4 ^I	7 ^I	6 ^I	9 ^I	8
2 ^W	5 ^I	4 ^I	7 ^I	6 ^I	9 ^I	8

If the backup window for the weekly deltas or fulls must run over an entire weekend, then the schedule rotates one more day with the first day starting on Friday night.

The result can be a schedule where the weekly deltas (green ^W) can be completed overnight and only the monthly fulls must be run differently.

Starting The Month

The best way to start the month is to run the monthly on the first weekend of the month. This prevents a full from being launch during one of the short mid-week nightly windows. Thus, the first few days of the month will follow the previous months pattern based on day of the week until that first weekend when the monthly pattern is reset.

Scripting Backup Schedule Table Creation

The creation of the scripts and programs necessary to describe these tables to a backup program, or launch the appropriate backup level programmatically are left as an exercise to the reader.

Summary

The Enhanced Towers of Hanoi schedule described in this paper goes one step further in economizing backup media utilization than a standard weekly full with daily incrementals schedule. It offers greater media conservation than even a traditional weekly Towers of Hanoi approach. It is hoped that backup enthusiasts find this information useful.