Check out the new USENIX Web site. next up previous
Next: Handling Multi-path Hierarchies Up: Adapting probPromote Previous: PROMOTE-LRU

PROMOTE-ARC

First, we summarize the ARC algorithm [25]: ARC maintains $ c$ pages in the cache and $ c$ history pages. LRU list $ T_1$ contains pages that have been seen only once recently, and $ T_2$ contains the pages that have been seen at least twice recently. The addresses of the pages recently evicted from $ T_1$ and $ T_2$ are stored in $ B_1$ and $ B_2$, respectively. $ \vert T_1\vert+\vert T_2\vert \le c$ is enforced, while the relative sizes of the lists are adapted according to the relative rates of hits in the corresponding history lists $ B_1$ and $ B_2$.

For simplicity, consider a single-path hierarchy of ARC caches (Figure 6). Theoretically, the caches could pass the marginal utility of the $ T_1$ and $ T_2$ lists to lower caches which could dynamically adapt $ probPromote$ at each cache level to equalize the utility across the hierarchy. However, it can be challenging to adapt $ probPromote$ in a stable way for both $ T_1$ and $ T_2$ lists at each level. We found a simple policy that works very well for ARC. For traffic destined for $ T_1$ lists, $ probPromote$ at each cache $ C_k$ is set to a fixed value $ \sum_{i=1}^{k-1}\vert C_i\vert / \sum_{i=1}^k\vert C_i\vert$. Instead of the cache life, the $ life/occupancy$ of the $ T_2$ list is passed to lower caches, where $ occupancy$ is the fraction of the cache occupied by $ T_2$. Merely using the cache life for $ T_2$ list did not fare well, compared to DEMOTE-ARC, in unlimited bandwidth cases. The $ probPromote$ for the $ T_2$ lists is dynamically adapted at each level so as to equalize $ life/occupancy$ across the hierarchy (Lines 41-43).

Another hint called the $ T_2hint$ is used along with read requests and replies to indicate that the page should be stored in a $ T_2$ list as it has been seen earlier (Line 46). If any cache decides to keep the page (Line 59), it creates the page in $ T_2$ if $ T_2hint$ is true; else it creates it in $ T_1$.


next up previous
Next: Handling Multi-path Hierarchies Up: Adapting probPromote Previous: PROMOTE-LRU
root 2008-01-08