METHOD AND SYSTEM FOR BINARY CACHE CLEANUP

• US 20110296122A1
• Filed: 05/31/2010
• Published: 12/01/2011
• Est. Priority Date: 05/31/2010
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: WU, William, Aslam, Ameen, Bennett, Alan, Gorobets, Sergei Anatolievich, Sprouse, Steven
• Granted Patent: US 9,235,530 B2
• Time in Patent Office: Days
• US Class Current: 711/156
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/121 using replacement algorithms

Abstract

A system and method for clearing data from a cache in a storage device is disclosed. The method may include analyzing the cache for the least recently fragmented logical group, and evicting the entries from the least recently fragmented logical group. Or, the method may also include analyzing compaction history and selecting entries for eviction based on the analysis of the compaction history. The method may also include scheduling of different eviction mechanisms during various operations of the storage device. The system may include a cache storage, a main storage and a controller configured to evict entries associated with a least recently fragmented logical group, configured to evict entries based on analysis of compaction history, or configured to schedule different eviction mechanisms during various operations of the storage device.

Claims

1. A method of evicting data from a cache storage to a main storage in a storage device, the cache storage storing a plurality of data associated with respective logical space indicators, the method comprising:

analyzing for a predetermined criterion less than all of the plurality of data stored in the cache that are associated with the respective logical space indicators;

selecting a logical space indicator, from the respective logical space indicators, associated with a portion of data satisfying the predetermined criterion; and

evicting at least some of the data in the cache storage that is associated with the selected logical space indicator.

2. The method of claim 1, wherein the logical space indicator comprises a logical group.

3. The method of claim 2, wherein the predetermined criterion comprises age.

4. The method of claim 2, wherein analyzing for a predetermined criterion less than all of the plurality of data stored in the cache that are associated with the respective logical space indicators consists of analyzing a single fragment for each of the respective logical space indicators.

5. The method of claim 2, wherein analyzing for a predetermined criterion comprises accessing time stamps of first fragment writes in at least a part of the cache storage for the respective logical groups;

and

wherein selecting at least one logical space indicator based on the analysis comprises selecting the logical group with an oldest time stamp.

6. A method of evicting data from a cache storage to a main storage in a storage device comprising:

analyzing at least a part of the cache storage for compaction history; and

evicting at least some of the data in the cache storage based on the analysis.

7. The method of claim 6, wherein analyzing at least a part of the cache storage for compaction history comprises determining the compaction history for at least one logical space indicator.

8. The method of claim 7, wherein the logical space indicator comprises a logical group;

and

wherein analyzing at least a part of the cache storage for the compaction history comprises analyzing the compaction history for a plurality of logical groups.

9. The method of claim 8, wherein analyzing the compaction history for a plurality of logical groups comprises determining compaction counts for the plurality of logical groups.

10. The method of claim 9, wherein analyzing at least a part of the cache storage for compaction comprises:

determining the logical groups that have been compacted more than a predetermined number of times; and

selecting a logical group from the logical groups that have been compacted more than the predetermined number of times.

11. The method of claim 9, wherein analyzing at least a part of the cache storage for compaction history comprises determining a logical group that has been compacted a greatest number of times in the at least a part of the cache storage;

and

wherein evicting at least some of the data in the cache storage based on the analysis comprises evicting at least some entries from the determined logical group that has been compacted the greatest number of times.

12. A method of evicting data from a cache storage to a main storage in a storage device comprising:

determining a phase of operation of the storage device;

selecting multiple cache eviction mechanisms in response to determining the phase of operation of the storage device; and

performing the multiple cache eviction mechanism during the phase of operation of the storage device.

13. The method of claim 12, wherein the phase of operation of the storage device is selected from the group consisting of host operation and idle operation.

14. The method of claim 13, wherein the selected multiple cache eviction mechanisms comprise a first cache eviction mechanism and a second cache eviction mechanism;

and

wherein performing the multiple cache eviction mechanism during the phase of operation of the storage device comprises alternating using the first cache eviction mechanism and the second cache eviction mechanism.

15. The method of claim 14, further comprising selecting a ratio for alternating in response to determining the phase of operation of the storage device;

and

wherein alternating using the first cache eviction mechanism and the second cache eviction mechanism comprises alternating using the first cache eviction mechanism and the second cache eviction mechanism in accordance with the selected ratio.

16. A storage device comprising:

a cache storage configured to receive data associated with host write commands and configured to store a plurality of data associated with respective logical space indicators;

a main storage in communication with the cache storage and configured to receive data transferred from the cache storage; and

a controller configured to;

analyze for a predetermined criterion less than all of the plurality of data stored in the cache that are associated with the respective logical space indicators;

select a logical space indicator, from the respective logical space indicators, associated with a portion of data satisfying the predetermined criterion; and

evict at least some of the data in the cache storage that is associated with the selected logical space indicator.

17. The storage device of claim 16, wherein the logical space indicator comprises a logical group.

18. The storage device of claim 17, wherein the predetermined criterion comprises age.

19. The storage device of claim 17, wherein the controller is configured to analyze a single fragment for each of the respective logical space indicators in order to select the logical group for eviction.

20. The storage device of claim 17, wherein the controller is configured to access time stamps of first fragment writes in at least a part of the cache storage for the respective logical groups;

and

wherein the controller is configured to select at least one logical space indicator based on the analysis comprises selecting the logical group with an oldest time stamp.

21. A storage device comprising:

a cache storage configured to receive data associated with host write commands;

a main storage in communication with the cache storage and configured to receive data transferred from the cache storage; and

a controller configured to;

analyze at least a part of the cache storage for compaction history; and

evict at least some of the data in the cache storage based on the analysis.

22. The storage device of claim 21, wherein the controller is configured to analyze at least a part of the cache storage for compaction history by determining the compaction history for at least one logical space indicator.

23. The storage device of claim 22, wherein the logical space indicator comprises a logical group;

and

wherein the controller is configured to analyze at least a part of the cache storage for the compaction history by analyzing the compaction history for a plurality of logical groups.

24. The storage device of claim 23, wherein the controller is configured to analyze the compaction history for a plurality of logical groups by determining compaction counts for the plurality of logical groups.

25. The storage device of claim 24, wherein the controller is configured to analyze at least a part of the cache storage for compaction by:

determining the logical groups that have been compacted more than a predetermined number of times; and

selecting a logical group from the logical groups that have been compacted more than the predetermined number of times.

26. The storage device of claim 24, wherein the controller is configured to analyze at least a part of the cache storage for compaction history by determining a logical group that has been compacted a greatest number of times in the at least a part of the cache storage;

and

wherein the controller is configured to evict at least some of the data in the cache storage based on the analysis by evicting at least some entries from the determined logical group that has been compacted the greatest number of times.

27. A storage device comprising:

a cache storage configured to receive data associated with host write commands;

a main storage in communication with the cache storage and configured to receive data transferred from the cache storage; and

a controller configured to;

determine a phase of operation of the storage device;

select multiple cache eviction mechanisms in response to determining the phase of operation of the storage device; and

perform the multiple cache eviction mechanism during the phase of operation of the storage device.

28. The storage device of claim 27, wherein the phase of operation of the storage device is selected from the group consisting of host operation and idle operation.

29. The storage device of claim 28, wherein the selected multiple cache eviction mechanisms comprise a first cache eviction mechanism and a second cache eviction mechanism;

and

wherein the controller is configured to perform the multiple cache eviction mechanism during the phase of operation of the storage device by alternating using the first cache eviction mechanism and the second cache eviction mechanism.

30. The storage device of claim 29, the controller is further configured to select a ratio for alternating in response to determining the phase of operation of the storage device;

and

wherein the controller is configured to alternate using the first cache eviction mechanism and the second cache eviction mechanism by alternating using the first cache eviction mechanism and the second cache eviction mechanism in accordance with the selected ratio.