[Fwd: Re: Squid store replacement policies]

Damn domain change ;-) Accidenly Cc'd this to squid-dev@ircache.net..

attached mail follows:

John Dilley wrote:
>
> The policy API looks pretty good to me (although the C++ style may make some
> squeamish, I'm not one of them :).

Object orientation is required to make it pluggable without having to
teach each and every store each and every policy. The style is about the
simplest and cleanest model of object orientation you can get in C
without turning to another language.

> I think the abstractions are good ones.
> I'm not really comfortable with adding an "entry" to a "policy"; rather I
> think the policy controls how objects are removed from the persistent store.
> I prefer to think in terms of adding an entry to a store, at which time the
> replacement policy associated with that store places it appropriately in the
> eviction queue. But the abstractions are the same...

I agree that the terminology is perhaps not the best, but I didn't find
any better ;-). However, to put you in the picture the API defined is
between the (persistent) store and the policy.

> > First question is if there is any other hints a replacement policy needs
> > to know? (other than the object info in StoreEntry, and access
> > references)
>
> For the frequency-based policies this is all that was needed (I adjusted the
> heap key and reordered the heap everywhere refcount was incremented). The
> policies I implemented used only size, frequency, and recency information in
> calculating the key.

Good.

> > I don't think LRU requires any other hints, but what about the heap
> > based policies, and other ideas for interesting algorithms?
>
> Other interesting algorithms use a "cost" function where cost can be
> determined by several factors including server response time or bandwidth
> cost.

All this is rather static information known when the object is added in
the first place isn't it (and probably deduceable from the StoreEntry)?
Also, if Squid knows about it then should be quite easy to look it up.
However, it also affects what needs to be stored in the persistent index
in order to be able to rebuild the policy after a restart..

> It would be nice if the walker could walk the object list in either order.
> Currently I presume the walker returns objects from least to most valuable
> (i.e., recent, frequent, or whatever). Going the other way is nice, too. The
> LRU list is walked from least to most when evicting, but most to least
> valuable when writing swap.state.

The API definition so far have two walkers. One which returns the
objects to be deleted, and another which simply walks the list of
objects without removing them. I did not originally include any
information on in which order the second walker should return the
objects, but I have since then desided that the API will define this
walker to return the objects in an order suitable for rebuilding the
policy. It's primary use is when writing clean persistent indexes.

If other types of walks are needed this can be added by simply adding
another method in the policy API, but I am currently trying to keep the
size of the API down as much as possible to simplify the policy
implementation.

> Unfortunately, doing this efficiently with a heap is difficult. Also keeping
> track of where you are with a heap iterator becomes very hard if there are
> calls that update the heap between the purgeInit and done. Given Squid's
> synchronous replacement model (where objects are replaced and then you go
> back to serving requests) this is fine. But in a new (say, threaded) model /
> architecture this might not be the case ... This is an implementation
> detail but a potentially significant one.

Yes, I know about this. It is an potential issue already, but for the
time being Squid only walks the policy while all request forwarding is
disabled (during log rotate or shutdown).

> (Minor nit: all of the API decls except free() include the "object" as the
> first parameter; they should be consistent.)

Thats a typo. Thanks for the correction.

/Henrik
Received on Mon Apr 24 2000 - 17:36:34 MDT