Puzzled at the replacement policy LFUDA.

Hi,

I think age means the time when last object is purged
from cache. And the LFUDA algorithm is to prevent
objects that were popular in the past but not popular
now from taking much cache spaces. But I think sometimes
the algotithm does not work as it is expected to
do. For example, object A was popular in the past but
not popular now. Object B is popular now. The formular
used in LFUDA is

key = age + (double) e->refcount - tie;

And the object that has the minimal value of key will
be purged out from cache.

When we decide which object to be purged, we calculate
the formular like this, The age value means the time
when last object is purged from cache. So object A
and object B has the same value. ( maybe last time an object
C has been moved from cache ) Am I correct?

And the value e->refcount of object B is greater than
that of object A. So, even if object B is not popular
now, the object will still has a greater value. And A will be
purged. Am I correct?

What puzzled me is when the key value will be re-calculated for the same
object and when the key value of the same object will be refreshed. I have
read the FAQ of squid on LRU and the paper written by HP on LFUDA. IMHO, I
think when the in-cache object is accessed again, the key value will be freshed.
But I am not sure about it. Am I correct?

Can you give me a simple explanation?

Best regards,
George Ma
Received on Tue May 28 2002 - 23:26:24 MDT