DATA-AWARE CACHE STATE MACHINE

• US 20080172531A1
• Filed: 03/25/2008
• Published: 07/17/2008
• Est. Priority Date: 01/30/2004
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Plurata Technologies LLC
• Inventors: Liu, Wei, Kahle, Steven H.
• Granted Patent: US 7,725,661 B2
• Time in Patent Office: Days
• US Class Current: 711/135
• 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

Management of a Cache is provided by differentiating data base on attributes associated with the data and reducing storage bottlenecks. The Cache differentiates and manages data using a state machine with a plurality of states. the Cache may use data patterns and statistics to retain frequently used data in the cache longer. The Cache uses content or attributes to differentiate and retain data longer. Further, the Cache may provide status and statistics to a data flow manager that determines which data to cache and which data to pipe directly through, or to switch cache policies dynamically, thus avoiding some of the cache overhead. The Cache may also place clean and dirty data in separate states to enable more efficient Cache mirroring and flush.

Claims

1. A method for controlling a cache, comprising:

managing data in the cache by assigning at least one state to each portion of the cache data, wherein managing each portion of the cache data is enabled by a state machine comprising a plurality of states and a set of state transitions;

associating each of the plurality of states with a control structure;

associating each portion of the cache data with a set of attributes; and

enabling each of the plurality of states to be aware of the cache data, wherein each state includes at least one of;

a Free state where the cache data contains unvalidated data;

a Clean state where the cache data is valid and clean and no flush is required;

a Dirty state where the cache data is valid and dirty and a flush is required;

a Sticky state where the cache data is valid and clean and was accessed at least twice by at least one of a read operation or a write operation;

a StickyDirty state where the cache data contains valid dirty data that was accessed at least twice by at least one of a read operation or a write operation;

a Flush state where the cache data contains valid dirty data that is to be written to a storage device; and

a Hash state where the cache is in the process of getting valid data from at least one of the physical storage device or a host.

2. The method of claim 1, further comprising:

utilizing a hash object to speed up cache data lookup;

enforcing a total maximum dirty data threshold;

collecting statistics for each portion of cache data including at least one of a read access count, a write access count, and a time since last flush; and

collecting statistics for the cache, including at least one of a cache hit count, a cache miss count, and an average access count.

3. The method of claim 1 wherein at least one state is treated as a separate virtual cache employing a replacement process.

4. The method of claim 1 wherein the combined states of Free state and Clean state have a minimum threshold, and wherein if the minimum threshold is exceeded, providing a request to flush a least one of a Data Flow Manager and a Flush Manager.

5. The method of claim 1 wherein the Dirty state has a maximum threshold, and wherein if the maximum threshold is exceeded, providing a request to flush to at least one of a Data Flow Manager and a Flush Manager.

6. The method of claim 1, further comprising:

enabling the Dirty state to provide a minimum threshold that enables a Data Flow manager to stop flushing before the cache data is completely flushed; and

enabling the StickyDirty state to provide a maximum threshold, wherein if the maximum threshold is exceeded, enabling a transition of one or more portions of cache data to the Dirty state, and wherein if the StickyDirty state is over the maximum threshold, providing a request to flush to at least one of a Data Flow Manager and a Flush Manager.

7. The method of claim 1, further comprising providing a request to flush to at least one of a Data Flow Manager and a Flush Manager if a time delta is greater than a time threshold.

8. The method of claim 1 wherein the Sticky state has a maximum threshold, wherein if the maximum threshold is exceeded, enabling a transition of one or more portions of cache data to the Clean state.

9. A computer readable medium with data that enables management of a cache, wherein the execution of at least a portion of the data enables actions, comprising:

assigning at least one state to each portion of the cache data, wherein managing each portion of the cache data is enabled by a state machine comprising a plurality of states and a set of state transitions;

associating each of the plurality of states with a control structure;

associating each portion of the cache data with a set of attributes; and

enabling each of the plurality of states to be aware of the cache data, wherein each state includes at least one of;

a Free state where the cache data contains unvalidated data;

a Clean state where the cache data is valid and clean and no flush is required;

a Dirty state where the cache data is valid and dirty and a flush is required;

a Sticky state where the cache data is valid and clean and was accessed at least twice by at least one of a read operation or a write operation;

a StickyDirty state where the cache data contains valid dirty data that was accessed at least twice by at least one of a read operation or a write operation;

a Flush state where the cache data contains valid dirty data that is to be written to a storage device; and

a Hash state where the cache is in the process of getting valid data from at least one of the physical storage device or a host.

10. The computer readable medium of claim 9, wherein the execution of at least a portion of the data enables further actions, comprising:

utilizing a hash object to speed up cache data lookup;

enforcing a total maximum Dirty data threshold;

collecting statistics for each portion of cache data including at least one of a read access count, a write access count, and a time since last flush; and

collecting statistics for the cache, including at least one of a cache hit count, a cache miss count, and an average access count.

11. The computer readable medium of claim 9, wherein at least one state is treated as a separate virtual cache employing a replacement process.

12. The computer readable medium of claim 9, wherein the combined states of Free state and Clean state have a minimum threshold, and wherein if the minimum threshold is exceeded, providing a request to flush a least one of a Data Flow Manager and a Flush Manager.

13. The computer readable medium of claim 9 wherein the Dirty state has a maximum threshold, and wherein if the maximum threshold is exceeded, providing a request to flush to at least one of a Data Flow Manager and a Flush Manager.

14. The computer readable medium of claim 9, wherein the execution of at least the portion of the data enables further actions, including:

enabling the Dirty state to provide a minimum threshold that enables a Data Flow manager to stop flushing before the cache data is completely flushed; and

enabling the StickyDirty state to provide a maximum threshold, wherein if the maximum threshold is exceeded, enabling a transition of one or more portions of cache data to the Dirty state, and wherein if the StickyDirty state is over the maximum threshold, providing a request to flush to at least one of a Data Flow Manager and a Flush Manager.

15. The computer readable medium of claim 9, wherein the execution of at least the portion of the data enables providing a request to flush to at least one of a Data Flow Manager and a Flush Manager if a time delta is greater than a time threshold.

16. The computer readable medium of claim 9, wherein the Sticky state has a maximum threshold, wherein if the maximum threshold is exceeded, enabling a transition of one or more portions of cache data to the Clean state.

17. A system for managing a cache, comprising:

a server for receiving a request for data;

a data flow manager that processes the request, including;

enabling data in the cache to be assigned at least one state to each portion of the cache data, wherein each portion of the cache data is further enabled for use with a state machine comprising a plurality of states and a set of state transitions;

enabling association of each of the plurality of states with a control structure;

enabling association of each portion of the cache data with a set of attributes; and

enabling each of the plurality of states to be aware of the cache data, wherein each state includes at least one of;

a Free state where the cache data contains unvalidated data;

a Clean state where the cache data is valid and clean and no flush is required;

a Dirty state where the cache data is valid and dirty and a flush is required;

a Sticky state where the cache data is valid and clean and was accessed at least twice by at least one of a read operation or a write operation;

a StickyDirty state where the cache data contains valid dirty data that was accessed at least twice by at least one of a read operation or a write operation;

a Flush state where the cache data contains valid dirty data that is to be written to a storage device; and

a Hash state where the cache is in the process of getting valid data from at least one of the physical storage device or a host.

18. The system of claim 17, further comprising separating Clean cache data from Dirty cache data to enable mirroring of the Dirty cache data for redundant cache coherency.

19. The system of claim 17, fiuther comprising:

utilizing a hash object to speed up cache data lookup;

enforcing a total maximum Dirty data threshold;

collecting statistics for each portion of cache data including at least one of a read access count, a write access count, and a time since last flush; and

collecting statistics for the cache, including at least one of a cache hit count, a cache miss count, and an average access count.

20. The system of claim 17, wherein at least one state is treated as a separate virtual cache employing a replacement process.

21. The system of claim 17, wherein the data flow manager performs further actions, including:

providing a request to flush a least one of a Data Flow Manager and a Flush Manager if the combined Free state and Clean state have a minimum threshold that is exceeded; and

providing a request to flush to at least one of a Data Flow Manager and a Flush Manager if a maximum threshold for the Dirty state is exceeded,

22. The system of claim 17, wherein the data flow manager performs further actions, including:

enabling the Dirty state to provide a minimum threshold that enables a Data Flow manager to stop flushing before the cache data is completely flushed; and

enabling the StickyDirty state to provide a maximum threshold, wherein if the maximum threshold is exceeded, enabling a transition of one or more portions of cache data to the Dirty state, and wherein if the StickyDirty state is over the maximum threshold, providing a request to flush to at least one of a Data Flow Manager and a Flush Manager.

23. The system of claim 17, wherein the data flow manager enables further actions, including enabling a request to flush to be provided to at least one of the Data Flow Manager and a Flush Manager if a time delta is greater than a time threshold.

24. An apparatus for managing a cache, comprising:

a data flow manager that processes a request for data, including;

enabling data in the cache to be assigned at least one state to each portion of the cache data, wherein each portion of the cache data is further enabled for use with a state machine comprising a plurality of states and a set of state transitions;

enabling association of each of the plurality of states with a control structure;

enabling association of each portion of the cache data with a set of attributes; and

enabling each of the plurality of states to be aware of the cache data, wherein each state includes at least one of;

a Free state where the cache data contains unvalidated data;

a Clean state where the cache data is valid and clean and no flush is required;

a Dirty state where the cache data is valid and dirty and a flush is required;

a Sticky state where the cache data is valid and clean and was accessed at least twice by at least one of a read operation or a write operation;

a StickyDirty state where the cache data contains valid dirty data that was accessed at least twice by at least one of a read operation or a write operation;

a Flush state where the cache data contains valid dirty data that is to be written to a storage device; and

a Hash state where the cache is in the process of getting valid data from at least one of the physical storage device or a host.