Method and a system for determining an appropriate amount of data to cache

• US 6,098,153 A
• Filed: 01/30/1998
• Issued: 08/01/2000
• Est. Priority Date: 01/30/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Selkirk, Stephen Sid, Fuld, Stephen Tracy
• Primary Examiner(s): Gossage, Glenn
• Assistant Examiner(s): Chavoshi, Javad
• Application Number:
  US09/016,676
• Time in Patent Office: 914 Days
• Field of Search: 711/133, 711/134, 711/136, 711/137, 711/113, 712/239, 712/237, 712/238, 712/240
• US Class Current: 711/134
• 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 2212/6024 History based prefetching
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch

Abstract

A method and a system for determining how much data to cache, that is, optimizing disk caching control by selecting the optimal staging mode are disclosed. Specifically, the method and system of the present invention provides an analytical framework for determining how much data to cache thus producing a maximum hit rate and optimal utilization of computer system resources. The method and system in accordance with the present invention includes determining a history of referencing data on a disk and predicting an optimal staging mode from a plurality of staging modes based upon the history. The method and system of the present invention in the preferred embodiment allow staging in one of at least three modes: record staging, staging to the end of track, and full track staging. In using the history of data referencing to predict the optimal staging mode, the method and system of present invention provide a thorough analytical framework for determining which of the modes of staging data is most desirable in view of prior referencing patterns.

Claims

1. A method for determining an appropriate amount of data to stage in cache memory in a data processing comprising the steps of:

a) determining a history of data accessing and storage on a disk, the disk including a plurality of regions, each of the plurality of regions having at least one sub-region, wherein each of the plurality of regions is associated with a plurality of counters, each of the plurality of counters corresponding to one the plurality of staging modes, the step of determining a history further comprising the steps of;

a1) determining which one of the plurality of staging modes should have been used based upon a data reference type; and

a2) incrementing a counter, the counter being one of the plurality of counters associated with the region and corresponding to the one of the plurality of staging methods that should have been used;

b) maintaining within a cache directory a data structure for each of the plurality of sub regions, said data structure comprising;

b1) a data segment identifier of an originally referenced data segment; and

b2) a plurality of indicators;

wherein, a first indicators of the plurality of indicators is set when a current reference is to a data segment positioned in the sub-region after the originally referenced data segment, and a second indicator is set when a current reference is to a data segment positioned in the sub-region before the originally referenced data segment, for establishing the data reference type; and

c) predicting an optimal staging mode from a plurality of staging modes based upon the history.

2. The method of claim 1 wherein the staging mode determining step (a1) further comprises the steps of:

a1a) determining if the current reference is to an originally referenced record;

a1b) determining whether previous references were made only to the originally referenced record if the current reference is to the originally reference record; and

a1c) indicating that record staging should have been used if the previous references were made only to the originally referenced record.

3. The method of claim 1 wherein the staging mode determining step (a1) further comprises the steps of:

a1a) determining if the current reference is to a record positioned after an originally referenced record;

a1b) determining whether previous references were made to other records positioned within the sub-region after the originally referenced record if the current reference is to the record positioned after the originally referenced record; and

a1c) indicating that end of sub-region staging should have been used if the previous references were made to the other records positioned within the sub-region after the originally referenced record.

4. The method of claim 1 wherein the staging mode determining step (a1) further comprises the steps of:

a1a) determining if the current reference is to a record positioned within the sub-region before an originally referenced record; and

a1b) indicating that full sub-region staging should have been used if the current reference is to the record positioned within the sub-region before the originally referenced record.

5. The method of claim 1 wherein the staging mode determining step (a1) further comprises the steps of:

a1a) determining if the current reference is to an originally referenced record;

a1b) determining whether previous references were made to other records positioned within the sub-region before the originally referenced record if the current reference is to the originally referenced record; and

a1c) indicating that full sub-region staging should have been used if the previous references were made to the other records positioned within the sub-region before the originally referenced record.

6. The method of claim 1 wherein the staging mode determining step (a1) further comprises the steps of:

a1a) determining if the current reference is to a record positioned in the sub-region after an originally referenced record;

a1b) determining whether previous references were made to other records positioned within the sub-region before the originally referenced record if the current reference is to the record positioned in the sub-region after an originally referenced record; and

a1c) indicating that full sub-region staging should have been used if the previous references were made to the other records positioned within the sub-region before the originally referenced record.

7. The method of claim 1 wherein the incrementing step (a2) further comprises the step of down-scaling each of the plurality of counters if the counter is nearing an overflow after being incremented.

8. The method of claim 1, wherein the determining step (a) further comprises the steps of:

a3) detecting a sequentiality of data references;

a4) prompting a staging of the sub-region according to the staging policy for the region if the sequentiality has not been detected; and

a5) allowing the staging of the sub-region in its entirety if the sequentiality has been detected.

9. The method of claim 1 wherein the data segment further comprises a record.

10. The method of claim 9 wherein the predicting step c further comprises the steps of:

c1) determining if the sub-region is being deallocated;

c2) determining if there is a partial miss if the sub-region is not being deallocated.

11. The method of claim 10, wherein the predicting step further comprises the steps of:

c3) determining if the counter being incremented corresponds to the one of the plurality of staging modes which is being used if the partial miss occurred;

c4) adjusting the recommended staging mode to the optimal staging mode if either, the partial miss occurred and the counter does not correspond to the one of the plurality of staging modes which is being used, or the sub-region is being deallocated.

12. The method of claim 11, wherein the adjusting step c4) further comprises the steps of

c4a) calculating a plurality of values based upon the history of data references for the region, wherein each of the plurality of values corresponds to one of the plurality of staging modes;

c4b) selecting an optimal staging mode which corresponds to one of the plurality of values from among the plurality of staging modes; and

c4c) setting a staging policy for the region to equal the optimal staging mode.

13. The method of claim 12, wherein each of the plurality of values comprises a number, the number being a signed integer.

14. The method of claim 13, wherein one of the plurality of values having a most positive number among the plurality of values corresponds to the optimal staging mode.

15. The method of claim 14, wherein the calculating step (c4a) further calculates three values, V_R, V_E, and V_F, wherein