Re: Squid store replacement policies

From: Henrik Nordstrom <hno@dont-contact.us>
Date: Tue, 25 Apr 2000 01:32:22 +0200

Duane Wessels wrote:

> Sounds sort of list-centric. Heaps don't really have a notion
> of "next"? But its probably minor.

The policy does not have to have a notion of next, only the walker. How
the walker finds the objects is up to the implementation, and the order
returned does not neccesary reflect the actual policy in any way. It all
depends on the function of the walker.

There are two kinds of walkers:

a: Purge walkers. Always returns the first object purge, and removes it
from the policy at the same time.

b: Index walkers. These returns all objects in some order without
removing them from the policy. The final API specification will probably
read "returns objects in some order suitable for rebuilding the policy".

The API is identical for both. Only the creation of the walker differs.

> The way it works now for both types is we always take
> the last entry in the list/heap. If its locked,
> then it gets moved to the top.

LRU yes, HEAP no. HEAP temporarily removes the locked objects from the
policy and then adds them back when done. There is no top where you can
move ojects to on a heap in the same sense as in a list. This is why it
is up to the policy implementation to make sure locked objects are not
returned when looking for objects to purge.

> the heap code has this always-increasing age parameter, which I
> dont particularly like, but its maintained internally.

I.e. not really something the API has to bother with.

/Henrik
Received on Mon Apr 24 2000 - 17:32:22 MDT

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