Re: approximate LRU in UFS

 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.

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

 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.

 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.

 Basically we talk about the same thing, but I'd suggest to avoid
 blowing away whole L2, but only objects that we consider LRU.

On 25 Mar 2001, at 0:53, Adrian Chadd <adrian@creative.net.au> wrote:

> We can take a storeentry, and figure out which L1/L2 directories
> it sits in based on its swap_filen.
>
> So, imagine assigning the LRU position to the actual L1+L2 directory.
> Instead of holding each StoreEntry in an LRU, we hold the directories
> in an LRU.
>
> So, when we need space, we just pick the least-recently used
> directory, which contains an average LRU of the entire dir, and
> blow it away.
>
> The trick here is to be able to delete an entire directory of
> objects whilst deleting the relevant StoreEntry's. We can't lookup
> a StoreEntry by swap_filen since the current index is by method/URL.
> Can anyone think of a neat way to purge an entire directory
> of objects *AND* the StoreEntry's of those objects at the same
> time?
>
> If we manage to do this, we'd be able to save quite a few bytes off
> the StoreEntry struct..

------------------------------------
 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 - 01:10:35 MST