On April 7th, Google launched a new version of Gmail for mobile for iPhone and Android-powered devices. We shared the behind-the-scenes story through this blog and decided to share more of our learnings in a brief series of follow-up blog posts. This week, I'll talk about the cache pattern for building offline-capable web applications.
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.
As shown in the diagram we also need a place to actually write the data. We use the
WSPL library to write a cache implementation portable across both Gears and HTML5 databases.
To actually implement these four data flows, we need to decide on a hit determination mechanism, a coherency strategy and a refresh approach.
Hit Determination
At its heart, a cache is a mapping from keys to values: the UI invokes the cache with a key and the cache returns the corresponding element. While this sounds pretty simple, there is an additional source of complexity if the application wants to provide the user with summary listings of some subset of all values available from the server. To provide this feature, the cache needs to contain not only "real" data values but additional "index" values that list the keys (and possibly user-visible summaries) for "data" values. For example, in Gmail for mobile, the cache stores conversations as its "real" data values and lists of conversations (such as the Inbox in Gmail for Mobile) as its "index" values. Keys for index values are computed specially to record what subset of the complete index is cached locally. For example, in Gmail for Mobile, while a user's Inbox may contain thousands of conversations, the cache might contain an index entry whose data values lists metadata for only conversations 1000 through 1100. Consequently, Gmail for Mobile's cache extends keys with the cached range so that a request for metadata for conversations 1101 through1110 would be considered a cache miss.
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:
The green box in the diagram shows the contents of the cache's write buffer changing over time and the cloud corresponds to the requests in-flight to the server with time advancing from left to right in the diagram. The function names shown in the diagram are from the simplenotes.js
example file in the Web Storage Portability Layer distribution. Here, the user has applied some change [1] and the cache has written it to the write buffer and has then requested new content resulting in query [Q]. The cache prefixes the outstanding actions from the write buffer to the query. Action [1] is marked as needing a resend on some sort of network failure.
Later, the user makes change [2] 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 [1][2][Q] to the server. In the mean time, the user makes yet another change [3]. This is written to the write buffer. Once changes [1] and [2] are acknowledged by the server along with the new cache contents for query [Q], changes [1] and [2] are removed from the write buffer. However, to keep the cache's state reflecting the user's changes, change [3] 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.
Cached Content To the UI
The first of the four data flows is delivering content to the UI is reasonably easy: query the cache for the desired content and when the query completes, forward the request to the UI. If you look at the
getNoteList_ function from the simplenotes.js example code included in the WSPL distribution, you'll see that the delivering cached content to the UI has the following basic steps:perform hit determination: deciding if the requested cache contents are actually in the cache.
- 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.
Changes From The UI
The second flow (
applyUiChange) is recording changes made by the user to the write buffer. It has a very similar structure- 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.
That's a brief intro to the cache architecture as found in Gmail for mobile. We're continuing to improve our implementation of this basic architecture to improve both the performance and robustness of Gmail for mobile. Please stay tuned for follow on blog posts.
Previous posts from Gmail for Mobile HTML5 SeriesHTML5 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
By Robert Kroeger, Software Engineer, Google Mobile Team
