Submission Throttling - Ajax Patterns

Submission Throttling

From Ajax Patterns

Evidence: 3/3

Tags: Queue Throttle Buffer Performance


Contents

In A Blink

TODO Diagram

1s User types "A", Buffer is "A" 2s User types "B", Buffer is "AB" 3s User types "C", Buffer is "ABC"

4s Buffer transferred to server 5s Server processes "A" then "B" then "C" 6s Server sends response


Goal Story

Tracy is holding an online meeting on an Ajaxian chat program. The others can read as she types, because every few seconds, the in-progress message is uploaded to the server.


Problem

How can information be submitted to the server?


Forces

  • Information is often uploaded in bursts, for example:
    • A chat application incurs many hits when a user is writing messages quickly.
    • A trading system incurs many hits after an announcement is made.
    • A Live Form incurs many hits after the user responds to some new information that's been presented.
  • It's difficult for the server to cope with lots of messages at once.
  • Each message has overheads such as packet headers and requires some processing at each stage of the browser-server round-trip.


Solution

Instead of submitting upon each Javascript event, retain data in a browser-based buffer and automatically upload it at fixed intervals. As with many applications of buffering and throttling, the purpose is to strike a balance between responsiveness and resources. In most cases, it would be ideal to respond to every keystroke and mouse movement - so for example, like a desktop application, tooltips could come directly from the server as the user mouses around. But that's not practical due to bandwidth considerations, and possibly server constraints too. So to ease bandwidth - and to lessen server I/O, call detail is accumulated and periodically uploaded.

Exactly what the buffer holds is application-specific, but there are two general styles: data buffers and command queues.

In the first buffer style, the buffer holds some data to be uploaded. Consider implementing a Suggestion interface like Google Suggest, which keeps showing information based on what's been typed. The simplest thing would be to add an "onchange" listener to the text field, and upload the buffer when each change occurs. However, what if you get a fast typist, one of those folks who revels in their "words per minute" metric? Banging out 100 words per minute means perhaps 10 characters per second, or a call every 100 milliseconds - feasible on a localhost web server, maybe workable on an intranet, but not scaleable for most public internet applications. So Suggestion systems, and more generally Live Command-Lines, run a fixed-period timer. Every 500 milliseconds, say, the browser checks if there was a change since the last call, and if so, uploads to get some information, and remembers what was uploaded to avoid doing so again. Effectively, the result for the current text field is cached, and the cache can only change on fixed periods.

A similar pattern might be used on a Live Form, where the entire form is periodically uploaded to the server, even though some fields are blank, along with an indication of the user's progress. The server can then use some intelligence to crtique the form data, so as to provide live feedback.

The other style of buffer is a command queue, a concept which will already be familiar to many real-time and enterprise system developers. Here, each user request is encapsulated as an instance of some kind, typically an object of type Command in object-oriented languages. "Design Patterns" (Gamma et al.) deals with the Command pattern in more detail. It's possible to build up a command queue, where commands are dealt with on a first-come, first-served, basis, and this is the idea behind this style of buffer. The user's calls are added to a queue inside the browser, the entire queue is perioidcally sent to the server for processing, and a new, empty, queue created to capture further browser-side commands.

In Javascript, it's feasible to use an object to represent each command, and an array to hold the queue sequence. In pushing this data to the server, each command must be serialisable, and it would make sense to place a serialise method for each command object, or ensure toString() provides sufficient detail for the server-side to reconstruct the object. Then, the calls can be sent to the server as a sequence of variables, e.g. 'command1=forward,10&command2=rotate,90&command3=back,30'.

Are the calls read-only, or do they change server state? Actually, both options are feasible. Calls for read-only data might be referred to as Query objects rather than Commands. In the Live Form example above, it was suggested that the entire form be uploaded periodically. That's a model which assumes ample bandwidth and, moreover, some smart server capabilities. If we wished to endow the browser with more responsibility, we could have the browser accumulate a queue of Queries, one for each field, and let the server routinely provide feedback on each of these.

So far, the pattern has been discussed as a straightforward trade-off between technical resources and usability. Ajax as a whole aims to improve usability, often at the expense of resources, Submission Throttling appears to address the balance somewhat by increasing resources at the expense of usability. Less resources are used because less calls are made, while usability potentially suffers because some commands are held a long time in the browser before even being sent for processing.

If we look more closely, we'll find that Submission Throttling can be a boon for users too. There's a reason why the Windows and Apple Operating Systems don't show copious logging details when booting. Technical users may appreciate the comprehensive output of a Linux boot sequence, but most users consider it infromation overload - much more information than they actually care about. With the right algorithms in place, throttling can be used to update information at more judicious times.

Even better, throttling can help reduce spurious error messages. You've probably used MS-Word's excellent spell-checking feature, which underlines incorrect words on the document. (And modern IDEs do the same thing with compilation errors.) Fortunately, MS-Word waits until you've finished the word before highlighting any error (at least under my current settings). But similar systems warn about the error while you're still typing. In most cases, this is as frustrating and obnoxious as the frustrating and obnoxious actor in the following conversation:

  • Speaker: I'd ...
  • Obnoxious Critic: "I'd" what? You haven't finished that sentence!
  • Speaker: ...like ...
  • Obnoxious Critic: Hello??? Error. 404. You'd like what?
  • Speaker: ...toTalkToSomeoneElseNow.

If the only way to avoid an error message is to rush to the finish line, that's a problem. Error messages are good when appropriate, but too many of them leave users frustrated. They also lead to the "crying wolf" syndrome, where they become so undervalued that all error messages are routinely ignored.

There are many caveats to this pattern. It's vulnerable to integrity issues, because synchronisation is being deliberately downgraded. The universe will have moved on since the user submitted these commands - the time will be different, new information may be available, existing information may have changed or been deleted, and other users may have executed commands in the meantime.

However, none of those reasons is enough to rule out the pattern. In fact, the entire asynchronous paradigm at the heart of Ajax is subject to much of this criticism. All this just means we have to take care and consider whether our designs might lead to any disaster scenarios.


Decisions

How will the server deal with incoming commands? Will all commands still valid?

You have to decide whether to process all the incoming commands as it's quite possible some should no longer be processed by the time they reach the server. For instance, purchase orders usually contain a corresponding price field, or perhaps an upper limit. If the price has increased since the order was made, the buyer won't be amused to discover the deal was nonetheless processed and charged at a higher rate. On the other hand, if the price has dropped, that's great for the buyer, but the server owner may be entitled to invalidate the deal. A similar scenario might occur if the order had an expiry time, e.g. within 5 seconds of being uploaded.

Thus, timeliness and data state can render earlier commands invalid. These situations can occur in any web system, Ajaxian or not, but the deliberate delay imposed by throttling increases their likelihood. In some cases, the system must strike off any invalid commands, and it's important to communicate this information to the user. This doesn't mean distracting the user every time an action occurs, informing them it's not yet been acknowledged. In most cases, it's more useful to act as if each command has been processed correctly, and only notify the user after a problem has occurred, e.g. a timeout calling the server.

When an invalid command is struck off, what do you do with the other commands that were submitted? In many cases, they too need to be scrapped, because the user may have intended the commands to occur as a whole, atomic, transaction. For instance, a retail system may require a product order followed by a payment. If it turns out the product cannot be dispatched due to an inventory shortage, the corresponding payment must also be cancelled. In other cases, it might make sense to allow as many commands to go through until one fails, and stop there. That might be the case in a web content manager - capture as many blocks of cointents as the user entered, until (say) some spurious data is encountered. The remaining commands may not make much sense if the middle block must be altered.

Or it can sometimes make sense to process commands as a stack, i.e. deal with the most recent commands first. This would be the case if previous commands overwrote the effects of earlier commands. So if the user says "Reserve storage unit 32 for Bob", then later says "Reserve storage unit 32 for Sue", the system will simply reserve the unit for Sue and invalidate the original query.

How will buffer uploads be triggered?

The most obvious algorithm for upload sequencing is a timer. Every minute (say), the browser polls the buffer and makes the corresponding call sequence. Or, if nothing has changed, it might do nothing for another minute. If a timer is used, a decision must be made as to when it will trigger. First, the period is usually fixed, but does not have to be. It might be increased during times of known server activity, or even altered to respond to those constraints dynamically. Furthermore, it might be based on the user in question: service level can be tweaked by giving premium users shorter throttle periods.

A more sophisticated variant is to immediately send the first command after a long wait, then begin building up the buffer again. This helps a user who only changes information occasionally. For instance, let's say the throttle period is 30 seconds. With a standard, fixed-interval, algorithm, the following sequence occurs:

  • 00 secs: System polls, no activity so no upload.
  • 30 secs: System polls, no activity so no upload.
  • 60 secs: System polls, no activity so no upload.
  • 61 secs: Infrequent user does something
  • 90 secs: System polls and uploads to server.

In contrast, the send-on-initial-activity variant works as follows:

  • 00 secs: System polls, no activity so no upload.
  • 30 secs: System polls, no activity so no upload.
  • 60 secs: System polls, no activity so no upload.
  • 61 secs: Infrequent user does something.
  • 61 secs: System immediately calls, and timer is reset.
  • 75 secs: Infrequent user does something. This time, it must wait since there was a recent call.
  • 91 secs: System polls, uploads if there was any further activity after 61 secs.

Prioritisation is another technique. A timer might be used for regular events, but priority given to any critical commands. A Live Form might periodically upload the progress of an individual field, so the server can provide suggestions for example. But as soon as the user proceeds to the next field, a call takes place immediately. It's conceivable that each command could even be allocated an importance score, so that the buffer is sent as soon the tally reaches as a threshold level, instead of waiting for the timer.

A further consideration is the user's activity during upload. It's often wise to avoid uploading something the user is currently working on, especially if other users will see it and especially if they probably won't be working on it much longer. So, one policy might involve uploading only after a period of idle activity.

Where the user is isolated from external events, it might seem reasonable to use a fixed-size buffer, and upload only when it's full. However, if the buffer includes Commands intended to change server state, the last lot of changes may be lost if the user logs out before the last buffer is full. There is a risk of data loss with a timer too, if the user immediately quits the browser after performing some commands. However, it's much more likely that the user will keep the browser open, but not submit any more information. Either way, Synchronisation Status should be shown to reduce this risk.

How many buffers per browser application?

There's no reason to have just one buffer for all commands. It's possible to have several buffers running parallel, providing you have considered the consequences of commands arriving in a different order to the user requesting them. Prioritisation was already mentioned above, and this would be one reason to have several buffers - higher-priority buffers being processed with greater frequency.

Here's how an image-processing website might use three buffers:

  • Low priority image upload queue - Each image added by the user is added to

a low-priority queue and soon persisted server-side. Throttle Period: 15 seconds.

  • Low priority image query queue - When a new image is required, the browser adds the image object to the DOM locally along with explanatory text (in the form of ALT/TITLE tags). The URL of the image is then added to the queue actual images and eventually the image appears on the page.

Throttle Period: 3 seconds.

  • High priority text buffer - For certain text fields, a Live Command-Line is used. While it's not necessary to upload upon each keystroke, any new information must be transferred rapidly in order to feel truly intereactive.

Throttle Period: 0.25 seconds.

This example illustrates that it's quite easy to run several buffers without threat to data integrity and without user confusion. It's made possible by designing according to an asynchronous mindset, as discussed in Fat Client.

How long should the throttle period be?

Deciding on the throttle period requires some analysis of user needs. As the image-processing example above demonstrates, there is a range of of periods that might be required:

  • For background synchronisation, the period can be a few minutes if resource constraints apply, although should ideally be in the order of 10 seconds. If it is several minutes, users must be aware of this process with appropriate Synchronisation Status, lest they quit and lost work before the upload kicks in. Furthermore, there should be a "Save Now" - or perhaps "Quit" - button that will process pending data immediately.
  • At the other end of the spectrum, for low-level interaction while the user types and mouse around, the period must be in the order of 100 milliseconds.

How to protect against "impatient" clients?

Submission throttling is subject to abuse from impatient users who are inclined to perform a few adjustments to the browser-side scripts. It's usually not difficult to locate the interval period and reduce it so as to make the application more responsive. That's an annoyance for public websites as the server's and bandwidth are stressed more than the designers had intended. In an application settings, the implications can be more severe, as it allows users to systematically jump the queue and make transactions others were about to make. This might mean the user with the eager browser ends up with the last concert ticket browser or the lowest price for a trade.

As a general rule, there's not much point in trying to obfuscate information like this, because it's always going to be in the browser in some form. What's more important is to detect such abuse server-side. In the application examples, that shouldn't be too difficult because the user is identified with each request. Some offline analysis makes it easy to check if requests are occurring with excessive frequency. For a public website, the session might also be tracked necessarily if the application is designed to use conversational state, i.e. tracking application state with cookies. In other public websites, it may be difficult to perform user tracking, and probably not worth the effort anyway.

Allowing for Explicit Submission may satisfy the needs of users who sometimes want information immediately uploaded.


Real-Life Examples

Google Suggest

Google Suggest features Suggestions, so when you type "AB", the browser pops up a list of popular searches beginning with "AB". It would be possible to submit each keystroke, but that would be undesirable if the user is a fast typist. First, it's expensive for Google. Second, the user's browser and connection might not be able to cope with so many requests at once, so the results will tend to lag behind.

To prevent against excessive queries, Google Suggest uses Submission Throttling. According to Chris Justus's Dissection]:

mainLoop sets itself up to be called repeatedly using the javascript setTimeout function... It's interesting to note that the designers decided to use this timeout based mechanism rather than the keydown mechanism... This would handle fast typers on slow connections (so if I typed 3 characters between timeouts, a single request would go out to google...) The mainLoop checks if the state of the input field has changed and if so, takes action - looking first in the result cache, then making a call out to google.

Interestingly, the interval between calls seems to be dynamic, adjusted according to how quickly the server responds.

Zuggest

Zuggest is a Live Search showing Amazon results as you type. So type "ab" and you'll get results like "Basic Ab Workout for Dummies" and "Absolutely Fabulous". The results are images s well as text, so it would be expensive to search for something you weren't interested in. So if you're searching for "Absolutely", it's best to avoid searching for "Ab" and "Abso" and "Absolut" along the way, which is the kind of thing the Google Suggest algorithm would do.

To ensure searches are relevant, Zuggest applies a delay while typing. The assumption is that you'll be typing at a rate of at least one character per second. Any time you hit a key, you'll see a "Waiting until you're done ..." message, and you'll have a second to hit another key. If no key is pressed, the application assumes you were looking for the current term, and performs a remote call.

As explained in the Fat Client pattern, the Wiki demo throttles in a similar manner.


Code Example

The Assistive Search demo throttles in a similar manner to Google Suggest and other Ajaxian search applications.

requestValidCategoriesLoop runs repeatedly, the precise interval (in milliseconds) determined by the THROTTLE_PERIOD variable. The last server query is always stored, and there's nothing to do if the current query remains the same as the previous query. If there has been a change, the new query is submitted to the server.

 function requestValidCategoriesLoop() {
     if (query()!=latestServerQuery) {
       vars = {
         queryType: "getValidCategories",
         queryText: escape(query())
       }
       ajaxCaller.get("categories.php", vars, onValidCategoriesResponse,
                      false, null);
       latestServerQuery = query();
     }
     setTimeout('requestValidCategoriesLoop();', THROTTLE_PERIOD);
 }


Alternatives

Explicit Submission

Explicit Submission is the counter-pattern to Submission Throttling. With Explicit Submission, the user decides when to submit, whereas Submission Throttling automates the process.


Related Patterns

Fat Client

Fat Client emphasises browser-intensive programming with minimal interference from the concern of browser-server communication. Submission Throttling helps as it has less impact on the user-interface and browser-side programming model than its counterpart, Explicit Submission.

Periodic Refresh

Periodic refresh is somewhat the reverse of Submission Throttling: instead of periodically uploading user input, Periodic Refresh periodically downloads server state.

Progress Indicator

A common trend while performing a periodic update is to include a small Progress Indicator, often a Popup with a message such as a "Saving".


Visual Metaphor

Science-fiction writers have speculated that interstellar communication would work like this. Because the trip is so great, each imperial command must contain a great amount of information - the inter-galactic emperor can't just tell the colonials to "go fetch a kettle" ... wait 20 years ... "now add some water" ...