Monday, August 18, 2008

Mobile Continuations for the Web

A continuation is basically the state of a program at the time the continuation was captured. For a common example, consider a blocking system call for any operating system. If the system call blocks the process, the continuation of that process is placed on a blocked queue until the system call completes. When the operation completes, the continuation is removed from the queue and resumed with the result of the system call.

There has been plenty of well-deserved hoopla around continuations for web interaction. Navigating a website is a great deal like operating on a program's continuations. A page generated from a server-side program contains references to a number of program continuations in its links and forms. Clicking a link or submitting a form invokes the captured continuation which the server then executes. The result is yet another set of continuations on the resulting page, ad infinitum.

Unfortunately, most continuation frameworks are designed around server-side continuations, where the continuations are saved on the server, and the client receives only a secure token naming the continuation. The Waterken server is a particularly beautiful example of this for Java. Awhile ago I ported an older version of the Waterken server to ASP.NET. Here is a public continuation for the comments page, and embedded in the comments page is the editing authority, which is an unguessable capability URL for the continuation to edit the comments page.

The Waterken "web-calculus" is actually a full blown persistent, distributed object system with a binding for the web.

However, maintaining persistent server-side state significantly complicates many aspects of web systems. It makes load balancing servers difficult, and persistent continuations are single threaded so only one invocation can proceed at a time which hurts scalability. Furthermore, if the continuations are persistent, as they are in Waterken which provides orthogonal persistence, then we must also contend with schema upgrade.

Two recent articles prompted me to re-examine these issues and devise a solution. First, Tommy McGuire posted a link to his "Infernal Device" paper on LtU. His paper describes a set of structures which can be used to develop an application by reifying the application's states as transitions in a finite state machine. The Transition objects are essentially application-specific partial continuations. The paper also details all of the different storage available in a browser, and how it can be exploited by a server to save state on the client.

For page-local state, the browser URL can hold up to 2kB on IE (other browsers can store more), and we have embedded form fields for POST requests. For site-local state, we have cookies which can be in the multi-kB size.

Then I came across this blog post about scaling Seaside by reducing the need to capture server-side state. The best way to optimize expensive operations is by avoiding them completely!

However, much program state does not need to reside on the server. We can capture a limited set of program state in the browser itself. In essence, we serialize the program continuation in the browser's URL or in its form fields. We also encrypt the serialized form to maintain integrity.

And so our program continuations have become mobile objects that migrate between client and server and can survive server restarts as long as any server state the continuations access also survives restart. A set of load balanced machines need only share the encryption keys, and user requests seamlessly migrate between them.

I've created a small library for mobile continuations written in C#. I also provide an IHttpHandler for use with ASP.NET. A web application using this library doesn't need to use any web controls or .aspx pages. An application is structured as a set of continuations which implement two operations: Show, and Apply. Show outputs the continuation via display-independent set of interfaces. Apply is invoked when a continuation receives a POST request. It takes a NameValueCollection containing all of the form's fields. This takes the place of a continuation's named arguments. I could implement a more elaborate system as found in the Waterken server where the fields are implicitly typed and named, but I felt a more limited scope is preferable for the time being.

By convention, continuations in the research literature are generally named "k", so the continuation interface is named K. This simple HelloWorld class implements the K interface and it embeds a continuation to an Adder object in its display:
    public struct HelloWorld : K
{
public void Show(IWindow v)
{
v.Title("Hello world!");
v.Body(this);
}

public void Show(IBody v)
{
v.Const("Hello", "Hello world!");
v.Promise("Adder", new Adder());
}

public void Show(IInput v)
{
}

public K Apply(NameValueCollection args)
{
return this;
}
}

The Adder class is equally simple, consisting of a text input and a submit button. This continuation builds a form which submits to itself. When applying the continuation, it adds its currently stored value to the value specified in the form and returns a new instance of Adder with the stored value.
    public struct Adder : K
{
int n;
string e;
public Adder(int n)
{
this.n = n;
this.e = "";
}

public void Show(IWindow v)
{
v.Title("Adder!");
v.Body(this);
}

public void Show(IBody v)
{
if (!string.IsNullOrEmpty(e))
{
v.Const("error", "Error: " + e);
}
v.Literal(n);
v.Literal(" + ");
v.K("y", "add", this);
}

public void Show(IInput v)
{
v.Text("x", "", "");
}

public K Apply(NameValueCollection args)
{
try
{
return new Adder(this.n + int.Parse(args["x"]));
}
catch
{
this.e = "Invalid number specified.";
return this;
}
}
}
The library also provides a compact object serializer. HelloWorld serializes to 48 bytes. Adding some simple fields barely increases the size at all. You probably won't be entering any of these URLs by hand of course. There are a few more optimizations that can be made to the serializer as well. CrystalTech hosts ASP.NET in a medium trust environment, so the library also works for shared hosts. Some contortions were necessary, and fully general object serialization is not yet available (for instance, serializing delegates will fail).

By default, the library assumes all continuation objects can be migrated to clients. This encourages more scalable program structures. If some object needs to remain server-side, simply implement the ILocal interface. There are no operations, but the interface marks the class as non-mobile. The default behaviour in this case is to generate a random 64-bit token, and migrate this token instead. When the token migrates back to the server, it re-connects to the original object. If the server restarts, this state is lost, but a state server as found in ASP.NET can be built which will allow the state to survive restarts and be shared between machines.

Schema upgrade can still pose a problem unfortunately, and unlike with server-side state where the continuations are stored centrally, you can't use a tool to upgrade them. Altering method implementations does not pose an upgrade problem. Adding and removing fields is problematic however.

Fortunately, applications using the library are already structured for easy upgrade and permit a configurable policy for deprecation. Basically, don't touch existing classes, and only create new classes. Replace the use of old classes in the program with the new classes, then whenever you judge it appropriate, remove the old class entirely. On any serialization errors, the library will invoke an application-specific handler which returns a continuation. I think any conceivable upgrade policy is feasible given these primitives.

The current source for the library is available here. I plan to improve the mechanism for displaying continuations in a medium-independent fashion. Ideally, I'd like to be able to create a binding for Windows.Forms, and for JSON requests, so that the same continuation-structured application can be reused unmodified in different environments.

No comments: