PaperlayerView exact revision on arXiv

Source-linked AI summary

DistCache: Provable Load Balancing for Large-Scale Storage Systems with Distributed Caching

Zaoxing Liu, Zhihao Bai, Zhenming Liu, Xiaozhou Li, Changhoon Kim, Vladimir Braverman, Xin Jin, Ion Stoica

arXiv:1901.08200v2cs.DCcs.NI

TL;DR

Large-scale storage must maintain strict SLOs despite skewed workloads, but cache-based load balancing becomes a bottleneck when scaling across clusters. DistCache combines multilayer cache allocation using independent hashes with power-of-two-choices routing, and demonstrates provable load balancing and linear scale-out in switch-based caching.

  • Problem

    Skewed workloads create storage hot spots, while existing cache partitioning or replication cannot scale across clusters without cache-node imbalance or high coherence overhead.

  • Method

    DistCache co-designs multilayer cache topology and allocation with independent hash functions, then routes queries online using the power-of-two-choices.

  • Results

    DistCache provides provable load balancing and demonstrates linear scale-out with minimal cache-coherence overhead in a switch-based caching prototype.

  • Takeaways & Limitations

    DistCache provides a general “one big cache” abstraction applicable to large-scale storage systems and emerging switch-based caching.

  • Takeaways & Limitations

    The analysis assumes each hot object’s query rate is no larger than eT/2, and network partition handling requires choosing consistency or availability.

Abstract

from arXiv · show

Load balancing is critical for distributed storage to meet strict service-level objectives (SLOs). It has been shown that a fast cache can guarantee load balancing for a clustered storage system. However, when the system scales out to multiple clusters, the fast cache itself would become the bottleneck. Traditional mechanisms like cache partition and cache replication either result in load imbalance between cache nodes or have high overhead for cache coherence. We present DistCache, a new distributed caching mechanism that provides provable load balancing for large-scale storage systems. DistCache co-designs cache allocation with cache topology and query routing. The key idea is to partition the hot objects with independent hash functions between cache nodes in different layers, and to adaptively route queries with the power-of-two-choices. We prove that DistCache enables the cache throughput to increase linearly with the number of cache nodes, by unifying techniques from expander graphs, network flows, and queuing theory. DistCache is a general solution that can be applied to many storage systems. We demonstrate the benefits of DistCache by providing the design, implementation, and evaluation of the use case for emerging switch-based caching.

1 Introduction

Large-scale storage systems face hot spots and tail-latency problems under skewed workloads, while existing cache-based balancing does not scale cleanly across clusters. DistCache addresses this with layered cache allocation, adaptive routing, and a concrete switch-based implementation.

  • Skewed workloads overload some storage nodes, creating hot spots, low throughput, and long tail latencies that threaten strict SLOs.
  • Existing clustered caching approaches cannot scale across multiple clusters because a single additional cache node becomes an inter-cluster throughput bottleneck.
  • DistCache creates a “one big cache” by co-designing multilayer topology, cache allocation, and query routing.
  • Independent hash functions distribute hot objects across layers, while power-of-two-choices routes each query adaptively to a less-loaded cache node.
  • The distributed routing solution avoids centralized coordination, is online, and is shown asymptotically optimal using queuing theory.
  • A prototype using Barefoot Tofino switches, commodity servers, and Redis demonstrates linear scale-out with minimal cache-coherence overhead.

2 Background and Motivation

Caching can balance clustered storage under highly skewed workloads, but scaling to many clusters creates an upper-layer cache-allocation problem. DistCache’s layered hashing and adaptive routing target the trade-off between cache-node balance and coherence overhead.

  • Small, Fast Cache for Load Balancing: Highly skewed workloads make proportional scaling difficult; about 60-90% of Memcached queries target the hottest 10% of objects.
  • Small, Fast Cache for Load Balancing: Caching the hottest O(nlogn) objects can guarantee balanced load across n storage nodes despite query distribution and total object count.
  • Small, Fast Cache for Load Balancing: A cache node with throughput eT = c · T can support at most c storage nodes, limiting existing solutions such as NetCache to one cluster.
  • Scaling out Distributed Storage: Across many clusters, one upper-layer cache node cannot meet the aggregate requirement of meT for m clusters, motivating multiple upper-layer cache nodes.
  • Scaling out Distributed Storage: Cache partition limits coherence updates but can imbalance cache-node load, whereas replication balances load while imposing high coherence overhead.
  • Scaling out Distributed Storage: DistCache uses independent hash functions across layers and power-of-two-choices routing to balance cache nodes while caching each object at most once per layer.

3 DistCache Caching Mechanism Design

DistCache combines layered cache allocation with distributed query routing to balance workloads across multiple clusters. Its analysis models cache service as a matching problem and proves near-linear supported throughput under broad query distributions.

  • Cache allocation: Independent hash functions partition hot objects across cache nodes in different layers, while lower and upper layers handle intra- and inter-cluster balancing.Each object is cached at most once per layer, limiting coherence overhead.
  • Query routing: The power-of-two-choices routes each query to the less-loaded cache node among those storing the queried object, without centralized coordination.Senders inspect only the relevant cache-node loads, enabling an online distributed solution.
  • Cache size and hierarchy: For m clusters, the lower layer caches O(ml logl) objects and the upper layer caches O(mlogm) objects for hierarchical load balancing.The mechanism can be applied recursively, using power-of-k-choices for k layers while trading additional cache nodes for reduced cache size.
  • Provable analysis: When k = O(mlogm), the cache nodes can absorb all queries to the hottest objects despite query distribution, providing performance guarantees across multiple clusters.The result follows from combining the cache-size bound with the two-layer throughput analysis.
  • Provable analysis: The cache-analysis problem becomes a bipartite perfect-matching problem in which object query rates are assigned across neighboring cache nodes without exceeding node throughput.The matching graph connects each object to the cache nodes selected by the independent hash functions.
  • Provable analysis: If k and m are polynomial-related and each hot object contributes at most eT/2, DistCache supports R = (1 −ε)α · meT for any query distribution with high probability.The power-of-two-choices process is stationary whenever a perfect matching exists, yielding the stated throughput guarantee.

4 DistCache for Switch-Based Caching

DistCache applies distributed caching to switch-based storage by combining cache partitioning, load-aware query routing, and decentralized coherence. Its design serves cache hits directly while forwarding misses and writes to storage servers without routing detours.

  • System scope: DistCache extends switch-based caching from one rack to cloud-scale key-value stores spanning many racks.The design targets emerging switch-based caching and uses a two-layer leaf-spine datacenter network.
  • Control plane: The controller computes cache partitions and updates them during reconfiguration, while remaining outside the query-handling data path.It is responsible for allocation rather than processing storage queries.
  • Query handling: Cache hits are answered directly by cache switches, whereas cache misses and writes are forwarded to the corresponding storage servers without routing detours.The example routes Get(A) between two cache switches; a miss proceeds to the server storing A.
  • Query routing: Client ToR switches use the power-of-two-choices to select the less-loaded cache switch containing the queried object.They compare cache-switch loads and then use existing routing mechanisms to forward the query.
  • Load telemetry: Cache-load telemetry piggybacks the total packet count from the last second in reply headers, while aging is available for stale load information but was not implemented in the prototype.The aging mechanism gradually decreases an outdated load to zero.
  • Cache coherence: A two-phase update protocol preserves cache coherence by invalidating all cached copies before updating them.Storage servers resend invalidation packets after a timeout if the invalidation does not return successfully.

5 Implementation

The prototype realizes DistCache with programmable Barefoot Tofino switches, commodity servers, and Redis integration. Its components implement caching, telemetry, routing, partition management, coherence, and workload generation.

  • Prototype: DistCache’s prototype includes cache switches, client ToR switches, a controller, storage servers, and clients.The implementation covers the full distributed switch-based caching system.
  • Cache switches: Cache-switch data-plane logic is written in P4 and compiled for programmable switch forwarding pipelines.The prototype uses P4 match-action tables on Protocol Independent Switch Architecture devices.
  • Cache switches: The prototype stores cache-switch load in a 32-bit telemetry register and uses Python agents with Thrift to manage cache partitions.Heavy-hitter detection and telemetry counters are reset every second.
  • Client ToR switches: Client ToR routing uses a P4 register array with 256 32-bit slots to store cache-switch loads and selects the least-loaded path.The routing module uses standard L3 routing and resembles CONGA and HULA.
  • Software integration: Python controller software computes partitions, storage-server shims implement coherence with hiredis and Redis, and the client library generates varied workloads.The workload generator supports different query distributions and write ratios.

6 Evaluation

The evaluation uses an emulated two-layer leaf-spine testbed to compare DistCache with alternative caching mechanisms under uniform, skewed, read-only, and write workloads. Results cover throughput, failure recovery, and switch resource usage.

  • 6.1 Methodology: The testbed emulates a datacenter with a two-layer leaf-spine network by dividing switches and servers into multiple logical partitions.The setup uses two Barefoot Tofino switches and two server machines, with physical resources emulating multiple virtual switches.
  • 6.1 Methodology: The evaluation compares DistCache, CacheReplication, CachePartition, and NoCache under uniform and Zipf-skewed workloads.Experiments vary workload skew, cache size, system scale, and write ratio.
  • 6.2 Performance for Read-Only Workloads: Under skewed read-only workloads, DistCache provides comparable throughput to CacheReplication while outperforming NoCache and CachePartition under load imbalance.CacheReplication provides optimal read-only throughput, whereas CachePartition remains limited by imbalance between cache switches.
  • 6.2 Performance for Read-Only Workloads: With larger caches, DistCache and CacheReplication gain substantial throughput improvements, while CachePartition improves only slightly because some spine switches become overloaded.The DistCache and CacheReplication curves flatten after reaching saturated throughput.
  • 6.3 Cache Coherence: As the write ratio increases, DistCache throughput decreases slowly, whereas CacheReplication degrades quickly because writes update all spine switches.DistCache caches each object once per layer, reducing cache-coherence overhead; all caching mechanisms eventually fall below NoCache as server resources are consumed.
  • 6.4 Failure Handling: After four of 32 spine switches fail, throughput drops to about 87.5% and recovery redistributes their partitions to surviving switches.With sending rate limited to half of maximum throughput, recovery raises throughput back to the original level before the failed switches return online.
  • 6.5 Hardware Resources: Adding DistCache caching requires only a small amount of switch resources compared with the fully functional baseline Switch.p4.The evaluation measures resource usage for spine switches, client-rack leaf switches, and storage-rack leaf switches.

7 Related Work

Related work addresses distributed storage, load balancing, and in-network computing. DistCache extends caching-based load balancing with distributed cache allocation and routing across large-scale systems.

  • Distributed storage: Prior distributed-storage work explores DRAM migration, hardware solutions, and software optimizations, while DistCache focuses on balancing the entire system across nodes.These single-node techniques are described as orthogonal to DistCache.
  • Load balancing: Replication, selective replication, data migration, and erasure coding address load balancing with storage, routing, consistency, or object-splitting trade-offs.DistCache pushes this line of work toward distributed caching for large-scale storage systems.
  • In-network computing: In-network computing research uses programmable devices for caching, consensus, and transaction control, but IncBricks does not focus on load balancing.DistCache applies programmable switches to distributed-cache load balancing.

8 Conclusion

The paper presents DistCache as a distributed caching mechanism for large-scale storage systems. It combines independent-hash cache allocation with power-of-two-choices routing and demonstrates the design through switch-based caching.

  • 8 Conclusion: DistCache uses independent hash functions for cache allocation and power-of-two-choices query routing to create a “one big cache” abstraction.The abstraction combines multiple cache nodes into an ensemble acting as a single ultra-fast cache.
  • 8 Conclusion: The paper shows that combining these techniques provides provable load balancing across various scenarios.The demonstrated use case is emerging switch-based caching.

A Analysis of our algorithm

This section provides formal proofs for the lemmas and theorem presented in Section 3. It therefore documents the paper’s analysis rather than introducing a new evaluation result.

  • A Analysis of our algorithm: The appendix section supplies formal proofs for the lemmas and theorem presented in Section 3.Its stated role is to provide the proof details for the algorithm’s earlier analysis.

A.1 Recap of our models and comparison

The model routes requests for hashed objects across two cache-node layers using power-of-two choices, and analyzes the resulting process as a flow problem. Unlike standard balls-and-bins models, repeated requests for an object reuse its hash functions, making power-of-two choices essential for stationarity.

  • 2m cache nodes are organized into two collections, A and B, while k objects arrive at rates p_i and each cache node processes at rate eT.
  • Edges connect each object to one cache node in each layer according to independent hash functions h0 and h1.The graph is defined by E = {{o_i,a_j0} | h0(i)=j0} ∪ {{o_i,b_j1} | h1(i)=j1}.
  • Comparison to the balls-and-bins model: This differs from balls-and-bins power-of-two choices because queries to the same object reuse hash functions rather than sampling fresh nodes.
  • Comparison to the balls-and-bins model: With constant probability uniform routing is non-stationary, whereas PoT is stationary with o(1) probability of non-stationarity.
  • The analysis interprets objects as supply nodes, cache nodes as sink nodes, and each handled request as one unit of flow.
  • The PoT policy locally routes queries according to cache loads without central coordination or prior knowledge of the optimal split.

A.2 Feasible flows/matching exists

The analysis establishes load feasibility by finding a capacity-respecting flow, then showing that PoT implements such a flow locally. Under bounded per-object load and polynomially related system dimensions, a high-probability perfect matching exists.

  • A perfect matching assigns each object’s demand across neighboring cache nodes while keeping every cache-node load at most eT.The weight constraints require each object to receive p_i·R total capacity and each cache node to receive at most eT.
  • If k ≤ m^β and max_i(p_i)·R ≤ eT/2, a perfect matching exists for R = (1−ε)^α·m eT with high probability.
  • Random expansion graphs and primal-dual flow arguments provide the lower bound on the optimal feasible flow size.

A.2.1 Step 1a: when k = αm and pi’s are uniform

For the uniform-rate case k = αm, the proof shows that the random bipartite cache graph expands with high probability, which yields a perfect matching and therefore feasible service.

  • When k = αm and request rates are uniform, the construction sets R = (1−ε)αm eT and assigns each object rate (1−ε)eT.
  • Hall’s theorem converts the expansion property of the unweighted bipartite graph into a perfect matching.
  • The proof bounds the probability of failed expansion by analyzing repeated right-side endpoints for large object subsets and split neighborhoods for small subsets.
  • With high probability, the graph has a perfect matching under the uniform-rate construction.

A.2.2 Step 1b. Generalization

The generalization reduces heterogeneous object counts and request rates to uniform graph-family building blocks. Coupling, scaling, rate rounding, and decomposition preserve feasible matchings and yield high-probability feasibility for broader systems.

  • (α,γ,t)-graph families provide scalable building blocks with uniform object rates, controlled total rate, and cache capacity t.
  • For ρ ∈ [1,2], (ρα,α,t)-graph families are feasible with probability 1−2/m^0.7, and the result extends to all ρ ≥ 1.
  • Coupling and scaling: Coupling merges or splits cache nodes and ties hash functions so that a perfect matching in the transformed graph implies one in the original graph.
  • General heterogeneous rates: The heterogeneous-rate case rounds rates upward geometrically, then decomposes the instance into subproblems with homogeneous rates.
  • General heterogeneous rates: If every matching subproblem has a perfect matching, the original problem does too; a union bound gives high-probability feasibility for the full graph.

A.3 Feasible flows imply PoT is stationary (Proof of Lemma 2 in the paper)

The proof shows that a perfect matching lets the power-of-two-choices cache process satisfy the conditions for stationarity. It establishes this by modeling arrivals, bounding traffic intensity, and applying the Markov-process criterion.

  • A perfect matching in the cache-object bipartite graph implies that the power-of-two-choices process is stationary.
  • The system is modeled as Poisson arrivals joining the shortest queue among an associated subset of cache nodes, with random tie-breaking.The construction uses exponential random variables with cache-node rates eT_i.
  • If the maximum traffic intensity ρmax is below one, the corresponding Markov process is positive recurrent and has a stationary distribution.
  • The proof derives ρmax < 1 by selecting the largest object set whose cache-node neighborhood lies within an arbitrary node subset and applying the perfect-matching flow bound.The bound is ∑i∈J p_iR ≤ (1−ε)|Γ(J)|eT.
  • The resulting theorem guarantees stationarity for R = (1−ε)α·meT under polynomially related k and m, with high probability for sufficiently large m.It also assumes maxi(p_i)·R ≤ eT/2 and holds for any P.
Loading 1901.08200v2…