Skip to content

CONCEPT Cited by 1 source

GDSF eviction

Definition

Greedy Dual Size Frequency (GDSF) is a cache eviction algorithm that generalizes LRU by incorporating page size and fetch cost into eviction priority. Where LRU only considers recency of access, GDSF assigns each cached item a priority value based on:

  • Frequency of access
  • Cost of a cache miss (fetch latency / I/O expense)
  • Size of the item (larger items consume more cache space)

When the cache is full, the item with the lowest priority is evicted. This makes GDSF a cost-aware policy suitable for workloads with heterogeneous page sizes and non-uniform miss costs.

Relationship to LRU

GDSF is a strict generalization: when all pages have the same size and the same miss cost, GDSF degenerates to LRU. In practice, database page caches and web caches have highly variable object sizes and miss costs, making GDSF a stronger baseline than pure LRU.

Role in elastic caching evaluation

Google Research uses an optimized GDSF implementation as the fixed-cache-size baseline when evaluating elastic caching in Spanner. The comparison demonstrates that elastic caching achieves lower total cost even against a strong cost-aware fixed-size policy, not just against naive LRU. (Source: sources/2026-06-25-google-optimizing-cloud-economics-with-linear-elastic-caching)

Seen in

Last updated · 559 distilled / 1,651 read