Skip to content

: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.

20.9 KB
Raw Blame
use std::collections::HashMap;
use std::sync::{Arc, Mutex};

use metrics::counter;
use tracing::warn;

use crate::charge::Charge;
use crate::partition_offset_ledger::{Held, LedgerError, PartitionOffsetLedger, TakenFrontier};
use crate::types::Offset;

/// Charges and settlements dropped because their stamp predates the
/// partition's current generation: a reassignment or a violation reset.
const STALE_SLICES: &str = "kafka_consumer_ledger_stale_slices_total";
/// Contract violations in the ledger's accounting; must stay at zero.
const ERRORS: &str = "kafka_consumer_ledger_errors_total";
/// Offsets a frontier commit walked over that Kafka never delivered.
const GAP_OFFSETS: &str = "kafka_consumer_ledger_gap_offsets_total";

/// A partition of a named topic, the key for everything the ledger tracks.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct TopicPartition {
    pub topic: String,
    pub partition: i32,
}

impl TopicPartition {
    pub fn new(topic: impl Into<String>, partition: i32) -> Self {
        Self {
            topic: topic.into(),
            partition,
        }
    }
}

/// Why a charge or settlement did not land on its partition's ledger.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Rejection {
    /// The work's stamp predates the partition's current generation: the
    /// partition was reassigned, or its ledger was reset after a violation.
    /// After a reassignment Kafka redelivers the offsets, so nothing is lost.
    Stale { stamp: u64, generation: u64 },
    /// The work violated the ledger's contract. The partition's window is
    /// unknown after this, so its ledger was reset to a new generation: work
    /// in flight drops as stale, and the next delivery founds a fresh ledger.
    /// `generation` and `held` describe the ledger before that reset.
    Violation {
        error: LedgerError,
        stamp: u64,
        generation: u64,
        held: Held,
    },
}

/// One [`PartitionOffsetLedger`] per partition, each founded under a
/// per-partition generation. Forgetting a partition advances its generation and
/// replaces its ledger in one step, so charges and completions stamped with an
/// earlier generation are dropped instead of corrupting the new assignment.
///
/// Staleness is one rule: work whose stamp is below the partition's current
/// generation is stale. Generations are independent per partition, so one
/// partition's reassignment never affects another's in-flight work.
///
/// The ledger counts its rejections and the gap offsets a take walks over.
#[derive(Default)]
pub struct TopicOffsetLedger {
    partitions: Mutex<HashMap<TopicPartition, PartitionOffsetLedger>>,
}

impl TopicOffsetLedger {
    pub fn new() -> Self {
        Self::default()
    }

    /// The partition's current generation, for stamping work as it is
    /// buffered; 0 for a partition the ledger has never seen.
    pub fn generation(&self, topic_partition: &TopicPartition) -> u64 {
        self.partitions
            .lock()
            .unwrap()
            .get(topic_partition)
            .map(PartitionOffsetLedger::generation)
            .unwrap_or_default()
    }

    /// Record one slice of delivered offsets on the partition's ledger,
    /// founding the ledger when the slice is the partition's first delivery.
    /// Returns what the partition's window holds after the charge, or why
    /// the slice was rejected.
    pub fn charge(
        &self,
        topic_partition: &TopicPartition,
        stamp: u64,
        offset_charges: impl IntoIterator<Item = (Offset, Charge)>,
    ) -> Result<Held, Rejection> {
        let result = {
            let mut partitions = self.partitions.lock().unwrap();
            let ledger = partitions
                .entry(topic_partition.clone())
                .or_insert_with(|| PartitionOffsetLedger::new(0));
            let generation = ledger.generation();
            if stamp < generation {
                Err(Rejection::Stale { stamp, generation })
            } else {
                match ledger.charge(offset_charges) {
                    Ok(_) => Ok(ledger.held()),
                    Err(error) => {
                        let held = ledger.held();
                        *ledger = PartitionOffsetLedger::new(generation + 1);
                        Err(Rejection::Violation {
                            error,
                            stamp,
                            generation,
                            held,
                        })
                    }
                }
            }
        };
        if let Err(rejection) = result {
            count_rejection("charge", rejection);
        }
        result
    }

    /// Settle one batch's offsets, stamped with the generation they were
    /// buffered under: mark them complete on the partition's ledger and
    /// report the next-to-read frontier that results, `None` while the first
    /// offset of the window is still incomplete. The window holds the offsets
    /// until `take_frontier` drains them.
    pub fn settle(
        &self,
        topic_partition: &TopicPartition,
        stamp: u64,
        offsets: impl IntoIterator<Item = Offset>,
    ) -> Result<Option<Offset>, Rejection> {
        let result = {
            let mut partitions = self.partitions.lock().unwrap();
            match partitions.get_mut(topic_partition) {
                // Nothing was ever charged, so the batch cannot have been either.
                None => Err(Rejection::Stale {
                    stamp,
                    generation: 0,
                }),
                Some(ledger) => {
                    let generation = ledger.generation();
                    if stamp < generation {
                        Err(Rejection::Stale { stamp, generation })
                    } else {
                        match ledger.complete(offsets) {
                            Ok(()) => Ok(ledger.frontier()),
                            Err(error) => {
                                let held = ledger.held();
                                *ledger = PartitionOffsetLedger::new(generation + 1);
                                Err(Rejection::Violation {
                                    error,
                                    stamp,
                                    generation,
                                    held,
                                })
                            }
                        }
                    }
                }
            }
        };
        if let Err(rejection) = result {
            count_rejection("settle", rejection);
        }
        result
    }

    /// Drain the completed prefix and return the span it covers: the window
    /// base it started from and the frontier it reached. `None` when the
    /// partition has no ledger or nothing has completed at the front of its
    /// window.
    pub fn take_frontier(&self, topic_partition: &TopicPartition) -> Option<TakenFrontier> {
        let taken = self
            .partitions
            .lock()
            .unwrap()
            .get_mut(topic_partition)?
            .take_frontier()?;
        report_gap_offsets(topic_partition, &taken);
        Some(taken)
    }

    /// What the partition's window still holds; nothing without a ledger.
    pub fn held(&self, topic_partition: &TopicPartition) -> Held {
        self.partitions
            .lock()
            .unwrap()
            .get(topic_partition)
            .map(PartitionOffsetLedger::held)
            .unwrap_or_default()
    }

    /// Start a new generation for each partition, dropping its ledger. Called
    /// when a partition is revoked or assigned: Kafka redelivers it from the
    /// committed offset, which a kept ledger would reject as duplicate
    /// delivery, and work still in flight from the old assignment must not
    /// land on the new one.
    pub fn forget_partitions<'a>(
        &self,
        topic_partitions: impl IntoIterator<Item = (&'a str, i32)>,
    ) {
        let mut partitions = self.partitions.lock().unwrap();
        for (topic, partition) in topic_partitions {
            let key = TopicPartition::new(topic, partition);
            let generation = partitions
                .get(&key)
                .map(PartitionOffsetLedger::generation)
                .unwrap_or_default();
            partitions.insert(key, PartitionOffsetLedger::new(generation + 1));
        }
    }
}

fn report_gap_offsets(topic_partition: &TopicPartition, taken: &TakenFrontier) {
    if taken.gap_offset_count == 0 {
        return;
    }
    let (topic, partition) = labels(topic_partition);
    counter!(GAP_OFFSETS, "topic" => topic, "partition" => partition)
        .increment(taken.gap_offset_count as u64);
    warn!(
        topic = %topic_partition.topic,
        partition = topic_partition.partition,
        window_base = taken.first.0,
        frontier = taken.offset.0,
        gap_offsets = taken.gap_offset_count,
        "Commit frontier walked over offsets Kafka never delivered"
    );
}

/// Count one charge or settlement the ledger rejected. A stale slice is
/// expected around a rebalance; a violation is a bug in the accounting. The
/// rejection is returned to the caller, which alone still holds the slice
/// and so is the place to log it.
fn count_rejection(stage: &'static str, rejection: Rejection) {
    match rejection {
        Rejection::Stale { .. } => {
            counter!(STALE_SLICES, "stage" => stage).increment(1);
        }
        Rejection::Violation { error, .. } => {
            counter!(ERRORS, "stage" => stage, "kind" => error.kind()).increment(1);
        }
    }
}

fn labels(topic_partition: &TopicPartition) -> (Arc<str>, Arc<str>) {
    (
        Arc::from(topic_partition.topic.as_str()),
        Arc::from(topic_partition.partition.to_string()),
    )
}

#[cfg(test)]
mod tests {
    use super::*;

    fn tp(topic: &str, partition: i32) -> TopicPartition {
        TopicPartition::new(topic, partition)
    }

    fn charge(ledger: &TopicOffsetLedger, tp: &TopicPartition, stamp: u64, offsets: &[i64]) {
        ledger
            .charge(
                tp,
                stamp,
                offsets.iter().map(|&offset| (Offset(offset), Charge::ZERO)),
            )
            .unwrap();
    }

    #[test]
    fn a_completed_batch_reports_its_frontier_and_drains() {
        let ledger = TopicOffsetLedger::new();
        let p0 = tp("events", 0);
        charge(&ledger, &p0, 0, &[10]);
        charge(&ledger, &p0, 0, &[11]);

        let frontier = ledger
            .settle(&p0, 0, [Offset(10), Offset(11)])
            .expect("live ledger settles");
        assert_eq!(frontier, Some(Offset(12)));

        assert_eq!(
            ledger.take_frontier(&p0).map(|taken| taken.offset),
            Some(Offset(12))
        );
        assert_eq!(ledger.held(&p0).offsets, 0);
    }

    #[test]
    fn forgetting_a_partition_drops_its_ledger_and_advances_its_generation() {
        let ledger = TopicOffsetLedger::new();
        let p0 = tp("events", 0);
        charge(&ledger, &p0, 0, &[10]);

        ledger.forget_partitions([("events", 0)]);

        assert_eq!(ledger.held(&p0).offsets, 0);
        assert_eq!(ledger.generation(&p0), 1);
    }

    #[test]
    fn forgetting_an_unseen_partition_still_opens_a_generation() {
        let ledger = TopicOffsetLedger::new();
        let p0 = tp("events", 0);
        ledger.forget_partitions([("events", 0)]);

        assert_eq!(ledger.generation(&p0), 1);
        assert_eq!(
            ledger.charge(&p0, 0, [(Offset(10), Charge::ZERO)]),
            Err(Rejection::Stale {
                stamp: 0,
                generation: 1
            })
        );
        assert_eq!(
            ledger
                .charge(&p0, 1, [(Offset(10), Charge::ZERO)])
                .map(|held| held.offsets),
            Ok(1)
        );
    }

    #[test]
    fn an_incomplete_prefix_reports_no_frontier_and_holds_offsets() {
        let ledger = TopicOffsetLedger::new();
        let p0 = tp("events", 0);
        charge(&ledger, &p0, 0, &[10]);
        charge(&ledger, &p0, 0, &[11]);

        let frontier = ledger
            .settle(&p0, 0, [Offset(11)])
            .expect("live ledger settles");
        assert_eq!(frontier, None);
        assert!(ledger.take_frontier(&p0).is_none());
        assert_eq!(ledger.held(&p0).offsets, 2);

        let frontier = ledger
            .settle(&p0, 0, [Offset(10)])
            .expect("live ledger settles");
        assert_eq!(frontier, Some(Offset(12)));
        assert_eq!(
            ledger.take_frontier(&p0).map(|taken| taken.offset),
            Some(Offset(12))
        );
        assert_eq!(ledger.held(&p0).offsets, 0);
    }

    #[test]
    fn a_batch_spanning_partitions_settles_each_independently() {
        let ledger = TopicOffsetLedger::new();
        let p0 = tp("events", 0);
        let p1 = tp("events", 1);
        charge(&ledger, &p0, 0, &[10, 11]);
        charge(&ledger, &p1, 0, &[20, 21]);

        let settled = ledger
            .settle(&p0, 0, [Offset(10), Offset(11)])
            .expect("live ledger settles");
        assert_eq!(settled, Some(Offset(12)));
        let held = ledger
            .settle(&p1, 0, [Offset(21)])
            .expect("live ledger settles");
        assert_eq!(held, None);

        ledger.take_frontier(&p0);
        ledger.take_frontier(&p1);
        assert_eq!(ledger.held(&p0).offsets, 0, "the settled partition drains");
        assert_eq!(
            ledger.held(&p1).offsets,
            2,
            "the held partition keeps its offsets"
        );
    }

    #[test]
    fn completions_for_a_forgotten_partition_are_stale() {
        let ledger = TopicOffsetLedger::new();
        let p0 = tp("events", 0);
        charge(&ledger, &p0, 0, &[10]);
        ledger.forget_partitions([("events", 0)]);

        assert_eq!(
            ledger.settle(&p0, 0, [Offset(10)]),
            Err(Rejection::Stale {
                stamp: 0,
                generation: 1
            })
        );
    }

    #[test]
    fn completions_for_a_never_charged_partition_are_stale() {
        let ledger = TopicOffsetLedger::new();
        assert_eq!(
            ledger.settle(&tp("events", 0), 0, [Offset(10)]),
            Err(Rejection::Stale {
                stamp: 0,
                generation: 0
            })
        );
    }

    #[test]
    fn partitions_are_keyed_by_topic_and_partition() {
        let ledger = TopicOffsetLedger::new();
        let events = tp("events", 0);
        let overflow = tp("overflow", 0);
        charge(&ledger, &events, 0, &[10]);
        charge(&ledger, &overflow, 0, &[10]);

        ledger
            .settle(&events, 0, [Offset(10)])
            .expect("live ledger settles");
        ledger.take_frontier(&events);

        assert_eq!(ledger.held(&events).offsets, 0);
        assert_eq!(ledger.held(&overflow).offsets, 1);
    }

    #[test]
    fn stale_completions_from_a_previous_assignment_are_dropped() {
        let ledger = TopicOffsetLedger::new();
        let p0 = tp("events", 0);
        charge(&ledger, &p0, 0, &[10]);

        // Revoke and reassign while the batch is in flight.
        ledger.forget_partitions([("events", 0)]);
        charge(&ledger, &p0, 1, &[10]);

        assert_eq!(
            ledger.settle(&p0, 0, [Offset(10)]),
            Err(Rejection::Stale {
                stamp: 0,
                generation: 1
            })
        );
        assert_eq!(
            ledger.held(&p0).offsets,
            1,
            "the redelivered offset stays uncompleted"
        );

        ledger
            .settle(&p0, 1, [Offset(10)])
            .expect("current-generation batch settles");
        ledger.take_frontier(&p0);
        assert_eq!(ledger.held(&p0).offsets, 0);
    }

    #[test]
    fn a_reassignment_affects_only_its_own_partition() {
        let ledger = TopicOffsetLedger::new();
        let p0 = tp("events", 0);
        let p1 = tp("events", 1);
        charge(&ledger, &p0, 0, &[10]);
        charge(&ledger, &p1, 0, &[20]);

        ledger.forget_partitions([("events", 0)]);
        charge(&ledger, &p0, 1, &[10]);
        assert_eq!(
            ledger.generation(&p1),
            0,
            "partition 1 keeps its generation"
        );

        assert_eq!(
            ledger.settle(&p0, 0, [Offset(10)]),
            Err(Rejection::Stale {
                stamp: 0,
                generation: 1
            })
        );
        ledger
            .settle(&p1, 0, [Offset(20)])
            .expect("untouched partition settles");
        ledger.take_frontier(&p1);

        assert_eq!(
            ledger.held(&p0).offsets,
            1,
            "the reassigned partition ignores the stale completion"
        );
        assert_eq!(
            ledger.held(&p1).offsets,
            0,
            "the untouched partition completes and drains"
        );
    }

    #[test]
    fn slices_spanning_another_partitions_generation_change_still_charge() {
        let ledger = TopicOffsetLedger::new();
        let p1 = tp("events", 1);
        charge(&ledger, &p1, 0, &[20]);

        ledger.forget_partitions([("events", 0)]);
        charge(&ledger, &p1, 0, &[21]);
        assert_eq!(ledger.held(&p1).offsets, 2);

        ledger
            .settle(&p1, 0, [Offset(20), Offset(21)])
            .expect("surviving ledger settles");
        ledger.take_frontier(&p1);
        assert_eq!(ledger.held(&p1).offsets, 0, "no message is lost");
    }

    #[test]
    fn a_partition_lost_for_a_generation_returns_under_a_later_one() {
        let ledger = TopicOffsetLedger::new();
        let p0 = tp("events", 0);
        charge(&ledger, &p0, 0, &[10]);

        // The revoke and the later assign both forget the partition.
        ledger.forget_partitions([("events", 0)]);
        ledger.forget_partitions([("events", 0)]);
        assert_eq!(ledger.generation(&p0), 2);

        assert_eq!(
            ledger.settle(&p0, 0, [Offset(10)]),
            Err(Rejection::Stale {
                stamp: 0,
                generation: 2
            })
        );
        assert_eq!(ledger.held(&p0).offsets, 0, "no ledger, nothing lands");

        charge(&ledger, &p0, 2, &[10]);
        ledger
            .settle(&p0, 2, [Offset(10)])
            .expect("the new assignment settles");
        ledger.take_frontier(&p0);
        assert_eq!(ledger.held(&p0).offsets, 0);
    }

    #[test]
    fn slices_from_every_older_generation_cannot_refound_a_dropped_ledger() {
        let ledger = TopicOffsetLedger::new();
        let p0 = tp("events", 0);
        charge(&ledger, &p0, 0, &[10]);
        ledger.forget_partitions([("events", 0)]);
        ledger.forget_partitions([("events", 0)]);

        assert_eq!(
            ledger.charge(&p0, 0, [(Offset(10), Charge::ZERO)]),
            Err(Rejection::Stale {
                stamp: 0,
                generation: 2
            })
        );
        assert_eq!(
            ledger.charge(&p0, 1, [(Offset(10), Charge::ZERO)]),
            Err(Rejection::Stale {
                stamp: 1,
                generation: 2
            })
        );
        assert_eq!(ledger.held(&p0).offsets, 0);

        assert_eq!(
            ledger
                .charge(&p0, 2, [(Offset(10), Charge::ZERO)])
                .map(|held| held.offsets),
            Ok(1)
        );
    }

    #[test]
    fn a_violating_charge_resets_the_partition_to_a_new_generation() {
        let ledger = TopicOffsetLedger::new();
        let p0 = tp("events", 0);
        charge(&ledger, &p0, 0, &[10, 11]);

        assert_eq!(
            ledger.charge(&p0, 0, [(Offset(11), Charge::ZERO)]),
            Err(Rejection::Violation {
                error: LedgerError::OffsetNotAboveWindow {
                    offset: Offset(11),
                    next: Offset(12),
                },
                stamp: 0,
                generation: 0,
                held: Held {
                    offsets: 2,
                    charge: Charge::ZERO
                },
            })
        );
        assert_eq!(ledger.held(&p0).offsets, 0, "the window is discarded");
        assert_eq!(ledger.generation(&p0), 1);

        assert_eq!(
            ledger.settle(&p0, 0, [Offset(10)]),
            Err(Rejection::Stale {
                stamp: 0,
                generation: 1
            })
        );
        assert_eq!(
            ledger
                .charge(&p0, 1, [(Offset(12), Charge::ZERO)])
                .map(|held| held.offsets),
            Ok(1)
        );
    }

    #[test]
    fn a_violating_completion_resets_the_partition_to_a_new_generation() {
        let ledger = TopicOffsetLedger::new();
        let p0 = tp("events", 0);
        charge(&ledger, &p0, 0, &[10]);

        assert_eq!(
            ledger.settle(&p0, 0, [Offset(15)]),
            Err(Rejection::Violation {
                error: LedgerError::CompletionUncharged { offset: Offset(15) },
                stamp: 0,
                generation: 0,
                held: Held {
                    offsets: 1,
                    charge: Charge::ZERO
                },
            })
        );
        assert_eq!(ledger.held(&p0).offsets, 0);
        assert_eq!(ledger.generation(&p0), 1);
        assert!(ledger.take_frontier(&p0).is_none());
    }
}