Sound advice - blog

Tales from the homeworld

My current feeds

Wed, 2005-Sep-21

State Tradeoffs

HTTP is stateless between requests, each of which involves stateful TCP/IP connections. Any subscription protocol requires state to be retained in the network for the lifetime of the subscription to keep track of who the subscribers are and what they want. Whenever I POST to a web server I can be pretty confident that I'm creating some kind of state, although how long-lived the state is or whether the state has associated costs in terms of memory utilisation or other resources is unkown to me. REST sides with HTTP and says we should be stateless beween requests, but is that always possible and what are the tradeoffs?

Mark Barker points to Fielding's disseration. Under the Related Work heading alongside the discussion of preexisting architectural styles he said this:

The interaction method of sending representations of resources to consuming components has some parallels with event-based integration (EBI) styles. The key difference is that EBI styles are push-based. The component containing the state (equivalent to an origin server in REST) issues an event whenever the state changes, whether or not any component is actually interested in or listening for such an event. In the REST style, consuming components usually pull representations. Although this is less efficient when viewed as a single client wishing to monitor a single resource, the scale of the Web makes an unregulated push model infeasible.

He discusses Chiron-2 as an example EBI style.

This opinion is interesting to me because I can perhaps see for the first time the difference between "corporate" and "internet" scales of software. If Fielding is to be believed, that difference is captured in exactly how much state a server can afford to maintain on behalf of its clients. In computer science courses students are taught that polling on the network is and obvious evil. It increases response latency, increases network bandwidth, or both. When thinking of the cost of network in terms of only the bandwidth and latency characteristics of the network the urge to use a publish subscribe scheme rather than polling is strong. Fielding gives us a different way to think about the problem.

I come from the SCADA world. Typically, a stable set of client and server applications are running on a secure or relatively-isolated network. Extreme load conditions usually come about when equipment being monitored changes state frequently and servers must process and pass on data under what is termed an avalanche condition. Varying quality constraints apply to different kinds of client in this scenareo. Historical storage of change records seeks to store as many interim states as possible without lagging too far behind the change records of right now. User-oriented services typically seek to have the very freshest data available at all times. Low latency and effective use of bandwidth are critical to making this work, as is the processing performance of actual clients.

Extreme load conditions on the web usually come about from client activity, and is termed in today's internet, the slashdot effect. Instead of thousands of changes being processed and passed on to clients, thousands of clients are either "just having a look" or actively participating in your web site mechanics. It's not just Fielding who things that state is a barrier to high performance under these condtions. Paul Vixie wrote the following earlier this year on

tcp requires state. state quotas are a vulnerability in the face of a DoS attack. tcp must remain a fallback for queries, and be reserved in the common case for updates and zone transfers. doesn't matter who runs the servers, if they're supposed to stay "up" then you can't depend on them to have room for another tcp protocol control block in the common case.

The sentiment is periodically echoed through the mailing list's lifetime. Paul is also the author of this earlier quote:

speaking for f-root, if we had to build a protocol control block for each of the 5000 to 10000 queries that came in every second, and exchange packets between our state machine and remote state machine, before finally sending the response and reclaiming the state-memory, we'd need a lot more hardware than we have today. it's not the bytes, or the packets-- those we can provision easily. it's the state-memory occupancy time that would dominate.

So in the extreme world of DNS, even the state associated with a TCP/IP connection is considered too much. In Fielding's view of the web anything more than TCP is too much. Scaled back down to a corporate setting and state is no longer the problem. Bandwidth and latency dominate. Clearly there is a sliding scale and there are tradeoffs to be made. Where do the tradeoffs lie?

When we're talking about real-time scada-like data clients have a cost if they aren't kept up to date. This applies to any time-sensitive data ranging from stock market quotes to eBay auction prices. To reduce the cost of getting information late clients must poll the service, incurring bandwidth and node procesing costs. Memory resources aren't used past those required to carry on TCP/IP comms between relevant network nodes, so a large quantity of requests can be handled with the main costs being processing and bandwidth. Those can be limited explicitly by the server, so it should be possible for the server to ride out the storm while clients see longer and longer response times during peak demand. The cost of bandwidth and processing can be traded off for extra memory resources by offering a publish/subscribe state synchronisation model to clients. This provides low-latency return of data to clients without polling and may reduce both processing and bandwidth costs. It still allows those costs to be managed by the server infrastructure, which may choose to drop intermim state updates or perform other load shedding activities. It does cost extra memory, though. Unlike bandwidth and processing, memory isn't a renewable resource. If you expend it all your server can't recovery by slowing the rate of requests or responses. Your server is likely to simply fall over.

State is sometimes necessary. If I book a flight online the flight booking state must be retained somewhere, or my booking won't be honoured. In cases like these I pay money to store the state so the accounting infrastructure exists to fund memory expansion. Even if the cost is amortized against actual successful bookings, the fact that the site is doing business mitigates the raw "interesting site" effect where thousands or users may decide to store small amounts of state on your server if they are allowed to. Importantly, this example also has an approximate limit to the amount of state stored. The number of planes in the sky at any one time controls the number of seats available. Even if a proportion of the bookings will have to be cancelled and remade and the state of those changes recorded that proportion should be roughly predictable on the large scale as a percentage of actual seats booked or available.

Other examples include WikipediA and Both are open to the slashdot effect of having a large number of clients. As well as doing stateless queries, these services allow users to store encylopedia articles or bookmarks on the sites. They must have storage capacity in proportion to the size of their user base, based on the average number of bytes a user contributes. Wikipedia has a small advantage over other sites in that once an article is written and authorative it seems likely that a proportion of the user base is cut out of contributing to that topic because everything they know about it has already been written down. I suspect delicious doesn't get this effect. In fact, my experience is that bookmarks found via delicious are often inserted back into delicious by the discoverer. This suggests to me that the storage requirements for delicious are in rough proportion to the user base but with a risk that it will eventually grow in rough proportion with the size of the web itself. Is such a service sustainable? Will its funding model allow for this possibly infinite growth in resource consumption requirements?

To answer that question, let's take a look at a bigger example. Google certainly seems to have been able to make a go of it so far. Their storage requirements follow the same curve but with a much larger constant. Instead of storing a bunch of URLs and the people who like them, google is effectively a full-text index of the internet. Other projects of that scale exist also, within and without the search engine manifold. The key seems to be ensuring your funding model grows along the same curve (or a steeper one if you can manage it). If you have storage needs in proportion to the size of an internet user base then you probably need to get funding proportional to that size. This is important in paying for bandwidth also. You need to get paid in proportion to how popular you are or you aren't going anywhere on the Internet. It seems that for the moment delicious is working from a venture capital pool, but at some point it will have to start returning money to its investors at a greater rate than the cost of scaling up the servers to handle load.

I don't know whether subscription is a viable concept on the web when the number of users is effectively unbounded. Servers can still reject subscriptions or refuse to renew them so a bounded number can be maintained... but you'll be giving a proportion of your user base error messages and that is never a good look. In the end it probably comes down to a matter of economics. Are you being paid in proportion to the number of subscriptions you provide? Is there an advertising stream alongside the subscription? Are users paying for the subscription itself, perhaps as a premium service? If you can get that side of things off the ground and are ready to scale your servers as your userbase grows and spikes (or in anticipation of the spike) then you can probably make a go of subscription. Otherwise you might be better off letting your server be polled and see your web site respond more slowly to users in moderate overload conditions rather than just cutting them out. In the end the big overload conditions will still cause errors to be returned, so it is really a matter of how much you can afford to spend and what it will cost you if clients don't see your offering as reliable.


Sun, 2005-Sep-18

The RESS[sic] architectural style

I've just read an email from Savas Parastatidis on the RESTfulness or not of AJAX. Savas perhaps has an agenda in his writing that REST is not sufficient to do what industry really wants to do with the internet. Together with Jim Webber he's been working on MEST (formerly ProcessMessage). MEST is an attempt to use REST ideas to give SOA and SOAP generally more life and longer legs.

A lot has been invested by various companies into SOAP infrstracture, so it is reasonble that those who have been backing that horse continue to try and make it work. History is full of differing technical solutions ultimately merging rather than supplanting each other entirely. It makes sense to think that what might come out of the current mix of web service styles is something that is neither REST nor SOAP, and MEST is an attempt to be that something.

Overall, I'm unconvinced by SOAP. My comment via return email was as follows:

In the end the constraints of REST are that everyone understands your messages/media-type/whatever. If that constraint proves to be accurate on the internet then it won't be possible to reach all users of the internet without a general-purpose and non-specific message set. This tension between explaining specifics sufficient for the client to be able to reason about message content and describing things generically enough that all clients can render or otherwise process the message is a difficult one to resolve. The more specific you get the better your target audience understands you, and the smaller your target audience can possibly be.

I think that trying to nail down schema issues and deal with very specific message types is an impossible mission on the internet where you don't control and distribute the client software your users have installed. Ultimately I think that on the internet scale you need to give your client a document of standard media type to work with. If that document explains how to fill out the very complex and specific form you need submitted back to you, then that's great. Just don't expect client software to understand how to do it unless you provide those necessary hints. Don't expect client software to be written to your API. Write AJAX, or XForms to make that happen.

Thinking about different architectural styles further, I made this comment:

Personally, when I think of software architecture the most important issues that come to mind are that of client and server. The client wants something done, and the server is capable of doing it. The client is responsible for acting or retrying or whatever is necessary until the server acknowledges completion of the activity or moves into a state consistent with compeltion of the activity. To me distributed software achitecture is primarily about synchronisation of that state, which comes back somewhat to pub/sub. You request something be done. You get an ack indicating that your request has been accepted, and you monitor some state on the server side until it changes to what you want it to be. This view of architecture is the reason I keep thinking about and worrying about the lack of a pub/sub system that I'm confident works on the internet.

I hereby declare the existence of another architectural style. I don't have a good name for it yet. RESS - REpresentational State Synchronisation or just SYNC, maybe. It is designed to support complex requests but not encourage complex message interactions. It is designed to put power into the hands of clients to determine when and under what conditions their request can be said to be complete. The constraints of this style are as follows:

  1. State and is synchronised from server resources to client according to standard interaction patterns
  2. Requests and synchronised state use standard media types
  3. Requests made from client to server resources are constructable from data available to the client

The following axis are not constrained:

  1. Agents may be included to act on behalf of a client. The client may monitor the agent or the origin server to assess completion of the request and compare the result against success criteria.
  2. Caches can (and should) be part of the synchronisation pattern
  3. I'm not yet prepared to constrain client to using standard methods. I think that the method used and the media type should be decided by the server, typically by providing an XForm to the client that indicates how to build the request the client wants.

It is currently pretty-much REST. I've weakened the constraint of using standard methods because I'm not convinced that the POST-abuse path is any better... but maybe I can be talked around on the practicalities of this point. The main difference is a focus on state synchronisation rather than just state transfer. I believe that clients need reliable subscription capabilities in order to assess whether their goals have been achieved without polling. This is an asynchronous view of interaction and I see the synchronisation model as a secure underpinning of all possible designs that require asynchronous functioning. Focusing on subscription of resource state rather than building a generic delayed response approach allows caches to get in there and give clients quick answers to what the server's state was just moments ago. This should provide the architectural benefits that REST purports to have without polling (assuming your synchronisation mechanism is not polling-based). When other operations are performed on the resource in question caches along the way should recheck the resource state before passing it on to clients as the current state.

I think the refocus on what clients really want to do with state most of the time (subscribe to it, rather than transfer it) is useful, and allows us to rethink the existing caching mechanism of the internet rather than holding it up at the reason we do things the way we do in REST. I think there is a lot more joy to be had with a "real" synchronisation mechanism for those corners of real application funcationality that don't change at reliable rates and those requests that aren't synchronous.


Sat, 2005-Sep-10

HTTP Subscription without SUBSCRIBE

I've been very serouslying considering dropping the only new http verb I've introduced for HttpSubscription: SUBSCRIBE.

I'm coming around to the idea of saying this is simply a GET. I've heard opinions that it should be essentially a GET to a "subscribable" version of a resource. I haven't quite swung that far around. In particular, I think that separating the subscribable and the gettable version of the resource is going to make things harder on clients. In fact, I think it doesn't make a lot of sense from the server side either. If this is a resource that is likely to change while the user is looking it it, it should offer either subscribe support or a refresh header indicating how often to poll the resource. To offer subscribe but only a single-shot GET doesn't really make sense. Therefore, insted of using a special SUBSCRIBE request I'm thinking along the lines of content negotiation on a GET request. SUBSCRIBE made sense when I thought we would be "creating" a subscription. In that world SUBSCRIBE was a good alternative to POST. Now it's looking like an alternative to GET, I think that is less appropriate.

As I mentioned in my previous entry, bugzilla uses mozilla's experimental multipart/x-mixed-replace mime type to put up a "wait" page before displaying the results of a large query. Mozilla browsers see this document, render it, then render the result section of the multipart replace so the user sees that results page they are after. Bugzilla doesn't use this technique for browsers that don't support it. How does bugzilla know? It looks at the user-agent header!

I think this is clearly unacceptable as a general model. New clients can be written, and unless they identify themselves as mozilla or get the bugzilla authors to add them to the "in" list bugzilla won't make effective use of their capability. I see this as a content negotiation issue, so it seems reasonable to start looking at the Accept header. It is interesting to note that mozilla doesn't explicitly include multipart/x-mixed-replace in its accept header. Instead, it contains something like this:

Accept: text/xml, application/xml, application/xhtml+xml, text/html;q=0.9, 
        text/plain;q=0.8, image/png,*/*;q=0.5

Only the '*/*' permits the return of x-mixed-replace at all. There may even be some doubt about exactly how to apply the accept header to multipart mime of data. If I accept a multipart mime does that mean I don't have any control over content below that level? The rfc is strangely quiet on the issue. I suspect it has just never come up.

In practice, I think a reasonable interpretation of accept for multipart content types is that if the accept contains that type and also other types then the accept continues to apply recursively down the multipart tree. If you say you accept both multipart/x-mixed-replace and text/html, then chances are the document will come back as plain text/html or text/html wrapped up in multipart/x-mixed-replace. An application/xml version of the same is probably not acceptable. Also in practice, I think it is necessary at the current time to treat mozilla browsers as if they included multipart/x-mixed-replace in their accept headers.


Sat, 2005-Sep-10

More HTTP Subscription

I've been actively tinkering away at the RestWiki HttpSubscription pages since my blog entry last and have started to knock some of the rough edges off my early specifications. I've begun coding up prototype implementations for the basic subscription concepts also, and have written up a little experience from that activity. I still have to resolve the issue of subscribing to multiple resources efficiently, and am currently proposing the idea of an aggregate resource to do that for me.

I'm hoping that what I'm proposing will eventually be RESTful, that is to say that at least parts of what I'm writing up will hit standardisation one day or become common enough that de jour standardisation occurs. I've been hitting more writeups of what people have done in the past in these areas and have added them to the wiki also.

There are various names for the basic technique I'm using, which is to return an indefinite or long-lived HTTP response to a client. There's server push, dynamic documents, pushlets, or simply pubsub. The mozilla family of browsers actually implements some of what I'm doing, at least for simple subscription. If you return a HTTP response with content-type multipart/x-mixed-replace, then each mime part will replace the previous one as it is received. This is a very basic form of subscription, and could be used for any kind of subscription really. That's the technique used by bugzilla to display a "wait" page to mozilla clients before returning the results of a long query. The key problems are these:

At the moment it seems we need to savagely hit the cache-control headers in order to prompt proxies to stream rather than buffer our responses to requests. If caches did understand what was going on, though, they could offer the subscription on behalf of the origin server rather than acting as a glorified router. A proxy could offer a subscription to a cached data representation, and separately update that representation using subscription techniques. This would give us the kind of multicasting for subscriptions as we currently get for everyday web documents.

Scaling up remains a problem. Using this technique, one subscription equals one TCP/IP connection. When that drops the subscription is ended, and if you need more than one subscription you need more than one connection. If you need a thousand subscriptions you need a thousand connections. It isn't hard to see how this might break some architectures.

My proposal to create aggregate resources is still a thorny one for me. I'm sure it would help in these architectures but there are issues to consider about what wrapping many http responses into a single response means. If aggregates can effectively be created, though, you could get back your one connection per client model for communications.

I'm eager to get more feedback on this topic, especially if you are developing software for my specification or are using similar techniques yourself. I have a vauge notion that in the longer term it will be possible for a client to be written to a HTTP protocol that explicitly permits subscription and prepares clients for the data stream they will get back. As I said earlier there are implementations already out there, but the data on the wire is in a myriad of forms and I see the lack of consistency as an opportunity to get it right.


Sun, 2005-Sep-04

HTTP Subscription v3

This is my third time around the mulberry bush with HTTP subscription, and I've been lucky to have had contact with a few people on the subject now. I've even seen working code, and an internet-scale demonstration. Unfortunately I'm unable to link the the demo at the request of its author who doesn't want a drowned server :)

In accordance with what has been developing, I have transferred some of my current thinking to the RestWiki. This site appears to be a little neglected so I've be starting to nibble around the edges to try and improve things. If I don't meet any resistance soon I may start really getting into the content and pushing my own view of REST and its variants.

I've updated the FAQ and intend to do some more pruning and updating after giving anyone who is actually still working on the site time to reject my input. I've also commented on an existing HTTP Subscription Specification, and most exciting of all I've collated my current thinking on HTTP subscription into a canonical resource that I intend to keep updating.

This URL will be the base of operations for any further updates and should avoid the fragmentary approach that developing specification via blogging tends to encourage. I have split the specification in a main introductary page, A page on the necessary and desirable features of a HTTP subscription protcol, and a page for the specifcation itself.

I have allowed room at the bottom of the requirements and specification pages for general comments.