Browser-Side Cache - Ajax Patterns

Browser-Side Cache

From Ajax Patterns

Evidence: 1/3

Tags: Auto-Update Memoise Memoize Sync Synchronise Sychronize Real-Time


Contents

In A Blink

Image: data pulled down and kept locally.

Goal Story

Tracy is tweaking parameters to run a complex mathematical calculation. The last thousand results are retained by the browser, so each time she attempts to perform one of those calculations, the browser shows the result automatically, saving a trip to the server and improving user experience.


Problem

How can you make the system respond quickly to user activity?


Forces

  • The application should respond to user actions quickly, ideally instantaneously.
  • Many user actions require a response from the server.
  • Responses from the server can be noticeably latent due to data transfer and server processing overheads.


Solution

Retain server results in a browser-side cache. The cache holds query-result pairs; the queries are cache keys and the server results are server results. So, whenever the browser performs an XMLHttpRequest Call, it first checks the cache. If the query is held as a key in the cache, the corresponding value is used as the result, and there is no need to access the server.

What format exactly are the key and value? In the simplest case, the query would just be the URL and the result would be the response body. Other times, the query and key might represent more high-level, semantic, content. This is really a design decision, covered in the next section.

A cache data structure requires some way to access the key-value pairs "randomly" - that is, directly, without having to traverse the entire data structure until the desired key-value pair is found. In Javascript, a cache can be created using an associative array (which is actually just an object underneath). So an empty array is created at startup and gradually accumulates server results. Of course, an Ajaxian application lives indefinitely, so the array could continue growing if not controlled. There are a few ways to handle this, as discussed in the next section.

It's common in many systems to treat the cache as a Proxy (see Gamma et al.'s Proxy pattern). That is, clients retrieve results from an object called something like "ResultFetcher", which encapsulates anything to do with fetching of results. From their perspective the ResultFetcher just provides results. It doesn't matter to the client whether all results are directly pulled from the server, or whether some of them are cached inside ResultFetcher.

TODO diag. Requester calls ResultFetcher, which contains cache and server connection.

Here's where the asynchronous nature of XMLHttpRequest adds a slight complication. Under normal circumstances, a caching ResultFetcher always returns the desired value synchronously, whether the result was in the cache or not. But with Ajax, it can only do this if the result was indeed found in the cache. Otherwise, the server response will come back some time later, after the fetching function has already returned. To deal with this, you might consider having the requester pass a callback function to the fetching procedure. So the fetching procedure never returns anything directly, but always ensures the callback function is called with the desired value.


Decisions


What will be stored as keys? For values?

The solution mentioned a couple of possibilities for keys and values. In the first instance, they might simply be URLs and response bodies. This is quite an effective solution, as long as you are following the RESTful Service approach of retrieving information with GET queries. If you're retrieving information by POST, you'll have to key on the entire request body. What's nice about this approach is that it completely separates the caching mechanism from the application. There are now quite a few libraries offering wrappers around XMLHttpRequest and many of these will probably incorporate such a facility.

Using the entire URL and response body does come at a cost. Both contain a lot of useless information, which limits how many items can be stored in the cache. An alternative is to use semantically related values. For example, the key might be customer names, and the values might be customer objects.


How will the cache size be kept under control?

You typically keep the cache size under control by deciding on its capacity, and deciding on some way to remove elements when that size has been reached. Usually, each new element results in an older element being discarded. For efficiency, you might discard a large batch at once, and then let the cache gradually build up again.

Two common algorithms are:

  • Least Recently Used (LRU): The discarded item is the one with the longest time since it was last retrieved.
  • Least Frequently Used (LFU): The discarded item is the one which has been retrieved the least.

Both algorithms are feasible in Javascript, provided you use the right data structure. The Code Example below illustrates LRU.


How will you protect against stale data?

It's all hunky-dory saving server calls, but if the server data's changed, doesn't the user need to know? How will the browser ever find out if it keeps getting results from the cache? The first question to ask here is, "How recent does the data have to be?" If it's real-time statistics being used by a nurse to monitor a patient's health, it probably needs to be pretty recent. So much so, that a cache might even be out of the question. If it's a student perusing a five-year old article on ancient Athenian literature, a twelve-hour cache will do fine.

There are several ways to enforce this decision:

  • Attach a timestamp to each item that goes into the cache. Whenever you retrieve an item, inspect the timestamp to determine if the result is recent enough.
  • As a variant on the above, schedule a periodic loop to actively delete stale items.
  • Implement a browser-server protocol which allows the browser to determine if items are stale. So the browser might keep a timestamp for each item and server exposes a service to accept a timestamp. The server only needs to send the whole response if the value has changed since that time. An alternative to timestamps would be a hash function, a function which the browser runs against the cached value and can then be compared by the server against the item's most recent hash value, to see if a change has occurred.
  • Implement a service on the server which announces changes that have occurred. Use Periodic Refresh to actively listen for such changes, and delete from the cache any items that have changed.


Real-World Examples

libXmlRequest

Stephen W. Cote's [1] was one of the earlier wrappers of the XMLHttpRequest object. A typical asynchronous request looks like this:

 getXml(path, callbackFunction, 1, requestId);

To make the request cached, simply add an extra argument at the end:

 getXml(path, callbackFunction, 1, requestId, 1);

The approach shows how cache functionality can be made orthogonal to core application functionality.


Refactoring Illustration

The basic Sum demo has to resort to the server each time the cache is reached. This refactoring adds caching functionality to reduce server calls, and is implemented in three stages.

Including the Query in the Response

The asynchronous nature of XMLHttpRequest Calls separates the initial query from the response, so it's not always clear, when a request comes in, what the corresponding request was. One way to achieve this is to include the original query as part of the response, and that's the first refactoring here. The refactoring is detailed in XML Message, and the net effect is a response like follows:

  <sum>
    <inputs>
      <figure id="1">4</figure>
      <figure id="2">8</figure>
      <figure id="3"></figure>
    </inputs>
    <outputs>12</outputs>
  </sum>

Previously, the response was just "7". The resulting value is extracted from the XML in a slightly different way, but the inputs are not used until the next iteration.

An Infinite Cache

The next refactoring creates a cache, but one that has no regard for the laws of physics - it just keeps growing indefinitely. That's a bad thing, but a useful stepping stone to the final iteration. The cache holds the sum against a "figuresString", simply a comma-separated list of the three figures.

First, the cache is created a global variable and initialised from the onload method:

 var sumByFigures;
 ...
 function restartCache(html) {
   sumByFigures = new Array();
   ...
 }

Each time a sum is submitted, figuresString is calculated to form a key for the cache. The cache then be interrogated to see if it already contains that sum. If not, an asynchronous call will be set up. Either way, the ultimate consequence is that repaintSum() will eventually be called with the new sum. If the result is already cached, it will be called straightaway. If not, it will be called after the server has returned.

 function submitSum() {
   ...
   var figuresString =
     figures.figure1 + "," + figures.figure2 + "," + figures.figure3;
   var cachedSum = sumByFigures[figuresString];
   if (cachedSum) {
     repaintSum(cachedSum);
   } else {
     repaintSum("---");
     ajaxCaller.get("sumXML.php", figures, onSumResponse, true, null);
   }
 }

onSumResponse not only calls repaintSum() with the value in the response, but also pushes the result onto the cache.

 function onSumResponse(xml, headers, callingContext) {
   var sum = xml.getElementsByTagName("output")[0].firstChild.nodeValue;
   repaintSum(sum);
   var figures = xml.getElementsByTagName("figure");
   var figuresString =   figures[0].firstChild.nodeValue + ","
                       + figures[1].firstChild.nodeValue + ","
                       + figures[2].firstChild.nodeValue;
   sumByFigures[figuresString] = sum;
 }

Finally, repaintSum is the function that detects a change - either way - and simply morphs the displayed sum.

 function repaintSum(html) {
   self.$("sum").innerHTML = html;
 }

A Finite Cache

The final cache enhances the previous version by introducing a least-recently used disposal algorithm. Each time a new item is added to the cache, the least recently used item is discarded from the cache. It would be inefficient to trawl through the entire cache each time that happens, comparing usage times. So, in addition to the associative array, a parallel data structure is composed. It's a queue, where each new item is pushed to the tail of the queue and gradually approaches the head as further items are pushed on. When the queue is full and an item is pushed on to the tail, each item moves down one, and the head item "falls off" the queue, so is deleted from both the queue and the associative array. Whenever an item is retrieved, it's sent back to the tail of the queue. That's what ensures the least recently used item is always at the head.

The queue itself is a generic class, with the following functions: enqueue(), dequeue(), sendToTail(). It works by tracking the head, the tail, and the size; and keeping the items in a doubly linked list. For example, enqueue() is defined like this:

 Queue.prototype.enqueue = function(obj) {
   newEntry = {
     value: obj,
     next: this.tail
   }
   if (this.tail) {
     this.tail.prev = newEntry;
   } else {
     this.head = newEntry;
   }
   this.tail = newEntry;
   this.size++;
 }

Back to the sum application. It now declares a queue as well as the associative array:

 var figuresQueue, sumByFigures;

Each time a new element arrives from the server, it's sent to encache(). encache will lop the least-recently used item off both data structures if the queue is full. Then it will add the new item to both.

 function encache(figuresString, sum) {
   // Add to both cache and queue.
   // Before adding to queue, take out queue head and 
   // also remove it from the cache.
   if (figuresQueue.size == cacheSize) {
     removedFigures = figuresQueue.dequeue(figuresString);
     delete figuresString[removedFigures];
   }
   figuresQueue.enqueue(figuresString);
   sumByFigures[figuresString] = sum;
   $("queueSummary").innerHTML = figuresQueue.describe();
 }

Whenever the cache is queried, the queried value is not only returned, but sent back to the tail of the queue to mark it as having been recently used:

 function queryCache(figuresString) {
   // Recently used, so move corresponding entry back to tail of queue
   // if it exists.
   figuresQueue.sendToTail(figuresString);
   $("queueSummary").innerHTML = figuresQueue.describe();
   return sumByFigures[figuresString];
 }

With these abstractions in place, there is not much change to the core part of the sum script. submitSum() queries the cache and calls the server if the result is not found. And the server response handler ensures new results are added to the cache:

 function submitSum() {
   ...
   var cachedSum = queryCache(figuresString);
   if (cachedSum) {
     repaintSum(cachedSum);
   } else {
     repaintSum("---");
     ajaxCaller.get("sumXML.php", figures, onSumResponse, true, null);
   }
 }

 ...

 function onSumResponse(xml, headers, callingContext) {
   ...
   encache(figuresString, sum);
 }


Alternatives

Built-In Browser Cache

Browser-Side Cache is an object created and accessed by the browser-side script. But browsers also have their own caches, which map URLs to content. XMLHttpRequest Calls are affected by browser caching in much the same way as regular page requests. Thus, caching can be automatically handled by arranging for the server to cache-related directives in the headers of XMLHttpRequest response. This can be done with server-side programming, and XMLHttpRequest can also be given a custom header for the request. The precise details are browser-specific.

Relying on the built-in browser cache is useful from a programming perspective, as it effectively delegates away the caching strategy to the browser. The potential downside is loss of control - it relies on the user's cache being enabled and sufficiently large, and your application's data can be removed from the cache when the user fills it with content from other websites being visited.

Server-Side Cache

Caching data on the server cuts down on processing, especially when the data is shared by multiple users. However, that's mainly a benefit if server processing is the bottleneck. Bandwidth is more often the chief constraint, and a server-side cache won't reduce browser-server traffic.

Fat Client

Fat Client involves transferring functionality from the server to the browser. The browser won't need to call the server if it can compute the result locally.


Related Patterns

Submission Throttling

Browser-Side Cache focuses on "read caching", in which responses from the server are held in the cache. Another flavour of caching is "write caching", where output is held in a buffer to defer outputting to its true destination. Submission Throttling is a form of write-caching.


Visual Metaphor

Consultants usually charge a fee to answer a query. Instead of directly querying them each time, retain their response and index it so you have it available next time.


Want to Know More?

Hi. Will it be possible to have the final source files of this example? I can't get it to work and I am sure it is just a little transcription error. It will be very helpfull. Thanks in advance.