Sequentially processing data in a cached data storage system

• US 4,882,642 A
• Filed: 07/02/1987
• Issued: 11/21/1989
• Est. Priority Date: 07/02/1987
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wagner, Robert E., Tayler, Gerald E.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Mills, John G.
• Application Number:
  US07/068,857
• Time in Patent Office: 873 Days
• Field of Search: 364/200, 364/900, 360/78.11, 360/78.12
• US Class Current: 360/78.11
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass
• CPC Class Codes: G06F 2212/312 In storage controller
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch

Abstract

The disclosure relates to sequential performance of a cached data storage subsystem with a minimal control signal processing. Sequential access is first detected by monitoring and examining the quantity of data accessed per unit of data storage (track) across a set of contiguously addressable tracks. Since the occupancy of the data in the cache is usually time limited, this examination provides an indication of the rate of sequential processing for a data set, i.e., a data set is being processed usually in contiguously addressable data storage units of a data storage system. Based upon the examination of a group of the tracks in a cache, the amount of data to be promoted to the cache from a backing store in anticipation of future host processor references is optimized. A promotion factor is calculated by combining the access extents monitored in the individual data storage areas and is expressed in a number of tracks units to be promoted. The examination of the group of tracks units and the implementation of the data promotion and demotion (early cast-out) is synchronized which results in a synergistic effect for increasing throughput of the cache for sequentially-processed data. A limit of promotion is determined to create a window of sequential data processing.

Claims

1. In a method of operating a cache which is interposed between a host processor and a backing store, the cache and the backing store including addressable like-capacity data storing tracks, where a track of data is the amount of data storable on one track of a magnetic disk recorder the cache including means for addressing tracks in the cache using addresses of the backing store whenever the cache tracks are individually allocated for storing data with respect to a respective addressable track in the backing store;

the steps of;

measuring and storing the measurement of those portions of each of said allocated tracks that are accessed by the host processor during the current allocation of the cache track to one of the tracks in the backing store;

selecting a group of the cache tracks that are addressable by contiguous ones of the backing store addresses;

establishing first and second access extent thresholds;

in each of the selected groups, comparing, as at first comparison, the stored measurement for one of the tracks in the selected group with said first access extent threshold, if the first comparison shows that the stored measurement for the one track is less than the first access extent threshold, operating the cache for said one cache track in a random access mode, if the first comparison shows that the one cache track stored measurement is greater than the first access extent threshold, then combining the stored measurements for all cache tracks in the group having the one cache track; and

comparing, as a second comparison, said combined stored measurement with said second access extent threshold, if said second comparison shows that the combined measurement exceeds said second access extent threshold, preparing the cache for cache bypass operations, if said second comparison shows that the combined measurement is not greater than said second access extent threshold, then establishing for tracks in the backing store having addresses contiguous with the backing store address of the one cache track a predetermined requested data promotion and demotion algorithm.

2. In the method set forth in claim 1, wherein said combining step includes summing the stored measurements for all of the tracks in the selected group;

establishing a look-ahead factor;

multiplying the sum with said look-ahead factor to obtain a promotion factor; and

promoting the data from a number of backing store tracks to the cache store having backing store addresses contiguous but increasingly greater than the backing store address of said one track.

3. In the method set forth in claim 2, further including the steps of:

maintaining a number of cache tracks in selected groups to be a constant number and including demoting tracks from the selected group to the backing store to accommodate the tracks promoted from the backing store to the cache store in accordance with said promotion factor.

4. In the method set forth in claim 3, further including the step of:

limiting the number of tracks in the selected group to be not greater than ten tracks.

5. In the method set forth in claim 4, further including the steps of:

establishing first and second addresses between which all data transfer operations are to occur with backing store addresses lying between said first and second addresses; and

promoting said tracks having increasingly greater contiguous addresses to the one track up to and including but not exceeding said second address.

6. In the method set forth in claim 5, further including the steps of:

demoting from said selected group and removing from said selected group tracks having lower backing store addresses within the selected group beginning with a backing store address equal to two less than the backing store address of the one track and ending with the backing store address which is equal to the promotion factor, in tracks, subtracted from said backing store address of the one track.

7. In the method set forth in claim 5, further including the steps of:

establishing a replacement procedure for all allocated cache tracks in the cache store, said replacement procedure including measuring the time of residency of the cache track since the last host processor access and removing by demoting data from the oldest cache resident tracks and deallocating the oldest cache resident tracks for freeing the oldest cache resident tracks for reallocation, such demotion procedure including the tracks within the selected groups.

8. In the method set forth in claim 5, further including the steps of:

including in said measuring step, the measurement of data transfers to identical portions of each of the allocated tracks such that multiple transfers to an identical portion add to said access extent for the given track; and

including measuring data transfers to and from the same portions of the respective allocated track such that multiple transfers which such same portions add to the access extent for the respective tracks in cache; and

measuring data transfers for accesses to the cache which are host explicit or implicit wherein the implicit transfers are data transfers from the backing store to the cache store and the explicit transfers are directly between the host processor and the cache store.

9. In the method set forth in claim 1, further including the steps of:

receiving from said host processor a commanded sequential mode of operation to promote data from the backing store to the cache store for accommodating a commanded sequential mode of operation; and

promoting data from the backing store to the cache store in accordance with said comparing step and repeating the measuring steps for all cache tracks related to and included in said commanded sequential mode of operation.

10. In the method set forth in claim 1, further including the steps of:

receiving from said host processor a commanded sequential mode of operation for identified backing store addressed tracks;

establishing a commanded sequential bit and an implicit sequential bit, setting the commanded sequential bit upon receiving the received commanded sequential mode for those tracks identified and setting the implicit sequential bit as a result of said comparing step indicating a sequential mode;

promoting data from the backing store to the cache store in accordance with said commanded sequential mode using a process unique to the commanded sequential mode and different from the implicit sequential mode; and

executing said measuring step for the tracks included within said commanded sequential mode.

11. In the method set forth in claim 1, further including the steps of:

establishing for all cache tracks allocated for backing store tracks a cache replacement algorithm wherein data stored in allocated ones of the cache tracks are demoted to the backing store and such demoted tracks are then deallocated from the cache; and

applying said replacement procedure to all tracks in the cache irrespective of the mode of operation thereof.

12. In the method set forth in claim 1, further including the steps of:

establishing for all tracks in the cache a replacement procedure for demoting data from the allocated tracks and deallocating the tracks storing the data, said procedure including determining the elapsed time since the last host processor access to the respective allocated track and replacing those tracks having the longest elapsed time since a last host access;

a command bit for indicating a commanded sequential mode of operation;

an implicit bit for indicating an implicit sequential mode of operation;

receiving a command from the host processor for commanding a sequential mode of operation and setting said command bit, in response to a set command bit promoting data from the backing store to the cache store in accordance with a predetermined promotion algorithm different from the promotion of data from the backing store to the cache store resulting from the comparing step; and

when said comparing step indicates that the combined measurement is greater than the first threshold and less than the second threshold, setting said implicit bit, then promoting data from the backing store to the cache store when the implicit bit is set in accordance with the algorithm set forth for the comparing step irrespective of whether or not a comparing step was executed; and

establishing a bypass bit;

setting a bypass bit whenever said comparison indicates the combined measurement is greater than the second threshold for said one track.

13. In a method of operating a cache store connected to and electrically interposed between a using unit and a backing store, the cache store having a large plurality of addressable data storing tracks, where a track of data is the amount of data storable on one track of a magnetic disk recorder, each of the tracks having a predetermined data storing capacity;

said using unit accessing the data storing tracks for reading data stored therein and for writing data therein;

the machine-executed steps of;

monitoring the accessing of the data storing tracks by the using unit including identifying which of the data storing tracks are accessed and the extent of each such access;

separately summing for each of the data storing tracks the monitored access extents and separately storing the sums as current access extents for the respective data storing tracks;

for each of the data storing tracks, establishing an access threshold which if exceeded indicates a possible sequential mode of using unit access to data stored in data storing tracks having addresses within a locality of references, establishing a locality of references for each of the data storing tracks as a predetermined range of contiguous addresses for data storing tracks which range includes the address of said each respective data storing track;

after each attempted access to each of said data storing tracks, defining such data storing track as a current track for purposes of comparing predetermined current access extents with predetermined access thresholds;

comparing the current access extent for the current track with said access threshold, whenever the current access extent exceeds said access threshold for the current track, determining said locality of references for the current track, then comparing the respective current access extent of each data storing track in cache within said locality of references for the current track, if all of the addresses of data storing tracks within said locality of references for the current track are in fact in cache and if the respective current access extents for each of the data storing tracks in said locality of references respectively exceed the respective access threshold for such data storing tracks, then indicating that the using unit is sequentially accessing data stored in the data storing tracks within said locality of references of the current track; and

summing the current access extents for the data storing tracks within said locality of references and using the current access extent sum to indicate a rate of sequential access by the using unit within said locality of references of the current track.

14. In the method set forth in claim 13, further including the steps of:

transferring data between the cache store, the backing store and a using unit in a series of equal sized records, identifying the records;

in said monitoring step, measuring the extent of each such access by counting the equal sized records transferred between the using unit and the cache store and summing the number of records transferred for indicating the extent of such each access and including summing the sum of each access for generating the current access extents and storing size of the record with the respective current access extent.

15. In the method set forth in claim 13, further including the steps of:

transferring data in constant size records each having a predetermined number of bytes of data between the using unit and both the said stores;

in said monitoring step, monitoring the accessing and measuring the extent by counting the number of records transferred between the using unit and the cache store irrespective of the portion of the data storing track in the cache store that receives or yields the record being transferred such that a plurality of transfers of a single record adds to the current access extent for the data storing track and cache with which transfers.

16. In the method set forth in claim 13, further including the steps of:

in said monitoring step, for each attempted access by the using unit to the cache store, monitoring the access including each access wherein the cache store has an allocated data storing track for the attempted access whether recording or reading; and

wherein the attempted access includes wherein the cache store has no allocated data storing track for the attempted access, then transferring data from the backing store directly to the using unit and placing a coy into the cache store after allocating a track thereto, upon completion of the transfer from the backing store to the cache store and using unit, performing said comparing step.

17. In the method set forth in claim 13, further including the steps of:

after performing the comparing step, but before performing the indicating step;

summing the current access extents for all of the tracks within the locality of references to create a rate access indicator, calculating a number of tracks to be promoted having backing store addresses contiguous but increasingly greater than the largest backing store address within the locality of references by taking the rate access indicator and multiplying the same by an arbitrary and predetermined constant for obtaining a number of bytes to be prefetched into the cache store, dividing the number of prefetch bytes by the capacity of the data storing tracks to obtain a number of tracks to be promoted into the cache store; and

then performing said indicating step.

18. In the method set forth in claim 17, further including the steps of:

taking the number of the tracks to be promoted, subtracting one from that number and then demoting from the cache store to the backing store tracks within the locality of references beginning with the track having a backing store address two less than the largest backing store address track in the locality of references and proceeding to cache tracks accessible by increasingly smaller addresses within the locality of references; and

adding the prefetched tracks to the locality of references such that the number of tracks within the locality of references is a function of the calculated rate access indicator.

19. In the method set forth in claim 18, further including the steps of:

receiving from the using unit a command indicating a defined extent of operations for transfer of said constant size records having a lower backing store address equal to a first address and a maximum backing store address equal to a second address; and

limiting the prefetching and demotion of cache tracks respectively to be numerically between the second and first addresses.