LICENSE

Abstract

Development of efficient caching systems is an important problem with the ubiquitous connectivity in the modern day. Most research in the field of web caching have approached the problem from improving the performance of the system through sophisticated eviction policies. However, there have been recent research that introduced the idea of admission policies that have shown to be effective in improving the performance of the underlying base eviction policies.

We provide a new algorithm for applying Bloom filters on caching algorithms named insert-on-second-hit which showed miss ratio improvement for most algorithms on the traces tested, including 6% to 10% additional byte miss ratio improvement on LRU for the Wikipedia trace compared to an existing algorithm. We find that sizing the Bloom filter can be optimized for the miss ratio; the optimal parameterization provides 1.3x to 5x traffic reduction compared to an infinite Bloom filter on LRU for a trace from Wikipedia’s CDN. We also find that Bloom filter’s effectiveness is not limited to LRU and byte miss ratio and extends to most classical and research algorithms across cache sizes. In addition to the analysis of Bloom filter, we introduce a simpler version of AdaptSize that simply leverages the percentile of sizes given a sliding window that showed comparable results for small cache sizes, showing 40% improvement over the base LRU caching algorithm.