← 研踪 PaperTrailarXiv: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
摘要
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()---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 , where is the phase dimension. Moreover, our model for CLOCK() recovers the canonical CLOCK when and FIFO when , 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
观测到的版本
相邻记录可能跳过中间版本;首次发现 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()---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 , where is the phase dimension. Moreover, our model for CLOCK() recovers the canonical CLOCK when and FIFO when , while empirically exhibiting Schur-concavity under the Independent Reference Model (IRM). Finally, we validate the model against a suite of trace-driven simulations.
查看此版本解读 →查看此版本原文 ↗