Abstract:
A method of reading data from a primary storage medium uses a reader moveable relative to the primary storage medium. The method includes sorting a list of files into an order which reduces the movement of the reader relative to the primary storage medium for the reading of the files and reading the files from the primary storage medium in that order.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    The invention relates to data reading and data protection. In particular, the invention relates to backing up data for protection against loss.  
           [0002]    Currently there are two basic methods of reading data from a storage disk for supply to secondary storage devices (e.g. tape drives). The first method is the “file-by-file” method which comprises proceeding sequentially through the file directory for the disk and reading each file from the disk one by one in the order in which they are specified in the directory structure. The second method is the “image” method which comprises reading the whole of the disk sequentially from its first sector, and then using the file system data to work out the locations of the files on the resulting back-up tape.  
           [0003]    The file-by-file method can be very slow when files are randomly stored across the disk, since the disk drive has to mechanically move its read head from one area to another for each file and, if the files are small, then performance is limited by the random access speed of the disk drive. It is relatively quick to restore a disk from a file-by-file back-up since the files are a single contiguous area in the tape or other kind of secondary storage device.  
           [0004]    The creation of an image back-up is always very fast as it involves reading large sequential blocks from the disk with little repositioning of the read head being required, so that performance is limited by the sequential speed of the disk which is usually higher than the performance of the tape drive or other secondary storage device used. However, with image back-up, there are problems associated with restoring the backed-up data to the disk, as the files may not be in a single contiguous area on the tape if they were not contiguous on the disk.  
           [0005]    The file by file method is slow to back-up a disk and quick to restore it, whereas the image method is quick to back-up a disk but slow to restore it.  
           [0006]    EP-A-0 767431 discloses a system for backing-up computer disk volumes by performing an image back-up of a primary storage medium and additionally creating a file index that is also stored on the secondary storage medium, in this case tape. The file index provides the portion of individual files on the secondary storage medium that allows files to be restored to be accessed from the secondary storage medium in as contiguous manner as possible. However, the performance of the restore is still less than a conventional file-by-file restore because the relatively slow secondary storage medium must be accessed to read the file index before a restore may actually be performed.  
         SUMMARY OF THE INVENTION  
         [0007]    An aim of the invention is to provide enhanced data reading and/or data back-up.  
           [0008]    According to one aspect, the invention provides a method of reading data from a storage medium using a reader moveable relative to the medium, the method comprising sorting a list of files into an order which reduces the movement of the reader relative to the medium for the reading of said files and reading the files from the medium in said order.  
           [0009]    According to another aspect, the invention provides apparatus for reading data from a primary storage medium, comprising a reader moveable relative to the primary storage medium for reading the files from the primary storage medium and a sorter for sorting files to be read into an order which reduces the movement of the reader relative to the primary storage medium.  
           [0010]    In one embodiment, the primary storage medium which is read is a disk, particularly a magnetic hard disk. Alternatively, the storage medium is, for example, a tape.  
           [0011]    By sorting the list of files to be read from the primary storage medium in this way, the speed of the back-up can be much greater than the aforementioned file-by-file method since the files can be read from the storage medium without wasting time seeking the files in the storage medium. For example, in the case where the storage medium is a magnetic hard disk, the reading can be done with relatively few read head realignment operations. Although the reading process has a speed approaching that of the image method, it has the advantage that the files can be written into back-up storage with greater contiguity, and the position of each file in the back-up storage is known from the order into which the list was sorted for reading purposes. This is particularly advantageous as no index of files is required to be additionally stored on the back up, or secondary storage, medium to allow the position of the files to be determined. There is therefore no loss in performance in terms of restoring files as there would be if it was necessary to first search a file index before accessing the secondary storage medium.  
           [0012]    In a preferred embodiment, the invention arrives at said order by sorting the files to be read into an order in accordance with their distance from an end location of the primary storage medium. This means that the files are read in the order in which they are to be found in the primary storage medium, thus reducing the need to reposition the reader relative to the medium.  
           [0013]    Preferably, if a file to be read from the primary storage medium is fragmented, the file&#39;s position in said order is determined by the position in the medium of the fragment representing the beginning of said file. This helps to optimise the speed of reading the list of files since, if the position of a fragmented file in the sorted order was represented by some other fragment, then upon reaching the fragmented file in the sorted list, the read operation would immediately have to skip from the fragment represented in the order to the fragment representing the beginning of the file, thus incurring a delay.  
           [0014]    In one embodiment, it is determined whether the number of fragmented files in the primary storage medium exceeds a threshold. If the threshold is exceeded, then defragmentation of the files is attempted prior to reading them. Advantageously, this improves the speed of reading the files from the primary storage medium.  
           [0015]    The invention can be used in the backing-up of data for data protection purposes, wherein the data, after having been read in the manner described above, is then written to back-up, or “secondary”, storage. Preferably, the back-up storage is a tape drive.  
           [0016]    Alternative terminology for primary and secondary storage medium is respectively online and offline storage.  
           [0017]    The invention extends to a storage area network (SAN) including apparatus according to the invention for reading data from a storage medium. The invention also extends to apparatus according to the invention for reading data from a storage medium wherein the reading process is initiated by a Network Data Management Protocol (NDMP) format request. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0018]    By way of example only, the invention will now be described with reference to the accompanying Figures in which:  
         [0019]    [0019]FIG. 1 illustrates some files on a hard disk;  
         [0020]    [0020]FIG. 2 is a block diagram of a computer system;  
         [0021]    [0021]FIG. 3 is a flow chart describing a back-up process; and  
         [0022]    [0022]FIG. 4 illustrates a storage area network (SAN).  
     
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS  
       [0023]    The surface of hard disk  100  of FIG. 1 is divided into a series of concentric annular tracks, only the three outermost of which are shown. Each of the tracks is divided into a number of sectors, e.g. 110. For clarity&#39;s sake, we will assume that each of the sectors contains a separate file. According to the directory structure for the hard disk  100 , the first four files on the disk are, in order, A, B, C and D. FIG. 1 shows the physical positions of files A, B, C and D on disk  100 . To read a file from the disk  100 , the read head of the disk drive containing disk  100  must be scanned over the sector containing the relevant file. The read head of the disk drive is capable of being moved radially with respect to disk  100  (as indicated by arrow S) in order to bring the read head into alignment with the track containing to the file to be read. The disk  100  rotates (in the direction indicated by arrow R) in order to scan the disk beneath the read head.  
         [0024]    In the simplest type of back-up operation, all of the files are read from the disk so that they can be written to a tape drive (or other back-up storage device). Consider the case where the files are read from the disk  100  in the order in which they are listed in the directory, i.e. beginning alphabetically with file A.  
         [0025]    Initially, the read head is positioned to the outermost track and the disk is rotated until file A has been found and scanned. Next, the read head is moved radially inward one track and then there is further delay of almost one complete revolution of disk  100  until file B passes beneath the read head and is scanned. Next, the read head is moved in one track and there is a further delay of almost a complete revolution of disk  100  before file C is scanned. Next, the read head is moved to the outermost track of disk  100 . Then, there is a delay of almost an entire revolution of disk  100  before file D is scanned. It will be appreciated that during this reading procedure, there are significant delays incurred by repositioning the read head to the various tracks of disk  100  and also delays due to waiting for the relevant portion of the disk to revolve beneath the read head after the latter has been positioned to the correct track. The invention can significantly reduce the occurrence of such read delays.  
         [0026]    The computer system  200  of FIG. 2 contains a hard drive  210  containing the disk  100  of FIG. 1. The computer system  200  has a reader  212  for reading information from the hard disk  210  and a writer  214  for writing information retrieved by reader  212  onto a tape drive  216  for back-up purposes. The computer system  200  contains a file directory  218  which lists the files contained in hard drive  210 .  
         [0027]    The computer system  200  also contains a sorter  220 . When the computer system  200  is instructed to back-up the files contained on the disk of hard disk drive  210  to tape drive  216 , the sorter  220  obtains from the file directory  218  the list of files stored on disk  100  of the hard drive  210 . The sorter  220  reorders the received list of files into the order in which the files are physically located on the disk  100 . That is, the sorter ranks the files according to their distance from the beginning (i.e. the first sector) of the disk. The sorter  220  passes the reordered list to reader  212  which retrieves the files from hard drive  210  in the order specified by the reordered list. The retrieved files are then passed to writer  214  which records them on tape drive  216 .  
         [0028]    The reordered file list provided by sorter  220  gives the files in the order in which they are to be found on the disk  100 . The sequence of the sectors on disk  100  begins with a nominated sector on the outermost track and proceeds anti-clockwise around the entire track. The sequence continues with the next track in and proceeds around that track in an anti-clockwise manner similar to that for the first track. The sequence continues from track to track in this way until the final sector is reached on the innermost track.  
         [0029]    If one assumes that the sector containing file Y is the first sector on the disk then, proceeding around the outermost track in anti-clockwise direction, the following file is X which is in the adjacent sector in the anti-clockwise direction. The read sequence proceeds around the track concluding with the last three sectors containing files Z, D and A respectively. The read head is then stepped inwardly one track and the new track is read in the same manner as the outermost track. Reading continues at the sector containing file G and proceeds anti-clockwise to the sector containing H and so on around the track until the reading of the track is completed with the reading of the three sectors containing files E, F and B respectively. The read head is then stepped inwardly one track and reading begins again at the sector containing file N and then proceeds in the anti-clockwise direction to read the file O and so on around the track in the anti-clockwise direction concluding with the reading of the sectors containing files L, M and C respectively.  
         [0030]    This completes the reading of the three tracks shown; in practice, the disk will contain many more tracks and the reading will continue track by track until all of the tracks have been read. In this example, the delays due to repositioning the head in the radial sense have been minimised and the delays due to rotating the disk in the direction R to find the relevant file have been eliminated, since every sector contains a file. In a real situation, there will, of course, be empty regions between files on a track (e.g. due to the deletion of files). However, modern file systems attempt to fit files into vacancies that appear on the disk which means that the empty regions will be small, of the order of 100KB. Modern disk drives usually have read-ahead cache of 2 to 4 MB in size, with the result that empty regions between files will normally be read into the read-ahead cache at the same time as the valid data preceding the empty region is read. Thus, an empty region can effectively be skipped over when the next piece of valid data is read from the disk.  
         [0031]    It will be appreciated that, due to the action of sorter  210 , the files are not read from the disk in alphabetical order but in order of their physical locations on the disk, i.e. Y, X . . . , Z, D, A, G, H . . . , E, F, B, N, O . . . , L, M, C . . . The order in which the files have been retrieved and written to the back-up storage is logged in order to facilitate swift recovery of files from the tape unit  216 . The reduction of the delays in the reading of data from disk  100  means that the tape drive  216  receives the back-up data at a rate high enough to prevent the tape drive  216  from pausing during writing of data to the tape. If tape drive  216  pauses, then it will switch off until the data steam resumes. By reducing the delays in reading data from the disk, the likelihood of the tape drive  216  switching off during back-up is reduced. This helps to shorten the back-up procedure since, if the tape drive  216  turns off then there is a significant delay whilst it starts up following a pause in the datastream from writer  214 .  
         [0032]    It is possible for disk  100  to contain fragmented files, i.e. files split between two or more sectors of the disk. Upon encountering a fragmented file, the sorter  100  includes the fragmented file in its reordered list by reference to the fragment containing the beginning of the fragmented file. This means that head repositioning required to locate the fragments of a fragmented file is reduced.  
         [0033]    If a disk contains many fragmented files, then it may be efficient to defragment the files on the disk prior to sorting them by order of their physical locations. This step is included in the flow chart of FIG. 3, which illustrates a back-up procedure according to an embodiment of the invention.  
         [0034]    At step  300 , the sorter  220  reads the list of files on the hard disk drive from the file directory  218 . At step  310  the sorter  220  determines the physical locations of the files on the disk, At step  312 , the sorter counts the number of fragmented files on the disk. At step  314 , the sorter determines whether more than 10% of the files on the disk are fragmented. If more than 10% of the files are fragmented, the sorter runs a defragmentation process at step  316  and then returns to step  310  to determine the physical positions of the files on the disk subsequent to the defragmentation operation. If at step  314  it is determined that less than 10% of the files on the disk are fragmented, the process moves to step  318 , where the sorter  220  reorders the files for retrieval in order of the sequence in which they are physically located on the disk. At step  320 , the files are read from the disk in the sorted order and, at step  322 , the retrieved files are written to the tape drive  216 .  
         [0035]    The files on the disk can be tagged to indicate which files on the disk  100  have changed since the last back-up to tape drive  216 . This provides the enhancement that only those files that have changed are then backed-up, thus reducing the time taken in the back-up process. Such an incremental back-up process cannot be done in a conventional image back-up arrangement.  
         [0036]    [0036]FIG. 4 illustrates the application of the invention to a storage area network, SAN  400 . The storage requirements of the servers  410  and  412  are met by SAN  400 , whose storage capacity is betokened by hard disk drive  210 . In FIG. 4, components carried over from FIG. 2 retain the same reference numerals and serve the same purposes. The operation of the back-up system of FIG. 4 is therefore to be understood by reference to the description of the FIG. 2 system, provided above.  
         [0037]    The invention is also compatible with the network data management protocol (NDMP). That is to say, the back-up process can be triggered by an NDMP command originating externally of the computer system  200  (or SAN  400 ) which causes the backing up of the files from the hard disk drive  210  to the tape drive  216  or to some other secondary storage device specified in the triggering command. The system may also report to the originator of the triggering command with the sequence of the files read from the hard disk drive  210 .