Load Balancing and Hot Spot Relief for Hash Routing among a Collection of Proxy Caches

This paper studies an Adaptable Controlled Replication (ACR) approach to load balancing and hot spot relief for a collection of loosely-coupled proxy caches coordinated by a hash routing protocol, such as CARP. Hash routing partitions the entire URL space among the proxy caches, creating a single logical cache. Each partition is assigned to a cache server. Client requests to a cache server for non-assigned-partition objects are forwarded to sibling caches. Duplication of cache contents is eliminated. However, in the presence of access skew, the load levels of the cache servers can be unbalanced, limiting the benefits of hash routing. We propose an adaptable controlled replication of non-assigned-partition objects in each cache server to reduce the possibility of repeatedly forwarding hot-spot requests to the same server. As a result, cpu utilizations among the cache servers are more balanced and the problem of hot-spot references can be relieved. Trace-driven simulations are conducted to study the effectiveness of ACR. The results show the (1) access skew exists, and the load of the cache servers tends to be unbalances in hash routing; (2) with a relatively small amount of ACR, such as 10% of the cache size, significant improvements in load balance can be achieved without a noticeable degradation in caching effectiveness; (3) ACR provides a very effective remedy for load imbalances due to hot spot references; and (4) increasing the cache size down not improve load balance unless replication is allowed.