A Survey of Miss-Ratio Curve Construction Techniques <s> TAXONOMY <s> Key-value stores are a vital component in many scale-out enterprises, including social networks, online retail, and risk analysis. Accordingly, they are receiving increased attention from the research community in an effort to improve their performance, scalability, reliability, cost, and power consumption. To be effective, such efforts require a detailed understanding of realistic key-value workloads. And yet little is known about these workloads outside of the companies that operate them. This paper aims to address this gap. To this end, we have collected detailed traces from Facebook's Memcached deployment, arguably the world's largest. The traces capture over 284 billion requests from five different Memcached use cases over several days. We analyze the workloads from multiple angles, including: request composition, size, and rate; cache efficacy; temporal patterns; and application use cases. We also propose a simple model of the most representative trace to enable the generation of more realistic synthetic workloads by the community. Our analysis details many characteristics of the caching workload. It also reveals a number of surprises: a GET/SET ratio of 30:1 that is higher than assumed in the literature; some applications of Memcached behave more like persistent storage than a cache; strong locality metrics, such as keys accessed many millions of times a day, do not always suffice for a high hit rate; and there is still room for efficiency and hit rate improvements in Memcached's implementation. Toward the last point, we make several suggestions that address the exposed deficiencies. <s> BIB001 </s> A Survey of Miss-Ratio Curve Construction Techniques <s> TAXONOMY <s> Memcached is a popular component of modern Web architectures, which allows fast response times - a fundamental performance index for measuring the Quality of Experience of end-users - for serving popular objects. In this work, we study how memory partitioning in Memcached works and how it affects system performance in terms of hit rate. Memcached divides the memory into different classes proportionally to the percentage of requests for objects of different sizes. Once all the available memory has been allocated, reallocation is not possible or limited, a problem called “calcification”. Calcification constitutes a symptom indicating that current memory partitioning mechanisms require a more careful design. Using an experimental approach, we show the negative impact of calcification on an important performance metric, the hit rate. We then proceed to design and implement a new memory partitioning scheme, called PSA, which replaces that of vanilla Memcached. With PSA, Memcached achieves a higher hit rate than what is obtained with the default memory partitioning mechanism, even in the absence of calcification. Moreover, we show that PSA is capable of “adapting” to the dynamics of clients' requests and object size distributions, thus defeating the calcification problem. <s> BIB002
In this section we present a taxonomy of the current miss-ratio curve construction techniques based on which metric is recorded, how the data is stored, and the derivation method of the miss-ratio curve. Cache Size (number of objects) Hit Rate etc psa Hit Rate vs. Cache Size Figure 1 : Hit Ratio Curve for two common synthetic web application workloads. ETC models the Facebook workload from BIB001 . It contains 50 million accesses (GETs) to 7 million unique objects. PSA is the D'Carra workload from BIB002 , it contains 50 million accesses to 7 million unique objects following an Pareto distribution.