Volume lease: a scalable cache consistency framework

In this thesis, we study scalable cache consistency. Caching remotely deployed services near users can reduce network overhead, shorten user response time, increase availability, and improve scalability. The effectiveness of caching, however, is determined to a great extent by the efficiency of cache consistency protocols. Given that many services of importance are accessed by thousands or millions of clients, scalable cache consistency is essential to realize the full potential of caching. We propose a general framework, Volume Lease, for scalable cache consistency design. Our framework allows us to decouple synchronization from invalidation. Synchronization in our framework is performed on sets of objects called volumes, which allows the cost of synchronization to be amortized over many objects in a volume. This framework captures the essential mechanism for high-performance scalable cache consistency design and is still flexible enough to allow us to explore a wide design space. With this framework, we are able to design various consistency protocols to provide a wide spectrum of consistency guarantees in a wide range of environments. In particular, we examine various mechanisms provided by Volume Lease to address challenges of scalable cache consistency: interactivity, flexibility, scalability, and robustness. We evaluate our consistency protocols experimentally with both trace-driven simulation. Our results show that our consistency protocols can scale to millions of machines, handle common failures gracefully, allow systems to exploit weak consistency requirements to reduce overhead, and provide close to optimal latency.