跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.24549 · v1

TTL Approximations for a Family of CLOCK-Like Cache Replacement Policies

首次提交 2026-11-18 22:52
版本更新 2026-11-18 22:52
雷达观测 2026-11-19 15:04
arXiv ↗PDF ↗

摘要

While CLOCK-like cache replacement policies are highly appealing in practice due to their frugal memory usage and implementation simplicity, analytical models for their performance remain limited. The difficulty stems from the "eviction hand" itself. As it scans sequentially for an evictee, sparing objects with survival counters along the way, it inherently entangles the state of one cached object with the next. This strong coupling heavily obscures the system's steady state. To address this gap, we introduce a time-to-live (TTL) approximation for a family of eviction policies---which we term CLOCK(KK)---that decouples individual object dynamics using a globally fixed timer. In contrast to the intrinsic coupling induced by assuming a fixed cache capacity, such a TTL proxy yields a tractable matrix-analytic solution for the steady-state miss ratio functions across a broad and highly expressive class of phase-type renewal traffic. Among other benefits, this effectively reduces the analysis per-object to solving a linear system of order O(Kd)O(Kd), where dd is the phase dimension. Moreover, our model for CLOCK(KK) recovers the canonical CLOCK when K=1K=1 and FIFO when K=0K=0, while empirically exhibiting Schur-concavity under the Independent Reference Model (IRM). Finally, we validate the model against a suite of trace-driven simulations.

作者备注:Accepted and presented at IFIP Performance 2026. To appear in ACM SIGMETRICS Performance Evaluation Review

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-18 22:52 · 最新观测版本

TTL Approximations for a Family of CLOCK-Like Cache Replacement Policies

While CLOCK-like cache replacement policies are highly appealing in practice due to their frugal memory usage and implementation simplicity, analytical models for their performance remain limited. The difficulty stems from the "eviction hand" itself. As it scans sequentially for an evictee, sparing objects with survival counters along the way, it inherently entangles the state of one cached object with the next. This strong coupling heavily obscures the system's steady state. To address this gap, we introduce a time-to-live (TTL) approximation for a family of eviction policies---which we term CLOCK(KK)---that decouples individual object dynamics using a globally fixed timer. In contrast to the intrinsic coupling induced by assuming a fixed cache capacity, such a TTL proxy yields a tractable matrix-analytic solution for the steady-state miss ratio functions across a broad and highly expressive class of phase-type renewal traffic. Among other benefits, this effectively reduces the analysis per-object to solving a linear system of order O(Kd)O(Kd), where dd is the phase dimension. Moreover, our model for CLOCK(KK) recovers the canonical CLOCK when K=1K=1 and FIFO when K=0K=0, while empirically exhibiting Schur-concavity under the Independent Reference Model (IRM). Finally, we validate the model against a suite of trace-driven simulations.

查看此版本解读 →查看此版本原文 ↗