Asynchronous HTTP Cache Validations
HTTP caching can go a long way to help scale a web application - instead of dynamically serving every single request, we can use memcached, Squid, Varnish, or a multitude of other tools to respond in just a few milliseconds. However, as developers at Yahoo have noted, there is a common failure scenario that is often left unaccounted for: what happens when the cache turns stale?
If fresh responses come in a small number of milliseconds (as they usually do in a well-tuned cache), while stale ones take 200ms or more (as running code often leads to), users will notice (as will your execs).The naïve solution is to pre-fetch things into cache before they become stale, but this leads to all sorts of problems; deciding when to pre-fetch is a major headache, and if you don’t get it right, you’ll overload your cache, the network or your back-end systems, if not all three.
HTTP Caching Extension: stale-while-revalidate
To address this problem Mark Nottingham recently proposed an HTTP caching extension: stale-while-revalidate. A very simple idea at its core, this pattern can have an enormous impact on the user experience. As the diagram shows, the tradeoff is freshness of data vs. response time. Specifically, if your application can afford to show slightly out of date content (colored grey), then stale-while-revalidate can guarantee that the user will always be served directly from the cache, hence guaranteeing a consistent response-time user-experience.
Proof of concept with Ruby and EventMachine
As Mark has noted in his diagram, the caching layer (in his case, Squid - v2.6 supports stale-while-revalidate), would have to be extended to issue an asynchronous request to the application layer telling it to refresh the cache. Also, interestingly enough, memcached FAQ elaborates on this exact scenario as well, offering a few suggestions for asynchronous updates: Gearman, and a recipe for Django. Following in these footsteps, I've built a proof of concept in Ruby, using EventMachine:
# www.igvita.com
require 'rubygems'
require 'eventmachine'
require 'evma_httpserver'
require 'memcache'
class StaleWhileRevalidate < EventMachine::Connection
include EventMachine::HttpServer
attr_accessor :memcached
attr_reader :http_request_uri, :http_query_string
def process_http_request
resp = EventMachine::DelegatedHttpResponse.new(self)
response = proc do |data|
resp.status = 200
resp.content = data
resp.send_response
end
# Cache two keys: 'key' (with an expire) and 'key-no-ttl' (with no expire)
# if 'key' has expired, return value at 'key-no-ttl', and start an async
# update process to update the cache
#
# key = full request path with query parameters
cache_key = @http_request_uri.to_s + @http_query_string.to_s
keys = {:key => cache_key, :no_ttl => cache_key + "-no-ttl", :processing => cache_key + "-processing"}
cache = @memcached.get_multi(*keys.values)
# async operation to compute value to be stored in the cache, in this case..
# data is a simple timestamp. This is where actual app logic and processing
# is done. (talking to database, etc.)
operation = proc do
sleep 5
@data = Time.now.to_s
end
# Callback to execute once the request is fulfilled, will update the
# memcached values for future requests
callback = proc do |res|
# if cache is empty, then this is a new request, and we need to render
# response back to user. This is the only time the user will hit live
# application server
response.call(@data) if cache.empty?
@memcached.set(keys[:key], @data, 10)
@memcached.set(keys[:no_ttl], @data, 0)
@memcached.set(keys[:processing], 0, 0)
puts "\t app server updated cache! New value for '#{keys[:key]}' : #{@data}"
end
# if key has not expired, then return immediately, we're safe!
if cache[cache_key]
puts "Valid cache for: #{cache_key} :: Data :: #{cache[cache_key]}"
response.call(cache[cache_key])
else
# check if we've seen this request before... if so we'll have the no-ttl
# key, which we'll return immediately, and then start an async process
# to update the stale cache
if cache[keys[:no_ttl]]
puts "Stale cache for: #{keys[:key]} :: Data :: #{cache[keys[:no_ttl]]} :: Processing? :: #{cache[keys[:processing]]}"
response.call(cache[keys[:no_ttl]])
# set processing flag to true, this avoids multiple requests piling on
# while the async query is waiting to complete
@memcached.set(keys[:processing], 1, 0)
end
EM.defer(operation, callback) if cache[keys[:processing]].to_i != 1
end
end
end
EventMachine::run {
@memcached = MemCache.new("localhost:11211")
EventMachine::start_server("0.0.0.0", 8081, StaleWhileRevalidate) { |conn|
conn.memcached = @memcached
}
puts "Listening on port 8081."
}em-stale-while-revalidate.rb - Ruby source
The application logic is simple: if we have never seen this request, process, and cache it; if we've seen this request, and the cache is valid, then render response; if we've seen this response, but the cache is stale, render the stale version immediately, and then continue the process to update the cache. Also, to avoid the 'stampeding' effect, we've added a flag to mark a request as in-progress, to indicate that an application server is working on updating the cache. Connecting all the pieces together, let's take a look at the server output for a few incoming requests:
Listening on port 8081. app server updated cache! New value for '/test/path' : Sun Oct 05 22:12:25 -0400 2008 Valid cache for: /test/path :: Sun Oct 05 22:12:25 -0400 2008 Valid cache for: /test/path :: Sun Oct 05 22:12:25 -0400 2008 Stale cache for: /test/path :: Sun Oct 05 22:12:25 -0400 2008 :: Processing? :: 0 Stale cache for: /test/path :: Sun Oct 05 22:12:25 -0400 2008 :: Processing? :: 1 app server updated cache! New value for '/test/path' : Sun Oct 05 22:12:40 -0400 2008 Valid cache for: /test/path :: Sun Oct 05 22:12:40 -0400 2008 Valid cache for: /test/path :: Sun Oct 05 22:12:40 -0400 2008
As you can see, the first request sets the cache, and subsequent two requests are served from it. Then, once the cache turns stale (after 10 seconds), two requests saw stale data, while the application server was busy updating the cache!
Implementing stale-while-revalidate
This pattern can be easily extracted into a Rails/Merb plugin format (as well as, improved: duplication of stored data, etc.), but ideally this logic should live in a layer above. Connecting Nginx and Memached directly can yield spectacular results, and it would be great to see a modified Memcached module for Nginx which could take advantage of this pattern as well (memcached_revalidate?) - no modifications on the application layer, and native support for any framework or language by definition.
Ilya Grigorik is a web ecosystem engineer, author of High Performance Browser Networking (O'Reilly), and Principal Engineer at Shopify — follow on Twitter.