# A Cache Policy Based on Request Association Analysis for Reliable NAND-Based Storage Systems
## 2 Related Work
### Cache Management Methods
Assuming that the cache can buffer c pages, the length limits of ARC are \(0\leq\mid\) L1\(\mid\)\(\leq\) c, \(0\leq\mid\) L1\(\mid\) + \(\mid\) L2\(\mid\)\(\leq\) 2c, \(0\leq\mid\) T1\(\mid\) + \(\mid\) T2\(\mid\)\(\leq\) c, \(0\leq\mid\) B1\(\mid\) + \(\mid\) B2\(\mid\)\(\leq\) c. If a newly inserted page does not exist in L1 and L2, it will be placed at the head of T1; otherwise, it will be placed at the head of T2. The space of T1 is decided by a target size p. When a new page is inserted to the cache that is full, we have to remove one victim page from T1 or T2 according to the following condition--if \(\mid\) T1\(\mid\)\(\geq\) p, the LRU page of T1 will be evicted and then its related metadata will be inserted to B1; otherwise, if \(\mid\) T1\(\mid\)\(<\) p, the LRU page of T2 will be evicted and then its related metadata will be inserted to B2. If a hit occurs in B1, the target size p of T1 will be increased by the maximum of \(\left\{\mid\) B2\(\mid\) / B1\(\mid\), 1\(\right\}\). If a hit occurs in B2, the target size p of T1 will be decreased by the maximum of \(\left\{\mid\) B1\(\mid\) / B2\(\mid\), 1\(\right\}\). ARC can dynamically and efficiently adjust the lengths of L1 and L2 for different workloads to achieve the best performance. 4. _VBBMS_: As shown in Figure 3, VBBMS [4] is a typical flash-aware buffer method to combine consecutive pages in the same virtual block. When the cache space is insufficient, VBBMS will evict the entire virtual block so that the data written to flash memory can be more sequential. By the eviction of the entire virtual block, VBBMS can easily make a block to have more invalid pages and reduce the overhead of the garbage collection. In addition, because random requests and sequential requests  
Figure 1: Two-Level LRU. Figure 2: ARC. have completely different characteristics, VBBMS uses an LRU list to manage random requests and a FIFO queue to manage sequential requests. In addition, the parameter setting (such as the size of a virtual block and the distributions of an LRU list and a FIFO queue) could have a large impact on the results. Because VBBMS [4] shows that it has better hit ratio than the flash-aware cache replacement policies such as CFLRU [14], BPLRU [15], AD-LRU [16], PR-LRU [17] and CLOCK-DNV [18], we compared the proposed method with VBBMS in the experiments. CFLRU is a page-based cache replacement policy and can take the asymmetry of read/write cost into consideration. CFLRU splits the cache into working region and clean-first region, where the LRU clean pages in the clean-first region are evicted first, otherwise the LRU dirty pages in the clean-first region are evicted. BPLRU is a block-level cache replacement policy and maintains some clusters by the LRU mechanism, where a cluster contains a series of consecutive pages that belong to a data block. AD-LRU is a page-based cache replacement policy and uses an adaptive mechanism to buffer pages in the hot and cold LRU queues. AD-LRU considers the frequency and recency of page references and also takes the asymmetry of read/write cost into consideration when replacing pages. PR-LRU is a page-based cache replacement policy and uses a probability of reference (PR) to predict whether a page may be referenced in the future. CLOCK-DNV proposes a hybrid write buffer architecture that consists of DRAM and non-volatile memory. CLOCK-DNV is managed differently to DRAM and non-volatile memory: CLOCK-D for DRAM at a page granularity and CLOCK-NV for non-volatile memory at a block granularity.