Re: memory-mapped files in Squid

From: John Dilley <jad@dont-contact.us>
Date: Wed, 03 Feb 1999 08:26:50 -0800

> > I think this is going to be a big part of the tuning for the cyclic
> > fs - how do you deal with, for instance, the next MS service pack -
> > 50Mb of heavily-hit object. Personally, re-writing objects on hits
> > doesn't give me warm fuzzy feelings...
>
> I would probably use a rewrite rate limit of 30%. It the object are in
> the newest 30% of the store, then don't rewrite it to the head.

        We've found a partitioned policy for cache replacement can work
better than a single policy alone. In this case it seems we could use
two policies to handle two distinct parts of the working set:

  1. The FIFO policy is optimized to handle writing many objects to
      disk as efficiently as possible. This matches the proxy cache
      workload, which consists of more writes than reads (in aggregate);
      furthermore most objects (over 50%) are never re-referenced, so
      they should be sent to disk and forgotten about as quickly as
      possible. Circular FIFO appears to accomplish this nicely, and
      can be optimized to lay out objects very efficiently with regards
      to disk blocks (as discussed here earlier).

  2. If an object is re-referenced it is possible it will become part
      of the hot object set. In the proxy workload some objects are
      very popular, hence Squid's main-memory hot object cache. A
      separate cache partition for popular objects with a frequency
      based replacement policy can improve the byte (and object) hit
      rate of the cache without degrading performance.

        Basically when objects are first added to the cache (cold miss)
they are added to the FIFO. If they are re-referenced, they are moved
to a separate cache partition. The move can be "logical" by adjusting
the cache metadata and leaving the data in the FIFO until "disk quite
time", or until it is about to be replaced.

        In this way the extra writes of Henrik's option 1, below, are
avoided some of the time. In addition, the popular objects can be
maintained with a replacement policy that works better than FIFO for
popular objects.

        A key question is how much better is a partitioned policy than a
simple FIFO policy on a real proxy cache workload? Does the improvement
justify implementation of a separate cache partition? Does this mixed
policy help alleviate the cache bottleneck (disk access)?

> > Except if you've already incurred the overhead of writing to disk, why
> > incur it again?
>
> As I see it there are three options in a cyclic file system:
>
> 1. Rewrite reused objects when reused, with a limit on by which rate the
> object is rewritten to the head.
> Penalties:
> * extra writes
> * changing store index numbers.
>
> 2. When rewriting a store chunk, preserve those objects that we are
> interested in keeping, but pack them together.
> Penalties:
> * extra reads
> * extra writes
> * no obvious way to determine what to keep and what to throw away
> * changing store index numbers.
>
> 3. When rewriting a store chunk, preserve those objects that we are
> interested in keeping where they are in the chunk.
> Penalties:
> * fragmentation
> * no obvious way to determine what to keep and what to throw away.
>
> Currently I think 1 is the way to go, but 2 or 3 allows for a more
> flexible or customisable replacement policy.

...

> > There's definately some nifty ideas there, but I'm not convinced that the
> > gains from a cyclic fs over a more traditional style fs are enough to warrant
> > the extra management complexity - shuffling objects around on disk, etc.
>
> I wouldn't say that there is much extra management complexity, but I
> admit that some of Squids interfaces does not fit well.

        I would encourage anyone looking into circular FS implementation
not to shuffle data around. One value of the FIFO approach is that data
are streamed to disk as efficiently as possible, thus alleviating the
disk bottleneck. I don't fully understand the impact of subsequent
(random access) reads of data from the FIFO, but as noted earlier,
another cache structure may make sense for the popular objects.

                             -- jad --
                          John Dilley <jad@hpl.hp.com>
Received on Tue Jul 29 2003 - 13:15:56 MDT

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