: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
//! Decides which key runs go to which worker, and when. The batcher task
//! feeds it polls, worker responses, retry wakeups, revokes and shutdown,
//! and performs the [`Effects`] each action returns. The state machine does
//! no I/O.
//!
//! The caller performs one action's effects in this order: order-sentinel
//! ACKs before evictions, then the sends in the order given, which is each
//! key's send order, and `drained` after `completions`. `next_wakeup`
//! replaces the previous wakeup; `None` needs no timer. `fatal` means the
//! state machine failed and the process must exit and replay.
//!
//! When work is pending, nothing is in flight, and no message was accepted
//! for `stall_timeout`, the state machine fails, so a wedged batcher restarts
//! instead of growing lag.
use std::collections::HashMap;
use std::num::NonZeroU32;
use std::sync::Arc;
use std::time::{Duration, Instant};
use common_kafka_consumer::{GroupCompletion, Offset, Partition};
use metrics::{counter, gauge, histogram};
use super::drains::PartitionDrains;
use super::governor::{Adaptation, Governor, GovernorSettings, GovernorSnapshot};
use super::in_flight::{InFlightRequest, InFlightRequests, RequestId, SentMessage};
use super::key_queues::{KeyQueues, KeyRun, Settlement};
use super::packer::Packer;
use super::request::{Request, RequestClass};
use super::retry_policy::{RetryPolicy, RetryReason};
use super::worker_assigner::{WorkerAssigner, WorkerInFlight};
use super::RevokeId;
use crate::order_sentinel::ack_mark;
use crate::routing::Candidate;
use crate::types::SerializedKafkaMessage;
use crate::worker_registry::WorkerId;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum FailureCause {
Fault,
Busy,
}
/// The worker's soft time budget for every request. A key resends without it
/// once `attempts` settles left its messages unfinished since it last finished
/// a run, or at once when its request finished nothing, so a message that
/// never fits the budget still finishes.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct RequestBudget {
pub soft_budget: Duration,
pub attempts: NonZeroU32,
}
#[derive(Debug)]
pub struct SendRequest {
pub request: RequestId,
pub worker: WorkerId,
pub class: RequestClass,
pub soft_budget: Option<Duration>,
pub runs: Vec<KeyRun>,
}
#[derive(Debug, PartialEq, Eq)]
pub struct KeyAck {
pub routing_key: Arc<str>,
pub max_offset: i64,
}
#[derive(Debug, PartialEq, Eq)]
pub struct WorkerOutcome {
pub worker: WorkerId,
pub fault: bool,
}
#[derive(Debug, Default)]
pub struct Effects {
pub sends: Vec<SendRequest>,
pub completions: Vec<GroupCompletion>,
pub drained: Vec<RevokeId>,
pub key_acks: Vec<KeyAck>,
pub evicted_keys: Vec<Arc<str>>,
pub worker_outcomes: Vec<WorkerOutcome>,
/// A draining worker listed here has finished its work.
pub idle_workers: Vec<WorkerId>,
pub busy_workers: Vec<WorkerId>,
pub fatal: Option<String>,
pub next_wakeup: Option<Instant>,
}
/// A point-in-time view of the batcher's load, for the debug API.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct BatcherSnapshot {
pub keys: usize,
pub pending_messages: usize,
pub queued_bytes: usize,
pub waiting_keys: usize,
pub claimed_keys: usize,
pub in_flight_requests: usize,
pub in_flight_messages: usize,
pub per_worker: Vec<WorkerInFlight>,
pub governor: GovernorSnapshot,
}
pub enum BatcherStateMachine {
Running(ActiveState),
Draining(ActiveState),
Stopped,
Failed,
}
impl BatcherStateMachine {
pub fn new(
packer: Packer,
assigner: WorkerAssigner,
retry: RetryPolicy,
stall_timeout: Duration,
now: Instant,
) -> Result<Self, String> {
if stall_timeout.is_zero() {
return Err("stall_timeout must be > 0".to_string());
}
// Messages waiting for the pack deadline count toward a stall, so the
// budget must leave most of the stall window.
if packer.latency_budget() * 2 > stall_timeout {
return Err(
"the pack latency budget must be at most half the stall timeout".to_string(),
);
}
// Without a target, one request takes every ready run of a class,
// and one failure replays all of it.
let targets = packer.targets();
if targets.events.is_none() && targets.bytes.is_none() {
return Err("set a pack target in events or bytes".to_string());
}
let governor = Governor::new(
GovernorSettings::observing(),
assigner.max_requests_per_worker(),
)?;
Ok(BatcherStateMachine::Running(ActiveState {
keys: KeyQueues::new(packer.run_cap()),
packer,
assigner,
in_flight: InFlightRequests::new(),
retry,
stall_timeout,
last_progress: now,
soft_budget: None,
governor,
reconnecting: HashMap::new(),
drains: PartitionDrains::default(),
}))
}
/// `None` sends no budget.
pub fn with_request_budget(self, budget: Option<RequestBudget>) -> Self {
match self {
BatcherStateMachine::Running(active) => BatcherStateMachine::Running(ActiveState {
soft_budget: budget.map(|budget| budget.soft_budget),
keys: active
.keys
.with_budget_attempts(budget.map(|budget| budget.attempts)),
..active
}),
other => other,
}
}
pub fn with_governor(self, settings: GovernorSettings) -> Result<Self, String> {
match self {
BatcherStateMachine::Running(active) => {
let governor = Governor::new(settings, active.assigner.max_requests_per_worker())?;
Ok(BatcherStateMachine::Running(ActiveState {
governor,
..active
}))
}
other => Ok(other),
}
}
pub fn on_groups(
self,
now: Instant,
workers: &[Candidate],
assignment_epoch: u64,
runs: Vec<KeyRun>,
) -> (Self, Effects) {
match self {
BatcherStateMachine::Running(mut active) => {
let result = active.on_groups(now, workers, assignment_epoch, runs);
Self::after(active, false, result)
}
BatcherStateMachine::Draining(_) | BatcherStateMachine::Stopped => {
Self::failed("groups submitted after shutdown started".to_string())
}
BatcherStateMachine::Failed => (BatcherStateMachine::Failed, Effects::default()),
}
}
pub fn on_request_succeeded(
self,
now: Instant,
workers: &[Candidate],
request: RequestId,
accepted: u32,
) -> (Self, Effects) {
self.act(|active, draining| {
active.on_request_succeeded(now, workers, draining, request, accepted)
})
}
/// The worker finished every message except `unfinished`. Those go back to
/// the front of their keys' queues and are sent again at once as replay,
/// without a budget when the worker finished nothing.
pub fn on_request_partial(
self,
now: Instant,
workers: &[Candidate],
request: RequestId,
accepted: u32,
unfinished: Vec<SerializedKafkaMessage>,
) -> (Self, Effects) {
self.act(|active, draining| {
active.on_request_partial(now, workers, draining, request, accepted, unfinished)
})
}
/// The failed request's messages go back to the front of their keys'
/// queues and are sent again as replay after the retry delay.
pub fn on_request_failed(
self,
now: Instant,
workers: &[Candidate],
request: RequestId,
cause: FailureCause,
messages: Vec<SerializedKafkaMessage>,
) -> (Self, Effects) {
self.act(|active, draining| {
active.on_request_failed(now, workers, draining, request, cause, messages)
})
}
pub fn on_wakeup(self, now: Instant, workers: &[Candidate]) -> (Self, Effects) {
self.act(|active, draining| {
let mut effects = Effects::default();
active.advance(now, workers, draining, &mut effects)?;
Ok(effects)
})
}
/// The new owner replays the revoked partitions, so their pending
/// messages drop. Runs already in flight finish; their messages of revoked
/// partitions that come back unfinished or failed drop too. `revoke`
/// comes back in [`Effects::drained`] once no request in flight carries
/// the partitions.
pub fn on_partitions_revoked(
self,
now: Instant,
revoke: RevokeId,
partitions: &[(String, i32)],
) -> (Self, Effects) {
self.act(|active, _| active.on_partitions_revoked(now, revoke, partitions))
}
/// Takes no new groups from now on, and stops once nothing is pending or
/// in flight.
pub fn on_shutdown(self, now: Instant, workers: &[Candidate]) -> (Self, Effects) {
match self {
BatcherStateMachine::Running(active) | BatcherStateMachine::Draining(active) => {
BatcherStateMachine::Draining(active).on_wakeup(now, workers)
}
other => (other, Effects::default()),
}
}
pub fn pending_messages(&self) -> usize {
self.active().map_or(0, ActiveState::pending_messages)
}
pub fn in_flight_messages(&self) -> usize {
self.active()
.map_or(0, |active| active.assigner.in_flight_messages())
}
pub fn snapshot(&self) -> BatcherSnapshot {
self.active()
.map_or_else(BatcherSnapshot::default, ActiveState::snapshot)
}
fn active(&self) -> Option<&ActiveState> {
match self {
BatcherStateMachine::Running(active) | BatcherStateMachine::Draining(active) => {
Some(active)
}
BatcherStateMachine::Stopped | BatcherStateMachine::Failed => None,
}
}
fn act(
self,
action: impl FnOnce(&mut ActiveState, bool) -> Result<Effects, String>,
) -> (Self, Effects) {
match self {
BatcherStateMachine::Running(mut active) => {
let result = action(&mut active, false);
Self::after(active, false, result)
}
BatcherStateMachine::Draining(mut active) => {
let result = action(&mut active, true);
Self::after(active, true, result)
}
finished => (finished, Effects::default()),
}
}
fn after(
active: ActiveState,
draining: bool,
result: Result<Effects, String>,
) -> (Self, Effects) {
match result {
Err(reason) => Self::failed(reason),
Ok(effects) if draining && active.is_drained() => (
BatcherStateMachine::Stopped,
Effects {
next_wakeup: None,
..effects
},
),
Ok(effects) if draining => (BatcherStateMachine::Draining(active), effects),
Ok(effects) => (BatcherStateMachine::Running(active), effects),
}
}
fn failed(reason: String) -> (Self, Effects) {
(
BatcherStateMachine::Failed,
Effects {
fatal: Some(reason),
..Effects::default()
},
)
}
}
pub struct ActiveState {
keys: KeyQueues,
packer: Packer,
assigner: WorkerAssigner,
in_flight: InFlightRequests,
retry: RetryPolicy,
stall_timeout: Duration,
last_progress: Instant,
soft_budget: Option<Duration>,
governor: Governor,
/// Workers whose stream a failure fenced, with the time of that failure.
/// The stream reconnects after a backoff, so a request sent since then
/// may wait it out and is no RTT sample. The first such request to settle
/// clears the mark.
reconnecting: HashMap<WorkerId, Instant>,
drains: PartitionDrains,
}
impl ActiveState {
fn pending_messages(&self) -> usize {
self.keys.queued_messages()
}
fn snapshot(&self) -> BatcherSnapshot {
BatcherSnapshot {
keys: self.keys.key_count(),
pending_messages: self.keys.queued_messages(),
queued_bytes: self.keys.queued_bytes(),
waiting_keys: self.keys.waiting_keys(),
claimed_keys: self.keys.claimed_keys(),
in_flight_requests: self.in_flight.len(),
in_flight_messages: self.assigner.in_flight_messages(),
per_worker: self.assigner.in_flight_per_worker(),
governor: self.governor.snapshot(),
}
}
/// The stall clock starts when work becomes pending, not at the last
/// action before a quiet period.
fn restart_stall_clock_if_quiet(&mut self, now: Instant) {
if self.pending_messages() == 0 && self.in_flight.is_empty() {
self.last_progress = now;
}
}
fn is_drained(&self) -> bool {
self.pending_messages() == 0 && self.in_flight.is_empty()
}
fn on_groups(
&mut self,
now: Instant,
workers: &[Candidate],
assignment_epoch: u64,
runs: Vec<KeyRun>,
) -> Result<Effects, String> {
self.restart_stall_clock_if_quiet(now);
for run in runs {
self.keys
.push(run.routing_key, assignment_epoch, run.messages, now);
}
let mut effects = Effects::default();
self.advance(now, workers, false, &mut effects)?;
Ok(effects)
}
fn on_request_succeeded(
&mut self,
now: Instant,
workers: &[Candidate],
draining: bool,
request: RequestId,
accepted: u32,
) -> Result<Effects, String> {
let mut effects = Effects::default();
let sent = self.take_request(request, &mut effects)?;
self.observe_rtt(&sent, now);
if accepted as usize != sent.message_count {
return Err(format!(
"worker accepted {accepted} of {} messages",
sent.message_count
));
}
effects.worker_outcomes.push(WorkerOutcome {
worker: sent.worker.clone(),
fault: false,
});
if accepted > 0 {
self.last_progress = now;
}
let assignment_epoch = sent.class.assignment_epoch;
let runs = sent.accepted();
effects.completions =
completions(assignment_epoch, runs.iter().flat_map(|run| &run.messages));
effects.key_acks = key_acks(runs.iter().map(|run| {
(
&run.routing_key,
run.first_keyed_partition(),
run.messages.as_slice(),
&[][..],
)
}));
for run in runs {
self.settle_key(&run.routing_key, Settlement::Done, now, &mut effects)?;
}
self.advance(now, workers, draining, &mut effects)?;
Ok(effects)
}
fn on_request_partial(
&mut self,
now: Instant,
workers: &[Candidate],
draining: bool,
request: RequestId,
accepted: u32,
unfinished: Vec<SerializedKafkaMessage>,
) -> Result<Effects, String> {
let mut effects = Effects::default();
let sent = self.take_request(request, &mut effects)?;
self.observe_rtt(&sent, now);
effects.worker_outcomes.push(WorkerOutcome {
worker: sent.worker.clone(),
fault: false,
});
if accepted > 0 {
self.last_progress = now;
}
let assignment_epoch = sent.class.assignment_epoch;
let unfinished_count = unfinished.len();
let partial_runs = sent.partially_accepted(accepted, unfinished)?;
counter!("ingestion_consumer_request_budget_partials_total").increment(1);
counter!("ingestion_consumer_request_budget_unfinished_messages_total")
.increment(unfinished_count as u64);
effects.completions = completions(
assignment_epoch,
partial_runs.iter().flat_map(|run| &run.accepted),
);
effects.key_acks = key_acks(partial_runs.iter().map(|run| {
(
&run.routing_key,
run.first_keyed_partition,
run.accepted.as_slice(),
run.unfinished.as_slice(),
)
}));
for run in partial_runs {
let settlement = if run.unfinished.is_empty() {
Settlement::Done
} else if accepted == 0 {
Settlement::Bounced(run.unfinished)
} else {
Settlement::Unfinished(run.unfinished)
};
self.settle_key(&run.routing_key, settlement, now, &mut effects)?;
}
self.advance(now, workers, draining, &mut effects)?;
Ok(effects)
}
fn on_request_failed(
&mut self,
now: Instant,
workers: &[Candidate],
draining: bool,
request: RequestId,
cause: FailureCause,
messages: Vec<SerializedKafkaMessage>,
) -> Result<Effects, String> {
let mut effects = Effects::default();
let sent = self.take_request(request, &mut effects)?;
self.reconnecting.entry(sent.worker.clone()).or_insert(now);
effects.worker_outcomes.push(WorkerOutcome {
worker: sent.worker.clone(),
fault: cause == FailureCause::Fault,
});
let runs = sent.hand_back(messages)?;
let retry_at = self.retry.retry_at(
now,
match cause {
FailureCause::Fault => RetryReason::Fault,
FailureCause::Busy => RetryReason::Busy,
},
);
for run in runs {
let settlement = Settlement::Failed {
messages: run.messages,
retry_at,
};
self.settle_key(&run.routing_key, settlement, now, &mut effects)?;
}
self.advance(now, workers, draining, &mut effects)?;
Ok(effects)
}
fn on_partitions_revoked(
&mut self,
now: Instant,
revoke: RevokeId,
partitions: &[(String, i32)],
) -> Result<Effects, String> {
let mut effects = Effects {
evicted_keys: self.keys.purge(partitions),
..Effects::default()
};
// After the purge no new request carries the partitions.
self.drains
.on_revoked(revoke, self.in_flight.carrying(partitions));
self.finish(now, &mut effects)?;
if self.keys.has_ready() {
effects.next_wakeup = Some(now);
}
Ok(effects)
}
fn take_request(
&mut self,
request: RequestId,
effects: &mut Effects,
) -> Result<InFlightRequest, String> {
let sent = self
.in_flight
.take(request)
.ok_or_else(|| format!("response for unknown request {request:?}"))?;
self.drains.on_request_settled(request);
if self.assigner.release(&sent.worker, sent.message_count) {
effects.idle_workers.push(sent.worker.clone());
}
Ok(sent)
}
/// Only an accepted or partial settlement is a sample, because a fault or
/// a busy answer measures the failure, not the worker. Saturation still
/// reaches the average, because the workers send no busy answer: a
/// request that finds no free slot waits for one, and at its soft budget
/// it comes back as a partial with nothing finished. Faults and ack
/// timeouts go to health routing instead, and a busy answer waits out the
/// busy retry delay.
fn observe_rtt(&mut self, sent: &InFlightRequest, now: Instant) {
let sent_while_reconnecting = self
.reconnecting
.get(&sent.worker)
.is_some_and(|failed_at| sent.sent_at >= *failed_at);
if sent_while_reconnecting {
self.reconnecting.remove(&sent.worker);
return;
}
let rtt = now.saturating_duration_since(sent.sent_at);
if let Some(decision) = self.governor.observe(rtt, now) {
counter!(
"ingestion_consumer_governor_adjustments_total",
"direction" => decision.direction.as_str(),
"applied" => if decision.applied { "true" } else { "false" }
)
.increment(1);
}
}
/// A request on a worker that left the pool holds none of the pool's
/// permits, so the governor counts only the requests on `workers`.
fn sync_governor(&mut self, workers: &[Candidate]) {
let in_flight = workers
.iter()
.map(|candidate| self.assigner.requests_on(&candidate.worker))
.sum();
self.governor.set_pool(workers, in_flight);
self.reconnecting
.retain(|worker, _| workers.iter().any(|candidate| candidate.worker == *worker));
}
fn settle_key(
&mut self,
routing_key: &Arc<str>,
settlement: Settlement,
now: Instant,
effects: &mut Effects,
) -> Result<(), String> {
let settled = self
.keys
.settle(routing_key, settlement, now)
.map_err(|err| err.to_string())?;
if settled.escalated {
counter!("ingestion_consumer_request_budget_escalations_total").increment(1);
}
if settled.evicted {
effects.evicted_keys.push(Arc::clone(routing_key));
}
Ok(())
}
fn advance(
&mut self,
now: Instant,
workers: &[Candidate],
draining: bool,
effects: &mut Effects,
) -> Result<(), String> {
self.restart_stall_clock_if_quiet(now);
self.sync_governor(workers);
// Past the stall deadline no new request starts, so overlapping
// failures drain to nothing in flight and the watchdog can fire.
let stalled = self.pending_messages() > 0 && now >= self.last_progress + self.stall_timeout;
if !stalled {
self.place(now, workers, draining, effects)?;
}
self.finish(now, effects)
}
fn place(
&mut self,
now: Instant,
workers: &[Candidate],
draining: bool,
effects: &mut Effects,
) -> Result<(), String> {
let free_slots = self.assigner.free_slots(workers);
let free_permits = self.governor.free();
let free = match self.governor.adaptation() {
Adaptation::On => free_slots.min(free_permits),
Adaptation::Off => free_slots,
};
let batch = self.packer.pack(&mut self.keys, now, free, draining);
// With adaptation off free slots size the pass, so the requests past
// the free permits are the ones the governor would have held back.
let mut starved_messages: usize = batch
.iter()
.skip(free_permits)
.map(|request| request.message_count)
.sum();
for request in batch {
let worker = self
.assigner
.assign(workers, request.message_count)
.ok_or("no worker took a request within the free slots")?;
if self.assigner.requests_on(&worker) == 1 {
effects.busy_workers.push(worker.clone());
}
self.send(now, worker, request, effects);
}
self.sync_governor(workers);
if self.governor.free() == 0 {
starved_messages += self
.keys
.ready_sizes()
.iter()
.map(|(_, size)| size.messages)
.sum::<usize>();
}
self.governor.set_starved_messages(starved_messages);
Ok(())
}
fn send(&mut self, now: Instant, worker: WorkerId, request: Request, effects: &mut Effects) {
let kind = if request.class.replay {
"replay"
} else {
"fresh"
};
histogram!("ingestion_consumer_request_events").record(request.message_count as f64);
histogram!("ingestion_consumer_request_bytes").record(request.bytes as f64);
histogram!("ingestion_consumer_request_queue_wait_seconds", "kind" => kind).record(
now.saturating_duration_since(request.oldest_arrival)
.as_secs_f64(),
);
let id = self
.in_flight
.register(worker.clone(), request.class, now, &request.runs);
effects.sends.push(SendRequest {
request: id,
worker,
class: request.class,
soft_budget: self.soft_budget.filter(|_| !request.class.unbudgeted),
runs: request.runs,
});
}
fn finish(&mut self, now: Instant, effects: &mut Effects) -> Result<(), String> {
effects.drained.extend(self.drains.take_drained());
// A stalled action and a revoke skip `pack`, so without this a due
// retry would set the next wakeup at or before `now`.
self.keys.promote_due(now);
let pending = self.pending_messages();
let in_flight = self.in_flight.len();
if pending == 0 && in_flight == 0 {
self.last_progress = now;
}
self.record_gauges();
let stall_deadline = self.last_progress + self.stall_timeout;
if pending > 0 && in_flight == 0 && now >= stall_deadline {
return Err("pending work made no progress within the stall timeout".to_string());
}
// A passed deadline waits for a free slot like any other ready work.
let pack_deadline = self.packer.deadline().filter(|deadline| *deadline > now);
effects.next_wakeup = [
self.keys.next_retry_at(),
pack_deadline,
(pack_deadline.is_none() && self.keys.has_ready())
.then(|| self.retry.retry_at(now, RetryReason::NoWorker)),
(pending > 0 && in_flight == 0).then_some(stall_deadline),
]
.into_iter()
.flatten()
.min();
Ok(())
}
fn record_gauges(&self) {
gauge!("ingestion_consumer_batcher_keys").set(self.keys.key_count() as f64);
gauge!("ingestion_consumer_batcher_queued_messages")
.set(self.keys.queued_messages() as f64);
gauge!("ingestion_consumer_batcher_queued_bytes").set(self.keys.queued_bytes() as f64);
gauge!("ingestion_consumer_batcher_claimed_keys").set(self.keys.claimed_keys() as f64);
gauge!("ingestion_consumer_batcher_waiting_keys").set(self.keys.waiting_keys() as f64);
gauge!("ingestion_consumer_batcher_in_flight_requests").set(self.in_flight.len() as f64);
let governor = self.governor.snapshot();
gauge!("ingestion_consumer_governor_permits").set(governor.permits as f64);
gauge!("ingestion_consumer_governor_ceiling").set(governor.ceiling as f64);
gauge!("ingestion_consumer_governor_free_permits").set(governor.free_permits as f64);
gauge!("ingestion_consumer_governor_starved_messages")
.set(governor.starved_messages as f64);
if let Some(rtt) = governor.rtt {
gauge!("ingestion_consumer_request_rtt_seconds").set(rtt.as_secs_f64());
}
}
}
fn completions<'a>(
assignment_epoch: u64,
messages: impl IntoIterator<Item = &'a SentMessage>,
) -> Vec<GroupCompletion> {
let mut by_partition: HashMap<(i32, u64), Vec<Offset>> = HashMap::new();
for message in messages {
by_partition
.entry((message.partition, message.generation))
.or_default()
.push(Offset(message.offset));
}
let mut completions: Vec<GroupCompletion> = by_partition
.into_iter()
.map(|((partition, generation), offsets)| GroupCompletion {
partition: Partition(partition),
assignment_epoch,
generation,
accepted: offsets.len() as u32,
offsets,
})
.collect();
completions.sort_by_key(|completion| (completion.partition.0, completion.generation));
completions
}
fn key_acks<'a>(
runs: impl IntoIterator<
Item = (
&'a Arc<str>,
Option<i32>,
&'a [SentMessage],
&'a [SerializedKafkaMessage],
),
>,
) -> Vec<KeyAck> {
runs.into_iter()
.filter_map(
|(routing_key, first_keyed_partition, accepted, unfinished)| {
let max_offset = ack_mark(
first_keyed_partition?,
accepted
.iter()
.map(|message| (message.partition, message.offset, message.keyed)),
unfinished
.iter()
.map(|message| (message.partition, message.offset)),
)?;
Some(KeyAck {
routing_key: Arc::clone(routing_key),
max_offset,
})
},
)
.collect()
}
#[cfg(test)]
mod tests {
use std::collections::VecDeque;
use std::num::NonZeroUsize;
use rstest::rstest;
use super::*;
use crate::batcher::key_queues::RunCap;
use crate::batcher::packer::PackTargets;
use crate::batcher::test_support::{message, offsets};
use crate::order_sentinel::{KeyOrderSentinel, KeyOrderViolation, SendKind};
use crate::routing::{Router, RoutingStrategy};
const FAULT_DELAY: Duration = Duration::from_millis(200);
const BUSY_DELAY: Duration = Duration::from_millis(20);
const NO_WORKER_DELAY: Duration = Duration::from_millis(100);
const STALL: Duration = Duration::from_secs(60);
const BUDGET: Duration = Duration::from_millis(250);
const LATENCY_BUDGET: Duration = Duration::from_secs(1);
const SLOW_RTT: Duration = Duration::from_secs(2);
fn retry_policy() -> RetryPolicy {
RetryPolicy::new(FAULT_DELAY, BUSY_DELAY, NO_WORKER_DELAY).expect("valid retry policy")
}
fn batcher(max_requests_per_worker: usize, now: Instant) -> BatcherStateMachine {
packing_batcher(1, Duration::ZERO, max_requests_per_worker, now)
}
fn packing_batcher(
events: usize,
budget: Duration,
max_requests_per_worker: usize,
now: Instant,
) -> BatcherStateMachine {
let packer = Packer::new(PackTargets {
events: NonZeroUsize::new(events),
bytes: None,
latency_budget: budget,
});
batcher_with(packer, max_requests_per_worker, now)
}
fn batcher_with(
packer: Packer,
max_requests_per_worker: usize,
now: Instant,
) -> BatcherStateMachine {
let assigner = WorkerAssigner::new(
Router::with_seed(RoutingStrategy::P2c, 0),
max_requests_per_worker,
)
.expect("valid request cap");
BatcherStateMachine::new(packer, assigner, retry_policy(), STALL, now)
.expect("valid stall timeout")
}
fn budgeted_batcher(events: usize, attempts: u32, now: Instant) -> BatcherStateMachine {
packing_batcher(events, Duration::ZERO, 4, now).with_request_budget(Some(RequestBudget {
soft_budget: BUDGET,
attempts: NonZeroU32::new(attempts).expect("nonzero attempts"),
}))
}
/// One worker with four slots, and a latency budget the slow settlements
/// of these tests exceed.
fn governed_batcher(adaptation: Adaptation, now: Instant) -> BatcherStateMachine {
batcher(4, now)
.with_governor(GovernorSettings {
adaptation,
latency_budget: Some(LATENCY_BUDGET),
..GovernorSettings::observing()
})
.expect("valid governor settings")
}
fn pool(workers: &[&str]) -> Vec<Candidate> {
workers
.iter()
.map(|w| Candidate::uniform(WorkerId::from(*w)))
.collect()
}
fn run(key: &str, offsets: &[i64]) -> KeyRun {
KeyRun {
routing_key: key.into(),
messages: offsets
.iter()
.map(|&offset| message(key, 0, offset))
.collect(),
}
}
fn shape(send: &SendRequest) -> Vec<(&str, Vec<i64>)> {
send.runs
.iter()
.map(|run| (&*run.routing_key, offsets(&run.messages)))
.collect()
}
fn apply_to_sentinel(sentinel: &KeyOrderSentinel, effects: &Effects) -> Vec<KeyOrderViolation> {
let mut batch = sentinel.batch();
for ack in &effects.key_acks {
batch.note_acked(&ack.routing_key, ack.max_offset);
}
for key in &effects.evicted_keys {
batch.evict(key);
}
let mut violations = Vec::new();
for send in &effects.sends {
let kind = if send.class.replay {
SendKind::Resend
} else {
SendKind::Fresh
};
for run in &send.runs {
violations.extend(batch.note_sent(&run.routing_key, &run.messages, kind));
}
}
violations
}
fn sent_messages(send: &SendRequest) -> Vec<SerializedKafkaMessage> {
send.runs
.iter()
.flat_map(|run| run.messages.iter().cloned())
.collect()
}
fn saturate_then_settle_slowly(
batcher: BatcherStateMachine,
now: Instant,
) -> (BatcherStateMachine, Vec<String>) {
let workers = pool(&["w"]);
let runs = vec![
run("a", &[1]),
run("b", &[2]),
run("c", &[3]),
run("d", &[4]),
];
let (batcher, effects) = batcher.on_groups(now, &workers, 0, runs);
let first = effects.sends[0].request;
let mut log = vec![format!("{effects:?}")];
let settled_at = now + SLOW_RTT;
let (batcher, effects) = batcher.on_request_succeeded(settled_at, &workers, first, 1);
log.push(format!("{effects:?}"));
let (batcher, effects) = batcher.on_groups(settled_at, &workers, 0, vec![run("e", &[5])]);
log.push(format!("{effects:?}"));
(batcher, log)
}
#[test]
fn with_adaptation_off_the_governor_changes_no_effect_while_its_shadow_pool_moves() {
let now = Instant::now();
let (baseline, baseline_log) = saturate_then_settle_slowly(batcher(4, now), now);
let (shadow, shadow_log) =
saturate_then_settle_slowly(governed_batcher(Adaptation::Off, now), now);
assert_eq!(baseline_log, shadow_log);
assert_eq!(baseline.snapshot().governor.permits, 4);
let governor = shadow.snapshot().governor;
assert_eq!(governor.rtt, Some(SLOW_RTT));
assert_eq!(
(governor.permits, governor.ceiling),
(3, 4),
"the shadow pool shrank below the ceiling"
);
assert_eq!(
governor.starved_messages, 1,
"e went out on a free slot past the shadow pool's free permits"
);
}
#[test]
fn with_adaptation_on_free_permits_cap_the_pass_until_a_permit_returns() {
let now = Instant::now();
let workers = pool(&["w"]);
let runs = vec![
run("a", &[1]),
run("b", &[2]),
run("c", &[3]),
run("d", &[4]),
];
let (batcher, effects) =
governed_batcher(Adaptation::On, now).on_groups(now, &workers, 0, runs);
assert_eq!(effects.sends.len(), 4);
let (a, b) = (effects.sends[0].request, effects.sends[1].request);
let settled_at = now + SLOW_RTT;
let (batcher, _) = batcher.on_request_succeeded(settled_at, &workers, a, 1);
let (batcher, effects) = batcher.on_groups(settled_at, &workers, 0, vec![run("e", &[5])]);
assert!(
effects.sends.is_empty(),
"a's slot is free but the pool shrank to three"
);
let governor = batcher.snapshot().governor;
assert_eq!(
(
governor.permits,
governor.free_permits,
governor.starved_messages
),
(3, 0, 1)
);
let (batcher, effects) = batcher.on_request_succeeded(settled_at, &workers, b, 1);
assert_eq!(shape(&effects.sends[0]), vec![("e", vec![5])]);
assert_eq!(
batcher.snapshot().governor.starved_messages,
0,
"the pass that sent e left nothing waiting"
);
}
#[test]
fn a_failure_and_the_requests_sent_until_its_worker_answers_again_give_no_rtt_sample() {
let now = Instant::now();
let workers = pool(&["w"]);
let (batcher, effects) = batcher(4, now).on_groups(now, &workers, 0, vec![run("a", &[1])]);
let request = effects.sends[0].request;
assert_eq!(batcher.snapshot().governor.free_permits, 3);
let failed_at = now + SLOW_RTT;
let (batcher, _) = batcher.on_request_failed(
failed_at,
&workers,
request,
FailureCause::Busy,
vec![message("a", 0, 1)],
);
let governor = batcher.snapshot().governor;
assert_eq!(governor.free_permits, 4);
assert_eq!(governor.rtt, None, "a busy answer is no round-trip sample");
let (batcher, effects) = batcher.on_wakeup(failed_at + BUSY_DELAY, &workers);
let retry = effects.sends[0].request;
let answered_at = failed_at + BUSY_DELAY + SLOW_RTT;
let (batcher, _) = batcher.on_request_succeeded(answered_at, &workers, retry, 1);
assert_eq!(
batcher.snapshot().governor.rtt,
None,
"the retry can wait out the stream's reconnect backoff"
);
let rtt = Duration::from_millis(100);
let (batcher, effects) = batcher.on_groups(answered_at, &workers, 0, vec![run("b", &[2])]);
let next = effects.sends[0].request;
let (batcher, _) = batcher.on_request_succeeded(answered_at + rtt, &workers, next, 1);
assert_eq!(batcher.snapshot().governor.rtt, Some(rtt));
}
#[test]
fn a_draining_workers_requests_hold_none_of_the_routable_workers_permits() {
let now = Instant::now();
let both = pool(&["a", "b"]);
let runs = (1..=8).map(|n| run(&format!("k{n}"), &[n])).collect();
let (mut batcher, effects) =
governed_batcher(Adaptation::On, now).on_groups(now, &both, 0, runs);
assert_eq!(effects.sends.len(), 8);
let on_a: Vec<_> = effects
.sends
.iter()
.filter(|send| send.worker == WorkerId::from("a"))
.map(|send| send.request)
.collect();
assert_eq!(on_a.len(), 4);
let only_a = pool(&["a"]);
for request in on_a {
let effects;
(batcher, effects) = batcher.on_request_succeeded(now, &only_a, request, 1);
assert!(effects.sends.is_empty());
}
let governor = batcher.snapshot().governor;
assert_eq!(
(governor.ceiling, governor.free_permits),
(4, 4),
"b's four requests in flight hold none of a's permits"
);
let (_, effects) = batcher.on_groups(now, &only_a, 0, vec![run("k9", &[9])]);
assert_eq!(shape(&effects.sends[0]), vec![("k9", vec![9])]);
}
#[test]
fn a_backlog_fills_each_worker_to_its_weighted_slots() {
let now = Instant::now();
let quarters = |w: &str, n: u64| {
Candidate::new(
WorkerId::from(w),
std::num::NonZeroU64::new(n).unwrap(),
std::num::NonZeroU64::new(4).unwrap(),
)
};
let workers = vec![quarters("whole", 4), quarters("half", 2)];
let runs = (1..=10).map(|n| run(&format!("k{n}"), &[n])).collect();
let (_, effects) = batcher(4, now).on_groups(now, &workers, 0, runs);
let mut sent: HashMap<WorkerId, usize> = HashMap::new();
for send in &effects.sends {
*sent.entry(send.worker.clone()).or_insert(0) += 1;
}
assert_eq!(
sent,
HashMap::from([(WorkerId::from("whole"), 4), (WorkerId::from("half"), 2)])
);
}
#[test]
fn each_key_run_is_its_own_request_and_its_next_run_waits_for_the_response() {
let now = Instant::now();
let workers = pool(&["w"]);
let batcher = batcher(4, now);
let (batcher, effects) =
batcher.on_groups(now, &workers, 0, vec![run("a", &[1]), run("b", &[2])]);
assert_eq!(
effects.sends.iter().map(shape).collect::<Vec<_>>(),
vec![vec![("a", vec![1])], vec![("b", vec![2])]]
);
let request = effects.sends[0].request;
let (batcher, effects) = batcher.on_groups(now, &workers, 0, vec![run("a", &[3])]);
assert!(effects.sends.is_empty(), "a's first run is still in flight");
let (_, effects) = batcher.on_request_succeeded(now, &workers, request, 1);
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![3])]);
assert_eq!(effects.completions.len(), 1);
assert_eq!(effects.completions[0].offsets, vec![Offset(1)]);
assert_eq!(
effects.key_acks,
vec![KeyAck {
routing_key: "a".into(),
max_offset: 1
}]
);
}
#[test]
fn a_key_arriving_under_a_new_epoch_stays_one_run_out() {
let now = Instant::now();
let workers = pool(&["w"]);
let batcher = batcher(4, now);
let (batcher, effects) = batcher.on_groups(now, &workers, 1, vec![run("k", &[1])]);
assert_eq!(effects.sends[0].class.assignment_epoch, 1);
let request = effects.sends[0].request;
let (batcher, effects) = batcher.on_groups(now, &workers, 2, vec![run("k", &[2])]);
assert!(
effects.sends.is_empty(),
"the epoch-2 message waits for k's run"
);
let (_, effects) = batcher.on_request_succeeded(now, &workers, request, 1);
assert_eq!(effects.sends[0].class.assignment_epoch, 2);
assert_eq!(shape(&effects.sends[0]), vec![("k", vec![2])]);
}
#[test]
fn a_transport_failure_retries_as_replay_after_the_fault_delay() {
let now = Instant::now();
let workers = pool(&["w"]);
let batcher = batcher(4, now);
let (batcher, effects) = batcher.on_groups(now, &workers, 0, vec![run("a", &[1])]);
let request = effects.sends[0].request;
let messages = vec![message("a", 0, 1)];
let (batcher, effects) =
batcher.on_request_failed(now, &workers, request, FailureCause::Fault, messages);
assert_eq!(
effects.worker_outcomes,
vec![WorkerOutcome {
worker: WorkerId::from("w"),
fault: true
}]
);
assert!(effects.completions.is_empty());
assert!(effects.sends.is_empty());
assert_eq!(effects.next_wakeup, Some(now + FAULT_DELAY));
let (_, effects) = batcher.on_wakeup(now + FAULT_DELAY, &workers);
assert!(effects.sends[0].class.replay);
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![1])]);
}
#[test]
fn a_revoke_after_a_retry_time_passed_asks_for_a_wakeup_now() {
let now = Instant::now();
let workers = pool(&["w"]);
let batcher = batcher(4, now);
let (batcher, effects) = batcher.on_groups(now, &workers, 0, vec![run("a", &[1])]);
let request = effects.sends[0].request;
let (batcher, _) = batcher.on_request_failed(
now,
&workers,
request,
FailureCause::Busy,
vec![message("a", 0, 1)],
);
let late = now + BUSY_DELAY * 3;
let (_, effects) =
batcher.on_partitions_revoked(late, REVOKE, &[("events".to_string(), 9)]);
assert_eq!(effects.next_wakeup, Some(late));
}
#[test]
fn a_request_without_a_worker_waits_and_is_sent_when_one_appears() {
let now = Instant::now();
let batcher = batcher(4, now);
let (batcher, effects) = batcher.on_groups(now, &pool(&[]), 0, vec![run("a", &[1])]);
assert!(effects.sends.is_empty());
assert_eq!(batcher.pending_messages(), 1);
assert_eq!(effects.next_wakeup, Some(now + NO_WORKER_DELAY));
let (_, effects) = batcher.on_wakeup(now + NO_WORKER_DELAY, &pool(&["w"]));
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![1])]);
}
#[test]
fn the_request_cap_holds_sends_until_a_slot_frees() {
let now = Instant::now();
let workers = pool(&["w"]);
let batcher = batcher(1, now);
let (batcher, effects) =
batcher.on_groups(now, &workers, 0, vec![run("a", &[1]), run("b", &[2])]);
assert_eq!(effects.sends.len(), 1);
let request = effects.sends[0].request;
let (_, effects) = batcher.on_request_succeeded(now, &workers, request, 1);
assert_eq!(shape(&effects.sends[0]), vec![("b", vec![2])]);
assert_eq!(effects.idle_workers, vec![WorkerId::from("w")]);
assert_eq!(effects.busy_workers, vec![WorkerId::from("w")]);
}
#[test]
fn a_worker_is_busy_from_its_first_request_until_its_last_settles() {
let now = Instant::now();
let workers = pool(&["w"]);
let batcher = batcher(2, now);
let (batcher, effects) =
batcher.on_groups(now, &workers, 0, vec![run("a", &[1]), run("b", &[2])]);
assert_eq!(effects.sends.len(), 2);
assert_eq!(effects.busy_workers, vec![WorkerId::from("w")]);
let (first, second) = (effects.sends[0].request, effects.sends[1].request);
let (batcher, effects) = batcher.on_request_succeeded(now, &workers, first, 1);
assert!(effects.idle_workers.is_empty());
let (_, effects) = batcher.on_request_succeeded(now, &workers, second, 1);
assert_eq!(effects.idle_workers, vec![WorkerId::from("w")]);
}
#[test]
fn a_revoke_drops_pending_messages_and_never_sends_them() {
let now = Instant::now();
let batcher = batcher(4, now);
let (batcher, effects) = batcher.on_groups(now, &pool(&[]), 0, vec![run("a", &[1])]);
assert!(effects.sends.is_empty());
let (batcher, effects) =
batcher.on_partitions_revoked(now, REVOKE, &[("events".to_string(), 0)]);
assert!(effects.sends.is_empty());
assert_eq!(effects.evicted_keys, vec![Arc::<str>::from("a")]);
assert_eq!(batcher.pending_messages(), 0);
let (_, effects) = batcher.on_wakeup(now + STALL / 2, &pool(&["w"]));
assert!(effects.sends.is_empty());
}
#[test]
fn shutdown_stops_once_drained() {
let now = Instant::now();
let workers = pool(&["w"]);
let batcher = batcher(4, now);
let (batcher, effects) = batcher.on_groups(now, &workers, 0, vec![run("a", &[1])]);
let request = effects.sends[0].request;
let (batcher, _) = batcher.on_shutdown(now, &workers);
assert!(matches!(batcher, BatcherStateMachine::Draining(_)));
let (batcher, effects) = batcher.on_request_succeeded(now, &workers, request, 1);
assert!(matches!(batcher, BatcherStateMachine::Stopped));
assert_eq!(effects.next_wakeup, None);
}
#[test]
fn a_pack_budget_over_half_the_stall_timeout_is_rejected() {
let assigner =
WorkerAssigner::new(Router::new(RoutingStrategy::P2c), 1).expect("valid cap");
let packer = Packer::new(PackTargets {
events: NonZeroUsize::new(1),
bytes: None,
latency_budget: STALL / 2 + Duration::from_millis(1),
});
let created =
BatcherStateMachine::new(packer, assigner, retry_policy(), STALL, Instant::now());
assert!(created.is_err());
}
#[test]
fn a_packer_without_a_target_is_rejected() {
let assigner =
WorkerAssigner::new(Router::new(RoutingStrategy::P2c), 1).expect("valid cap");
let created = BatcherStateMachine::new(
Packer::new(PackTargets::default()),
assigner,
retry_policy(),
STALL,
Instant::now(),
);
assert!(created.is_err());
}
#[test]
fn a_second_shutdown_keeps_a_waiting_retrys_wakeup() {
let now = Instant::now();
let workers = pool(&["w"]);
let batcher = batcher(4, now);
let (batcher, effects) = batcher.on_groups(now, &workers, 0, vec![run("a", &[1])]);
let request = effects.sends[0].request;
let (batcher, _) = batcher.on_request_failed(
now,
&workers,
request,
FailureCause::Busy,
vec![message("a", 0, 1)],
);
let (batcher, _) = batcher.on_shutdown(now, &workers);
let (batcher, effects) = batcher.on_shutdown(now, &workers);
assert!(matches!(batcher, BatcherStateMachine::Draining(_)));
assert_eq!(effects.next_wakeup, Some(now + BUSY_DELAY));
}
#[test]
fn a_zero_stall_timeout_is_rejected() {
let assigner =
WorkerAssigner::new(Router::new(RoutingStrategy::P2c), 1).expect("valid cap");
let created = BatcherStateMachine::new(
Packer::new(PackTargets {
events: NonZeroUsize::new(1),
..PackTargets::default()
}),
assigner,
retry_policy(),
Duration::ZERO,
Instant::now(),
);
assert!(created.is_err());
}
#[test]
fn work_stuck_without_progress_fails_the_state_machine() {
let now = Instant::now();
let batcher = batcher(4, now);
let (batcher, _) = batcher.on_groups(now, &pool(&[]), 0, vec![run("a", &[1])]);
let (batcher, effects) = batcher.on_wakeup(now + STALL, &pool(&[]));
assert!(matches!(batcher, BatcherStateMachine::Failed));
assert!(effects.fatal.is_some());
assert_eq!(effects.next_wakeup, None);
}
#[test]
fn a_passed_stall_deadline_with_a_request_in_flight_never_asks_for_a_past_wakeup() {
let now = Instant::now();
let workers = pool(&["w"]);
let batcher = batcher(1, now);
let (batcher, _) =
batcher.on_groups(now, &workers, 0, vec![run("a", &[1]), run("b", &[2])]);
let late = now + STALL * 2;
let (batcher, effects) = batcher.on_wakeup(late, &workers);
assert!(matches!(batcher, BatcherStateMachine::Running(_)));
assert!(effects.next_wakeup.is_some_and(|at| at > late));
}
#[test]
fn a_retry_due_past_the_stall_deadline_waits_the_no_worker_delay() {
let now = Instant::now();
let workers = pool(&["w1", "w2"]);
let (batcher, effects) =
batcher(1, now).on_groups(now, &workers, 0, vec![run("a", &[1]), run("b", &[2])]);
let a = effects
.sends
.iter()
.find(|send| &*send.runs[0].routing_key == "a")
.expect("a was sent")
.request;
let (batcher, _) = batcher.on_request_failed(
now + STALL - BUSY_DELAY / 2,
&workers,
a,
FailureCause::Busy,
vec![message("a", 0, 1)],
);
let late = now + STALL + BUSY_DELAY;
let (batcher, effects) = batcher.on_wakeup(late, &workers);
assert!(matches!(batcher, BatcherStateMachine::Running(_)));
assert_eq!(effects.next_wakeup, Some(late + NO_WORKER_DELAY));
}
#[test]
fn past_the_stall_deadline_no_new_request_starts_until_the_in_flight_one_settles() {
let now = Instant::now();
let workers = pool(&["w"]);
let batcher = batcher(1, now);
let (batcher, effects) =
batcher.on_groups(now, &workers, 0, vec![run("a", &[1]), run("b", &[2])]);
let request = effects.sends[0].request;
let late = now + STALL;
let (batcher, effects) = batcher.on_request_failed(
late,
&workers,
request,
FailureCause::Busy,
vec![message("a", 0, 1)],
);
assert!(effects.sends.is_empty(), "b stays unsent past the deadline");
assert!(matches!(batcher, BatcherStateMachine::Failed));
}
#[test]
fn an_idle_period_does_not_count_toward_a_stall() {
let start = Instant::now();
let workers = pool(&["w"]);
let batcher = batcher(4, start);
let arrival = start + STALL * 3;
let (batcher, effects) = batcher.on_groups(arrival, &workers, 0, vec![run("a", &[1])]);
assert!(matches!(batcher, BatcherStateMachine::Running(_)));
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![1])]);
}
#[test]
fn keys_pack_into_one_request_and_their_next_runs_wait_for_the_response() {
let now = Instant::now();
let workers = pool(&["w"]);
let batcher = packing_batcher(100, Duration::ZERO, 4, now);
let (batcher, effects) =
batcher.on_groups(now, &workers, 0, vec![run("a", &[1]), run("b", &[2])]);
assert_eq!(effects.sends.len(), 1);
assert_eq!(
shape(&effects.sends[0]),
vec![("a", vec![1]), ("b", vec![2])]
);
let request = effects.sends[0].request;
let (batcher, effects) = batcher.on_groups(now, &workers, 0, vec![run("a", &[3])]);
assert!(effects.sends.is_empty(), "a's first run is still in flight");
let (_, effects) = batcher.on_request_succeeded(now, &workers, request, 2);
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![3])]);
assert_eq!(effects.completions.len(), 1);
assert_eq!(effects.completions[0].offsets, vec![Offset(1), Offset(2)]);
assert_eq!(effects.evicted_keys, vec![Arc::<str>::from("b")]);
assert_eq!(
effects.key_acks,
vec![
KeyAck {
routing_key: "a".into(),
max_offset: 1
},
KeyAck {
routing_key: "b".into(),
max_offset: 2
},
]
);
}
#[test]
fn a_key_with_runs_under_two_epochs_sends_them_one_at_a_time() {
let now = Instant::now();
let budget = Duration::from_millis(30);
let workers = pool(&["w"]);
let batcher = packing_batcher(100, budget, 4, now);
let (batcher, _) = batcher.on_groups(now, &workers, 1, vec![run("k", &[1])]);
let (batcher, effects) = batcher.on_groups(now, &workers, 2, vec![run("k", &[2])]);
assert!(effects.sends.is_empty());
let (batcher, effects) = batcher.on_wakeup(now + budget, &workers);
assert_eq!(
effects.sends.len(),
1,
"the epoch-2 message waits for k's run"
);
assert_eq!(effects.sends[0].class.assignment_epoch, 1);
assert_eq!(shape(&effects.sends[0]), vec![("k", vec![1])]);
let request = effects.sends[0].request;
let later = now + budget * 2;
let (batcher, _) = batcher.on_request_succeeded(later, &workers, request, 1);
let (_, effects) = batcher.on_wakeup(later + budget, &workers);
assert_eq!(effects.sends[0].class.assignment_epoch, 2);
assert_eq!(shape(&effects.sends[0]), vec![("k", vec![2])]);
}
#[test]
fn a_transport_failure_retries_on_its_own_delay_whatever_the_pack_budget() {
let now = Instant::now();
let budget = Duration::from_millis(10);
let workers = pool(&["w"]);
let batcher = packing_batcher(2, budget, 4, now);
let (batcher, effects) =
batcher.on_groups(now, &workers, 0, vec![run("a", &[1]), run("b", &[2])]);
let request = effects.sends[0].request;
let messages = vec![message("a", 0, 1), message("b", 0, 2)];
let (batcher, effects) =
batcher.on_request_failed(now, &workers, request, FailureCause::Fault, messages);
assert_eq!(
effects.worker_outcomes,
vec![WorkerOutcome {
worker: WorkerId::from("w"),
fault: true
}]
);
assert!(effects.completions.is_empty());
assert_eq!(effects.next_wakeup, Some(now + FAULT_DELAY));
let (batcher, effects) = batcher.on_wakeup(now + budget, &workers);
assert!(
effects.sends.is_empty(),
"the pack budget does not pace retries"
);
let (_, effects) = batcher.on_wakeup(now + FAULT_DELAY, &workers);
assert_eq!(effects.sends.len(), 1, "the retries pack into one request");
assert!(effects.sends[0].class.replay);
}
#[test]
fn messages_below_the_target_leave_together_at_the_pack_deadline() {
let now = Instant::now();
let budget = Duration::from_millis(30);
let workers = pool(&["w"]);
let batcher = packing_batcher(100, budget, 4, now);
let (batcher, effects) = batcher.on_groups(now, &workers, 0, vec![run("a", &[1])]);
assert!(effects.sends.is_empty());
assert_eq!(effects.next_wakeup, Some(now + budget));
let (batcher, effects) =
batcher.on_groups(now + budget / 2, &workers, 0, vec![run("b", &[2])]);
assert!(effects.sends.is_empty());
assert_eq!(effects.next_wakeup, Some(now + budget));
let (_, effects) = batcher.on_wakeup(now + budget, &workers);
assert_eq!(
shape(&effects.sends[0]),
vec![("a", vec![1]), ("b", vec![2])]
);
}
#[test]
fn a_saturated_pool_keeps_requests_full_instead_of_claiming_keys_early() {
let now = Instant::now();
let workers = pool(&["w"]);
let batcher = packing_batcher(4, Duration::ZERO, 1, now);
let first: Vec<_> = (0..4).map(|n| run(&format!("k{n}"), &[n])).collect();
let (mut batcher, effects) = batcher.on_groups(now, &workers, 0, first);
let request = effects.sends[0].request;
for n in 4..10 {
let effects;
(batcher, effects) =
batcher.on_groups(now, &workers, 0, vec![run(&format!("k{n}"), &[n])]);
assert!(effects.sends.is_empty(), "the only slot is busy");
}
let (batcher, effects) = batcher.on_groups(now, &workers, 0, vec![run("k4", &[10])]);
assert!(effects.sends.is_empty());
let (_, effects) = batcher.on_request_succeeded(now, &workers, request, 4);
assert_eq!(effects.sends.len(), 1);
assert_eq!(
shape(&effects.sends[0]),
vec![("k4", vec![4, 10]), ("k5", vec![5]), ("k6", vec![6]),],
"the freed slot gets a full request, and k4's later message joins its run"
);
}
#[test]
fn a_hot_keys_backlog_leaves_in_capped_runs_while_other_keys_keep_moving() {
let now = Instant::now();
let workers = pool(&["w"]);
let batcher = packing_batcher(2, Duration::ZERO, 2, now);
let (batcher, effects) = batcher.on_groups(
now,
&workers,
0,
vec![run("hot", &[1, 2, 3, 4, 5, 6]), run("other", &[10])],
);
assert_eq!(
effects.sends.iter().map(shape).collect::<Vec<_>>(),
vec![vec![("hot", vec![1, 2])], vec![("other", vec![10])]]
);
let (failed, messages) = (effects.sends[0].request, sent_messages(&effects.sends[0]));
let (batcher, _) =
batcher.on_request_failed(now, &workers, failed, FailureCause::Fault, messages);
let retry_at = now + FAULT_DELAY;
let (mut batcher, effects) = batcher.on_wakeup(retry_at, &workers);
assert!(effects.sends[0].class.replay);
assert_eq!(shape(&effects.sends[0]), vec![("hot", vec![1, 2])]);
let mut request = effects.sends[0].request;
for expected in [vec![3, 4], vec![5, 6]] {
let effects;
(batcher, effects) = batcher.on_request_succeeded(retry_at, &workers, request, 2);
assert_eq!(shape(&effects.sends[0]), vec![("hot", expected)]);
request = effects.sends[0].request;
}
}
#[test]
fn a_run_cap_above_the_target_sends_a_hot_keys_backlog_in_one_round_trip() {
let now = Instant::now();
let workers = pool(&["w"]);
let packer = Packer::new(PackTargets {
events: NonZeroUsize::new(2),
bytes: None,
latency_budget: Duration::ZERO,
})
.with_run_cap(RunCap {
messages: NonZeroUsize::new(6),
bytes: None,
});
let batcher = batcher_with(packer, 2, now);
let (batcher, effects) = batcher.on_groups(now, &workers, 0, vec![run("hot", &[1])]);
let request = effects.sends[0].request;
let (batcher, effects) = batcher.on_groups(now, &workers, 0, vec![run("hot", &[2, 3, 4])]);
assert!(effects.sends.is_empty());
let (batcher, _) = batcher.on_groups(now, &workers, 0, vec![run("hot", &[5, 6, 7, 8])]);
let (_, effects) = batcher.on_request_succeeded(now, &workers, request, 1);
assert_eq!(
effects.sends.iter().map(shape).collect::<Vec<_>>(),
vec![vec![("hot", vec![2, 3, 4, 5, 6, 7])]]
);
}
#[test]
fn the_pack_budget_starts_when_a_slot_frees_not_when_messages_arrive() {
let now = Instant::now();
let budget = Duration::from_millis(30);
let workers = pool(&["w"]);
let batcher = packing_batcher(2, budget, 1, now);
let (batcher, effects) =
batcher.on_groups(now, &workers, 0, vec![run("a", &[1]), run("b", &[2])]);
let request = effects.sends[0].request;
let (batcher, effects) = batcher.on_groups(now, &workers, 0, vec![run("c", &[3])]);
assert!(effects.sends.is_empty());
let freed = now + budget * 2;
let (batcher, effects) = batcher.on_request_succeeded(freed, &workers, request, 2);
assert!(effects.sends.is_empty());
assert_eq!(effects.next_wakeup, Some(freed + budget));
let (_, effects) = batcher.on_wakeup(freed + budget, &workers);
assert_eq!(shape(&effects.sends[0]), vec![("c", vec![3])]);
}
#[test]
fn shutdown_sends_messages_waiting_for_the_pack_deadline_at_once() {
let now = Instant::now();
let workers = pool(&["w"]);
let batcher = packing_batcher(100, Duration::from_secs(10), 4, now);
let (batcher, _) = batcher.on_groups(now, &workers, 0, vec![run("a", &[1])]);
let (batcher, effects) = batcher.on_shutdown(now, &workers);
assert!(matches!(batcher, BatcherStateMachine::Draining(_)));
let request = effects.sends[0].request;
let (batcher, effects) = batcher.on_request_succeeded(now, &workers, request, 1);
assert!(matches!(batcher, BatcherStateMachine::Stopped));
assert_eq!(effects.next_wakeup, None);
}
#[test]
fn messages_waiting_out_the_pack_budget_do_not_trip_the_stall_check() {
let start = Instant::now();
let budget = STALL / 2;
let workers = pool(&["w"]);
let batcher = packing_batcher(100, budget, 4, start);
let arrival = start + STALL * 3;
let (batcher, effects) = batcher.on_groups(arrival, &workers, 0, vec![run("a", &[1])]);
assert!(matches!(batcher, BatcherStateMachine::Running(_)));
assert_eq!(effects.next_wakeup, Some(arrival + budget));
let (batcher, effects) = batcher.on_wakeup(arrival + budget, &workers);
assert!(matches!(batcher, BatcherStateMachine::Running(_)));
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![1])]);
// Waiting the pack budget again would pass the stall deadline.
let failed_at = arrival + budget + Duration::from_secs(1);
let (batcher, _) = batcher.on_request_failed(
failed_at,
&workers,
effects.sends[0].request,
FailureCause::Fault,
vec![message("a", 0, 1)],
);
let (batcher, effects) = batcher.on_wakeup(failed_at + FAULT_DELAY, &workers);
assert!(matches!(batcher, BatcherStateMachine::Running(_)));
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![1])]);
assert!(effects.sends[0].class.replay);
}
#[test]
fn a_revoke_of_every_message_waiting_for_the_pack_deadline_releases_the_slot() {
let now = Instant::now();
let budget = Duration::from_secs(10);
let workers = pool(&["w"]);
let batcher = packing_batcher(100, budget, 4, now);
let (batcher, effects) = batcher.on_groups(now, &workers, 0, vec![run("a", &[1])]);
assert!(effects.sends.is_empty());
let (batcher, effects) =
batcher.on_partitions_revoked(now, REVOKE, &[("events".to_string(), 0)]);
assert_eq!(effects.evicted_keys, vec![Arc::<str>::from("a")]);
assert_eq!(batcher.pending_messages(), 0);
let (_, effects) = batcher.on_wakeup(now + budget, &workers);
assert!(effects.sends.is_empty());
assert_eq!(effects.next_wakeup, None);
}
#[test]
fn every_offset_completes_exactly_once_across_failures_partials_retries_and_packing() {
let now = Instant::now();
let retry_at = now + FAULT_DELAY;
let workers = pool(&["w1", "w2"]);
let mut completed = Vec::new();
let mut record = |effects: &Effects| {
for completion in &effects.completions {
completed.extend(completion.offsets.iter().map(|offset| offset.0));
}
};
let (batcher, effects) = packing_batcher(3, Duration::ZERO, 2, now).on_groups(
now,
&workers,
0,
vec![
run("a", &[1, 2]),
run("b", &[3]),
run("c", &[4]),
run("d", &[5, 6]),
],
);
assert_eq!(
effects.sends.iter().map(shape).collect::<Vec<_>>(),
vec![
vec![("a", vec![1, 2]), ("b", vec![3])],
vec![("c", vec![4]), ("d", vec![5, 6])],
]
);
let (failed, failed_messages) =
(effects.sends[0].request, sent_messages(&effects.sends[0]));
let succeeded = effects.sends[1].request;
let (batcher, _) =
batcher.on_request_failed(now, &workers, failed, FailureCause::Fault, failed_messages);
let (batcher, effects) = batcher.on_groups(now, &workers, 0, vec![run("a", &[7])]);
assert!(effects.sends.is_empty(), "a is claimed by its replay");
let (batcher, effects) = batcher.on_request_succeeded(now, &workers, succeeded, 3);
record(&effects);
let (batcher, effects) = batcher.on_wakeup(retry_at, &workers);
assert!(effects.sends[0].class.replay);
assert_eq!(
shape(&effects.sends[0]),
vec![("a", vec![1, 2]), ("b", vec![3])]
);
let replay = effects.sends[0].request;
let (batcher, effects) =
batcher.on_request_partial(retry_at, &workers, replay, 2, vec![message("a", 0, 1)]);
record(&effects);
assert!(effects.sends[0].class.replay);
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![1])]);
let resend = effects.sends[0].request;
let (batcher, effects) = batcher.on_request_succeeded(retry_at, &workers, resend, 1);
record(&effects);
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![7])]);
let last = effects.sends[0].request;
let (batcher, effects) = batcher.on_request_succeeded(retry_at, &workers, last, 1);
record(&effects);
completed.sort_unstable();
assert_eq!(completed, vec![1, 2, 3, 4, 5, 6, 7]);
assert_eq!(batcher.pending_messages(), 0);
assert_eq!(batcher.in_flight_messages(), 0);
}
#[test]
fn a_worker_accepting_fewer_messages_than_sent_fails_the_state_machine() {
let now = Instant::now();
let workers = pool(&["w"]);
let batcher = packing_batcher(4, Duration::ZERO, 4, now);
let (batcher, effects) = batcher.on_groups(now, &workers, 0, vec![run("a", &[1, 2])]);
let request = effects.sends[0].request;
let (batcher, effects) = batcher.on_request_succeeded(now, &workers, request, 1);
assert!(matches!(batcher, BatcherStateMachine::Failed));
assert!(effects.fatal.is_some());
}
#[test]
fn an_accepted_request_completes_each_partition_and_acks_keyed_messages_on_the_first_partition()
{
let now = Instant::now();
let workers = pool(&["w"]);
let batcher = packing_batcher(2, Duration::ZERO, 4, now);
let keyed = KeyRun {
routing_key: "a".into(),
messages: vec![message("a", 0, 1), message("a", 1, 2)],
};
let unkeyed = KeyRun {
routing_key: ":2:5".into(),
messages: vec![SerializedKafkaMessage {
key: None,
..message("unkeyed", 2, 5)
}],
};
let (batcher, effects) = batcher.on_groups(now, &workers, 0, vec![keyed, unkeyed]);
let (keyed_request, unkeyed_request) = (effects.sends[0].request, effects.sends[1].request);
let (batcher, effects) = batcher.on_request_succeeded(now, &workers, keyed_request, 2);
let completed: Vec<_> = effects
.completions
.iter()
.map(|completion| (completion.partition.0, completion.offsets.clone()))
.collect();
assert_eq!(completed, vec![(0, vec![Offset(1)]), (1, vec![Offset(2)])]);
assert_eq!(
effects.key_acks,
vec![KeyAck {
routing_key: "a".into(),
max_offset: 1
}]
);
let (_, effects) = batcher.on_request_succeeded(now, &workers, unkeyed_request, 1);
assert_eq!(effects.completions[0].offsets, vec![Offset(5)]);
assert!(effects.key_acks.is_empty());
}
#[test]
fn a_partial_leaving_a_keys_first_partition_unfinished_resends_it_without_a_violation() {
let now = Instant::now();
let workers = pool(&["w"]);
let sentinel = KeyOrderSentinel::new();
let run = KeyRun {
routing_key: "a".into(),
messages: vec![message("a", 0, 10), message("a", 1, 100)],
};
let (batcher, effects) =
packing_batcher(2, Duration::ZERO, 4, now).on_groups(now, &workers, 0, vec![run]);
assert!(apply_to_sentinel(&sentinel, &effects).is_empty());
let request = effects.sends[0].request;
let (_, effects) =
batcher.on_request_partial(now, &workers, request, 1, vec![message("a", 0, 10)]);
assert_eq!(effects.completions[0].offsets, vec![Offset(100)]);
assert!(
effects.key_acks.is_empty(),
"partition 1's offset is no mark for partition 0"
);
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![10])]);
assert!(apply_to_sentinel(&sentinel, &effects).is_empty());
}
#[test]
fn a_failed_run_spanning_a_revoked_partition_replays_only_the_kept_partition_in_order() {
let now = Instant::now();
let workers = pool(&["w"]);
let spanning = KeyRun {
routing_key: "a".into(),
messages: vec![message("a", 0, 1), message("a", 1, 7)],
};
let (batcher, effects) =
packing_batcher(4, Duration::ZERO, 4, now).on_groups(now, &workers, 0, vec![spanning]);
let (request, messages) = (effects.sends[0].request, sent_messages(&effects.sends[0]));
let later = KeyRun {
routing_key: "a".into(),
messages: vec![message("a", 1, 8)],
};
let (batcher, effects) = batcher.on_groups(now, &workers, 0, vec![later]);
assert!(effects.sends.is_empty());
let (batcher, effects) =
batcher.on_partitions_revoked(now, REVOKE, &[("events".to_string(), 0)]);
assert!(effects.evicted_keys.is_empty(), "a's run is in flight");
let (batcher, _) =
batcher.on_request_failed(now, &workers, request, FailureCause::Fault, messages);
let retry_at = now + FAULT_DELAY;
let (batcher, effects) = batcher.on_wakeup(retry_at, &workers);
assert!(effects.sends[0].class.replay);
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![7])]);
let replay = effects.sends[0].request;
let (_, effects) = batcher.on_request_succeeded(retry_at, &workers, replay, 1);
assert_eq!(effects.completions[0].offsets, vec![Offset(7)]);
assert!(!effects.sends[0].class.replay);
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![8])]);
}
#[test]
fn a_revoke_then_reassign_drops_the_old_requeue_and_sends_the_new_epoch_run_once() {
let now = Instant::now();
let workers = pool(&["w"]);
let (batcher, effects) = packing_batcher(4, Duration::ZERO, 4, now).on_groups(
now,
&workers,
1,
vec![run("a", &[1, 2])],
);
let (request, messages) = (effects.sends[0].request, sent_messages(&effects.sends[0]));
let (batcher, _) = batcher.on_partitions_revoked(now, REVOKE, &[("events".to_string(), 0)]);
// The new owner of the partition replays the uncommitted offsets.
let mut replay = run("a", &[1, 2, 3]);
for message in &mut replay.messages {
message.generation = 2;
}
let (batcher, effects) = batcher.on_groups(now, &workers, 2, vec![replay]);
assert!(effects.sends.is_empty(), "a's epoch-1 run is still out");
let (batcher, effects) =
batcher.on_request_failed(now, &workers, request, FailureCause::Fault, messages);
assert_eq!(effects.sends.len(), 1, "the epoch-2 run goes at once");
assert_eq!(effects.sends[0].class.assignment_epoch, 2);
assert!(!effects.sends[0].class.replay);
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![1, 2, 3])]);
let request = effects.sends[0].request;
let (batcher, effects) = batcher.on_request_succeeded(now, &workers, request, 3);
assert_eq!(effects.completions.len(), 1);
assert_eq!(effects.completions[0].assignment_epoch, 2);
assert_eq!(effects.completions[0].generation, 2);
assert_eq!(
effects.completions[0].offsets,
vec![Offset(1), Offset(2), Offset(3)]
);
assert_eq!(batcher.pending_messages(), 0);
assert_eq!(batcher.in_flight_messages(), 0);
}
#[test]
fn a_second_response_for_the_same_request_fails_the_state_machine() {
let now = Instant::now();
let workers = pool(&["w"]);
let (batcher, effects) = batcher(4, now).on_groups(now, &workers, 0, vec![run("a", &[1])]);
let request = effects.sends[0].request;
let (batcher, _) = batcher.on_request_succeeded(now, &workers, request, 1);
let (batcher, effects) = batcher.on_request_succeeded(now, &workers, request, 1);
assert!(matches!(batcher, BatcherStateMachine::Failed));
assert!(effects.fatal.is_some());
assert!(effects.completions.is_empty());
}
#[rstest]
#[case::a_middle_message_of_a_shared_key(&[2], &[1, 3, 4], Some(1))]
#[case::the_tail_of_a_key(&[2, 3], &[1, 4], Some(1))]
#[case::a_whole_key(&[1, 2, 3], &[4], None)]
fn a_partial_completes_the_accepted_offsets_and_requeues_the_unfinished_ones_at_the_front(
#[case] unfinished: &[i64],
#[case] completed: &[i64],
#[case] ack_for_a: Option<i64>,
) {
let now = Instant::now();
let workers = pool(&["w"]);
let sentinel = KeyOrderSentinel::new();
let (batcher, effects) = packing_batcher(4, Duration::ZERO, 4, now).on_groups(
now,
&workers,
0,
vec![run("a", &[1, 2, 3]), run("b", &[4])],
);
assert_eq!(
shape(&effects.sends[0]),
vec![("a", vec![1, 2, 3]), ("b", vec![4])]
);
assert!(apply_to_sentinel(&sentinel, &effects).is_empty());
let request = effects.sends[0].request;
let (batcher, effects) = batcher.on_groups(now, &workers, 0, vec![run("a", &[5])]);
assert!(effects.sends.is_empty(), "a's run is in flight");
let accepted = 4 - unfinished.len() as u32;
let unfinished_messages = unfinished
.iter()
.map(|&offset| message("a", 0, offset))
.collect();
let (batcher, effects) =
batcher.on_request_partial(now, &workers, request, accepted, unfinished_messages);
assert_eq!(
effects.completions[0].offsets,
completed
.iter()
.map(|&offset| Offset(offset))
.collect::<Vec<_>>()
);
let mut expected_acks = Vec::new();
if let Some(max_offset) = ack_for_a {
expected_acks.push(KeyAck {
routing_key: "a".into(),
max_offset,
});
}
expected_acks.push(KeyAck {
routing_key: "b".into(),
max_offset: 4,
});
assert_eq!(effects.key_acks, expected_acks);
assert_eq!(effects.evicted_keys, vec![Arc::<str>::from("b")]);
assert_eq!(
effects.sends.len(),
1,
"a's fresh message waits for the replay"
);
assert!(effects.sends[0].class.replay);
assert_eq!(shape(&effects.sends[0]), vec![("a", unfinished.to_vec())]);
let violations = apply_to_sentinel(&sentinel, &effects);
assert!(
violations.is_empty(),
"the ACK mark stops before the unfinished message, so its resend is legal: \
{violations:?}"
);
let replay = effects.sends[0].request;
let (_, effects) =
batcher.on_request_succeeded(now, &workers, replay, unfinished.len() as u32);
assert_eq!(
effects.completions[0].offsets,
unfinished
.iter()
.map(|&offset| Offset(offset))
.collect::<Vec<_>>()
);
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![5])]);
let violations = apply_to_sentinel(&sentinel, &effects);
assert!(
violations.is_empty(),
"the fresh send after the resend is legal: {violations:?}"
);
}
#[test]
fn a_partial_that_does_not_match_the_request_fails_the_state_machine() {
let now = Instant::now();
let workers = pool(&["w"]);
let (batcher, effects) = batcher(4, now).on_groups(now, &workers, 0, vec![run("a", &[1])]);
let request = effects.sends[0].request;
let (batcher, effects) =
batcher.on_request_partial(now, &workers, request, 0, vec![message("a", 0, 2)]);
assert!(matches!(batcher, BatcherStateMachine::Failed));
assert!(effects.fatal.is_some());
}
#[test]
fn partials_that_accept_nothing_do_not_hold_off_the_watchdog() {
let now = Instant::now();
let workers = pool(&["w"]);
let (batcher, effects) = batcher(4, now).on_groups(now, &workers, 0, vec![run("a", &[1])]);
let request = effects.sends[0].request;
let (batcher, effects) = batcher.on_request_partial(
now + STALL / 2,
&workers,
request,
0,
vec![message("a", 0, 1)],
);
assert!(effects.fatal.is_none());
let resend = effects.sends[0].request;
let (batcher, effects) =
batcher.on_request_partial(now + STALL, &workers, resend, 0, vec![message("a", 0, 1)]);
assert!(matches!(batcher, BatcherStateMachine::Failed));
assert!(effects.fatal.is_some());
}
#[test]
fn a_key_that_keeps_running_out_of_budget_resends_alone_without_one() {
let now = Instant::now();
let retry_at = now + FAULT_DELAY;
let workers = pool(&["w"]);
let (batcher, effects) =
budgeted_batcher(4, 2, now).on_groups(now, &workers, 0, vec![run("a", &[1, 2, 3])]);
let first = effects.sends[0].request;
let (batcher, effects) = batcher.on_request_partial(
now,
&workers,
first,
1,
vec![message("a", 0, 2), message("a", 0, 3)],
);
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![2, 3])]);
assert_eq!(effects.sends[0].soft_budget, Some(BUDGET));
let second = effects.sends[0].request;
let (batcher, effects) =
batcher.on_request_partial(now, &workers, second, 1, vec![message("a", 0, 3)]);
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![3])]);
assert_eq!(effects.sends[0].soft_budget, None);
assert!(effects.sends[0].class.unbudgeted);
let escalated = effects.sends[0].request;
let (batcher, effects) = batcher.on_groups(now, &workers, 0, vec![run("b", &[4])]);
let budgeted = effects.sends[0].request;
let (batcher, _) = batcher.on_request_failed(
now,
&workers,
escalated,
FailureCause::Fault,
vec![message("a", 0, 3)],
);
let (batcher, _) = batcher.on_request_failed(
now,
&workers,
budgeted,
FailureCause::Fault,
vec![message("b", 0, 4)],
);
let (_, effects) = batcher.on_wakeup(retry_at, &workers);
let sends: Vec<_> = effects
.sends
.iter()
.map(|send| (shape(send), send.soft_budget))
.collect();
assert_eq!(
sends,
vec![
(vec![("a", vec![3])], None),
(vec![("b", vec![4])], Some(BUDGET)),
],
"a failure keeps the escalation, the escalated replay goes first, and a budgeted \
replay never rides along"
);
}
#[test]
fn a_partial_that_finished_nothing_resends_without_a_budget_at_once() {
let now = Instant::now();
let workers = pool(&["w"]);
let (batcher, effects) =
budgeted_batcher(4, 3, now).on_groups(now, &workers, 0, vec![run("a", &[1, 2])]);
let request = effects.sends[0].request;
let (_, effects) = batcher.on_request_partial(
now,
&workers,
request,
0,
vec![message("a", 0, 1), message("a", 0, 2)],
);
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![1, 2])]);
assert_eq!(effects.sends[0].soft_budget, None);
assert!(effects.sends[0].class.unbudgeted);
}
#[test]
fn a_finished_run_resets_the_escalation_count() {
let now = Instant::now();
let workers = pool(&["w"]);
let (batcher, effects) =
budgeted_batcher(4, 2, now).on_groups(now, &workers, 0, vec![run("a", &[1, 2])]);
let first = effects.sends[0].request;
let (batcher, _) = batcher.on_groups(now, &workers, 0, vec![run("a", &[3, 4])]);
let (batcher, effects) =
batcher.on_request_partial(now, &workers, first, 1, vec![message("a", 0, 2)]);
let resend = effects.sends[0].request;
let (batcher, effects) = batcher.on_request_succeeded(now, &workers, resend, 1);
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![3, 4])]);
let next = effects.sends[0].request;
let (_, effects) =
batcher.on_request_partial(now, &workers, next, 1, vec![message("a", 0, 4)]);
assert_eq!(
effects.sends[0].soft_budget,
Some(BUDGET),
"the earlier unfinished attempt no longer counts"
);
}
#[test]
fn a_failure_handing_back_extra_messages_fails_the_state_machine() {
let now = Instant::now();
let workers = pool(&["w"]);
let (batcher, effects) = batcher(4, now).on_groups(now, &workers, 0, vec![run("a", &[1])]);
let request = effects.sends[0].request;
let (batcher, effects) = batcher.on_request_failed(
now,
&workers,
request,
FailureCause::Fault,
vec![message("a", 0, 1), message("a", 0, 2)],
);
assert!(matches!(batcher, BatcherStateMachine::Failed));
assert!(effects.fatal.is_some());
}
#[test]
fn a_revoke_during_a_replay_wait_leaves_no_wait_behind_for_a_fresh_sibling_partition() {
let now = Instant::now();
let workers = pool(&["w"]);
let (batcher, effects) = batcher(4, now).on_groups(now, &workers, 0, vec![run("a", &[1])]);
let (request, messages) = (effects.sends[0].request, sent_messages(&effects.sends[0]));
let sibling = KeyRun {
routing_key: "a".into(),
messages: vec![message("a", 1, 7)],
};
let (batcher, _) = batcher.on_groups(now, &workers, 0, vec![sibling]);
let (batcher, _) =
batcher.on_request_failed(now, &workers, request, FailureCause::Fault, messages);
let (batcher, effects) =
batcher.on_partitions_revoked(now, REVOKE, &[("events".to_string(), 0)]);
assert_eq!(effects.next_wakeup, Some(now), "a is ready again at once");
let (_, effects) = batcher.on_wakeup(now, &workers);
assert!(!effects.sends[0].class.replay);
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![7])]);
}
#[test]
fn the_watchdog_fires_once_overlapping_failures_drain_even_with_waiting_retries() {
let now = Instant::now();
let workers = pool(&["w"]);
let (mut batcher, effects) =
batcher(2, now).on_groups(now, &workers, 0, vec![run("a", &[1]), run("b", &[2])]);
let mut outstanding: VecDeque<_> = effects
.sends
.iter()
.map(|send| (send.request, sent_messages(send)))
.collect();
let mut at = now;
let (failed, fired_at) = loop {
at += BUSY_DELAY;
assert!(at < now + STALL * 2, "the watchdog never fired");
let (request, messages) = outstanding.pop_front().expect("a request in flight");
let (next, effects) =
batcher.on_request_failed(at, &workers, request, FailureCause::Busy, messages);
if effects.fatal.is_some() {
break (next, at);
}
let (next, effects) = next.on_wakeup(at + BUSY_DELAY, &workers);
outstanding.extend(
effects
.sends
.iter()
.map(|send| (send.request, sent_messages(send))),
);
batcher = next;
};
assert!(matches!(failed, BatcherStateMachine::Failed));
assert!(fired_at <= now + STALL + BUSY_DELAY * 3);
}
#[test]
fn draining_stops_when_an_in_flight_run_of_a_revoked_partition_fails() {
let now = Instant::now();
let workers = pool(&["w"]);
let (batcher, effects) = batcher(4, now).on_groups(now, &workers, 0, vec![run("a", &[1])]);
let (request, messages) = (effects.sends[0].request, sent_messages(&effects.sends[0]));
let (batcher, _) = batcher.on_shutdown(now, &workers);
let (batcher, _) = batcher.on_partitions_revoked(now, REVOKE, &[("events".to_string(), 0)]);
assert!(
matches!(batcher, BatcherStateMachine::Draining(_)),
"a is in flight"
);
let (batcher, effects) =
batcher.on_request_failed(now, &workers, request, FailureCause::Fault, messages);
assert!(matches!(batcher, BatcherStateMachine::Stopped));
assert!(effects.sends.is_empty());
assert!(effects.completions.is_empty());
assert_eq!(effects.next_wakeup, None);
}
#[test]
fn a_partial_response_of_a_draining_partition_completes_only_what_was_accepted() {
let now = Instant::now();
let workers = pool(&["w"]);
let (batcher, effects) = packing_batcher(3, Duration::ZERO, 4, now).on_groups(
now,
&workers,
0,
vec![run("a", &[1, 2, 3])],
);
let request = effects.sends[0].request;
let (batcher, effects) =
batcher.on_partitions_revoked(now, REVOKE, &[("events".to_string(), 0)]);
assert!(effects.drained.is_empty(), "a is in flight");
let (_, effects) =
batcher.on_request_partial(now, &workers, request, 2, vec![message("a", 0, 2)]);
assert_eq!(effects.completions[0].offsets, vec![Offset(1), Offset(3)]);
assert!(
effects.sends.is_empty(),
"the unfinished offset is not resent"
);
assert_eq!(effects.drained, vec![REVOKE]);
}
const REVOKE: RevokeId = RevokeId(1);
const OTHER_REVOKE: RevokeId = RevokeId(2);
fn partition(number: i32) -> Vec<(String, i32)> {
vec![("events".to_string(), number)]
}
fn key_run(key: &str, messages: &[(i32, i64)]) -> KeyRun {
KeyRun {
routing_key: key.into(),
messages: messages
.iter()
.map(|&(partition, offset)| message(key, partition, offset))
.collect(),
}
}
fn request_of(effects: &Effects, key: &str) -> RequestId {
effects
.sends
.iter()
.find(|send| &*send.runs[0].routing_key == key)
.expect("a request for the key")
.request
}
fn completed_offsets(effects: &Effects) -> Vec<i64> {
effects
.completions
.iter()
.flat_map(|completion| completion.offsets.iter().map(|offset| offset.0))
.collect()
}
#[test]
fn a_drain_waits_only_for_the_requests_carrying_its_partitions() {
let now = Instant::now();
let workers = pool(&["w"]);
let (batcher, effects) = batcher(4, now).on_groups(
now,
&workers,
0,
vec![
key_run("a", &[(0, 1)]),
key_run("b", &[(1, 7)]),
key_run("c", &[(1, 8)]),
],
);
let (on_p0, on_p1) = (request_of(&effects, "a"), request_of(&effects, "b"));
let (batcher, effects) = batcher.on_partitions_revoked(now, REVOKE, &partition(0));
assert!(effects.drained.is_empty());
let (batcher, effects) = batcher.on_request_succeeded(now, &workers, on_p1, 1);
assert!(
effects.drained.is_empty(),
"partition 0's request is in flight"
);
let (_, effects) = batcher.on_request_succeeded(now, &workers, on_p0, 1);
assert_eq!(
effects.drained,
vec![REVOKE],
"c's request for partition 1 is still in flight"
);
}
#[test]
fn a_failed_run_spanning_a_draining_partition_ends_the_drain_and_replays_only_the_kept_partition(
) {
let now = Instant::now();
let workers = pool(&["w"]);
let (batcher, effects) = packing_batcher(4, Duration::ZERO, 4, now).on_groups(
now,
&workers,
0,
vec![key_run("a", &[(0, 1), (1, 7)])],
);
let (request, messages) = (effects.sends[0].request, sent_messages(&effects.sends[0]));
let (batcher, _) = batcher.on_partitions_revoked(now, REVOKE, &partition(0));
let (batcher, effects) =
batcher.on_request_failed(now, &workers, request, FailureCause::Fault, messages);
assert_eq!(
effects.drained,
vec![REVOKE],
"partition 1's replay is not awaited"
);
let (_, effects) = batcher.on_wakeup(now + FAULT_DELAY, &workers);
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![7])]);
}
#[test]
fn a_partial_response_spanning_a_draining_partition_resends_only_the_kept_partition() {
let now = Instant::now();
let workers = pool(&["w"]);
let (batcher, effects) = packing_batcher(4, Duration::ZERO, 4, now).on_groups(
now,
&workers,
0,
vec![key_run("a", &[(0, 1), (1, 7), (0, 2), (1, 8)])],
);
let request = effects.sends[0].request;
let (batcher, _) = batcher.on_partitions_revoked(now, REVOKE, &partition(0));
let (_, effects) = batcher.on_request_partial(
now,
&workers,
request,
2,
vec![message("a", 0, 2), message("a", 1, 8)],
);
assert_eq!(completed_offsets(&effects), vec![1, 7]);
assert_eq!(shape(&effects.sends[0]), vec![("a", vec![8])]);
assert_eq!(effects.drained, vec![REVOKE]);
}
#[test]
fn two_drains_each_end_when_their_own_requests_settle() {
let now = Instant::now();
let workers = pool(&["w"]);
let (batcher, effects) = batcher(4, now).on_groups(
now,
&workers,
0,
vec![key_run("a", &[(0, 1)]), key_run("b", &[(1, 7)])],
);
let (on_p0, on_p1) = (request_of(&effects, "a"), request_of(&effects, "b"));
let (batcher, _) = batcher.on_partitions_revoked(now, REVOKE, &partition(0));
let (batcher, _) = batcher.on_partitions_revoked(now, OTHER_REVOKE, &partition(1));
let (batcher, effects) = batcher.on_request_succeeded(now, &workers, on_p1, 1);
assert_eq!(effects.drained, vec![OTHER_REVOKE]);
let (_, effects) = batcher.on_request_succeeded(now, &workers, on_p0, 1);
assert_eq!(effects.drained, vec![REVOKE]);
}
fn queued_without_a_worker(now: Instant) -> BatcherStateMachine {
let (batcher, _) = batcher(4, now).on_groups(now, &pool(&[]), 0, vec![run("a", &[1])]);
batcher
}
fn waiting_for_a_retry(now: Instant) -> BatcherStateMachine {
let workers = pool(&["w"]);
let (batcher, effects) = batcher(4, now).on_groups(now, &workers, 0, vec![run("a", &[1])]);
let (request, messages) = (effects.sends[0].request, sent_messages(&effects.sends[0]));
let (batcher, _) =
batcher.on_request_failed(now, &workers, request, FailureCause::Busy, messages);
batcher
}
#[rstest]
#[case::queued_without_a_worker(queued_without_a_worker)]
#[case::waiting_for_a_retry(waiting_for_a_retry)]
fn a_drain_with_nothing_in_flight_ends_at_once_and_its_messages_are_never_sent(
#[case] setup: fn(Instant) -> BatcherStateMachine,
) {
let now = Instant::now();
let (batcher, effects) = setup(now).on_partitions_revoked(now, REVOKE, &partition(0));
assert_eq!(effects.drained, vec![REVOKE]);
let (_, effects) = batcher.on_wakeup(now + FAULT_DELAY, &pool(&["w"]));
assert!(effects.sends.is_empty());
}
#[test]
fn a_drain_during_shutdown_ends_with_the_last_request() {
let now = Instant::now();
let workers = pool(&["w"]);
let (batcher, effects) = batcher(4, now).on_groups(now, &workers, 0, vec![run("a", &[1])]);
let request = effects.sends[0].request;
let (batcher, _) = batcher.on_shutdown(now, &workers);
let (batcher, effects) = batcher.on_partitions_revoked(now, REVOKE, &partition(0));
assert!(effects.drained.is_empty());
let (batcher, effects) = batcher.on_request_succeeded(now, &workers, request, 1);
assert!(matches!(batcher, BatcherStateMachine::Stopped));
assert_eq!(completed_offsets(&effects), vec![1]);
assert_eq!(effects.drained, vec![REVOKE]);
}
}