hesela.devHyperbolic caching
Hyperbolic caching is a replacement policy that estimates an object's frequency over its current cache residence and evaluates sampled eviction candidates lazily.
The base score is access count divided by time since insertion, not time since the last hit. Insertion starts the count at one; eviction discards this residence history. The lowest current score among sampled candidates is selected, not necessarily the global minimum. [1]
Constructed example: A has four accesses since time 0; B has one since time 9. With no further accesses to either, their scores at time 10 are 2/5 and 1; at time 12 both are 1/3; at time 20 they are 1/5 and 1/11. The lower-priority object changes from A to B. These are exact arithmetic results, not measured cache performance. [3]
For 100 residents, a fixed lowest-priority set of ten and eight independent uniform draws with replacement, the chance of sampling at least one of those ten is 1 - (9/10)^8 = 56.953279%. This is neither the chance of selecting the unique global minimum nor a hit-rate prediction. [3]
The author simulator's ordinary Sampling.sample path uses integer draws that permit repeated candidates. Retained-candidate and other sampling variants require their own probability model. [2]
Relations
Citations
- Blankstein, Sen and Freedman. Hyperbolic Caching: Flexible Caching for Web Applications. USENIX ATC 2017, pp. 499-511, sections 2.1 and 2.4, Figure 1.
- Author simulator: Sampling.sample, commit 884c466c311bb5b9fbdd09791d829b04032f3947.
- Hesela: exact priority-crossing and sampling calculations.
Further reading
Sources & caveats
- Primary-paper and pinned-source review; no execution of the historical author simulator.
- Equal-size, equal-cost resident objects; positive residence ages only. The reference calculation rejects zero age rather than specifying a production tie or timestamp policy.