Web State Machines

[ Comments ] [ Copyright ] [ Main contents ]

As I noted in my last article on building large CGI-mediated applications, maintaining state information is a real problem for the web programmer. If you want to make your site available to everyone on the web, you can't afford to make assumptions about their browser, or rely on proprietary technologies; by definition, the web is cross-platform, and failing to realise this will lead to problems.

For example, see A major UK retailer. Their web site relies on ActiveX and VBScript; if you don't have 'em, you can't use the site. I wanted to buy a £500 PDA, but because I don't have any browsers capable of running ActiveX/VBScript applications (I'm a Microsoft-free zone) my money went elsewhere.

Obviously their web production team thought it was worthwhile to stick to Microsoft products, and to a point they were right -- it probably made their development cycle easier. But it also lost them at least one sale, and the lesson to draw from this is: don't make assumptions about your reader's technology. Assuming they've got anything beyond HTML 2.0 and forms is a mistake. (Of course, if their computer doesn't have a forms- capable web browser you're really stuck: there's no way of effectively letting them feed you information, so you might as well give up on the idea of writing interactive web applications. But that's another matter.)

Shopping systems are one example of a situation where supporting the most generic level of browser is a Good Thing; a failed connection is a lost sale. But how can you write a web application that maintains detailed state information, without relying on cookies, JavaScript, VBScript, ActiveX, or similar proprietary features?

I've lately had to implement a complex CGI interface that had to track a lot of user information -- in fact, sixteen screens-worth. Users had to be able to go back and edit earlier screens, jump around the set, and do all sorts of weird things (ever seen a CGI application with context- sensitive online help?). This forced me to confront the problem of building a state-tracking CGI application without making any browser-specific assumptions.

Defining the problem

Firstly, I had to define the problem.

The problem was how to track data entered in several HTML forms, in such a way that it would be accessible (but not visible) in other forms, and in a manner that would allow intuitive user navigation among the forms. For example: you fill form (a) out, then hit the NEXT button to go to form (b). While filling form (b) out you realise you made a mistake in (a) and need to go back. You use the application's BACK button, and correct form (a), then hit the NEXT button again to go to form (b) -- and the information you had begun to enter in the form should still be there, waiting for you.

This data can therefore be stored in two places:

I decided at the outset not to use a server-side database to keep track of user state. The application I had to write needed to throw enough information back and forth that each user could generate up to 20 database transactions in the course of five minutes. It would therefore impose a fair load on the server if it had to support a SQL database as well as a thumping great CGI system.

In addition, by keeping all the user state information in the client, I made it scaleable; the application can be replicated on a couple of hosts, and I can bounce the user from a script on host #1 to a script on host #2 without them losing any state information (and without needing a distributed RDBMS). This wasn't essential, but it was a nice extra -- a cheap array of distributed linux workstations cost a lot less to set up than a multi-processor SPARC server and, using this system, can support a similar load.

Given that the goal was to devise an efficient state information storage mechanism, it seemed obvious that hidden fields offered the best place to store state information that wasn't to be displayed in a form. However, the question was how to ensure that they were passed from state to state?

Storing information persistently

I like using the module by Lincoln Stein. It provides an efficient object-oriented way of building CGI scripts. In order to add a state information storage system, I wrote a subclass of, called CGI::State. The CGI::State module inherits all the attributes of CGI objects, and adds a new one: the concept of a 'store'. A store is a named variable that is stored in a CGI::State object. You can create new stores by name, retreive their contents, and put stuff into them. (When you initialize a store you need to indicate the root data type it holds -- scalar, array, or hash -- but you're free to put more complex things in them; for example, an array store can hold an array of references to objects, all of which will be stored in the CGI::State object when you emit it.)

In use, the only difference between and CGI::State is that where in CGI you would end a form by saying:

print $cgi->end_form;

In CGI::State you would say:

print $cgi->commit;

Which first 'freezes' the data stored in the CGI::State object (using the FreezeThaw data stringification module), then writes them out in hidden variables, and finally calls CGI::end_form.

Here's the man page for CGI::State:

Package name: CGI::State

Purpose: provide an OO mechanism for storing perl data structures inside a CGI object, passing them from one invocation to the next by burying them in hidden fields. Makes it easy to pass hashes, arrays, and more complex data structures (anything amenable to being squished down by FreezeThaw).


*  Uses FreezeThaw
*  Also uses Data::Dumper (if debugging is switched on)
*  Inherits everything from
*  Adds:
   -  init_store(storename, data_type)
   -  put_store(storename, entity)
   -  fetch_store(storename)
   -  del_store(storename)
   -  commit()
*  Overloads:
   - new()

A CGI::State object is a CGI object by any other name. The main difference is that it has one or more associated invisible ``stores''. A store is identified by name, and can be treated as a hash. init_store() creates a new named store attached to the current object. put_store() puts the contents of a hashref into a store. fetch_store() returns a hashref containing the key:value items in the store. del_store() deletes a named store. new() automagically rebuilds any stores which were passed from an HTML form, and commit() pumps 'em back out into the current form before ending it.

Internally, a store is a frozen string stored in %{ $self->{.stores} }, where the key value is the store's name.

Because it uses FreezeThaw to handle stringified storage, it's possible to freeze complex data structures (but not globs or coderefs). At present, you need to explciitly state whether a store is going to contain an ARRAY, HASH, SCALAR or REF when you create it with init_store(). Don't even THINK about trying to use GLOB or CODE ...

The main point to note is that a store doesn't become persistent between invocations of the CGI script unless the form is ended correctly, by calling commit() before endform().

To prevent collisions with other named parameters in the CGI field namespace, CGI::State prefixes its saved objects with whatever is stored in $CGI::State::prefix (currently XXpersistent, but you can override this if necessary).

For example:

  my ($q) = new CGI::State;
  print $q->startform();
  # usual stuff goes here ...
  my ($result) = $q->init_store("A");    # create a store called "A"
  $q->put_store("A", { qw( color blue 
                           taste sweet number 6) }); # stash data in "A"
  my ($handle) = $q->fetch_store("A");
  # $handle is a reference to a hash: {"color" => "blue", 
  #                                    "taste" => "sweet",
  #                                    "number" => "6"}
  $handle->{"quality"} = "poor"; # modify the contents of the hash
  $q->put_store("A", $handle);   # update the persistent store                                   
  $q->commit();   # export persistent data
  $q->endform();   # finish writing form

Using stored state information effectively

This is the hard part.

To make use of stored state information, I wrote a CGI script that behaves as a finite state automaton.

Most interactive applications exist in a series of states. They respond to user input by changing their state; the face they display depends on the state they're in. How can you do this with a CGI script, which by definition is state-free (given that the HTTP protocol it relies on is stateless)?

The answer is to freeze the state information into the HTML forms, and ensure that they're generated by the script. When you click on a navigation link in one of the forms it provides, it sends a package of data back to the script. The script wakes up, unpacks the state information hidden in the form, works out what it's meant to do in this state (including switching to another state), then prints a new form (carefully freezing its internal state information into it before it exits).

Obviously, each state has different actions associated with it. So I designed my state automaton accordingly. When first invoked, by the default HTTP method (GET), the script looks for and reads in a configuration file. The configuration file gives it a list of states, including a start state, a finish state, and a sequence of states to follow. It also supplies two filenames for each state -- an HTML file, and a file containing perl commands.

Once it's read in the configuration file, the script looks for the perl command file associated with the start state; if it exists, it executes the commands in the file (by eval()). These commands probably cause it to undergo a state transition -- subroutines in the script allow for this, and are accessible from the perl 'stub' corresponding to each state. Then it looks for the HTML file associated with its new state. Rather than printing this file verbatim, it performs macro substitution on it (using a simple macro language, described below). Among other things, the macros %startform% and %endform% trigger actions in the script that cause it to freeze its internal state (using CGI::State) and save it in the output stream.

The next time the script runs, receiving a wadge of data via method POST, it already has its state table loaded, and knows exactly which perl script to eval and which HTML file corresponds to its new state.

Operational considerations

Obviously, a CGI script this big runs like a snail. To speed things up, I implemented it as a CGI::Apache script.

Apache is the leading web server of choice on the internet at large, with about 40% of all commercial sites running it. Apache is modular in structure; one of the modules mod_perl lets you embed a perl interpreter inside Apache. Using the associated CGI::Apache module, which attempts to emulate the environment provided by, you can write Perl scripts which look like CGI scripts but actually remain resident in the Apache http daemon after the first time they are invoked. Such scripts are executed in a loop by the server and only end when the server is reaped. A discussion of mod_perl is outside the scope of this essay, but suffice to say I use it extensively.

A demonstration system

A demo system based on the state.cgi application runs on this server. The server itself is only a 486/66 with 20Mb of RAM, running Linux; as such it would normally be far too slow to support such a heavy CGI system.

Press me!

Source code

state.cgi source DEFAULT.CFG source
State 1 html State 1 perl
State 2 html State 2 perl
State 3 html State 3 perl

The manual

[ Comments ] [ Copyright ] [ Main contents ]