SIEVE

Goal

Provide strong scan resistance with very low metadata and update overhead.

Core Idea

SIEVE is a simple FIFO-like policy with a one-bit filter:

• New entries are inserted as “cold”.
• On access, an entry is marked “hot” via a single bit.
• Eviction scans from the FIFO head:
  • hot entry: clear bit and give it one more pass
  • cold entry: evict immediately

This creates low-cost second-chance behavior without maintaining full LRU order.

Core Data Structures (Typical)

• Hash index K -> EntryMeta
• FIFO queue for insertion/eviction order
• One hot/cold bit per entry

Complexity & Overhead

• Access path is O(1): bit set only (no relinking)
• Eviction is amortized O(1) with queue head advancement
• Metadata is minimal: queue links/indices + one bit

Notes For CacheKit

• Aligns well with contiguous storage and index-based handles.
• Attractive for high-throughput paths where LRU relinking is too expensive.
• Benchmark against S3-FIFO, Clock, and LRU on scan-heavy mixes.

References

• Zhang et al. (2023): “SIEVE is Simpler than LRU: an Efficient Turn-Key Eviction Algorithm for Web Caches”, in Proceedings of the ACM on Measurement and Analysis of Computing Systems (POMACS).
• Wikipedia (taxonomy context): https://en.wikipedia.org/wiki/Cache_replacement_policies