: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.
Python ab-testingai-analyticsanalyticscdpdata-warehouseexperimentsfeature-flagsjavascriptproduct-analyticspythonreactsession-replaysurveystypescriptweb-analytics
//! [`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);
}
}