Grandfather-father-son

Backup rotation scheme

From Wikipedia, the free encyclopedia

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (January 2010)

A backup rotation scheme refers to a system of backing up data to computer media (such as tapes) that minimizes, via re-use, the number of media used. The scheme determines how and when each piece of removable storage is used for a backup job and how long it is retained once it has backup data stored on it. Different techniques have evolved over time to balance data retention and restoration needs with the cost of extra data storage media. Such a scheme can be quite complicated if it takes incremental backups, multiple retention periods, and off-site storage into consideration.

Contents   [hide]  1 Schemes 1.1 First In, First Out 1.2 Grandfather-father-son 1.3 Tower of Hanoi 1.3.1 Three-tape Hanoi schedule 1.3.2 Four-tape Hanoi schedule 1.3.3 Five-tape Hanoi schedule 1.4 Weighted random approach 1.5 Incremented media method 2 See also 3 References

[edit]Schemes

[edit]First In, First Out

A First In, First Out (FIFO) backup scheme saves new or modified files onto the oldest media in the set. Performing a daily backup onto a set of 14 media, the backup depth would be 14 days. Each day, the oldest media would be inserted when performing the backup. This is the simplest rotation scheme, and is usually the first to come to mind. It was commonly used when floppy disks were used as backup media.

Advantages of the FIFO scheme include:

• Used to keep the longest possible tail of daily backups
• Used when archived backups are not as important (i.e. no need to go back one year)
• Useful when data before the rotation period is irrelevant

This scheme, however, suffers from the possibility of data loss. To understand why, consider a file in which an unsuspected error is introduced. Several generations of backups and revisions have since occurred. The error is then detected. At this time, it would be pointless to have all of the most recent generations because all of them have the error. It would instead be beneficial to have at least one of the older generations, as it would not have the error.

[edit]Grandfather-father-son

Grandfather-father-son backup refers to a common rotation scheme for backup media. Originally designed for tape backup, it works well for any hierarchical backup strategy. The basic method is to define three sets of backups, such as daily, weekly and monthly. The daily, or son, backups are rotated on a daily basis with one graduating to father status each week. The weekly or father backups are rotated on a weekly basis with one graduating to grandfather status each month. In addition, quarterly, biannual, and/or annual backups can also be separately retained. Often one or more of the graduated backups is removed from the site for safekeeping and disaster recovery purposes.

[edit]Tower of Hanoi

The Tower of Hanoi rotation method is more complex. It is based on the mathematics of the Tower of Hanoi puzzle, with what is essentially a recursive method. It is a 'smart' way of archiving an effective number of backups as well as the ability to go back over time, but it is more complex to understand. Basically, every tape is associated with a disk in the puzzle, and every disk movement to a different peg corresponds with a backup to that tape. So the first tape is used every other day (1, 3, 5, 7, 9,...), the second tape is used every fourth day (2, 6, 10, ...), the third tape is used every eighth day (4, 12, 20, ...).^[1]

A set of n tapes (or tapes sets) will allow backups for 2 ^n-1 days before the last set is recycled. So, three tapes will give four days worth of backups and on the fifth day Set C will be overwritten; four tapes will give eight days, and Set D is overwritten on the ninth day; five tapes will give 16 days, etc. Files can be restored from 1, 2, 4, 8, 16, ..., 2 ^{n - 1} days ago.^[2] Mathematically, you can look at the sequence of the binary notation of the day number. In each step, the number of zeros on the (right) end of the number determines the tape number to use.

The following tables show which tapes are used on which days of various cycles. Note that the Towers of Hanoi rotation method has the drawback of overwriting the very first backup (day 1 of the cycle) after only two days. However, this can easily be overcome by starting on the last day of a cycle (marked in red in the tables).

[edit]Three-tape Hanoi schedule

	Day of the Cycle
	01	02	03	04	05	06	07	08
Set	A		A		A		A
		B				B
				C				C

[edit]Four-tape Hanoi schedule

	Day of the Cycle
	01	02	03	04	05	06	07	08	09	10	11	12	13	14	15	16
Set	A		A		A		A		A		A		A		A
		B				B				B				B
				C								C
								D								D

[edit]Five-tape Hanoi schedule

	Day of the Cycle
	01	02	03	04	05	06	07	08	09	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32
Set	A		A		A		A		A		A		A		A		A		A		A		A		A		A		A		A
		B				B				B				B				B				B				B				B
				C								C								C								C
								D																D
																E																E

[edit]Weighted random approach

An alternative approach to keeping generations distributed across all points in time is to delete (or overwrite), past generations (except the oldest and the most-recent-ngenerations) when necessary in a weighted-random fashion. For each deletion, the weight assigned to each of the deletable generations is the probability of it being deleted. One acceptable weight is a constant exponent (possibly the square) of the multiplicative inverse of the duration (possibly expressed in the number of days) between the date of the generation and the generation available before it.

Using a larger exponent leads to a more uniform distribution of generations, whereas a smaller exponent lead to a distribution with more recent and fewer older generations. This technique probabilistically ensures that past generations are always distributed across all points in time as desired.

[edit]Incremented media method

This method has many variations and names. A set of numbered media is used until the end of the cycle. Then the cycle is repeated using media numbered the same as the previous cycle, but incremented by one. The lowest numbered tape from the previous cycle is retired and kept permanently. Thus, one has access to every backup for one cycle, and one backup per cycle before that. This method has the advantage of ensuring even media wear, but requires a schedule to be precalculated. The system is generally too complex to mentally calculate the next media to be used.