Mike Ferrier

I beat code into submission.

My Beautiful Dark Twisted Reverse-proxy LRU Cache

Reverse-proxy caching is generally one of the low-hanging fruit of scaling a site. If your reverse proxy is nginx, then you’ve probably seen the modules HttpMemcachedModule and HttpRedis, both of which are pretty good at fetching from memcached or redis based on a simple key.

The config would look a little something like this:

1
2
3
4
5
6
7
8
9
10
11
12
server {
  location / {
    set $memcached_key $uri;
    memcached_pass     redis_server:11211;
    default_type       text/html;
    error_page         404 @fallback;
  }

  location @fallback {
    proxy_pass backend;
  }
}

But what if you want to do something a bit more complex? Say you wanted to do namespaced caching, where there are two cache operations per request: one to fetch the version number of the requested resource, and a second to fetch the actual cached data from a key which interpolates the value of the first operation. Since HttpRedis only allows you to fetch values from redis based on a key computed in your nginx script, this isn’t possible.

Enter the nginx modules Redis2 and Lua. The former allows you to make any call you like to redis, as opposed to HttpRedis which only allows the plain old GET command. The latter allows you do embed Lua scripts in your nginx config, effectively giving nginx a bigger brain and allowing you to do some pretty fancy stuff.

In this post we’ll set nginx and redis up to serve as a reverse-proxy LRU cache. We recently started using this setup on 4ormat and it’s sped up our site considerably and offloaded the hits to the application server by around 91%!

  1. Install lua and redis.parser
  2. Build nginx with module support
  3. Redis structure
  4. Configure nginx
  5. Cache script
  6. Configure Redis
  7. Configure your app
  8. Conclusion and Benchmark

1. Install lua and redis.parser

In order to build the nginx lua module, you’ll need lua installed on your system. We also need the redis.parser library in order to easily parse raw redis responses.

On most systems, lua is already installed or is easily installed with your local package manager.

OSX:

1
brew install lua

Ubuntu:

1
sudo apt-get install lua

Gentoo:

1
sudo emerge lua

Once that’s done, you just need the redis.parser library:

1
2
3
4
5
6
$ curl https://github.com/agentzh/lua-redis-parser/tarball/v0.04 -s -L -o lua-redis-parser.tar.gz

$ tar zxvf lua-redis-parser.tar.gz
...untar output...

$ cd agentzh-lua-redis-parser-ceffe35

On Linux, you can just type make to build, but on OSX I found you have to do it by hand:

1
2
3
4
5
# linux:
$ make
# osx:
$ gcc -I/usr/local/Cellar/lua/include/ -O2 -fPIC -Wall -Werror -o parser.lo -c redis-parser.c
$ gcc -o parser.so -bundle -undefined dynamic_lookup -fomit-frame-pointer parser.lo

Then, install the library:

1
$ sudo make INSTALL_PATH=/usr/local/lib/lua/5.1/ install

2. Build nginx with module support

Nginx does not support dynamic module loading, so in order to build new functionality into nginx you need to recompile it with the appropriate modules.

Here’s how I do it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
$ curl http://nginx.org/download/nginx-1.0.0.tar.gz -s -O
$ curl http://mdounin.ru/hg/ngx_http_upstream_keepalive/archive/tip.tar.gz -s -o ngx_http_upstream_keepalive.tar.gz
$ curl https://github.com/chaoslawful/lua-nginx-module/tarball/v0.1.6rc5 -s -L -o lua-nginx-module.tar.gz
$ curl https://github.com/agentzh/set-misc-nginx-module/tarball/v0.21rc3 -s -L -o set-misc-nginx-module.tar.gz
$ curl https://github.com/simpl/ngx_devel_kit/tarball/v0.2.17rc2 -s -L -o ngx_devel_kit.tar.gz
$ curl https://github.com/agentzh/redis2-nginx-module/zipball/v0.06 -s -L -o redis2-nginx-module.tar.gz
$ for f in *.gz; do tar xzvf $f; rm -f $f; done
...untar output...

$ ls -1
agentzh-redis2-nginx-module-62f5b6a
agentzh-set-misc-nginx-module-4b0512a
chaoslawful-lua-nginx-module-0e0b0fc
nginx-1.0.0
ngx_http_upstream_keepalive-c6396fef9295
simpl-ngx_devel_kit-bc97eea

$ cd nginx-1.0.0
$ ./configure \
>     --prefix=/opt \
>     --conf-path=/etc/nginx/nginx.conf \
>     --add-module=../agentzh-redis2-nginx-module-62f5b6a \
>     --add-module=../agentzh-set-misc-nginx-module-4b0512a \
>     --add-module=../chaoslawful-lua-nginx-module-0e0b0fc \
>     --add-module=../ngx_http_upstream_keepalive-c6396fef9295 \
>     --add-module=../simpl-ngx_devel_kit-bc97eea \
>     --add-module=/usr/local/rvm/gems/ruby-1.8.7-p330@default/gems/passenger-3.0.6/ext/nginx

...configure output...

Configuration summary
  + using system PCRE library
  + OpenSSL library is not used
  + md5: using system crypto library
  + sha1: using system crypto library
  + using system zlib library

  nginx path prefix: "/opt"
  nginx binary file: "/opt/sbin/nginx"
  nginx configuration prefix: "/etc/nginx"
  nginx configuration file: "/etc/nginx/nginx.conf"
  nginx pid file: "/opt/logs/nginx.pid"
  nginx error log file: "/opt/logs/error.log"
  nginx http access log file: "/opt/logs/access.log"
  nginx http client request body temporary files: "client_body_temp"
  nginx http proxy temporary files: "proxy_temp"
  nginx http fastcgi temporary files: "fastcgi_temp"
  nginx http uwsgi temporary files: "uwsgi_temp"
  nginx http scgi temporary files: "scgi_temp"

$ make
...make output...

$ make install
...install output...

A lot of these modules were written by the very awesome agentzh, so a big thanks to him. He’s working on something very exciting, a full fledged web application server in nginx and lua! Will definitely be keeping my eye on that project.

You’ll notice I add the Phusion Passenger module in with the path to my gem. You can omit that if you’re not using Passenger.

3. Redis structure

This is a good time to figure out where things are going to live in redis. We have two bits of information we need to store:

  1. Resource versions, which will be numbers that we increment when something changes in the app in order to invalidate the cache
  2. Cached content, which will be written by the app after a cacheable request is complete, so that future requests can be served from cache

For this post, I’m storing the resource version numbers in “resource_versions”, which will be a hash keyed by the request URI. The cached content itself will live in the root of the redis database, keyed by the request URI plus “:version=n”, where n is the resource version. Like this:

1
2
3
4
5
6
7
8
9
10
{
  "resource_versions": {
    "http://myproject.dev/": 1,
    "http://myproject.dev/foos": 2,
    "http://myproject.dev/foo/123": 3,
  },
  "http://myproject.dev/:version=1": "<html>...</html>",
  "http://myproject.dev/foos:version=2": "<html>...</html>",
  "http://myproject.dev/foo/123:version=3": "<html>...</html>",
}

Why not also store the cached content in a hash? The redis LRU eviction policy evicts keys from the root of the hash when the memory limit is reached; if there were only two keys, then either all our cached content would be evicted, or all our resource versions. Storing the cached content in the root ensures that it will be a least recently used bit of HTML that gets evicted.

4. Configure nginx

First thing you need to do is an an upstream block in your nginx.conf pointing to your redis server:

1
2
3
4
5
6
7
8
# keepalive connection pool to a single redis running on localhost
upstream redis {
  server localhost:6379;

  # a pool with at most 1024 connections
  # and do not distinguish the servers:
  keepalive 1024 single;
}

Keepalive connections are more efficient than creating a new connection to redis every time; this is enabled by the the ngx_http_upstream_keepalive module compiled into nginx.

Nginx has a powerful internal system called subrequests. It basically allows complex request rerouting internally to nginx that remains transparent to both the client and application. In this nginx config, internal locations are used to pass off requests further down the chain as necessary.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
server {
  listen 80;
  server_name myproject.dev;
  root /Users/mferrier/dev/myproject/public;

  location / {
    # try to serve files directly from root, otherwise pass to @cache
    try_files $uri @cache;
  }

  location @cache {
    internal;
    default_type   text/html;

    set $full_uri $scheme://$host$request_uri;

    content_by_lua_file '/Users/mferrier/dev/myproject/config/nginx.cache.lua';

    error_page     404 = @app;
  }

  location @app {
    internal;
    passenger_enabled on;
  }
}

First we check for the existence of the requested file in the filesystem. If it doesn’t exist, we pass control to @cache. @cache uses the content_by_lua_file directive from the Lua nginx module to specify that the content for this request should be generated by an external lua script. If that script returns a 404, then we pass control down to @app. @app is our application, in this case a Rails app handled by Passenger.

The equals sign = after the error code specifies to ultimately use the response code returned by @app rather than the 404 returned by @cache.

We also need some internal locations to simplify the querying of redis. Our structure will require GET requests for the cached content in the root of the database, and HGET requests for the resource versions stored at resource_versions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# requires the "key" argument
# http://redis.io/commands/get
location /redis_get {
  internal;
  set_unescape_uri $key $arg_key;
  redis2_query get $key;

  redis2_connect_timeout 200ms;
  redis2_send_timeout 200ms;
  redis2_read_timeout 200ms;
  redis2_pass redis;

  error_page 500 501 502 503 504 505 @empty_string;
}

# requires the "hash_key and "key" argument
# http://redis.io/commands/hget
location /redis_hget {
  internal;
  set_unescape_uri $key $arg_key;
  redis2_query hget $arg_hash_key $key;

  redis2_connect_timeout 200ms;
  redis2_send_timeout 200ms;
  redis2_read_timeout 200ms;
  redis2_pass redis;

  error_page 500 501 502 503 504 505 @empty_string;
}

# returns an empty string
location @empty_string {
  internal;
  content_by_lua 'ngx.print("")';
}

Both /redis_get and /redis_hget are meant to be used in an ngx_lua block with ngx.location.capture and redis.parser.parse_reply (more on that in the next step.)

You’ll also notice some sensible timeouts, and we pass control of any errors to the @empty_string internal location, defined last. This location serves as a rescue, and returns an empty string back to @cache, which treats an empty string as a cache miss. So if the redis server goes away or takes too long, it ends up being a cache miss rather than a 500 on the request.

All that is needed now is the lua script which will check for cached content in redis, and either return that content or return a 404 if it wasn’t found.

5. Cache script

In the previous step, we specified that the content for the @cache internal location was to be handled by the script nginx.cache.lua. Every incoming request which isn’t a request for a static file will be handled by this script, and it will either return some cached content, or pass the request along to @app.

This script needs to:

  1. Determine if the request is cacheable based on the request method and request path, and return HTTP_NOT_FOUND if it isn’t
  2. Try to grab the current version of the requested resource from redis, and return HTTP_NOT_FOUND if it doesn’t exist
  3. Construct the cached content key for the requested resource from the result of the previous step
  4. Try to grab the cached content from redis using the cached content key from the previous step, and return HTTP_NOT_FOUND if no cached content is found Otherwise, we have a cache hit and can return the cached content

Remember, a 404 response code in the @cache location causes control to be passed to @app.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
if (ngx.var.request_method ~= "GET" and ngx.var.request_method ~= "HEAD") then
  ngx.log(ngx.NOTICE, "@cache: skipping uncacheable request method: ", ngx.var.request_method)
  ngx.exit(ngx.HTTP_NOT_FOUND)
end

-- lua patterns, not regexes
local cacheable_resource_matchers = {
  "^/$",
  "^/foo",
}

-- whether the request is cacheable
local cacheable = false

for i, matcher in ipairs(cacheable_resource_matchers) do
  if (string.find(ngx.var.uri, matcher)) then
    ngx.log(ngx.NOTICE, "@cache: cacheable request found: ", ngx.var.host, ngx.var.uri)
    cacheable = true
    break
  end
end

if (cacheable == false) then
  ngx.log(ngx.NOTICE, "@cache: skipping uncacheable request: ", ngx.var.host, ngx.var.uri)
  ngx.exit(ngx.HTTP_NOT_FOUND)
end

-- parser object that will receive redis responses and parse them into lua objects
local parser = require("redis.parser")

-- key in redis that stores the resource version numbers
local version_hash_key = "resource_versions"

-- full uri of the request, used to construct the cache key
local full_uri = ngx.var.scheme.."://"..ngx.var.host..ngx.var.request_uri

-- key under which the current version of this resource is stored
local version_key = ngx.var.request_uri
local response_body = ngx.location.capture("/redis_hget",
    {args = {hash_key = version_hash_key, key = version_key}}).body
local res, typ = parser.parse_reply(response_body)

if (typ == parser.BULK_REPLY and not(res == nil) and (#res > 0)) then
  ngx.log(ngx.NOTICE, "@cache: cache HIT on version key ", version_key, ", value: ", res)

  local version_value = tonumber(res)
  local cache_key = string.format("%s:version=%s", full_uri, version_value)
  local response_body = ngx.location.capture("/redis_get",
      {args = {key = cache_key}}).body
  local res, typ = parser.parse_reply(response_body)

  if (typ == parser.BULK_REPLY and not(res == nil) and (#res > 0)) then
    ngx.log(ngx.NOTICE, "@cache: cache HIT on cache key: ", cache_key, ", content length: ", #res)
    ngx.print(res)
    ngx.exit(ngx.OK)
  else
    ngx.log(ngx.NOTICE, "@cache: cache MISS on cache key: ", cache_key)
  end
else
  ngx.log(ngx.NOTICE, "@cache: cache MISS on version key: ", version_key)
end

ngx.exit(ngx.HTTP_NOT_FOUND)

In this script we do opt-in caching: only the locations we specify in cacheable_resource_matchers are eligible to be cached. The opposite of this would be opt-out caching, where everything is cached unless we specify it shouldn’t be. I find opt-in caching to be safer, because it’s generally worse to cache something that shouldn’t be rather than not cache something that should be.

The cacheable resource matchers are Lua Patterns, which are kind of like regular expressions, but a bit less powerful: you can’t use the logical OR operator “|”. If you need full blown regular expressions, there are lua regex libraries you can install.

One of the great things about the lua nginx module is that code is automatically cached between requests. That means you don’t have to worry about the require statement in the lua script; it will only ever happen once.

6. Configure Redis

Adding these two lines to your redis config will ensure that your memory usage never exceeds the limit you set:

1
2
maxmemory 64mb
maxmemory-policy allkeys-lru

7. Configure your app

All that remains to be done at this point is to set up your app so that it will do two things:

  1. Write back the result of a cacheable request to redis
  2. Increment the resource version when a resource is updated

Most of this should be customized to your particular app, but here’s the basic framework I use in Rails.

First we need to set up redis and the around_filter in ApplicationController:

config/initializers/redis.rb

1
2
REDIS_CONFIG = YAML.load_file(Rails.root.join('config', 'redis.yml'))[Rails.env].with_indifferent_access
$REDIS = Redis.new REDIS_CONFIG

app/controllers/application_controller.rb:

1
2
3
class ApplicationController < ActionController::Base
  around_filter Cache
end

app/controllers/cache.rb:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
module Cache
  CACHEABLE_RESOURCE_MATCHERS = [
    "^/$",
    "^/foo",
  ]

  VERSION_HASH_KEY = "resource_versions"
  CACHE_KEY_FORMAT   = "%s:version=%s"

  def request_cacheable?(request)
    return false unless (request.method == "GET" || request.method == "HEAD")
    CACHEABLE_RESOURCE_MATCHERS.any? do |pattern|
      request.path =~ /#{pattern}/
    end
  end

  def response_cacheable?(response)
    response.status == 200
  end

  def version_key_for_request(request)
    "#{request.scheme}://#{request.host}#{request.fullpath}"
  end

  def version_value_for_request(request)
    query_safely do |cache|
      cache.hget(VERSION_HASH_KEY, version_key_for_request(request))
    end
  end

  def cache_key_for_request(request, version = 0)
    full_url = "#{request.scheme}://#{request.host}#{request.fullpath}"
    CACHE_KEY_FORMAT % [full_url, version]
  end

  def cache_response(request, response, version_value)
    query_safely do |cache|
      cache.multi do
        # if version value is nil, ensure it hasn't been set since the beginning
        # of this request so that we don't clobber it
        version_value ||= version_value_for_request(request)
        if version_value.nil?
          version_key = version_key_for_request(request)
          log %{initializing version key "#{version_key}" with value "0"}
          cache.hset(VERSION_HASH_KEY, version_key, 0)
          version_value = 0
        end

        cache_key = cache_key_for_request(request, version_value)
        log %{writing cache: key = "#{cache_key}", content length #{response.body.length})}
        cache.set(cache_key, response.body)
      end
    end
  end


  def filter(controller)
    if request_cacheable?(controller.request)
      version_value = version_value_for_request(controller.request)
      yield
      if response_cacheable?(controller.response)
        cache_response(controller.request, controller.response, version_value)
      end
    else
      yield
    end
  end

  def invalidate_cache_for_url(url)
    query_safely do |cache|
      cache.hincrby(VERSION_HASH_KEY, url, 1)
    end
  end

  def log(msg, level = :info)
    Rails.logger.send(level, %{[CACHE] #{msg.to_s}})
  end

  # yields the redis client, but catches connection errors. use this when you 
  # don't mind if your cache operation fails silently.
  def query_safely
    begin
      yield $REDIS
    rescue Errno::ECONNREFUSED
      log %{ERROR: Connection refused while connecting to redis! Discarding query silently.}, :warn
    rescue Errno::EAGAIN
      log %{ERROR: Connection timeout while querying redis! Discarding query silently.}, :warn
    end
  end
end

It has been said that there are only two hard problems in computer science: naming things and cache invalidation. Implementing effective cache invalidation for your particular application is left as an exercise for the reader, but as an example let’s say you have a Foo model whose current state affects the paths /foos and /foo/:id. You could write an observer like this:

app/models/foo_observer.rb:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class FooObserver < ActiveRecord::Observer
  def after_save(record)
    return unless record.changed?

    afftected_urls(record).each do |u|
      Cache.invalidate_cache_for_url u
    end
  end

  def after_destroy(record)
    afftected_urls(record).each do |u|
      Cache.invalidate_cache_for_url u
    end
  end

  def affected_urls(record)
    [
      "http://myproject.com/foos",
      "http://myproject.com/foo/#{record.to_param}",
    ]
  end
end

config/application.rb

1
2
3
4
5
module MyProject
  class Application < Rails::Application
    config.active_record.observers = :foo_observer
  end
end

8. Conclusion and Benchmark

By serving content from nginx, you can easily see 1000% improvement in requests per second served. From a baseline Rails app served on a High CPU Medium instance on EC2 that serves around 100 requests per second, here’s a benchmark once the caching is added:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
$ ab -n 1000 -c 100 http://testserver/
This is ApacheBench, Version 2.3 <$Revision: 655654 $>
Copyright 1996 Adam Twiss, Zeus Technology Ltd, http://www.zeustech.net/
Licensed to The Apache Software Foundation, http://www.apache.org/

Benchmarking ocadportfolio.com (be patient)
Completed 100 requests
Completed 200 requests
Completed 300 requests
Completed 400 requests
Completed 500 requests
Completed 600 requests
Completed 700 requests
Completed 800 requests
Completed 900 requests
Completed 1000 requests
Finished 1000 requests


Server Software:        nginx/0.8.54
Server Hostname:        testserver
Server Port:            80

Document Path:          /features
Document Length:        8357 bytes

Concurrency Level:      100
Time taken for tests:   0.970 seconds
Complete requests:      1000
Failed requests:        0
Write errors:           0
Total transferred:      8540096 bytes
HTML transferred:       8394800 bytes
Requests per second:    1031.12 [#/sec] (mean)
Time per request:       96.982 [ms] (mean)
Time per request:       0.970 [ms] (mean, across all concurrent requests)
Transfer rate:          8599.47 [Kbytes/sec] received

Connection Times (ms)
              min  mean[+/-sd] median   max
Connect:        9   11   2.5     10      41
Processing:    22   83  32.2     84     263
Waiting:       11   73  32.4     74     254
Total:         32   94  32.6     95     274

Percentage of the requests served within a certain time (ms)
  50%     95
  66%    117
  75%    119
  80%    121
  90%    129
  95%    142
  98%    163
  99%    168
 100%    274 (longest request)

Over 1000 requests per second, with a 96ms mean request time, and less than 1ms mean time across all concurrent requests. This setup also has the nice side effect of being able to serve cached content even if the application is completely down. Not too shabby!

It’s also worth noting that recently Salvatore Sanfilippo, author of redis, added experimental lua scripting to a side branch of redis. This seems to have gotten a lot of positive feedback from the community, and it should find its way into the master branch pretty soon. This basically adds the same embedded lua scripting support to redis, which means the same sorts of things implemented in nginx in this post could be achieved on the server side of redis without any special nginx modules.

Code for this post can be found here. If you have any questions, feel free to post in the comments.

If you enjoyed this post, feel free to upvote on hackernews.

Comments