Hierarchical Cache Consistency in a WAN

This paper explores ways to provide improved consis-tency for Internet applications that scale to millions of clients. We make four contributions. First, we iden-tify how workloads affect the scalability of cache consis-tency algorithms. Second, we define two primitive mech-anisms, split and join, for growing and shrinking consis-tency hierarchies, and we present a simple mechanism for implementing them. Third, we describe and evaluate policies for using split and join to address the fault toler-ance and performance challenges of consistency hierar-chies. Fourth, using synthetic workload and trace-based simulation, we compare various algorithms for maintain-ing strong consistency in a range of hierarchy configura-tions. Our results indicate that a promising configuration for providing strong consistency in a WAN is a two-level consistency hierarchy where servers and proxies work to maintain consistency for data cached at clients. Specif-ically, by adapting to clients ’ access patterns, two-level hierarchies reduce the read latency for demanding work-loads without introducing excessive overhead for nonde-manding workloads. Also, they can improve scalability by orders of magnitude. Furthermore, this configuration is easy to deploy by augmenting proxies, and it allows invalidation messages to traverse firewalls.