Sunday 9 March 2014

Caching - Part 1

I feel caching is the most effective but least utilized feature in building application. I think it come from the fact that no product manager would pay for it. It is true that caching bring huge benefit to system, but sometimes,  no one take initiative to calculate and represent how much performance the system will earn from it. Moreover, the benefit of caching is not so obvious under low load condition. The benefit is only shown clearly when the production server is up and serving huge load.

However, we should develop the application with the assumption that it will serve high load in the future; because if we do not, it will be too late when this happen. In this article, I will share my experience on integrating caching to the system that I have built before.

Cost and benefit of caching

Caching cost memory and little of processing time. It is worth the effort, providing that load and hit rate both are high enough and you do not let it occupied all the memory available. To simplify the calculation, we can build a simple model:

h : hit rate, the proportion of access hitting cache.  0 <= h <= 1
t1: processing time for fetching record from cache.
t2: processing time for fetching record from original source.

When we get the record from the cache, response time will be t1. When we fail to get record from the cache, the response time can be simplified as (t1+t2).



Then the average response time when having cache will be:

t = h * t1 + (1-h) * (t1+t2) = t1 + (1-h)*t2

The response time when not having cache is t2. Then the average response time change is

dt = t1 + (1-h)*t2 -t2 = t1 - h*t2.

Providing that normally t1 is normally smaller than t2 by large margin, you do not need hit rate to be very high to improve average response time. However, caching does not only cost processing time, it also use memory. If the cache storage is smaller than amount of concurrent users accessing data, the records on the cache will be constantly purged due to out of storage, which will greatly lower the hit rate.

Another concern for caching is validity of data. It depends on the mechanism to maintain validity of data, it may add to total cost of caching. If the record is stored with expiration time, it will periodically be refreshed when the old record is time out. Some developers prefer to have a better control by regularly fetching new records from data source. In this case, the effort of fetching new records need to be included as well.

Because of that, developer need to maintain balance between cost and benefit of caching. For a general rule of thumb, I would suggest that we should implement caching if we manage to achieve hit rate of at least 50% and still have at least of 50% of RAM available under modest load. Any lower amount will not justify the effort.


Where to cache?

As the most popular architecture now a day is 3-tier, I will discuss the caching mechanism on this architecture.

 Illustration of 3-tier Architecture by blog.simcrest.com


There is no clear guidance for the best place to implement caching; however, you still need to carefully design how you want to do caching. If you over use caching, you may waste resource if the records on lower tier cache being idle, waiting to be expired because the data have been served from higher tier cache. In this case, the cost is still induced but no benefit can be gained at all.

Caching on each tier has its own characteristics, with the client tier caching provide greatest performance boost but less reliable and lower tier caching provide less benefit but give higher level control.

Let go into detail of caching on each tier.

Caching on client tier 

Caching on client make use of browser to store data. This is the fastest cache as it even do not require the request to be send to server. As, it is summarised here,

"the fastest http request is the one that not made"

There are three places that can be used to cache different types of information. They are browser cache, cookie and javascript objects. Each of them have their own life-cycle and aim to store different kinds of resources but share a common attribute of low reliability. This is no surprise because the browser belong to user, not developer.

1/ Browser Cache 

There is a default-on feature on any browser. Depend on resources available and configuration, the browser may choose to cache up to a certain amount static resource. Generally, Chrome has the biggest cache with storage size up to 80MB, IE and Firefox only limit at 50MBs. Through HTTP 1.1, the server can tell browser to turn on/off caching for each response and whether the resource should have expiration time. As mentioned above, browser cache is not reliable, any time, user can clear the whole cache and turn off caching.

To facilitate browser cache, developer need to know how to enable/disable caching for each request. Other than using HTTP header, there are some other useful information related to browser caching:

  • GET request can be cached, POST request can not be cached. However, POST request is generally use more bytes to transfer content and can be broken into 2 consecutive requests, one for header, one for request body
http://benramsey.com/blog/2008/04/http-status-100-continue/
  • The resource is uniquely identified by URL. It is a well-known technique to include a dynamic query to force browser to load resource from server as it make the URL always unique. The simplest way of generating dynamic query is to apply current time to the resource URL. This solution is included as part of jQuery.ajax() API (as mentioned above, only applicable to GET requests). However, kindly notice the impact of this method as browser still attempt to cache the response, it just never use the data in the cache. So, the browser storage is wasted. 
  • There is no need to worry about expiration time of a resource if the resource content is uniquely identified by resource url. You can achieve this by using some Javascript framework like Rhino, YUI Compressor or UglifyJS. 
  • There are two kinds of GET requests, conditional update request and unconditional request. With the former request, browser include a header named If-Modified-Since to the request. The server simply response with HTTP response code 304 Not Modified instead of serving full content. Normally, if user press F5, browser will load resources with conditional update requests and if user press Ctrl + F5, browser will load resources with unconditional request. This work well, except for IE. IE do not bother to make a conditional update request as long as the cache still alive.
  • GWT RPC use POST request to transfer data. Because of this, GWT never cache the response. However, it is achievable if you construct your own HTTP request instead of using RPC, just remember to use the GET request rather than POST. I my self always prefer mixing GWT with static HTML by loading HtmlFrame. GWT by native do not cache but lots of contents are safe and supposed to be cached. To make caching more reliable, I make use of technique above to include hash code to any url to avoid rendering obsoleted data. 

2/ Cookie

Cookie can be used to store information but the size is limited (4 kb) and we can only store string. The advantage of cookie is this resource persist when user hit F5. Because of this, you can use it to store small information. For example, if your web page has a combo box contain all phone manufactures, it is not necessary to hit server to load this content again.

However, kindly notice that this is on theory only. I have not used cookie for this kind of purpose. If we found the combox box is simple enough, I prefer to load the content of combo box as part of main page html rather than using Ajax request to populate content.

3/ Javascript Objects

I use this often, coming from the fact that it is easy to write code this way if you make use of GWT. Even if you use plain javascript, it is still easy to cache object but GWT offer great benefit by providing scope for your javascript object.

Javascript objects should be used only when your webapp is rich client application and have repetitive calls. When user refresh web page, all java-script objects are deleted.



1 comment: