Collaborative caching for multitenant solutions:

 With the case study for developing a multitenant solution for the delivery of user generated content to designated audience, different algorithms are required to tune the system for higher performance. These include collaborative caching, context aware streaming, user redirection, distribution tree etc. This section discusses one of them.

Content caches are strategically located through the network which support services with optimally distributing the content from its source to its consumers. Collaborative caching allows software to use hints to influence cache management. When the hints are about the inclusion property, optimal caching can be achieved if the access sequence and cache size are known beforehand. An example of such a hint could be a binary choice between Least Recently Used Algorithm or Most Recently Used Algorithm. Another way a hint could be provided is with a number encoding a property. The result is a new algorithm that can be described as priority LRU and captures the full range between MRU and LRU.

Hints are added by annotating each memory access with a numerical priority. Data accessed with a higher priority takes precedence than data accessed with a lower priority. Collaborative caches enable the caller to specify the importance and the system to determine the priority to manage the data. LRU/MRU used to infer this importance but with a sliding scale priority specified by the caller, a new type of inclusion – non-uniform inclusion becomes possible.

The word inclusion derives from the hierarchy of caches at the machine level namely L1, L2 and so on. The property states that the larger cache will always contain the content of the smaller cache. Generally, a stack data structure is used to visualize hits and misses in play. The stack distance is a useful metric derived from the stack simulations such as for LRU and denotes the amount of data accessed between consecutive re-uses of the same entry and suggests system locality. Data elements at the top c stack positions are the ones in a cache of size c. The stack position defines the priority of the stored data. All accessed data are ordered by their priority in a priority list. The stack distance gives the minimal cache size to make an access, a cache hit and is calculated by simulating such a cache of an infinite size. In the simple LRU case, the data is prioritized by the most recent access time.  The data in a MRU cache is also prioritized by the most recent access time but unlike LRU, the lowest priority is the data element with the most recent access time.  The LRU-MRU can also be mixed where a hint indicates whether the access is LRU or MRU.  Its stack distance would be computed by the stack-based algorithm by assigning the current access time as priority for LRU and corresponding negation for the MRU. The priority hint changes the default scheme.

The effects of the priority hints on cache management include 4 cases for cache hits and 2 cases for cache miss. Consider the access to w with a priority i, (w,i) arriving in a cache of size m, and the current stack position j. The change in priority leads to the item moved up, not at all or moved down in the stack of m items and the move is just conceptual pertaining only to the organization in the stack.

These cases include:

1.       1 <= i < j <= m and w is found in the cache which leads to hit up move where item moves up to position i and the entries from i to j-1 move one position lower.

2.       1 <= j  = i <= m and w is found in the cache which leads to no movement

3.       1 <= j < i <= m and w is found in the cache which leads to hit down move where the item moves down to position I and the entries j+1 to I move one position higher.

4.       1 <= j <= m < I and w is moved out of the cache and the entries from j+1 to m are moved one position higher. This is a voluntary eviction.

5.       j = infinity and 1 <=i and <= m and the accessed data element w is missed from the cache and moved into the position at I and all entries move one position lower. The lowest priority entry is evicted.

6.       J = infinity and i > m which results in a miss bypass and the entries in the cache are unaffected.

This way the priorities stated in the hints and those implied in the access sequence is reconciled.