Method and system for self-tuning cache management

• US 9,112,922 B2
• Filed: 08/28/2012
• Issued: 08/18/2015
• Est. Priority Date: 08/28/2012
• Status: Active Grant

• Current Assignee: Masimo Corporation
• Original Assignee: Vantrix Corporation
• Inventors: Ct, Sbastien, Buchnajzer, Robert, Benoit, Louis
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): WONG, NANCI N
• Application Number:
  US13/596,169
• Publication Number:
  US 20140068196A1
• Time in Patent Office: 1,085 Days
• Field of Search: 711/135
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass
• 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: G06F 2212/464 Multimedia object, e.g. image, video
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data

Abstract

Web objects, such as media files are sent through an adaptation server which includes a transcoder for adapting forwarded objects according to profiles of the receiving destinations, and a cache memory for caching frequently requested objects, including their adapted versions. The probability of additional requests for the same object before the object expires, is assessed by tracking hits. Only objects having experienced hits in excess of a hit threshold are cached, the hit threshold being adaptively adjusted based on the capacity of the cache, and the space required to store cached media files. Expired objects are collected in a list, and may be periodically ejected from the cache, or when the cache is nearly full.

Claims

1. A method for managing caching of objects in a cache, comprising:

receiving a request (hit) for an object having a predetermined expiry time;

obtaining the object from a media source provided the object is not cached;

caching the object after receiving an Nth request for the object, N being greater than a hit threshold HT, provided there is space available in the cache;

adapting the object into an adapted object according to a destination profile;

determining a normalized hit threshold HT_TN for caching adapted objects, the normalized hit threshold HT_TN being computed by proportionately reducing the hit threshold HT according to an average size reduction of adapted objects with respect to the size of respective objects from which the adapted objects were adapted; and

caching the adapted object provided a number of requests for the adapted object exceeds the normalized hit threshold HT_TN.

2. The method of claim 1, wherein the dynamically adjusting further comprises generating a hits distribution list according to a corresponding number of requests received by each object, and adjusting the hit threshold HT so that objects with the most hits are cached.

3. The method of claim 2, wherein the generating the hits distribution list further comprises:

indexing the hits distribution list by a number of requests received for said each object;

storing at each indexed location of the hits distribution list accumulated sizes of objects having received the number of requests corresponding to the index; and

selecting the highest index, above or including which a sum of the accumulated sizes does not exceed a capacity of the cache, as the hit threshold HT.

4. The method of claim 1, wherein the caching of objects is performed in two phases, a convergence phase and a plateau phase, the convergence phase starting when a first request for an object is received, wherein a convergence cache size threshold is gradually increased at a rate which is a function of an average time to live (TTL_avg) of the objects until the cache size threshold is reached, at which time the plateau phase begins, wherein a plateau cache size threshold is fixed at a level of the convergence cache size threshold, which is reached at the end of the convergence phase.

5. The method of claim 1, wherein the objects are out of band (OOB) objects available from a source, the method further comprising

obtaining the object to be adapted from the cache provided the object was cached, otherwise obtaining the object from the source before adapting the object.

6. The method of claim 5, further comprising determining an average bandwidth saving factor (ABS), the ABS being a function of the sizes of all cached adapted objects which were adapted according to the same destination profile and the sizes of the corresponding OOB objects from which the adapted objects were adapted.

7. The method of claim 3, wherein the dynamically adjusting further comprises adjusting the hit threshold HT as a function of an actual total cache usage, an average size of cached objects, and an average time to live for the objects.

8. The method of claim 2, wherein the hits distribution list comprises hit buckets, each hit bucket for accumulating an object size of each requested object according to a number of requests received for said each requested object.

9. The method of claim 2, further comprising storing expiry times of the object in a time-to-live (TTL) window, wherein the TTL window is divided into a number of TTL buckets, each TTL bucket covering a predetermined time span for storing object descriptors of objects whose TTL expires in said time span.

10. A media adaptation server computer, comprising:

a processor and a cache; and

a self-tuning cache management module for managing the cache, comprising computer readable instructions stored in a memory causing the processor to;

receive a request (hit) for an object having a predetermined expiry time;

obtain the object from a media source provided the object is not cached;

cache the object after receiving an Nth request for the object, N being greater than a hit threshold HT, provided there is space available in the cache;

adapt an object into an adapted object according to a destination profile;

determine a normalized hit threshold HT_TN for caching adapted objects, the normalized hit threshold HT_TN being computed by proportionately reducing the hit threshold HT according to an average size reduction of adapted objects with respect to the size of respective objects from which the adapted objects were adapted; and

caching the adapted object provided a number of requests for the adapted object exceeds the normalized hit threshold HT_TN.

11. The media adaptation server computer of claim 10, the computer readable instructions further cause the processor to generate a hits distribution list according to a corresponding number of requests received by each object, and to adjust the hit threshold HT so that objects with the most hits are cached.

12. The media adaptation server computer of claim 11, wherein the computer readable instructions further cause the processor to:

index the hits distribution list by a number of requests received for said each object;

store at each indexed location of the hits distribution list accumulated sizes of objects having received the number of requests corresponding to the index; and

select the highest index, above or including which a sum of the accumulated sizes does not exceed a capacity of the cache, as the hit threshold HT.

13. The media adaptation server computer of claim 10, wherein the self-tuning cache management module is configured to perform caching of objects in two phases, a convergence phase and a plateau phase, the convergence phase starting when a first request for an object is received, wherein a convergence cache size threshold is gradually increased at a rate which is a function of an average time to live (TTL_avg) of the objects until the cache size threshold is reached, at which time the plateau phase begins, wherein a plateau cache size threshold is fixed at a level of the convergence cache size threshold, which is reached at the end of the convergence phase.

14. The media adaptation server computer of claim 10, wherein the objects are out of band (OOB) objects available from a source, the computer readable instructions further cause the processor to obtain the object to be adapted from the cache provided the object was cached, otherwise obtain the object from the source before adapting the object.

15. The media adaptation server computer of claim 14, wherein the computer readable instructions further cause the processor to determine an average bandwidth saving factor (ABS), the ABS being a function of the sizes of all cached adapted objects which were adapted according to the same destination profile and the sizes of the corresponding OOB objects from which the adapted objects were adapted.

16. The media adaptation server computer of claim 12, wherein the computer readable instructions further cause the processor to adjust the hit threshold HT as a function of an actual total cache usage, an average size of cached objects, and an average time to live for the objects.

17. The media adaptation server computer of claim 11, wherein the hits distribution list comprises hit buckets, each hit bucket for accumulating an object size of each requested object according to a number of requests received for said each requested object.

18. The media adaptation server computer of claim 11, wherein the computer readable instructions further cause the processor to form a time-to-live (TTL) window for storing expiry times of the object, the TTL window being divided into a number of TTL buckets, each TTL bucket covering a predetermined time span for storing object descriptors of objects whose TTL expires in said time span.

19. A method of caching one of a plurality of objects in a cache of predetermined capacity having a cache size threshold less than the predetermined capacity, comprising:

registering a descriptor of each of the plurality of objects in an object registry upon a first request for each object, the descriptor including a respective expiry time for said each object;

storing a reference to each object in a list sorted according to the respective expiry time;

determining an adaptive hit threshold (HT) for caching as a function of the sizes of objects already cached and the cache size threshold, and caching each object after said each object has received more than HT requests;

removing the descriptor of each object from the object registry after the respective expiry time for said each object;

removing each object from the cache after the respective expiry time for said each object;

adapting an object into an adapted object according to a destination profile;

determining an average bandwidth saving factor (ABS), the ABS being a function of the sizes of all cached adapted objects which were adapted according to the same destination profile and sizes of objects from which the adapted objects were adapted;

computing a normalized hit threshold HT_TN as a function of the hit threshold HT and the ABS; and

caching the adapted object provided a number of requests for the adapted object exceeds the normalized hit threshold HT_TN.

20. The method of claim 19, wherein the objects are summarized in a hits distribution list according to a corresponding number of requests (hits) received by each object, and the adaptive hit threshold HT is periodically adjusted so that objects with the most hits are cached.

21. The method of claim 19, wherein the adaptive hit threshold HT is adjusted periodically by a correction amount computed as a function of an actual cache usage C_tot, the cache size threshold C_S, and an expected increase in cache usage C_incr, which is determined as a function of an average time to live (TTL_avg) of the objects.

22. The method of claim 19, wherein the determining the hit threshold HT comprises:

recording a size of each of the objects;

generating a hits distribution array comprising;

indexing the hits distribution array by an index representing a number of requests received;

storing at each indexed location of the hits distribution array a size sum of sizes of all objects having received the number of requests corresponding to the index; and

selecting as the hit threshold HT the highest index above which a sum of the size sums does not exceed the predetermined capacity of the cache.

23. The method of claim 22, wherein the objects are out of band (OOB) objects available from a source, the method further comprising

obtaining the object to be adapted from the cache provided the object was cached, otherwise obtaining the object from the source before adapting the object.

24. A media adaptation server comprising a self-tuning cache management sub system for processing requests for caching objects in a media cache, the system comprising:

a processor, and a non-transitory computer readable storage medium having computer readable instructions stored thereon for execution by the processor, forming;

a caching control module for determining caching of objects, and operating in combination with data structures, the caching control module comprising;

an object registry for identifying and registering objects;

a hit buckets array of hit buckets for storing accumulated sizes of registered objects, and indexed by a hit number which corresponds to a number of requests (hits) each registered object has received;

a hit threshold register for storing an adaptively determined hit threshold (HT) specifying a minimum number of hits after which an object is cached;

a time-to-live (TTL) window list for storing expiry times of respective registered objects;

a timer for determining an occurrence of times for removing registered objects from the object registry and from the cache;

a terminal profiles database, and an adaptation engine for adapting registered objects into adapted objects for transmission to media clients, the adaptation for each media client being performed according to a terminal profile stored in the terminal profiles database;

the caching control module further comprising readable instructions for execution by the processor for;

determining a normalized hit threshold HT_TN for caching adapted objects, the normalized hit threshold HT_TN being computed by proportionately reducing the hit threshold HT according to an average size reduction of adapted objects with respect to the size of respective registered objects from which the adapted objects were adapted; and

caching the adapted object provided a number of requests for the adapted object exceeds the normalized hit threshold HT_TN.

25. The media adaptation server of claim 24, wherein each hit bucket of the hit buckets array is used to store a sum of sizes of only those registered objects which have received the number of hits, the number of hits being the value of the index of the corresponding hit bucket.

26. The media adaptation server of claim 25, wherein the hit threshold HT is determined by:

successively indexing the hit buckets array starting at the highest index;

summing contents of the indexed hit buckets until a predetermined cache size threshold is exceeded; and

setting the hit threshold HT to the last index.

27. The media adaptation server of claim 24, wherein the TTL window is divided into a number of TTL buckets, each TTL bucket covering a predetermined time span for storing object descriptors of registered objects whose TTL expires in said time span.

28. The media adaptation server of claim 24, wherein the normalized hit threshold HT_TN is computed by taking into account only registered objects and adapted objects that are already cached.

29. A self-tuning cache management system for processing requests for caching objects in a media cache, the system comprising:

a non-transitory computer readable storage medium having computer readable instructions stored thereon for execution by a processor, causing the processor to perform functions of;

registering requested objects upon respective first requests for the requested objects in an object registry, including a time to live (TTL) for each requested object;

accumulating an object size of each requested object in hit buckets according to a number of requests received for said each requested object;

storing a hit threshold (HT) in a hit threshold register, the HT determining a minimum number of requests any of the requested object must have before the requested object is cached;

listing the requested objects in a TTL window according to respective expiry times according to the TTL of said requested object;

scanning the TTL window and removing requested objects from the object registry when the requested objects are expired, furthermore removing the requested objects from the cache provided the requested objects had been cached;

adapting an object into an adapted object according to a destination profile;

determining a normalized hit threshold HT_TN for caching adapted objects, the normalized hit threshold HT_TN being computed by proportionately reducing the hit threshold HT according to an average size reduction of adapted objects with respect to the size of respective objects from which the adapted objects were adapted; and

caching the adapted object provided a number of requests for the adapted object exceeds the normalized hit threshold HT_TN.