Re: questions about LRU implementation

Kin-Yeung WONG wrote:

> When Squid receives a request, it first checks whether the requested
> object is cached or not by looking at the hash table.
> If not, then ask for the remote site.
> Otherwise, the node of requested object in the link list is moved to the
> head of the LRU list.

Yes.

> Here my question arises. How does Squid know the position of the
> requested object in the link list?

It doesn't. The LRU list is a doubly linked list.

> Are there address pointers stored in the hash table?
> If it is true, that means each time the link list changes, the hash
> table has to be updated?

Both the LRU list and the hash table indexes StoreEntry structures. The
indexes are otherwise separate from each other.

> On the other hand, when squid needs to replace cached objects, it takes
> objects from the tail of the LRU list.
> Is it correct that each time it takes objects from the list, the
> corresponding entries in the hash table has to be deleted?

Deleted objects are removed from both indexes yes.

--
Henrik Nordstrom
Squid hacker