Submission Throttling






Submission Throttling

Buffer, Queue, Performance, Throttle

Submission Throttling


Developer Story

Devi's producing an Ajax chat web site and wants to transmit text as the user types. However, she knows some users will type faster than the system can cope with so she introduces a throttling mechanism that ensures no more than one message is uploaded every 200 milliseconds.

Problem

How can information be submitted to the server?

Forces

  • Information is often uploaded in bursts; e.g., a chat tool incurs many hits when a user becomes passionate about the topic, or a data entry tool incurs many hits when the user responds to some new information.

  • It's difficult for the server to cope with lots of messages at once.

  • Browsers can only handle a limited number of pending XMLHttpRequest Calls at any moment.

  • 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 movementso, 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 bandwidthand to lessen server processing, 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 (Chapter 14) interface like Google Suggest (http://www.google.com/webhp?complete=1&hl=en), 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 millisecondsfeasible with a localhost web server, maybe workable on an intranet, but not scalable for most public Internet applications. So Suggestion systems, and more generally Live Command-Lines (Chapter 14), 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 (Chapter 14), 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 critique the form data, so as to provide live feedback.

The other style of buffer is a command queue. Here, Commands (see Gamma et al., 1995) are held in a queue, and the whole queue periodically uploaded to the server before being cleared. Some kind of serialization must take place, so the Commands must be represented as Strings and the Queue must ensure they can be pulled apart by the server; e.g., by separating them with a delimiter character. It's up to the developers to agree on a protocol for defining how Commands are represented as Strings. For example, a wiki might use the string "Del Issues" to delete the Issues page. Another technique would be to store the commands as custom JavaScript objects and serialize them into JSON Messages (Chapter 9).

Submission Throttling might appear to optimize technical resources at the expense of usability, but can actually 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 overloadmuch more information than they actually care about. Throttling is a good way to prevent information overload in the browser, especially error messages that might come back because the user is only halfway through an edit.

Decisions

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

Submission Throttling is vulnerable to integrity issues, because synchronization is being deliberately downgraded. The universe will have moved on since the user submitted the original commandsthe 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. All of these scenarios are unavoidable manifestations of the asynchronous nature of Ajax, and the design must take them into account.

The server needs to decide whether to process each incoming command as it's quite possible some are no longer valid. For example, a stock purchase order might be refused on the basis that the price has just risen or because the server has since expired an initial quote it made to the client. Some of these decisions can be made by standard techniques such as atomic database transactions, but others might require some custom business logic. Furthermore, some business logic will be required to decide what to do with the rest of the Commands in a queue, should one Command in the middle fail. Sometimes, it's okay to keep processing the rest and sometimes not.

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 variant, usually more useful, is to cap the rate but immediately send the first command after a long wait. This helps a user who changes information only occasionally. Let's say the throttle period is 30 seconds. With a standard, fixed-interval, algorithm, the following sequence occurs:

  1. 00 secs: system polls, no activity so no upload

  2. 30 secs: system polls, no activity so no upload

  3. 60 secs: system polls, no activity so no upload

  4. 65 secs: infrequent user does something; no upload yet

  5. 75 secs: infrequent user does something; still no upload

  6. 90 secs: system polls and uploads both pending commands

We can still cap the rate at 30 seconds, but upload a command immediately if there's been no activity for the past 30 seconds:

  1. 00 secs: system polls, no activity so no upload

  2. 30 secs: system polls, no activity so no upload

  3. 60 secs: system polls, no activity so no upload

  4. 65 secs: infrequent user does something

  5. 65 secs: system notices and uploads command immediately

  6. 75 secs: infrequent user does something; this time, the command must wait since there was a recent call

  7. 95 secs: system polls, uploads if there was any further activity after 65 secs

Prioritization is another technique. A timer might be used for regular events, but with priority given to any critical commands. A Live Form (Chapter 14) 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.

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

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 in parallel, providing you have considered the consequences of commands arriving in a different order to the user requesting them. Prioritization was already mentioned above, which would be one reason to have several buffershigher-priority buffers being processed with greater frequency.

Here's how a blog reader might use three buffers in parallel:

  • A low priority queue uploads comments submitted by the user. Throttle period: 15 seconds.

  • A medium priority queue pulls down requested feeds from the server. Throttle period: 3 seconds.

  • A high priority text buffer lets the user tag articles with a Suggestion mechanism. While it's not necessary to upload upon each keystroke, any new information must be transferred quite rapidly. Throttle period: 0.2 seconds.

This example illustrates that it's quite easy to run several buffers without threat to data integrity and without user confusion.

How long should the throttle period be?

Deciding on the throttle period requires some analysis of user needs. As the previous blog reader example demonstrates, there is a range of periods that might be required:

  • For background synchronization, the period can be a few minutes if resource constraints apply, although it should ideally be in the order of 10 seconds. If it is several minutes, users should be kept informed with appropriate Progress Indicators (Chapter 14), lest they quit and lose work before the upload kicks in. Ideally, there should be an Explicit Submission (later in this chapter) mechanism as well, to allow immediate saving.

  • At the other end of the spectrum, for low-level interaction while the user types and mouses around, the period must be in the order of 100 milliseconds.

Real-World Examples

Google Suggest

Google Suggest (http://www.google.com/webhp?complete=1) features Suggestions, so when you type "A," the browser pops up a list of popular searches beginning with "A." To prevent against excessive queries, Google Suggest (http://serversideguy.blogspot.com/2004/12/google-suggest-dissected.html) uses Submission Throttling.

Zuggest

Zuggest (http://www.francisshanahan.com/zuggest.aspx) is a Live Search (Chapter 14) showing Amazon results as you type (Figure). So type "Ab" and you'll get results like "Basic Ab Workout for Dummies" and "Absolutely Fabulous." The results are images as 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.

Zuggest


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 (http://ajaxify.com/run/wiki) throttles in a similar manner.

Gmail

Gmail (http://gmail.com/) has an auto-save feature that periodically uploads a message being composed.

Prototype framework

Prototype (http://prototype.conio.net/) offers a reusable component, TimedObserver, which performs Submission Throttling. ListSomething (http://listsomething.com/), a search engine for classified ads, utilizes TimedObserver for its Live Search.

Code Example: AjaxPatterns Assistive Search

The Assistive Search demo (http://ajaxify.com/run/assistiveSearch) throttles in a similar manner to Google Suggest and other Ajax search apps.

requestValidCategoriesLoop runs repeatedly; the precise interval (in milliseconds) is determined by the ThrOTTLE_PERIOD constant (about 100 milliseconds). 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);
  }

Related Patterns

Periodic Refresh

Periodic Refresh (see earlier) 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 (Chapter 14), often as a Popup with a message such as a "Saving."

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 big load of informationthe inter-galactic emperor can't just tell the colonials to "go fetch a kettle" ... (20 light-years later) . . . "now add some water" . . . .



 Python   SQL   Java   php   Perl 
 game development   web development   internet   *nix   graphics   hardware 
 telecommunications   C++ 
 Flash   Active Directory   Windows