: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
//! Per-key ordered deferral, extracted from the shape proven in
//! `ingestion-consumer`'s stash and adopted by the personhog router's.
//!
//! Both services face the same problem one layer apart: work is pinned to
//! a key-sticky target (a worker, an owner pod) that is temporarily
//! unroutable, and per-key ordering must survive the outage — including
//! across *failed delivery attempts*. The queue makes that survivable by
//! construction rather than by choreography:
//!
//! - Every entry is stamped with a monotonic sequence at admission, so an
//! entry's position is a property of the entry, not of queue physics. A
//! failed attempt cannot corrupt order because putting an entry back
//! restores it to its sequence position.
//! - Entries leave only through [`KeyedStash::complete`] — a
//! definitive outcome. An attempt that cannot finish puts its entries
//! back and they will be re-attempted first, in order.
//! - [`KeyedStash::is_deferring`] is the outstanding gate: while a
//! key has queued or in-attempt entries, new work for that key must be
//! deferred behind them — never sent directly — or it would race ahead
//! of the backlog.
//!
//! Deliberately single-owner (`&mut self`) and free of I/O, locking, and
//! policy: callers wrap it in their own concurrency envelope and layer
//! their own admission bounds, batch accounting, or reply plumbing on
//! top, exactly as the two existing stashes do.
use std::collections::{HashMap, VecDeque};
use std::hash::Hash;
/// One deferred entry: the caller's item plus the admission-order stamp
/// that fixes its position among its key's entries forever.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Entry<T> {
pub seq: u64,
pub item: T,
}
/// A per-key ordered deferral queue. See the crate docs for the contract.
#[derive(Debug)]
pub struct KeyedStash<K, T> {
queues: HashMap<K, VecDeque<Entry<T>>>,
/// Per key: entries taken for an attempt and not yet completed or put
/// back. Counted so `is_deferring` covers in-flight work, not just
/// queued work.
in_attempt: HashMap<K, usize>,
next_seq: u64,
len: usize,
}
impl<K, T> Default for KeyedStash<K, T> {
fn default() -> Self {
Self {
queues: HashMap::new(),
in_attempt: HashMap::new(),
next_seq: 0,
len: 0,
}
}
}
impl<K: Eq + Hash + Clone, T> KeyedStash<K, T> {
pub fn new() -> Self {
Self::default()
}
/// Defer `item` behind everything already deferred for `key`.
/// Returns the entry's sequence stamp.
pub fn push(&mut self, key: K, item: T) -> u64 {
let seq = self.next_seq;
self.next_seq += 1;
self.queues
.entry(key)
.or_default()
.push_back(Entry { seq, item });
self.len += 1;
seq
}
/// Whether new work for `key` must be deferred: the key has queued
/// entries, or entries taken for an attempt whose outcome is not yet
/// known. Sending new work directly while this holds would let it
/// race ahead of the key's backlog.
pub fn is_deferring(&self, key: &K) -> bool {
self.has_in_attempt(key) || self.queues.get(key).is_some_and(|q| !q.is_empty())
}
/// Whether `key` has entries taken for an attempt and not yet completed or put back.
pub fn has_in_attempt(&self, key: &K) -> bool {
self.in_attempt.get(key).is_some_and(|n| *n > 0)
}
/// Take up to `max` entries from the front of `key`'s queue for a
/// delivery attempt. The entries count as in-attempt until each is
/// either [`complete`](Self::complete)d or returned via
/// [`put_back`](Self::put_back); dropping them instead loses items
/// and permanently latches `is_deferring` for the key.
pub fn take_front(&mut self, key: &K, max: usize) -> Vec<Entry<T>> {
let Some(queue) = self.queues.get_mut(key) else {
return Vec::new();
};
let n = max.min(queue.len());
let taken: Vec<Entry<T>> = queue.drain(..n).collect();
if queue.is_empty() {
self.queues.remove(key);
}
if !taken.is_empty() {
*self.in_attempt.entry(key.clone()).or_default() += taken.len();
self.len -= taken.len();
}
taken
}
/// Record a definitive outcome for one in-attempt entry of `key` —
/// delivered, or failed in a way that was reported to its origin.
/// The entry is gone; its successors may now be attempted.
pub fn complete(&mut self, key: &K) {
let count = self
.in_attempt
.get_mut(key)
.expect("complete() without a matching take_front()");
*count -= 1;
if *count == 0 {
self.in_attempt.remove(key);
}
}
/// Return entries whose attempt was aborted before any outcome
/// existed (supersession, a target that became unroutable). They
/// re-enter at their sequence positions — ahead of everything
/// admitted after them — so the next attempt sees them first, in
/// order.
pub fn put_back(&mut self, key: &K, entries: Vec<Entry<T>>) {
if entries.is_empty() {
return;
}
let count = self
.in_attempt
.get_mut(key)
.expect("put_back() without a matching take_front()");
*count -= entries.len();
if *count == 0 {
self.in_attempt.remove(key);
}
self.len += entries.len();
let queue = self.queues.entry(key.clone()).or_default();
// Taken entries always predate everything still queued, so they
// belong at the front; restoring in reverse preserves their
// internal order. The debug assertion pins the seq invariant the
// fast path relies on.
debug_assert!(
queue
.front()
.is_none_or(|next| entries.last().is_none_or(|e| e.seq < next.seq)),
"put_back entries must predate every queued entry"
);
for entry in entries.into_iter().rev() {
queue.push_front(entry);
}
}
/// Keys that currently have queued entries, in no particular order.
/// In-attempt-only keys are excluded: their next attempt is decided
/// by the outcome of the current one.
pub fn keys_with_backlog(&self) -> impl Iterator<Item = &K> {
self.queues.keys()
}
/// Keys for which [`is_deferring`](Self::is_deferring) holds; a key
/// with both queued and in-attempt entries may appear twice.
pub fn deferring_keys(&self) -> impl Iterator<Item = &K> {
self.queues.keys().chain(self.in_attempt.keys())
}
/// Total queued entries across all keys (in-attempt entries are not
/// queued).
pub fn len(&self) -> usize {
self.len
}
pub fn is_empty(&self) -> bool {
self.len == 0 && self.in_attempt.is_empty()
}
}
#[cfg(test)]
mod tests {
use std::collections::HashSet;
use super::*;
use proptest::prelude::*;
/// The outstanding gate covers both queued and in-attempt work: a key
/// stays "deferring" from first push until the last outcome, never
/// dropping out in between — the window where new work could race
/// ahead of a retry.
#[test]
fn the_gate_holds_across_the_attempt_window() {
let mut q: KeyedStash<u8, u32> = KeyedStash::new();
assert!(!q.is_deferring(&1));
q.push(1, 10);
assert!(q.is_deferring(&1));
let taken = q.take_front(&1, 8);
assert_eq!(taken.len(), 1);
assert!(q.is_deferring(&1), "in-attempt work must keep the gate up");
q.put_back(&1, taken);
assert!(q.is_deferring(&1));
let taken = q.take_front(&1, 8);
q.complete(&1);
assert!(!q.is_deferring(&1));
drop(taken);
}
/// Put-back restores aborted entries ahead of work admitted after
/// them — the leapfrog case: a retry must never be overtaken by a
/// newer same-key item.
#[test]
fn put_back_precedes_later_admissions() {
let mut q: KeyedStash<u8, &str> = KeyedStash::new();
q.push(1, "a");
q.push(1, "b");
let taken = q.take_front(&1, 2);
q.push(1, "c");
q.put_back(&1, taken);
let order: Vec<&str> = q.take_front(&1, 8).into_iter().map(|e| e.item).collect();
assert_eq!(order, vec!["a", "b", "c"]);
}
/// Model-based property check: against an arbitrary interleaving of
/// push / take / complete / put_back across several keys, delivery
/// order per key equals admission order per key (completions observe
/// strictly increasing seqs), and every admitted item is exactly once
/// delivered or still held. This is the invariant that makes internal
/// retry safe to build on top.
#[derive(Debug, Clone)]
enum Op {
Push { key: u8 },
AttemptDeliver { key: u8, max: u8 },
AttemptAbort { key: u8, max: u8 },
}
fn op_strategy() -> impl Strategy<Value = Op> {
prop_oneof![
(0u8..4).prop_map(|key| Op::Push { key }),
(0u8..4, 1u8..5).prop_map(|(key, max)| Op::AttemptDeliver { key, max }),
(0u8..4, 1u8..5).prop_map(|(key, max)| Op::AttemptAbort { key, max }),
]
}
proptest! {
#[test]
fn per_key_order_and_conservation_hold(ops in proptest::collection::vec(op_strategy(), 1..120)) {
let mut q: KeyedStash<u8, u64> = KeyedStash::new();
let mut admitted: HashMap<u8, u64> = HashMap::new();
let mut delivered: HashMap<u8, Vec<u64>> = HashMap::new();
let mut admitted_total = 0u64;
for op in ops {
match op {
Op::Push { key } => {
let n = admitted.entry(key).or_default();
q.push(key, *n);
*n += 1;
admitted_total += 1;
}
Op::AttemptDeliver { key, max } => {
let taken = q.take_front(&key, max as usize);
let mut last_seq = None;
for entry in taken {
prop_assert!(last_seq.is_none_or(|s| s < entry.seq));
last_seq = Some(entry.seq);
delivered.entry(key).or_default().push(entry.item);
q.complete(&key);
}
}
Op::AttemptAbort { key, max } => {
let taken = q.take_front(&key, max as usize);
q.put_back(&key, taken);
}
}
let deferring: HashSet<u8> = q.deferring_keys().copied().collect();
for k in 0u8..4 {
prop_assert_eq!(deferring.contains(&k), q.is_deferring(&k));
}
}
// Per-key delivery order == admission order.
for (key, items) in &delivered {
let expected: Vec<u64> = (0..items.len() as u64).collect();
prop_assert_eq!(items, &expected, "key {} delivered out of order", key);
}
// Conservation: everything admitted is delivered or still queued.
let delivered_total: usize = delivered.values().map(Vec::len).sum();
prop_assert_eq!(delivered_total + q.len(), admitted_total as usize);
}
}
}