0

There are many parallel requests for elements in a collection. There are more elements than there are cache slots. All of the parallel requests request all of the elements in the collection, at slightly different times. The elements are immutable and have unique names.

If the cache size is smaller than number of the elements in the collection (as it is now), cache misses are a problem. I predict cache thrashing occurs from an even distribution of requests for different elements. The cache currently uses LRU. I haven't tested other cache algorithms. Thinking through most of them, I predict thrashing would would also occur.

What are good cache algorithm options for this scenario?

This is a web application, which is where the slight difference in timing comes from. Many users are requesting the same collection of elements, close to the same time.

1 Answer 1

0

How do you know that LRU isn't an effective caching algorithm? Are you keeping statistics on cache utilization (hits, misses, etc...)?

Choosing a cache algorithm is primarily choosing the algorithm that best approximates the need for elements immediately prior to request. In the abstract, you generally want the elements sorted at request and eviction time. Perfect caching essentially means you have an oracle that knows exactly what will be needed and when.

So the question is really, what describes how elements are needed in the cache, or what f(x) best approximates need at a given time? With LRU, f(x) = t where t is last access time, MRU f(x) = 1/t or f(x) = -t, LFU f(x) = n where n is number of times accessed, etc...

From what you describe, the collection of elements accessed are likely to be needed again within a short duration of time, so I would think using LRU and grouping by the collections should already be reasonably effective.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.