Re: Puzzled at the replacement policy LFUDA.

maer727@sohu.com wrote:

> I think age means the time when last object is purged
> from cache. And the LFUDA algorithm is to prevent

No, the heap age has nothing to do with time. It is purely an artificial
value that is guaranteed to increase over time. Any future heap ages are
guaranteed to be greater than or equal than the current (applied
recursively).

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

As this calculation includes the heap age, the object which was popular
in the past will have it's priority decreased as new objects are being
inserted (or actually other objects being deleted).

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

Yes, which will be the object which haven't been used for a long time if
there is many more recent objects, assuming your cache is full, and has
been full for a while causing the heap to age. (the heap do not age if
no objects is being evicted)

> 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?

The decision is purely based on what keys the objects got assigned when
they last entered the heap.

> 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?

The key is not recalculated while purging objects. The key is only
calculated when the object enters the heap, or the object has been
toched.

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

When the object has been used. Objects not being used stay with their
last assigned key.

> 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?

Yes.

Regards
Henrik
Received on Wed May 29 2002 - 16:51:28 MDT