Subject: Re: I-D Action: draft-nottingham-linked-cache-inv-00.txt

From: Brian Pane <[email-masked]>
Date: Thu, 2 Jun 2011 09:22:08 -0700

On Tue, May 31, 2011 at 9:47 PM, Mark Nottingham <[email-masked]> wrote:
>
> On 01/06/2011, at 2:46 PM, Brian Pane wrote:
>
>> On Tue, May 31, 2011 at 3:05 PM, Mark Nottingham <[email-masked]> wrote:
>> [...]
>>> I keep the associations in memory (hashed in some cases to preserve space), and that seems to work well.
>>
>> Does that mean that your implementation, upon seeing a response for
>> resource A that contains a Link header that invalidates resource B,
>> will persistently retain the knowledge that changes to A should
>> invalidate B?
>
> Yes, until another response is received with differing information.
>
>> I'd been assuming that the invalidation of B would be a one-time
>> event: the receiving client or intermediary would invalidate B in its
>> cache and forget about the message thereafter.  That's a scalable
>> model (in practice, implementations limit the max total header size
>> they'll allow per message, and that puts an upper bound on the number
>> of invalidations that a single response message can trigger).
>> Retaining the associations persistently is a much harder model to
>> scale.
>
>
> Remember that the association is bounded by the freshness lifetime of the response it was carried in; that keeps things reasonable.

Depending on one's cache implementation, though, an expired resource
may live in the cache for a very long time - e.g., until a client
requests it or it's evicted to make room for something else.  Most
proxy implementations that I've seen don't proactively sweep their
caches to find stale entries, for good performance reasons.  In the
general case, the association data can have O(n*m) size, where n is
the number of resources in a cache and m is the number of related
links specified per resource, and my concern is that that's too high a
per-resource tax to impose on cache implementors.

But are there scenarios where maintaining the association data within
the cache would work better than treating the invalidation headers as
a one-time operation?  I'm focusing mainly on reverse-proxy use cases,
so the stored-association model may have some forward-proxy or client
benefits I'm overlooking.

Thanks,
-Brian

---

From: Mark Nottingham <[email-masked]>
Date: Fri, 3 Jun 2011 09:20:26 +1000

[ taking Bala and Craig off the thread, as this is getting away from the reason I added them ]

> benefits I'm overlooking.

I was hoping to avoid digging through the implementation to remind myself of how it was done; oh well ;)

Basically, it remembers the association for the freshness lifetime plus a small window. Once the object becomes stale, normal operation of Squid (like any conformant HTTP cache) is to attempt to revalidate, only using the stale response if there's a network error, etc. This is considered desirable behaviour; if the publisher doesn't want a stale response to be used, they have ways to control that (e.g., must-revalidate, stale-if-error).

It is effectively one-shot, because we don't just mark them stale, we HTCP CLR them, which IIRC in Squid remove the object (it doesn't just mark it stale), and the manager removes the association at the same time. When a new response gets cached, any associations in it will get re-added to the manager.

I was very concerned about the memory overhead of this scheme, and took a number of steps to make it more compact, but in the end it wasn't as bad as I feared; I don't have specific numbers on hand, but it hasn't been a big problem in our deployments (which *are* on a large scale, as reverse proxies).

Cheers,

--
Mark Nottingham   http://www.mnot.net/