Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-05-13
2001-07-10
Bragdon, Reginald G. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S133000, C711S137000, C711S136000, C711S156000
Reexamination Certificate
active
06260115
ABSTRACT:
TECHNICAL FIELD
The present invention relates to the field of sequential detection and track prestaging methods in a disk storage system.
BACKGROUND ART
The pattern of access requests by a host processor to a specific logical volume of a storage device in a cached disk storage system may contain a mixture of random and sequential patterns during any given time frame. This mixture may be caused by changes in the access request patterns presented by the host applications, and by the presence of multiple data sets on a given logical volume of a storage device. Storage management software programs, such as the System Managed Storage program, can complicate the mixture even more by changing the placement of multiple data sets on any given volume over time. Disk storage locations for a mainframe host can be logically described by its logical device, cylinder, track and record address. Other systems may use Logical Block Addresses (LBA). Sequential patterns or streams occur when the host application accesses these locations in increasing address sequences such as increasing cylinder, track or record number or increasing LBA. Any reference to sequential detection using cylinder, track or record number, and references to prestaging tracks into cache can be easily extended by one skilled in the art to apply to sequential detection for LBA addressing and prestaging appropriate LBAs into cache.
Modern storage subsystems frequently employ one or more levels of mapping of logical disk addresses as presented and referenced by the host to physical storage locations in the storage subsystem such as cache memory locations and/or physical disk locations. For example it is very common to map Count, Key and Data (CKD) addressing for a large number of logical devices from mainframe hosts to LBA addressing on a much smaller number of physical disk drives. The invention described here is largely independent of the mapping schemes employed. Unless otherwise stated, the sequential detection schemes described are in reference to the host view of data addresses. The mapping or translation of these addresses into physical addresses on the actual hard disk drives that store data, even for the purpose of prestaging the desired data into cache memory, is carried out by methods outside the scope of this invention.
Performance of cached disk storage systems is improved by prestaging tracks or logical blocks from the storage devices into cache memory when sequential access request patterns occur. Host sequential patterns are sometimes also referred to as sequential streams. Host programs which access tracks or logical blocks in sequential order may set special flags in the sequence of commands presented to the storage subsystem to provide explicit sequential access hints. The storage subsystem may also recognize particular command sequences which result from executing programs which access data in sequential order. These command sequences provide implicit hints of sequential access, referred to later as prestaging hints. Alternatively the subsystem may detect the sequential nature of a group of access requests. Sequential patterns may occur concurrently with other sequential requests or with otherwise independent or random access requests on a given logical volume. When a sequential pattern is detected, either due to hints or due to software detection of the sequential nature of access patterns, one or more tracks or LBAs are prestaged into the cache memory in anticipation of a subsequent access request. The intent is to change what would otherwise be a cache miss into a cache hit which reduces the service time as seen by the host processor. In order to increase the probability of having a track in cache by the time the host accesses that track, prestaging processes should prestage some number of tracks ahead of the current access and then maintain prestaging a sufficient number of tracks ahead of the host access to allow time for the tracks to be staged from disk. The number of tracks ahead of the current access will be referred to as the prestage factor. The prestage factor may vary for different scenarios such as different sequential hints, different command types or recent history of sequential patterns that indicate that sequential access is likely to continue. Effective prestaging methods must coordinate the use of sequential hints presented directly by the host processors, implied hints contained in the channel programs, and sequential detection methods where no hints are present. Effective prestaging methods must also record which tracks have already been prestaged to avoid requesting the prestaging of the same tracks multiple times which would waste valuable storage subsystem processing cycles and possibly even back-end bandwidth. It is desirable to only prestage those additional tracks necessary to maintain a desired prestage factor ahead of the current host access.
Simple sequential detection methods compare the address of the requested track with the just previously accessed track for a given volume or device. This approach works well for single streams of access requests, but fails to maintain sequential detection and prestaging when multiple sequential streams are executed concurrently for the same logical device, or when one or more sequential streams execute concurrently with random access requests on that logical device. Multiple concurrent streams of access frequently occur as a result of multiple applications accessing the same logical volume. One approach to solving this problem is to record information in the logical track directory entries of each logical storage device. This information would indicate which tracks are part of a sequential pattern and which tracks have been prestaged. However, in a disk storage system with a large number of possible directory entries, it is expensive to keep a directory entry for every possible track in a fast access type memory to allow the rapid checking of prior track directory entries for sequential detection, making this approach impractical.
DISCLOSURE OF INVENTION
The present invention is a method for detecting and remembering multiple sequential access patterns made from a host to a memory system having one or more logical storage devices. Once a sequential access pattern is detected, one or more tracks are requested to be prestaged ahead of the current access request. One list, having multiple entries, is provided for each logical storage device. The list is logically divided into two parts. One part, the sequential part, contains entries for access streams which the system has determined are sequential and for which the system may have prestaged one or more tracks into cache. A second part of the list, the candidate part, contains information about recent host accesses which have not as yet been determined to be sequential. These typically either have not included host sequential hints or have not been recognized as sequential patterns by meeting certain sequential pattern criteria. The entries within each of the two parts of the list are logically ordered in a Most Recently Used (MRU) fashion. The division between the two parts of the list is allowed to change so that although the total number of entries may be held constant, the proportion of the entire list allocated to each of the two parts can be varied. An insertion point in the list defines the boundary between the two parts of the list. In order to ensure the ability to detect new sequential streams in the presence of otherwise random accesses, the insertion point is maintained to always keep a minimum amount of storage available in the list for candidate entries.
MRU lists themselves are well known in the prior art. A MRU list has implied order with the most recent list entry at the logical head or top of the list, the oldest entry at the logical bottom or tail of the list and the intervening entries maintained in logical order. The order of entries can be maintained physically by rearranging the stored information in memory although this is very inefficient. The order is usually mainta
O'Brien John Timothy
Permut Alan R.
Radebaugh Keith Allen
Vandenbergh Hendrikus Everhardus
Bragdon Reginald G.
Brooks & Kushman P.C.
Chace Christian P.
Storage Technology Corporation
LandOfFree
Sequential detection and prestaging methods for a disk... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Sequential detection and prestaging methods for a disk..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sequential detection and prestaging methods for a disk... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2473727