sarc · research · also Sequential Prefetching in Adaptive Replacement Cache

SARC

SARC is a cache-management policy that adaptively divides space between sequentially prefetched and randomly accessed data.

Gill and Modha's 2005 policy keeps SEQ and RANDOM LRU lists and adjusts the desired SEQ size using estimated marginal utility: the expected reduction in misses from extra cache space. This is not ARC's recency/frequency partition, and SARC does not require ARC's history of recently evicted pages. [1] [2]

The adjustment uses sequential misses between bottom-of-RANDOM hits. A bottom-of-SEQ hit can also select the maximum positive adjustment when the estimated utility ratio exceeds the configured threshold; subsequent evictions apply that adjustment. Its magnitude is bounded, and the desired size changes when an eviction occurs, not just as wall-clock time passes. The implementation approximates bottom-list membership using timestamps. [3]

Figure 4 selects the older of the two LRU tails when either list is smaller than the bottom-window size (delta L). Otherwise it evicts from SEQ when that list exceeds its desired size, and from RANDOM when it does not. Thus the desired partition does not always choose the victim list. [3]

SARC's partition control is distinct from AMP's adaptation of prefetch degree and trigger distance for concurrent sequential streams. Allocating more space to prefetched data does not itself choose when or how much each stream should fetch. [7]

Relations

related

Prefetch wastage, Cache inclusion property, Adaptive Replacement Cache, Prefetch trigger distance, readahead (Linux syscall)

Limitations

• The reported comparison used a disk-array controller and an SPC-1 Like prototype workload; it is not a certified SPC-1 result. The paper reports scaled IOPS with an undisclosed multiplier, so those axis values cannot be read as absolute IOPS. [4, 5]
• The reported improvements are conditional on the tested configurations, not a universal guarantee for every load, metric or modern storage device. Table II includes light-load points where an LRU variant has a lower mean read latency. [6]
• The Shark results used experimental software. Endnote 1 states that the commercial ESS Model 800 did not use any of the three evaluated replacement policies or the described prefetch algorithm. These measurements therefore do not establish shipped-product performance or SARC deployment. [8]

Citations

1. Gill and Modha. SARC: Sequential Prefetching in Adaptive Replacement Cache. USENIX ATC 2005, pp. 293-308; section III-A distinguishes SARC from ARC. (accessed 2026-10-30)
2. Gill and Modha, SARC, section III-B: SEQ/RANDOM partition and estimated marginal utility. (accessed 2026-10-30)
3. Gill and Modha, SARC, section III-G and Figure 4: bounded adjustment, eviction-driven update and timestamp approximation. (accessed 2026-10-30)
4. Gill and Modha, SARC, section IV-C: SPC-1 Like prototype and undisclosed IOPS scaling. (accessed 2026-10-30)
5. Gill and Modha, SARC, section IV-B: one-cluster IBM Shark experimental configuration. (accessed 2026-10-30)
6. Gill and Modha, SARC, section IV-F.1 and Table II: configuration- and load-specific response times. (accessed 2026-10-30)
7. Gill and Bathen. AMP: Adaptive Multi-stream Prefetching in a Shared Cache. FAST 2007, pp. 185-198; sections I-D, II-D and III. (accessed 2026-10-30)
8. Gill and Modha, SARC, p. 307, endnote 1: experimental software is distinct from the commercial Shark implementation. (accessed 2026-11-02)

JSON: /data/terms/sarc.json