2020 USENIX Annual Technical Conference (USENIX ATC '20). Virtual Boston, MA, July 15–17, 2020.
Dong Zhou1, Huacheng Yu2, Michael Kaminsky3, David Andersen4
1 Tsinghua University, Carnegie Mellon University
2 Princeton University
3 BrdgAI
4 BrdgAI, Carnegie Mellon University
The high packet rates handled by network appliances and similar software-based packet processing applications place a challenging load on caches such as flow caches. In these environments, both hit rate and cache hit latency are critical to throughput. Much recent work, however, has focused exclu- sively on one of these two desiderata, missing opportunities to further improve overall system throughput. This paper in- troduces Bounded Linear Probing (BLP), a new cache design optimized for network appliances. BLP works well across different workloads and cache sizes by balancing between hit rate and lookup latency. To accompany BLP, we also present a new, lightweight cache eviction policy called Probabilistic Bubble LRU that achieves near-optimal cache hit rate (assum- ing the algorithm is offline) without using any extra space. We make three main contributions: a theoretical analysis of BLP, a comparison between existing and proposed cache designs using microbenchmarks, and an end-to-end evaluation of BLP in the popular Open vSwitch (OvS) system. Our end-to-end experiments show that BLP is effective in practice: replacing the microflow cache in OvS with BLP improves throughput by up to 15%.
FULL PAPER: pdf / talk video / slides