Re: Squid store replacement policies

From: Alex Rousskov <rousskov@dont-contact.us>
Date: Thu, 27 Apr 2000 15:20:38 -0600 (MDT)

On Thu, 27 Apr 2000, Henrik Nordstrom wrote:

> So you are proposing we introduce a requirement on yet another
> persistent index, or even a third runtime index?
>
> Squid has two runtime indexes:
>
> a) The global main store index, indexing all the known objects on MD5
> hashes.
>
> b) The removal policy priority, kept on a per cache_dir basis.

The number of indexes stays the same. The only difference is that each
FS stores/loads its part of the main store index and the policy stores
the order, if needed.

Ideally, there should be no "main store index" but a collection of FS
indexes. FS should be able to decide on how to lookup an object based on
request headers. The latter is probably a better design (with small
overhead compared to the centralized index), but the difference is not
that big, I think.
 
> What we want to preserve on a shutdown is a index of what is kept in
> each of the cache_dir's, while preserving as much as possible of the
> ordering in the removal policy.

That's exactly what I am after.

> > Note that the policy should store just its metadata (if any), not FS
> > index. FS stores its metadata independent of the policy in use. The
> > latter may, in some cases, increase storage requirements a little bit,
> > but in most cases the difference will be negligible, if any.
>
> And how do you connect the two together in an efficient manner?

Depends on the policy. The general idea is that cache_dir index has the
same interface for all cache_dirs and policies use that interface to
re-index entries in their own index if needed. A policy may store more
metadata than just a pointer to StoreEntry, depending on the policy
needs.

For LRU, maintaining a queue of ids/pointers to StoreEntries (run-time)
and storing/loading StoreEntry ids/filenos should be sufficient.

> If you have any ideas on how the indexes should be implemented then
> please say so.

See above.

> I will however go ahead and implement the policy API as it is now.
> Changing it later is not a big deal, abstracting it out of the main
> code is the most important part at this time.

You win then. Sorry for wasting your time.

> > The "hot object cache" policy indexes StoreEntries (that may have
> > MemoryObject structures). What is removed when you purge the "hot object
> > cache" is the StoreEntry. It is removed from the "hot memory index"
> > leaving "file store index" and its entries unchanged.
>
> Again no. The "hot object cache" currently indexes MemoryObjects which
> happens to have a StoreEntry. A StoreEntry cannot be indexed by the "hot
> object cache" if it doesn't have a MemoryObject.

I was describing how the things may be organized, not how they work now.
 
> The "hot object cache" is not at all implemented as a FS type store. It
> is completely different almost all aspects. It simply piggy-backs on
> Squids object forwarding.

Exactly. And, IMO, that is not the best design possible.
 

> It is called by the policy's users to create the policy before use.

Thats exactly what I am against! That function should not be called to
create policies (except by the parser), individual policy constructors
should be called. "createPolicy(type) should be a "protected" method of
the parser not an interface for others to use.
 
> It is the FS who gets the input from the user on which policy to create,
> and it is the FS who creates the policy for it's objects.

It may be better to allow users to configure FS with a pre-created
policy. The design where the policy can be created internally only is
excessively rigid, IMO.
 
Alex.
Received on Thu Apr 27 2000 - 15:21:15 MDT

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