hesela.devGreedyDual-Size
GreedyDual-Size is a cache-replacement policy that combines retrieval cost per unit size with aging and refreshes priority on access.
On insertion or a hit, set H = L + cost/size. Evict a minimum-H object when space is needed, advancing L to that victim's H, and repeat until the requested object fits. L is an eviction-driven offset, not elapsed time; it avoids decrementing every resident priority. [1]
The cost unit defines the objective: unit cost counts retrievals, while cost equal to size counts fetched bytes. Neither is automatically a latency model. Young's related Landlord formulation permits different hit-credit refresh choices; those choices need not reproduce the same eviction history. [2]
DULO adapts this cost-density idea to sequences of disk blocks. Its historical design favors retaining short sequences under an assumed equal sequence-fetch cost, rather than merely minimizing block misses. That assumption is not a measurement of current SSDs. [3]
Hesela's exact-arithmetic replay compares explicit decrements with the common-offset representation after every request. Deterministic identifier-order ties, fixed object metadata and initially empty caches are declared model choices. Operation counts exclude victim search and do not establish a runtime speedup. [4]
For the declared seven-request witness, unit-cost GDS misses eight size units and byte-cost GDS misses nine, out of eleven requested. This is a counterexample to a per-trace optimality claim, not evidence that unit cost generally wins. The tie rule and full inputs are in the replay packet. [4]
Relations
- related
- Request hit ratio, Byte hit ratio, Cache pollution, Cache admission, Least recently used replacement
Limitations
- The original evaluation used historical Web-access traces; its performance comparisons are not a guarantee for a current storage workload. [1]
- The file-caching model does not resolve changing retrieval costs, cache consistency, or distributed coordination. [2]
Citations
- Cao and Irani. Cost-Aware WWW Proxy Caching Algorithms. USITS 1997, sections 3-5 and Figure 5.
- Young. On-Line File Caching. Algorithmica 33 (2002), pp. 371-383, section 1 and Figure 1. DOI: 10.1007/s00453-001-0124-5.
- Jiang, Ding, Chen, Tan and Zhang. DULO. FAST 2005, sections 3.4 and 4.
- Hesela. GreedyDual-Size priority equivalence: constructed inputs, exact replay and limitations.
Sources & caveats
- Primary-source synthesis plus constructed arithmetic examples, not reproduction of the papers' trace-driven performance measurements.