Re: approximate LRU in UFS

On 30 Mar 2001, at 18:50, Adrian Chadd <adrian@creative.net.au> wrote:

> > To mimic LRU better we could note storeentry's lastref time, and
> > if it is fresher than some threshold, skip that entry from removal.
> > Or we could rewrite the object at the head of FIFO, as has been
> > proposed with FIFO-fs (this could even work ok with small objects).
>
> Then you have to keep walking the StoreEntry's, which can become
> a long process. On a very busy cache, who knows?

 You mean to find releasable object? You walk array of swap_filen, all
 the time. I imagine like VM systems walk ram, with two-handed clock,
 one hand pointing at next free slot, where new items are added, and
 other hand moving along old objects releasing enough disk to keep
 free space within limits. Constant action, very small overhead per
 run. Given that hitrate is low and reuse rate makes it even more,
 probability of hitting stale object every time is very high.

> > I don't think deleting entire L2 directory is a good thing. I don't
> > quite see what you meant by "average LRU of the dir", but it sounds
> > like needing regular "average" computations and sorting of the list.
> > But mainly I dislike that we again are prone to loosing hot objects
> > that produce lots of hits, as pure FIFO-fs is. 10% of objects can
> > produce over 50% of hits. I feel like we still need to have removal
> > policy that works per item, not per some group of items.
>
> Perhaps some way needs to be found for objects that have high
> hit rates to be placed in similar-hitrate "buckets".

 Too "intelligent"? I think it would be tough job. We'll end up with
 removal policy other than LRU.

> > Basically we talk about the same thing, but I'd suggest to avoid
> > blowing away whole L2, but only objects that we consider LRU.
>
> I'd like to avoid it too, however my suggestion is targeted to cut
> down the RAM requirements.

 well, we can reduce number of cached objects. Reducing hitrate is
 equal to that. I wonder if it is worth reducing ram usage at a cost
 of reduced hitrate.

 Imho, least ram consumes array that is filled always from ground up,
 and cleared in whatever fancy order.

------------------------------------
 Andres Kroonmaa <andre@online.ee>
 CTO, Delfi Online
 Tel: 6501 731, Fax: 6501 708
 Pärnu mnt. 158, Tallinn,
 11317 Estonia
Received on Fri Mar 30 2001 - 05:01:22 MST