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

From: Mark Nottingham <[email-masked]>
Date: Sat, 28 May 2011 10:56:37 +1000

FYI. This is an individual draft, not a WG effort. Nevertheless, feedback welcome.

Regards,

Begin forwarded message:

> From: [email-masked]
> Date: 27 May 2011 10:15:29 PM AEST
> To: [email-masked]
> Subject: I-D Action: draft-nottingham-linked-cache-inv-00.txt
> Reply-To: [email-masked]
> 
> A New Internet-Draft is available from the on-line Internet-Drafts directories.
> 
> 	Title           : Linked Cache Invalidation
> 	Author(s)       : Mark Nottingham
>                          Mike Kelly
> 	Filename        : draft-nottingham-linked-cache-inv-00.txt
> 	Pages           : 8
> 	Date            : 2011-05-27
> 
>   This memo defines Web link types that invalidate HTTP caches, along
>   with an HTTP cache-control extension that allows caches that
>   understand those link types to use responses containing them.
>   Together, these mechanisms offer a way to avoid use of a response
>   that has become stale due to another request that changes server-side
>   state.  Collectively, this is referred to as Linked Cache
>   Invalidation (LCI).
> 
> 
> A URL for this Internet-Draft is:
> http://www.ietf.org/internet-drafts/draft-nottingham-linked-cache-inv-00.txt
> 
> Internet-Drafts are also available by anonymous FTP at:
> ftp://ftp.ietf.org/internet-drafts/
> 
> This Internet-Draft can be retrieved at:
> ftp://ftp.ietf.org/internet-drafts/draft-nottingham-linked-cache-inv-00.txt
> _______________________________________________
> I-D-Announce mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/i-d-announce
> Internet-Draft directories: http://www.ietf.org/shadow.html
> or ftp://ftp.ietf.org/ietf/1shadow-sites.txt

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

---

From: "Yngve N. Pettersen (Developer Opera Software ASA)" <[email-masked]>
Date: Sat, 28 May 2011 03:10:25 +0200

For reference, based on a quick skim of the document, while this seem to  
have a slightly different goal, and seems to be more targeted, it  
resembles functionality my (currently expired) Cache Context draft  
<http://datatracker.ietf.org/doc/draft-pettersen-cache-context/> suggest  
using a different mechanism.

For background on that draft, please see my article  
<http://my.opera.com/yngve/blog/show.dml/783534>

-- 
Sincerely,
Yngve N. Pettersen
********************************************************************
Senior Developer		     Email: [email-masked]
Opera Software ASA                   http://www.opera.com/
Phone:  +47 23 69 32 60              Fax:    +47 23 69 24 01
********************************************************************

---

From: Brian Pane <[email-masked]>
Date: Sat, 28 May 2011 03:40:11 -0700

What do you think about allowing the origin server (or an intermediate
proxy, for that matter) to indicate a new Last-Modified timestamp for
a related resource, rather than just indicating that any cached copy
of the related resource should be considered invalid?

Here's the use case where I think a Last-Modified update would be useful:

Consider a website on which most HTML pages reference a stylesheet,
    <link rel="stylesheet" href="/common.css">
In common practice, common.css is with a large max-age value to
encourage downstream caching.  Eventually a web developer will modify
the document at the origin server, and it will become important that
any client that subsequently requests any HTML resource from the site
must also fetch the new version of the stylesheet.  A common solution
for this is to add versioning information to the URI -- e.g.,
/common.css?v=2 -- but that's a cumbersome technique for many reasons.

The linked cache invalidation isn't quite a match for this scenario.
The server could send an inv-by the next time each client requests any
HTML page,
    Link: </common.css>; rel="inv-by"
but that should only be sent once per client, so as to avoid
invalidating the cache on every subsequent HTML resource request.  And
in the general case it's impossible to keep track of what clients have
already received the inv-by.

But what about the following variant?
    Link: </common.css>; rel="last-mod"; value="[some valid HTTP-date]"
Upon seeing that header in the response, the recipient (whether the
origin client or an intermediate cache) could decide whether to
invalidate its cached copy of /common.css based on the supplied
last-mod timestamp.  It would be safe for the server to send that
header to the same client (or intermediate cache) arbitrarily many
times.

-Brian

---

From: Mark Nottingham <[email-masked]>
Date: Tue, 31 May 2011 14:35:27 +1000

Hi Brian,

Yep, this sounds very much like Bala and Craig Wills' work on Piggyback Cache Invalidation more than a decade ago -- See <http://www2.research.att.com/~bala/papers/> and scroll down to "Web Caching."

Using the Link header makes sense here, and I think it'd be desirable to have a separate max-age (like that done in LCI) to allow people to specify longer freshness lifetimes when the cache understands the extension and is willing to invalidate based upon it.

The question in my mind is whether it makes sense to combine PbCI and LCI into a single mechanism, or to keep them separate. The downside to separating them is that it might be necessary to have *two* new max-ages, which wouldn't be great (especially considering figuring out how they'd interact).

I would observe that LCI is tilted towards deployment in "reverse" proxy caches, where PbCI seems a bit more suitable for forward proxies and browser caches.

The other question, of course, is whether any cache vendors (intermediary or browser) would implement. For experimentation purposes, it might be possible to shoehorn it into Squid in a similar manner to LCI was (i.e., with a helper process).

Bala/Craig, any thoughts? The draft under discussion is <http://tools.ietf.org/html/draft-nottingham-linked-cache-inv-00.html>.

Cheers,

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Tue, 31 May 2011 17:53:30 +0000

I am sure this will have pretty bad performance and I am not
convinced it will actually work as expected.

Whenever an object with "inv-by" is received, the cache is forced
to do a lookup of the target of that "inv-by" in order to establish
the necessary linkage (= a storage cost) to effect the dependent
invalidation.

This lookup+linkage must be done for each and every object with an
"inv-by" property, no matter how frequent or infrequent invalidations
are.

(The only other way to implement this is to do a brute force scan
of the cache on each invalidation.)

Turning the linkage around, by setting "invalidates" on the nexus
object, is not as horrible, because it allows lazy evaluation without
storage overhead, which again means that the cost will only be borne
on actual invalidations.

In either case, a massively parallel multi-user cache, either has
to suffer a debilitating amount of locking for each invalidation,
or take a very relaxed view of the temporal relationship between
the objects associated by the Link: header.

The next thing that strikes me, is that all implementations will
have to contain some kind of loop-avoidance to avoid some really
stupid behaviour (A invalidates B, B invalidates C, C invalidates A)

I do not have a ready proposal for a better way of doing this,  that
does not involve either a mandatory "lazy ban" facility (like we
have in Varnish), or a mandatory secondary index in the cache.

This makes me suspect that this is an attempt to solve the wrong
problem the right place or the right problem the wrong place.

After all that negativity, let me point out constructively that
prototyping the "inv-by" and "invalidates" properties in Varnish,
can be used to make a sanity check (in the sense of "running code")
to see if this concept would actually work in practice.

Poul-Henning

-- 
Poul-Henning Kamp       | UNIX since Zilog Zeus 3.20
[email-masked]         | TCP/IP since RFC 956
FreeBSD committer       | BSD since 4.3-tahoe    
Never attribute to malice what can adequately be explained by incompetence.

---

From: Mark Nottingham <[email-masked]>
Date: Wed, 1 Jun 2011 08:05:14 +1000

Hi PHK,

I have running code and a few years of deployment experience, and things aren't quite so dire.

See:
  https://github.com/mnot/squid-lci

I keep the associations in memory (hashed in some cases to preserve space), and that seems to work well.

It is true that the invalidations aren't atomic, but in practice the speed of application is good enough.

It's true that a large proxy cache probably won't want to spend the memory on this scheme, but that's OK.

Cheers,

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Tue, 31 May 2011 22:44:59 +0000

In message <[email-masked]>, Mark Nottingham wri

>speed of application is good enough.

If speed is not a part of the design the draft should say so.

---

From: Dzonatas Sol <[email-masked]>
Date: Tue, 31 May 2011 17:47:52 -0700

> It is true that the invalidations aren't atomic, but in practice the speed of application is good enough.

With idealogy of an X server on port 80 (for 8 screens) with custom xlib 
that recognizes qr coded HTTP header line (transforms), atomicals can 
exist with ray-tracer algorithms, which are equivalent to quantum 
computers in the fiber optic link.

I wondered about some sinless use for the TRACE method (i.e. screen 0: 
YUV "secret sum of a bit"... screen 1 RGB is user viewport). GUID for 
each window name, UUID+octal(Y) for each UDP, raw etc, and I avoided 
causes of any reproof for this part of the stack when there is plenty of 
books, phase shifts, wavelets, and affine transformations that already 
do their history portion of the workspace (as much as possible), 
already. YUV is forward and RGB is backward. Pretty flow...

Instead of (proposed DSM-V entry for) "Internet Addiction", I thought of 
an atomical that logs(Y) U(heat)V(delta) in manner like 
<http://tools.ietf.org/html/rfc958> without the date. May be of 
convenience for net stability "testing" and load balancers (because 
firewalls need an icewall).

http://www.youtube.com/watch?v=mcU89Td53Gg

I would first suspend any "simulated" quantums computations that rely on 
quantum spin metrics, as if that exists then so does vanity. There are 
more important message we can convey than that of the BASIC repository 
mirror. Science is evil like that.

-- 
--- https://twitter.com/Dzonatas_Sol ---
Web Development, Software Engineering, Virtual Reality, Consultant

---

From: Brian Pane <[email-masked]>
Date: Tue, 31 May 2011 21:46:00 -0700

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?

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.

-Brian

---

From: Mark Nottingham <[email-masked]>
Date: Wed, 1 Jun 2011 14:47:45 +1000

> will persistently retain the knowledge that changes to A should

Yes, until another response is received with differing information.

> Retaining the associations persistently is a much harder model to

Remember that the association is bounded by the freshness lifetime of the response it was carried in; that keeps things reasonable.

Cheers,