Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
1999-06-10
2003-12-16
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S112000, C711S156000
Reexamination Certificate
active
06665779
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to disk drive backup systems and, more particularly, to image backup methods for backing up selected data from disk partitions of storage devices.
2. Description of the Related Art
Modern computer systems typically include one or more mass storage devices such as hard disk drives, optical disc drives, floppy disk drives, removable disk drives, and the like to store a large amount of information. Often, however, the storage devices fail to operate properly for various electromechanical defects. In the event of such failures, valuable data stored on the storage devices may be lost permanently or may require costly and time consuming repairs to recover the original data. To guard against such failures, modern computer systems typically employ a backup system to backup data stored on a storage device. When the storage device fails or original data becomes corrupted, the backup system uses the backed up data to restore the original data.
Generally, storage devices contain one or more disks for storing data. For example, hard disk drives typically include one or more disks arranged to store data. The hard disk drives include a plurality of sectors and may be partitioned into one or more partitions (e.g., volumes, logical drives, etc.) as is well known in the art. In addition, each of the disk partitions is a logically self-contained volume and is typically represented by a drive letter such as “C,” “D,” “E,” or the like. Each partition contains files and directory bit maps such as file allocation table or the like. Typically, a partition is organized as a linear sequence of clusters, each of which is comprised of a number of sectors.
FIG. 1A
illustrates a schematic diagram of an exemplary disk
100
for storing data. The disk
100
is configured to include a plurality of tracks
102
. Each of the tracks
102
is divided into sectors
104
for storing data. The disk
100
may be partitioned into one or more partitions with each partition having a file allocation data structure such as a file allocation table.
FIG. 1B
shows a schematic diagram of an exemplary track
102
divided into sectors
104
. In this arrangement, files are configured to be stored in the disk
100
in units of clusters
106
. Each of the clusters
106
includes a pair of sectors
104
. As is well known in the art, however, a cluster may include any number of number of contiguous sectors typically in powers of two (e.g., 1, 2, 4, 8, 16, etc.).
In general, a cluster is the smallest allocation unit for a file as implemented in many operating systems (e.g., MS-DOS™, MS WINDOWS™, etc.). A file uses one or more clusters to store its data. For example, if a file is comprised of a single byte of data, a single cluster is allocated to store the file data. On the other hand, if the size of the file exceeds that of a single cluster, a plurality of clusters may be required to store the large file data.
FIG. 1C
shows a schematic diagram of a plurality of clusters
106
used to store files F
1
, F
2
, F
3
, and F
4
. The clusters
106
are arranged sequentially in the order of clusters C
1
, C
2
, C
3
, C
4
, C
5
, C
6
, C
7
, and C
8
. The files F
1
and F
3
are smaller than a cluster size and are stored in clusters C
1
and C
5
, respectively. On the other hand, the files F
2
and F
4
are larger than a cluster size and thus require more than a cluster to store them. For example, the file F
2
is stored in the clusters C
2
and C
3
while the file F
4
is stored in the clusters C
6
and C
7
. The files F
1
, F
2
, F
3
, and F
4
do not completely fill the clusters C
1
, C
3
, C
5
, and C
7
, respectively, so as to leave spaces
108
that are not used. However, in the absence of compression, these spaces
108
are typically not used to store data from other files. Since the clusters C
1
, C
2
, C
3
, C
5
, C
6
, and C
7
are used to store valid file data, they are referred to herein as used-clusters, valid data space, or the like.
In contrast, the clusters C
4
and C
8
are not used to store valid file data and its spaces
110
are available for storing data. The spaces
110
corresponding to the unused clusters C
4
and C
8
are also referred to herein as “free spaces,” “available spaces,” “holes,” or the like. The spaces
110
may be classified into two categories. On the one hand, the spaces
110
may contain zeros because the clusters have not been used to store data. On the other hand, the spaces
110
may include data from a file that has been previously deleted. In this case, the spaces may include non-zero or garbage data. In either case, the spaces represent unused spaces or clusters where data may be written to.
Operating systems in modem computer systems typically keep track of the free spaces by means of free list, bit map, or the like. For example, conventional bit maps provide a bit for each allocation unit (e.g., cluster) indicating whether the associated allocation unit is available or not for writing data. In this manner, when new data are to be written to a disk, the operating system checks the bit map and determines one or more available allocation units to write the data. The free list or bit map is generally provided in a file allocation data structure (e.g., file allocation table or FAT) for each partition and is well known in the art.
Back up techniques typically fall into two broad categories: file-based backup and image-based backup. In file-based backup systems, the contents of individual files are copied from a source disk to a backup media. The files are usually copied without regard for how they are arranged on the source disk. For example, a partition may have ten sectors containing two files. One file is stored in sectors two through four and sectors eight and nine while the other file is stored in sectors five through seven. The remaining sectors zero and one are unused. In this case, the file-based backup would store information in the backup in the following sequence: sectors two through four, eight and nine, five through seven, such that the unused sectors zero and one are not copied.
However, since a partition or drive often includes hundreds or even thousands of files, backing up all files of the entire partition or drive may require a substantial number of non-sequential read and write operations. For example, to back up the former file in sectors two through four and sectors eight and nine, a backup system reads sectors two through four first, and then performs a seek to sector eight for reading sectors eight and nine. Such non-sequential read and write operation entails numerous seek operations to proper sectors of clusters. Accordingly, the conventional file backup method may require a substantial amount of time to backup the entire partition or drive.
By comparison, the image-based backup method generally reduces the time required to backup an entire partition. Image-based backup systems operate on a partition or drive basis and are capable of backing up a disk or one or more partitions of the disk. In this method, all data on the partition, including valid data, free space, and invalid data, are copied and stored on a backup medium. For example, to perform an image backup of a partition “C,” the image-based backup method operates to read and store the data on the partition sequentially from beginning sector to the end. By thus reading and storing the sectors linearly, seek operations are minimized. Hence, the backup time is typically reduced in comparison with the file-based backup technique.
Unfortunately, the conventional image-based backup methods have several drawbacks. For example, since conventional image backup systems typically store all data including valid data, free space, and invalid data, a substantial portion of the backup medium may be used to store unnecessary data such as the invalid data and the free space data, which typically consists of zeros. To the extent that a partition has a relatively high percentage of free space, the conventional backup systems may exhibit a corres
Berhan Michael D.
Evers Daniel L.
Halloran Thomas G.
Polfer Daniel A.
Anderson Matthew D.
Kim Matthew
Martine & Penilla LLP
Roxio, Inc.
LandOfFree
Image backup method for backing up disk partitions of a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image backup method for backing up disk partitions of a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image backup method for backing up disk partitions of a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3143540