Software Setup

Figure 7: CacheSim block diagram: Multiple instances form a hierarchy of caches. Algorithm-specific interfaces are marked: D, H, and T ($T_2hint$).

We implemented CacheSim (Figure 7), a framework which allows us to benchmark various algorithms for a wide range of cache sizes, real-life traces, and any single and multi-path hierarchy. CacheSim is instantiated with a given cache size and one of the following policies: LRU, ARC, DEMOTE-LRU, DEMOTE-ARC, PROMOTE-LRU, and PROMOTE-ARC. One instance of CacheSim simulates one level of cache in a multi-level cache hierarchy, while communicating to the higher and lower caches over a TCP/IP network. The highest level reads requests from a trace file one I/O (size $512$ bytes) at a time, with no thinktime, while the lowest level simulates disk responses with a fixed response time.

Apart from the traditional read interfaces, CacheSim also implements two special interfaces:

• DEMOTE interface: Used only by the DEMOTE technique to transfer evicted pages to the next lower cache.
• Hint interface: Used by the PROMOTE technique to periodically transfer life and occupancy information to the next lower cache.

CacheSim simulates the following realistic roundtrip response times for storage system hierarchies (based on our knowledge): For two-level scenarios: $t_1$ = $0.5$ ms, $t_2$ = $1.0$ ms, $t_m$ = $5.0$. For three-level scenarios: $t_1$ = $0.5$ ms, $t_2$ = $1.0$ ms, $t_3$ = $2.0$ ms, $t_m$ = $10.0$ ms. The results in this paper are applicable for any set of values where $t_i < t_{i+1}$.