CACHE EVICTION SCHEME FOR ACCEPTABLE SUBSTITUTES IN ONLINE MEDIA

• US 20190340135A1
• Filed: 05/07/2018
• Published: 11/07/2019
• Est. Priority Date: 05/07/2018
• Status: Active Grant

• Current Assignee: Akamai Technologies, Inc.
• Original Assignee: Akamai Technologies, Inc.
• Inventors: McCall, Michael
• Granted Patent: US 10,452,563 B1
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/12 Replacement control
• 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 2212/1044 Space efficiency improvement
• CPC Class Codes: G06N 10/00 Quantum computing, i.e. information processing based on quantum-mechanical phenomena
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data

Abstract

Among other things, this document describes systems, devices, and methods for improving cache performance when caching multiple versions of an object. In some embodiments, a network cache can execute a cache eviction algorithm that considers the versatility of object versions when making eviction decisions. The techniques described herein can be applied to wide variety of media objects, such as an original image and a set of derivative images in various formats, sizes, or compression levels. A versatile version is versatile because it can be substituted for one or more other versions requested by a client. Hence, the techniques described herein may prefer, under certain conditions, to evict from a network cache less versatile versions prior to evicting more versatile versions.

Claims

1. A cache eviction method performed by a network cache, the method comprising:

storing first and second objects in a network cache, each of the first and second objects corresponding to a different version of a media object and being available to requesting clients from the network cache;

determining to evict content from the network cache, the determination based at least in part on an amount of available storage space in the network cache;

in response to said determination, selecting the first object for eviction and keeping the second object stored in the cache, the selection being based at least in part on a versatility attribute of the second object, wherein versatility comprises a property allowing the network cache to substitute the second object for the first object when responding to a client request for the first object; and

,

evicting the first object from the network cache.

2. The method of claim 1, further comprising, receiving a client request for the first object, and in response, serving the second object from the network cache.

3. The method of claim 1, wherein the media object comprises any of:

an image file, an audio file, and a video file.

4. The method of claim 1, wherein the first and second objects are different at least because of differences in one or more of:

format, compression ratio, resolution, aspect ratio, image dimensions.

5. The method of claim 1, further comprising receiving the versatility attribute for the second object from an origin server.

6. The method of claim 1, further comprising receiving the versatility attribute for the second object from a configuration provided by a user.

7. The method of claim 1, further comprising receiving the versatility attribute for the second object from a learning algorithm.

8. The method of claim 1, further comprising receiving the versatility attribute for the second object from a learning algorithm that analyzes at least request frequency by any of:

user agent, player application, and client device type.

9. The method of claim 1, further comprising:

receiving the second object from an origin server and generating the first object from the second object.

10. The method of claim 1, wherein the versatility attribute comprises a ranking of the first and second objects.

11. The method of claim 10, further comprising receiving the ranking from any of:

an origin server and a configuration portal.

12. The method of claim 1, further comprising, prior to selecting the first object for eviction, selecting a group comprised of the first and second objects for eviction.

13. An apparatus, comprising:

a network cache, comprising;

circuitry providing at least one processor;

a storage device providing space for storing objects;

a non-transitory computer readable medium storing instructions that, when executed by the at least one processor, cause the network cache to;

store first and second objects in a network cache, each of the first and second objects corresponding to a different version of a media object and being available to requesting clients from the network cache;

determine to evict content from the network cache, the determination based at least in part on an amount of available storage space in the network cache;

in response to said determination, select the first object for eviction and keeping the second object stored in the cache, the selection being based at least in part on a versatility attribute of the second object, wherein versatility comprises a property allowing the network cache to substitute the second object for the first object when responding to a client request for the first object; and

,

evict the first object from the network cache.

14. The apparatus of claim 13, the non-transitory computer readable medium storing instructions that, when executed by the at least one processor, cause the network cache to:

receive a client request for the first object, and in response, serving the second object from the network cache.

15. The apparatus of claim 13, wherein the first and second objects are different at least because of differences in one or more of:

format, compression ratio, resolution, aspect ratio, image dimensions.

16. The apparatus of claim 13, the non-transitory computer readable medium storing instructions that, when executed by the at least one processor, cause the network cache to:

receive the second object from an origin server and generate the first object from the second object.

17. The apparatus of claim 13, wherein the versatility attribute comprises a ranking of the first and second objects.

18. A cache eviction method for a network cache, comprising:

storing first and second objects in a network cache, each of the first and second objects corresponding to a different version of a media object and being available to requesting clients from the network cache;

determining to evict content from the network cache, the determination being based at least in part on an amount of available storage space in the network cache;

in response to said determination, selecting the first object for eviction and keeping the second object stored in the cache, the selection being based at least in part on a versatility attribute of the second object, wherein versatility of the second object is a function of proportion of clients that can decode the second object; and

,

evicting the first object from the network cache.

19. The method of claim 18, comprising generating a ranking of the versatility of the plurality of objects, and further comprising, in response to the determination to evict content from the network cache, consulting the ranking.