Abstract
Web requests have grown exponentially since the 1990s, a trend accelerated by the rise of cloud services. Historically, these requests were thought to follow a Zipf-like power-law distribution ($\alpha \le 1$). However, modern petabyte-scale cloud systems exhibit a shifted power-law distribution (Pareto Type II or Lomax) with $\alpha > 1$. This paper introduces a new statistical multi-core power-law model to explain this phenomenon, attributing it to the parallel execution of multiple virtual machines. We verify this model using the Kolmogorov-Smirnov (K-S) test and provide a theoretical analysis demonstrating that LRU and LFU-based algorithms achieve $O(1)$ performance ratios under these stochastic distributions.
Introduction
For decades, web caching strategies have relied on the "Golden Rule" of the Zipf distribution: a small number of items account for the vast majority of requests. Traditional worst-case competitive analysis often suggests that common algorithms like Least-Recently-Used (LRU) perform poorly, with a competitive ratio proportional to the cache size $k$. This creates a significant gap between theoretical predictions and practical performance.
Modern cloud environments have further complicated this landscape. Systems running hundreds of virtual machines (VMs) in parallel no longer adhere to simple Zipf laws. Instead, they display a "flattened" head in their request distributions and exponents where $\alpha > 1$. This paper addresses both the statistical shift in modern workloads and the theoretical justification for why standard caching algorithms remain highly effective in these environments.
Statistical Modeling of Multi-Core Workloads
The authors propose that the observed Pareto Type II distribution is a natural consequence of $\kappa$ independent cores or VMs interleaving their request streams into a shared cache. In a single-core system, the most popular page dominates. However, in a multi-core system, the competition between independent processes effectively caps the maximum probability of any single page being requested at a given time step.
This "flattening" effect transforms the standard power law into a shifted power law. The researchers validated this model using real-world memory access traces from Huawei’s Dorado storage systems, which manage petabytes of data and support over 500 concurrent VMs.
Theoretical Analysis: Beyond Worst-Case
To bridge the theoretical gap, the study moves away from worst-case competitive analysis toward the Ratio-of-Expectations (RoE) metric. RoE compares the expected cost of an online algorithm to that of an optimal offline solver (OPT) over a random sequence of requests drawn from a distribution $\pi$.
The analysis utilizes a phase-based approach:
- LRU: Analyzed using standard marking phases.
- LFU: Evaluated via a novel phase definition that categorizes pages as "big" or "small" to bound expected page faults.
The core theoretical contribution is the proof that for any sequence following a power-law or multi-core power-law distribution, both LRU and "Perfect LFU" (PLFU) achieve a constant $O(1)$ RoE. This explains why these algorithms maintain high performance even as system scale and request volume grow.
Experimental Results
The multi-core power-law model was tested against traditional models using the Kolmogorov-Smirnov (K-S) test. The results demonstrate a significantly better fit for modern cloud traces. For instance, in Trace 2, the K-S error dropped from 0.121 under the traditional model to 0.053 under the multi-core model.
Furthermore, the data confirmed that the power-law exponent $\alpha$ in modern systems often exceeds 1, reaching values as high as 1.5. This contradicts older assumptions of $\alpha \le 1$ and highlights the necessity of updated statistical models for system design.
Conclusion
This work provides a robust statistical and theoretical foundation for understanding paging in modern multi-core cloud systems. By identifying the multi-core power-law distribution and proving the $O(1)$ performance of LRU and LFU under these conditions, the authors align theoretical analysis with empirical reality. Future research will explore extending these models to account for temporal locality via Markov paging models and investigating the role of prefetching in highly virtualized environments.
Summary updated