[Fwd: Re: Squid store replacement policies]

And the response from John Dilley, which because of me also was sent to
the wrong (old) address.

/Henrik

attached mail follows:

The policy API looks pretty good to me (although the C++ style may make some
squeamish, I'm not one of them :). 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...

> * Hint to the policy that an object is/has been referenced
>
> policy->referenced(policy, entry)
>
> 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.

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

> Second question is if I have forgotten anything obvious (or less
> obvious) in the API definition above, or added anything which does not
> belong there?

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.

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.

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

> Note: I do not intend to have the store policy determine when space
> needs to be recaimed or how much. This is up to the storage directories
> to handle. The job of the storage policy is solely to determine in which
> order the objects are deleted.

I agree that this is the right philosophy. When the replacement policy runs
to get space it needs to get a list of things to remove, but should not know
how that list is determined. When returning objects to remove the walker
should not care how much space is needed.

Regards,

-- jad --
John Dilley
jad@akamai.com
Received on Mon Apr 24 2000 - 17:42:39 MDT