System and method for caching sets of objects

• US 6,654,766 B1
• Filed: 04/04/2000
• Issued: 11/25/2003
• Est. Priority Date: 04/04/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ehnebuske, David L., Iyengar, Arun K., Rouvellou, Isabelle M., Degenaro, Louis R., McKee, Barbara Jane Alspach
• Primary Examiner(s): Mizrahi, Diane D.
• Assistant Examiner(s): Mofiz, Apu M
• Application Number:
  US09/542,269
• Time in Patent Office: 1,330 Days
• Field of Search: 707/4, 707/6, 707/10, 707/101, 707/103.R, 707/103.Y, 707/104.1, 707/201, 707/202, 707/203, 709/213, 709/223, 709/238, 345/440, 711/118
• US Class Current: 1/1
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A system and method for managing cacheable sets of objects having explicit lifetime specifications, wherein a time-based cache manager maintains and updates one or more sets of objects stored in the cache. A cached set of objects comprises objects having start times and/or end times representing, respectively, times at which such objects become valid and expire. An update time is determined for a given cached set of objects based, in part, on the start times and end times of objects comprising the cached set of objects. When a request for the retrieval of an object from the given cached set of objects (or the entire cached set) is received, a determination is made if the cached set of objects is valid at the time of the request based on the update time. If the cached set of objects is not valid because, e.g., the update time has elapsed, the cached set of objects is updated (and any other cached sets, if necessary) by deleting and/or adding objects to the cached set of objects having start times and end times that meet predefined time criteria for inclusion in the cached set of objects.

Claims

1. A method for storing objects in a system comprising a plurality of objects, the method comprising the steps of:

assigning a start time to one or more of the plurality of objects, wherein a start time is an attribute of an object and wherein the start time represents a time when the object becomes valid;

generating a set of objects comprising at least one object having an assigned start time;

storing the set of objects in a storage medium; and

in response to a query, returning the at least one object having the assigned start time, if the object is valid at a time corresponding to the query.

2. The method of claim 1, further comprising the step of assigning an end time to at least one of the plurality of objects.

3. The method of claim 2, further comprising the steps of:

designating a collection by assigning a first time t1 and a last time t2, wherein t2 is greater than t1; and

selecting, as a member of the collection, one or more of the plurality of objects having an end time that is not less than t1 and a start time that is not greater than t2.

4. The method of claim 3, further comprising the step of determining a collection subset from the collection, wherein the collection subset comprises objects having an elapsed start time and having an end time that has not elapsed.

5. The method of claim 4, further comprising the step of ordering, between t1 and t2, start times and end times of objects in the collection.

6. The method of claim 5, wherein the ordering is stored in one of a list and a balanced tree.

7. The method of claim 5, further comprising the step of updating the collection subset using the ordered start times and end times.

8. The method of claim 7, wherein the step of updating comprises adding into the collection subset an object having a currently elapsed start time.

9. The method of claim 7, wherein the step of updating comprises deleting from the collection subset an object having a currently elapsed end time.

10. The method of claim 5, further comprising the step of assigning an update time to the collection subset using the ordered start times and end times.

11. The method of claim 10, wherein the update time is one of the earliest end time of an object in the collection subset and the earliest non-elapsed start time of an object that is included in the collection but not included in the collection subset.

12. The method of claim 4, wherein the storage medium is a cache and wherein the set of objects stored in the storage medium comprises one of the collection, the collection subset and both.

13. The method of claim 1, wherein the set of objects comprises a set of objects satisfying a query.

14. The method of claim 1, wherein the storage medium is a cache associated with a client and the plurality of objects are associated with a server, and further comprising the step of sending a message from the server to the client to update the cache.

15. The method of claim 14, wherein the message comprises one of a new start time in the future and an end time in the future for an object.

16. The method of claim 14, further comprising the step of periodically sending a request by the client to the server to request cache update information.

17. The method of claim 14, further comprising the step of periodically requesting, by a plurality of clients, cache update information from the server, wherein the requests occur at different times.

18. The method of claim 14, wherein the message comprises information indicating a time in the future when new cache update information is one of available and likely to be available.

19. The method of claim 1, wherein the method, steps are tangibly embodied as program instructions on a program storage device, wherein the program instructions are readable and executable on a machine to perform the method steps.

20. A method for managing a cache in a system comprising a plurality of objects, the method comprising the steps of:

caching a set of objects, wherein the set of objects comprises at least one object having an assigned start time or a start time and end time, wherein the start time is an attribute of an object and wherein the start time represents a time when the object becomes valid and the end time represents a time when the object becomes invalid;

assigning an update time corresponding to a time at which the cached set of objects becomes invalid;

determining, at a current time, if the cached set of objects is valid based on the update time; and

updating the cache if the cached set of objects is determined to be invalid.

21. The method of claim 20, wherein the cached set of objects comprises query results associated with a query.

22. The method of claim 20 wherein the update time comprises one of an end time of an object in the cached set of objects, a start time of an object in the cached set of objects, a start time of an object that is not a member of the cached set of objects and an end time of an object that is not a member of the cached set of objects.

23. The method of claim 20, wherein the step of updating the cache comprises the step of updating the cached set of objects by one of deleting from the cached set of objects an object having an end time that has elapsed at the current time, adding into the cached set of objects an object having a start time that has elapsed as of the current time and a combination thereof.

24. The method of claim 20, further comprising the steps of:

assigning one of a start time, an end time, and a start time and end time to at least one of the plurality of objects; and

generating a superset of objects from the plurality of objects based, at least in part, on predefined time criteria, wherein the superset comprises objects that are used to update the cached set of objects.

25. The method of claim 24, wherein the step of generating the superset comprises:

assigning a first time t1 and a last time t2 to the superset of objects; and

selecting, as a member of the superset, at least one object from the plurality of objects having an end time that is not less than t1 and a start time that is not greater than t2.

26. The method of claim 25, wherein the update time comprises one of t1, t2, an end time of an object in the superset, and a start time of an object in the superset.

27. The method of claim 25, wherein the cached set of objects is deemed invalid if the update time has elapsed as of the current time, and wherein the step of updating comprises a step of one of deleting from the cached set of objects an object having an end time that has elapsed as of the current time, selecting from the superset, for inclusion in the cached set of objects, an object having a start time that has elapsed as of the,current time, and a combination thereof.

28. The method of claim 27, further comprising the step of updating the superset at the current time if the current time does not fall within the range of t1 through t2.

29. The method of claim 28, wherein the step of updating the superset comprises the steps of:

calculating one of a new first time, a new last time, and a combination thereof for the superset of objects; and

removing from the superset an object having one of a start time that is greater than the new last time and an end time that is less than the new first time; and

adding into the superset an object from the plurality of objects having a start time that is not greater than the new last time and an end time that is not less than the new first time.

30. The method of claim 28, further comprising the step of calculating a new cached set of objects in response to the updating of the superset;

and

determining a new update time for the new cached set of objects.

31. The method of claim 24, further comprising the step of storing the superset in a cache.

32. The method of claim 20, wherein the method steps are tangibly embodied as program instructions on a program storage device, wherein the program instructions are readable and executable on a machine to perform the method steps.

33. A system for managing a cache, comprising:

a cache for storing at least one set of objects, wherein the at least one set of objects stored in the cache comprises at least one object having an assigned start time or a start time and end time, wherein the start time and end time are attributes of an object and wherein the start time represents a time when the object becomes valid and wherein the end time represents a time when the object becomes invalid;

at least one client comprising a cache manager for providing time-based management of the cache, wherein in response to a query for an object, the cache manager will return the object if the object is valid at a time corresponding to the query based on at least the start time of the object; and

at least one server for providing information to the at least one client for updating the cache.

34. The system of claim 33, wherein the server comprises a database comprising a plurality of objects from which the at least one set of objects stored in the cache is generated.

35. The system of claim 33, wherein the cache manager comprises a data configuration module for designating a collection by assigning a first time t1 and a last time t2, wherein t2 is greater than t1;

and

a collection refresh module for selecting, as a member of the collection, at least one object from a plurality of objects having an end time that is not less than t1 and a start time that is not greater than t2.

36. The system of claim 35, wherein the cache manager further comprises a collection subset module for determining a collection subset from the collection, wherein the collection subset comprises objects having an elapsed start time and having an end time that has not elapsed, and wherein the collection subset comprises the at least one set of objects stored in the cache.

37. The system of claim 36, wherein the collection refresh module orders, between t1 and t2, start times and end times of objects in the collection.

38. The system of claim 37, wherein the collection subset module updates the collection subset using the ordered start times and end times.

39. The system of claim 38, wherein the update comprises one or adding into the collection subset an object having a currently elapsed start time, deleting from the collection subset an object having a currently elapsed end time, and combination thereof.

40. The system of claim 37, wherein the cache manager assigns an update time to the collection subset using the ordered start times and end times.

41. The system of claim 40, wherein the update time is one of the earliest end time of an object in the collection subset and the earliest non-elapsed start time of an object that is included in the collection but not included in the collection subset.

42. The system of claim 33, wherein the update information comprises one of a new start time in the future and an end time in the future for an object.

43. The system of claim 33, wherein the update information indicates a time in the future when new cache update information is one of available and likely to be available.

44. A method for storing objects in a system comprising a plurality of objects, the method comprising the steps of:

assigning a start time to an object, wherein the start time is an attribute of the object and wherein the start time represents a time when the object becomes valid;

storing the object in a storage medium; and

in response to a query, returning the stored object if the object is valid a time corresponding to the query.

45. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for storing objects in a system comprising a plurality of objects, the method steps comprising:

assigning a start time to an object, wherein the start time is an attribute of the object and wherein the start time represents a time when the object becomes valid;

storing the object in a storage medium; and

in response to a query, returning the stored object if the object is valid a time corresponding to the query.