  Distributed caches are widely deployed to serve social networks and web
applications at billion-user scales. This paper presents Cache-on-Track (CoT),
a decentralized, elastic, and predictive caching framework for cloud
environments. CoT proposes a new cache replacement policy specifically tailored
for small front-end caches that serve skewed workloads. Front-end servers use a
heavy hitter tracking algorithm to continuously track the top-k hot keys. CoT
dynamically caches the hottest C keys out of the tracked keys. Our experiments
show that CoT's replacement policy consistently outperforms the hit-rates of
LRU, LFU, and ARC for the same cache size on different skewed workloads. Also,
\algoname slightly outperforms the hit-rate of LRU-2 when both policies are
configured with the same tracking (history) size. CoT achieves server size
load-balance with 50\% to 93.75\% less front-end cache in comparison to other
replacement policies.
