Re: Squid store replacement policies

From: Alex Rousskov <rousskov@dont-contact.us>
Date: Mon, 24 Apr 2000 21:37:13 -0600 (MDT)

On Mon, 24 Apr 2000, John Dilley wrote:

> Providing two walks (an inorder walk
> which removes each object from the heap and a walk in some arbitrary order
> that returns a pointer to each object without adjusting its position) seems
> adequate and safe (i.e., the semantics are clearly defined).

Just to be a pain, I would note that the proposed semantics seems to be
incomplete. A "walk" is not [necessarily] an atomic operation. One has
to define (at least) what happens if objects get
referenced/added/deleted/etc. while the walk is in progress. I am not
even talking about things like re-configure when an entire "drive" may
disappear from the store while somebody is slowly searching for an
object that matches some "interesting" criteria...

Either any walk must be guaranteed not to be preempted by store
modifications (a potentially costly for API users, albeit
easy-to-enforce, condition) OR all walkers must handle store
modifications (a non-enforceable condition that may be hard or even
impossible to support for some walkers). Without clear specification, a
naive walker may end up returning the same object twice or skipping an
object because of concurrent modifications, etc.

I do not know the ideal solution to this dilemma, but would suggest that
a solution is documented and, if possible, enforced by the API.

$0.02,

Alex.

this->f(this)
Received on Mon Apr 24 2000 - 21:37:49 MDT

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