Reserved cache space in content delivery networks

• US 10,049,051 B1
• Filed: 12/11/2015
• Issued: 08/14/2018
• Est. Priority Date: 12/11/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Baldwin, Matthew Graham
• Primary Examiner(s): Tsui, Daniel
• Assistant Examiner(s): Khan, Masud
• Application Number:
  US14/967,218
• Time in Patent Office: 977 Days
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 12/0893 Caches characterised by their organisation or structure
• 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: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/1021 Hit rate improvement
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

Systems and methods are described to reserve cache space of points of presence (“POPs”) within a content delivery network (“CDN”). A provider may submit a request to the CDN to reserve cache space on one or more POPs for data objects designated by that provider. Thereafter, the CDN may mark those designated data objects within its cache as protected from eviction. When the CDN implements a cache eviction policy on the cache, the protected objects may be ignored for purposes of eviction, or may be evicted only after non-protected data objects.

Claims

1. A content delivery system comprising:

a non-transitory data store implementing a data cache to store data objects from at least two different providers providing content to the content delivery system, the data cache including a plurality of data objects previously accessed by end users of the content delivery system, wherein the plurality of data objects stored within the data cache includes data objects from the at least two different providers, the data cache further including information indicating a most recent access time for data objects of the plurality of data objects;

a computing device comprising a processor and memory, the processor configured with specific computer-executable instructions that, when executed, cause the processor to;

receive a request from a first provider of the plurality of providers to reserve a portion of the data cache on the content delivery system for data objects within the data cache associated with the first provider, wherein the portion is associated with a data size;

identify, from the plurality of data objects stored within the data cache including data objects from the at least two different providers, one or more most-recently-accessed data objects associated with the first provider, wherein a collective size of the one or more most-recently-accessed data objects is not more than the specified data size;

mark as protected from eviction the one or more most-recently-accessed data objects associated with the first provider within the data cache including data objects from the at least two different providers;

determine that a collective size of the plurality of data objects from the at least two different providers within the data cache exceeds a cache size limit;

identify, within the plurality of data objects from the at least two different providers, one or more least-recently-accessed data objects that are not marked as protected from eviction; and

delete, from the data cache, the one or more least-recently-accessed data objects identified within the plurality of data objects from the at least two different providers.

2. The content delivery system of claim 1, wherein the specific computer-executable instructions, when executed, further cause the processor to:

receive a request for a first data object associated with the first provider;

determine that the first data object is not stored within the data cache;

retrieve the first data object from an external content source; and

mark the first data object as protected from eviction.

3. The content delivery system of claim 2, wherein the specific computer-executable instructions, when executed, further cause the processor to:

determine that a collective size of the first data object and the previously identified one or more most-recently-accessed data objects associated with the first provider exceeds the specified data size;

identify, from the one or more most-recently-accessed data objects associated with the first provider, a least recently used data object; and

mark the least recently used data object as not protected from eviction.

4. The content delivery system of claim 1, wherein the information indicating a most recent access time for data objects of the plurality of data objects comprises a doubly linked list identifying a relative recency of access between the data objects.

5. The content delivery system of claim 1, wherein the non-transitory data store further includes a doubly linked list identifying a relative recency of access between data objects associated with the first provider.

6. A computer-implemented method comprising:

implementing, within a memory, a data cache storing a plurality of data objects that were previously accessed by end users, wherein the data cache indicates a most recent access time for data objects of the plurality of data objects, and wherein the plurality of data objects stored within the data cache includes data objects from at least two different providers;

receiving a request to reserve a portion of the data cache for data objects within the data cache associated with a first provider of the at least two providers, wherein the portion is associated with a size;

identifying, from the plurality of data objects stored within the data cache including data objects from the at least two different providers, one or more data objects associated with the first provider that have been accessed more recently than other data objects associated with the first provider that are within the plurality of data objects wherein a collective size of the one or more data objects is not more than the size;

marking, within the data cache including data objects from the at least two different providers, the one or more data objects associated with the first provider as protected from eviction;

determining that a collective size of the plurality of data objects from the at least two different providers within the data cache exceeds a cache size limit;

identifying, within the plurality of data objects from the at least two different providers, at least one data object that is not marked as protected from eviction; and

deleting, from the data cache, the at least one data object identified within the plurality of data objects from the at least two different providers.

7. The computer-implemented method of claim 6 further comprising:

receiving a request from a second provider of the at least two different providers to reserve a second portion of the data cache for data objects within the data cache associated with the second provider, wherein the second portion is associated with a second size;

identifying, from the plurality of data objects stored within the data cache including data objects from the at least two different providers, one or more data objects associated with the second provider that have been accessed more recently than other data objects associated with the second provider that are within the plurality of data objects, wherein a collective size of the one or more data objects associated with the second provider is not more than the second size; and

marking, within the data cache including data objects from the at least two different providers, the one or more data objects associated with the second provider as protected from eviction.

8. The computer-implemented method of claim 6, wherein the cache size limit is at least one of an absolute size limit or a size limit relative to a total capacity of the data cache.

9. The computer-implemented method of claim 6, wherein the at least two different providers are among a plurality of providers providing content to a content delivery system.

10. The computer-implemented method of claim 6, wherein identifying, within the plurality of data objects from the at least two different providers, the at least one data object that is not marked as protected from eviction comprises identifying a least-recently-used data object within the data cache that is not marked as protected from eviction.

11. The computer-implemented method of claim 6 further comprising:

receiving a request for a first data object associated with the first provider;

determining that the first data object is not stored within the data cache;

retrieving the first data object from an external content source; and

marking the first data object as protected from eviction.

12. The computer-implemented method of claim 11 further comprising:

determining that a collective size of the first data object and the previously identified one or more data objects associated with the first provider exceeds the size; and

marking at least one of i) the first data object or ii) a data object from the one or more data objects associated with the first provider as not protected from eviction.

13. The computer-implemented method of claim 12, wherein marking at least one of i) the first data object or ii) a data object from the one or more data objects associated with the first provider as not protected from eviction comprising:

identifying a least recently used data object from a group including the first data object and the one or more data objects associated with the first provider; and

marking the least recently used data object as not protected from eviction.

14. Non-transitory computer-readable media including instructions executable by a computing device to:

implement, within a memory, a data cache storing a plurality of data objects that were previously accessed by end users, wherein the data cache indicates access times for data objects of the plurality of data objects, and wherein the plurality of data objects stored within the data cache includes data objects from at least two different providers;

obtain instructions to reserve a portion of the data cache for data objects within the data cache associated with a first provider of the at least two providers, wherein the portion is associated with a size;

identify, from the plurality of data objects stored within the data cache including data objects from the at least two different providers, one or more data objects associated with the first provider, wherein a collective size of the one or more data objects is not more than the size;

mark, within the data cache including data objects from the at least two different providers, the one or more data objects associated with the first provider as protected from removal;

determine that a collective size of the plurality of data objects from the at least two different providers within the data cache exceeds a cache size limit;

identify, within the plurality of data objects from the at least two different providers, at least one data object that is not marked as protected from removal; and

delete, from the data cache, the at least one data object identified within the plurality of data objects from the at least two different providers.

15. The non-transitory computer-readable media of claim 14, wherein the instructions are executable by the computing device to identify the one or more data objects associated with the first provider based at least partly on identification of which data objects associated with the first provider have been most-recently-accessed in the data cache.

16. The non-transitory computer-readable media of claim 14, wherein the instructions are further executable by the computing device to:

obtain instructions to reserve a second portion of the data cache for data objects within the data cache associated with a second provider of the at least two providers, wherein the second portion is associated with a second size;

identify, from the plurality of data objects stored within the data cache including data objects from the at least two different providers, one or more data objects associated with the second provider, wherein a collective size of the one or more data objects is not more than the second size; and

mark the one or more data objects associated with the second provider as protected from eviction.

17. The non-transitory computer-readable media of claim 14, wherein the instructions are executable by the computing device to identify, within the plurality of data objects from the at least two different providers, the at least one data object that is not marked as protected from eviction at least partly by identifying a least-recently-used data object within the data cache that is not marked as protected from eviction.

18. The non-transitory computer-readable media of claim 14, wherein the instructions are further executable by the computing device to:

obtain a request for a first data object associated with the first provider;

determine that the first data object is not stored within the data cache;

retrieve the first data object from an external content source; and

mark the first data object as protected from eviction.

19. The non-transitory computer-readable media of claim 18, wherein the instructions are further executable by the computing device to:

determine that a collective size of the first data object and the previously identified one or more data objects associated with the first provider exceeds the size; and

mark at least one data object selected from i) the first data object or ii) the one or more data objects associated with the first provider as not protected from eviction.

20. The non-transitory computer-readable media of claim 18, wherein the at least one data object selected from i) the first data object or ii) the one or more data objects associated with the first provider represents the least recently used data object in a group consisting of i) the first data object and ii) the one or more data objects associated with the first provider represents.