Re: modules

From: Alex Rousskov <rousskov@dont-contact.us>
Date: Mon, 31 May 1999 17:49:44 -0600

On Mon, 31 May 1999, Terence Kelly wrote:

> I'm aware of exactly one
> widely-cited paper that deals with reasonable cache sizes: Rizzo &
> Vicisano's "Replacement Policies for a Proxy Cache". They use the
> DEC trace (22M requests before filtering) and simulate up to 10GB.

Sigh. I was hoping for something fresh. 1996 DEC traces are getting quite
old. Also, I do not recall _significant_ improvements over LRU in their
paper, but apparently I have to re-read it.

> In my WCW99 presentation I showed data on cache sizes up to 8GB on
> two-week NLANR request streams of 5-7 million requests. Now I'm
> working with six 28-day NLANR request streams, each of which contains
> between 10 and 35 million requests. I'm simulating caches up to
> 32GB. My data show that LFU with an aging mechanism offers
> substantially higher byte hit rates than LRU; for instance, on our
> largest trace, an 8GB LRU cache gives you a 51% BHR whereas LFU gives
> you 55%. I'll have a paper ready for submission in a few weeks.

Hmm.. Except UC and SD (which are special), NLANR caches get ~15% byte hit
ratio (max 25%) despite cache sizes larger than 8GB. Either you are not
accounting for updates, reloads, expirations etc. or Squid LRU is *really*
far from classic LRU. Based on statistics reported by other cache admins, I
would suggest the former (not too many people can brag about 50% BHRs
without violating HTTP and doing other extreme optimizations). Note that
NLANR caches (or traces) have even lower than average hit rates because of
our location in the hierarchy.

> Are the Squid developers interested in replacement policies
> well-suited to small (RAM-sized) caches? Would you consider using
> two different removal policies, one to manage the Squid "Hot Object"
> in-core store and one to manage the overall cache?

I would be interested in a symbiosis that does not optimize hit ratios
(just keeps them about as high as LRU or higher), but rather reduces number
of disk writes. I have such an algorithm that performs well in simple
simulations, but had no time to try it in practice.

Alex.
Received on Tue Jul 29 2003 - 13:15:58 MDT

This archive was generated by hypermail pre-2.1.9 : Tue Dec 09 2003 - 16:12:09 MST