Make for URLs, or dependency-directed compositing
kragen at pobox.com
Mon Nov 28 03:37:02 EST 2005
(3800 words, terribly sorry)
Lots of web pages are computed dynamically from some set of resources.
For example, a blog's front page is computed dynamically from a
(potentially large) set of blog posts. The display of an RSS aggregator,
such as the LiveJournal friends page, is computed dynamically from a
subscription list and a bunch of friends' blogs. Many web pages use some
kind of templating system, so the page consists at least of "content"
and the template.
Performance problems in web page compositing
These applications have a set of performance problems. Retrieving the
resources they depend on can take time, use bandwidth, and cost other
people money; dynamically generating the web pages themselves uses CPU
time; and all of this often happens while a human being is impatiently
waiting for a response.
Dependency-directed software builds: make
Normally people write software as a human-readable "source code file"
which gets "compiled" (by a slow program) into an "object file" containing
"machine code", which then gets "linked" with other object files (by a
fast program) into an "executable" which they can run. When they make
changes to the source code, they often want to see the results of their
changes, and they have to rerun this whole process. But typically, they
haven't changed all the source files, so they only have to recompile
some of the source files.
There's a widely used program called "make" that figures out which
object files are out of date and need to be recompiled from source.
We write a "Makefile" which gives the command to build each object
file, and the command to link the final executable, along with a list
of source files that go into that object file (or object files that go
into that executable.) If any of these "dependencies" are newer than the
"target", then "make" reruns the command, which "rebuilds" the "target"
from the data in the "dependencies".
Specifying these dependencies is error-prone, and if something fails to
get rebuilt when it should, it often results in hard-to-debug problems.
Interposition in make, with Vesta
Vesta (http://www.vestasys.org/) is a free-software system for, among
other things, replacing make. It uses "filesystem encapsulation" to make
sure it has dependencies correct; its approach to tracking dependencies
(http://www.vestasys.org/doc/sdl-ref/walkthrough.html#RunTool) is to
run the compiler (and linker and whatnot) in a chroot in which the only
filesystem available is one provided by Vesta itself. This means that
it can detect every file the compiler reads, and they're all checked
into its version-tracking repository, so it can reliably tell whether
rerunning a build step would produce the same results as before ---
in which case, it can safely use the previous results.
(Vesta's replacement for make isn't compatible with Makefiles, using its
own syntax and even terminology, and it only works if you store your
files in Vesta's version-tracking repository. I suspect these may be
reasons Vesta isn't more widely used. Perhaps someone should create a
version of make that works the same way.)
Interposition in web-page compositing
It seems to me that you could use the Vesta strategy with a web-page
compositing system, integrated into a caching proxy HTTP server.
If all the inputs to your web-page generating script are fetched by HTTP
through this proxy, then the proxy can know what they are, and serve
cached output if they haven't changed. It can measure the CPU cost of
running each script, and only cache output when the time saved is worth
the space used. It could even run some scripts periodically (if they
take a while to run, and their results are likely to be used) in order
to ensure that their results are available promptly when needed.
You'd have to make sure that you didn't forget any inputs, though --- if you
used any inputs that weren't handled automatically (like the filesystem,
perhaps, or the system clock) you'd want to have a way to handle those
A caching proxy caches HTTP results at the level of entire
resources (well, their representations). If you write a
script that depends on eBay's "Toshiba Laptops, 500-666MHz" page
in order to inform you when a new Tecra 8100 is going on sale, you
might not want to rerun your script every time the banner ad on that
page changes. Instead, you could split it into two parts: one that
executes some query on that page (maybe "<tr> containing "8100" and not
containing <tr>") and makes the results available at some other URL,
and a heavier-weight script that uses the stripped-down page at this
other URL. Then your heavier-weight script would only run when the part
of the page it cared about had changed.
This lightweight part-extractor component will be useful in many
applications, since often you only care about a part of the pages you
depend on, and it can make this fact visible to the execution environment.
An analogous component is one that combines several resources into one,
perhaps so that you can extract parts from the combination more easily,
or perhaps so that you can display the combination itself as your
"portal" page. By separating out this "compositing" or "templating"
function as a separate task, you allow the various pieces to be recomputed
(and possibly cached) independently.
A third common component, which might subsume the task of the first two,
is an XSLT transformer.
The Atom format, which is normally used for sequences of updates, has
several potentially interesting components that can live within this
framework. Specifically, it has a "truncator" that drops all but the
most recent N events from a given feed; an "aggregator" that takes
several Atom feeds and interleaves their posts according to time; and
an "encapsulator" or "watcher" that takes an entire web page and
encapsulates it as a single Atom item in a one-item-long feed.
Other features of this execution environment
In addition to network access, input caching, output caching, CPU
measurement, and speculative pre-caching (this last I haven't
discussed), the following features would fit in nicely:
- special handling of Cache-control: max-age (and Age: of course.). Scripts
inside the system could use this to prevent the proxy from polling an origin
server too often, and normally it would propagate from a request for a
composited page to the requests used to fetch the components of that page.
- invalidation propagation. Speculative pre-caching, if it produces a new
representation for an existing resource, may invalidate other cached
representations that were computed from that one. (HTTP might not consider
those representations "stale", but they no longer reflect the current state
of the resources they depend on.) The execution environment should propagate
the cache invalidation. In some cases, it may be wise to speculatively
recompute those other resources as well. (All of this might also occur while
a request is being processed, but it would be wise to defer any speculative
recomputation until the response is finished.)
- special HTTP error handling. In many cases, it's better to get an
out-of-date cached representation for a resource than an error
message, and any caching proxy would be in a position to provide this
benefit (although I don't know of any that do). In other cases, you
might want to propagate e.g. 500 and 404 errors through automatically,
rather than having special-case code in your service that handles
this. (Perhaps that's better to put in a library rather than an
execution framework, though.)
The choice of which representations to cache cannot be solved locally, since
the benefit of caching something depends on the cost of computing it.
Something that makes sense to cache because it depends on some uncached and
expensive computation might cease to make sense to cache once that uncached
computation gets cached itself. It turns out that this is related to
well-known problems in OLAP. See J. Ullman, "Efficient Implementation of Data
Cubes via Materialized Views", http://dbpubs.stanford.edu/pub/1996-32.
Given limited resources, the optimal frequency to speculatively recompute
something (whether it's as simple as a cached copy of a web page, or
something much more CPU-intensive) does not increase monotonically as
the update rate of its dependents increases. At some point, it is no
longer worth it to re-fetch web pages more often in hope that they will be
up-to-date when they are needed. See Arasu, Cho, Garcia-Molina, Paepcke,
Raghavan, "Searching the Web", http://dbpubs.stanford.edu/pub/2000-37.
Other systems complementary to this dependency-driven execution environment
Without a protocol for pushing cache invalidations across the network,
the above-described cache-invalidation protocol only works inside a
single server. Given a cache-invalidation protocol for HTTP resources
(for example, the one suggested in my zLab note, "Synchronizing REST
Resources With Asynchronous Notification: A Practical Proposal", which
presently resides at
it is possible to prevent any composited page from being out of date
except when the network is unreliable or under conditions of excessive
Such a protocol could be added to existing web sites with a program we
at CommerceNet have been calling a "delta proxy": a reverse proxy that
sits in front of your web server and notices when resources'
representations change. It is then in a position to provide various
kinds of change notifications, such as a Google "sitemap" file, RSS and
Atom feeds, or pushed cache invalidations.
With Ajax, you can actually push the update notification all the way
to the web browser, updating information on somebody's screen in real
time. (The current suite of Ajax tools don't support asynchronous
event delivery to the browser --- they don't hold any connection open
to the server --- but as we showed at KnowNow, it is possible to do it
with all modern browsers with some difficulty.)
Many applications you might want to build would require some
historical information --- for example, if you have a web page that
shows the current temperature in Portland, Oregon, you might want to
graph it over time.
Given the previously-mentioned "watcher" component that encapsulates a
web page as an Atom feed, there's one additional component that
doesn't quite fit into this framework that can enable such
applications. It's a "feed extender", which turns a shorter Atom feed
(such as a one-item feed) into a longer feed, with up to N items, by
remembering items it saw in the past and inserting "new" items at the
beginning of the feed.
There's also the question of how to avoid scaling problems in
publishing of resources like this. I think we can build a
decentralized network that gives you a few orders of magnitude
improvement here; I've written about this previously at
If you supplement the system described there with cryptographic
signatures with serial numbers, with key hashes included in the URL, you
can avoid the necessity for anyone to hit the origin server, so there
need not be a publicly-accessible origin server any more.
Internal State as Cached Computations on I/O History
Several formalisms describe a program as a function from an input
history to an output action; my own "rumor-oriented programming" idea
depends on this. If you map your input history into URL space as REST
resources, then your program can be entirely stateless --- all its state
can live out in the web, with this caching proxy to save it from taking
a long time to do anything at all.
Of course, you don't want *any* change to the input history to
invalidate *all* your previous computations. So you structure your
program in parts. Suppose, for concreteness, you have a blogging
application whose input history consists of HTTP form POSTs to some URL.
You have one resource that lists all the past form POSTs as links, in
order, and one resource for each form POST. Your blog-front-page
program looks at this form POST index and issues a request for each
group of ten form POSTs, containing their URLs, to a summarization
script, which returns the dates of the blog posts contained in those
form POSTs. Then the front-page program decides which ten or fifteen
form POSTs are relevant to displaying the front page, and fetches them
directly. Although the front-page program's cached results are
invalidated whenever a new POST is made, the summarization script's
results are not, and most of the computation (trawling through massive
amounts of text and deciding which posts are authorized and which
aren't, for instance) is in the summarization script.
In general you can turn a computation on your entire input history into
more-cacheable computations on subsets of it in this way. It may be
difficult to fit the specifications for these computations into a URL,
Some apps depend on the past representations of some other
URL-addressable resource instead of explicit user actions. These apps
can be wrapped up into this framework with the Atom "watcher" and "feed
extender" components discussed above.
Sample app outline: eBay querier
Suppose you want to follow the current market price of Toshiba Tecra
8100s on eBay over time. eBay used to allow easy searching of
recently-completed auctions, which gave you an easy way to get the
current market price: look for successfully-completed auctions of recent
similar items and use the final selling price. "Buy it now!" added a
confounding factor, since it allowed a bad seller to depress the
apparent market price, but you could ignore the "Buy it now!" hits.
But first they moved the "search completed items" option off the main
search page onto search-completed.ebay.com. Now even that requires that
you log into your eBay account, so they can track who's searching for
My approach now is to do a current search, find the non-buy-it-now
auctions ending soonest, bookmark the links to those auctions, and
follow those links after the auctions are scheduled to end. This is a
little laborious, and it would be nice to automate.
So you establish a "watcher" and a "feed extender" with a polling
interval of, say, an hour, on some relevant eBay category page. Then
you write a script which looks at the "extended feed" and, given a
search string, finds items in a recent version of the page matching the
string that are not there in the current version of the page. Then it
fetches the items' individual auction pages and extracts the number of
bids and the closing price, and returns a table of these with the item
descriptions and links.
Sample app outline: webmail viewer
How could you build an application like Squirrelmail or Hotmail in this
framework? (This relates to the application area I had in mind in
(This is somewhat oriented to my own style of email usage, in which all
the email I have ever received is a database of useful facts and
ideas, but I rarely read new email often than twice a week. Apparently
for most people it's a sort of reliable work queuing system, which they
use as a sort of to-do list, and delete items once they're done.)
You map the history of incoming email messages into URL space: perhaps a
web page consisting of links to all the incoming messages for a
particular account for a particular month, and another "master index"
web page listing the total number of messages in each month, with links
to the individual-month pages. These pages are not accessible to
everyone, perhaps by virtue of having unguessable URLs that never leak
outside the system.
This email-history necessarily lives outside the framework I've been
discussing, since it has internal persistent state. It might store the
messages in MySQL, with a thin layer of Perl or Python on top to render
incremental indices in the manner described above.
This allows you to display read-only views of recent messages; to
optimize this, you might want "most recent 100 messages", "most recent
1000 messages", and "most recent 10000 messages" resources that can be
cached internally, computed from the master index and some number of
individual month pages; and these summaries can include information
commonly used for search, such as From, To, Subject, and References.
If you want full-text search, you can compute inverted-index resources
per month. (There's no point in creating per-year inverted indices,
because they would depend on the master index, and so they would become
invalid any time you received a new mail message.) You might cache a
merged index for all months except the current one, by encoding the list
of months in the URL, and use that index (usually cached) plus the
current-month index (fast to recompute) for full-text searches.
Of course, you'd probably prefer not to have the full-text searcher
"download" the entire inverted index for every search, even from a local
cache. But you can map arbitrarily small parts of it into URL space:
words beginning with 'i', words beginning with 'in', words beginning
with 'ind', etc. Of course, the thing that extracts that small part
must "download" the entire inverted index, but not very often.
To provide deletion and filing in different folders, you need to store a
history of user actions, i.e. form posts. Then you can compute
resources such as "deletions from folder INBOX", "deletions from folder
Work", "filings into folder Work", etc., from this history of user
actions, and the display of the folder Work might depend on the "filings
into folder Work" and "deletions from folder Work" resources, plus some
random collection of incoming message resources.
Suppose you want to subdivide "deletions from folder INBOX" into smaller
subsets that pertain to individual months of incoming messages, so that
you can look at lists of messages you received (but didn't delete) last
year, and not have them take a long time to display. So you have a
"deletions from folder INBOX of messages originally received in
November 2003" resource, which depends on "deletions from folder INBOX"
as well as "messages received in November 2003". But "deletions from
folder INBOX" changes fairly often, and whenever it does, it invalidates
"deletions from folder INBOX, November 2003". Recalculating that
resource's representation might show that it didn't change, so there's
no need to recalculate other things that depend on it ("display of INBOX
messages received in November 2003"). But, since "deletions from INBOX
Nov 2003" involves reading all of "deletions from INBOX", it's probably
more expensive to recompute anyway.
Of course, user actions that have some effect outside this system, such
as sending email to someone outside the system, don't fit inside this
framework; you need some external "gateway" program for that.
Sample app outline: custom portal
You want a web page that tells you the top news stories, the prices on
your favorite stocks, the current value of your stock portfolio,
headlines from BBC News, and your current to-do list items (pulled from
some external system like Tadalist.)
If you have the XPath-extractor service described earlier, you can
describe this almost entirely in terms of a sequence of URLs whose
<body> contents should be concatenated. (You might need an XSLT
transformer for the RSS feeds.) Then you can put this sequence of URLs
on a page on your personal web site and pass its URL to the "custom
portal app" running inside this dependency-driven recomputation
environment; it reads your list of URLs and fetches a resource for each
URL, some of which (the XPath-extractor, perhaps) are inside the DDR
system and depend on external URLs. External URLs are cached and
fetched rarely, and the compositing program doesn't have to think about
any of it.
I've mentioned a few services above that make this system more useful,
while standing outside the strict dependency-driven evaluation graph;
Here's a list of the things I've thought of:
- the Atom "feed extender" listed above, which provides a window into
- the form-POST logger occasionally mentioned above; probably this will
be most useful if its URL is secret or otherwise not globally
- URL shorteners, along the lines of makeashorterlink.com, provide four
useful services in this context:
- if your overall tree of dependencies is large, you may have a hard
time fitting it into a single URL query string (containing encoded
URLs containing their own query strings pointing at still other
URLs). A URL shortening service can keep the URL lengths under
- if you can change the URLs they point to, they serve the function of
- if they proxy for URLs rather than redirecting to them, they can
provide revocability for access to secret capability URLs.
- if they can take a query string with named parameters and combine
that with any original query string, they provide currying.
- a user interface that appreciates that URLs can take other URLs as
"Currying as a UI technique for devolution of power to users" for my
thoughts on that, particularly the scenario entitled "An Example
Application" and the explanatory text in the section "A REST-backed
- a web-wide invalidation protocol, like that described in the zLab note
The inverted-index case points out that, in some cases, one small
program can compute a large number of resources ("words beginning with
a; words beginning with b; etc.") with no more work than it needs to
compute one of them.
As illustrated by the "INBOX deletions, Nov 2003" example above, because
there's no way to store information inside the system, there's no way to
deal with externally provided resources that are too large in
granularity and change frequently. You can cache smaller resources that
contain subsets of them, but revalidating those cached subsets involves
rereading the entire large resource.
The idea that a dependent resource might not actually change when the
thing it depends on changes poses a couple of problems:
- it casts doubt on the idea that a cost-based optimization algorithm
can a priori figure out a good set of things to cache
- it interferes with eager invalidation, where the invalidations flow
forward along the data flow edges without recomputing any of the
intermediate values unless the invalidations reach something that's
currently being observed. ("eager invalidation" is the lazy
evaluation scheme described in
"lazy evaluation in a distributed system", and
"lazy evaluation in Python in a way that supports distributed
"dynamically updating dependency networks in Smalltalk".) I think
it's possible to reconcile the two schemes by having three states per
cached resource (valid, possibly invalid, invalid) instead of just
two, but I haven't done the work to find out.
The ideas in here were inspired by work by, and were honed in
discussions with, Dan Moniz, Ben Sittler, Rohit Khare, Allan Schiffman,
Donovan Preston, and Mark Lentczner.
More information about the Kragen-tol