One of the bigger challenges with deploying dynamic web servers is being able to cope with load peaks that happen when the URL is communicated to larger communities in a short time. I have seen several sites being slashdotted and collapse under the load, and it is common to blame the underlying server technology for crashes; being Lisp lovers, we don't want to see that happen for our sites.

Using a caching frontend to reduce backend load

Following industry practice, we have been using a caching reverse proxy in front of our Lisp based dynamic web servers from the beginning. Our choice was Squid, as I had prior experience configuring it and found it to work reliably once the configuration was in place. I was never quite happy with that choice, though, because Squid's main operation mode is forward proxying. It has gazillions of configuration options that are not needed for a reverse proxy, which made us feel that Squid would not be a perfect match for our demands.

This is not to say that Squid has hurt us in any way. It has served us well during a load peak on the create-rainforest web site, but as reverse proxying has become very common in the last few years, we found it about time to go shopping for a solution that might be a better match to our needs.

We hoped to find a frontend proxy having the following features:

• Caching - We want the frontend to cache all content that is not session dependent in order to reduce the load on our Lisp backend.
• Scalable - The frontend must be able to handle loads much larger than what we see normally in order to accomodate for peaks.
• Request queueing - Ideally, we'd like the frontend to handle all concurrency issues and send requests to the backend one after the other using a single persistent http connection, maybe with pipelining.

Evaluating varnish

varnish seems to have most of the features that we require: It supports caching, has been tested under very high loads and supports FreeBSD which is our deployment platform. Varnish has been written by Poul-Henning Kamp of FreeBSD fame, so we also found it to be culturally compatible.

Our evaluation revealed that varnish is under active development and support, and we found the developers be very responsive to our bug reports and requests. Its architecture looks well thought out, and the configuration language (even if underdocumented) makes the request handling process very transparent.

There are a number of downsides with varnish, though:

We would have liked to switch to varnish because of the very good support and because it is meant to be a web frontend, nothing else. Yet, at the current point in time, it does not seem to be mature enough to serve our needs. After having evaluated it, we turned back to squid as it seemed to be the only other option. We found that squid meets our requirements for cache cleaning and revalidation of cached objects very well.

Making objects cacheable

Chosing a front end software is only part of what needs to be done to make a web system fast and robust enough to withstand high loads. The most important factor is to make the frontend serve a large percentage of the incoming requests from its cache and only consult the backend server for content that is really dynamic. The HTTP/1.1 protocol provides for request and response headers that control how content can be cached, and there is little need for explicit configuration if these headers are used correctly.

Using If-modified-since

One way to limit the traffic to the backend is implement the If-modified-since mechanism. It is supported by Hunchentoot for static files by default, and can also be used for dynamic handlers that can check whether a resource has changed since it had previously been requested. Varnish will set the If-modified-since header when it requests resources that it already has in the cache, so every cacheable resource will normally be transfered from the backend to Varnish only once.

Controlling cache refreshing

Often, resources are dynamic, yet it is not crucial that every client sees the absolutely latest version of the resource. For example, in our square meter sales application, visitors should always see the current number of square meters sold, but it is not vital that this information is accurate to the second. Thus, we want the cache to refresh such pages only at a certain interval. The HTTP/1.1 provides for the cache-control directive and in particular the max-age parameter. It specifies how long a cache may consider a cached resource be valid without revalidating with the originating server. By setting this parameter in responses sent by the backend, we can effectively limit the maximum refresh rate for dynamic resources that do not need completely up to date every time.

Testing realistically

In order to test the performance of a Web system, it needs better tools than the often-used ApacheBench tool, which only tests response times and throughput of a single URL. For meaningful results, one should simulate a user load that reflects the load that real users create. I have been using SIEGE for informal testing often, as it is easy to use, but I have also found it a little flakey and prune to random crashes, which made us look for more reliable solutions.

In the FreeBSD ports collection, we found tsung. Tsung is an open-source multi-protocol distributed load testing tool written in Erlang, and it has good support for HTTP. In addition to running load tests against web servers and generating statistics reports, it supports a session recorder that can be used to create a log of the URLs that a user visits when browsing a web server which can then be directly used to simulate many simultaneous users. As an added bonus, it is possible to capture dynamically generated information from web server responses into variables and use them in subsequents requests in a session. This feature can be used to generate sale transactions or user registrations in a load simulation.

Using tsung and squid, we were able to tune our Lisp backend so that all non-dynamic content is served from the cache, pinpoint a serious performance problem and simulate realistic loads. We are now confident that our setup can withstand the next rush of users without crashing.

Shadowing functions is useful for example when testing.
Suppose we want to build a tiny test suite around the following function:

 
(defparameter *appointment* ...)
 
(defun overdue-p ()
  (>= (get-universal-time) *appointment*))

Testing OVERDUE-P obviously requires us to test two branches: one where the appointment is overdue and one where it is not.

Let’s say that you can’t change *APPOINTMENT* in your testing context for whatever reasons (the reason here being that this example is ultra-contrived for simplicity).
Assuming a fixed value for *APPOINTMENT* we need to change the return value of CL:GET-UNIVERSAL-TIME. This can be achieved by shadowing this function for the duration of our test.

Unfortunately, shadowing a function in Common Lisp isn’t obvious.

You can’t use FLET or LABELS because they have lexical scope.
You can’t use DEFUN either because it affects the global function namespace and doesn’t let you save or restore the old definition.

The only way I know of is using the function (SETF FDEFINITION):

(let ((orig (fdefinition 'get-universal-time)))
  (setf (fdefinition 'get-universal-time) (lambda () *my-testing-time*))
  (prog1
    (overdue-p) ; you'd run some test checks against the result here
    (setf (fdefinition 'bar) orig)))

Wrapping this in a macro is left as an exercise to the reader.

This doesn’t work for special operators, and neither for FLET or LABELS. See the CLHS entry for accessor FDEFINITION.

The other day, I realized that there wasn't a great place to discuss Lisp that was using a post-Y2K sort of interface. Sure, comp.lang.lisp has been around forever, and through Google Groups it has an HTTP interface, but when you post to Usenet you become an instant spam magnet. And new users think an all text-mode interface with no markup is just so 1985. And yes, there's always #lisp on Freenode.net IRC, which is great for realtime, but bad for searching for coherent answers.

So, I created Lisp Forum: www.lispforum.com

The content is a bit sparse right now. That's where you come in. Please register, hang out, and participate. My goal is to make this a friendly place with a bit less Smug Lisp Weenie-ness than comp.lang.lisp, suitable for both newcomers and old pros.

I came across geohash.org while browsing the Semantic Web last night. This site uses a simple latitude/longitude encoding to convert locations into short strings. Here, for example, is the URL for my house.

http://geohash.org/drs3nbcszvze

The nice thing is that strings with common prefixes are geographically close to one another. I saw that there were several ports of the algorithm to Ruby, Perl, PHP, etc. but no Common Lisp love. The geohash system on Common-Lisp.net fixes that! Enjoy

When benchmarking, it is all too easy to use the Common Lisp [time][time] macro to see how long something takes. For example,

(time (dotimes (i 1000) (do-my-function)))

There are at least two problems with this simple approach. Firstly, time doesn’t make it easy to record the values it computes; secondly, if your function is very fast, you may end up timing how quickly your lisp execute dotimes rather than measuring what you want. A better way to approach this sort of question is to ask “how many times can I execute my function in, e.g., 5-seconds?” The only downside of this approach is that it takes a little more code to set things up. Once you have the code, however, Bob is your uncle. [LIFT][] includes a small (and sadly under-documented) selection of functions and macros to help you benchmark and profile your code. Two of these are:

(defun count-repetitions (fn delay)
  "Funcalls `fn` repeatedly for `delay` seconds. Returns
the number of times `fn` was called. Warning: the code
assumes that `fn` will not be called more than a fixnum
number of times."
   ...)

and

(defmacro while-counting-repetitions ((&optional (delay 1.0)) &body body)
"Execute `body` repeatedly for `delay` seconds. Returns
the number of times `body` is executed per second.
Warning: assumes that `body` will not be executed more
than a fixnum number of times. The `delay` defaults to
1.0."
  ...)

The main difference between the two variants — well, aside from one being a macro and one a function — is that count-repetitions must funcall your function whereas while-counting-repetitions includes your code in-line.

Let’s use them to look at three different solutions for the perennial “I want to turn a string into a keyword” problem. I’m also going to require that all of the strings be lowercased (just because). One solution uses read-from-string

(defun form-keyword-1 (name)
  (read-from-string (format nil "~(:~A~) " name)))

another uses intern. We’ll look at two variants: the first looks up the keyword package each time; the second does it just once:

(defun form-keyword-2a (name)
  (intern (string-downcase name) (find-package '#:keyword)))

(defun form-keyword-2b (name)
  (intern (string-downcase name)
    (load-time-value (find-package '#:keyword))))

Lastly, let’s see if there is any cost to calling intern unnecessarily by adding a variant that first uses find-symbol and only calls intern if it must.

(defun form-keyword-3 (name)
  (let ((downcased-name (string-downcase name))
        (keyword-package (load-time-value (find-package '#:keyword))))
    (or (find-symbol downcased-name keyword-package)
        (intern downcased-name keyword-package))))

Here’s what it looks like to try a simple test. We’ll use 5-seconds as our delay.

cl-user> (lift:count-repetitions
           (lambda () 
             (form-keyword-1 "hello")
             (form-keyword-1 "butter")) 
           5.0)
57214.8

So form-keyword-1 (the read-from-string variant) can run about 57,000-times a second (this is under ACL in EMACS under Slime). The other three variants give counts of:

          ACL        SBCL
 1:    57,215      37,354
2a:   689,888     329,896
2b:   986,085     447,137
 3: 1,028,928     461,868

(Note: I’m using a somewhat out of date SBCL so these numbers shouldn’t be used to compare these two Lisps).

That’s a pretty huge difference on both of these Lisps. Allegro especially benefits from the load-time-value resolution of the keyword package and both Lisps should a slight improvement when calling find-symbol first (which actually surprised me. I would have thought that intern would have handled that logic already.)

Now lets see if funcalling is doing anything to change the results by switching over to the while-counting-repetitions macro:

cl-user> (lift:while-counting-repetitions (5) 
           (form-keyword-1 "hello")
           (form-keyword-1 "butter"))
57633.6

Here’s the table

          ACL        SBCL
 1:    57,634      37,960
2a:   686,941     328,316
2b:   992,373     451,186
 3: 1,050,546     448,714

In this example, at least, the macro and the function appear to have no advantages one over the other.