Re: approximate LRU in UFS

On Fri, Mar 30, 2001, Andres Kroonmaa wrote:
>
> This makes me think of LRU-like FIFO-fs. We could have an array of
> pointers to storeentry's indexed by swap_filen. Storedb is passed
> in a FIFO circular manner, overwriting anything that was under.
> LRW (W - written) removal policy with 1 pointer per storeentry.

Oh. Thats basically COSS.

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

> To avoid swap_filen array, we could put whole storeentry db into
> array. Perhaps divide it into chunks, and those chunks could well
> be as large as L2 dir can hold. Having storedb in array would be
> good, as it is the most memory waster due malloc alignment anyway.

Thats what I was thinking.

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

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

Blah. After I get COSS and the other FS code tidied up, I'll give
implementing this a go. :-)

Adrian

-- 
Adrian Chadd		"The fact you can download a 100 megabyte file
<adrian@creative.net.au>  from half way around the world should be viewed
			    as an accident and not a right."
					-- Adrian Chadd and Bill Fumerola