Multi-tier caching system

• US 6,732,237 B1
• Filed: 08/29/2000
• Issued: 05/04/2004
• Est. Priority Date: 08/29/2000
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Woo, Norman C., Demers, Alan, Jacobs, Lawrence
• Primary Examiner(s): Sparks, Donald
• Assistant Examiner(s): TRUONG, BAO Q
• Application Number:
  US09/650,498
• Time in Patent Office: 1,344 Days
• Field of Search: 711/119, 711/120, 711/122, 711/129, 711/3
• US Class Current: 711/119
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811

Abstract

A multi-tier caching system is provided for a computing device. The system comprises a first cache implemented in operating system or kernel space (e.g., in memory managed by or allocated to an operating system). The system also comprises a second cache implemented in application or user space (e.g., in memory managed by or allocated to an application program). Also provided is a method of operating the multi-tier caching system to serve one type of data from the first cache and a second type of data from the second cache. The first cache may store frequently requested data items and/or those that require little processing of a data request in order to identify a responsive data item. The first cache may also store data items that can be served in response to data requests having different forms, types, parameters, qualifiers or other indicia. Data that may vary according to the form or content of a data request, and data items that are responsive to data requests that must be fully parsed, examined or processed may be stored in the second cache. A content analysis engine may be configured to determine which of said first cache and said second cache a data item should be stored in. Such determinations may be made by analyzing data requests and/or data items served in response to the requests, guidelines set by a system administrator, and other criteria.

Claims

1. A method of responding to a data request in a computer system having multiple caches, the method comprising:

receiving a first data request from a user;

searching a first memory for a first data item responsive to said first data request, wherein the contents of said first memory are managed by an operating system;

searching a second memory for said first data item, wherein the contents of said second memory are managed by an application program;

if said searches of said first memory and said second memory are unsuccessful;

receiving said first data item from a storage device other than said first memory and said second memory; and

identifying one of said first memory and said second memory in which to store said first data item for serving in response to a later data request; and

serving said first data item to said user;

wherein said first data request comprises a parameter having a value, and wherein said identifying comprises storing said first data item in said second memory if a second data item different from said first data item must be served to a second data request having a different value for said parameter than said first data request.

2. The method of claim 1, wherein said identifying comprises storing said first data item in said first memory if said first data item is responsive to multiple different data requests.

3. The method of claim 1, further comprising transferring said first data item from one of said first memory and said second memory to the other of said first memory and said second memory.

4. The method of claim 3, wherein said first data item is transferred because of a characteristic of said first data item.

5.The method of claim 4, wherein said characteristic of said first data item is one of the set of: popularity, invalidity, size, type, and age.

5. The method of claim 1, further comprising prior to said serving, if one of said searches of said first memory and said second memory is successful:

determining whether said first data item is invalid compared to a version of said first data item stored on a storage device other than said first memory and said second memory.

6. The method of claim 6, wherein said first data item is determined to be invalid;

and

wherein said serving said first data item comprises serving said invalid first data item.

11. The method of claim 6, wherein said storage device is a computer server coupled to the computer system by a network link.

7. The method of claim 7, further comprising:

if said first data item is determined to be invalid, forwarding to said storage device a request for an updated version of said first data item.

8. The method of claim 7, further comprising prior to said serving:

if said first data item is determined to be invalid, determining whether a desired performance level of the computer system is maintainable if an updated version of said first data item is requested from said storage device to serve to said user in place of said invalid first data item.

13. The method of claim 8, further comprising:

receiving said data item from a data storage device;

serving said data item in response to said first data request; and

identifying one of said first memory and said second memory in which to store said data item.

16. The method of claim 13, wherein said first memory comprises a portion of memory of the computer system allocated to said operating system and said second memory comprises a portion of said computer system memory allocated to said application program.

17. The method of claim 13, further comprising:

serving said invalid cached version of said data item in response to said first data request.

18. The method of claim 13, further comprising:

requesting an updated version of said data item from said storage device.

9. The method of claim 9, wherein said determining whether a desired performance level of the computer system is maintainable comprises examining a characteristic of said first data item;

wherein said characteristic is selected from a group including;

popularity of said first data item, level of invalidity of said first data item, ages of said first data item, size of said first data item, type of said first data item, and cost of retrieving said first data item from said storage device.

10. The method of claim 9, wherein said determining whether a desired performance level of the computer system is maintainable comprises examining a performance characteristic of the computer system;

wherein said performance characteristic is selected from a group including;

desired response time for said first data request, number of user connections with the computer system, and a threshold number of data requests.

12. A method of responding to a data request in a computer system having multiple caches, the method comprising:

receiving a first data request;

identifying a relative level of processing that may be necessary, for said first data request, to identify a data item to be served in response to said data request;

if said level of processing is relatively low, searching a first memory of the computer system for said data item, wherein contents of said first memory are managed by an operating system; and

if said level of processing is relatively high, searching a second memory of the computer system for said data item, wherein contents of said second memory are managed by an application programs

determining whether a cached version of said data item stored in one of said first memory and said second memory is invalid compared to a version of said data item stored on a storage device other than said first memory and said second memory; and

if said cached version of said data item is determined to be invalid, determining whether a desired performance level is maintainable if an updated version of said data item is retrieved from said storage device for service and said first data request is held to await said updated version.

14. The method of claim 14, in which said identifying comprises determining a relative frequency with which said data item may be served in response to later data requests.

15. The method of claim 14, in which said identifying comprises determining whether said data item may be served in response to a second data request different from said first data request.

19. A method of caching data in a multi-tier caching system, comprising:

receiving a first data request at a computer system having a memory;

searching a first memory for a data item responsive to said first data request, wherein said first memory comprises a portion of the computer system memory configured to store contents managed by an operating system;

searching a second memory for said data item, wherein said second memory comprises a portion of the computer system memory configured to store contents managed by an application program;

receiving a second data request;

serving, in response to said second data request, an invalid version of said data item from one of said first memory and said second memory;

receiving said data item from a storage device other than said first memory and said second memory;

serving said data item in response to said first data request; and

storing said data item in one of said first memory and said second memory.

20. The method of claim 20, wherein said storing comprises determining whether to store said data item in said first memory or said second memory based on a characteristic of said data item.

22. The method of claim 20, wherein said storing comprises determining whether to store said data item in said first memory or said second memory based on a level of processing of said first data request required to identify said data item.

23. The method of claim 20, wherein said storing comprises determining whether to store said data item in said first memory or said second memory based on whether said data item is responsive to a data request different from said first data request.

24. The method of claim 20, further comprising copying said data item from one of said first memory and said second memory to the other of said first memory and said second memory due to a characteristic of said data item.

25. The method of claim 20, wherein said serving an invalid version of said data item comprises:

determining whether a desired performance level is maintainable if said second data request is held to await an updated version of said data item;

wherein said receiving said data item from a storage device comprises receiving said updated version of said data item.

21. The method of claim 21, wherein said characteristic is one of the set of:

popularity of said data item, size of said data item, age of said data item, invalidity of said data item and type of said data item.

26. A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of caching data in a multi-tier caching system, the method comprising:

receiving a first data request at a computer system having a memory;

searching a first memory for a data item responsive to said first data request, wherein said first memory comprises a portion of the computer system memory configured to store contents managed by an operating system;

searching a second memory for said data item, wherein said second memory comprises a portion of the computer system memory configured to store contents managed by an application program;

receiving a second data request;

serving, in response to said second data request, an invalid version of said data item from one of said first memory and said second memory,

receiving said data item from a storage device other than said first memory and said second memory;

serving said data item in response to said first data request; and

storing said data item in one of said first memory and said second memory.

27. The computer readable storage medium of claim 27, wherein said storing comprises determining whether to store said data item in said first memory or said second memory based on a characteristic of said data item.

28. The computer readable storage medium of claim 27, wherein said storing comprises determining whether to store said data item in said first memory or said second memory based on a level of processing of said first data request required to identify said data item.

29. The computer readable storage medium of claim 27, wherein said storing comprises determining whether to store said data item in said first memory or said second memory based on whether said data item is responsive to a data request different from said first data request.

30. A multi-tier caching system for a computing device having a main memory, the caching system comprising:

a first memory of the computing device, wherein contents of said first memory are managed by an operating system;

a second memory of the computing device, wherein contents of said second memory are managed by an application; and

a data analysis module configured to determine, for a first data item retrieved in response to a first data request, in which of said first memory and said second memory said first data item should be stored.

31. The multi-tier caching system of claim 31, wherein said data analysis module makes said determination based on a level of processing required to identify said first data item from said first data request.

32. The multi-tier caching system of claim 31, wherein said data analysis module makes said determination based on a characteristic of said first data item.

33. The multi-tier caching system of claim 31, further comprising:

an invalidation determination module configured to determine whether a second data item, stored in one of said first memory and said second memory, is invalid.

37. The multi-tier caching system of claim 31, wherein the main memory of the computing device comprises said first memory and said second memory.

34. The multi-tier caching system of claim 34, wherein said second data item is determined to be invalid if an updated version of said second data item is available on a storage device coupled to the computing device.

36. The multi-tier caching system of claim 34, wherein said second data item is invalid, further comprising:

a performance determination module configured to determine, when a second data request is received to which said second data item is responsive, whether a response to said second data request can be delayed to await said updated version of said second data item for service in place of said invalid second data item without threatening a desired performance level of the caching system.

35. The multi-tier caching system of claim 35, wherein said second data item is determined to be invalid and said invalid second data item is served in response to a second data request.

38. A computer readable storage medium containing a data structure configured for serving data items in response to data requests, the data structure comprising:

a first cache configured to store a first data item that is readily identifiable as being responsive to a first data request, wherein said first cache comprises a portion of the computer readable storage medium configured to store contents managed by an operating system; and

a second cache configured to store a second data item that is identifiable, after said second data request is analyzed, as being responsive to a second data request, wherein said second cache comprises a portion of the computer readable storage medium configured to be managed by an application program.

39. A method of operating a multi-tiered caching system in a single computer system, comprising:

receiving a first data request at a computer system having a multi-tiered caching system comprising multiple caches;

searching a first cache of the multiple caches for a data item responsive to said first data request, wherein contents of said first cache are managed by an operating system of the computer system; and

if said searching of said first cache is unsuccessful, passing said first data request to a second cache of the multiple caches managed by an application program executing on the computer system.

40. The method of claim 40, further comprising:

if a data item responsive to said first data request is not found in either of said first cache and said second cache, retrieving a responsive data item from a storage unit coupled to the computer system;

serving said retrieved data item in response to said first data request; and

selecting one of said first cache and said second cache to store said retrieved data item in.

41. The method of claim 40, wherein said data item is found in one of said first cache and said second cache, the method further comprising:

determining whether said data item is invalid compared to a version of said data item stored in a storage device other than said first cache and said second cache.

42. The method of claim 42, wherein said data item is determined to be invalid, the method further comprising:

serving said invalid data item in response to said first data request.

43. The method of claim 42, further comprising:

if said data item is determined to be invalid, forwarding a request for an updated version of said data item from said storage device.

44. The method of claim 42, further comprising prior to said serving:

if said data item is determined to be invalid, determining whether a desired performance level of the multi-tiered computer system is maintainable if an updated version of said data item is requested from said storage device to serve in response to said first data request.

45. A multi-tier caching system, comprising:

a first caching means configured to cache a first set of data items for serving in response to data requests, wherein said first caching means comprises a portion of a computer memory managed by an operating system executing on the computer;

a second caching means configured to cache a second set of data items for serving in response to data requests, wherein said second caching means comprises a portion of the computer memory managed by an application program executing on the computer;

selection means configured to select one of said first caching means and said second caching means to cache a new data item retrieved from a storage device external to the computer; and

serving means configured to serve, from one of said first caching means and said second caching means, an invalid version of a first data item in response to a request for the first data item;

wherein a current version of the first data item is stored on the storage device.

46. The multi-tier caching system of claim 46, wherein said selection means is further configured to move a first data item cached in one of said first caching means and said second caching means to the other of said first caching means and said second caching means.

47. The multi-tier caching system of claim 46, wherein said selection means is configured to store, in said second caching means, a first data item for serving in response to a data request comprising a first parameter having a first value if a second data item, different from the first data item, is to be served in response to a data request comprising the first parameter having a second value different from the first value.

48. The multi-tier caching system of claim 46, further comprising a performance determination module configured to determine, if a requested first data item is invalid, whether a desired performance level of the computer system is maintainable if an updated version of the first data item is requested from the storage device to serve in place of the first data item.

49. A computer readable medium storing instructions that, when executed by a computer, cause the computer to perform a method of caching data in a multi-tier caching system, the method comprising:

receiving a first data request from a user;

searching a first memory for a first data item responsive to said first data request, wherein the contents of said first memory are managed by an operating system;

searching a second memory for said first data item, wherein the contents of said second memory are managed by an application program;

if said searches of said first memory and said second memory are unsuccessful;

receiving said first data item from a storage device other than said first memory and said second memory; and

identifying one of said first memory and said second memory in which to store said first data item for serving in response to a later data request; and

serving said first data item to said user;

wherein said data request comprises a parameter having a value, and wherein said identifying comprises storing said first data item in said second memory if a second data item different from said first data item must be served to a second data request having a different value for said parameter than said first data request.

50. The computer readable medium of claim 50, wherein said identifying comprises storing said first data item in said first memory if said first data item is responsive to multiple different data requests.

51. The computer readable medium of claim 50, further comprising transferring said first data item from one of said first memory and said second memory to the other of said first memory and said second memory.

52. The computer readable medium of claim 50, further comprising prior to said serving, if one of searches of said first memory and said second memory is successful:

determining whether said first data item is invalid compared to a version of said first data item stored on a storage device other than said first memory and said second memory; and

if said first data item is determined to be invalid, determining whether a desired performance level of the computer system is maintainable if an updated version of said first data item is requested from said storage device to serve to said user in place of said invalid first data item.

53. A method of responding to a data request in a computer system having multiple caches, the method comprising:

receiving a first data request from a user;

searching a first memory for a first data item to be served in response to said first data request, wherein the contents of said first memory are managed by an operating system;

searching a second memory for said first data item, wherein the contents of said second memory are managed by an application program; and

if one or more of said searches of said first memory and said second memory is successful;

determining whether said first data item is invalid compared to a version of said first data item stored on a storage device other than said first memory and said second memory; and

if said first data item is determined to be invalid, determining whether a desired performance level of the computer system is maintainable if an updated version of said first data item is requested from said storage device to serve to said user in place of said invalid first data item; and

serving said first data item to the user.

54. The method of claim 54, further comprising:

transferring said first data item from one of said first memory and said second memory to the other of said first memory and said second memory.

55. The method of claim 54, wherein if said first data item is determined to be invalid, said serving comprises serving said invalid first data item.

56. The method of claim 54, wherein said determining whether a desired performance level of the computer system is maintainable comprises examining a popularity of said first data item.

57. The method of claim 54, wherein said determining whether a desired performance level of the computer system is maintainable comprises examining a level of invalidity of said first data item.

58. The method of claim 54, wherein said determining whether a desired performance level of the computer system is maintainable comprises examining an age of said first data item.

59. The method of claim 54, wherein said determining whether a desired performance level of the computer system is maintainable comprises examining a size of said first data item.

60. The method of claim 54, wherein said determining whether a desired performance level of the computer system is maintainable comprises examining a type of said first data item.

61. The method of claim 54, wherein said determining whether a desired performance level of the computer system is maintainable comprises examining a cost of retrieving said first data item from said storage device.

62. The method of claim 54, wherein said determining whether a desired performance level of the computer system is maintainable comprises determining whether said first data item is relatively static or relatively dynamic.

63. The method of claim 54, wherein said determining whether a desired performance level of the computer system is maintainable comprises examining a desired response time for responding to said first data request.

64. The method of claim 54, wherein said determining whether a desired performance level of the computer system is maintainable comprises examining a number of user connections with the computer system.

65. The method of claim 54, wherein said determining whether a desired performance level of the computer system is maintainable comprises examining a maximum desirable number of data requests for the computer system.

66. A computer readable medium storing instructions that, when executed by a computer, cause the computer to perform a method of responding to a data request in a computer system having multiple caches, the method comprising:

receiving a first data request;

identifying a relative level of processing that may be necessary, for said first data request, to identify a data item to be served in response to said data request;

if said level of processing is relatively low, searching a first memory of the computer system for said data item, wherein contents of said first memory are managed by an operating system;

if said level of processing is relatively high, searching a second memory of the computer system for said data item, wherein contents of said second memory are managed by an application program;

determining whether a cached version of said data item stored in one of said first memory and said second memory is invalid compared to a version of said data item stored on a storage device other than said first memory and said second memory; and

if said cached version of said data item is determined to be invalid, determining whether a desired performance level is maintainable if an updated version of said data item is retrieved from said storage device for service and said first data request is held to await said updated version.

67. The computer readable medium of claim 67, wherein said identifying comprises determining a relative frequency with which said data item may be served in response to later data requests.

68. The computer readable medium of claim 67, wherein said identifying comprises determining whether said data item may be served in response to a second data request different from said first data request.

69. The computer readable medium of claim 67, further comprising:

serving said invalid cached version of said data item in response to said first data request.

70. A computer readable medium storing instructions that, when executed by a computer, cause the computer to perform a method of operating a multi-tiered caching system in a single computer system, comprising:

receiving a first data request at a computer system having a multi-tiered caching system comprising multiple caches;

searching a first cache of the multiple caches for a data item responsive to said first data request, wherein contents of said first cache are managed by an operating system of the computer system; and

if said searching of said first cache is unsuccessful, passing said first data request to a second cache of the multiple caches managed by an application program executing on the computer system.

71. A computer readable medium storing instructions that, when executed by a computer, cause the computer to perform a method of responding to a data request in a computer system having multiple caches, the method comprising:

receiving a first data request from a user;

searching a first memory for a first data item to be served in response to said first data request, wherein the contents of said first memory are managed by an operating system;

searching a second memory for said first data item, wherein the contents of said second memory are managed by an application program; and

if one or more of said searches of said first memory and said second memory is successful;

determining whether said first data item is invalid compared to a version of said first data item stored on a storage device other than said first memory and said second memory; and

if said first data item is determined to invalid, determining whether a desired performance level of the computer system is maintainable if an updated version of said first data item is requested from said storage device to serve to said user in place of said invalid first data item; and

serving said first data item to the user.