Download Time Analysis for Distributed Storage Codes with Locality and\n Availability

Mehmet S. Aktaş, Swanand Kadhe, Emina Soljanin, Alex Sprintson

In the world of distributed storage, the "hot data" problem is a constant headache. When thousands of users want the same file simultaneously, a single server becomes a bottleneck. While we usually solve this with replication or erasure coding, a newer class of codes—availability codes—promises a more elegant solution by providing multiple independent ways to reconstruct the same piece of data.

This paper provides the first rigorous mathematical framework for analyzing the download latency of these codes, moving beyond simple storage efficiency to look at how they perform under real-world queuing conditions.

TL;DR

The authors develop analytical techniques to calculate the expected download time for distributed storage systems using availability codes. They demonstrate that while these codes offer a powerful "middle ground" between simple replication and efficient MDS codes, their performance is highly sensitive to system load and the number of servers involved in data recovery.

What Problem Does This Paper Address?

Distributed systems traditionally use Replication (simple but storage-heavy) or Maximum Distance Separable (MDS) codes (storage-efficient but slow to recover data). Locally Recoverable Codes (LRCs) were introduced to make recovery faster by only requiring a small group of servers (a "recovery group") to reconstruct a missing piece of data.

Availability codes take this a step further: they ensure an object has multiple disjoint recovery groups. This means you can download a file from its primary server OR reconstruct it from Group A, Group B, etc., all at the same time.

The challenge is quantifying the download latency. If you send a request to all these groups simultaneously (a "Fork-Join" strategy), the first one to finish wins. However, calculating the expected wait time is mathematically "intractable" because of the complex way queues build up across interdependent servers. This paper seeks to provide the bounds and approximations needed to make these systems predictable.

Methods

The authors analyze the system under two main regimes:

  1. Low-Traffic Regime: Here, they assume only one request is in the system at a time. They use order statistics and the Beta function to derive a clean, closed-form expression for the expected download time.
  2. High-Traffic (Queuing) Regime: This is the "real world" where requests overlap and queues form. Because an exact solution is impossible due to "state space explosion," the authors use:
  3. Restricted Models: They create two simplified versions of the system (FJ-Fixed Arrival and FJ-Split Merge) to establish upper and lower bounds on performance.
  4. M/G/1 Approximation: For the common case where recovery groups consist of two servers (locality $r=2$), they propose an approximation based on standard queuing theory.
  5. Matrix-Analytic Methods: For specific simple codes, they use iterative numerical procedures to find even tighter bounds.

Datasets

As a theoretical paper, it does not use a "training" dataset. Instead, the authors validate their mathematical models using extensive numerical simulations. They model server service times as independent and identically distributed (i.i.d.) exponential random variables, a standard benchmark in queuing theory that reflects the variability found in large-scale data centers.

Key Insights and Ideas

  • The Cost of Locality: The authors show that increasing "locality" ($r$, the number of servers in a recovery group) significantly slows down downloads. This is because a recovery group is only as fast as its slowest member. For large $r$, the mean time scales by $\ln r$.
  • Diminishing Returns of Availability: While adding more recovery groups ($t$) reduces latency, the benefit per group drops off quickly (roughly $1/rt$). There is a "sweet spot" for how much redundancy you should add.
  • The Storage-Latency Tradeoff: Availability codes act as a bridge. They offer better latency than MDS codes but require more storage; they use less storage than 3-way replication but have slightly higher latency.
  • Queue Leveling: A key observation is that in Fork-Join systems, the "leading" servers (those ahead in their queues) eventually get slowed down by the "slow" servers because redundant copies are cancelled once a request is fulfilled. This "loose coupling" is what makes the M/G/1 approximation surprisingly accurate.

Key Results

  • Closed-Form Expression: For low traffic, the expected download time is $E[T] = \frac{1}{\mu r} \beta(t+1, 1/r)$, where $\mu$ is the service rate, $r$ is locality, and $t$ is availability.
  • Performance Comparison: In a head-to-head comparison, a (14, 6, 2, 3)-availability code achieved lower latency than the MDS codes used by Google or the LRCs used by Windows Azure, albeit with higher storage overhead.
  • Approximation Accuracy: The proposed M/G/1 approximation for high-traffic scenarios was shown via simulation to be highly accurate, providing a practical tool for system designers to estimate latency without running massive simulations.

Limitations and Future Work

  • Aggressive Redundancy: The paper focuses on the "Fork-Join" strategy where every request is sent to every possible group. While this minimizes latency for the individual, it adds massive load to the system.
  • Service Time Assumptions: The models assume exponential service times. Future work could explore "heavy-tailed" distributions (like Pareto) which are common in some real-world systems.
  • Selective Redundancy: The authors suggest investigating "state-dependent" strategies—only sending redundant requests when the system load is low—to find a more optimal balance between individual latency and total system throughput.

Summary updated

Abstract

The paper presents techniques for analyzing the expected download time in\ndistributed storage systems that employ systematic availability codes. These\ncodes provide access to hot data through the systematic server containing the\nobject and multiple recovery groups. When a request for an object is received,\nit can be replicated (forked) to the systematic server and all recovery groups.\nWe first consider the low-traffic regime and present the close-form expression\nfor the download time. By comparison across systems with availability, maximum\ndistance separable (MDS), and replication codes, we demonstrate that\navailability codes can reduce download time in some settings but are not always\noptimal. In the high-traffic regime, the system consists of multiple\ninter-dependent Fork-Join queues, making exact analysis intractable.\nAccordingly, we present upper and lower bounds on the download time, and an\nM/G/1 queue approximation for several cases of interest. Via extensive\nnumerical simulations, we evaluate our bounds and demonstrate that the M/G/1\nqueue approximation has a high degree of accuracy.\n
BibTeX
@inproceedings{aktas2015download,
  author = {Mehmet S. Aktaş and Swanand Kadhe and Emina Soljanin and Alex Sprintson},
  title = {{Download Time Analysis for Distributed Storage Codes with Locality and\textbackslash\{\}n Availability}},
  booktitle = {ISIT},
  year = {2015},
  doi = {10.1109/isit.2015.7282699},
}
Figure