# To Cache or Not to Cache
## 4 Evaluation
### Adversarial Workloads  
**FOMO** improves upon the results of the underlying cache replacement algorithm for every workload and cache size, as seen in Figure 7, with the exception of CloudCache. In fact, CloudCache workloads did not appear to have any of the non-datapath caches perform well compared to their datapath caching algorithm counterparts. When investigating the reason for this behavior, several things of note were observed, which will be highlighted with a focused discussion on one of these CloudCache workloads: webserver-2012-11-22-1.blk.  
Webserver-2012-11-22-1.blk has an instance that shows a large time frame where non-datapath caching algorithms do not perform well compared to the datapath cache algorithms, shown in Figure 11. In particular, the time period between one million and four million requests has this behavior. When observing the block address access pattern plots of this CloudCache workload (Figure 12), it is noticeable that the workloads include several concurrent working sets and patterns (combinations of scans, random accesses, looping and repeated accesses). This mixing of patterns increases the likelihood of both **FOMO** and mARC observing reuse and discerning patterns in the workload based on them. This is why, as the cache size increases, the difference between the datapath and non-datapath caches begins to decrease.  
Each of the non-datapath cache algorithms have their own reasons for why these access patterns were problematic. For LARC, which observes reuse on an individual basis, an item being reused often would not be reused again prior to being evicted, leading to many missed opportunities that the datapath cache algorithms can take advantage of. mARC, with its dependence on cache hit rate for decisions, with its use of the _Unstable_ state as a intermediary transition between _Stable_ and _Unique Access_ states, and the long evaluation times, finds itself within the _Unstable_ state more often and gains some level of advantage over both LARC and FOMO due to it. Lastly, FOMO, lo  
Figure 10: The hit rates of LARC, mARC, and **FOMO**(ARC) for the CloudPhysics workload w54_vscsi2.itrace. **FOMO**(ARC) is shown as it performs the worst among **FOMO**(LRU) and **FOMO**(ARC) in this instance. The background is colored with the state of **FOMO**, where red = _Filter_ and blue = _Insert_. As **FOMO** state switches, it adapts to the workload for the chance to improve the hit rate and is able to achieve much more than both LARC and mARC due to **FOMO’**s Miss-History. & **FOMO**(ARC) started filtering prior to mARC, missing some hits. & **FOMO**(ARC)’s changing states captures some opportunities for hits by switching to the _Insert_ state rapidly.& **FOMO**(ARC) is able to recognize a pattern of reuse and is able to promptly respond and have many cache hits that LARC and mARC instead miss.  
workload, would periodically find a pattern of reuse, change the state to _Insert_, obtain some cache hits that eventually overtake the reuse found in the workload, change state to _Filter_ and so on repeatedly during such highly overlapping periods. Finally, we note that when particular patterns, or reuse in general, were more significant within these workloads, all of the non-datapath cache algorithms would identify and react to achieve cache hits.  
Figure 11: Hit rate plot of CloudCache workload webserver-2012-11-22-1.blk, focusing on ARC as the datapath caching algorithm to compare the performance of the non-datapath caching algorithm to (LARC, mARC, and **FOMO**(LRU)). The background colors correspond to the state of **FOMO**(LRU) at the time, with blue = Insert and red = Filter. From around one million to four million requests ARC is achieving hits that LARC, mARC, and **FOMO**(LRU) are not able to obtain, though **FOMO**(LRU) obtains the most among the non-datapath caching algorithms, as seen in 1