# To Cache or Not to Cache
## 5 Related Work
### Non-Datapath Caches  
LARC [14] is a non-datapath caching algorithm that focuses on reducing forced updates to a non-datapath cache. At a high-level, LARC prevents inserting items not found in the cache in case they have not been accessed sufficiently recently. LARC consists of two LRU lists, one for cached items and a second first-in-first-out _filter list_ for tracking non-cached items that have been accessed recently. A cache update is only performed when an item that is not found in the cache _is_ found in the filter list. While LARC's filtering approach is straightforward, its filter is always operational and, as a result, can prevent important items from entering the cache in a timely fashion. In particular, LARC populates the cache at least twice as slowly as most other algorithms when workload working sets change.  
mARC [13] is a selective caching algorithm that improves performance and endurance by using cache _hit rate_ as a metric to selectively turn on/off cache insertions. To make this possible, mARC defines three distinct _workload states: unstable_, _stable_, and _unique access_ and reflects these states within the mARC state model. mARC bases its state detection mechanisms by observing a single system metric, the cache hit rate. While mARC is able to utilize its knowledge about workload states to allow updates or not in the cache, it has important limitations. First, since it does not account for the _stable_\(\rightarrow\)_unique_ (and vice-versa) state transitions, it is unable to handle certain workloads. Second, mARC fixes the values of various parameters that compromises its ability to adapt and recognize workload states for arbitrary workloads. Thirdly, mARC relies on cache-hits in order to understand the workload behavior, which leaves mARC not analyzing the workload itself, but rather the effects of the workload on the cache. This method of analysis is slow, requiring the item to _first_ be inserted into the cache.  
FlashTier [8] is a system architecture built for solid-state caches. FlashTier aims to address the main limitations of caching when using traditional SSDs, providing an interface designed specifically for caching. The limitations FlashTier focuses on relate to reducing the cost of cache block management, providing cache consistency guarantees, and silent evictions of blocks during garbage collection for performance gains. While focused on improving non-datapath caches, FlashTier itself used Facebook's _FlashCache for Linux_[29] for evaluation, as FlashTier is not a cache algorithm itself.  
Least Hit Density (LHD) [30] uses a calculation of _hit density_ to determine what to filter and evict from a cache. Furthermore, _hit density_ is a predicted value based on age, frequency, application ID, and size. Additionally, the implementation utilizes several techniques to improve throughput, such as random sampling of the cache for eviction and reducing lock contention by reducing the number of updates to the data structure. LHD relies on precomputed ranks that then adapt after a million requests, working under the intention that application behavior is stable for short periods of time. **FOMO** assumes there to bothbe more dynamism within the workload behavior while working in a context where objects are of a constant size.