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.
Post a Comment