Skip to content

s3-fifo.md

Latest commit

 

History

History
161 lines (128 loc) · 5.48 KB

s3-fifo.md

File metadata and controls

161 lines (128 loc) · 5.48 KB

S3-FIFO

Feature: policy-s3-fifo

Goal

Achieve scan resistance with O(1) operations using simple FIFO queues and minimal metadata.

Core Idea

S3-FIFO (Simple, Scalable, Scan-resistant FIFO) uses three FIFO queues to filter one-hit wonders and protect frequently accessed items:

  • Small (S): FIFO queue for newly inserted items
  • Main (M): FIFO queue for items that were accessed while in Small
  • Ghost (G): Bounded list tracking recently evicted keys (no values)

Behavior:

  • New items go to Small with frequency counter = 0
  • Accessing an item increments its frequency (capped at 3)
  • When evicting from Small:
    • If freq > 0: promote to Main (reset freq to 0)
    • If freq == 0: evict and record key in Ghost
  • When evicting from Main:
    • If freq > 0: reinsert at Main head (decrement freq)
    • If freq == 0: evict
  • Ghost-guided admission: if inserting a key that's in Ghost, insert to Main (not Small)

Core Data Structures

┌─────────────────────────────────────────────────────────────────────────┐
│  index: HashMap<K, NodePtr>                                             │
│  ┌──────────┬──────────┐                                                │
│  │   Key    │ NodePtr  │                                                │
│  └──────────┴──────────┘                                                │
│                                                                         │
│  Small Queue (FIFO):   head ──► [new] ◄──► [old] ◄── tail (evict)      │
│  Main Queue (FIFO):    head ──► [hot] ◄──► [cold] ◄── tail (evict)     │
│  Ghost List:           Tracks recently evicted keys                     │
└─────────────────────────────────────────────────────────────────────────┘

Each node stores:

  • Key, Value
  • Frequency counter (2 bits, 0-3)
  • Queue indicator (Small or Main)
  • Doubly-linked list pointers

Operations

Insert

insert(key, value):
  1. Key exists? → Update value, increment freq
  2. Key in Ghost? → Insert to Main (ghost-guided admission)
  3. Otherwise → Insert to Small
  4. Evict if over capacity

Get

get(key):
  1. Lookup in index → not found? return None
  2. Increment freq (capped at 3)
  3. Return &value

Eviction

evict_if_needed():
  while len > capacity:
    1. Pop from Small tail:
       - If freq > 0: promote to Main head, reset freq
       - If freq == 0: evict, record in Ghost
    2. If Small empty, pop from Main tail:
       - If freq > 0: reinsert to Main head, decrement freq
       - If freq == 0: evict

Complexity & Overhead

  • O(1) all operations (insert, get, evict)
  • Per-entry overhead: ~2 pointers + 1 byte (freq + queue flag)
  • Ghost list adds memory for tracking evicted keys (keys only, no values)

Comparison with Other Policies

Aspect S3-FIFO LRU 2Q
Scan resistance Excellent Poor Good
Get complexity O(1) O(1)* O(1)
Per-access work Increment freq Move to head Maybe promote
Memory overhead Low Medium Medium
Implementation Simple Complex lists Two lists

* LRU requires pointer updates on every access

Configuration Parameters

Parameter Default Description
small_ratio 0.1 Fraction of capacity for Small queue
ghost_ratio 0.9 Fraction of capacity for Ghost list

Typical values:

  • small_ratio: 0.1 (10%) works well for most workloads
  • ghost_ratio: 0.5-1.0 depending on memory budget

When to Use

Best for:

  • CDN edge caches with mixed popularity
  • Database buffer pools with occasional scans
  • Web caches with long-tail access patterns
  • Any workload where scans shouldn't pollute the cache

Avoid when:

  • Access patterns are purely recency-based (use LRU)
  • Strict frequency ordering is needed (use LFU)
  • Memory is extremely constrained (Ghost list adds overhead)

Example Usage

use cachekit::policy::s3_fifo::S3FifoCache;
use cachekit::traits::CoreCache;

// Create S3-FIFO cache with 100 capacity
let mut cache = S3FifoCache::new(100);

// Or with custom ratios
let mut cache = S3FifoCache::with_ratios(100, 0.1, 0.9);

// Insert items (go to Small queue)
cache.insert("page1", "content1");
cache.insert("page2", "content2");

// Access promotes frequency
cache.get(&"page1");

// Hot items survive scans
for i in 0..200 {
    cache.insert(format!("scan_{}", i), "data");
}

// "page1" likely survived (was accessed)
assert!(cache.contains(&"page1"));

Using the Builder

use cachekit::builder::{CacheBuilder, CachePolicy};

let mut cache = CacheBuilder::new(100).build::<u64, String>(
    CachePolicy::S3Fifo {
        small_ratio: 0.1,
        ghost_ratio: 0.9,
    }
);

References

  • Yang et al., "FIFO queues are all you need for cache eviction", SOSP 2023
  • https://s3fifo.com/