Request management for hierarchical cache

• US 10,666,756 B2
• Filed: 09/10/2018
• Issued: 05/26/2020
• Est. Priority Date: 06/06/2016
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Baldwin, Matthew Graham, Watson, Ryan F.
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US16/126,437
• Publication Number:
  US 20190007515A1
• Time in Patent Office: 624 Days
• Field of Search: 709213, 709216, 709217, 709219, 709226
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2212/601 Reconfiguration of cache memory
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

A computer implemented cache management system and method is provided for use with a service provider configured to communicate with one or more client devices and with a content provider. The system includes a cache hierarchy comprising multiple cache levels that maintain at least some resources for the content provider, and one or more request managers for processing client requests for resources and retrieving the resources from the cache hierarchy. In response to a resource request, the request manager selects a cache level from the cache hierarchy based on a popularity associated with the requested resource, and attempts to retrieve the resource from the selected cache level while bypassing cache level(s) inferior to the selected level.

Claims

1. A cache management system comprising:

a hierarchical cache structure comprising a plurality of cache levels; and

a request management unit comprising a physical processor, the request management unit configured with computer-executable instructions that, when executed, cause the request management unit to;

process resource popularity information associated with a target resource received from an external source;

update an entry in a resource tracking index corresponding to the target resource from a first popularity value to a second popularity value higher than the first popularity value based on the resource popularity information;

adjust a mapping between a resource popularity of the target resource and a cache level in the plurality of cache levels based on the updated entry; and

in response to a request for the target resource, retrieve the target resource from the cache level indicated by the adjusted mapping.

2. The cache management system of claim 1, wherein the computer-executable instructions, when executed, further cause the request management unit to bypass at least one cache level in the plurality of cache levels to retrieve the target resource from the cache level indicated by the adjusted mapping.

3. The cache management system of claim 1, wherein the external source comprises one of a second request management unit of a point of presence (POP) that includes the request management unit, a third request management unit of a second POP different than the POP that includes the request management unit, a cache server, an information broadcasting service associated with a content delivery network (CDN) service provider, an information transmittal service associated with the CDN service provider, or the CDN.

4. The cache management system of claim 1, wherein the resource popularity information comprises one of counts or timestamps associated with requests for the target resource received by the external source.

5. The cache management system of claim 4, wherein the computer-executable instructions, when executed, further cause the request management unit to calculate the second popularity value based on at least one of logs maintained by the request management unit or the counts or timestamps.

6. The cache management system of claim 1, wherein each cache level of the plurality of cache levels comprises one or more cache servers.

7. The cache management system of claim 1, wherein the highest cache level comprises one or more one or more origin servers.

8. A computer-implemented method comprising:

receiving resource popularity information associated with a target resource from an external source;

updating an entry in a resource tracking index corresponding to the target resource based on the resource popularity information;

adjusting a mapping between a resource popularity of the target resource and a cache level in a plurality of cache levels based on the updated entry; and

in response to a request for the target resource, retrieving the target resource from the cache level indicated by the adjusted mapping.

9. The computer-implemented method of claim 8, wherein retrieving the target resource further comprises bypassing at least one cache level in the plurality of cache levels to retrieve the target resource from the cache level indicated by the adjusted mapping.

10. The computer-implemented method of claim 8, wherein the external source comprises one of a second request management unit of a point of presence (POP) that includes the request management unit, a third request management unit of a second POP different than the POP that includes the request management unit, a cache server, an information broadcasting service associated with a content delivery network (CDN) service provider, an information transmittal service associated with the CDN service provider, or the CDN.

11. The computer-implemented method of claim 8, wherein the resource popularity information comprises one of counts or timestamps associated with requests for the target resource received by the external source.

12. The computer-implemented method of claim 11, further comprising calculating a new popularity value for the target resource based on the counts or timestamps.

13. The computer-implemented method of claim 8, wherein each cache level of the plurality of cache levels comprises one or more cache servers.

14. The computer-implemented method of claim 8, wherein the highest cache level comprises one or more one or more origin servers.

15. The computer-implemented method of claim 8, wherein different cache levels of the plurality of cache levels are associated with different latencies.

16. The computer-implemented method of claim 8, wherein the target resource corresponds to at least a portion of one of an audio presentation, a video presentation, an audiovisual presentation, a movie, a television show, a video, or a podcast.

17. Non-transitory computer storage having stored thereon instructions that, when executed by a computer system, cause the computer system to:

process a resource popularity information associated with a target resource received from an external source;

update a stored resource popularity of the target resource based on the resource popularity information;

adjust a mapping between the target resource and a cache level in a plurality of cache levels based on the updated stored resource popularity of the target resource; and

in response to a request for the target resource, retrieve the target resource from the cache level indicated by the adjusted mapping.

18. The non-transitory computer storage of claim 17, wherein the instructions further cause the computer system to bypass at least one cache level in the plurality of cache levels to retrieve the target resource from the cache level indicated by the adjusted mapping.

19. The non-transitory computer storage of claim 17, wherein the external source comprises one of a second request management unit of a point of presence (POP) that includes the request management unit, a third request management unit of a second POP different than the POP that includes the request management unit, a cache server, an information broadcasting service associated with a content delivery network (CDN) service provider, an information transmittal service associated with the CDN service provider, or the CDN.

20. The non-transitory computer storage of claim 17, wherein the resource popularity information comprises one of counts or timestamps associated with requests for the target resource received by the external source, and wherein the instructions further cause the computer system to calculate a new popularity value for the target resource based on the counts or timestamps.