Re: Squid store replacement policies

From: Henrik Nordstrom <hno@dont-contact.us>
Date: Tue, 25 Apr 2000 19:29:03 +0200

Alex Rousskov wrote:

> If that is the choice, I suggest that it is not only documented, but
> _enforced_. That is, policy/store API should
> assert(number-of-pending-index-walkers == 0)
> in functions that modify the store. Why should the result be undefined?

This is entirely up to the policy. The effect is undefined and may well
be an assert if the policy implementator feels it is a good thing. The
API definition as written does not stop a storage policy from having
these asserts, neither does it force the policy to have one.

> The "atomicity" requirement will make the "purge" walker cumbersome to
> implement, because that walker is suppose to purge objects from the
> cache. In my experience, it is better not to provide a "purge" walker
> at all I found it much easier to add a
> entry = policy->nextVictim()
> interface instead.

The reason why it is a walker is because the policy might need to
maintain some special state while the purge is taking place. For example
locked objects might need to be moved out of the way of the purge and
then reinserted when the purge has finished. The most efficient way to
do this varies with the different policies and is why it is contained in
the policy and not the generic code.

> N.B. In your model, "theIndex" and "thePolicy" may be the same, I am not
> sure.

The policy does not replace the main store index we have based on the
MD5 hashes. Only the LRU list (or heap).

> Note that the only purpose of any walker (aka iterator) is to maintain
> some "state" of the iteration process. In removal policies that I am
> aware of, maintaining a state (especially in an object separate from the
> policy itself!) is either (a) not needed or (b) extremely difficult.

In this case it is required to maintain special state by at least the
heap based policies.

> the policy. On the other hand, with algorithms that use object size and
> disk placement, a removal of a single object may change the "value" of
> many objects at once; the "state" is then essentially an entire store
> table. If there is no state we want to maintain in a separate object,
> there is no need for a walker

That is up to the policy, and is why the purge walker is only defined to
return "the next object to purge". Between two purgewalker->next() there
might be a total reorganisation of the entire policy order for what the
API is concerned.

> Finally, please note that "atomicity" would make deliberately-slow
> things like incremental building of a cache digest impossible. Thus, the
> Cache Digest and similar chunk-at-a-time users will have to be disabled
> if new store API is in place (I assume that with the new API, there will
> be no direct access to ``store table'').

Cache digests should not be built from individual the storage policies,
they should be built from the master storage index we have in the MD5
hash index.

Yes, there should be some method for walking the MD5 hash index in a
clean manner, but that belongs in a separate discussion.

/Henrik
Received on Tue Apr 25 2000 - 11:29:00 MDT

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