Time-Continuous Modeling of Zipfian Workload Locality

Traditional workload analysis uses discrete times measured by data accesses, including the subarea of workloads with stochastic and independent accesses. A precise analysis in this flavor is the classic independent reference model (IRM) (King, 1971) where data are treated as independent random variables with stationary access probabilities. Despite the exponential blow-up of the exact solution to IRM (King, 1971), effective approximations have been developed, notably by Dan and Towsley (1990) and by Denning and Schwartz (1972). While these techniques were unrelated in the past, they are of the same species using different discrete steps. This paper presents Cell, a time-continuous model of locality for workloads with stochastic access patterns adhering to IRM. To draw connections between theory and applications, we evaluate our model on the challenging Zipfian workloads, which are ubiquitously found in web requests and caching systems. With trace simulation, we compare the modeling results for the Cell model, as well as for those presented by the formerly mentioned related work. Additionally, we present a partitioning strategy to effectively approximate the locality of a large Zipfian workload with a small number of partitions using the proposed Cell model, further reducing the time of locality analysis for the practical task.