I have been thinking quite a bit about how to improve our invalidation
scheme. It occurs to me that the last time I wrote a note about
invalidations was before the OSDI paper. Obviously, quite a bit has
changed since then.

Since the scheme described in the paper is different than what I had
been discussing before (as well as what I am currently planning), it
seems worthwhile to remind everyone exactly what I put in the
paper. And of course it has some limitations that motivate a new
invalidation scheme.

Each entry in the cache that is still valid has a set of associated
invalidation tags. Invalidation tags can take two forms. They can
consist of a table and key-value pair, for queries that do index
equality lookups, e.g. "users:name=alice". For other queries, we need
a wildcard invalidation on the entire table, e.g. "users:*". The idea
is that wildcard invalidations should almost never be necessary. The
database attaches invalidation tags to query results based on the
access methods used.

The database also generates an invalidation for every tag that can be
affected by an update. This is not just one tag invalidation per
tuple, but one per each index on that tuple. These tags get
distributed to all cache servers on commit, ordered by the
transaction's commit time.

(An important but easily-overlooked contribution here is that the
invalidations are tagged with timestamp and distributed as an ordered
stream. The alternatives are fraught with race conditions. Maintaining
this property when we extend the system to replicated databases will
require care.)

You may recall that I once discussed invalidation tags as an arbitrary
hierarchy and the associated rules (invalidating a tag requires
invalidating any object tagged with any parent *or* any child of that
tag). This scheme is a restricted subset of that and follows the same
rules. I merely omitted the discussion of the hierarchy since we only
had two levels; the wildcard presentation was easier to follow.

I put this together as a quick hack so that we could get some decent
benchmark results for the paper. Indeed, it worked: invalidations are
a crucial part of performance -- they are largely responsible for
improving our bottom-line result from a 77% speedup to a 5x one
between drafts of the paper.

Nevertheless, it has several shortcomings that I would like to
address:

  - it really supports only index-equality queries. Anything else has
    to be promoted to a table-granularity tag, which is pretty awful
    for performance. In particular, that includes index-range queries,
    which some applications use quite extensively; we'd like to
    support these.

  - it generates an invalidation for any tag that could be affected by
    an update, even if no data with that tag has ever been in the
    cache. As an extreme example, a write-only workload will generate
    lots of invalidations, none useful. The database ought not to
    generate invalidations for data that has not been queried since
    its last invalidation.

  - it distributes all invalidations to all cache nodes, even if only
    one contains an object that needs to be invalidated. Processing
    those invalidations can be expensive. This fact evoked a wide-eyed
    look of horror in someone from Facebook at OSDI. It would be nice
    if we could selectively target invalidations. (I do not have a
    good answer as to how to do this, though!)

In the next installment of this series, I'll try to actually solve
these problems.