Modeling Online Paging in Multi-Core Systems

Mathieu Mari, Anish Mukherjee, Runtian Ren, Piotr SankowskiarXiv 2024 · OpenReview

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.

The probability distribution of memory requests in a multi-core system, showing the characteristic "flattened" head of the Pareto Type II distribution.

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.

Parameters ($\alpha, \kappa$) and K-S test results for the multi-core power-law model across eight Huawei traces.

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

Abstract

Web requests are growing exponentially since the 90s due to the rapid development of the Internet. This process was further accelerated by the introduction of cloud services. It has been observed statistically that memory or web requests generally follow power-law distribution, Breslau et al. INFOCOM'99. That is, the $i^{\text{th}}$ most popular web page is requested with a probability proportional to $1 / i^{\alpha}$ ($\alpha > 0$ is a constant). Furthermore, this study, which was performed more than 20 years ago, indicated Zipf-like behavior, i.e., that $\alpha \le 1$. Surprisingly, the memory access traces coming from petabyte-size modern cloud systems not only show that $\alpha$ can be bigger than one but also illustrate a shifted power-law distribution -- called Pareto type II or Lomax. These previously not reported phenomenon calls for statistical explanation. Our first contribution is a new statistical {\it multi-core power-law} model indicating that double-power law can be attributed to the presence of multiple cores running many virtual machines in parallel on such systems. We verify experimentally the applicability of this model using the Kolmogorov-Smirnov test (K-S test). The second contribution of this paper is a theoretical analysis indicating why LRU and LFU-based algorithms perform well in practice on data satisfying power-law or multi-core assumptions. We provide an explanation by studying the online paging problem in the stochastic input model, i.e., the input is a random sequence with each request independently drawn from a page set according to a distribution $\pi$. We derive formulas (as a function of the page probabilities in $\pi$) to upper bound their ratio-of-expectations, which help in establishing O(1) performance ratio given the random sequence following power-law and multi-core power-law distributions.
BibTeX
@misc{mari2024modeling,
  author = {Mathieu Mari and Anish Mukherjee and Runtian Ren and Piotr Sankowski},
  title = {{Modeling Online Paging in Multi-Core Systems}},
  year = {2024},
  eprint = {2401.05834},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2401.05834},
}
Figure