Method, system and program product for caching data objects

• US 7,231,496 B2
• Filed: 09/15/2003
• Issued: 06/12/2007
• Est. Priority Date: 09/15/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Curtis, John D.
• Primary Examiner(s): Song; Jasmine
• Application Number:
  US10/662,539
• Publication Number:
  US 20050060498A1
• Time in Patent Office: 1,366 Days
• Field of Search: None
• US Class Current: 711/137
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 2212/6024 History based prefetching

Abstract

Under the present invention, a history of requests for data objects are tracked and maintained in a cache log. Based on the history, certain data objects are prefetched into a cache. When a request for a cached data object is later received, the requested data object can be retrieved from the cache and served to the requesting user. Thus, the latency involved with obtaining the data objects from the appropriate sources is eliminated. Further, under the present invention, discard and refresh rules are assigned to each data object on a class basis. Accordingly, data objects in the cache can be refreshed and/or discarded so that the caching operation can be optimized.

Claims

1. A method for caching data objects that are registered according to classes, the method comprising:

providing a cache having a cache log for the data objects, wherein the cache log is adapted to log a history of requests for a data object that is not stored in the cache;

assigning discard rules to the data objects on a class basis;

predicting needed data objects based on the cache log;

prefetching the needed data objects that are predicted to be needed into the cache;

discarding particular data objects from the cache based on the discard rules; and

managing a discard queue and a refresh queue concurrently.

2. The method of claim 1, further comprising refreshing the needed data objects in the cache based on refresh rules.

3. The method of claim 2, wherein the needed data objects are refreshed from the refresh queue.

4. The method of claim 1, wherein the discarding step comprises discarding the particular data objects from the cache to the discard queue based on the discard rules.

5. The method of claim 1, further comprising:

receiving a request for certain data objects; and

retrieving the certain data objects from the cache.

6. The method of claim 1, wherein the cache log comprises a relational database.

7. The method of claim 1, wherein the needed data objects are predicted from a history of requests as tracked in the cache log.

8. The method of claim 1, further comprising dynamically adjusting the discard rules.

9. The method of claim 1, wherein the predicting step comprises predicting a sequence of needed data objects based on time of day.

10. A system for caching data objects, that are registered according to classes, the system comprising:

a logger for logging a history of requests for data objects in a cache log that is adapted to log the history of requests for a data object that is not stored in the cache;

a predictor for analyzing the cache log and prefetching needed data objects that are predicted to by into a cache based on the history of requests;

a request analyzer for discarding data objects from the cache based on discard rules assigned to the data objects, wherein the discard rules are assigned to the data objects on a class basis and;

a governor for concurrently managing a refresh queue and a discard queue.

11. The system of claim 10, wherein the refresh queue contains refreshed data objects, and wherein the refreshed data objects are moved from the refresh queue into the cache based on refresh rules by a queue refresher.

12. The system of claim 10, wherein the discard queue contains data objects discarded from the cache by the request analyzer based on the discard rules.

13. The system of claim 10, wherein the request analyzer further dynamically updates the discard rules.

14. The system of claim 10, further comprising a request handler for receiving a request for a certain data object and retrieving the certain data object from the cache.

15. The system of claim 10, wherein the cache log comprises a relational database.

16. The system of claim 10, wherein the predictor predicts a sequence of needed data objects and prefetches the sequence of needed data objects into the cache.

17. A program product stored on a storage medium for caching data objects, that are registered according to classes, the program when executed, comprises:

program code for logging a history of requests for data objects in a cache log that is adapted to log the history of requests for a data object that is not stored in the cache;

program code for analyzing the cache log and prefetching needed data objects into a cache based on the history of requests;

program code for discarding data objects from the cache based on discard rules assigned to the data objects, wherein the discard rules are assigned to the data objects on a class basis; and

program code for concurrently managing a refreshed queue and a discard queue.

18. The program product of claim 17, wherein the refresh queue contains refreshed data objects, and wherein the refreshed data objects are moved from the refresh queue into the cache based on refresh rules.

19. The program product of claim 17, wherein the discard queue contains data objects discarded from the cache by the program code for analyzing based on the discard rules.

20. The program product of claim 17, further comprising program code for dynamically updates the discard rules.

21. The program product of claim 17, further comprising program code for receiving a request for a certain data object and retrieving the certain data object from the cache.

22. The program product of claim 17, wherein the cache log comprises a relational database.

23. The program product of claim 17, wherein the program code for analyzing predicts a sequence of needed data objects and prefetches the sequence of needed data objects into the cache.