storage system engineers

Abstract: Block caches commonly serve scan-heavy I/O workloads, motivating extensive studies on scan-resistant eviction algorithms. Many of these algorithms adopt a multi-queue structure. However, they focus primarily on one-time scans and do not handle repeated scans well. Two important challenges from repeated scans are miss-ratio cliffs, where a small increase in cache size sharply reduces the miss ratio, and Belady's anomalies, where increasing the cache size increases the miss ratio. In this paper, we first develop two quantitative metrics to measure these behaviors. With these metrics, we find that LIRS is the only multi-queue algorithm that is scan-resistant (almost cliff- and anomaly-free). Contrary to conventional wisdom, we show that stack distance is not the secret sauce that makes LIRS scan-resistant. Instead, regulating the queues are the key to its scan resistance. Based on these insights, we design the \gadgetprefix Gadgets, easy-to-integrate augmentations that make existing algorithms scan-resistant without changing their eviction heuristics or queue structures. We implement the \gadgetprefix Gadgets in five algorithms: S3-FIFO, SIEVE, ARC, 2Q, and TinyLFU, and make them scan-resistant. Evaluated on 5,538 production traces, all augmented algorithms outperform their base versions, reducing miss ratios by up to 23.1% while consistently reducing cliffs and Belady's anomalies across the production traces.

Abstract: Locally decodable codes (LDCs) enable recovery of any message symbol by probing only a small number of positions in a possibly corrupted codeword. The central parameters of an LDC are its rate, locality, and error tolerance. Ideally, one would like all three parameters to be constant. However, classical lower bounds show that such codes cannot exist. A recent line of work introduced amortized locally decodable codes (aLDCs), in which the decoder is tasked with recovering an entire block of consecutive message symbols rather than a single symbol. While prior work obtained ideal aLDCs with constant rate, constant error tolerance, and constant amortized locality, those constructions relied on either shared randomness hidden from the channel or computational assumptions restricting the channel. Another well-studied relaxation is the notion of a relaxed locally decodable code (RLDC), in which the decoder may output a special failure symbol $\bot$ rather than risk decoding incorrectly. In this work, we introduce the notion of an amortized relaxed locally decodable code (aRLDC), combining amortized decoding with the relaxed decoding paradigm. Unlike prior ideal aLDC constructions, our model is fully information-theoretic and makes no assumptions about shared randomness or computational limitations of the adversarial channel. We construct the first aRLDC with constant rate, constant error tolerance, and constant amortized locality. Moreover, for any block of length $Ω(\mathrm{polylog}(k))$, our decoder achieves amortized locality $1+δ^{1 - o(1)}$, where $δ$ is the error tolerance parameter. Thus, asymptotically, recovering a long block requires essentially less than two codeword probe per message symbol recovered. By contrast, without amortization no RLDC can simultaneously achieve constant rate, constant error tolerance, and constant locality.