Efficient data cache

• US 20050268044A1
• Filed: 06/01/2005
• Published: 12/01/2005
• Est. Priority Date: 06/01/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Arcas, Blaise Aguera y
• Granted Patent: US 7,546,419 B2
• Time in Patent Office: Days
• 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; 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 said initial compression ratio of said at least one cache object.

5. The method of claim 1 wherein said increasing comprises decreasing said initial 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 at least one of said cache objects other than a given one of said cache objects; and

increase an amount of data storage space occupied by said given 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 said given cache object by said given amount.

21. The apparatus of claim 18 wherein said decreasing comprises increasing said initial compression ratio of said at least one cache object.

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

23. The apparatus of claim 18 wherein said given 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 said at least one cache object.

25. The apparatus of claim 18 wherein said increasing comprises supplementing said stored data for said given 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 given 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 an initial condition;

if insufficient data storage space is present in said cache under said initial condition to store at least one new object in said cache, compressing at least one object in said cache to clear data storage space for said at least one new object; and

storing said at least one new object in said cache.

30. The method of claim 29 wherein said initial condition corresponds to said cache being empty.

31. The method of claim 30 further comprising continuing to store new objects in said cache without compressing said objects stored in said cache until insufficient data storage space remains in said cache to store any additional new object.

32. The method of claim 29 further comprising:

storing said at least one new object in said cache without said compressing, if sufficient space for storing said at least one new object is present in said cache under said initial condition.