# A Cache Policy Based on Request Association Analysis for Reliable NAND-Based Storage Systems
## 2 Related Work  
### Cache Management Methods  
The current mainstream storage architectures [5; 6; 7] (e.g., SSDs or NVDIMM) usually adopt NAND flash memory as the storage medium. A read/write unit in NAND flash memory [8; 9] is a page and cannot be overwritten unless its residing block is erased first. When the number of free pages in NAND flash memory is not enough, the activities of garbage collection will first select a victim block, copy the victim block's valid pages to other free pages and then erase the victim block to generate a free block. In the process of garbage collection, when a large number of page writes and erase operations are concentrated on a specific block, the block will be quickly worn out to damage the lifetime of NAND flash memory [10; 11; 12; 13]. Therefore, DRAM is usually added to NAND flash memory as cache to store the frequently accessed data, because DRAM has a higher access speed and better reliability than NAND flash memory. So, a cache can speed up the performance of NAND flash memory by reducing the read and write requests. However, the cache capacity is limited. When the cache space is full, how to select the appropriate victims to be replaced has always been an important research topic. In the following, we will introduce some typical cache management methods. Different from the previous cache management methods that mainly consider the temporal/spatial locality, we will modify the ARC method (that will be described later) to both consider the temporal/spatial locality and the request associations between the accessed data to improve the cache hit ratio. 1. _LRU_: A least-recently-used (LRU) method [1] is a common replacement strategy based on temporal locality. Pages that have been frequently and recently accessed will have a high chance of being accessed again after a while. Therefore, when the cache space is full, an LRU method will select the least-recently-used (LRU) page as a victim and remove it. An LRU method generally uses a linked list. The newly inserted page will be at the head of the list. When any page is hit in the cache, the page will be moved to the head of the list. When the cache space is full, the least-recently-used (LRU) page at the tail of the list will be selected as a victim. However, the hot data stored in the cache could be easily evicted to cause performance degradation due to a lot of sequential accessing. 2. _Two-Level LRU_: As shown in Figure 1, a two-level LRU method [2] uses two LRU linked lists. The newly inserted page that does not exist in the cache will be placed at the head of the first list. When any page is hit in the cache, the page will be moved to the head of the second list. If the second list is full, the page at the tail of the second list will be moved to the head of the first list. If the first list is full, the page at the tail of the first list will be evicted from the list. Compared with the LRU method, when encountering a lot of sequential accesses, it will only affect the first list and will not affect the hot data in the second list. So, the two-level LRU method can effectively improve the cache hit ratio. However, different length settings of the two LRU lists will affect its performance, and how to dynamically and efficiently adjust the lengths of the two LRU lists for different workloads will be described later (e.g., ARC). 3. _ARC_: As shown in Figure 2, an adaptive replacement cache (ARC) [3] also uses two LRU linked lists: L1 and L2. L1 stores the pages that appear only once, and L2 stores the pages that appear two or more times. L1 is divided into T1 and B1, and L2 is divided into T2 and B2. T1 and T2 store the contents of the pages in the cache and the related metadata in the cache directory, but B1 and B2 (e.g., ghost buffers) only store the related metadata evicted from T1 and T2, respectively.