1use super::ack::AckTx;
13use super::tracker::{PartitionTracker, ResolveOutcome};
14use super::{AckMsg, AckRef, BatchId};
15use crate::error::FatalError;
16use crate::record::PartitionId;
17use std::collections::{HashMap, HashSet};
18use std::sync::Arc;
19use std::sync::atomic::{AtomicU32, Ordering};
20use std::time::Instant;
21
22#[derive(Clone, Copy, Debug)]
24struct Registration {
25 id: BatchId,
26 last_offset: i64,
27}
28
29#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
31pub struct DrainStats {
32 pub applied: usize,
34 pub stale_epoch: usize,
37 pub duplicates: usize,
39 pub unknown: usize,
41}
42
43#[derive(Debug)]
51pub struct AckIssuer {
52 ack_tx: crossbeam_channel::Sender<AckMsg>,
53 reg_tx: crossbeam_channel::Sender<Registration>,
54 shared_epoch: Arc<AtomicU32>,
55 local_epoch: u32,
56 seqs: HashMap<PartitionId, u64>,
57}
58
59impl Clone for AckIssuer {
60 fn clone(&self) -> Self {
61 AckIssuer {
62 ack_tx: self.ack_tx.clone(),
63 reg_tx: self.reg_tx.clone(),
64 shared_epoch: Arc::clone(&self.shared_epoch),
65 local_epoch: self.local_epoch,
66 seqs: HashMap::new(),
67 }
68 }
69}
70
71impl AckIssuer {
72 pub fn issue(&mut self, partition: PartitionId, last_offset: i64) -> AckRef {
78 let epoch = self.shared_epoch.load(Ordering::Acquire);
79 if epoch != self.local_epoch {
80 self.local_epoch = epoch;
82 self.seqs.clear();
83 }
84 let seq_slot = self.seqs.entry(partition).or_insert(0);
85 let seq = *seq_slot;
86 *seq_slot += 1;
87
88 let id = BatchId {
89 partition,
90 epoch,
91 seq,
92 };
93 let _ = self.reg_tx.send(Registration { id, last_offset });
97 AckRef::new(id, last_offset, AckTx::Channel(self.ack_tx.clone()))
98 }
99}
100
101#[derive(Debug)]
120pub struct Checkpointer {
121 ack_tx: crossbeam_channel::Sender<AckMsg>,
122 ack_rx: crossbeam_channel::Receiver<AckMsg>,
123 reg_tx: crossbeam_channel::Sender<Registration>,
124 reg_rx: crossbeam_channel::Receiver<Registration>,
125 shared_epoch: Arc<AtomicU32>,
126 epoch: u32,
127 trackers: HashMap<PartitionId, PartitionTracker>,
128 admitted: HashSet<PartitionId>,
132}
133
134impl Default for Checkpointer {
135 fn default() -> Self {
136 Self::new()
137 }
138}
139
140impl Checkpointer {
141 #[must_use]
146 pub fn new() -> Self {
147 let (ack_tx, ack_rx) = crossbeam_channel::unbounded();
148 let (reg_tx, reg_rx) = crossbeam_channel::unbounded();
149 Checkpointer {
150 ack_tx,
151 ack_rx,
152 reg_tx,
153 reg_rx,
154 shared_epoch: Arc::new(AtomicU32::new(0)),
155 epoch: 0,
156 trackers: HashMap::new(),
157 admitted: HashSet::new(),
158 }
159 }
160
161 #[must_use]
163 pub fn handle(&self) -> AckIssuer {
164 AckIssuer {
165 ack_tx: self.ack_tx.clone(),
166 reg_tx: self.reg_tx.clone(),
167 shared_epoch: Arc::clone(&self.shared_epoch),
168 local_epoch: self.shared_epoch.load(Ordering::Acquire),
169 seqs: HashMap::new(),
170 }
171 }
172
173 pub fn begin_epoch(&mut self, partitions: &[PartitionId], epoch: u32) {
182 assert!(
183 epoch > self.epoch || (self.epoch == 0 && self.trackers.is_empty()),
184 "assignment epochs must be strictly increasing: {} -> {epoch}",
185 self.epoch
186 );
187 self.epoch = epoch;
188 self.trackers = partitions
189 .iter()
190 .map(|&p| (p, PartitionTracker::new()))
191 .collect();
192 self.admitted = partitions.iter().copied().collect();
196 self.shared_epoch.store(epoch, Ordering::Release);
199 }
200
201 pub fn extend_epoch(&mut self, partitions: &[PartitionId]) -> Result<(), FatalError> {
226 for &p in partitions {
229 if self.admitted.contains(&p) {
230 let live = if self.trackers.contains_key(&p) {
231 "is already tracked"
232 } else {
233 "was revoked earlier in this epoch"
234 };
235 return Err(FatalError {
236 component: "checkpoint".into(),
237 reason: format!(
238 "additive assignment reused partition {} which {live}; every \
239 added lane must carry a partition never seen in this epoch \
240 (a returning partition needs a new epoch)",
241 p.0
242 ),
243 });
244 }
245 }
246 for &p in partitions {
247 self.trackers.insert(p, PartitionTracker::new());
248 self.admitted.insert(p);
249 }
250 Ok(())
251 }
252
253 pub fn revoke(&mut self, partitions: &[PartitionId]) {
257 for p in partitions {
258 self.trackers.remove(p);
259 }
260 }
261
262 pub fn drain(&mut self) -> DrainStats {
270 let mut stats = DrainStats::default();
271 self.drain_registrations(&mut stats);
272
273 let mut deferred = Vec::new();
274 while let Ok(msg) = self.ack_rx.try_recv() {
275 self.apply(msg, &mut stats, Some(&mut deferred));
276 }
277
278 if !deferred.is_empty() {
279 self.drain_registrations(&mut stats);
280 for msg in deferred {
281 self.apply(msg, &mut stats, None);
282 }
283 }
284 stats
285 }
286
287 fn drain_registrations(&mut self, stats: &mut DrainStats) {
288 while let Ok(reg) = self.reg_rx.try_recv() {
289 if reg.id.epoch != self.epoch {
290 stats.stale_epoch += 1;
291 continue;
292 }
293 match self.trackers.get_mut(®.id.partition) {
294 Some(tracker) => tracker.register(reg.id.seq, reg.last_offset),
295 None => stats.stale_epoch += 1,
297 }
298 }
299 }
300
301 fn apply(&mut self, msg: AckMsg, stats: &mut DrainStats, defer: Option<&mut Vec<AckMsg>>) {
302 if msg.id.epoch != self.epoch {
303 stats.stale_epoch += 1;
304 return;
305 }
306 let Some(tracker) = self.trackers.get_mut(&msg.id.partition) else {
307 stats.stale_epoch += 1;
308 return;
309 };
310 match tracker.resolve(msg.id.seq, msg.status) {
311 ResolveOutcome::Applied => stats.applied += 1,
312 ResolveOutcome::Duplicate | ResolveOutcome::AlreadyAdvanced => stats.duplicates += 1,
313 ResolveOutcome::Unregistered => match defer {
314 Some(deferred) => deferred.push(msg),
315 None => {
316 debug_assert!(false, "resolution without registration: {:?}", msg.id);
317 stats.unknown += 1;
318 }
319 },
320 }
321 }
322
323 #[must_use]
327 pub fn take_watermarks(&mut self) -> Vec<(PartitionId, i64)> {
328 let mut out: Vec<_> = self
329 .trackers
330 .iter_mut()
331 .filter_map(|(&p, t)| t.advance().map(|w| (p, w)))
332 .collect();
333 out.sort_unstable_by_key(|&(p, _)| p);
334 out
335 }
336
337 #[must_use]
339 pub fn pending(&self, partition: PartitionId) -> usize {
340 self.trackers
341 .get(&partition)
342 .map_or(0, PartitionTracker::pending)
343 }
344
345 #[must_use]
347 pub fn max_pending(&self) -> usize {
348 self.trackers
349 .values()
350 .map(PartitionTracker::pending)
351 .max()
352 .unwrap_or(0)
353 }
354
355 #[must_use]
358 pub fn stalled_partitions(&self) -> Vec<(PartitionId, Instant)> {
359 let mut out: Vec<_> = self
360 .trackers
361 .iter()
362 .filter_map(|(&p, t)| t.stalled_since().map(|since| (p, since)))
363 .collect();
364 out.sort_unstable_by_key(|&(p, _)| p);
365 out
366 }
367}
368
369#[cfg(all(test, not(loom)))]
370mod tests {
371 use super::*;
372
373 const P0: PartitionId = PartitionId(0);
374 const P1: PartitionId = PartitionId(1);
375
376 fn checkpointer(partitions: &[PartitionId]) -> (Checkpointer, AckIssuer) {
377 let mut cp = Checkpointer::new();
378 cp.begin_epoch(partitions, 1);
379 let issuer = cp.handle();
380 (cp, issuer)
381 }
382
383 #[test]
384 fn issue_drain_take_happy_path() {
385 let (mut cp, mut issuer) = checkpointer(&[P0]);
386 drop(issuer.issue(P0, 99));
387 drop(issuer.issue(P0, 199));
388 let stats = cp.drain();
389 assert_eq!(stats.applied, 2);
390 assert_eq!(
391 stats,
392 DrainStats {
393 applied: 2,
394 ..Default::default()
395 }
396 );
397 assert_eq!(cp.take_watermarks(), vec![(P0, 200)]);
398 }
399
400 #[test]
401 fn extend_epoch_adds_partitions_without_disturbing_inflight_acks() {
402 let (mut cp, mut issuer) = checkpointer(&[P0]);
403 let ack = issuer.issue(P0, 99);
405 cp.extend_epoch(&[P1]).unwrap();
406 drop(ack);
408 drop(issuer.issue(P1, 9));
409 let stats = cp.drain();
410 assert_eq!(stats.applied, 2);
411 assert_eq!(stats.stale_epoch, 0);
412 assert_eq!(cp.take_watermarks(), vec![(P0, 100), (P1, 10)]);
413 }
414
415 #[test]
416 fn extend_epoch_rejects_a_live_partition() {
417 let (mut cp, _issuer) = checkpointer(&[P0]);
418 let err = cp.extend_epoch(&[P0]).unwrap_err();
419 assert!(err.reason.contains("already tracked"), "{err}");
420 }
421
422 #[test]
423 fn extend_epoch_rejects_a_partition_revoked_earlier_in_the_epoch() {
424 let (mut cp, mut issuer) = checkpointer(&[P0]);
431 drop(issuer.issue(P0, 9));
432 cp.drain();
433 cp.revoke(&[P0]);
434
435 let err = cp.extend_epoch(&[P0]).unwrap_err();
436 assert_eq!(err.component, "checkpoint");
437 assert!(
438 err.reason.contains("revoked earlier in this epoch"),
439 "{err}"
440 );
441
442 drop(issuer.issue(P0, 19));
446 let stats = cp.drain();
447 assert_eq!(stats.applied, 0);
448 assert_eq!(stats.stale_epoch, 2);
449
450 cp.begin_epoch(&[P0], 2);
452 cp.extend_epoch(&[P1]).unwrap();
453 }
454
455 #[test]
456 fn take_watermarks_is_empty_until_new_progress() {
457 let (mut cp, mut issuer) = checkpointer(&[P0]);
458 drop(issuer.issue(P0, 9));
459 cp.drain();
460 assert_eq!(cp.take_watermarks(), vec![(P0, 10)]);
461 assert_eq!(cp.take_watermarks(), vec![]);
462 drop(issuer.issue(P0, 19));
463 cp.drain();
464 assert_eq!(cp.take_watermarks(), vec![(P0, 20)]);
465 }
466
467 #[test]
468 fn out_of_order_acks_across_partitions() {
469 let (mut cp, mut issuer) = checkpointer(&[P0, P1]);
470 let a0 = issuer.issue(P0, 9);
471 let a1 = issuer.issue(P0, 19);
472 let b0 = issuer.issue(P1, 99);
473 drop(a1);
475 drop(b0);
476 cp.drain();
477 assert_eq!(cp.take_watermarks(), vec![(P1, 100)]);
478 assert_eq!(cp.pending(P0), 2);
479 drop(a0);
480 cp.drain();
481 assert_eq!(cp.take_watermarks(), vec![(P0, 20)]);
482 }
483
484 #[test]
485 fn failed_batch_stalls_partition_and_reports() {
486 let (mut cp, mut issuer) = checkpointer(&[P0]);
487 let bad = issuer.issue(P0, 9);
488 bad.fail();
489 drop(bad);
490 drop(issuer.issue(P0, 19));
491 cp.drain();
492 assert_eq!(cp.take_watermarks(), vec![]);
493 let stalled = cp.stalled_partitions();
494 assert_eq!(stalled.len(), 1);
495 assert_eq!(stalled[0].0, P0);
496 }
497
498 #[test]
499 fn stale_epoch_acks_are_discarded() {
500 let (mut cp, mut issuer) = checkpointer(&[P0]);
501 let old = issuer.issue(P0, 9);
502 cp.begin_epoch(&[P0], 2);
503 drop(old); let stats = cp.drain();
505 assert_eq!(stats.applied, 0);
506 assert_eq!(stats.stale_epoch, 2);
508 assert_eq!(cp.take_watermarks(), vec![]);
509
510 drop(issuer.issue(P0, 49));
512 let stats = cp.drain();
513 assert_eq!(stats.applied, 1);
514 assert_eq!(cp.take_watermarks(), vec![(P0, 50)]);
515 }
516
517 #[test]
518 fn revoke_mid_flight_discards_later_acks() {
519 let (mut cp, mut issuer) = checkpointer(&[P0, P1]);
520 let in_flight = issuer.issue(P1, 9);
521 cp.drain(); cp.revoke(&[P1]);
523 drop(in_flight);
524 let stats = cp.drain();
525 assert_eq!(stats.stale_epoch, 1);
526 assert_eq!(cp.take_watermarks(), vec![]);
527 assert_eq!(cp.pending(P1), 0);
528 }
529
530 #[test]
531 fn registration_and_ack_in_same_drain() {
532 let (mut cp, mut issuer) = checkpointer(&[P0]);
535 drop(issuer.issue(P0, 9));
536 let stats = cp.drain();
537 assert_eq!(stats.applied, 1);
538 assert_eq!(stats.unknown, 0);
539 assert_eq!(cp.take_watermarks(), vec![(P0, 10)]);
540 }
541
542 #[test]
543 fn cross_thread_issue_and_resolve() {
544 let (mut cp, issuer) = checkpointer(&[P0, P1]);
545 let handles: Vec<_> = [P0, P1]
546 .into_iter()
547 .map(|p| {
548 let mut issuer = issuer.clone();
549 std::thread::spawn(move || {
550 for i in 0..100i64 {
551 drop(issuer.issue(p, (i + 1) * 10 - 1));
552 }
553 })
554 })
555 .collect();
556 for h in handles {
557 h.join().unwrap();
558 }
559 let stats = cp.drain();
560 assert_eq!(stats.applied, 200);
561 assert_eq!(stats.unknown, 0);
562 assert_eq!(cp.take_watermarks(), vec![(P0, 1000), (P1, 1000)]);
563 }
564
565 #[test]
566 fn pending_counts_feed_backpressure() {
567 let (mut cp, mut issuer) = checkpointer(&[P0, P1]);
568 let held: Vec<_> = (0..5).map(|i| issuer.issue(P0, i)).collect();
569 drop(issuer.issue(P1, 9));
570 cp.drain();
571 assert_eq!(cp.pending(P0), 5);
572 assert_eq!(cp.max_pending(), 5);
573 drop(held);
574 cp.drain();
575 let _ = cp.take_watermarks();
576 assert_eq!(cp.max_pending(), 0);
577 }
578
579 #[test]
580 #[should_panic(expected = "strictly increasing")]
581 fn epoch_regression_panics() {
582 let mut cp = Checkpointer::new();
583 cp.begin_epoch(&[P0], 5);
584 cp.begin_epoch(&[P0], 5);
585 }
586}
587
588#[cfg(all(test, not(loom)))]
589mod proptests {
590 use super::*;
591 use proptest::prelude::*;
592
593 #[derive(Clone, Debug)]
594 enum Op {
595 Issue { partition: u8, fail: bool },
596 ResolveOldest,
597 Rebalance { partitions: Vec<u8> },
598 DrainAndTake,
599 }
600
601 fn ops() -> impl Strategy<Value = Vec<Op>> {
602 prop::collection::vec(
603 prop_oneof![
604 (0..3u8, any::<bool>()).prop_map(|(partition, fail)| Op::Issue { partition, fail }),
605 Just(Op::ResolveOldest),
606 prop::collection::vec(0..3u8, 1..3)
607 .prop_map(|partitions| Op::Rebalance { partitions }),
608 Just(Op::DrainAndTake),
609 ],
610 0..120,
611 )
612 }
613
614 proptest! {
615 #[test]
619 fn epoch_churn_never_leaks_stale_acks(ops in ops()) {
620 let mut cp = Checkpointer::new();
621 let mut epoch = 1u32;
622 let mut assigned: Vec<PartitionId> = vec![PartitionId(0), PartitionId(1), PartitionId(2)];
623 cp.begin_epoch(&assigned, epoch);
624 let mut issuer = cp.handle();
625 let mut offsets: std::collections::HashMap<PartitionId, i64> =
626 std::collections::HashMap::new();
627 let mut held: std::collections::VecDeque<(AckRef, u32, bool)> =
629 std::collections::VecDeque::new();
630 let mut last_watermark: std::collections::HashMap<PartitionId, i64> =
631 std::collections::HashMap::new();
632
633 for op in ops {
634 match op {
635 Op::Issue { partition, fail } => {
636 let p = PartitionId(u32::from(partition));
637 if !assigned.contains(&p) {
638 continue;
639 }
640 let next = offsets.entry(p).or_insert(0);
641 *next += 10;
642 let ack = issuer.issue(p, *next - 1);
643 if fail {
644 ack.fail();
645 }
646 held.push_back((ack, epoch, fail));
647 }
648 Op::ResolveOldest => {
649 held.pop_front(); }
651 Op::Rebalance { partitions } => {
652 epoch += 1;
653 assigned = partitions
654 .into_iter()
655 .map(|p| PartitionId(u32::from(p)))
656 .collect::<std::collections::BTreeSet<_>>()
657 .into_iter()
658 .collect();
659 cp.begin_epoch(&assigned, epoch);
660 offsets.clear();
663 last_watermark.clear();
664 }
665 Op::DrainAndTake => {
666 cp.drain();
667 for (p, w) in cp.take_watermarks() {
668 prop_assert!(
669 assigned.contains(&p),
670 "watermark for unassigned partition {p:?}"
671 );
672 if let Some(&prev) = last_watermark.get(&p) {
673 prop_assert!(w > prev, "watermark not monotonic for {p:?}");
674 }
675 last_watermark.insert(p, w);
676 }
677 }
678 }
679 }
680
681 let stale_epochs: Vec<u32> =
684 held.iter().map(|&(_, e, _)| e).filter(|&e| e != epoch).collect();
685 held.clear();
686 let stats = cp.drain();
687 prop_assert!(stats.unknown == 0, "driver-bug resolutions: {stats:?}");
688 for (p, w) in cp.take_watermarks() {
689 prop_assert!(assigned.contains(&p));
690 if let Some(&prev) = last_watermark.get(&p) {
691 prop_assert!(w > prev);
692 }
693 }
694 if !stale_epochs.is_empty() {
696 prop_assert!(stats.stale_epoch > 0);
697 }
698 }
699 }
700}