Efficient data cache

• US 7,546,419 B2
• Filed: 06/01/2005
• Issued: 06/09/2009
• Est. Priority Date: 06/01/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Aguera y Arcas, Blaise
• Primary Examiner(s): Ellis; Kevin L
• Assistant Examiner(s): Bertram; Ryan
• Application Number:
  US11/141,958
• Publication Number:
  US 20050268044A1
• Time in Patent Office: 1,469 Days
• Field of Search: 711/133
• US Class Current: 711/133
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 12/0886 Variable-length word access
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 12/127 using additional replacement algorithms
• CPC Class Codes: G06F 2212/401 Compressed data

Abstract

A method is disclosed which may include providing a cache in a computing system having an initial group of cache objects, the cache object having an initial compression ratio and including stored data; decreasing an amount of data storage space in the cache occupied by at least one of the cache objects other than a given one of the cache objects; and increasing an amount of data storage space in the cache occupied by the given cache object.

Claims

1. A method, comprising:

providing a cache in a computing system having an initial group of cache objects, each said cache object having an initial compression ratio and including stored data;

decreasing an amount of data storage space occupied by at least one of said cache objects other than a given one of said cache objects, wherein the amount of data storage space occupied by the at least one of said cache objects is progressively decreased based on a decreasing likelihood of need for the at least one of said cache objects, wherein the data storage space is progressively decreased by compressing the at least one of said cache objects utilizing at least two different compression ratios, such that each compression ratio results in a compression of the at least one of said cache objects; and

increasing an amount of data storage space occupied by said given cache object.

2. The method of claim 1 wherein said decreasing comprises decreasing said amount of data storage space by a given amount.

3. The method of claim 2 wherein said increasing comprises increasing said amount of data storage space occupied by said given cache object by said given amount.

4. The method of claim 1 wherein said decreasing comprises increasing from a first compression ratio to a second compression ratio of said at least one cache object.

5. The method of claim 1 wherein said increasing comprises decreasing from a second compression ratio to a first compression ratio of said given cache object.

6. The method of claim 1 wherein said given cache object is a most recently used cache object of said cache objects.

7. The method of claim 1 wherein said at least one cache object undergoing said decreasing step comprises a least recently used cache object of said cache objects.

8. The method of claim 1 wherein said decreasing comprises:

removing a portion of the stored data for said at least one cache object.

9. The method of claim 1 wherein said increasing comprises supplementing said stored data for said given cache object.

10. The method of claim 1 wherein an amount of data storage space available for each of said cache objects may equal one of a finite number of discrete values.

11. The method of claim 1 wherein said decreasing comprises reducing said amount of data storage space for at least one randomly selected cache object of said cache objects, other than said given cache object.

12. The method of claim 11 wherein said reducing comprises reducing said amount of data storage space for said at least one randomly selected cache object to a randomly determined extent.

13. The method of claim 11 wherein said randomly selected cache object is selected using one of a random method and pseudorandom method.

14. The method of claim 11 wherein said selection of said randomly selected cache object is guided by a heuristic.

15. The method of claim 1 further comprising:

storing said given cache object in a losslessly compressed form after said increasing.

16. The method of claim 1 further comprising:

storing said given cache object in uncompressed form after said increasing.

17. The method of claim 1 wherein said decreasing comprises removing at least one of said cache objects other than said given cache object.

18. An apparatus, comprising:

a computing system having at least one processor capable of operative communication with a main memory; and

a cache in said computing system having an initial group of cache objects, each said cache object having an initial compression ratio and including stored data;

wherein said computing system is operable to;

decrease an amount of data storage space occupied by a first cache object of the initial group of cache objects, wherein the amount of data storage space occupied by the first cache object is progressively decreased based on a decreasing likelihood of need for the first cache object, wherein the amount of data storage space occupied by the first cache object is progressively decreased in at least three increments, wherein each increment corresponds to a new determination of a decreased likelihood of need for the first cache object; and

increase an amount of data storage space occupied by a second cache object.

19. The apparatus of claim 18 wherein said decreasing comprises decreasing said amount of data storage space by a given amount.

20. The apparatus of claim 19 wherein said increasing comprises increasing said amount of data storage space occupied by the second cache object by said given amount.

21. The apparatus of claim 18 wherein said decreasing comprises increasing from an initial ratio to a subsequent ratio for the first object.

22. The apparatus of claim 18 wherein said increasing comprises decreasing an initial compression ratio of said second cache object.

23. The apparatus of claim 18 wherein said second cache object is a most recently used cache object of said cache objects.

24. The apparatus of claim 18 wherein said decreasing comprises removing a portion of the stored data for the first cache object.

25. The apparatus of claim 18 wherein said increasing comprises supplementing said stored data for said second cache object.

26. The apparatus of claim 18 wherein an amount of data storage space available for each of said cache objects may equal one of a finite number of discrete values.

27. The apparatus of claim 18 wherein said decreasing comprises reducing said amount of data storage space for at least one randomly selected cache object of said cache objects, other than said second cache object.

28. The apparatus of claim 27 wherein said reducing comprises reducing said amount of data storage space for said at least one randomly selected cache object to a randomly determined extent.

29. A method, comprising:

providing a cache in a computing system, said cache having a second object, wherein the second object is at a first size;

making a first determination that an insufficient amount of data storage space is present in said cache for a first object;

compressing the second object in said cache to clear data storage space for the first object, wherein the second object is compressed to a second size that is smaller than the first size based on a decreasing recency of use or access of the second object;

making a second determination that an insufficient amount of data storage is present in said cache; and

compressing the second object in said cache, wherein the second object is compressed to a third size that is smaller than the second size based on a decreasing recency of use or access of the second object.

30. The method of claim 29 wherein said first object is a new object to said cache or an existing object in said cache.

31. The method of claim 30 further comprising determining the second object has a decreasing recency of use or decreasing level of access.

32. The method of claim 29 further comprising storing said first object in said cache without compressing said first object.