Data-aware cache state machine

• US 7,356,651 B2
• Filed: 01/31/2005
• Issued: 04/08/2008
• Est. Priority Date: 01/30/2004
• Status: Expired due to Fees

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Piurata Technologies LLC
• Inventors: Liu, Wei, Kahle, Steven H.
• Primary Examiner(s): Sparks, Donald
• Assistant Examiner(s): Mackall, Larry T
• Application Number:
  US11/047,433
• Publication Number:
  US 20050172082A1
• Time in Patent Office: 1,163 Days
• Field of Search: 711/118, 711/141, 711/138, 711/144, 711/145, 711/136, 711/142
• US Class Current: 711/144
• 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 12/127 using additional replacement algorithms
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch

Abstract

A method and system directed to improve effectiveness and efficiency of cache and data management by differentiating data based on certain attributes associated with the data and reducing the bottleneck to storage. The data-aware cache differentiates and manages data using a state machine having certain states. The data-aware cache may use data pattern and traffic statistics to retain frequently used data in cache longer by transitioning it into Sticky or StickyDirty states. The data-aware cache may also use content or application related attributes to differentiate and retain certain data in cache longer. Further, the data-aware cache may provide cache status and statistics information to a data-aware data flow manager, thus assisting data-aware data flow manager to determine which data to cache and which data to pipe directly through, or to switch cache policies dynamically, thus avoiding some of the overhead associated with caches. The data-aware cache may also place clean and dirty data in separate states, enabling more efficient cache mirroring and flush, thus improve system reliability and performance.

Claims

1. A method for controlling a cache, comprising:

managing each line or block of data in the cache by assigning each line or block of data to one of 7 or more states, wherein managing each line or block of data in the cache is performed by a cache state machine comprising 7 or more states and a collection of state transitions, wherein each cache state is associated with a control structure, and wherein each line is associated with a line control block comprising a set of line or block attributes;

utilizing a hash object to speed up cache line lookup;

enforcing a total maximum dirty line threshold;

collecting statistics for each line including read access count, write access count, and time since flush;

collecting statistics for the cache including cache hits, cache misses, and average access count; and

wherein the 7 states are defined as;

(1) Free—

the cache lines do not contain valid data yet;

(2) Clean—

the cache lines contain valid clean data (no flush needed);

(3) Dirty—

the cache lines contain valid dirty data (need flush sometime later);

(4) Sticky—

the cache lines contain valid clean data that has been accessed at least twice (e.g. two or more reads);

(5) StickyDirty—

the cache lines contain valid dirty data that has been accessed at least twice (e.g. 1 write, 1 or more reads;

or 2 or more writes, etc.);

(6) Flush—

the cache lines contain valid dirty data and are about to be written to a physical disk storage; and

(7) Hash—

the cache lines are in the process of getting valid data from either physical disk storage (read) or host (write).

2. The method of claim 1 wherein each state (except Hash) is treated as a separate virtual cache using a Least Recently Used “

LRU”

replacement algorithm.

3. The method of claim 2 wherein the combined states of Free and Clean have a minimum threshold which when exceeded triggers a request to flush to a Data Flow Manager and Flush Manager.

4. The method of claim 2 wherein the state Dirty has a maximum threshold which when exceeded triggers a request to flush to a Data Flow Manager and Flush Manager.

5. The method of claim 2 wherein the state Dirty may have a minimum threshold that reports to the data flow manager allowing it to stop flushing before the state is completely empty, and wherein the state StickyDirty has a maximum threshold which when exceeded triggers a transition of one or more lines of data to the Dirty state if that state is not already over its threshold in which case a request to flush is passed to a Data Flow Manager and Flush Manager.

6. The method of claim 2 wherein the state Sticky has a maximum threshold which when exceeded triggers a transition of one or more lines of data to the Clean state.

7. The method of claim 1 wherein the certain attributes for each line of data can be used as criteria for differentiating data and transitioning the lines of data into the Sticky or StickyDirty states, or Tag or TagDirty states.

8. The method of claim 1 wherein the statistics collected for each block or line of data can be used to trigger a flush request when one or more thresholds are met.

9. The method of claim 1 wherein the statistics collected for the cache pertaining to state thresholds and pending flush requests can be used by a data flow manager to decide to bypass the cache with data that would normally benefit from caching, alleviating “

read-induced-write”

, “

read-wait-write”

, “

write-induced-write” and

“

write-wait-write”

delays.

10. The method of claim 1 wherein the statistics collected for the cache pertaining to state thresholds can be used by a data flow manager to dynamically switch cache policies such as write back, write through, write allocate, write invalidate, alleviating “

write-induced-write” and

“

write-wait-write”

delays, or improve reliability.

11. The method of claim 1, wherein a Flush line can be transitioned to Free state or be retained in Clean state after the flush completion, based on the line'"'"'s Access Count attribute.

12. The method of claim 1, wherein a Dirty line can only exist in one of three states Flush state, Dirty state or StickyDirty state, each organized in LRU fashion.

13. The method of claim 12 further comprising a hierarchy of Flush/Dirty/StickyDirty states that maximize efficiency for managing cache flush pace and timing.

14. The method of claim 12 further comprising a separation of Clean lines from Dirty lines that improve the efficiency of cache mirroring by allowing a system to mirror only the Dirty lines for redundant cache coherency.

15. The method of claim 1 wherein a hash table is used to insert and search for data in cache.

16. The method of claim 15 further comprising a hash collision resolution list that is a doubly linked LRU list.

17. An apparatus, comprising:

a cache arranged to operate in accordance with 7 cache states, wherein the 7 states are defined as;

(1) Free—

cache lines do not contain valid data yet;

(2) Clean—

cache lines contain valid clean data (no flush needed);

(3) Dirty—

cache lines contain valid dirty data (need flush sometime later);

(4) Sticky—

cache lines contain valid clean data that has been accessed at least twice (e.g. two or more reads);

(5) StickyDirty—

cache lines contain valid dirty data that has been accessed at least twice (e.g. 1 write, 1 or more reads;

or 2 or more writes, etc.);

(6) Flush—

cache lines contain valid dirty data and are about to be written to a physical disk storage; and

(7) Hash—

cache lines are in the process of getting valid data from either the physical disk storage (read) or a host (write); and

an interface arranged to receive an access request associated with the cache and to communicate with the cache regarding the request.