Re:Re: Comments conflicts with codes in HeapKeyGen_StoreEntry_LFUDA

Thanks, Yee pal!

I still have a question, I think the object that has the
minimal key value (not the maximal value) will be purged out
from cache. Am I correct?

Another question, you mentioned,
/////////////////////////////////////////////////////////
The algorithm I used is to set the age to the heap key of
the most recently evicted object. The key will grow over time
/////////////////////////////////////////////////////////

I do not understand why "The key will grow over time" if the
algorithm is described as before. Can you give me a simple
explanation?

Best regards,
George Ma

----- Original Message -----
From: Yee Man Chan
To: maer727@sohu.com ;squid-dev@squid-cache.org
Cc: squid-dev@squid-cache.org
Subject: Re: Comments conflicts with codes in HeapKeyGen_StoreEntry_LFUDA
Sent: Wed May 29 02:15:28 CST 2002

>
> --- maer727@sohu.com wrote:
> > Here are the comments taken from the above of the
> > function,
> > HeapKeyGen_StoreEntry_LFUDA.
> > ///////////////////////////////////////////////////
> > but with aging to handle turnover of the popular
> > document set
> > ///////////////////////////////////////////////////
> >
> > Here are the codes taken from the same function,
> > ///////////////////////////////////////////////////
> > key = age + (double) e->refcount - tie;
> > ///////////////////////////////////////////////////
> >
> > I think age means how long the object has been in
> > cache.
> > And if an object has a minimal key value then the
> > object will be purged out from cache. Am I correct?
> >
>
> Wrong. age is the age of the heap. *Not* the age of an
> object.
>
> > The comment says that the purpose of LFUDA algorithm
> > is to
> > let the hot objects has less ability to stay in
> > cache. Am
> > I correct?
> >
>
> What is "ability"?
>
> I asked a similar question to John Dilley (the guy who
> wrote this part of code) and here is his reply.
> ---------------------------------------------------
> The heap age is a technique to prevent frequency- or
> refcount-based
> policies
> from perferring formerly popular objects over newer
> objects. Imagine an
> object that got a thousand hits a week ago and a
> policy that computes
> heap
> key using refcount/size. The thousand hitter will
> never be evicted.
>
> However if you "age" all of the objects in the cache
> by, say, dividing
> their
> key by some constant (say 2) or subtracting some
> constant value from
> their
> key periodically then formerly-popular objects can be
> evicted. A naiive
> approach would walk the cache and touch each object
> but this is very
> expensive when there are millions of objects in the
> cache.
>
> Instead, the subtraction can be accomplished by adding
> a "heap age" to
> each
> key when the key is computed (an object added or
> updated). So if the
> key
> calculation is performed thus:
> key = refs/size + age
> you can easily see that incrementing the age by X
> before adding a new
> object
> to cache has the same effect as decrementing all
> previous keys by X.
>
> There is a choice of how to compute age. The algorithm
> I used is to set
> the
> age to the heap key of the most recently evicted
> object. The key will
> grow
> over time, so it was made a float.
> ------------------------------------------------
>
> Cheers,
> Yee Man
>
>
> __________________________________________________
> Do You Yahoo!?
> Yahoo! - Official partner of 2002 FIFA World Cup
> http://fifaworldcup.yahoo.com
Received on Tue May 28 2002 - 21:49:16 MDT