Person:

Kate, Bryan

This thesis presents the design of Pequod, a distributed, application-level Web cache. Web developers store data in application-level caches to avoid expensive operations on persistent storage. While useful for reducing the latency of data access, an application-level cache adds complexity to the application. The developer is responsible for keeping the cached data consistent with persistent storage. This consistency task can be difficult and costly, especially when the cached data represent the derived output of a computation.

Pequod improves on the state-of-the-art by introducing an abstraction, the cache join, that caches derived data without requiring extensive consistency-related application maintenance. Cache joins provide a mechanism for filtering, joining, and aggregating cached data. Pequod assumes the responsibility for maintaining cache freshness by automatically applying updates to derived data as inputs change over time.

This thesis describes how cache joins are defined using a declarative syntax to overlay a relational data model on a key-value store, how cache data are generated on demand and kept fresh with a combination of eager and lazy incremental updates, how Pequod uses the memory and computational resources of multiple machines to grow the cache, and how the correctness of derived data is maintained in the face of eviction.

We show through experimentation that cache joins can be used to improve the performance of Web applications that cache derived data. We find that moving computation and maintenance tasks into the cache, where they can often be performed more efficiently, accounts for the majority of the improvement.