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."
}

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 GrigorikIlya Grigorik is a web ecosystem engineer, author of High Performance Browser Networking (O'Reilly), and Principal Engineer at Shopify — follow on Twitter.