Today’s data-intensive clouds are increasingly bottlenecked on the data I/O. Cluster caching systems come as a popular solution that substantially improves the I/O performance. By deploying a cluster of cache servers in front of the disk-based storage, I/O-intensive applications can access data at memory speed, leading to order-of-magnitude performance improvement. Despite the popularity of cluster caching systems, memory caches remain a highly constrained resource and are intensely contended among multiple applications/users. Therefore, achieving efficient cache utilization and fair cache sharing among individual users have become a pressing need in cluster caching systems. Specifically, there are three fundamental challenges that should be judiciously addressed, i.e., what da...[ Read more ]

Today’s data-intensive clouds are increasingly bottlenecked on the data I/O. Cluster caching systems come as a popular solution that substantially improves the I/O performance. By deploying a cluster of cache servers in front of the disk-based storage, I/O-intensive applications can access data at memory speed, leading to order-of-magnitude performance improvement. Despite the popularity of cluster caching systems, memory caches remain a highly constrained resource and are intensely contended among multiple applications/users. Therefore, achieving efficient cache utilization and fair cache sharing among individual users have become a pressing need in cluster caching systems. Specifically, there are three fundamental challenges that should be judiciously addressed, i.e., what data to cache (efficient replacement), how to allocate the cache among users (fair allocation), and how to load-balance the cache servers (placement).

However, the prior art does not provide satisfactory solutions to all the three challenges. First, traditional cache replacement policies simply make the caching decisions based on data access history but keep agnostic to the readily available future data access pattern in cloud datacenters, which is usually inefficient and even erroneous. Second, the existing cache allocation schemes provide no fair sharing among users but rather remain vulnerable to the constant free-riding cheating. The free-riding issue is a unique challenge in the cache allocation, as memory caches are non-exclusively shared among user. Third, load balancing across cache servers is profoundly difficult in the presence of skewed file popularities, i.e., a small number of files account for the majority of data access. Existing load balancing techniques either incur significant cache redundancy or require high computational overhead of data encoding/decoding. The result is excessive I/O latency that can even eliminate the benefits of cluster caching.

To address the above three unique challenges, we design, analyze, and build new caching strategies that achieve efficient, fair and load-balanced cluster caching.

First, we propose a novel cache replacement policy, termed Least Reference Count (LRC), which optimizes the cache efficiency by exploiting the data dependency information of the cluster caching systems. Prevalent data analytics engines running atop the cluster caching systems, e.g., Spark and Piccolo, can provide rich runtime semantics of data dependency in the form of directed acyclic graphs (DAGs). LRC takes advantage of the DAG information to obtain the reference count of each data block and always evicts the block with the smallest reference count. Compared with traditional cache replacement strategies that purely rely on data access history, LRC significantly improves the cache hit ratio and computation throughput.

Second, we propose Opportunistic Sharing (OpuS), a cache allocation algorithm that achieves fair cache sharing for multiple users. At the core of OpuS lies a two-stage cache allocation scheme built atop the classic Vickrey-Clarke-Groves (VCG) auction mechanism. We prove that OpuS provides fair cache sharing among users and prevents any kind of untruthful behavior including the “free-riding” manipulation.

Third, we propose an effective approach to achieve load balancing among distributed cache servers without any extra cache redundancy or computation overhead. Our solution, termed SP-Cache, selectively partitions files based on the loads they contribute and evenly caches those partitions across the caching cluster. We develop an efficient algorithm to determine the optimal number of partitions for a hot file—too few partitions are incapable of balancing the loads, while too many are susceptible to stragglers. SP-Cache can quickly react to the changing load by dynamically re-balancing cache servers.