# GreedyDual-Size (GDS)
## Goal
Improve byte-level cache efficiency by preferring entries with better value-per-byte
when item sizes and miss costs vary.
## Core Idea
Each resident entry carries a priority `H`; eviction removes the smallest `H`.
A common GDS-style score:
- `H = (cost / size) + L`
Where:
- `cost`: estimated miss penalty (latency, backend pressure, or monetary cost)
- `size`: object size in bytes
- `L`: global inflation term set to the `H` of the most recently evicted entry
The inflation term prevents old low-value entries from sticking forever.
## Core Data Structures (Typical)
- Hash index `K -> EntryMeta`
- Min-heap keyed by `H` for victim selection
- Global inflation scalar `L`
## Complexity & Overhead
- Heap updates are usually O(log n) on insert/update/evict
- More metadata than LRU/FIFO due to per-entry score and object size/cost
## Notes For CacheKit
- Useful when optimizing byte hit rate, not just request hit rate.
- Integrates naturally if entry size is already tracked in storage metadata.
- Keep score updates explicit and avoid per-access allocation.
## References
- Cao, Irani (1997): “GreedyDual-Size: An algorithm for web caching”.
- Wikipedia: https://en.wikipedia.org/wiki/Cache_replacement_policies