# To Cache or Not to Cache
## 3 Design
### **Fomo** States  
**FOMO** incorporates a simple, two state design: _Insert_ and _Filter_. This simplicity eliminates complex state transitions while still encompassing the necessary actions when identifying workload behaviors. When **FOMO** is in the _Insert_ state, all requests are passed to the underlying cache replacement algorithm, where it may cache it and choose what to evict, if needed. **FOMO** always begins in the _Insert_ state to gather information while filling up the cache. When **FOMO** is in the _Filter_ state, **FOMO** decides whether or not a request will be passed to the underlying cache replacement algorithm. How **FOMO** decides this is similar to LARC: the request exists in the cache or reuse is observed for an item _not_ in the cache. **FOMO** tracks this observable reuse with the Miss-History. Should **FOMO** encounter a cache miss that exists within the Miss-History while in the _Filter_ state, it will observe that the item has reuse and pass it on to the cache to insert, as well as remove this item from the Miss-History. This removal from the Miss-History while in the _Filter_ state is desirable mainly to avoid the possibilities of _cache churning_[13]. Cache churning occurs when the working set is a superset of the items in the cache, but the lowest frequency items in the cache and some of those outside the cache are similar. This has meant that the lowest frequency items in the cache are evicted to make way for the similarly (or lower) frequency items outside of the cache, introducing several misses that instead could be hits by protecting the items in the cache from eviction. Figures 2 and 3 show examples of how **FOMO** operates within these states and how the Miss-History is affected. With these two states (_Insert_ and _Filter_), the conditions to transition between them must be defined. We define two conditions that represent each state: \(HR_{cache}<HR_{\mathit{Miss-History}}\) and \(HR_{\mathit{cache}}\geq HR_{\mathit{Miss-History}}\), where \(HR\) represents the hit-rate observed by either the cache or the Miss-History. The conditions we define below are a consequence of empirical observations and analysis of algorithm behavior. The transition from _Filter_ to _Insert_ was determined to be advantageous where the reuse in the Miss-History was significant, or greater than the hits to the cache. The transition from _Insert_ to _Filter_ was determined to be advantageous where the reuse of the Miss-History was not significant. In order to calculate both \(HR_{\mathit{cache}}\) and \(HR_{\mathit{Miss-History}}\), the last _period_ of requests are observed for hits/reuse, where the period's size is set to 1% of the cache size. This selection was motivated by having **FOMO** react swiftly to changes and protect the items in the cache. We noticed that **FOMO** would at times encounter situations where both \(HR_{\mathit{cache}}\) and \(HR_{\mathit{Miss-History}}\) were low and the slightest changes encouraged **FOMO** too strongly to transition from the _Filter_ state to the _Insert_ state. This led to an additional condition being added to the _Filter_ to _Insert_ transition: \(HR_{\mathit{Miss-History}}>5\%\). The addition of this condition prevented this edge-case scenario from improperly using the reuse of a few items in the Miss-History as justification to change state to the _Insert_ state. The final state design can be seen in Figure 4, while the finalized algorithm can be seen in Algorithm 1. Figure 4: **FOMO** states and transition conditions.