Multi-tier caching system
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
71 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. - View Dependent Claims (2, 3, 4, 5)
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. - View Dependent Claims (11)
- and
-
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. - View Dependent Claims (8, 13, 16, 17, 18)
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.- View Dependent Claims (10)
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.
-
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.
-
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.
-
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.
- 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.
-
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. - View Dependent Claims (41)
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. - View Dependent Claims (43, 44)
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.
-
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.
-
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. - View Dependent Claims (55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65)
-
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.
-
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.
-
Specification