Skip to content

:hedgehog: PostHog is the leading platform for building self-driving products. Our developer tools – AI observability, analytics, session replay, flags, experiments, error tracking, logs, and more – capture all the context agents need to diagnose problems, uncover opportunities, and ship fixes. Steer it all from Slack, web, desktop, or the MCP.

16.7 KB
Raw Blame
//! [`EvictionQueue`]: the deadline-ordered queue the sweep drains soonest-first.
//!
//! A worker schedules each live behavioral key; the sweep drains keys whose deadline has passed.
//! The timer is in [`super::scheduler`].
//!
//! # Why a `BTreeMap` + reverse index, not `BinaryHeap` + epoch map
//!
//! A key's deadline can move *earlier*, not just later: `daily_eviction_deadline`
//! (`stage1/daily.rs`) returns the boundary of the **oldest non-zero bucket**, so a late event
//! landing in a bucket older than the current oldest pulls the deadline backward. With a
//! lazily-deleted heap, an earlier-reschedule leaves the superseded, far-future entry in the heap
//! until its stale deadline eventually surfaces — up to the window length (≤180 days). Those
//! accumulate and `heap.len()` grows with total reschedules while the live-key count stays flat: an
//! unbounded leak unless you add compaction, and the natural compaction (store the live coordinate
//! so you can find and remove the old one) *is* this shape.
//!
//! A `BTreeMap<(deadline_ms, seq), K>` keyed by `(deadline, seq)` is ordered, so the soonest-due key
//! is `first_key_value`; a `HashMap<K, (deadline_ms, seq)>` reverse index lets a reschedule remove
//! the superseded entry **precisely** in `O(log n)`, in either direction. `len()` therefore always
//! equals the live-key count, and the staleness problem class disappears. `K` needs no `Ord` (it is
//! the map *value*); `seq` is a global monotonic tiebreaker that only disambiguates two live keys
//! sharing a deadline, giving a deterministic selection order.

use std::collections::{BTreeMap, HashMap};
use std::hash::Hash;

/// The ordered coordinate of a live entry: its deadline (epoch ms) plus a monotonic tiebreaker.
/// `Copy`, so it is cheaply read out of the reverse index before a mutating call.
type Coord = (i64, u64);

/// A deadline-ordered queue of keys, drained soonest-first by [`due_keys`](Self::due_keys) +
/// [`take_due`](Self::take_due).
///
/// Single-threaded by design: each partition worker owns one `EvictionQueue<BehavioralKey>` and is
/// the only mutator, so no internal synchronization is needed. Generic over `K` purely so the
/// structure can be unit-tested in isolation from `BehavioralKey`.
///
/// Invariant, upheld by every method: `by_deadline` and `index` hold exactly the same set of keys,
/// so `by_deadline.len() == index.len() == ` the live-key count, and each key maps to exactly one
/// coordinate in both directions.
pub struct EvictionQueue<K> {
    /// Keys ordered by `(deadline_ms, seq)`, so the front of the map is always the soonest due. `seq`
    /// only breaks ties between equal deadlines.
    by_deadline: BTreeMap<Coord, K>,
    /// Reverse index `K → its live coordinate`, so a reschedule (or [`cancel`](Self::cancel)) removes
    /// the superseded `by_deadline` entry precisely in `O(log n)` instead of leaving it to surface
    /// stale later.
    index: HashMap<K, Coord>,
    /// Global monotonic tiebreaker handed to each scheduled entry. `u64` never realistically wraps:
    /// even at a billion schedules a second it lasts ~580 years.
    next_seq: u64,
}

impl<K> EvictionQueue<K>
where
    K: Hash + Eq + Clone,
{
    pub fn new() -> Self {
        Self {
            by_deadline: BTreeMap::new(),
            index: HashMap::new(),
            next_seq: 0,
        }
    }

    /// Schedule `key` to evict at `deadline_ms`, or reschedule it if already present. A reschedule
    /// removes the previous entry first (precise supersede), so the queue holds exactly one
    /// coordinate per key whether the new deadline is later **or earlier** — and `len()` never grows
    /// with reschedules.
    pub fn schedule(&mut self, key: K, deadline_ms: i64) {
        if let Some(&old_coord) = self.index.get(&key) {
            self.by_deadline.remove(&old_coord);
        }
        let coord = (deadline_ms, self.next_seq);
        self.next_seq += 1;
        self.by_deadline.insert(coord, key.clone());
        self.index.insert(key, coord);
    }

    /// The soonest-due keys whose deadline is **strictly before** `due_before_ms`, in pop order, at
    /// most `limit` of them — **without removing any of them**. Selection and removal are split so
    /// the queue stays the single source of truth for a key's deadline while a sweep pass is in
    /// flight: a selected key an event reschedules or a merge cancels is simply no longer claimable
    /// by [`take_due`](Self::take_due), instead of sitting in a copy that has to be reconciled.
    ///
    /// The cutoff is `due_before_ms = now_ms − safety_margin_ms`, computed by the caller (see
    /// [`due_before_ms`](super::scheduler::due_before_ms)) so the queue stays clock- and
    /// arithmetic-free.
    pub fn due_keys(&self, due_before_ms: i64, limit: usize) -> impl Iterator<Item = &K> + '_ {
        // `seq` is unsigned, so `(due_before_ms, 0)` is the least coordinate at the cutoff: the range
        // is exactly the strictly-earlier deadlines.
        self.by_deadline
            .range(..(due_before_ms, 0))
            .map(|(_, key)| key)
            .take(limit)
    }

    /// Remove `key` only if its **current** deadline is still strictly before `due_before_ms`,
    /// returning that deadline so a failed batch can put the key back where it was. [`None`] when the
    /// key was cancelled or rescheduled to or past the cutoff since it was selected, in which case it
    /// stays queued on its live deadline.
    pub fn take_due(&mut self, key: &K, due_before_ms: i64) -> Option<i64> {
        let &coord = self.index.get(key)?;
        let (deadline_ms, _) = coord;
        if deadline_ms >= due_before_ms {
            return None;
        }
        self.by_deadline
            .remove(&coord)
            .expect("the indexed coordinate is present");
        self.index.remove(key);
        Some(deadline_ms)
    }

    /// Remove `key` from the queue, if present, so its pending eviction never fires.
    pub fn cancel(&mut self, key: &K) {
        if let Some(coord) = self.index.remove(key) {
            self.by_deadline.remove(&coord);
        }
    }

    /// The soonest live deadline, or [`None`] when empty. For observability.
    pub fn peek_next_deadline(&self) -> Option<i64> {
        self.by_deadline
            .keys()
            .next()
            .map(|&(deadline, _)| deadline)
    }

    /// The number of live keys.
    pub fn len(&self) -> usize {
        self.by_deadline.len()
    }

    pub fn is_empty(&self) -> bool {
        self.by_deadline.is_empty()
    }
}

impl<K> Default for EvictionQueue<K>
where
    K: Hash + Eq + Clone,
{
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// Select the soonest due key and claim it, the two-step the sweep runs. `None` when nothing is
    /// due — the shape the scheduling tests below assert against.
    fn claim_soonest_due<K: Hash + Eq + Clone>(
        queue: &mut EvictionQueue<K>,
        due_before_ms: i64,
    ) -> Option<(K, i64)> {
        let key = queue.due_keys(due_before_ms, 1).next()?.clone();
        let deadline = queue
            .take_due(&key, due_before_ms)
            .expect("a key selected as due is claimable when nothing intervened");
        Some((key, deadline))
    }

    fn drain<K: Hash + Eq + Clone>(
        queue: &mut EvictionQueue<K>,
        due_before_ms: i64,
    ) -> Vec<(K, i64)> {
        let mut out = Vec::new();
        while let Some(entry) = claim_soonest_due(queue, due_before_ms) {
            out.push(entry);
        }
        out
    }

    #[test]
    fn due_boundary_triple() {
        // Strict `<`, on both halves of the pair: at the exact cutoff and beyond, the key is neither
        // selected nor claimable; one ms before, it is both.
        let due_before = 1_000;
        for (deadline, should_evict) in [
            (due_before - 1, true),
            (due_before, false),
            (due_before + 1, false),
        ] {
            let mut queue = EvictionQueue::new();
            queue.schedule("k", deadline);
            assert_eq!(
                queue.due_keys(due_before, 16).count(),
                usize::from(should_evict),
                "selection: deadline {deadline} vs due_before {due_before}",
            );
            assert_eq!(
                queue.take_due(&"k", due_before).is_some(),
                should_evict,
                "claim: deadline {deadline} vs due_before {due_before}",
            );
            assert_eq!(queue.len(), if should_evict { 0 } else { 1 });
        }
    }

    #[test]
    fn take_due_refuses_a_key_rescheduled_past_the_cutoff_since_selection() {
        // The freshness guarantee the split buys: a key selected as due, then pushed past the cutoff
        // by an intervening event, is not claimable and stays queued on its live deadline.
        let mut queue = EvictionQueue::new();
        queue.schedule("k", 100);
        let selected: Vec<&str> = queue.due_keys(200, 16).copied().collect();
        assert_eq!(selected, vec!["k"]);

        queue.schedule("k", 900); // a late event slid the window forward
        assert_eq!(queue.take_due(&"k", 200), None);
        assert_eq!(queue.len(), 1, "the refused key stays queued");
        assert_eq!(queue.peek_next_deadline(), Some(900));
    }

    #[test]
    fn take_due_refuses_a_key_cancelled_since_selection() {
        // The other half: a merge cancels the key between selection and claim, so the claim finds
        // nothing and the eviction never fires.
        let mut queue = EvictionQueue::new();
        queue.schedule("k", 100);
        assert_eq!(queue.due_keys(200, 16).count(), 1);

        queue.cancel(&"k");
        assert_eq!(queue.take_due(&"k", 200), None);
        assert_eq!(queue.len(), 0);
    }

    #[test]
    fn due_keys_stops_at_the_limit_without_removing_anything() {
        let mut queue = EvictionQueue::new();
        for (key, deadline) in [("a", 100), ("b", 200), ("c", 300)] {
            queue.schedule(key, deadline);
        }
        let selected: Vec<&str> = queue.due_keys(1_000, 2).copied().collect();
        assert_eq!(
            selected,
            vec!["a", "b"],
            "soonest first, capped at the limit"
        );
        assert_eq!(queue.len(), 3, "selection removes nothing");

        // Selecting again returns the same keys, so a pass that abandons its candidates loses none.
        let again: Vec<&str> = queue.due_keys(1_000, 2).copied().collect();
        assert_eq!(again, selected);
    }

    #[test]
    fn reschedule_to_later_pops_once_at_the_later_deadline() {
        let mut queue = EvictionQueue::new();
        queue.schedule("k", 100);
        queue.schedule("k", 500); // window slid forward
        assert_eq!(queue.len(), 1, "reschedule must not duplicate the key");

        // Nothing due at the original deadline anymore.
        assert_eq!(claim_soonest_due(&mut queue, 101), None);
        assert_eq!(queue.len(), 1);

        assert_eq!(claim_soonest_due(&mut queue, 501), Some(("k", 500)));
        assert_eq!(queue.len(), 0);
        assert_eq!(claim_soonest_due(&mut queue, 501), None);
    }

    #[test]
    fn reschedule_to_earlier_leaves_no_stale_entry() {
        // The regression that motivates the BTreeMap: an earlier reschedule must remove the old
        // far-future entry, so the key pops once at the earlier deadline and `len()` returns to 0.
        let mut queue = EvictionQueue::new();
        queue.schedule("k", 10_000); // far-future
        queue.schedule("k", 200); // late event in an older bucket pulls it earlier
        assert_eq!(queue.len(), 1);

        assert_eq!(claim_soonest_due(&mut queue, 201), Some(("k", 200)));
        assert_eq!(
            queue.len(),
            0,
            "the superseded far-future entry must not linger",
        );
        // Draining far past the old far-future deadline yields nothing — proof it is gone.
        assert_eq!(claim_soonest_due(&mut queue, 1_000_000), None);
        assert_eq!(queue.peek_next_deadline(), None);
    }

    #[test]
    fn cancel_removes_the_key_so_it_never_pops() {
        let mut queue = EvictionQueue::new();
        queue.schedule("k", 100);
        queue.cancel(&"k");
        assert_eq!(queue.len(), 0);
        assert!(queue.is_empty());
        assert_eq!(claim_soonest_due(&mut queue, 1_000_000), None);

        // Cancelling an absent key is a no-op.
        queue.cancel(&"missing");
        assert_eq!(queue.len(), 0);
    }

    #[test]
    fn cancel_only_removes_the_named_key() {
        let mut queue = EvictionQueue::new();
        queue.schedule("a", 100);
        queue.schedule("b", 200);
        queue.cancel(&"a");
        assert_eq!(queue.len(), 1);
        assert_eq!(claim_soonest_due(&mut queue, 1_000), Some(("b", 200)));
    }

    #[test]
    fn resurrection_after_pop_pops_again_at_the_new_deadline() {
        let mut queue = EvictionQueue::new();
        queue.schedule("k", 100);
        assert_eq!(claim_soonest_due(&mut queue, 101), Some(("k", 100)));
        assert_eq!(queue.len(), 0);

        queue.schedule("k", 900);
        assert_eq!(queue.len(), 1);
        assert_eq!(
            claim_soonest_due(&mut queue, 200),
            None,
            "not due at the old deadline"
        );
        assert_eq!(claim_soonest_due(&mut queue, 901), Some(("k", 900)));
        assert_eq!(queue.len(), 0);
    }

    #[test]
    fn equal_deadlines_pop_in_insertion_order() {
        // `seq` makes a shared deadline deterministic: FIFO by schedule order.
        let mut queue = EvictionQueue::new();
        for key in ["a", "b", "c", "d"] {
            queue.schedule(key, 500);
        }
        let drained = drain(&mut queue, 501);
        assert_eq!(
            drained,
            vec![("a", 500), ("b", 500), ("c", 500), ("d", 500)],
        );
        assert_eq!(queue.len(), 0);
    }

    #[test]
    fn selection_is_in_deadline_then_seq_order() {
        let mut queue = EvictionQueue::new();
        // Insert out of deadline order, with a tie at 200.
        queue.schedule("late", 300);
        queue.schedule("tie_first", 200);
        queue.schedule("early", 100);
        queue.schedule("tie_second", 200);

        let selected: Vec<&str> = queue.due_keys(1_000, usize::MAX).copied().collect();
        assert_eq!(
            selected,
            vec!["early", "tie_first", "tie_second", "late"],
            "one selection pass already yields the drain order",
        );

        let drained = drain(&mut queue, 1_000);
        assert_eq!(
            drained,
            vec![
                ("early", 100),
                ("tie_first", 200),
                ("tie_second", 200),
                ("late", 300),
            ],
        );
    }

    #[test]
    fn peek_next_deadline_tracks_the_soonest_live_deadline() {
        let mut queue = EvictionQueue::new();
        assert_eq!(queue.peek_next_deadline(), None);

        queue.schedule("a", 500);
        assert_eq!(queue.peek_next_deadline(), Some(500));

        queue.schedule("b", 200);
        assert_eq!(queue.peek_next_deadline(), Some(200));

        queue.schedule("b", 900);
        assert_eq!(queue.peek_next_deadline(), Some(500));

        queue.cancel(&"a");
        assert_eq!(queue.peek_next_deadline(), Some(900));

        assert_eq!(claim_soonest_due(&mut queue, 1_000), Some(("b", 900)));
        assert_eq!(queue.peek_next_deadline(), None);
    }

    #[test]
    fn very_negative_due_before_holds_everything_without_panic() {
        // The caller's saturating `now − margin` (now small, margin huge) yields a far-negative
        // cutoff. Both halves of the pair are arithmetic-free comparisons, so they hold every real
        // (positive) deadline — the safe "nothing due" direction — and never panic. See
        // `scheduler::tests::due_before_saturates_when_margin_exceeds_now`.
        let mut queue = EvictionQueue::new();
        queue.schedule("k", 1);
        let cutoff = 0_i64.saturating_sub(i64::MAX);
        assert_eq!(queue.due_keys(cutoff, usize::MAX).count(), 0);
        assert_eq!(queue.due_keys(i64::MIN, usize::MAX).count(), 0);
        assert_eq!(queue.take_due(&"k", cutoff), None);
        assert_eq!(queue.take_due(&"k", i64::MIN), None);
        assert_eq!(queue.len(), 1);
    }

    #[test]
    fn partial_drain_leaves_not_yet_due_keys() {
        let mut queue = EvictionQueue::new();
        queue.schedule("a", 100);
        queue.schedule("b", 200);
        queue.schedule("c", 300);

        let drained = drain(&mut queue, 250);
        assert_eq!(drained, vec![("a", 100), ("b", 200)]);
        assert_eq!(queue.len(), 1);
        assert_eq!(queue.peek_next_deadline(), Some(300));
    }

    #[test]
    fn default_is_empty() {
        let queue: EvictionQueue<&str> = EvictionQueue::default();
        assert!(queue.is_empty());
        assert_eq!(queue.len(), 0);
        assert_eq!(queue.peek_next_deadline(), None);
    }
}