False Negative Awareness in Indicator-Based Caching Systems

Distributed caching systems such as content distribution networks often advertise their content via lightweight approximate indicators (e.g., Bloom filters) to efficiently inform clients where each datum is likely cached. While false-positive indications are necessary and well understood, most exist...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on networking 2022-12, Vol.30 (6), p.2674-2687
Main Authors: Cohen, Itamar, Einziger, Gil, Scalosub, Gabriel
Format: Article
Language:English
Subjects:
Advertising
Algorithms
Bandwidth
Bandwidths
Cache memory
Caching
Content distribution networks
Costs
Data structures
distributed databases
forecast uncertainty
IEEE transactions
Network latency
Policies
storage area networks
Uncertainty
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Distributed caching systems such as content distribution networks often advertise their content via lightweight approximate indicators (e.g., Bloom filters) to efficiently inform clients where each datum is likely cached. While false-positive indications are necessary and well understood, most existing works assume no false-negative indications. Our work illustrates practical scenarios where false-negatives are unavoidable and ignoring them significantly impacts system performance. Specifically, we focus on false-negatives induced by indicator staleness, which arises whenever the system advertises the indicator only periodically, rather than immediately reporting every change in the cache. Such scenarios naturally occur, e.g., in bandwidth-constraint environments or when latency impedes each client's ability to obtain an updated indicator. Our work introduces novel false-negative aware access policies that continuously estimate the false-negative ratio and sometimes access caches despite negative indications. We present optimal policies for homogeneous settings and provide approximation guarantees for our algorithms in heterogeneous environments. We further perform an extensive simulation study with multiple real system traces. We show that our false-negative aware algorithms incur a significantly lower service cost than existing approaches or match the cost of these approaches while requiring an order of magnitude fewer resources (e.g., caching capacity or bandwidth).
ISSN:1063-6692
1558-2566
DOI:10.1109/TNET.2022.3177282