System and method for adaptive data caching

• US 20020087798A1
• Filed: 02/08/2001
• Published: 07/04/2002
• Est. Priority Date: 11/15/2000
• Status: Abandoned Application

• Current Assignee: Sunstone Components LLC (Intellectual Ventures LLC), MEC Management, LLC (Three Affiliated Tribes of the Fort Berthold Reservation, North Dakota)
• Original Assignee: MEC Management, LLC (Three Affiliated Tribes of the Fort Berthold Reservation, North Dakota)
• Inventors: Conley, Paul Alan, Smith, Erik Richard, Perincherry, Vijayakumar
• Application Number:
  US09/778,716
• Publication Number:
  US 20020087798A1
• Time in Patent Office: Days
• US Class Current: 711/133
• CPC Class Codes: G06F 16/24552 Database cache management

Abstract

A system and method for selecting database objects to be stored in a cache based on the cache-worthiness of the objects. The technique collects cache-worthiness data for a plurality of objects in a database, determines a cache-worthiness value using the collected data for each of the plurality of objects, and selects one or more of the plurality of objects to be stored in the cache, wherein the objects are selected using the values.

Claims

1. In a database system wherein objects are stored in a database, a method for selecting one or more of the objects to be stored in a cache, comprising:

(a) collecting cache-worthiness data for a plurality of objects in the database;

(b) determining a cache-worthiness value for each of said plurality of objects using said cache-worthiness data; and

(d) selecting one or more of said plurality of objects to be stored in the cache, wherein the objects are selected using said cache-worthiness values.

2. The method of claim 1, wherein said cache-worthiness data comprises requests for one or more of said plurality of objects.

3. The method of claim 2, wherein said determining comprises adding an increment to those values corresponding to said requests.

4. The method of claim 3, wherein said increment is given by:

η

*(1-c_i,t)

where η

is a first constant and c_i,t is the cache-worthiness value of object i at time t.

5. The method of claim 4, wherein said cache-worthiness data further comprises an indication that the number of requests for a first object has not satisfied a first threshold, wherein said first object is one of said plurality of objects.

6. The method of claim 5, wherein said determining further comprises subtracting said increment from the cache-worthiness value corresponding to said first object.

7. The method of claim 1, wherein said cache-worthiness data comprises central processing unit (CPU) utilization data.

8. The method of claim 7, wherein said determining comprises adjusting by an increment the cache-worthiness value of each object stored in the cache.

9. The method of claim 8, wherein said increment is given by:

ε

(1-c_i,t)

where ε

is indicative of the change in CPU utilization, and c_i,t is the cache-worthiness value of object i at time t.

10. The method of claim 7, wherein said CPU utilization data is indicative of a change in CPU utilization from a first time to a second time, said determining comprises adjusting the cache-worthiness value of a first one of said plurality of objects, and said first one of said plurality of objects is added to the cache between said first time and said second time.

11. The method of claim 7, wherein said CPU utilization data is indicative of a change in CPU utilization from a first time to a second time, said determining comprises adjusting the cache-worthiness value of a first one of said plurality of objects, and said first one of said plurality of objects is removed from the cache between said first time and said second time.

12. The method of claim 1, wherein said cache-worthiness data comprises central processing unit (CPU) utilization data and requests for one or more of said plurality of objects.

13. The method of claim 12, wherein said determining comprises:

(a) adjusting the cache-worthiness value corresponding to each of said requested objects by a first increment; and

(b) adjusting the cache-worthiness value of each object stored in the cache by a second increment, wherein said second increment is a function of said CPU utilization data.

14. The method of claim 1, wherein said one or more objects are selected to maximize total cache-worthiness subject to a constraint comprising the size of the cache.

15. The method of claim 1, wherein objects are selected from the group consisting of tables, columns, records, cells, and constraints.

16. The method of claim 1, wherein said determining reflects a decreasing marginal utility of cumulative cache-worthiness data.

17. The method of claim 1, further comprising initializing said cache-worthiness values.

18. The method of claim 17, wherein said initial cache-worthiness values are indicative of cache-worthiness data available when said values are initialized.

19. The method of claim 1, wherein said plurality of objects is chosen based on user preference from the objects stored in the database.

20. The method of claim 1, wherein said plurality of objects is chosen randomly from the objects stored in the database.

21. The method of claim 1, further comprising determining whether the selected objects are stored in the cache, and if not, copying the selected objects from the database to the cache.

22. A method for controlling caching of database objects, comprising:

associating a cache-worthiness value with a database object; and

caching said database object when the associated cache-worthiness value satisfies a pre-determined criterion.

23. The method of claim 22 further comprising removing a database object from a cache when the associated cache-worthiness value no longer satisfies said predetermined criterion.

24. The method of claim 23, wherein said pre-determined criterion comprises maximization of a total cache-worthiness of said cache subject to a constraint comprising the size of said cache.

26. The software code of claim 25, wherein said cache-worthiness data comprises requests for one or more of said plurality of objects.

27. The software code of claim 25, wherein said data comprises central processing unit (CPU) utilization data.

28. The software code of claim 25, further comprising code to initialize said cache-worthiness values.

29. The software code of claim 28, further comprising code to determine whether the selected objects are stored in the cache, and if not, to copy the selected objects from the database to the cache.

25. In a database system wherein objects are stored in a database, computer executable software code for selecting one or more of the objects to be stored in a cache, comprising:

code to collect cache-worthiness data for a plurality of objects in the database;

code to determine a cache-worthiness value for each of said plurality of objects using said data; and

code to select one or more of said plurality of objects to be stored in the cache, wherein the objects are selected using said cache-worthiness values.

30. A system comprising:

a database;

a plurality of objects stored in said database, wherein a cache-worthiness value is associated with each of said objects

a cache, coupled to said database; and

means for populating said cache from said plurality of objects based on said cache-worthiness values.

31. The system of claim 30, wherein said means for populating comprises:

means for collecting cache-worthiness data corresponding to said plurality of objects;

means for determining said cache-worthiness values using said cache-worthiness data;

means for selecting one or more of said plurality of objects using said cache-worthiness values; and

means for copying said selected objects from said database to said cache.

32. The system of claim 31, wherein said database and said cache are configured in an inline cache configuration.

33. The system of claim 31, wherein said database and said cache are configured in a parallel cache configuration.