: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::collections::VecDeque;
use std::fmt;
use std::ops::{Add, AddAssign};
use crate::charge::Charge;
use crate::types::Offset;
#[derive(Debug)]
struct Slot {
complete: bool,
charge: Charge,
delivered: bool,
}
/// A charge or completion the ledger's window cannot account for. The ledger
/// checks each offset as it applies it, so on an error the window holds the
/// offsets applied before the offending one; the owner discards the ledger
/// rather than reasoning about that state.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum LedgerError {
/// A charge delivered an offset that is not above every offset already
/// recorded.
OffsetNotAboveWindow { offset: Offset, next: Offset },
/// A completion arrived before any delivery was charged.
CompletionBeforeDelivery { offset: Offset },
/// A completion for an offset `take_frontier` already consumed.
CompletionBelowWindow { offset: Offset, base: Offset },
/// A completion for an offset the window never charged.
CompletionUncharged { offset: Offset },
/// A completion for an offset completed before.
CompletedTwice { offset: Offset },
}
impl LedgerError {
/// A stable label for metrics.
pub fn kind(&self) -> &'static str {
match self {
LedgerError::OffsetNotAboveWindow { .. } => "offset_not_above_window",
LedgerError::CompletionBeforeDelivery { .. } => "completion_before_delivery",
LedgerError::CompletionBelowWindow { .. } => "completion_below_window",
LedgerError::CompletionUncharged { .. } => "completion_uncharged",
LedgerError::CompletedTwice { .. } => "completed_twice",
}
}
}
impl fmt::Display for LedgerError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
LedgerError::OffsetNotAboveWindow { offset, next } => {
write!(
f,
"offset {offset} delivered but not above the window's next offset {next}"
)
}
LedgerError::CompletionBeforeDelivery { offset } => {
write!(f, "offset {offset} completed before any delivery")
}
LedgerError::CompletionBelowWindow { offset, base } => {
write!(f, "offset {offset} completed below the window base {base}")
}
LedgerError::CompletionUncharged { offset } => {
write!(f, "offset {offset} completed but never charged")
}
LedgerError::CompletedTwice { offset } => write!(f, "offset {offset} completed twice"),
}
}
}
impl std::error::Error for LedgerError {}
/// A consumed contiguous prefix: the window base it started from, its
/// commit-ready frontier, the charge it covers, and how many of its offsets
/// Kafka never delivered.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct TakenFrontier {
pub first: Offset,
pub offset: Offset,
pub charge: Charge,
pub gap_offset_count: usize,
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct Held {
pub offsets: usize,
pub charge: Charge,
}
impl Add for Held {
type Output = Held;
fn add(self, rhs: Held) -> Held {
Held {
offsets: self.offsets + rhs.offsets,
charge: self.charge + rhs.charge,
}
}
}
impl AddAssign for Held {
fn add_assign(&mut self, rhs: Held) {
*self = *self + rhs;
}
}
/// Per-partition offset accounting: record offsets as they are delivered,
/// complete them in any order, and read the frontier in Kafka's
/// committed-offset representation. Observing the frontier never changes it;
/// a commit point consumes it with `take_frontier`.
///
/// Charge every record the poll delivers, including records the caller drops
/// without processing: an omitted offset is indistinguishable from an offset
/// Kafka never delivered, and the frontier commits past it as if it held no
/// message.
///
/// A ledger lives for one partition assignment: create it on assign, drop it
/// on revoke. Kafka redelivers a partition from its committed offset after a
/// rebalance, so a ledger kept across assignments sees the redelivery as
/// duplicate delivery and rejects it. Completions from a previous
/// assignment's in-flight work must be discarded before they reach the new
/// ledger; it never charged those offsets and rejects them too. Both come
/// back as a [`LedgerError`]: the ledger never panics, so an owner holding
/// it under a lock stays usable.
#[derive(Debug)]
pub struct PartitionOffsetLedger {
/// The partition generation this ledger was founded under. The owner
/// compares it with the stamp on incoming work to drop work from an
/// earlier assignment.
generation: u64,
/// The offset of `slots[0]`; `None` until the first delivery.
base_offset: Option<Offset>,
/// Number of completed slots at the front of the window, kept current on
/// every completion so `frontier` stays O(1).
completed_prefix_len: usize,
/// Charge of every slot in the window, kept current on every charge and
/// take so `held` stays O(1).
held_charge: Charge,
/// A dense sliding window over one contiguous offset range: `charge`
/// appends at the back, `take_frontier` pops the front, and `complete`
/// indexes by offset minus `base_offset`. Every operation is amortized constant
/// time per offset.
slots: VecDeque<Slot>,
}
impl PartitionOffsetLedger {
pub fn new(generation: u64) -> Self {
Self {
generation,
base_offset: None,
completed_prefix_len: 0,
held_charge: Charge::ZERO,
slots: VecDeque::new(),
}
}
/// The partition generation this ledger was founded under.
pub fn generation(&self) -> u64 {
self.generation
}
/// Record offsets in delivery order and return their total charge. An
/// offset gap (transaction control records) never blocks the frontier and
/// carries no charge.
///
/// Fails when an offset is not above every offset already recorded.
/// Duplicate or out-of-order delivery is a caller bug, and recording it
/// would corrupt the commit accounting.
pub fn charge(
&mut self,
offset_charges: impl IntoIterator<Item = (Offset, Charge)>,
) -> Result<Charge, LedgerError> {
let mut total = Charge::ZERO;
for (offset, charge) in offset_charges {
let base_offset = *self.base_offset.get_or_insert(offset);
let next_offset = base_offset + self.slots.len();
if offset < next_offset {
return Err(LedgerError::OffsetNotAboveWindow {
offset,
next: next_offset,
});
}
// A gap becomes pre-completed zero-charge filler so the index
// math stays aligned with offsets.
for _ in 0..offset - next_offset {
self.slots.push_back(Slot {
complete: true,
charge: Charge::ZERO,
delivered: false,
});
}
self.slots.push_back(Slot {
complete: false,
charge,
delivered: true,
});
total += charge;
self.held_charge += charge;
}
Ok(total)
}
/// Mark delivered offsets complete in any order.
///
/// Fails when an offset was never charged, was completed before, or was
/// already consumed by `take_frontier`. Each case means the completion
/// does not belong to this ledger's window, and marking it would corrupt
/// the commit accounting.
pub fn complete(
&mut self,
offsets: impl IntoIterator<Item = Offset>,
) -> Result<(), LedgerError> {
for offset in offsets {
let Some(base_offset) = self.base_offset else {
return Err(LedgerError::CompletionBeforeDelivery { offset });
};
let slot_index = usize::try_from(offset - base_offset).map_err(|_| {
LedgerError::CompletionBelowWindow {
offset,
base: base_offset,
}
})?;
let slot = self
.slots
.get_mut(slot_index)
.ok_or(LedgerError::CompletionUncharged { offset })?;
if slot.complete {
return Err(LedgerError::CompletedTwice { offset });
}
slot.complete = true;
}
while self
.slots
.get(self.completed_prefix_len)
.is_some_and(|slot| slot.complete)
{
self.completed_prefix_len += 1;
}
Ok(())
}
/// The next offset to read: one past the highest contiguous completed
/// offset, in Kafka's committed-offset representation, so a commit uses
/// it verbatim. `None` before the first completion.
pub fn frontier(&self) -> Option<Offset> {
let base_offset = self.base_offset?;
(self.completed_prefix_len > 0).then(|| base_offset + self.completed_prefix_len)
}
pub fn take_frontier(&mut self) -> Option<TakenFrontier> {
let frontier_offset = self.frontier()?;
let window_base = self.base_offset.expect("a frontier implies a window base");
let mut charge = Charge::ZERO;
let mut gap_offset_count = 0;
for slot in self.slots.drain(..self.completed_prefix_len) {
charge += slot.charge;
if !slot.delivered {
gap_offset_count += 1;
}
}
self.held_charge -= charge;
self.base_offset = Some(frontier_offset);
self.completed_prefix_len = 0;
Some(TakenFrontier {
first: window_base,
offset: frontier_offset,
charge,
gap_offset_count,
})
}
/// What the window still holds: offsets charged and not yet drained by
/// `take_frontier`, and their charge.
pub fn held(&self) -> Held {
Held {
offsets: self.slots.len(),
charge: self.held_charge,
}
}
}
#[cfg(test)]
mod tests {
use super::*;
fn charge(offset: i64) -> (Offset, Charge) {
(
Offset(offset),
Charge {
events: 1,
bytes: 10,
},
)
}
#[test]
fn out_of_order_completion_does_not_move_the_frontier() {
let mut ledger = PartitionOffsetLedger::new(1);
ledger.charge([charge(0), charge(1), charge(2)]).unwrap();
ledger.complete([Offset(2)]).unwrap();
assert_eq!(ledger.frontier(), None);
assert_eq!(ledger.take_frontier(), None);
ledger.complete([Offset(0), Offset(1)]).unwrap();
assert_eq!(ledger.frontier(), Some(Offset(3)));
}
#[test]
fn a_partial_take_keeps_the_remainder_completable() {
let mut ledger = PartitionOffsetLedger::new(1);
ledger.charge([charge(0), charge(1), charge(2)]).unwrap();
ledger.complete([Offset(0)]).unwrap();
let taken = ledger.take_frontier().unwrap();
assert_eq!(taken.offset, Offset(1));
assert_eq!(taken.charge.events, 1);
assert_eq!(taken.gap_offset_count, 0);
assert_eq!(ledger.held().offsets, 2);
ledger.complete([Offset(1), Offset(2)]).unwrap();
assert_eq!(ledger.frontier(), Some(Offset(3)));
assert_eq!(ledger.take_frontier().unwrap().charge.events, 2);
}
#[test]
fn duplicate_delivery_is_rejected() {
let mut ledger = PartitionOffsetLedger::new(1);
ledger.charge([charge(0), charge(1)]).unwrap();
assert_eq!(
ledger.charge([charge(1)]),
Err(LedgerError::OffsetNotAboveWindow {
offset: Offset(1),
next: Offset(2),
})
);
}
#[test]
fn completion_before_any_delivery_is_rejected() {
let mut ledger = PartitionOffsetLedger::new(1);
assert_eq!(
ledger.complete([Offset(0)]),
Err(LedgerError::CompletionBeforeDelivery { offset: Offset(0) })
);
}
#[test]
fn double_completion_is_rejected() {
let mut ledger = PartitionOffsetLedger::new(1);
ledger.charge([charge(0)]).unwrap();
ledger.complete([Offset(0)]).unwrap();
assert_eq!(
ledger.complete([Offset(0)]),
Err(LedgerError::CompletedTwice { offset: Offset(0) })
);
}
#[test]
fn completing_an_undelivered_offset_is_rejected() {
let mut ledger = PartitionOffsetLedger::new(1);
ledger.charge([charge(0)]).unwrap();
assert_eq!(
ledger.complete([Offset(5)]),
Err(LedgerError::CompletionUncharged { offset: Offset(5) })
);
}
#[test]
fn completing_below_the_window_after_a_take_is_rejected() {
let mut ledger = PartitionOffsetLedger::new(1);
ledger.charge([charge(0), charge(1)]).unwrap();
ledger.complete([Offset(0)]).unwrap();
ledger.take_frontier().unwrap();
assert_eq!(
ledger.complete([Offset(0)]),
Err(LedgerError::CompletionBelowWindow {
offset: Offset(0),
base: Offset(1),
})
);
}
#[test]
fn frontier_is_idempotent_and_take_drains_it() {
let mut ledger = PartitionOffsetLedger::new(1);
ledger.charge([charge(0), charge(1)]).unwrap();
ledger.complete([Offset(0), Offset(1)]).unwrap();
assert_eq!(ledger.frontier(), Some(Offset(2)));
assert_eq!(ledger.frontier(), Some(Offset(2)));
assert_eq!(ledger.take_frontier().unwrap().charge.events, 2);
assert_eq!(ledger.held().offsets, 0);
}
#[test]
fn delivery_gaps_do_not_block_delivered_offsets() {
let mut ledger = PartitionOffsetLedger::new(1);
ledger.charge([charge(0), charge(3)]).unwrap();
ledger.complete([Offset(0), Offset(3)]).unwrap();
assert_eq!(ledger.frontier(), Some(Offset(4)));
}
#[test]
fn gap_filler_carries_no_charge_and_the_frontier_walks_over_it() {
let mut ledger = PartitionOffsetLedger::new(1);
ledger.charge([charge(0), charge(3)]).unwrap();
ledger.complete([Offset(0)]).unwrap();
assert_eq!(ledger.frontier(), Some(Offset(3)));
ledger.complete([Offset(3)]).unwrap();
let taken = ledger.take_frontier().unwrap();
assert_eq!(taken.offset, Offset(4));
assert_eq!(taken.charge.events, 2);
assert_eq!(
taken.gap_offset_count, 2,
"offsets 1 and 2 were never delivered"
);
}
#[test]
fn a_take_counts_each_gap_offset_once() {
let mut ledger = PartitionOffsetLedger::new(1);
ledger.charge([charge(0), charge(2), charge(5)]).unwrap();
ledger.complete([Offset(0), Offset(2)]).unwrap();
// Filler is complete by construction, so the frontier runs up to the
// incomplete offset 5 over the three undelivered offsets 1, 3 and 4.
let taken = ledger.take_frontier().unwrap();
assert_eq!(taken.offset, Offset(5));
assert_eq!(taken.gap_offset_count, 3);
assert_eq!(ledger.held().offsets, 1);
ledger.complete([Offset(5)]).unwrap();
let taken = ledger.take_frontier().unwrap();
assert_eq!(taken.offset, Offset(6));
assert_eq!(
taken.gap_offset_count, 0,
"drained filler is not counted again"
);
}
#[test]
fn held_charge_follows_charges_and_takes() {
let mut ledger = PartitionOffsetLedger::new(1);
ledger.charge([charge(0), charge(1), charge(3)]).unwrap();
assert_eq!(
ledger.held(),
Held {
offsets: 4,
charge: Charge {
events: 3,
bytes: 30
}
},
"gap filler holds a slot but no charge"
);
// The take drains the completed prefix, gap filler included.
ledger.complete([Offset(0), Offset(1)]).unwrap();
ledger.take_frontier().unwrap();
assert_eq!(
ledger.held(),
Held {
offsets: 1,
charge: Charge {
events: 1,
bytes: 10
}
}
);
}
#[test]
fn the_window_slides_across_take_frontier() {
let mut ledger = PartitionOffsetLedger::new(1);
ledger.charge([charge(0), charge(1)]).unwrap();
ledger.complete([Offset(0), Offset(1)]).unwrap();
let first_take = ledger.take_frontier().unwrap();
assert_eq!(first_take.first, Offset(0));
ledger.charge([charge(2)]).unwrap();
ledger.complete([Offset(2)]).unwrap();
assert_eq!(ledger.frontier(), Some(Offset(3)));
let second_take = ledger.take_frontier().unwrap();
assert_eq!(second_take.charge.events, 1);
assert_eq!(
second_take.first, first_take.offset,
"each take starts where the last one ended"
);
}
}