Exoskeleton: Fast Cache-enabled Load Balancing for Key-Value Stores
Report ID: TR-991-15Author: Sethi, Raghav
Date: 2015-06-11
Pages: 44
Download Formats: |PDF|
Abstract:
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 e ective 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 speci cally for the limitations imposed by switch hardware. E ective 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.