Quick links

Exoskeleton: Fast Cache-enabled Load Balancing for Key-Value Stores

Report ID:
June 11, 2015
Download Formats:


Key-value stores are a fundamental building block for many large web-scale applica-
tions. These applications typically face highly-skewed trac, i.e. the most popular
keys are requested many orders of magnitude more frequently than the median key.
Schemes that simply balance storage capacity across a cluster are therefore unable
to adequately balance trac load across cluster nodes. Dynamic load-balancing is
therefore critical to maintaining service-level objectives, and necessitates expensive
over-provisioning if it is imperfect or slow to deal with rapidly changing trac
distributions. An eective technique to provide load-balancing is to use popularity
based caching. However, existing cache architectures have limitations - querying the
cache before querying the persistent store requires a round-trip to the cache for every
request, and putting a cache on the data path limits the throughput of the system
to that of the cache.
Exoskeleton is a cache architecture which enables the routing of requests for pop-
ular keys directly to cache nodes at line-rate. This architecture leverages the power
and speed of programmable switches to perform content-aware routing. Clients do
not need to maintain any state to take advantage of this architecture, and simply
encode key information directly into request packet headers. Exoskeleton removes
the constraints of previous architectures, which required operators to optimize for
either low latency or scalability, but not both. In addition, Exoskeleton deals with
rapidly-changing workloads through a cache update mechanism designed specically
for the limitations imposed by switch hardware. Eective load-balancing enables this
system to eciently deal with modern web workloads using a heterogeneous clus-
ter architecture comprising cheap SSD-based backend nodes and a small number of
powerful cache nodes.

Follow us: Facebook Twitter Linkedin