: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
use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::fmt;
use std::num::NonZeroUsize;
use std::time::Duration;
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
use serde::Serialize;
use tokio::sync::mpsc;
use super::ops::{
DispatchedOperation, NanosSincePhaseStart, OpClass, OpDescriptor, OperationId, PhaseId,
PhaseMismatch, TimestampOrderError,
};
use super::rates::{FeedMode, RatePerSecond, RateSpec};
const NANOS_PER_SECOND: f64 = 1_000_000_000.0;
const CLASS_SEED_MIX: u64 = 0x9e37_79b9_7f4a_7c15;
#[derive(Debug)]
struct ClassSchedule {
rate: RatePerSecond,
rng: StdRng,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct HeapEntry {
scheduled_at: NanosSincePhaseStart,
class: OpClass,
}
impl Ord for HeapEntry {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.scheduled_at
.as_nanos()
.cmp(&other.scheduled_at.as_nanos())
.then_with(|| self.class.cmp(&other.class))
}
}
impl PartialOrd for HeapEntry {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct ScheduledArrival {
pub class: OpClass,
pub scheduled_at: NanosSincePhaseStart,
}
#[derive(Debug)]
pub struct ArrivalSchedule {
phase_id: PhaseId,
classes: [Option<ClassSchedule>; OpClass::COUNT],
heap: BinaryHeap<Reverse<HeapEntry>>,
}
impl ArrivalSchedule {
pub fn new(phase_id: PhaseId, seed: u64, rates: &[RateSpec]) -> Result<Self, ArrivalError> {
let mut classes: [Option<ClassSchedule>; OpClass::COUNT] = std::array::from_fn(|_| None);
let mut heap = BinaryHeap::new();
let mut seen = [false; OpClass::COUNT];
for rate in rates {
let index = rate.class.index();
if seen[index] {
return Err(ArrivalError::DuplicateClass(rate.class));
}
seen[index] = true;
if !rate.target.get().is_finite() || rate.target.get() < 0.0 {
return Err(ArrivalError::InvalidRate {
class: rate.class,
rate: rate.target.get(),
});
}
if !rate.target.is_active() || rate.feed == FeedMode::Closed {
continue;
}
let class_seed =
seed ^ CLASS_SEED_MIX.wrapping_mul(u64::try_from(index + 1).unwrap_or(u64::MAX));
let mut class_schedule = ClassSchedule {
rate: rate.target,
rng: StdRng::seed_from_u64(class_seed),
};
let first_at = sample_interval_nanos(&mut class_schedule.rng, rate.target);
heap.push(Reverse(HeapEntry {
scheduled_at: NanosSincePhaseStart::from_nanos(phase_id, first_at),
class: rate.class,
}));
classes[index] = Some(class_schedule);
}
Ok(Self {
phase_id,
classes,
heap,
})
}
pub fn phase_id(&self) -> PhaseId {
self.phase_id
}
pub fn peek_next_at(&self) -> Option<NanosSincePhaseStart> {
self.heap.peek().map(|entry| entry.0.scheduled_at)
}
pub fn next_arrival(&mut self) -> Option<ScheduledArrival> {
let Reverse(entry) = self.heap.pop()?;
self.advance(entry);
Some(ScheduledArrival {
class: entry.class,
scheduled_at: entry.scheduled_at,
})
}
pub fn pop_due(
&mut self,
now: NanosSincePhaseStart,
) -> Result<Option<ScheduledArrival>, ArrivalError> {
if now.phase_id() != self.phase_id {
return Err(ArrivalError::PhaseMismatch(PhaseMismatch {
expected: self.phase_id,
actual: now.phase_id(),
}));
}
let Some(next_at) = self.peek_next_at() else {
return Ok(None);
};
if next_at.as_nanos() > now.as_nanos() {
return Ok(None);
}
Ok(self.next_arrival())
}
fn advance(&mut self, entry: HeapEntry) {
let class_schedule = self.classes[entry.class.index()]
.as_mut()
.expect("heap entries always have class state");
let interval = sample_interval_nanos(&mut class_schedule.rng, class_schedule.rate);
let Some(next_at) = entry.scheduled_at.checked_add(interval) else {
self.classes[entry.class.index()] = None;
return;
};
self.heap.push(Reverse(HeapEntry {
scheduled_at: next_at,
class: entry.class,
}));
}
}
#[derive(Debug, Clone, PartialEq)]
pub enum ArrivalError {
PhaseMismatch(PhaseMismatch),
DuplicateClass(OpClass),
InvalidRate { class: OpClass, rate: f64 },
}
impl fmt::Display for ArrivalError {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::PhaseMismatch(error) => error.fmt(formatter),
Self::DuplicateClass(class) => write!(formatter, "duplicate rate for {class:?}"),
Self::InvalidRate { class, rate } => {
write!(formatter, "invalid arrival rate {rate} for {class:?}")
}
}
}
}
impl std::error::Error for ArrivalError {}
fn sample_interval_nanos(rng: &mut impl Rng, rate: RatePerSecond) -> u64 {
// Inverse exponential CDF; 1 - U keeps ln's input in (0, 1].
let open_unit_interval = 1.0 - rng.gen::<f64>();
let nanos = -open_unit_interval.ln() / rate.get() * NANOS_PER_SECOND;
if !nanos.is_finite() || nanos >= u64::MAX as f64 {
return u64::MAX;
}
(nanos.ceil() as u64).max(1)
}
#[derive(Debug, Clone, Copy)]
pub struct PhaseClock {
phase_id: PhaseId,
epoch: tokio::time::Instant,
}
impl PhaseClock {
pub fn new(phase_id: PhaseId, epoch: tokio::time::Instant) -> Self {
Self { phase_id, epoch }
}
pub fn start_now(phase_id: PhaseId) -> Self {
Self::new(phase_id, tokio::time::Instant::now())
}
pub fn phase_id(&self) -> PhaseId {
self.phase_id
}
pub fn now(&self) -> Result<NanosSincePhaseStart, ClockError> {
let now = tokio::time::Instant::now();
if now < self.epoch {
return Err(ClockError::BeforePhaseEpoch);
}
let elapsed = now.duration_since(self.epoch);
let nanos = u64::try_from(elapsed.as_nanos()).map_err(|_| ClockError::OutOfRange)?;
Ok(NanosSincePhaseStart::from_nanos(self.phase_id, nanos))
}
pub async fn wait_until(&self, scheduled_at: NanosSincePhaseStart) -> Result<(), ClockError> {
if scheduled_at.phase_id() != self.phase_id {
return Err(ClockError::PhaseMismatch(PhaseMismatch {
expected: self.phase_id,
actual: scheduled_at.phase_id(),
}));
}
let deadline = self
.epoch
.checked_add(Duration::from_nanos(scheduled_at.as_nanos()))
.ok_or(ClockError::OutOfRange)?;
tokio::time::sleep_until(deadline).await;
Ok(())
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ClockError {
PhaseMismatch(PhaseMismatch),
BeforePhaseEpoch,
OutOfRange,
}
impl fmt::Display for ClockError {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::PhaseMismatch(error) => error.fmt(formatter),
Self::BeforePhaseEpoch => formatter.write_str("clock precedes the phase epoch"),
Self::OutOfRange => formatter.write_str("phase timestamp is outside the timer range"),
}
}
}
impl std::error::Error for ClockError {}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
#[serde(rename_all = "snake_case")]
pub enum DispatchOutcome {
Enqueued,
Shed,
Closed,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
pub struct DispatchRecord {
pub operation_id: OperationId,
pub class: OpClass,
scheduled_at: NanosSincePhaseStart,
dispatched_at: NanosSincePhaseStart,
pub outcome: DispatchOutcome,
}
impl DispatchRecord {
pub fn scheduled_at(self) -> NanosSincePhaseStart {
self.scheduled_at
}
pub fn dispatched_at(self) -> NanosSincePhaseStart {
self.dispatched_at
}
pub fn dispatch_lag_nanos(self) -> u64 {
self.dispatched_at.as_nanos() - self.scheduled_at.as_nanos()
}
}
#[derive(Debug)]
pub struct BoundedDispatcher {
sender: mpsc::Sender<DispatchedOperation>,
shed: u64,
}
impl BoundedDispatcher {
pub fn channel(capacity: NonZeroUsize) -> (Self, mpsc::Receiver<DispatchedOperation>) {
let (sender, receiver) = mpsc::channel(capacity.get());
(Self { sender, shed: 0 }, receiver)
}
pub fn shed_count(&self) -> u64 {
self.shed
}
pub fn try_dispatch_at(
&mut self,
descriptor: OpDescriptor,
dispatched_at: NanosSincePhaseStart,
) -> Result<DispatchRecord, DispatchError> {
let operation_id = descriptor.operation_id;
let class = descriptor.class();
let scheduled_at = descriptor.scheduled_at;
let dispatched = DispatchedOperation::try_new(descriptor, dispatched_at)
.map_err(DispatchError::Timestamp)?;
let outcome = match self.sender.try_send(dispatched) {
Ok(()) => DispatchOutcome::Enqueued,
Err(mpsc::error::TrySendError::Full(_)) => {
self.shed = self.shed.saturating_add(1);
DispatchOutcome::Shed
}
Err(mpsc::error::TrySendError::Closed(_)) => DispatchOutcome::Closed,
};
Ok(DispatchRecord {
operation_id,
class,
scheduled_at,
dispatched_at,
outcome,
})
}
pub async fn dispatch_with_backpressure(
&self,
descriptor: OpDescriptor,
clock: &PhaseClock,
) -> Result<DispatchRecord, DispatchError> {
let operation_id = descriptor.operation_id;
let class = descriptor.class();
if class == OpClass::CanonicalRead {
return Err(DispatchError::ClosedLoopRead);
}
let scheduled_at = descriptor.scheduled_at;
clock
.wait_until(scheduled_at)
.await
.map_err(DispatchError::Clock)?;
let permit = match self.sender.reserve().await {
Ok(permit) => permit,
Err(_) => {
let dispatched_at = clock.now().map_err(DispatchError::Clock)?;
DispatchedOperation::try_new(descriptor, dispatched_at)
.map_err(DispatchError::Timestamp)?;
return Ok(DispatchRecord {
operation_id,
class,
scheduled_at,
dispatched_at,
outcome: DispatchOutcome::Closed,
});
}
};
let dispatched_at = clock.now().map_err(DispatchError::Clock)?;
let dispatched = DispatchedOperation::try_new(descriptor, dispatched_at)
.map_err(DispatchError::Timestamp)?;
permit.send(dispatched);
Ok(DispatchRecord {
operation_id,
class,
scheduled_at,
dispatched_at,
outcome: DispatchOutcome::Enqueued,
})
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DispatchError {
ClosedLoopRead,
Timestamp(TimestampOrderError),
Clock(ClockError),
}
impl fmt::Display for DispatchError {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::ClosedLoopRead => formatter.write_str("canonical reads must remain open-loop"),
Self::Timestamp(error) => error.fmt(formatter),
Self::Clock(error) => error.fmt(formatter),
}
}
}
impl std::error::Error for DispatchError {}
#[cfg(test)]
mod tests {
use serde_json::json;
use super::*;
use crate::benchmark::ops::{OpPayload, PersonUpsertPayload};
const PHASE: PhaseId = PhaseId::new(1);
fn open_rate(class: OpClass, target: f64) -> RateSpec {
RateSpec {
class,
target: RatePerSecond::new(target),
feed: FeedMode::Open,
}
}
fn descriptor(id: u64, scheduled_at: u64) -> OpDescriptor {
descriptor_in_phase(PHASE, id, scheduled_at)
}
fn descriptor_in_phase(phase_id: PhaseId, id: u64, scheduled_at: u64) -> OpDescriptor {
OpDescriptor::new(
OperationId(id),
NanosSincePhaseStart::from_nanos(phase_id, scheduled_at),
OpPayload::PersonUpsert(PersonUpsertPayload {
team_id: 1,
person_uuid: uuid::Uuid::nil(),
properties: json!({}),
version: 1,
}),
)
}
#[test]
fn poisson_schedule_is_monotonic_and_independent_of_wakeup_delay() {
let rates = [open_rate(OpClass::CanonicalRead, 14_474.0)];
let mut direct = ArrivalSchedule::new(PHASE, 42, &rates).expect("valid schedule");
let expected = (0..512)
.map(|_| direct.next_arrival().expect("arrival"))
.collect::<Vec<_>>();
assert!(expected.windows(2).all(|window| {
window[0].scheduled_at.as_nanos() < window[1].scheduled_at.as_nanos()
}));
let mut delayed = ArrivalSchedule::new(PHASE, 42, &rates).expect("valid schedule");
let wakeup = NanosSincePhaseStart::from_nanos(
PHASE,
expected
.last()
.expect("last arrival")
.scheduled_at
.as_nanos()
+ 1_000_000,
);
let mut actual = Vec::with_capacity(expected.len());
while actual.len() < expected.len() {
actual.push(
delayed
.pop_due(wakeup)
.expect("same phase")
.expect("overdue arrival"),
);
}
assert_eq!(actual, expected);
}
#[test]
fn full_open_loop_channel_sheds_without_growing() {
let capacity = NonZeroUsize::new(1).expect("nonzero");
let (mut dispatcher, receiver) = BoundedDispatcher::channel(capacity);
let accepted = dispatcher
.try_dispatch_at(
descriptor(1, 10),
NanosSincePhaseStart::from_nanos(PHASE, 10),
)
.expect("on-time dispatch");
let shed = dispatcher
.try_dispatch_at(
descriptor(2, 11),
NanosSincePhaseStart::from_nanos(PHASE, 12),
)
.expect("late dispatch");
assert_eq!(accepted.outcome, DispatchOutcome::Enqueued);
assert_eq!(shed.outcome, DispatchOutcome::Shed);
assert_eq!(shed.dispatch_lag_nanos(), 1);
assert_eq!(dispatcher.shed_count(), 1);
assert_eq!(receiver.len(), 1);
}
#[test]
fn early_dispatch_is_rejected_before_touching_the_queue() {
let capacity = NonZeroUsize::new(1).expect("nonzero");
let (mut dispatcher, receiver) = BoundedDispatcher::channel(capacity);
let result = dispatcher.try_dispatch_at(
descriptor(1, 10),
NanosSincePhaseStart::from_nanos(PHASE, 9),
);
assert!(matches!(
result,
Err(DispatchError::Timestamp(
TimestampOrderError::DispatchBeforeSchedule
))
));
assert_eq!(receiver.len(), 0);
assert_eq!(dispatcher.shed_count(), 0);
let mixed_phase = dispatcher.try_dispatch_at(
descriptor(2, 10),
NanosSincePhaseStart::from_nanos(PhaseId::new(2), 10),
);
assert!(matches!(
mixed_phase,
Err(DispatchError::Timestamp(
TimestampOrderError::PhaseMismatch(_)
))
));
assert_eq!(receiver.len(), 0);
}
#[tokio::test(start_paused = true)]
async fn backpressured_dispatch_publishes_only_after_its_scheduled_time() {
let phase_id = PhaseId::new(7);
let clock = PhaseClock::start_now(phase_id);
let capacity = NonZeroUsize::new(1).expect("nonzero");
let (dispatcher, mut receiver) = BoundedDispatcher::channel(capacity);
let task = tokio::spawn(async move {
dispatcher
.dispatch_with_backpressure(descriptor_in_phase(phase_id, 1, 10), &clock)
.await
});
tokio::task::yield_now().await;
assert!(matches!(
receiver.try_recv(),
Err(mpsc::error::TryRecvError::Empty)
));
tokio::time::advance(Duration::from_nanos(10)).await;
let received = receiver.recv().await.expect("published descriptor");
let record = task.await.expect("dispatch task").expect("dispatch record");
assert_eq!(received.operation_id(), OperationId(1));
assert!(record.dispatched_at().as_nanos() >= record.scheduled_at().as_nanos());
}
#[test]
fn invalid_arrival_rates_are_rejected_instead_of_disabled() {
for invalid_rate in [-1.0, f64::NAN, f64::INFINITY] {
let result = ArrivalSchedule::new(
PHASE,
42,
&[open_rate(OpClass::CanonicalRead, invalid_rate)],
);
assert!(matches!(result, Err(ArrivalError::InvalidRate { .. })));
}
}
}