  One of the most popular setups for a back-end of a high performance website
consists of a relational database and a cache which stores results of performed
queries. Several application frameworks support caching of queries made to the
database, but few of them handle cache invalidation correctly, resorting to
simpler solutions such as short TTL values, or flushing the whole cache after
any write to the database. In this paper a simple, correct, efficient and
tested in real world application solution is presented, which allows for
infinite TTL, and very fine grained cache invalidation. Algorithm is proven to
be correct in a concurrent environment, both theoretically and in practice.

Databases