Questions about caching turn up on the Freebase developer’s list from time to time, usually in the form of a bug report like this: “mqlwrite succeeded, but subsequent mqlreads did not reflect the changes – what gives?” More often than not, the problem is related to writing with one user agent (e.g., a browser) while reading with another (e.g., a Perl script), which brings us to a previously undocumented aspect of the Freebase/Metaweb API – the limited write/read consistency guarantee.
By default, the Freebase/Metaweb API guarantees write/read consistency to individual cookie-aware user agents. A user agent can immediately read the results of its own writes. There is no guarantee, however, that a user agent can immediately read the results of another user agent’s writes. To explain why this is so, I’ll quickly summarize the mechanics and limitations of HTTP caching and then describe variable expiration, a technique we’ve developed that trades off consistency for speed under certain conditions.
HTTP Expiration and Validation
HTTP caching can be complicated. In the worst case, end-to-end behavior depends on user agent request headers, origin server response headers, proxy cache configurations and heuristics, and protocol version mismatches, clock skew, and bugs across the request chain. But the underlying principles are simple: expiration and validation.
“Expiration” means that an origin server specifies the amount of time a response may be used downstream without being validated. Expiration is specified via “Expires” and/or “Cache-Control” response headers.
“Validation” means that a user agent or proxy cache asks an origin server to either confirm that an expired cached response is still valid or return a new response. Validation is typically requested via “If-Modified-Since” and/or “If-None-Match” request headers. Validating requests are also called “conditional requests”.
Expiration versus Invalidation
The expiration/validation model works well for content that changes at predictable intervals, and for applications that can generally tolerate content that is inconsistent with the origin server for a limited amount of time. It works less well for read/write applications that require content to be consistent in some, but not all, circumstances. It requires the origin server to choose between performance (long expiration, less frequent validation) and consistency (short expiration, more frequent validation) at the time it generates the response headers for a resource, whereas the best choice may depend on the user’s expectations at the time of a particular subsequent request for the resource.
Readers expect rapid responses. Writers expect to see the results of their writes immediately. Servers and clients comprising read/write applications often suppress caching aggressively (i.e., “cache busting” via “Cache-Control: no-cache”, “Expires:” values in the past, and so on), forgoing quick responses to readers in order to guarantee consistent responses to writers. This increases latency, bandwidth usage, and origin server load unnecessarily in many cases.
A great deal of research has gone into addressing this problem. Invalidation is one approach that has been well studied and successfully implemented in certain situations. “Invalidation” means that an origin server notifies downstream caches when a previously cached response becomes invalid, allowing expiration to be set far in the future – in principle, to forever. But notification imposes problems having to do with state management and reachability that have prevented the idea from catching on. Mark Nottingham describes in his blog an exciting polled variant of invalidation called Cache Channels that overcomes these problems in reverse proxy setups.
But there is another problem with invalidation in the context of fine-grained read/write applications: There is simply no efficient way, in many cases, to accurately and precisely determine which cached reads should be invalidated by a given write. In the ACID world of relational database query caches, often the best that can be done is to invalidate all reads that depend on a given table whenever that table is written. MQL and the Freebase/Metaweb data model do not lend themselves to this sort of fractional cache invalidation.
Variable Expiration
For read-mostly read/write applications like Freebase, freshness requirements can be thought of more as a function of user context than as properties of the responses themselves. Readers expect to receive responses quickly. Writers expect to receive responses that reflect their most recent writes. This disparity in user expectations suggests a variable expiration mechanism that provides readers with reasonably quick (but possibly out-of-date) responses and writers with consistent (but slower) responses.
How It Works
Most responses to read requests are tagged with very short expirations, but longer expirations are used internally by the Freebase/Metaweb caches. Responses to successful write requests include an “mwLastWriteTime” cookie with a date value indicating when the write concluded. Whenever a read request can be satisfied with a response from the Freebase/Metaweb caches (according to the RFC 2616 expiration rules for transparent caches, but using the longer internal expiration value), a comparison is made between the cached response Date and the mwLastWriteTime cookie in the request. If the response Date is later than the cookie date (or if the cookie is not present) the result is a cache hit – the cached response is served. Otherwise the result is a cache miss – the request is forwarded to the origin server and a new response is returned.
To recap:
- Short external expirations
- Longer internal expirations
- mwLastWriteTime cookie updated on write
- Enhanced freshness test considers mwLastWriteTime cookie on read
As a result, readers (who lack an mwLastWriteTime cookie) tend to receive whatever responses happen to be in the Freebase/Metaweb caches. Writers, on the other hand, receive only responses that have been generated since they last wrote.
This technique reduces bandwidth usage and origin server load, in many cases, while guaranteeing write/read consistency to individual cookie-aware user agents. It does require a validating round-trip for reads, so latency is not reduced as much as it would be if inconsistency was considered generally tolerable and external expirations were set long. The validating round-trip provides a window of opportunity for the enhanced freshness test to be applied.
Some cached responses that fail the enhanced freshness test may not actually be out-of-date. But writers tend to look at the things they expect to be affected by their writes, pulling fresh copies into the caches for everyone. Call it interactive invalidation.
This brings us back to the consistency issue mentioned at the outset. A user agent’s writes may not be immediately readable by another user agent, depending on the current contents of the Freebase/Metaweb caches, because their distinct mwLastWriteTime cookie values are interpreted as distinct freshness expectations.
HTTP Compliance
You may be asking yourself “if two user agents may see two different responses depending on their mwLastWriteTime cookies, shouldn’t the responses be marked Vary: Cookie”? RFC 2616 seems to indicate that “Vary: Cookie” is not required here. The mwLastWriteTime cookie is not part of the cache key – a single version of each resource is shared by all readers and writers. The cookie only affects the freshness calculation.
Cache-Busting is Still an Option
The variable expiration mechanism does not preclude the use of Cache-Control: max-age, no-cache, etc., in requests to force fresh responses. Put another way, an HTTP client need never touch mwLastWriteTime in order to see fresh content. But touching mwLastWriteTime is a simple way to guarantee responses generated after some reference date. This is what the “Refresh cache” link in the “Dev Tools” bar at the bottom of most Freebase pages does (by executing an empty mqlwrite POST, causing the mwLastWriteTime cookie to be updated without actually writing anything).
