USENIX Technical Program - Abstract - Internet Technologies & Systems 99
Hierarchical Cache Consistency in a WAN
Jian Yin, Lorenzo Alvisi, Mike Dahlin, and Calvin Lin, University of Texas at Austin
Abstract
This paper explores ways to provide improved consistency for
Internet applications that scale to millions of clients. We make four
contributions. First, we identify how workloads affect the scalability
of cache consistency algorithms. Second, we define two primitive
mechanisms, split and join, for growing and shrinking consistency
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 tolerance and performance challenges of consistency hierarchies.
Fourth, using synthetic workload and trace-based simulation, we
compare various algorithms for maintaining strong consistency in a
range of hierarchy configurations. 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. Specifically, by
adapting to clients' access patterns, two-level hierarchies reduce the
read latency for demanding workloads without introducing excessive
overhead for
nondemanding 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.
|