Re: memory-mapped files in Squid

 Although we already perhaps all agree that fifo can be trivially changed
 into LRU-like replacement policy, I'd like to point out few bits that
 still seem to be missed in regards to replacement policies.

While talking of pure FIFO-based replacement,
On 28 Jan 99, at 10:12, Alex Rousskov <rousskov@nlanr.net> wrote:
> On Thu, 28 Jan 1999, Andres Kroonmaa wrote:
>
> > Of 100% fresh objects that we fetch, some part will survive a cycle.
>
> Correct me if I am wrong, but the recommended LRU expiration age is 3 - 7
> days. The "cycle" is not something short. If a cache receives 3GB of
> cachable traffic per day and has 30GB disk cache, it would take 10 days to
> complete a cycle (just an example). If an object was not referenced twice
> in 3-7 days, it is useless with a very high probability.

 But given 10K average object size and 3G per day, it makes about 300K reqs
 per day. I'd like to see the cache manager who allocates 30G of disk
 for this small workload (even nowadays). if you also count the current
 RAM needs for such a box, it will be way far from cheap cache box.

 And if we have say 30G/day, to have a expiration age of 10 days, we'd love
 to have 300G of disks? What if we target 60 days for zillions of .gifs?

 LRU is a lovely hack that works amasingly well "inspite of common sense" ;)

 But it is totally based on locality, and it is awfully dumb.
 As long as we compare hit-counts or even dumb hit-bytes, it beats most
 other policies or is pretty close.

 But if you attach a price-tag for bytes or counts, it does not fit too
 well anymore. Suppose you need to have $$$/G saved, based on inter-ISP
 peering costs? would LRU fit at all? Or if you need RTT-mSec/G saved?
 LRU is "one-fits-all". But is doesn't fit all.
 It might be way cool to see 30-60% hitrate on URLs to your local web
 server, but it really gives anyone very little benefit, isn't it?
 If a really cheap object gets into cache, and it is popular, LRU will
 not drop it, it would rather drop all the rest. Is that smart?

 We need more inteligent replacement policies not to increase hit-rate,
 but to increase a value per hit, value per GB kept.

> Thus, FIFO may work for most of reasonably configured caches, especially
> if augmented with a small buffer for popular objects (say, those
> referenced at least twice).

 Small buffer would be 30-40% of my disk space. Of 30G it makes 10G.
 I wouldn't call it small, and I wouldn't call maintaining it trivial.

 But FIFO can be converted into LRU, and the lovely hack comes in.
 And I'd agree it is much easier to use fifo/LRU, although it may be
 much harder to include some other criteria based policies later...

> > Some part is expired long before. But just this part that survives is
> > what increases squid' hit/miss ratio, and we want to keep it. The
> > other part is a waste, and we'd want to replace it first.
>
> For a lot (most?) of reasonable configurations, it does not matter much
> what you are replacing as long as that stuff is several days old. The
> latter is the reason why all "traditional" caching policies perform the
> same on any reasonable size cache. Essentially, you are selecting between
> old garbage and very old garbage.

 If you ever need to pay $0.25 per 10K gif, you'd start thinking totally
 different. (its just example, but it exactly illustrates those who fight
 with payperbyte).

 Old (or very old) is not equal to garbage. Only if this "old" becomes
 more costly to keep than refetch do we assign it a tag of garbage.
 Determining the point of when it becomes more costly to keep is the
 whole point of different replacement policies.

 Last reference time is simplest of all, but it has nothing to do with
 any kind of _cost_.

> > 1) we want to have our disks as full as possible. 90% at least.
> > 2) we want that these disks are full of _useful_ stuff, not waste.
>
> Sure. However, none of the traditional policies caches useful data! All
> traditional policies that I know of fill cache with garbage, on average.
> Provided your cache is of a reasonable size, of course.

 Sure.
 But its not a matter of caching useful data or garbage. Its a matter
 of _keeping_ useful data and _dropping_garbage_. Please note the difference.

 LRU does that. It picks (what it thinks)useful data to keep, and ignores
 the rest. The only criteria is "last-reference". It just happens so that
 the rest gets dropped if not referenced intime. This is the charm of its
 simplicity. But this is also its dumbness.

 FIFO byitself does not do anything to keep useful data. It just happens
 that with 4-10 times the same amount of disk we have comparable hitrate
 as with LRU.

> The real challenge is avoid caching waste in the first place. And not to
> reduce disk space requirements, but to decrease disk _bandwidth_
> contention and hence speedup hits.

 No, we can't avoid caching waste. For that we'd need to "see" the future.
 We can try to predict it, but we can never be exactly right.

 And NO, not to decrease the _disk_ bandwidth or increase the hits, but to
 reduce the _cost_ of (international) network traffic and thus being able to
 purchase higher bandwidth links. Sure, collapsing cache box is worth little,
 but you can feel the difference in interests. Fast cache box is very cool,
 but disk-space-effective box might be much more important to some.
  
> > So, we have to look at allocation algorithms that integrates both
> > 1) intelligent replacement policy
> > 2) and does not suffer speed loss at high disk utilisation.
>
> IMO, all reasonable _replacement_ policies will perform the same no matter
> how intelligent they are. I have not seen a single study that shows an
> alternative super intelligent policy outperforming LRU-TH by a significant
> margin on a reasonable size cache.

 I hope I have succeeded to explain myself by now.

 * hit-rate is not everything.

 I agree that LRU performs well. Intelligent? No.
 Who needs this intelligence? Those who count bits and bytes in bucks.

> We may need an intelligent _caching_ (or cache admission) policy, but I am
> afraid we are not ready for that yet.

 In fact we were, sort of, in squid 1.0, by means of ttl_patterns... ;-)

 ----------------------------------------------------------------------
  Andres Kroonmaa mail: andre@online.ee
  Network Manager
  Organization: MicroLink Online Tel: 6308 909
  Tallinn, Sakala 19 Pho: +372 6308 909
  Estonia, EE0001 http://www.online.ee Fax: +372 6308 901
 ----------------------------------------------------------------------
Received on Tue Jul 29 2003 - 13:15:56 MDT