June 25th, 2009 | Published in Google Code
I recently gave a talk (preserved YouTube here) about the cache pattern and the Web Storage Portability Layer (WSPL) at Google I/O. It was exciting getting to give a talk at the Moscone Center as previously I had only ever been one of the audience members. The conference seemed to go by in a blur for me as I was sleep-deprived from getting the WSPL to "just good enough" to actually be released. (And some ofyou have already pointed out that I missed several bugs.) In my talk, I provided a general overview of the cache pattern and this post expands on the handling of hit determination and merging server and local changes.
The cache pattern is a design pattern for building an offline-capable web application. We implemented the cache pattern to make Gmail for Mobile tolerant of flaky wireless connections but the approach is generally applicable. Here's how it works. Consider a typical AJAX application. As shown in the diagram, we have a web application with a local model, view and controllers. The user interacts with theapplication and the controller dispatches XmlHttpRequests (XHRs for short) to the server. The server sends asynchronous requests to the application which it inserts into the model.
As shown in this next diagram, in the cache pattern, we insert a cache between the application and the server. Having done so, many requests that would otherwise require a round-trip to the network.
A software cache like this one shares a great deal conceptually with hardware caches. When designing the cache used in Gmail for mobile, we used this similarity to guide our design. For example, to keep our cache as simple as possible, we implemented a software equivalent to a write-through cache with early forwarding and LRU eviction. The cache pattern in general (and consequently our implementation) has four important data flows as shown in the diagram.
- Cached content bound for the UI.
- Changes made to the cache by the user in the UI. These need to be both reliably sent to the server and updated locally in the cache so that reads from the cache for UI updates show the state including user changes.
- The changes recorded in the cache need to be sent upstream to the server as the network connection is available.
- Changes made to the server (like email delivery in the case of Gmail) need to be merged into the contents of the cache.
To actually implement these four data flows, we need to decide on a hit determination mechanism, a coherency strategy and a refresh approach.
Coherency and Refresh
Perhaps the most complex aspect of the cache implementation is deciding how to get updated content from the server and how to merge server updates with changes made locally. A traditional hardware cache resolves this problem by only letting one processor modify its a cache at a time and have the memory broadcast any changes to all the other caches in the system. This approach cannot work here because the Gmail server can't connect to all of its clients and update their state. Instead, the approach we took for Gmail for Mobile was for the client device regularly poll the server for alterations.Polling the server for changes such as new email or the archiving of email by the same user from a different device implies a mechanism for merging local changes with server side changes. As mentioned above, Gmail for Mobile is a write-through cache. By keeping all of the modifications to the cache in a separate queue until they have been acknowledged, they can be played back against updates delivered from the server so that the cache contains the merge of changes from the server and the local user. The following diagram shows the basic idea:
Later, the user makes change  to the UI which causes the cache to append it to the write buffer in the applyUIChange call. Later still, another query is made and so, the cache sends [Q] to the server. In the mean time, the user makes yet another change . This is written to the write buffer. Once changes  and  are acknowledged by the server along with the new cache contents for query [Q], changes  and  are removed from the write buffer. However, to keep the cache's state reflecting the user's changes, change  is applied (again) over top of the result for [Q].
Simplifying the implementation of this reapplication stage is the most important benefit of implementing a write-through cache. By separating the changes from the state, it becomes much easier to reapply the changes to the cache once the server has delivered new content to the cache. As discussed in a previous post, the use of SQL triggers can greatly improve database performance. Whether updating or re-updating, triggers are a great way to make the application of changes to the cache much more efficient.
- create a database transaction, and while in the transaction
- query the database for the desired key
- accumulate the results
- then outside of the transaction, return the result to the UI.
- create a database transaction, and while in the transacation
- write the change to the write buffer
- wait for a trigger to update the state of the cache.
Updates Bound For The Server
As discussed above, once the changes have been written to the write buffer, they still have to be sent to the server. This happens by prepending them to queries bound for the server. The fetchFromServer from the example is responsible for this. As might be familiar by now, the flow is
- create a database transaction and while in the transaction
- query the write buffer for all the entries that need to be sent to the server
- accumulate the entries
- then outside the transaction, send the combination of changes and query to the server
Changes From The Server
Finally, we need to merge the changes from the server into the cache as is done in the insertUpdate method from the example. Here the flow is as follows:
- create a database transaction and while in the transaction
- update the directory
- write the new content into the cache
- touch the changes in the write buffer that need to be re-applied to the cache
- wait for the trigger to complete its update
- then, outside of the transaction, send the response to the UI if it was satisfying a cache miss.
Previous posts from Gmail for Mobile HTML5 Series
HTML5 and Webkit pave the way for mobile web applications
Using AppCache to launch offline - Part 1
Using AppCache to launch offline - Part 2
Using AppCache to launch offline - Part 3
A Common API for Web Storage
Suggestions for better performance
Robert Kroeger, Software Engineer, Google Mobile Team