# To Cache or Not to Cache
## 1 Introduction  
Conventional caching algorithms (e.g., LRU [1], Clock [2], FIFO [1], ARC [3], MQ [4], LIRS [5], etc.) were designed for _datapath caches_. These _datapath caches_ are defined by their requirement whereby every cache miss requires that a cache **insertion** occurs and, should that cache be full, a cache **eviction** is also incurred. While this is suitable for CPU and DRAM caches, where the write endurance cost of each **insertion** is relatively inexpensive, it is not true for flash or persistent memory SSD caches that are typically used to cache storage system data. When using host-side SSD caches [6; 7; 8], data can be served to the application directly from back-end storage without having to first retrieve them into the cache. This opens up a unique opportunity: _selective updates_, whereby cache updates are not always made upon a cache miss but are instead decided on every access. Caches that allow for this flexibility are _non-datapath caches_. Non-datapath caching algorithms with _selective updates_, can improve the lifetime of cache devices that wear out on account of device-level writes [9; 10]. These algorithms, also have the ability to improve cache hit rate by avoiding cache replacement in cases wherein the evicted item is considered more valuable than the inserted item [11; 12]. Prior research has demonstrated that state-of-the-art caching algorithms such as ARC can compromise both the cache hit rate as well as the cache write rate when applied to non-datapath caches [13; 14]. [PERSON] et al. [13] demonstrated that workloads are heterogeneous and manifest different characteristics in different phases of their execution. They proposed mARC [13], a non-datapath caching algorithm that responds to workload phases by either turning _on_ or _off_ a filter that prevents items from entering an ARC-managed cache upon first access. However, it is not clear whether mARC would generalize to cache replacementpolicies other than ARC (e.g., LIRS [5]), some of which have been found valuable in addressing the wide array of storage workload types in production. Furthermore, mARC relied on a set of workload-sensitive constants (totaling eight in all) that defined cache behavior; we demonstrate that this compromises mARC's ability to adapt to the variations within and across workloads. In this paper, we propose _Fear of Missing Out_ (**FOMO**), a generalized non-datapath admission policy that can be used to augment any datapath cache replacement policy. **FOMO** augments datapath cache replacement policies to become better suited for non-datapath caches. **FOMO** exists in one of two possible states at any given time--_Insert_ or _Filter_. When in the _Insert_ state, **FOMO** forwards all cache requests to the underlying cache replacement policy while observing the behaviors of both the cache and the workload. When in the _Filter_ state, **FOMO** selectively disables cache updates to improve both cache update rate (cache writes) and the cache hit rate by preventing cache pollution. Cache pollution is the insertion of items into the cache whose ultimate value is less than that of the item evicted from the cache, hence why the cache is polluted with worse items. **FOMO** decides which state to be in by utilizing information about accesses to items that were in the cache or were recent cache misses. To determine the reuse of recent cache misses, **FOMO** maintains a Miss-History structure that keeps track of these items and their reuse. Using small periods of observation to come to these decisions, **FOMO** is capable of reacting rapidly to changes in workload behavior. This reaction speed is important for **FOMO**. **FOMO** does not want to _miss out_ on inserting items into the cache for future hits nor does it want to _miss out_ on preserving the items in the cache or preventing items lacking reuse from entering into the cache. Therefore, just as someone wishing to keep up with the latest trends, **FOMO** does not want to _miss out_ on reacting to the latest workload behavior.