A simple caching strategy · [code, food, stuff] while(1)

W e frequently read stories about <insert company name> growing <insert four-digit number>% in six months and somewhere along the way they hit a scalability wall. Requests dropped, users suffered. Many prayers and goat sacrifices later, the problem was solved by leveraging <insert caching technology> running on <insert number> servers built on top of <insert consensus protocol> and using <hack #1> and <hack #2> to retrofit into existing system. Well, this is not one of those stories.

We have 1000+ contributors creating content on our platform at Sidelines. The content generated on the Sidelines platform gets distributed to millions of users through websites, apps, and ad networks, sometimes peaking at 50,000 users/second. Therefore the Sidelines platform is mostly read-only, with the relatively small number of writes coming from contributors publishing the content. These numbers are not particularly impressive in and of themselves, but when you consider that we scaled to this point with zero downtime using only a few lines of Python and a simple caching methodology things start to look a little more interesting.

Everything goes in the cache but not before it doesn’t

Every piece of code is written as if the cache didn’t exist. This ensures that: (1) DB indexes are being used properly, (2) long running queries are detected during testing, (3) if the cache restarts cold, the DB can survive a flood of requests and (4) if the cache fails we will not take any downtime. In fact, we can turn caching off altogether via a simple config value.

Relational databases are great. In fact, if the data fits in RAM then a relational database can return results as fast as your cache. All modern databases include a caching layer, usually called a buffer cache. Every time the database engine needs to access a page, whether it’s an index node or a data leaf, it checks in the buffer cache and if the data exists and is not dirty, the database simply returns it. At Sidelines, anything below a 99.5% buffer cache hit ratio triggers an alert in our monitoring system.

Beyond that, our caching strategy is trivially simple. We strive to store fully computed results instead of individual objects. Also, data such as images & video have no place in our cache or database, instead they go into a CDN and we cache the metadata.

Redis & Horizontal Scaling

Redis is one reliable piece of software. Before switching to running on Elasticache, we had a simple Redis Master-Slave config running on a box with a ton of RAM. That setup worked flawlessly for a whole year without any disruptions, excluding intermittent AWS network connectivity snags. We have fsync enabled on every request to prevent a scenario where the master comes back online after a failover and wipes the slave clean. Although in retrospect, given that we can handle the load of a cold cache with some degredation, we plan to turn fsync off during the next upgrade. We also rely on Redis to handle key expiration.

There are various solutions for scaling Redis. We are fortunate enough that our data fits in < 32GB of RAM so we have no plans to introduce key sharding, Redis Cluster or any other technological wonder that hits the Hacker News frontpage.

Enough already, show me the code

Everything revolves around this one simple function.

def get_cached(key, expiration=None, miss_fcn=None):
    """
    Fetches a key from the cache. If the key is not found, compute `miss_fcn' and try to store it in the cache before returning it
    :param key: a string
    :param expiration: in seconds
    :param miss_fcn: a function to execute that will fetch the data from the authoritative source if not found in the DB
    """
    if not settings.cache_enabled: # enable when testing cache failure scenarios
        return miss_fcn() if miss_fcn else None

    t0 = time.time()
    try:
        result = cache.get(key)
        if result is not None:
            statsd.increment('cache.hit', sample_rate=0.5)
            statsd.timing('cache.hit.perf', time.time() - t0, sample_rate=0.2)
            return result
        else:
            statsd.increment('cache.miss', sample_rate=0.5)
    except Exception:
        logger.error("Error fetching key %s from cache", key, exc_info=True)

    # key not found or error, try to set
    # Note: Leave this outside the try/catch and let the caller handle the error
    if miss_fcn is not None:
        val = miss_fcn()
        try:
            if expiration is not None and val is not None:
                cache.set(key, val, expiration)
            elif val is not None:
                cache.set(key, val)
        except Exception:
            logger.error('Error setting key %s in cache', key, exc_info=True)

        statsd.timing('cache.miss.perf', time.time() - t0, sample_rate=0.2)
        return val
    else:
        return None

One potential optimization that comes to mind above is to avoid setting the value right there and instead queue an async task to update the cache and return the results to the user ASAP. Another is to put a Redis monitor around the value to avoid race conditions between processes trying to replace the same key with different values. However, both would introduce additional and unnecessary complexity. Setting a value in Redis takes less than a few milliseconds and by the nature of our product, we don’t have multiple competing writers.

Key Versioning & Management

Key management is an important aspect of a caching system. Remember when I said that we cache entire results instead of small data snippets? What happens if we change the algorithm? Or if we introduce more data? To work around these scenarios, we built versioning right into the key by following a convention in our naming. All keys are stored centrally in a Python dictionary-like structure. Below is a made-up example of what the key management looks like. By keeping it in our codebase we get versioning for free, courtesy of git but it can probably become unwieldy if you have more than 100 or so keys.

KeySpec = namedtuple('KeySpec', ['key', 'deps'])

class CacheKeysFactory(object):
    KEY_SPECS = {'CAMPAIGN_CONTENT': KeySpec(key='campaign_content:v1:{campaign_id}:{content_id}',
                                             deps={'CONTENT', 'IMAGE_METADATA'}),
                 'IMAGE_METADATA': KeySpec(key='image:metadata:v1:{image_id}',
                                           deps={}),
                 'CONTENT': KeySpec(key='content:v3:{content_id}:notification:subscribers',
                                    deps={'CONTENT_CONTRIBUTOR'}),
                 'CONTENT_CONTRIBUTOR': KeySpec(key='content:metadata:v1:{content_id}',
                                                deps={})
                 }

    def __getattr__(self, attr):
        """
        :param attr: case-sensitive lookup string
        :return: a function we can use to get the final value for this key by passing the parameters as if formatting
            a string
        """
        try:
            return self.KEY_SPECS.get(attr).key.format
        except TypeError:
            raise AttributeError(attr)

cache_key_specs = CacheKeysFactory()

Fetching Data

So given all the above, what does fetching data look like? Some pseudocode:

def get_campaign_content(request):
    def _db_fetch_process():
        # execute some DB query and processing
        return results

    CACHE_KEY = cache_key_specs.CAMPAIGN_CONTENT(campaign_id=request.GET['campaign_id'],
                                                 content_id=request.GET['content_id'])
    return get_cached(key=CACHE_KEY,
                      expiration=6*settings.AN_HOUR,
                      miss_fcn=_db_fetch_process)

Cache Invalidation

My father always told me, cache invalidation is hard. Ok, he didn’t say that, but it would be cool if he had. When updating a value, one must remember to invalidate the key after the update. These are the kind of bugs that are usually caught by code review or by disciplined unit testing. We use an extremely crude method here to make catching such bugs early on easier: All functions that modify data persistently are prefixed with update_. In addition, all cache invalidation is wrapped in functions named invalidate_cache_. Therefore, it is expected that right after an update_ method, we see a call to cache invalidation unless called out explicitly.

For unit testing, instead of mocking the cache, we empty out a database in Redis prior to each test and use really long expiration times. The unit test is as simple as fetching the value via the cache, which will force a cache miss and a cache set, updating the value and making sure the cache db is now empty again.

One complication that arises is that we like to cache the results of complex computations. To make sure those computations also get invalidated properly, we compute a DAG right from data kept in the key management dictionary.

Advanced Redis

Some of our subsystems are slightly more advanced and use Redis’ built-in datastructures to make quick decisions. For example, our real-time optimizer keeps certain data in Redis Ordered Sets and Hash Tables and we use HyperLogLog for certain counts. These are use cases specific to Sidelines, however; the only lesson here is that using something as advanced as Redis for simple caching allows for more complicated scenarios without having to introduce yet another piece of infrastructure.

Conclusion

Caching doesn’t have to be hard. If you have a very read-heavy application:

Make sure your data fits in RAM
Spin a VM with lots of memory in some cloud
Exercise caution when it comes to updating data and cache invalidation
Make it easy to test what happens if the cache dies or restarts cold

Interested in building simple solutions to seemingly complex problems? Join us at Sidelines, we are hiring