METHOD AND SYSTEM FOR SELF-TUNING CACHE MANAGEMENT

• US 20140068196A1
• Filed: 08/28/2012
• Published: 03/06/2014
• Est. Priority Date: 08/28/2012
• Status: Active Grant

• Current Assignee: Masimo Corporation
• Original Assignee: Louis Benoit, Robert Buchnajzer, Sebastien Cote
• Inventors: CT, Sbastien, BENOIT, Louis, BUCHNAJZER, Robert
• Granted Patent: US 9,112,922 B2
• Time in Patent Office: Days
• US Class Current: 711/135
• 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-34. -34. (canceled)

35. 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;

dynamically adjusting the hit threshold HT as a function of available cache space; and

removing the object from the cache after the predetermined expiry time has passed provided the object was cached, thereby making space available in the cache.

36. The method of claim 35, 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.

37. The method of claim 36, 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.

38. The method of claim 35, 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.

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

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

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.

40. The method of claim 39, further comprising 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 they were adapted.

41. The method of claim 40, 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 they were adapted.

42. The method of claim 37, 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.

43. The method of claim 36, 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.

44. The method of claim 36, 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.

45. 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;

dynamically adjust the hit threshold HT as a function of available cache space; and

remove the object from the cache after the predetermined expiry time has passed provided the object was cached, thereby making space available in the cache.

46. The media adaptation server computer of claim 45, 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.

47. The media adaptation server computer of claim 46, 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.

48. The media adaptation server computer of claim 45, 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.

49. The media adaptation server computer of claim 45, wherein the objects are out of band (OOB) objects available from a source, the computer readable instructions further cause the processor to:

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

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.

50. The media adaptation server computer of claim 49, wherein the computer readable instructions further cause the processor to 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 they were adapted.

51. The media adaptation server computer of claim 50, 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 they were adapted.

52. The media adaptation server computer of claim 47, 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.

53. The media adaptation server computer of claim 46, 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.

54. The media adaptation server computer of claim 46, 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.

55. 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 respective object, the descriptor including a respective expiry time for the corresponding 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 only after it has received more than HT requests;

removing the descriptor of each corresponding object from the object registry after its expiry time; and

removing each object from the cache after its expiry time.

56. The method of claim 55, 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.

57. The method of claim 55, 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.

58. The method of claim 55, 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.

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

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

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.

60. The method of claim 59, 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 OOB objects from which they were adapted;

computing a normalized hit threshold HT_TN as a function of the hit threshold HT and the ABS according to the destination profile;

caching the adapted object provided the number of requests for the requested object to be adapted exceeds the normalized hit threshold HT_TN.

61. 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 comprising executable instructions 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; and

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

62. The media adaptation server of claim 61, 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.

63. The media adaptation server of claim 62, 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.

64. The media adaptation server of claim 61, 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.

65. The media adaptation server of claim 61, further comprising 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.

66. The media adaptation server of claim 65, the caching control module further comprising executable instructions 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 they were adapted.

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

68. 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;

adjusting the HT periodically according to a cache fill;

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

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.