W3C home > Mailing lists > Public > ietf-http-wg@w3.org > April to June 2011

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

From: Poul-Henning Kamp <phk@phk.freebsd.dk>
Date: Tue, 31 May 2011 17:53:30 +0000
To: Mark Nottingham <mnot@mnot.net>
cc: Brian Pane <brianp@brianp.net>, httpbis Group <ietf-http-wg@w3.org>, Balachander Krishnamurthy <bala@research.att.com>, cew@cs.wpi.edu
Message-ID: <38514.1306864410@critter.freebsd.dk>

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
phk@FreeBSD.ORG         | TCP/IP since RFC 956
FreeBSD committer       | BSD since 4.3-tahoe    
Never attribute to malice what can adequately be explained by incompetence.
Received on Tuesday, 31 May 2011 17:53:56 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Friday, 27 April 2012 06:51:41 GMT