# To Cache or Not to Cache
## 4 Evaluation
### **Fomo's Miss-History: A Case Study**  
**Fomo's hit rate and write rate results show the benefit of **Fomo's** design. However, the structure central to **Fomo's understanding of the workload: _the Miss-History_ has not been analyzed for effectiveness. We present a case where the Miss-History reveals a pattern that **Fomo** takes advantage of, but neither LARC nor mARC do--the first 60 million requests of the CloudPhysics workload w54_vscsi2_itrace with a cache size of 1% of the number of unique addresses requested. Some of the previously noted shortcomings of mARC are present within Figure 9. These particular shortcomings are the lack of a direct transition between the _Stable_ and the _Unique Access_ states, incurring extra writes to the cache, and mARC's analysis of the workload using cache hit rate, which prevents it from noticing opportunities for hits.  
What is interesting about this workload is that the majority of repeated accesses are limited to the second access of an item, with very few third or fourth accesses within a reasonable time frame. This can be seen in Figure 9, where the LRU hit rate mostly mirrors that of the Miss-History, which, in general, removes items from its structure on the item's second access.  
Figure 9: **(top)** The hit rates of both LARC and mARC for the CloudPhysics workload w54_vscsi2_itrace, in which LARC and mARC do not perform well. The background has colors that indicate the state of mARC. LARC stops seeing a significant amount of hits after it fills the cache. mARC stops seeing a significant amount of hits after it switches to the _Stable_ state \⃝\). mARC incurs unnecessary writes by transitioning to the _Unstable_ state before transitioning to the _Unique Access_ state \⃝\). mARC does not see any cache hit rate activity and therefore cannot find a reason to change state \⃝\), even though plenty of opportunities for cache hits exist, as can be seen in Figure 9b. **(bottom)** The cache hit rates of LRU and the reuse rates of **Fomo’s Miss-History. The caching algorithm that **Fomo** augments does not matter here, as the focus is on the Miss-History. To be able to see both hit rates more clearly, the hit rate of the Miss-History has been mirrored over the horizontal axis (negated). This, compounded with the hit rates of LARC and mARC, show both that LRU is capable of having hits and that **Fomo’s Miss-History** is seeing the same hits. Taken together, these plots demonstrate that the workload is mostly composed of items limited to second accesses. As such, both LARC and mARC (when acting similar to LARC) are only caching items when they have the second access, but do not receive any benefit in doing so.  
**FOMO** is capable of finding patterns within the workload, and makes reasonable decisions based on these patterns, which can be seen in Figure 10. **FOMO's** decisions here capture many opportunities for hits that go unrecognized by both LARC and mARC, whose hit rate (and mARC's states) can be seen in Figure 9. This is unfortunate for mARC, which places emphasis on identifying workload states. mARC, due to its focus on using cache hit rate to identify workload state instead of something similar to **FOMO's Miss-History, cannot see the pattern within this workload, leaving mARC to stay in the _Unique Access_ state.