Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1997-12-10
2002-02-19
Bragdon, Reginald G. (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S158000, C711S202000
Reexamination Certificate
active
06349356
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates in general to a file retrieval system, and in particular, to a file retrieval system including a host-available device block map for optimally retrieving one or more blocks of data from a serpentine tape drive.
2. Description of Related Art
As computer technology develops, data storage systems have become more sophisticated and require the storage and retrieval of greater amounts of data. Even though disk-based storage systems have evolved significantly, such storage systems still have problems in terms of both cost and scalability.
The use of tape-based storage systems for data processing, backup, and/or archival purposes is well known in the art. For example, tape storage systems have traditionally been applied to sequential processing such as batch updating of master files. Tape storage systems also are used in data mining applications where thousands of queries are aggregated in one complete sequential scan of the data.
Advances in magnetic tape storage technology and devices have led to greatly increased capacity per cartridge. With the increase in capacity and new applications, there is a concomitant increase in the number of objects that may be stored per cartridge. indeed, the use of tape storage systems can be as much as two orders of magnitude more efficient than disk storage systems, in terms of cost per byte recorded and the number of bytes stored per unit (cartridge, etc.). However, one problem with tape storage systems is that the random access latency of tape is several orders of magnitude slower than disk storage systems.
New longitudinal tape formats such as IBM 3570 and IBM 3590 drives employ a tape track format described as serpentine longitudinal. These formats differ from previous IBM 3480/3490 drives in one regard by having higher track densities, thereby resulting in multiple tape passes in both the “out” and “in” directions.
In contrast, 18 track IBM 3480 drives write data only in the out direction and 36 track IBM 3490 drives write one set of tracks “out” and one set of tracks “in”. Optimized retrieval sequences for these devices comprise straightforward sequential ordering with no requirement for specialized ordering.
With IBM 3570 and IBM 3590 drives, however, there are 16 “out” and “in” tracks and 4 “out” and “in” tracks, respectively. Access to these tracks is accomplished by indexing the heads of the drive, a process that is very rapid as compared to searching the length of tape media.
In general, a serpentine longitudinal tape drive records data on a wrap (i.e., track) or a group of wraps in one direction along a length of the serpentine longitudinal tape media. Then, the tape drive reverses the recording direction and shifts its recording heads sideways a small distance to record another wrap or group of wraps in the opposite direction along the length of the tape. The tape drive continues these operations back and forth along the serpentine longitudinal tape media until all of the blocks of data are written.
Alternatively, instead of shifting its heads sideways a small distance to record another wrap or group of wraps, the serpentine longitudinal tape drive may electronically select another recording head or group of recording heads and move up the length of the tape media and continue back and forth until all of the blocks of data are written to the tape media. It will be appreciated, of course, that other types of recording techniques can be used as well.
As a result, a straightforward sequential retrieval order for serpentine longitudinal tape drives is most likely not optimized. The sequential retrieval order usually bears no relationship to the physical location of the blocks of data stored on serpentine tape media. Accordingly, the random retrieval of the blocks of data which are spaced apart on the serpentine tape can cause a significant latency. Indeed, for serpentine tape, the random retrieval of blocks of data spaced relatively far apart on the tape will likely result in grossly sub-optimal performance, if the blocks of data are retrieved in sequential order with respect to the order they were written.
Various techniques and systems for recording data on and retrieving data from a tape and for reducing access latency are known in the art. For example, the publication by Bruce K. Hillyer and Avi Silberschatz, entitled “Random I/O Scheduling in Online Tertiary Storage Systems” , ACM Conference, 1996, describes techniques for I/O scheduling for tape drives to resolve the problem of access latency. U.S. Pat. No. 5,485,321 issued to Leonhardt et al. entitled “Format and Method for Recording Optimization” discloses a serpentine recording technique for reducing access time. U.S. Pat. No. 5,373,485 issued to hogan et al. entitled “Method for Locating Data in a Data Cartridge System” discloses a physical and logical block search for data on a serpentine pattern which eliminates search time. U.S. Pat. No. 5,121,270 issued to Alcudia et al. entitled “Multitransducer Head Positioning Servo for Use in a Bi-directional Magnetic Tape System” discloses a serpentine recording mode of operation. U.S. Pat. No. 4,858,039 issued to Mintzlaff entitled “Streaming Tape Drive With Direct Block Addressability” discloses reducing the time for retrieving a selected block of data recorded in a serpentine fashion. U.S. Pat. No. 4,796,20 issued to Glass et al. entitled “System and Method for Encoding and Storing Digital Information on Magnetic Tape” discloses a system for increasing the speed of serpentine tape writes and reads. Japanese publication JP 8-235775 (English abstract only) discloses a device for access to linear serpentine tape. Japanese publication JP 7-24443 (English abstract only) discloses shortening the access time to a file stored in a magnetic tape of a serpentine track system.
However, none of these patents or publications provide a completely satisfactory solution to the above mentioned problems in retrieving files stored on serpentine longitudinal tape media. It should thus be apparent that a need exists for methods for optimized file retrieval from serpentine longitudinal tape media.
SUMMARY OF THE INVENTION
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a method, apparatus, and article of manufacture for optimizing the retrieval of blocks of data from a serpentine longitudinal tape media. A device block map (DBM) is stored on the tape media, wherein the DBM comprises a table having one or more rows and one or more columns for each block of data stored on the tape media. The columns are selected from a group comprising a wrap column, a position column, a logical block number column, and a file identifier column wherein the wrap column indicates a track where the block of data is recorded on the tape media, the position column indicates a physical position where the block of data is recorded on the tape media, the logical block number column indicates a logical block number for the block of data, and a file identifier column indicates a logical file identifier for the block of data. One or more retrieval paths for the blocks of data are determined from the device block map, wherein each of the retrieval paths comprises an ordered sequence of the blocks of data and the manner in which the tape media is to be traversed to accomplish the retrieval of the ordered sequence. A sum of distances is determined for each of the retrieval paths and an optimal one of the retrieval paths is selected based on the determined sum of distances. Thereafter, the blocks of data are retrieved from the tape media using the optimal retrieval path.
One advantage of the present invention is that it provides a significant improvement in the latency of random access to files stored on a serpentine longitudinal tape media. Another advantage is that the present invention provides a portable device block map which is accessible
Basham Robert Beverley
Fry Scott Milton
Gniewek John James
Johnson Steven Douglas
Wilson Steven Bennett
Bragdon Reginald G.
Konrad Raynes & Victor & Mann LLP
Victor David W.
LandOfFree
Host-available device block map for optimized file retrieval... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Host-available device block map for optimized file retrieval..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Host-available device block map for optimized file retrieval... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2977362