Zack Galler's Experience with Stateful vs Stateless Web Apps

Communication using HTTP between client and server is a simple problem of halted computation.

A client computes a request, transmits and halts, waiting for a server response. On receipt, the server computes a response, transmits and halts, waiting for the next client request.

This much is well known.

Racket's magnificent stateful Web server does three things on the server side:

1. it reifies a Racket continuation, capturing where the server computation has halted.
2. it externalizes the continuation, creating a URL-representation that uniquely maps to the Racket continuation
3. it disseminates the externalized continuation to interested clients, typically via HTTP response, but alternately via SMTP or any other protocol.

Then, it waits.

Later, when presented with an externalized continuation, a quick inverse mapping occurs, the underlying Racket continuation is invoked, and the server processes the new client request.

Rinse and repeat.

The problem with this approach is twofold

1. the reified Racket continuations live in server memory. And there's no safe way to garbage collect, as the continuations could be invoked at any time. There are strategies to reclaim memory, but some load level will noticeably decrease the performance of your application. And its not possible to figure out what that load level is prior to finishing your application. This is a problem.
2. Again, the reified Racket continuations live in server memory and cannot be moved. So there's no way to scale an application to more than one server. It's a necessarily one machine system. This makes problem #1 worse.

Racket's yet more magnificent stateless Web server does exactly the same three things:

1. to reify, it rewrites the entire call stack into a format known as A-Normal Form (ANF).
2. to externalize, the ANF'd stack is encoded for transmission over HTTP.
3. and then it's sent over to the client (dissemination).

Later, when presented with encoded stack, the stateless server performs an inverse transform to reconstruct the call stack, at which point the server keeps going.

So we've lost the invocation step and substituted a reconstruction.

But in exchange, we've eliminated continuations from server memory, and solved both enumerated problems above. Neat trick.

I provide a few lessons learned for the archives for the next person to attempt porting #lang racket to #lang web-server code.

First, the predicate serializable? from racket/serialize is invaluable. The #lang web-server code will not transform if there are non-serializable constructs in the dynamic extent of the invocation of send/suspend, such as a local binding or argument.

Second, invocations of native continuations reified with call/cc frequently throw errors related to continuation prompts, such as “attempt to cross a continuation barrier” or “no corresponding prompt tag in continuation”. In all cases, I was able to remedy the situation by enclosing the invocation in call-with-continuation-prompt. This may be an error in the system, but it is unclear at this time.

Third, the transformation does not allow parameters or dynamic-wind, because the internal data-structures representing them are not serializable, but continuation-marks can be used to reimplement the piece of the functionality you need.

Finally, thank you to the Racket team. I think the stateless Web language is important technology and must have required an enormous amount of work to implement.

Anecdotally, application speed seems at or better than the stateful code.

To learn more about the stateless Web application infrastructure, consult the manual or post to the mailing list.

(This post was written by Zack Galler with minor edits before posting by Jay McCarthy.)

The Two-State Solution: Native and Serializable Continuations Accord

The Racket Web Server allows an expressive way of writing Web applications using first-class continuations to capture the control-flow of the server while it is waiting for the client to respond. For example:

#lang web-server/insta
(define (get-number p)
  (string->number
   (extract-binding/single
    'num
    (request-bindings
     (send/suspend
      (λ (k-url)
        `(html 
          (body
           (form ([action ,k-url])
                 ,p nbsp (input ([name "num"]))
                 (input ([type "submit"])))))))))))
(define (start req)
  (define how-many
    (get-number "How many numbers to add?"))
  (number->string
   (foldr 
    + 0
    (build-list 
     how-many
     (λ (i)
       (get-number 
        (format "Provide number: ~a" 
                (add1 i))))))))

This application creates a re-usable get-number interaction abstraction and uses it in a number of different contexts. In particular, it uses it in the higher-order context of build-list. This application also reuses useful third-party library functions like foldr, etc.

Such an application would be complicated to write in a traditional Web programming environment because the continuation of each get-number invocation is considerably more complex than is typical. Yet, the first-class continuations in Racket ensure that this continuation is captured exactly, correctly, every time.

Unfortunately, the native first-class continuations of Racket are not serializable, so they impose a per-session resource expenditure on the server. This can be alleviated through expiration policies, but such policies are inherently unsound because continuations URLs are global roots.

In the past, PLT has provided tools that automatically restructure this kind of program into one that uses serializable continuations through an acronym soup of source transformations: CPS, lambda-lifting, defunctionalization, SPS, and so on. These tools effectively create automatically what most Web programmers write manually, except the tools don't mistakes. But the tools also don't take into consideration what functions actually contribute to the interaction context and transform library functions like foldr (which is unnecessary in the continuation) the same as functions like build-list (which are necessary.)

Our past work (based on another PLT paper) alleviates this problem by only requiring functions like build-list to be transformed. From the perspective of a programmer, "transformed" is tantamount to "rewritten" because the source code for a third-party library may not be readily available. Programmers would have to program add-many-numbers.com as:

#lang web-server
(require web-server/servlet-env)
(define (get-number p)
  (string->number
   (extract-binding/single
    'num
    (request-bindings
     (send/suspend
      (λ (k-url)
        `(html 
          (body
           (form ([action ,k-url])
                 ,p nbsp (input ([name "num"]))
                 (input ([type "submit"])))))))))))
(define (build-list n f)
  (for/list ([i (in-range n)])
    (f i)))
(define (start req)
  (define how-many
    (get-number "How many numbers to add?"))
  (number->string
   (foldr 
    + 0
    (build-list
     how-many
     (λ (i)
       (get-number 
        (format "Provide number: ~a"
                (add1 i))))))))
; This requires a pre-release version
; to run in an un-named DrRacket buffer
(serve/servlet start #:stateless? #t)

where build-list has been re-implemented, but functions like foldr have not. This application, despite its striking similarity to the first, requires absolutely no per-session server state, so it is considerably more scalable.

Do we need to re-implement build-list? What if the third-party, higher-order function (build-list) that we use with a higher-order argument that causes Web interaction (get-number) is too complicated to re-implement?

Naturally this blog post would not exist if we didn't solve this problem.

Our new approach, dubbed The Two-State Solution, allows the programmer to transparently use a very small amount of per-session server state to store just the part of the continuation inside functions like build-list while serializing everything else to the client.

The key is to use delimited, composable continuations to isolate the appropriate part of the continuation. The programmer designates this piece of the continuation through the serial->native and native->serial annotations. The programmer can write the application as:

#lang web-server
(require web-server/servlet-env)
(define (get-number p)
  (string->number
   (extract-binding/single
    'num
    (request-bindings
     (send/suspend
      (λ (k-url)
        `(html 
          (body
           (form ([action ,k-url])
                 ,p nbsp (input ([name "num"]))
                 (input ([type "submit"])))))))))))
(define (start req)
  (define how-many
    (get-number "How many numbers to add?"))
  (number->string
   (foldr 
    + 0
    (serial->native
     (build-list
      how-many
      (λ (i)
        (native->serial
         (get-number 
          (format "Provide number: ~a"
                  (add1 i))))))))))
; This requires a pre-release version
; to run in an un-named DrRacket buffer
(serve/servlet start #:stateless? #t)

The important distinction here is that both the build-list and the get-number abstractions do not need to change. We simply mark the context as being a "serial" or "native" context through the annotation forms. This re-written version will be more scalable than a purely native version, but represents an easier to achieve step in the evolution of a program, because third-party, higher-order functions can be used as is.

This work will be presented at OOPSLA 2010. It is also described in a paper with same name this blog post: The Two-State Solution: Native and Serializable Continuations Accord.

Serializable Closures in PLT Scheme

PLT Scheme supports an extensible serialization system for structures. A structure is serializable if it has a prop:serializable property. There are many properties in PLT Scheme for other extensions, such as applicable structures and custom equality predicates.

The PLT Web application development framework uses these features to provide serializable continuations through a number of source transformations and a serializable closure structure.

Warning: This remainder post refers to features only available in the latest SVN revision of PLT Scheme.

I've recently made these closures more accessible to non-Web programs through web-server/lang/serial-lambda. Here's a demo:

#lang scheme
(require web-server/lang/serial-lambda
         scheme/serialize)

(define f
  (let ([z 5])
    (serial-lambda
     (x y)
     (+ x y z))))

(define (test-it)
  (printf "~S~n" (f 1 2))
  (let ([fs (serialize f)])
    (printf "~S~n" fs)
    (let ([df (deserialize fs)])
      (printf "~S~n" df)
      (printf "~S~n" (df 1 2)))))

> (test-it)
8
((2) 1 ((#"/Users/jay/Dev/svn/plt/collects/web-server/exp/test-serial.ss" . "lifted.6")) 0 () () (0 5))
#(struct:7a410aca70b31e88b4c2f0fe77fa7ffe:0 #)
8

Now, let's see how it is implemented. web-server/lang/serial-lambda is thin wrapper around web-server/lang/closure, which has two syntax transformer functions: define-closure! which defines the closure structure and make-closure which instantiates the closure. (The two tasks are separated to easily provide a user top-level definition syntax for named closures with different free identifires, rather than simply anonymous lambdas with fixed free identifiers.)

make-closure does the following:

1. Expands the procedure syntax using local-expand, so it can use free-vars to compute the free identifires.
2. Uses define-closure! to define the structure and get the name for the constructor.
3. Instantiates the closure with the current values of the free identifiers.

The more interesting work is done by define-closure!. At a high-level, it needs to do the following:

1. Create a deserialization function.
2. Create a serialization function that references the deserializer.
3. Define the closure structure type that references the serializer.
4. Provide the deserializer from the current module so that arbitrary code can deserialize instances of this closure type.

These tasks are complicated in a few ways:

1. The deserializer needs the closure structure type definition to create instances and the serializer needs the closure structure type to access their fields.
2. The serializer needs the syntactic identifier of the deserializer so that scheme/serialize can dynamic-require it during deserialization.
3. The deserializer must be defined at the top-level, so it may be provided.
4. All this may occur in a syntactic expression context.

Thankfully, the PLT Scheme macro system is powerful to support all this.

• syntax-local-lift-expression allows a syntax transformer to lift an expression to the top-level of a module and returns the identifier it is bound to.
• syntax-local-lift-values-expression (added in 4.2.0.3) provides the same for expressions that return multiple values, such as make-struct-type, which is used to define structures.
• syntax-local-lift-provide (added in 4.2.0.4) allows a syntax transformer to lift a provide to the top-level.

The only complicated piece is allowing the deserializer and serializer to refer to the closure structure constructor and accessors. This is easily accomplished by first defining lifting boxes that will hold these values and initializing them when the structure type is defined. This is safe because all accesses to the boxes are under lambdas that are guaranteed not to be run before the structure type is defined.

An aside on the closure representation. The closure is represented as a structure with one field: the environment. The environment is represented as a thunk that returns n values, one for each of the free identifiers. This ensures that references that were under lambdas in the original syntax, remain under lambdas in the closure construction, so the serializable closures work correctly inside letrec. This thunk is applied by the serializer and the free values are stored in a vector. The closure also uses the prop:procedure structure property to provide an application function that simply invokes the environment thunk and binds its names, then applys the original procedure syntax to the arguments.

An aside on the serializer. The deserializer is bound to lifted identifier which is represented in PLT Scheme as an unreadable symbol. Version 4.2.0.5 added support for (de)serializing these.

The Two State Solution: Native and Serializable Continuations in the PLT Web Server

One of the annoyance of the stateless Web application language that comes with the PLT Web Server is that you can't call third-party higher-order library procedures with arguments that try to capture serializable continuations. (I know, you try to do that all the time.) For example:

(build-list
 3
 (lambda (i)
   (call-with-serializable-current-continuation
    (lambda (k) (serialize k)))))

The problem is that the stateless language performs a transformation on your program to extract the continuations into a serializable representation. If you really need to do this, we've developed a compromise called "The Two State Solution": one state on the client and the other on the server. Only the third-party parts of the continuation (in this case, the code inside build-list) are stored on the server; everything else is shipped to the client. You just need to annotate your code slightly to indicate where the transition is:

(serial->native
 (build-list
  3
  (lambda (i)
    (native->serial
     (call-with-serializable-current-continuation
      (lambda (k) (serialize k)))))))

serial->native signals the transition to the third-party and native->serial signals the transition back.

It is still a little annoying to find when you've called these third-party higher-order library procedures with arguments that try to capture serializable continuations, so there's a simple macro that provides a transitioning wrapper for you:

(define-native (build-list/native _ ho) build-list)

expands to:

(define (build-list/native fst snd)
  (serial->native
   (build-list
    fst
    (lambda args
      (native->serial
       (apply snd args))))))

This new feature is documented in the online manual, of course.

Soft State in the PLT Web Server

Many Web applications and network protocols have values in the continuation that are necessary to complete the computation, but that may be recomputed if they are not available. This is "soft state".
For example, a Web application may cache a user's preferences from a database and deliver it to a Web browser as a hidden value; when the value is returned to the application in subsequent steps, it is used to customize the display. However, if the preferences were not available (or were corrupted in some way), the application could retrieve them from the database.
When using the PLT Web Server's native continuations, this roughly corresponds to the use of a weak box: a box that the GC is allowed to erase the contents of. When using the PLT Web Server's serializable continuations it roughly corresponds to a weak box and a weak hash table (that holds its keys weakly) to give the box a serializable value as an identifier.
This programming pattern is a bit difficult to get right. So, a library that implements it is now provided with PLT Scheme: web-server/lang/soft.
Here's a trivial example:

#lang web-server

(provide interface-version start)
(define interface-version 'stateless)

(define softie
  (soft-state
   (printf "Doing a long computation...~n")
   (sleep 1)))

(define (start req)
  (soft-state-ref softie)
  (printf "Done~n")
  (start
   (send/suspend
    (lambda (k-url)
      `(html (body (a ([href ,k-url]) "Done")))))))

What is send/suspend?

I often ponder what send/suspend really is. It is a lot like call/cc, but has the curious property that the continuation escapes in a single way and is only called in a particular context. I often wonder if there is something weaker than call/cc that implements send/suspend.

Today I wrote a little dispatcher that uses threads to implement send/suspend. In this implementation, sending truly suspends the computation.

Here's the code: http://www.copypastecode.com/codes/view/5003

The trick is to have channels for communicating responses and requests. When you run this example, you should be able to add two numbers. But, in contrast to the normal send/suspend, all the URLs are one-shots, because once the computation is resumed, it moves forward... it is never saved.

This implementation technique also precludes clever implementations of send/suspend/dispatch, like:

(define (send/suspend/dispatch mk-page)
  (let/cc k0
    (send/back
     (mk-page
      (lambda (handler)
        (let/ec k1 
          (k0 (handler (send/suspend k1)))))))))

Web Application Development in PLT Scheme

Many users often post to the plt-scheme mailing list asking for introductions to Web application development in PLT Scheme. They've heard of the continuation-based PLT Web Server and want a gentle introduction. Unfortunately, there has been a distinct lack of good documentation and tutorials for the server. Taking the cue from two users: Jens Axel Soegaard and David Reynolds, we've written a tutorial with Danny Yoo.

The tutorial is available at http://docs.plt-scheme.org/continue/index.html. It walks through the creation of a blog application, introducing features slowly and culminates in an SQL-backed database for the posts. Of particular interest, is the fast start servlet setup based on the Instaservlet package from Untyped.

Please take a look and pass along this as a pointer to those who may be interested in PLT Scheme.

A Privacy Flaw, Thwarted

My student Brendan Hickey recently identified the following security hole.

A university (let's call it Orange University) wants to let its graduating students vote on their graduation speaker. They used to do it by paper; catching up with the times, they now do it on the Web.

They used to have a box into which you could type the name of your nominee. But that is surely problematic: people misspell names, you have to argue about how to count ambiguous votes, someone will vote for their pet bonobo, etc. Better (perhaps) to give them the names of all the students and let them choose. [Alert: if Orange U adopts a simple naming scheme for email addresses, a student can immediately screen-scrape a pretty plum list to sell a spammer. Brendan and I noticed this in a femtosecond; I don't know why this didn't occur to the university.]

Anyway, now you have a Web page where people are going to choose, and the software that processes the responses must distinguish between these choices. You have to associate a key with each student. You've already got a key for each candidate: their student ID number. So you use that as your key. Now anyone viewing the page source can immediately see which student ID number goes with which student name. So much for confidentiality.

Whoops.

I'd like to point out that Pete Hopkins's send/suspend/dispatch, and the improved version of it by Jay McCarthy, identify and solve just this code structuring problem in a way that the privacy leak can never occur. For the most up-to-date presentation of it, read section 3.2 and section 4 of our paper.

Maybe Orange U should be using Scheme.

Experience Report: Scheme in Commercial Web Application Development

Our paper “Experience Report: Scheme in Commercial Web Application Development” is online. As the title suggests, it describes our experiences over the past year developing a number of web-based applications in PLT Scheme. If we'd chosen a language like Java or Ruby we could have used a large number of libraries developed for web apps, whereas PLT Scheme has relatively few libraries in this area, and they haven't been tested under high load. So we were gambling that Scheme would make us so productive we could develop our own libraries and the applications we were contracted to produce in the same time it would take to develop just the applications in another language. It was a gamble that paid off. You'll have to read the paper for all the details, but suffice to say we delivered the applications on time (and more are in development) and our libraries already compare well against big names like Ruby on Rails and J2EE.

On thing that got cut from the paper was our use of Flapjax is parts of the interface. If you write complicated Javascript to take a look at it. It really does simplify event handling, and our code using Flapjax is half the size of our original code without it.

Update: This is more or less the same post as on Untyping