← Stale-While-Revalidate Cache cachingmedium ready

Problem

Stale-While-Revalidate Cache (Rust)

Topics: caching, background refresh, request coalescing, concurrency

Problem

Implement a stale-while-revalidate cache. Each entry is fresh for fresh, then stale for a further stale window, then expired. The point: never block a caller on a refresh while a usable value exists, and never stampede the origin (CDN/HTTP stale-while-revalidate).

pub struct Swr { /* … */ }
impl Swr {
    pub fn new(fresh: Duration, stale: Duration,
               load: impl Fn(&str) -> i32 + Send + Sync + 'static) -> Self;
    pub fn get(&self, key: &str) -> i32;
    pub fn wait(&self);   // test helper: block until background refreshes finish
}

get(key):

fresh → return the cached value; do not call load.
stale → return the stale value immediately, and trigger one background refresh for that key (further stale gets while it runs do not start another — dedup).
expired / missing → call load synchronously, store, and return it.

Key concepts

Two deadlines per entry: fresh_until = now + fresh, stale_until = fresh_until + stale.
Async revalidate: the stale path serves the old value and refreshes in a thread, so the caller never waits.
Dedup: a refreshing: HashSet ensures at most one in-flight refresh per key — the thundering-herd guard.
inflight + Condvar: count background refreshes so wait can block until they finish (the Mutex/Condvar pair stands in for a wait group).

The struct, new, store, and wait are provided; you implement get and spawn_refresh.

Grading

Your solution.rs is compiled together with a trusted tests.rs (which include!s it) using rustc --test. Only solution.rs is yours to edit.

Sign in to submit your solution.

Leaderboard score: lower is better, 1.0 ≈ reference

#	Name	score	ns/op	allocs

Output

No submission yet.

use std::collections::{HashMap, HashSet};
use std::sync::{Arc, Condvar, Mutex};
use std::thread;
use std::time::{Duration, Instant};

// Stale-while-revalidate: each entry is *fresh* for `fresh`, then *stale* for a
// further `stale` window, then expired. A get:
//   - fresh  -> return the cached value, no load;
//   - stale  -> return the stale value immediately AND kick off a single
//               background refresh (deduped per key);
//   - expired/missing -> load synchronously.
// It's the CDN/HTTP `stale-while-revalidate` pattern: never block on a refresh
// while a usable value exists, and never stampede the origin.
//
// The struct, `new`, `store`, and `wait` are provided; implement `get` and
// `spawn_refresh` (a thread that reloads, restamps the entry, clears the
// refreshing flag, decrements `inflight`, and notifies `done`).

struct Item {
    val: i32,
    fresh_until: Instant,
    stale_until: Instant,
}

struct Inner {
    items: HashMap<String, Item>,
    refreshing: HashSet<String>,
    inflight: usize,
}

pub struct Swr {
    fresh: Duration,
    stale: Duration,
    load: Arc<dyn Fn(&str) -> i32 + Send + Sync>,
    inner: Arc<Mutex<Inner>>,
    done: Arc<Condvar>,
}

impl Swr {
    pub fn new(
        fresh: Duration,
        stale: Duration,
        load: impl Fn(&str) -> i32 + Send + Sync + 'static,
    ) -> Self {
        Swr {
            fresh,
            stale,
            load: Arc::new(load),
            inner: Arc::new(Mutex::new(Inner {
                items: HashMap::new(),
                refreshing: HashSet::new(),
                inflight: 0,
            })),
            done: Arc::new(Condvar::new()),
        }
    }

pub fn get(&self, key: &str) -> i32 {
        let _ = key;
        unimplemented!()
    }

/// Waits for all in-flight background refreshes to finish (test helper).
    pub fn wait(&self) {
        let mut inner = self.inner.lock().unwrap();
        while inner.inflight > 0 {
            inner = self.done.wait(inner).unwrap();
        }
    }

fn store(&self, key: &str, val: i32) -> i32 {
        let now = Instant::now();
        let mut inner = self.inner.lock().unwrap();
        inner.items.insert(
            key.to_string(),
            Item {
                val,
                fresh_until: now + self.fresh,
                stale_until: now + self.fresh + self.stale,
            },
        );
        val
    }

fn spawn_refresh(&self, key: String) {
        let _ = key;
        unimplemented!()
    }
}