Fog Creek

Wasabi: Fragment Caching and Memoization

Stefan recently discussed some of the benefits of picture
functions and metaprogramming in Wasabi. One of the first (and arguably one of
the most useful) internal tools that these features spawned during FogBugz 6
development was the ability to easily memoize and cache function results.

Performance was one of our primary concerns when working
on FogBugz 6, so the ability to reuse previously calculated results within any single
request (memoization) or to store longer-lasting results in the database for
use in future requests (fragment caching) was badly needed. Those who are
familiar with other popular web frameworks are probably used to having these
caching tools readily available, although their implementations are sometimes
quite clunky. We were a little bit jealous, so we decided to chase after our
own implementation.  Unfortunately, in
classic ASP/VBScript there is no way to easily achieve this behavior without
massive code duplication and, as a result, an increasingly high likelihood of
cache-related errors.

Wasabi metaprogramming lets us solve the problem
gracefully. What we need is a way to tag a function as <Cacheable>, in which case every call to the function
will check the database for previously stored results and short-circuit if such
a result is found, avoiding the possibly expensive function execution (for the
rest of this article I will only discuss caching, which uses the FogBugz
database as its storage, although memoization is an almost equivalent piece of
functionality which uses per-request in-memory storage).

However, there are a number of complicating factors:

1. Different function inputs produce different outputs.
2. Cached results, or fragments, are usually
user-specific. I should never see the cached result of a function called by
Stefan or Joel.
3. Changes in the database state over time may invalidate
pieces of the fragment cache. 

Let's modify Stefan's flower picture function and make a
little utility function that generates the picture of a flower stem with a leaf
either on the left or the right. It also places the flower in a pot depending
on the state of the database: 


<Cacheable(“FlowerPots”),
Picture> _

Sub MyStem( fLeft )
    If fLeft Then
       
%><pre>
         __ |
         \ \|
          \ |
           \|
       
</pre><%
    Else
       
%><pre>
            | __
            |/ /
            | /
            |/
       
</pre><%
    End If

    If HasFlowerPot()
Then
        %>
        _________
        \       /
         \     /
          \___/
        <%
    End If
End Sub 


Notice that we've added a <Cacheable> attribute to this function. This means that
anytime, say, Joel's user logs in
to FogBugz and generates a call to
MyStem requesting a leaf on the left, we check the database to see if the
result of this function with matching parameter values has already been stored
for Joel. If so, we give him back the stored value in presumably much shorter
time than letting the entire function run (you'll have to pretend for this
example that execution actually takes a significant amount of time), Joel
doesn't wait as long for the page to load, FogBugz is faster, and everyone's
happier.

What did we need to accomplish this?  We need to intercept calls to MyStem,
normalize all parameters, and check the database for any matching cached
results.  If we don't find any, we need
to run the original MyStem function, take a picture of its result, store the
result in our cache, and return the result. These pieces are easy with Wasabi,
and Stefan has already covered most of the necessary tools. I won't go into the
specifics here, but the intermediate code generated by Wasabi would look
something like:


Sub MyStem( fLeft )

    Dim sArgs =
Hash(CStr(fLeft))

    If
FragmentCache.Exists(“MyStem”,
sArgs) Then
 
       
Response.Write FragmentCache.Retrieve(“MyStem”, sArgs) 
    Else 
        Dim sResult
= PictureOf OriginalMyStem(fLeft)
       
FragmentCache.Store(“MyStem”,
sArgs, sResult)
       
Response.Write sResult
   
End If

End Sub


A slightly more interesting piece of the fragment cache
is its database-oriented cache maintenance. The original <Cacheable> attribute sent an
additional argum
ent along to its code generator, “FlowerPots”. This string matches the name of a database table which
MyStem now depends on, and anytime the contents of table FlowerPots changes,
the cached results of MyStem are invalidated.

How does this work? Since Wasabi knows about all
Cacheable functions at compile time, we can build up a dictionary which
associates database table names with their dependent cached functions. Since
all SQL queries go through our own SQL command wrapper, any time a SQL command
is run from within FogBugz we can simply detect which tables are being changed
and invalidate all associated function results. 
This means that whenever I “DELETE
* FROM FlowerPots”, the cached results of MyStem are also deleted so no stale
potted flowers are incor
rectly drawn. Although it may seem that
detecting any and all updates to FlowerPots is too aggressive of a
cache-invalidation tactic, we do have all types of more specific tools which
let programmers choose whether or not to invalidate the cache during specific
queries.

As mentioned by Stefan, one of the nicest things about
letting Wasabi generate code at compile-time is that the user doesn't have to
wait for these associations to be created and for cache maintenance to be
performed.

Being able to simply add <Cacheable(“TableName”)> to any expensive
function and gain safe, database-dependent fragment caching has been an
enormous advantage, particularly when generating large chunks of HTML. There is
no way FogBugz 6 would perform anywhere near its current
speed if we weren't
able to make use of easy tricks like <Cacheable> and <Memoizable>.

In the future, when we have nice
serialization/deserialization worked out for all of our objects, we'll also be
able to cache objects (which we can already memoize since in this case they're
simply stored in memory).