use bytes::Bytes;
use dashmap::DashMap;
use std::collections::VecDeque;
use std::mem::size_of;
use std::sync::atomic::{AtomicU32, AtomicU64, AtomicUsize, Ordering};
use std::time::{Duration, Instant, SystemTime, UNIX_EPOCH};
static EPOCH_COUNTER: AtomicU32 = AtomicU32::new(0);
pub(crate) enum RecoveryResult {
Recovered {
publications: Vec<Bytes>,
epoch: u32,
offset: u64,
},
NotRecovered { epoch: u32, offset: u64 },
NoHistory,
}
pub(crate) struct RecoveryConfig {
pub(crate) buffer_size_bits: u32,
pub(crate) history_ttl_secs: u64,
pub(crate) max_recovery_messages: usize,
pub(crate) global_memory_budget: usize,
}
impl Default for RecoveryConfig {
fn default() -> Self {
Self {
buffer_size_bits: 7, history_ttl_secs: 300, max_recovery_messages: 500,
global_memory_budget: 256 * 1024 * 1024, }
}
}
pub(crate) const CLEANUP_INTERVAL: Duration = Duration::from_secs(30);
pub(crate) const MARK_INTERVAL: Duration = Duration::from_secs(1);
const MAX_MARKS: usize = 86_400;
const LATELY_MARGIN: Duration = Duration::from_secs(3);
const MAX_UNKEPT_TOPICS: usize = 100_000;
pub(crate) const MAX_BUFFER_SIZE_BITS: u32 = 16;
const BUFFER_OVERHEAD: usize = 128;
struct RecoveryEntry {
data: Bytes,
offset: u64,
seq: u64,
}
type Arrived = (u64, Bytes);
fn interleave(streams: Vec<Vec<Arrived>>) -> Vec<Bytes> {
let mut out = Vec::with_capacity(streams.iter().map(Vec::len).sum());
let mut streams: Vec<_> = streams
.into_iter()
.map(|stream| stream.into_iter().peekable())
.collect();
while let Some((_, i)) = streams
.iter_mut()
.enumerate()
.filter_map(|(i, stream)| stream.peek().map(|(seq, _)| (*seq, i)))
.min()
{
if let Some((_, data)) = streams[i].next() {
out.push(data);
}
}
out
}
fn foreign_topic(key: &str) -> &str {
key.split_once('\0').map_or(key, |(topic, _)| topic)
}
struct TopicRecoveryBuffer {
entries: VecDeque<(Bytes, u64)>,
capacity: usize,
evicted_through: u64,
head_offset: u64,
epoch: u32,
total_bytes: usize,
key_len: usize,
last_write: Instant,
}
impl TopicRecoveryBuffer {
fn new(capacity_bits: u32, key_len: usize) -> Self {
let epoch = (SystemTime::now()
.duration_since(UNIX_EPOCH)
.unwrap_or_default()
.as_nanos() as u32)
.wrapping_add(std::process::id())
.wrapping_add(EPOCH_COUNTER.fetch_add(1, Ordering::Relaxed));
Self {
entries: VecDeque::new(),
capacity: 1usize << capacity_bits.min(MAX_BUFFER_SIZE_BITS),
evicted_through: 0,
head_offset: 0,
epoch,
total_bytes: 0,
key_len,
last_write: Instant::now(),
}
}
fn tail_offset(&self) -> u64 {
self.head_offset - self.entries.len() as u64
}
fn footprint(&self) -> usize {
self.total_bytes
+ self.entries.capacity() * size_of::<(Bytes, u64)>()
+ self.key_len
+ BUFFER_OVERHEAD
}
fn push(&mut self, data: Bytes, seq: u64) -> u64 {
if self.entries.len() >= self.capacity
&& let Some((old, old_seq)) = self.entries.pop_front()
{
self.total_bytes -= old.len();
self.evicted_through = self.evicted_through.max(old_seq);
}
let offset = self.head_offset;
self.total_bytes += data.len();
self.entries.push_back((data, seq));
self.head_offset += 1;
self.last_write = Instant::now();
offset
}
fn recover_since(&self, after_offset: u64, max_messages: usize) -> Option<Vec<Arrived>> {
let start = match after_offset.checked_add(1) {
Some(s) => s,
None => return Some(Vec::new()), };
let tail = self.tail_offset();
if self.head_offset > 0 && start < tail {
return None;
}
if start >= self.head_offset {
return Some(Vec::new());
}
let count = ((self.head_offset - start) as usize).min(max_messages);
let first = (start - tail) as usize;
Some(
self.entries
.iter()
.skip(first)
.take(count)
.map(|(data, seq)| (*seq, data.clone()))
.collect(),
)
}
fn seq_at(&self, offset: u64) -> Option<u64> {
let tail = self.tail_offset();
(offset >= tail && offset < self.head_offset)
.then(|| self.entries[(offset - tail) as usize].1)
}
fn anchor_seq(&self, offset: u64) -> Option<u64> {
self.seq_at(offset)
.or_else(|| {
(offset.checked_add(1) == Some(self.tail_offset()) && self.evicted_through > 0)
.then_some(self.evicted_through)
})
.or_else(|| {
(offset.saturating_add(1) >= self.head_offset)
.then(|| self.entries.back().map(|(_, seq)| *seq))
.flatten()
})
}
fn whole_after(&self, seq: u64) -> Option<Vec<Arrived>> {
(self.evicted_through == 0 && self.entries.iter().all(|(_, s)| *s > seq)).then(|| {
self.entries
.iter()
.map(|(data, s)| (*s, data.clone()))
.collect()
})
}
fn last_seq(&self) -> u64 {
self.entries
.back()
.map_or(self.evicted_through, |(_, seq)| *seq)
}
fn held_from(&self, from: u64) -> impl Iterator<Item = (u64, u64, &Bytes)> {
let tail = self.tail_offset();
let from = from.max(tail);
self.entries
.iter()
.skip(usize::try_from(from - tail).unwrap_or(usize::MAX))
.zip(from..)
.map(|((data, seq), offset)| (offset, *seq, data))
}
fn arrived_after(&self, seq: u64) -> Option<Vec<Arrived>> {
if self.evicted_through > seq {
return None;
}
Some(
self.entries
.iter()
.filter(|(_, s)| *s > seq)
.map(|(data, s)| (*s, data.clone()))
.collect(),
)
}
}
#[derive(Clone, Copy)]
struct Removed {
through: u64,
at: Instant,
shared_through: u64,
}
impl Removed {
fn note(&mut self, seq: u64, shared: bool) {
self.through = self.through.max(seq);
self.at = Instant::now();
if shared {
self.shared_through = self.shared_through.max(seq);
}
}
fn none() -> Self {
Self {
through: 0,
at: Instant::now(),
shared_through: 0,
}
}
}
struct Delivered {
epoch: u32,
through: u64,
above: u64,
at: Instant,
}
impl Delivered {
fn first(epoch: u32, offset: u64) -> Self {
Self {
epoch,
through: offset,
above: 0,
at: Instant::now(),
}
}
fn of(buf: &ForeignRecoveryBuffer) -> Option<Self> {
if !buf.initialized {
return None;
}
let through = buf
.contiguous_through()
.or_else(|| buf.head_offset.checked_sub(1))?;
let above = buf
.entries
.iter()
.flatten()
.filter(|entry| entry.offset > through && entry.offset - through <= 64)
.fold(0u64, |above, entry| {
above | 1 << (entry.offset - through - 1)
});
Some(Self {
epoch: buf.epoch,
through,
above,
at: buf.last_write,
})
}
fn deliver(&mut self, offset: u64) -> bool {
self.at = Instant::now();
if offset <= self.through {
return false;
}
let mut ahead = offset - self.through - 1;
if ahead >= 64 {
let shift = ahead - 63;
self.above = self.above.checked_shr(shift.min(64) as u32).unwrap_or(0);
self.through += shift;
ahead = 63;
}
let bit = 1u64 << ahead;
if self.above & bit != 0 {
return false;
}
self.above |= bit;
let run = self.above.trailing_ones();
self.through += u64::from(run);
self.above = self.above.checked_shr(run).unwrap_or(0);
true
}
fn has(&self, offset: u64) -> bool {
offset <= self.through || {
let ahead = offset - self.through - 1;
ahead < 64 && self.above & (1 << ahead) != 0
}
}
fn any_after(&self, offset: u64) -> bool {
if offset < self.through {
return true;
}
let ahead = offset - self.through;
ahead < 64 && self.above.checked_shr(ahead as u32).unwrap_or(0) != 0
}
}
struct ForeignRecoveryBuffer {
entries: Box<[Option<RecoveryEntry>]>,
mask: u64,
head_offset: u64,
tail_offset: u64,
epoch: u32,
total_bytes: usize,
key_len: usize,
last_write: Instant,
initialized: bool,
evicted_through: u64,
}
impl ForeignRecoveryBuffer {
fn new(capacity_bits: u32, epoch: u32, key_len: usize) -> Self {
let capacity = 1u64 << capacity_bits.min(MAX_BUFFER_SIZE_BITS);
let mut entries = Vec::with_capacity(capacity as usize);
entries.resize_with(capacity as usize, || None);
Self {
entries: entries.into_boxed_slice(),
mask: capacity - 1,
head_offset: 0,
tail_offset: 0,
epoch,
total_bytes: 0,
key_len,
last_write: Instant::now(),
initialized: false,
evicted_through: 0,
}
}
fn footprint(&self) -> usize {
self.total_bytes
+ self.entries.len() * size_of::<Option<RecoveryEntry>>()
+ self.key_len
+ BUFFER_OVERHEAD
}
fn push_at(&mut self, data: Bytes, origin_offset: u64, seq: u64) -> bool {
let capacity = self.mask + 1;
if !self.initialized {
self.tail_offset = origin_offset;
self.head_offset = origin_offset;
self.initialized = true;
}
if origin_offset < self.tail_offset || self.seq_at(origin_offset).is_some() {
return false;
}
if origin_offset >= self.head_offset {
let new_tail = origin_offset.saturating_sub(capacity - 1);
if new_tail.saturating_sub(self.tail_offset) >= capacity {
for slot in self.entries.iter_mut() {
if let Some(old) = slot.take() {
self.total_bytes -= old.data.len();
self.evicted_through = self.evicted_through.max(old.seq);
}
}
self.tail_offset = new_tail;
} else {
while self.tail_offset < new_tail {
let evict_idx = (self.tail_offset & self.mask) as usize;
if let Some(old) = self.entries[evict_idx].take() {
self.total_bytes -= old.data.len();
self.evicted_through = self.evicted_through.max(old.seq);
}
self.tail_offset += 1;
}
}
self.head_offset = origin_offset.saturating_add(1);
}
let idx = (origin_offset & self.mask) as usize;
let data_len = data.len();
if let Some(old) = self.entries[idx].take() {
self.total_bytes -= old.data.len();
self.evicted_through = self.evicted_through.max(old.seq);
}
self.entries[idx] = Some(RecoveryEntry {
data,
offset: origin_offset,
seq,
});
self.total_bytes += data_len;
self.last_write = Instant::now();
true
}
fn contiguous_through(&self) -> Option<u64> {
if !self.initialized || self.head_offset <= self.tail_offset {
return None;
}
let mut offset = self.tail_offset;
while offset < self.head_offset && self.seq_at(offset).is_some() {
offset += 1;
}
offset.checked_sub(1)
}
fn recover_since(&self, after_offset: u64, max_messages: usize) -> Option<Vec<Arrived>> {
let start = match after_offset.checked_add(1) {
Some(s) => s,
None => return Some(Vec::new()),
};
if self.head_offset > self.tail_offset && start < self.tail_offset {
return None;
}
if start >= self.head_offset {
return Some(Vec::new());
}
let count = ((self.head_offset - start) as usize).min(max_messages);
let mut result = Vec::with_capacity(count);
for i in 0..count {
let offset = start + i as u64;
let idx = (offset & self.mask) as usize;
if let Some(entry) = &self.entries[idx] {
if entry.offset == offset {
result.push((entry.seq, entry.data.clone()));
} else {
return None;
}
} else {
return None;
}
}
Some(result)
}
fn seq_at(&self, offset: u64) -> Option<u64> {
self.entries[(offset & self.mask) as usize]
.as_ref()
.filter(|entry| entry.offset == offset)
.map(|entry| entry.seq)
}
fn anchor_seq(&self, offset: u64) -> Option<u64> {
if let Some(seq) = self.seq_at(offset) {
return Some(seq);
}
let next = offset.saturating_add(1);
if next == self.tail_offset && self.evicted_through > 0 {
return Some(self.evicted_through);
}
if next >= self.head_offset {
return self.entries.iter().flatten().map(|entry| entry.seq).max();
}
self.entries
.iter()
.flatten()
.filter(|entry| entry.offset > offset)
.min_by_key(|entry| entry.offset)
.map(|entry| entry.seq.saturating_sub(1))
}
fn whole_after(&self, seq: u64) -> Option<Vec<Arrived>> {
if !self.initialized || self.tail_offset != 0 || self.evicted_through != 0 {
return None;
}
if self.head_offset > 0 && self.contiguous_through() != Some(self.head_offset - 1) {
return None;
}
let mut held: Vec<&RecoveryEntry> = self.entries.iter().flatten().collect();
if held.iter().any(|entry| entry.seq <= seq) {
return None;
}
held.sort_unstable_by_key(|entry| entry.offset);
Some(
held.into_iter()
.map(|entry| (entry.seq, entry.data.clone()))
.collect(),
)
}
fn last_seq(&self) -> u64 {
self.entries
.iter()
.flatten()
.map(|entry| entry.seq)
.max()
.unwrap_or(0)
.max(self.evicted_through)
}
fn arrived_after(&self, seq: u64) -> Option<Vec<Arrived>> {
if self.evicted_through > seq {
return None;
}
let mut after: Vec<&RecoveryEntry> = self
.entries
.iter()
.flatten()
.filter(|entry| entry.seq > seq)
.collect();
after.sort_unstable_by_key(|entry| entry.offset);
if let Some(first) = after.first() {
let before = first.offset.checked_sub(1);
let held = before
.is_none_or(|before| before < self.tail_offset || self.seq_at(before).is_some());
let contiguous = after.windows(2).all(|w| w[1].offset == w[0].offset + 1);
if !held || !contiguous {
return None;
}
}
Some(
after
.into_iter()
.map(|entry| (entry.seq, entry.data.clone()))
.collect(),
)
}
}
pub(crate) struct RecoveryManager {
buffers: DashMap<String, TopicRecoveryBuffer>,
local_buffers: DashMap<String, TopicRecoveryBuffer>,
foreign_buffers: DashMap<String, ForeignRecoveryBuffer>,
foreign_epochs: DashMap<String, Vec<u32>>,
arrival: AtomicU64,
interest_since: DashMap<String, (u64, Instant)>,
marks: parking_lot::Mutex<VecDeque<(Instant, u64)>>,
removed_through: DashMap<String, Removed>,
removed_any: parking_lot::Mutex<Option<Removed>>,
forgotten: AtomicU64,
relayed_unkept: DashMap<String, Delivered>,
config: RecoveryConfig,
total_bytes: AtomicUsize,
}
impl RecoveryManager {
pub(crate) fn new(config: RecoveryConfig) -> Self {
Self {
buffers: DashMap::new(),
local_buffers: DashMap::new(),
foreign_buffers: DashMap::new(),
foreign_epochs: DashMap::new(),
arrival: AtomicU64::new(1),
interest_since: DashMap::new(),
marks: parking_lot::Mutex::new(VecDeque::new()),
removed_through: DashMap::new(),
removed_any: parking_lot::Mutex::new(None),
forgotten: AtomicU64::new(0),
relayed_unkept: DashMap::new(),
config,
total_bytes: AtomicUsize::new(0),
}
}
#[cfg(test)]
pub(crate) fn push_stamped<F>(&self, topic: &str, build: F) -> Option<Bytes>
where
F: FnOnce(u32, u64) -> Bytes,
{
self.stamp(topic, false, build).0
}
#[cfg(test)]
pub(crate) fn push_stamped_local<F>(&self, topic: &str, build: F) -> Option<Bytes>
where
F: FnOnce(u32, u64) -> Bytes,
{
self.stamp(topic, true, build).0
}
pub(crate) fn stamp<F>(&self, topic: &str, local_only: bool, build: F) -> (Option<Bytes>, u64)
where
F: FnOnce(u32, u64) -> Bytes,
{
let buffers = if local_only {
&self.local_buffers
} else {
&self.buffers
};
let mut created = false;
let mut entry = match buffers.get_mut(topic) {
Some(entry) => entry,
None if self.total_bytes.load(Ordering::Relaxed)
>= self.config.global_memory_budget =>
{
let seq = self.arrival.fetch_add(1, Ordering::Relaxed);
self.note_removed(topic, seq, !local_only);
return (None, seq);
}
None => buffers.entry(topic.to_owned()).or_insert_with(|| {
created = true;
TopicRecoveryBuffer::new(self.config.buffer_size_bits, topic.len())
}),
};
let buf = entry.value_mut();
let epoch = buf.epoch;
let offset = buf.head_offset; let data = build(epoch, offset);
let old_bytes = if created { 0 } else { buf.footprint() };
let seq = self.arrival.fetch_add(1, Ordering::Relaxed);
buf.push(data.clone(), seq);
let new_bytes = buf.footprint();
if new_bytes > old_bytes {
self.total_bytes
.fetch_add(new_bytes - old_bytes, Ordering::AcqRel);
} else if old_bytes > new_bytes {
let _ = self
.total_bytes
.try_update(Ordering::AcqRel, Ordering::Acquire, |cur| {
Some(cur.saturating_sub(old_bytes - new_bytes))
});
}
(Some(data), seq)
}
#[cfg(test)]
pub(crate) fn push(&self, topic: &str, data: Bytes) {
self.push_stamped(topic, move |_epoch, _offset| data);
}
pub(crate) fn push_foreign(
&self,
topic: &str,
data: Bytes,
origin_epoch: u32,
origin_offset: u64,
) -> bool {
thread_local! {
static KEY: std::cell::RefCell<String> = const { std::cell::RefCell::new(String::new()) };
}
KEY.with_borrow_mut(|key| {
use std::fmt::Write;
key.clear();
let _ = write!(key, "{topic}\0{origin_epoch}");
self.push_foreign_at(key, data, origin_epoch, origin_offset)
})
}
fn push_foreign_at(
&self,
key: &str,
data: Bytes,
origin_epoch: u32,
origin_offset: u64,
) -> bool {
let mut created = false;
let mut entry = match self.foreign_buffers.get_mut(key) {
Some(entry) => entry,
None if self.total_bytes.load(Ordering::Relaxed)
>= self.config.global_memory_budget =>
{
if !self.deliver_unkept(key, origin_epoch, origin_offset) {
return false;
}
let seq = self.arrival.fetch_add(1, Ordering::Relaxed);
self.note_removed(foreign_topic(key), seq, false);
return true;
}
None if let Some(mut delivered) = self.relayed_unkept.get_mut(key)
&& (delivered.has(origin_offset) || delivered.any_after(origin_offset)) =>
{
if !delivered.deliver(origin_offset) {
return false;
}
drop(delivered);
let seq = self.arrival.fetch_add(1, Ordering::Relaxed);
self.note_removed(foreign_topic(key), seq, false);
return true;
}
None => self
.foreign_buffers
.entry(key.to_owned())
.or_insert_with(|| {
created = true;
ForeignRecoveryBuffer::new(
self.config.buffer_size_bits,
origin_epoch,
key.len(),
)
}),
};
if created {
self.relayed_unkept.remove(key);
}
if created && let Some((topic, _)) = key.split_once('\0') {
let mut epochs = self.foreign_epochs.entry(topic.to_owned()).or_default();
if !epochs.contains(&origin_epoch) {
epochs.push(origin_epoch);
}
}
let buf = entry.value_mut();
let old_bytes = if created { 0 } else { buf.footprint() };
let new = buf.push_at(
data,
origin_offset,
self.arrival.fetch_add(1, Ordering::Relaxed),
);
let new_bytes = buf.footprint();
if new_bytes > old_bytes {
self.total_bytes
.fetch_add(new_bytes - old_bytes, Ordering::AcqRel);
} else if old_bytes > new_bytes {
let _ = self
.total_bytes
.try_update(Ordering::AcqRel, Ordering::Acquire, |cur| {
Some(cur.saturating_sub(old_bytes - new_bytes))
});
}
new
}
pub(crate) fn foreign_positions(&self) -> Vec<(String, u32, u64)> {
let held = self.foreign_buffers.iter().filter_map(|entry| {
let (topic, _) = entry.key().split_once('\0')?;
let through = entry.value().contiguous_through()?;
Some((topic.to_owned(), entry.value().epoch, through))
});
let unkept = self.relayed_unkept.iter().filter_map(|entry| {
let (topic, _) = entry.key().split_once('\0')?;
Some((topic.to_owned(), entry.value().epoch, entry.value().through))
});
held.chain(unkept).collect()
}
fn deliver_unkept(&self, key: &str, epoch: u32, offset: u64) -> bool {
if let Some(mut delivered) = self.relayed_unkept.get_mut(key) {
return delivered.deliver(offset);
}
if self.relayed_unkept.len() >= MAX_UNKEPT_TOPICS {
return true;
}
match self.relayed_unkept.entry(key.to_owned()) {
dashmap::Entry::Occupied(mut delivered) => delivered.get_mut().deliver(offset),
dashmap::Entry::Vacant(slot) => {
slot.insert(Delivered::first(epoch, offset));
true
}
}
}
pub(crate) fn published_after(&self, topic: &str, epoch: u32, after: u64) -> Vec<(u64, Bytes)> {
let Some(buf) = self.buffers.get(topic) else {
return Vec::new();
};
if buf.epoch != epoch {
return Vec::new();
}
buf.held_from(after.saturating_add(1))
.map(|(offset, _, data)| (offset, data.clone()))
.collect()
}
fn own_stream(
&self,
topic: &str,
epoch: u32,
) -> Option<dashmap::mapref::one::Ref<'_, String, TopicRecoveryBuffer>> {
self.buffers
.get(topic)
.filter(|buf| buf.epoch == epoch)
.or_else(|| {
self.local_buffers
.get(topic)
.filter(|buf| buf.epoch == epoch)
})
}
fn each_own<R>(
&self,
topic: &str,
mut each: impl FnMut(&TopicRecoveryBuffer) -> Option<R>,
) -> Option<R> {
for own in [&self.buffers, &self.local_buffers] {
if let Some(buf) = own.get(topic)
&& let Some(found) = each(&buf)
{
return Some(found);
}
}
None
}
pub(crate) fn recover(&self, topic: &str, epoch: u32, after_offset: u64) -> RecoveryResult {
let max = self.config.max_recovery_messages;
let anchored = if let Some(buf) = self.own_stream(topic, epoch) {
let missed = buf
.head_offset
.saturating_sub(after_offset.saturating_add(1)) as usize;
Some((
if missed <= max {
buf.recover_since(after_offset, max)
} else {
None
},
buf.anchor_seq(after_offset),
buf.head_offset,
))
} else if let Some(fbuf) = self.foreign_buffers.get(&format!("{topic}\0{epoch}"))
&& fbuf.epoch == epoch
{
let missed = fbuf
.head_offset
.saturating_sub(after_offset.saturating_add(1)) as usize;
Some((
if missed <= max {
fbuf.recover_since(after_offset, max)
} else {
None
},
fbuf.anchor_seq(after_offset),
fbuf.head_offset,
))
} else {
None
};
let Some((own, anchor_seq, head)) = anchored else {
return match self.each_own(topic, |buf| Some((buf.epoch, buf.head_offset))) {
Some((epoch, offset)) => RecoveryResult::NotRecovered { epoch, offset },
None => RecoveryResult::NoHistory,
};
};
let not_recovered = RecoveryResult::NotRecovered {
epoch,
offset: head,
};
if let Some(removed) = self.removed_after(topic)
&& anchor_seq.is_none_or(|seq| removed > seq)
{
return not_recovered;
}
let Some(mut publications) = own else {
return not_recovered;
};
let relayed_whole = |seq: Option<u64>| {
let since = self
.interest_since
.get(topic)
.map_or(u64::MAX, |since| since.0);
seq.is_some_and(|seq| seq >= since)
};
let anchored_relayed = self.own_stream(topic, epoch).is_none();
let relays = self
.foreign_epochs
.get(topic)
.is_some_and(|epochs| !epochs.is_empty());
if (anchored_relayed || relays) && !relayed_whole(anchor_seq) {
return not_recovered;
}
let mut streams: Vec<Option<Vec<Arrived>>> = Vec::new();
self.each_own(topic, |buf| {
if buf.epoch != epoch {
streams.push(match anchor_seq {
Some(seq) => buf.arrived_after(seq),
None => buf.entries.is_empty().then(Vec::new),
});
}
None::<()>
});
let others: Vec<u32> = self
.foreign_epochs
.get(topic)
.map(|epochs| epochs.iter().copied().filter(|e| *e != epoch).collect())
.unwrap_or_default();
for other in others {
if let Some(fbuf) = self.foreign_buffers.get(&format!("{topic}\0{other}")) {
streams.push(match anchor_seq {
Some(seq) => fbuf.arrived_after(seq),
None => fbuf.arrived_after(u64::MAX),
});
}
}
let mut merged = false;
for stream in streams {
let Some(mut more) = stream else {
return not_recovered;
};
merged |= !more.is_empty();
publications.append(&mut more);
}
if publications.len() > max {
return not_recovered;
}
if merged {
publications.sort_unstable_by_key(|(seq, _)| *seq);
}
RecoveryResult::Recovered {
publications: publications.into_iter().map(|(_, data)| data).collect(),
epoch,
offset: head.saturating_sub(1),
}
}
pub(crate) fn recover_streams(
&self,
topic: &str,
anchor: (u32, u64),
named: &[(u32, u64)],
) -> RecoveryResult {
let max = self.config.max_recovery_messages;
let not_recovered = RecoveryResult::NotRecovered {
epoch: anchor.0,
offset: anchor.1,
};
let position = |epoch: u32| named.iter().find(|(e, _)| *e == epoch).map(|(_, o)| *o);
let since = self.interest_since.get(topic).map(|since| since.0);
let foreign_epochs: Vec<u32> = self
.foreign_epochs
.get(topic)
.map(|epochs| epochs.clone())
.unwrap_or_default();
let local_anchor = self
.own_stream(topic, anchor.0)
.map(|buf| buf.seq_at(anchor.1));
let anchor_seq = match local_anchor {
Some(seq) => seq,
None => self
.foreign_buffers
.get(&format!("{topic}\0{}", anchor.0))
.and_then(|fbuf| fbuf.seq_at(anchor.1)),
};
if let Some(removed) = self.removed_after(topic)
&& anchor_seq.is_none_or(|seq| removed > seq)
{
return not_recovered;
}
let mut streams: Vec<Vec<Arrived>> = Vec::with_capacity(foreign_epochs.len() + 1);
let mut missed = 0usize;
let mut head = anchor.1.saturating_add(1);
let mut seen: Vec<u32> = Vec::with_capacity(foreign_epochs.len() + 1);
let failed = self.each_own(topic, |buf| {
seen.push(buf.epoch);
if buf.epoch == anchor.0 {
head = head.max(buf.head_offset);
}
let more = match position(buf.epoch) {
Some(offset) => {
missed += buf.head_offset.saturating_sub(offset.saturating_add(1)) as usize;
if missed > max {
return Some(());
}
buf.recover_since(offset, max)
}
None => anchor_seq.and_then(|seq| buf.whole_after(seq)),
};
let Some(more) = more else {
return Some(());
};
streams.push(more);
None
});
if failed.is_some() {
return not_recovered;
}
for epoch in foreign_epochs {
let Some(fbuf) = self.foreign_buffers.get(&format!("{topic}\0{epoch}")) else {
continue;
};
seen.push(epoch);
if epoch == anchor.0 {
head = head.max(fbuf.head_offset);
}
let more = match position(epoch) {
Some(offset) => {
let first = offset.saturating_add(1);
let from = if first >= fbuf.head_offset {
fbuf.seq_at(fbuf.head_offset.saturating_sub(1))
} else {
fbuf.seq_at(first)
};
let covered = from.is_some_and(|seq| since.is_some_and(|since| seq >= since));
missed += fbuf.head_offset.saturating_sub(first) as usize;
if !covered || missed > max {
return not_recovered;
}
fbuf.recover_since(offset, max)
}
None => anchor_seq
.filter(|_| {
fbuf.entries
.iter()
.flatten()
.map(|entry| entry.seq)
.min()
.is_none_or(|first| since.is_some_and(|since| first >= since))
})
.and_then(|seq| fbuf.whole_after(seq)),
};
let Some(more) = more else {
return not_recovered;
};
streams.push(more);
}
if named.iter().any(|(epoch, _)| !seen.contains(epoch)) {
return not_recovered;
}
if streams.iter().map(Vec::len).sum::<usize>() > max {
return not_recovered;
}
RecoveryResult::Recovered {
publications: interleave(streams),
epoch: anchor.0,
offset: head.saturating_sub(1),
}
}
pub(crate) fn published_since(&self, topic: &str, before: &[(u32, u64)]) -> Option<Vec<Bytes>> {
let max = self.config.max_recovery_messages;
let last = |epoch: u32| before.iter().find(|(e, _)| *e == epoch).map(|(_, o)| *o);
let mut streams: Vec<Vec<Arrived>> = Vec::new();
let mut total = 0u64;
let gone = self.each_own(topic, |buf| {
let more = match last(buf.epoch) {
Some(offset) => {
total += buf.head_offset.saturating_sub(offset.saturating_add(1));
buf.recover_since(offset, max)
}
None => {
total += buf.head_offset;
buf.whole_after(0)
}
};
match more {
Some(more) => {
streams.push(more);
None
}
None => Some(()),
}
});
if gone.is_some() {
return None;
}
let foreign_epochs: Vec<u32> = self
.foreign_epochs
.get(topic)
.map(|epochs| epochs.clone())
.unwrap_or_default();
for epoch in foreign_epochs {
let Some(fbuf) = self.foreign_buffers.get(&format!("{topic}\0{epoch}")) else {
continue;
};
let more = match last(epoch) {
Some(offset) => {
total += fbuf.head_offset.saturating_sub(offset.saturating_add(1));
fbuf.recover_since(offset, max)?
}
None => {
total += fbuf.head_offset;
fbuf.whole_after(0)?
}
};
streams.push(more);
}
let held = streams.iter().map(Vec::len).sum::<usize>();
if total > max as u64 || held as u64 != total {
return None;
}
Some(interleave(streams))
}
pub(crate) fn streams(&self, topic: &str) -> Vec<(u32, u64)> {
let mut streams = Vec::new();
self.each_own(topic, |buf| {
if buf.head_offset > 0 {
streams.push((buf.epoch, buf.head_offset - 1));
}
None::<()>
});
let foreign_epochs: Vec<u32> = self
.foreign_epochs
.get(topic)
.map(|epochs| epochs.clone())
.unwrap_or_default();
for epoch in foreign_epochs {
if let Some(fbuf) = self.foreign_buffers.get(&format!("{topic}\0{epoch}"))
&& fbuf.initialized
&& fbuf.head_offset > 0
{
streams.push((epoch, fbuf.head_offset - 1));
}
}
streams
}
pub(crate) fn get_position(&self, topic: &str) -> Option<(u32, u64)> {
self.each_own(topic, |buf| Some((buf.epoch, buf.head_offset)))
}
pub(crate) fn cleanup(&self) {
let ttl = Duration::from_secs(self.config.history_ttl_secs);
for (own, shared) in [(&self.buffers, true), (&self.local_buffers, false)] {
let expired: Vec<String> = own
.iter()
.filter(|entry| entry.value().last_write.elapsed() > ttl)
.map(|entry| entry.key().clone())
.collect();
for key in &expired {
if let Some((_, removed)) = own.remove(key) {
self.removed_own(key, &removed, shared);
}
}
}
let mut foreign_to_remove = Vec::new();
for entry in self.foreign_buffers.iter() {
if entry.value().last_write.elapsed() > ttl {
foreign_to_remove.push(entry.key().clone());
}
}
for key in &foreign_to_remove {
if let Some(removed) = self.remove_foreign(key) {
self.note_removed(foreign_topic(key), removed.last_seq(), false);
let _ = self
.total_bytes
.try_update(Ordering::Relaxed, Ordering::Relaxed, |cur| {
Some(cur.saturating_sub(removed.footprint()))
});
}
}
if self.total_bytes.load(Ordering::Relaxed) > self.config.global_memory_budget {
#[derive(Clone, Copy)]
enum Held {
Shared,
Local,
Foreign,
}
let mut candidates: Vec<(String, Instant, Held)> = Vec::new();
for (own, held) in [
(&self.buffers, Held::Shared),
(&self.local_buffers, Held::Local),
] {
for e in own.iter() {
candidates.push((e.key().clone(), e.value().last_write, held));
}
}
for e in self.foreign_buffers.iter() {
candidates.push((e.key().clone(), e.value().last_write, Held::Foreign));
}
candidates.sort_by_key(|(_, lw, _)| *lw);
for (key, _, held) in candidates {
if self.total_bytes.load(Ordering::Relaxed) <= self.config.global_memory_budget {
break;
}
match held {
Held::Shared | Held::Local => {
let (own, shared) = match held {
Held::Shared => (&self.buffers, true),
_ => (&self.local_buffers, false),
};
if let Some((_, removed)) = own.remove(&key) {
self.removed_own(&key, &removed, shared);
}
}
Held::Foreign => {
if let Some(removed) = self.remove_foreign(&key) {
self.note_removed(foreign_topic(&key), removed.last_seq(), false);
let _ = self.total_bytes.try_update(
Ordering::Relaxed,
Ordering::Relaxed,
|cur| Some(cur.saturating_sub(removed.footprint())),
);
}
}
}
}
}
let gone: Vec<String> = self
.removed_through
.iter()
.filter(|entry| {
let topic = entry.key();
entry.value().at.elapsed() > ttl
&& !self.buffers.contains_key(topic)
&& !self.local_buffers.contains_key(topic)
&& !self.foreign_epochs.contains_key(topic)
})
.map(|entry| entry.key().clone())
.collect();
for topic in gone {
if let Some((_, removed)) = self.removed_through.remove(&topic) {
self.forgotten
.fetch_max(removed.shared_through, Ordering::Relaxed);
}
}
let mut any = self.removed_any.lock();
if let Some(removed) = *any
&& removed.at.elapsed() > ttl
{
self.forgotten
.fetch_max(removed.shared_through, Ordering::Relaxed);
*any = None;
}
drop(any);
self.relayed_unkept
.retain(|_, delivered| delivered.at.elapsed() <= ttl);
self.trim_marks();
}
fn removed_own(&self, topic: &str, removed: &TopicRecoveryBuffer, shared: bool) {
self.note_removed(topic, removed.last_seq(), shared);
let _ = self
.total_bytes
.try_update(Ordering::Relaxed, Ordering::Relaxed, |cur| {
Some(cur.saturating_sub(removed.footprint()))
});
}
fn removed_after(&self, topic: &str) -> Option<u64> {
let own = self
.removed_through
.get(topic)
.map(|removed| removed.through);
let any = self.removed_any.lock().map(|removed| removed.through);
own.max(any)
}
pub(crate) fn lost_after(&self, topic: &str, after: u64) -> Vec<String> {
let any = self
.removed_any
.lock()
.map_or(0, |removed| removed.shared_through);
if any.max(self.forgotten.load(Ordering::Relaxed)) > after {
return vec![topic.to_owned()];
}
if crate::server::is_pattern(topic) {
let mut lost: Vec<String> = self
.removed_through
.iter()
.filter(|entry| entry.value().shared_through > after)
.filter(|entry| crate::server::glob_match(topic, entry.key()))
.map(|entry| entry.key().clone())
.chain(
self.buffers
.iter()
.filter(|entry| entry.value().evicted_through > after)
.filter(|entry| crate::server::glob_match(topic, entry.key()))
.map(|entry| entry.key().clone()),
)
.collect();
lost.sort_unstable();
lost.dedup();
return lost;
}
let removed = self
.removed_through
.get(topic)
.is_some_and(|removed| removed.shared_through > after);
let evicted = self
.buffers
.get(topic)
.is_some_and(|buf| buf.evicted_through > after);
if removed || evicted {
vec![topic.to_owned()]
} else {
Vec::new()
}
}
pub(crate) fn lost_everything(&self) {
let mut topics: Vec<String> = self
.interest_since
.iter()
.map(|entry| entry.key().clone())
.chain(self.foreign_epochs.iter().map(|entry| entry.key().clone()))
.chain(
self.relayed_unkept
.iter()
.map(|entry| foreign_topic(entry.key()).to_owned()),
)
.chain(self.buffers.iter().map(|entry| entry.key().clone()))
.chain(self.local_buffers.iter().map(|entry| entry.key().clone()))
.filter(|topic| !crate::server::is_pattern(topic))
.collect();
topics.sort_unstable();
topics.dedup();
for topic in &topics {
self.not_kept(topic);
}
}
pub(crate) fn lost(&self, topic: &str) {
if !crate::server::is_pattern(topic) {
self.not_kept(topic);
return;
}
let mut matched: Vec<String> = self
.buffers
.iter()
.map(|entry| entry.key().clone())
.chain(self.local_buffers.iter().map(|entry| entry.key().clone()))
.chain(self.foreign_epochs.iter().map(|entry| entry.key().clone()))
.chain(self.interest_since.iter().map(|entry| entry.key().clone()))
.filter(|name| {
!crate::server::is_pattern(name) && crate::server::glob_match(topic, name)
})
.collect();
matched.sort_unstable();
matched.dedup();
for name in &matched {
self.not_kept(name);
}
}
fn note_removed(&self, topic: &str, seq: u64, shared: bool) {
if seq == 0 {
return;
}
if let Some(mut removed) = self.removed_through.get_mut(topic) {
removed.note(seq, shared);
return;
}
if self.removed_through.len() >= MAX_UNKEPT_TOPICS {
self.removed_any
.lock()
.get_or_insert_with(Removed::none)
.note(seq, shared);
return;
}
self.removed_through
.entry(topic.to_owned())
.or_insert_with(Removed::none)
.note(seq, shared);
}
pub(crate) fn not_kept(&self, topic: &str) {
let seq = self.arrival.fetch_add(1, Ordering::Relaxed);
self.note_removed(topic, seq, false);
}
pub(crate) fn interest_began(&self, topic: &str) {
self.interest_since.insert(
topic.to_owned(),
(self.arrival.load(Ordering::Relaxed), Instant::now()),
);
}
pub(crate) fn interests(&self) -> Vec<(String, u64)> {
self.interest_since
.iter()
.map(|entry| {
let age = entry.value().1.elapsed().as_millis();
(entry.key().clone(), u64::try_from(age).unwrap_or(u64::MAX))
})
.collect()
}
pub(crate) fn mark(&self) {
let next = self.arrival.load(Ordering::Relaxed);
let mut marks = self.marks.lock();
if marks.back().is_some_and(|(_, last)| *last == next) {
return;
}
if marks.len() == MAX_MARKS {
marks.pop_front();
}
marks.push_back((Instant::now(), next));
}
fn trim_marks(&self) {
let oldest = self
.buffers
.iter()
.filter_map(|buf| buf.entries.front().map(|(_, seq)| *seq))
.min()
.unwrap_or(u64::MAX);
let mut marks = self.marks.lock();
while marks.len() > 1 && marks[1].1 <= oldest {
marks.pop_front();
}
}
fn arrival_at(&self, at: Instant) -> u64 {
let marks = self.marks.lock();
let after = marks.partition_point(|(mark, _)| *mark <= at);
after.checked_sub(1).map_or(0, |i| marks[i].1)
}
pub(crate) fn own_topics_matching(&self, pattern: &str) -> Vec<String> {
self.buffers
.iter()
.filter(|entry| crate::server::glob_match(pattern, entry.key()))
.map(|entry| entry.key().clone())
.collect()
}
pub(crate) fn published_unheard(
&self,
topic: &str,
after: u64,
named: impl Fn(u32) -> bool,
) -> Option<(u32, Vec<(u64, Bytes)>)> {
let buf = self.buffers.get(topic)?;
if named(buf.epoch) {
return None;
}
let messages = buf
.held_from(0)
.filter(|(_, seq, _)| *seq > after)
.map(|(offset, _, data)| (offset, data.clone()))
.collect();
Some((buf.epoch, messages))
}
pub(crate) fn arrived_through(&self) -> u64 {
self.arrival.load(Ordering::Acquire).saturating_sub(1)
}
pub(crate) fn arrived_before(&self, age: Duration) -> u64 {
Instant::now()
.checked_sub(age.saturating_add(LATELY_MARGIN))
.map_or(0, |at| self.arrival_at(at).saturating_sub(1))
}
pub(crate) fn interest_ended(&self, topic: &str) {
self.interest_since.remove(topic);
}
pub(crate) fn interest_linger(&self) -> Duration {
const MAX_LINGER_SECS: u64 = 10 * 365 * 86_400;
Duration::from_secs(self.config.history_ttl_secs.min(MAX_LINGER_SECS))
}
fn remove_foreign(&self, key: &str) -> Option<ForeignRecoveryBuffer> {
let (key, removed) = self.foreign_buffers.remove_if(key, |key, removed| {
#[cfg(test)]
REMOVING.with_borrow(|hook| hook.as_ref().map(|hook| hook()));
self.forget_foreign(key, removed.epoch);
true
})?;
if let Some(delivered) = Delivered::of(&removed)
&& self.relayed_unkept.len() < MAX_UNKEPT_TOPICS
{
self.relayed_unkept.insert(key, delivered);
}
Some(removed)
}
fn forget_foreign(&self, key: &str, epoch: u32) {
if let Some((topic, _)) = key.split_once('\0') {
if let Some(mut epochs) = self.foreign_epochs.get_mut(topic) {
epochs.retain(|e| *e != epoch);
}
self.foreign_epochs
.remove_if(topic, |_, epochs| epochs.is_empty());
}
}
pub(crate) fn history_secs(&self) -> u64 {
self.config
.history_ttl_secs
.saturating_add(CLEANUP_INTERVAL.as_secs())
}
pub(crate) fn topic_count(&self) -> usize {
self.buffers.len()
}
#[cfg(test)]
pub(crate) fn foreign_buffer_count(&self) -> usize {
self.foreign_buffers.len()
}
pub(crate) fn total_bytes(&self) -> usize {
self.total_bytes.load(Ordering::Relaxed)
}
}
#[cfg(test)]
thread_local! {
static REMOVING: std::cell::RefCell<Option<Box<dyn Fn()>>> = const { std::cell::RefCell::new(None) };
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn a_foreign_stream_made_again_as_cleanup_removes_it_is_still_recovered() {
let mgr = std::sync::Arc::new(RecoveryManager::new(RecoveryConfig {
history_ttl_secs: 0, ..RecoveryConfig::default()
}));
mgr.interest_began("topic");
mgr.push_foreign("topic", make_data("old"), 77, 0);
std::thread::sleep(std::time::Duration::from_millis(5));
let pushing = std::sync::Arc::new(std::sync::Mutex::new(None));
let (relay, slot) = (std::sync::Arc::clone(&mgr), std::sync::Arc::clone(&pushing));
REMOVING.with_borrow_mut(|hook| {
*hook = Some(Box::new(move || {
let relay = std::sync::Arc::clone(&relay);
let pushed = std::thread::spawn(move || {
relay.push_foreign("topic", make_data("new"), 77, 1);
relay.push_foreign("topic", make_data("later"), 77, 2);
});
std::thread::sleep(std::time::Duration::from_millis(50));
*slot.lock().unwrap() = Some(pushed);
}));
});
mgr.cleanup();
REMOVING.with_borrow_mut(|hook| *hook = None);
let pushed = pushing
.lock()
.unwrap()
.take()
.expect("cleanup removed the buffer");
pushed.join().unwrap();
assert_eq!(mgr.streams("topic"), vec![(77, 2)]);
}
fn make_data(s: &str) -> Bytes {
Bytes::from(s.to_owned())
}
#[test]
fn test_push_recover_roundtrip() {
let mut buf = TopicRecoveryBuffer::new(4, 0); for i in 0..5 {
buf.push(make_data(&format!("msg{i}")), i + 1);
}
let recovered = buf.recover_since(2, 500).unwrap();
assert_eq!(recovered.len(), 2);
assert_eq!(&recovered[0].1[..], b"msg3");
assert_eq!(&recovered[1].1[..], b"msg4");
}
#[test]
fn test_buffer_overflow() {
let mut buf = TopicRecoveryBuffer::new(2, 0); for i in 0..10 {
buf.push(make_data(&format!("msg{i}")), i + 1);
}
assert_eq!(buf.head_offset, 10);
assert_eq!(buf.tail_offset(), 6);
assert!(buf.recover_since(3, 500).is_none());
let boundary = buf.recover_since(5, 500).unwrap();
assert_eq!(boundary.len(), 4); assert_eq!(&boundary[0].1[..], b"msg6");
let recovered = buf.recover_since(7, 500).unwrap();
assert_eq!(recovered.len(), 2);
assert_eq!(&recovered[0].1[..], b"msg8");
assert_eq!(&recovered[1].1[..], b"msg9");
}
#[test]
fn test_epoch_mismatch() {
let config = RecoveryConfig::default();
let mgr = RecoveryManager::new(config);
mgr.push("topic1", make_data("hello"));
let (real_epoch, _) = mgr.get_position("topic1").unwrap();
let wrong_epoch = real_epoch.wrapping_add(1);
match mgr.recover("topic1", wrong_epoch, 0) {
RecoveryResult::NotRecovered { epoch, offset } => {
assert_eq!(epoch, real_epoch);
assert_eq!(offset, 1); }
_ => panic!("expected NotRecovered for epoch mismatch"),
}
}
#[test]
fn test_empty_buffer() {
let config = RecoveryConfig::default();
let mgr = RecoveryManager::new(config);
match mgr.recover("nonexistent", 0, 0) {
RecoveryResult::NoHistory => {}
_ => panic!("expected NoHistory for missing topic"),
}
}
#[test]
fn test_ttl_cleanup() {
let config = RecoveryConfig {
history_ttl_secs: 0, ..RecoveryConfig::default()
};
let mgr = RecoveryManager::new(config);
mgr.push("topic1", make_data("data"));
assert_eq!(mgr.topic_count(), 1);
std::thread::sleep(std::time::Duration::from_millis(5));
mgr.cleanup();
assert_eq!(mgr.topic_count(), 0);
assert_eq!(mgr.total_bytes(), 0);
}
#[test]
fn test_global_budget_eviction() {
let config = RecoveryConfig {
global_memory_budget: 10, history_ttl_secs: 3600, ..RecoveryConfig::default()
};
let mgr = RecoveryManager::new(config);
mgr.push("t1", make_data("aaaaaaa")); std::thread::sleep(std::time::Duration::from_millis(2));
mgr.push("t2", make_data("bbbbbbb")); std::thread::sleep(std::time::Duration::from_millis(2));
mgr.push("t3", make_data("ccccccc"));
assert!(mgr.total_bytes() > 10);
mgr.cleanup();
assert!(mgr.total_bytes() <= 10);
assert!(mgr.topic_count() < 3);
}
#[test]
fn test_get_position() {
let config = RecoveryConfig::default();
let mgr = RecoveryManager::new(config);
assert!(mgr.get_position("topic1").is_none());
mgr.push("topic1", make_data("msg0"));
mgr.push("topic1", make_data("msg1"));
mgr.push("topic1", make_data("msg2"));
let (_epoch, offset) = mgr.get_position("topic1").unwrap();
assert_eq!(offset, 3); }
#[test]
fn over_the_budget_a_new_topic_goes_unstamped() {
let mgr = RecoveryManager::new(RecoveryConfig {
global_memory_budget: 1,
..RecoveryConfig::default()
});
assert!(mgr.push_stamped("first", |_, _| make_data("a")).is_some());
assert!(mgr.push_stamped("first", |_, _| make_data("b")).is_some());
assert!(mgr.push_stamped("second", |_, _| make_data("c")).is_none());
}
#[test]
fn push_stamped_offset_matches_storage_and_recover() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
let mut reserved = Vec::new();
for _ in 0..3 {
let stored = mgr
.push_stamped("topic1", |epoch, offset| {
reserved.push((epoch, offset));
make_data(&format!("o={offset}"))
})
.unwrap();
let (_, off) = *reserved.last().unwrap();
assert_eq!(&stored[..], format!("o={off}").as_bytes());
}
assert_eq!(
reserved.iter().map(|(_, o)| *o).collect::<Vec<_>>(),
vec![0, 1, 2]
);
assert!(reserved.iter().all(|(e, _)| *e == reserved[0].0));
let (epoch, _) = mgr.get_position("topic1").unwrap();
match mgr.recover("topic1", epoch, 0) {
RecoveryResult::Recovered { publications, .. } => {
assert_eq!(&publications[0][..], b"o=1");
assert_eq!(&publications[1][..], b"o=2");
}
_ => panic!("expected Recovered"),
}
}
#[test]
fn test_recover_cap() {
let config = RecoveryConfig {
max_recovery_messages: 3,
buffer_size_bits: 5, ..RecoveryConfig::default()
};
let mgr = RecoveryManager::new(config);
for i in 0..20 {
mgr.push("topic1", make_data(&format!("msg{i}")));
}
let (epoch, _) = mgr.get_position("topic1").unwrap();
match mgr.recover("topic1", epoch, 5) {
RecoveryResult::NotRecovered {
epoch: ep,
offset: off,
} => {
assert_eq!(ep, epoch);
assert_eq!(off, 20); }
_ => panic!("expected NotRecovered when cap truncates"),
}
match mgr.recover("topic1", epoch, 17) {
RecoveryResult::Recovered { publications, .. } => {
assert_eq!(publications.len(), 2); assert_eq!(&publications[0][..], b"msg18");
assert_eq!(&publications[1][..], b"msg19");
}
_ => panic!("expected Recovered when within cap"),
}
}
#[test]
fn test_foreign_push_recover() {
let config = RecoveryConfig::default();
let mgr = RecoveryManager::new(config);
mgr.interest_began("topic1");
let foreign_epoch: u32 = 42;
for i in 0u64..5 {
mgr.push_foreign("topic1", make_data(&format!("fmsg{i}")), foreign_epoch, i);
}
match mgr.recover("topic1", foreign_epoch, 2) {
RecoveryResult::Recovered {
publications,
epoch,
offset,
} => {
assert_eq!(epoch, foreign_epoch);
assert_eq!(offset, 4); assert_eq!(publications.len(), 2);
assert_eq!(&publications[0][..], b"fmsg3");
assert_eq!(&publications[1][..], b"fmsg4");
}
other => panic!(
"expected Recovered, got {:?}",
match other {
RecoveryResult::NotRecovered { .. } => "NotRecovered",
RecoveryResult::NoHistory => "NoHistory",
_ => "unknown",
}
),
}
}
#[test]
fn a_relayed_message_held_already_is_not_new() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
assert!(mgr.push_foreign("t", make_data("m0"), 7, 0));
assert!(mgr.push_foreign("t", make_data("m1"), 7, 1));
assert!(!mgr.push_foreign("t", make_data("m1"), 7, 1));
assert!(!mgr.push_foreign("t", make_data("m0"), 7, 0));
assert!(mgr.push_foreign("t", make_data("m3"), 7, 3));
assert!(mgr.push_foreign("t", make_data("m2"), 7, 2));
assert!(!mgr.push_foreign("t", make_data("m2"), 7, 2));
}
#[test]
fn a_node_asks_from_its_first_hole_in_each_relayed_stream() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
for offset in [0, 1, 2, 4, 5] {
mgr.push_foreign("a", make_data("x"), 7, offset);
}
for offset in 10..13 {
mgr.push_foreign("b", make_data("y"), 9, offset);
}
let mut points = mgr.foreign_positions();
points.sort();
assert_eq!(
points,
vec![("a".to_owned(), 7, 2), ("b".to_owned(), 9, 12)]
);
mgr.push_foreign("a", make_data("x"), 7, 3);
assert!(mgr.foreign_positions().contains(&("a".to_owned(), 7, 5)));
}
#[test]
fn an_own_stream_that_let_go_what_a_client_missed_is_not_recovered_by_streams() {
let mgr = RecoveryManager::new(RecoveryConfig {
buffer_size_bits: 2,
..RecoveryConfig::default()
});
mgr.push("prices", make_data("0"));
let (epoch, _) = mgr.get_position("prices").unwrap();
for n in 1..=10 {
mgr.push("prices", make_data(&n.to_string()));
}
assert!(not_recovered(&mgr.recover_streams(
"prices",
(epoch, 0),
&[(epoch, 0)]
)));
assert!(not_recovered(&mgr.recover("prices", epoch, 0)));
let RecoveryResult::Recovered { publications, .. } =
mgr.recover_streams("prices", (epoch, 7), &[(epoch, 7)])
else {
panic!("not recovered");
};
assert_eq!(publications.len(), 3);
mgr.push_stamped_local("local", |_, _| make_data("0"));
let (local, _) = mgr.get_position("local").unwrap();
for n in 1..=10 {
mgr.push_stamped_local("local", |_, _| make_data(&n.to_string()));
}
assert!(not_recovered(&mgr.recover_streams(
"local",
(local, 0),
&[(local, 0)]
)));
}
#[test]
fn a_window_of_delivered_offsets_tells_what_is_new() {
let mut delivered = Delivered::first(7, 5);
assert!(!delivered.deliver(5) && !delivered.deliver(0));
assert!(delivered.deliver(7), "a hole at 6");
assert_eq!((delivered.through, delivered.above), (5, 0b10));
assert!(!delivered.deliver(7));
assert!(delivered.any_after(6) && !delivered.any_after(7));
assert!(delivered.deliver(6));
assert_eq!((delivered.through, delivered.above), (7, 0));
assert!(delivered.deliver(200));
assert_eq!(delivered.through, 136);
assert!(delivered.has(200) && !delivered.has(199));
assert!(!delivered.deliver(200));
assert!(delivered.deliver(137));
assert_eq!(delivered.through, 137);
let mut edge = Delivered::first(7, u64::MAX - 1);
assert!(edge.deliver(u64::MAX) && !edge.deliver(u64::MAX));
}
#[test]
fn a_stream_relayed_with_no_room_to_keep_it_is_not_delivered_twice() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.push("setup", make_data("s"));
let budget = mgr.total_bytes();
let mgr = with_budget(mgr, budget);
assert!(mgr.push_foreign("prices:open", make_data("0"), 7, 0));
assert!(mgr.foreign_buffers.is_empty());
assert!(
mgr.foreign_positions()
.contains(&("prices:open".to_owned(), 7, 0))
);
assert!(!mgr.push_foreign("prices:open", make_data("0"), 7, 0));
assert!(mgr.push_foreign("prices:open", make_data("2"), 7, 2));
let mgr = with_budget(mgr, usize::MAX);
assert!(mgr.push_foreign("prices:open", make_data("1"), 7, 1));
assert!(mgr.foreign_buffers.is_empty());
assert!(!mgr.push_foreign("prices:open", make_data("2"), 7, 2));
assert!(mgr.push_foreign("prices:open", make_data("3"), 7, 3));
assert_eq!(mgr.foreign_buffers.len(), 1);
assert!(mgr.relayed_unkept.is_empty());
assert!(!mgr.push_foreign("prices:open", make_data("1"), 7, 1));
}
#[test]
fn a_relayed_buffer_removed_leaves_where_this_node_stood() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
for offset in [0, 1, 3] {
mgr.push_foreign("a", make_data("x"), 7, offset);
}
let mgr = with_budget(mgr, 0);
mgr.cleanup();
assert!(mgr.foreign_buffers.is_empty());
assert!(mgr.foreign_positions().contains(&("a".to_owned(), 7, 1)));
for offset in [0, 1, 3] {
assert!(!mgr.push_foreign("a", make_data("x"), 7, offset));
}
assert!(mgr.push_foreign("a", make_data("x"), 7, 2));
}
#[test]
fn a_peer_gets_what_this_node_published_after_its_position() {
let mgr = RecoveryManager::new(RecoveryConfig {
buffer_size_bits: 2, ..RecoveryConfig::default()
});
for i in 0..6 {
mgr.push("t", make_data(&format!("m{i}")));
}
let (epoch, head) = mgr.get_position("t").unwrap();
assert_eq!(head, 6);
let sent = |after| -> Vec<(u64, String)> {
mgr.published_after("t", epoch, after)
.into_iter()
.map(|(offset, data)| (offset, String::from_utf8(data.to_vec()).unwrap()))
.collect()
};
assert_eq!(sent(3), vec![(4, "m4".to_owned()), (5, "m5".to_owned())]);
assert_eq!(sent(0).first(), Some(&(2, "m2".to_owned())));
assert_eq!(sent(0).len(), 4);
assert!(sent(5).is_empty());
assert!(sent(u64::MAX).is_empty());
assert!(
mgr.published_after("t", epoch.wrapping_add(1), 0)
.is_empty()
);
assert!(mgr.published_after("other", epoch, 0).is_empty());
}
#[test]
fn test_foreign_epoch_mismatch() {
let config = RecoveryConfig::default();
let mgr = RecoveryManager::new(config);
let foreign_epoch: u32 = 42;
mgr.push_foreign("topic1", make_data("data"), foreign_epoch, 0);
let wrong_epoch = 99;
match mgr.recover("topic1", wrong_epoch, 0) {
RecoveryResult::NoHistory => {}
_ => panic!("expected NoHistory for unmatched foreign epoch"),
}
}
#[test]
fn test_foreign_buffer_eviction() {
let config = RecoveryConfig {
global_memory_budget: 20,
history_ttl_secs: 3600,
..RecoveryConfig::default()
};
let mgr = RecoveryManager::new(config);
mgr.push("t_local", make_data("aaaaaaa"));
std::thread::sleep(std::time::Duration::from_millis(2));
mgr.push_foreign("t_foreign", make_data("bbbbbbb"), 42, 0);
std::thread::sleep(std::time::Duration::from_millis(2));
mgr.push_foreign("t_foreign2", make_data("ccccccc"), 43, 0);
assert!(mgr.total_bytes() > 20);
mgr.cleanup();
assert!(mgr.total_bytes() <= 20);
}
#[test]
fn fresh_foreign_epochs_stop_at_the_budget() {
let config = RecoveryConfig {
global_memory_budget: 64 * 1024,
..RecoveryConfig::default()
};
let mgr = RecoveryManager::new(config);
mgr.interest_began("t");
for epoch in 0..10_000u32 {
mgr.push_foreign("t", make_data("x"), epoch, 0);
}
let one_buffer = ForeignRecoveryBuffer::new(mgr.config.buffer_size_bits, 0, 8).footprint();
assert!(
mgr.total_bytes() <= 64 * 1024 + one_buffer,
"{}",
mgr.total_bytes()
);
assert!(mgr.foreign_buffers.len() < 10_000);
mgr.push_foreign("t", make_data("y"), 0, 1);
assert!(mgr.streams("t").contains(&(0, 1)));
assert!(not_recovered(&mgr.recover("t", 0, 0)));
}
#[test]
fn test_foreign_ttl_cleanup() {
let config = RecoveryConfig {
history_ttl_secs: 0, ..RecoveryConfig::default()
};
let mgr = RecoveryManager::new(config);
mgr.push_foreign("topic1", make_data("data"), 42, 0);
std::thread::sleep(std::time::Duration::from_millis(5));
mgr.cleanup();
assert_eq!(mgr.total_bytes(), 0);
assert_eq!(mgr.foreign_buffers.len(), 0);
}
#[test]
fn test_foreign_and_local_coexist() {
let config = RecoveryConfig::default();
let mgr = RecoveryManager::new(config);
mgr.interest_began("topic1");
mgr.push("topic1", make_data("local0"));
mgr.push("topic1", make_data("local1"));
let (local_epoch, _) = mgr.get_position("topic1").unwrap();
let foreign_epoch: u32 = 77;
mgr.push_foreign("topic1", make_data("foreign0"), foreign_epoch, 0);
mgr.push_foreign("topic1", make_data("foreign1"), foreign_epoch, 1);
match mgr.recover("topic1", local_epoch, 0) {
RecoveryResult::Recovered { publications, .. } => {
let got: Vec<&[u8]> = publications.iter().map(|p| &p[..]).collect();
assert_eq!(got, [&b"local1"[..], b"foreign0", b"foreign1"]);
}
_ => panic!("expected Recovered from both streams"),
}
match mgr.recover("topic1", foreign_epoch, 0) {
RecoveryResult::Recovered { publications, .. } => {
assert_eq!(publications.len(), 1);
assert_eq!(&publications[0][..], b"foreign1");
}
_ => panic!("expected Recovered from foreign buffer"),
}
}
#[test]
fn two_nodes_interleaved_recover_in_arrival_order() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.interest_began("room");
let other: u32 = 0xa;
mgr.push_foreign("room", make_data("a1"), other, 0);
mgr.push("room", make_data("b1"));
mgr.push_foreign("room", make_data("a2"), other, 1);
mgr.push("room", make_data("b2"));
let (epoch, _) = mgr.get_position("room").unwrap();
mgr.push_foreign("room", make_data("a3"), other, 2);
mgr.push("room", make_data("b3"));
mgr.push_foreign("room", make_data("a4"), other, 3);
mgr.push("room", make_data("b4"));
match mgr.recover("room", epoch, 1) {
RecoveryResult::Recovered { publications, .. } => {
let got: Vec<&[u8]> = publications.iter().map(|p| &p[..]).collect();
assert_eq!(got, [&b"a3"[..], b"b3", b"a4", b"b4"]);
}
_ => panic!("expected Recovered from both streams"),
}
}
#[test]
fn a_relayed_stream_with_a_hole_after_the_anchor_is_not_recovered() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.interest_began("room");
mgr.push_foreign("room", make_data("b0"), 7, 0);
mgr.push("room", make_data("a0"));
let (epoch, _) = mgr.get_position("room").unwrap();
mgr.push_foreign("room", make_data("b1"), 7, 1);
mgr.push_foreign("room", make_data("b3"), 7, 3);
assert!(matches!(
mgr.recover("room", epoch, 0),
RecoveryResult::NotRecovered { .. }
));
}
#[test]
fn a_stream_that_lost_what_came_after_the_anchor_is_not_recovered() {
let mgr = RecoveryManager::new(RecoveryConfig {
buffer_size_bits: 1, ..RecoveryConfig::default()
});
mgr.push_foreign("room", make_data("b0"), 7, 0);
mgr.push("room", make_data("a0"));
let (epoch, _) = mgr.get_position("room").unwrap();
for (i, text) in ["b1", "b2", "b3"].iter().enumerate() {
mgr.push_foreign("room", make_data(text), 7, i as u64 + 1);
}
assert!(matches!(
mgr.recover("room", epoch, 0),
RecoveryResult::NotRecovered { .. }
));
}
fn replayed(result: RecoveryResult) -> Option<Vec<String>> {
match result {
RecoveryResult::Recovered { publications, .. } => Some(
publications
.iter()
.map(|p| String::from_utf8(p.to_vec()).unwrap())
.collect(),
),
_ => None,
}
}
#[test]
fn a_client_from_a_node_that_saw_the_streams_in_another_order_loses_nothing() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.interest_began("room");
let (a, b) = (0xa, 0xb);
mgr.push_foreign("room", make_data("a0"), a, 0);
mgr.push_foreign("room", make_data("b0"), b, 0);
mgr.push_foreign("room", make_data("b1"), b, 1);
mgr.push_foreign("room", make_data("a1"), a, 1);
assert_eq!(
replayed(mgr.recover_streams("room", (a, 1), &[(a, 1), (b, 0)])),
Some(vec!["b1".to_owned()])
);
}
#[test]
fn every_named_stream_comes_from_its_own_offset() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.interest_began("room");
mgr.push("room", make_data("l0"));
mgr.push_foreign("room", make_data("f0"), 7, 0);
mgr.push("room", make_data("l1"));
mgr.push_foreign("room", make_data("f1"), 7, 1);
mgr.push("room", make_data("l2"));
let (local, _) = mgr.get_position("room").unwrap();
assert_eq!(
replayed(mgr.recover_streams("room", (local, 0), &[(local, 0), (7, 0)])),
Some(vec!["l1".to_owned(), "f1".to_owned(), "l2".to_owned()])
);
assert_eq!(
replayed(mgr.recover_streams("room", (local, 2), &[(local, 2), (7, 1)])),
Some(vec![])
);
}
#[test]
fn a_named_stream_this_node_does_not_hold_is_not_recovered() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.interest_began("room");
mgr.push_foreign("room", make_data("a0"), 0xa, 0);
assert_eq!(
replayed(mgr.recover_streams("room", (0xa, 0), &[(0xa, 0), (0xc, 4)])),
None
);
}
#[test]
fn a_named_stream_with_a_hole_after_the_position_is_not_recovered() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.interest_began("room");
mgr.push_foreign("room", make_data("a0"), 0xa, 0);
mgr.push_foreign("room", make_data("a2"), 0xa, 2);
assert_eq!(
replayed(mgr.recover_streams("room", (0xa, 0), &[(0xa, 0)])),
None
);
}
#[test]
fn an_unnamed_stream_that_came_before_the_last_message_is_not_recovered() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.interest_began("room");
mgr.push_foreign("room", make_data("c0"), 0xc, 0);
mgr.push_foreign("room", make_data("a0"), 0xa, 0);
assert_eq!(
replayed(mgr.recover_streams("room", (0xa, 0), &[(0xa, 0)])),
None
);
}
#[test]
fn an_unnamed_stream_that_came_after_the_last_message_is_replayed() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.interest_began("room");
mgr.push_foreign("room", make_data("a0"), 0xa, 0);
mgr.push_foreign("room", make_data("c0"), 0xc, 0);
mgr.push_foreign("room", make_data("c1"), 0xc, 1);
assert_eq!(
replayed(mgr.recover_streams("room", (0xa, 0), &[(0xa, 0)])),
Some(vec!["c0".to_owned(), "c1".to_owned()])
);
}
#[test]
fn an_unnamed_stream_held_from_its_middle_is_not_recovered() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.interest_began("room");
mgr.push_foreign("room", make_data("a0"), 0xa, 0);
mgr.push_foreign("room", make_data("c5"), 0xc, 5);
assert_eq!(
replayed(mgr.recover_streams("room", (0xa, 0), &[(0xa, 0)])),
None
);
}
#[test]
fn a_stream_removed_after_the_last_message_is_not_recovered() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.interest_began("room");
mgr.push_foreign("room", make_data("a0"), 0xa, 0);
mgr.push_foreign("room", make_data("c0"), 0xc, 0);
std::thread::sleep(Duration::from_millis(2));
mgr.push_foreign("room", make_data("a1"), 0xa, 1);
let budget = mgr.total_bytes() - 1;
let mgr = RecoveryManager {
config: RecoveryConfig {
global_memory_budget: budget,
..RecoveryConfig::default()
},
..mgr
};
mgr.cleanup();
assert!(!mgr.streams("room").iter().any(|(epoch, _)| *epoch == 0xc));
assert_eq!(
replayed(mgr.recover_streams("room", (0xa, 0), &[(0xa, 0)])),
None
);
}
fn with_budget(mgr: RecoveryManager, budget: usize) -> RecoveryManager {
RecoveryManager {
config: RecoveryConfig {
global_memory_budget: budget,
..RecoveryConfig::default()
},
..mgr
}
}
fn not_recovered(result: &RecoveryResult) -> bool {
matches!(result, RecoveryResult::NotRecovered { .. })
}
#[test]
fn a_node_lost_anew_leaves_no_topic_here_said_whole() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.push("news", make_data("0"));
mgr.push_stamped_local("local", |_, _| make_data("0"));
let (news, _) = mgr.get_position("news").unwrap();
let (local, _) = mgr.get_position("local").unwrap();
assert!(!not_recovered(&mgr.recover("news", news, 0)));
assert!(!not_recovered(&mgr.recover("local", local, 0)));
mgr.lost_everything();
assert!(not_recovered(&mgr.recover("news", news, 0)));
assert!(not_recovered(&mgr.recover_streams(
"news",
(news, 0),
&[(news, 0)]
)));
assert!(not_recovered(&mgr.recover("local", local, 0)));
assert!(not_recovered(&mgr.recover_streams(
"local",
(local, 0),
&[(local, 0)]
)));
}
#[test]
fn a_client_with_one_position_is_not_told_a_removed_stream_was_replayed() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.interest_began("room");
mgr.push("room", make_data("l0"));
let (local, _) = mgr.get_position("room").unwrap();
std::thread::sleep(Duration::from_millis(2));
mgr.push_foreign("room", make_data("f0"), 0xf, 0);
std::thread::sleep(Duration::from_millis(2));
mgr.push("room", make_data("l1"));
let budget = mgr.total_bytes() - 1;
let mgr = with_budget(mgr, budget);
mgr.cleanup();
assert!(mgr.streams("room").iter().all(|(epoch, _)| *epoch == local));
assert!(not_recovered(&mgr.recover("room", local, 0)));
}
#[test]
fn a_relayed_message_with_no_room_to_keep_it_is_never_recovered_as_nothing() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.interest_began("room");
mgr.push("room", make_data("l0"));
let (local, _) = mgr.get_position("room").unwrap();
let budget = mgr.total_bytes();
let mgr = with_budget(mgr, budget);
assert!(mgr.push_foreign("room", make_data("f0"), 0xf, 0));
assert!(mgr.streams("room").iter().all(|(epoch, _)| *epoch == local));
assert!(not_recovered(&mgr.recover("room", local, 0)));
assert_eq!(
replayed(mgr.recover_streams("room", (local, 0), &[(local, 0)])),
None
);
}
#[test]
fn a_message_published_with_no_room_to_keep_it_is_never_recovered_as_nothing() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.interest_began("room");
mgr.push_foreign("room", make_data("f0"), 0xf, 0);
let budget = mgr.total_bytes();
let mgr = with_budget(mgr, budget);
assert!(mgr.push_stamped("room", |_, _| make_data("l0")).is_none());
assert!(not_recovered(&mgr.recover("room", 0xf, 0)));
assert_eq!(
replayed(mgr.recover_streams("room", (0xf, 0), &[(0xf, 0)])),
None
);
}
#[test]
fn a_message_relayed_with_no_position_is_never_recovered_as_nothing() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.push("room", make_data("l0"));
let (local, _) = mgr.get_position("room").unwrap();
mgr.not_kept("room");
assert!(not_recovered(&mgr.recover("room", local, 0)));
assert_eq!(
replayed(mgr.recover_streams("room", (local, 0), &[(local, 0)])),
None
);
mgr.push("room", make_data("l1"));
assert!(!not_recovered(&mgr.recover("room", local, 1)));
}
#[test]
fn a_peer_hears_what_it_did_not_hear_of_and_this_node_no_longer_holds() {
let mgr = with_budget(RecoveryManager::new(RecoveryConfig::default()), 0);
let heard = mgr.arrived_through();
for topic in ["news", "prices:a"] {
assert!(mgr.push_stamped(topic, |_, _| make_data("x")).is_none());
}
assert!(
mgr.push_stamped_local("mine", |_, _| make_data("x"))
.is_none()
);
mgr.push_foreign("theirs", make_data("x"), 0xf, 0);
mgr.not_kept("told");
assert_eq!(mgr.lost_after("news", heard), ["news"]);
assert_eq!(mgr.lost_after("prices:*", heard), ["prices:a"]);
for topic in ["other", "mine", "theirs", "told"] {
assert!(mgr.lost_after(topic, heard).is_empty(), "{topic}");
}
assert!(mgr.lost_after("news", mgr.arrived_through()).is_empty());
}
#[test]
fn a_message_the_ring_let_go_before_a_peer_heard_of_it_is_told() {
let mgr = RecoveryManager::new(RecoveryConfig {
buffer_size_bits: 1,
..RecoveryConfig::default()
});
let heard = mgr.arrived_through();
for text in ["a", "b", "c"] {
mgr.push("news", make_data(text));
}
assert_eq!(mgr.lost_after("news", heard), ["news"]);
assert_eq!(mgr.lost_after("n*", heard), ["news"]);
assert!(mgr.lost_after("news", heard + 1).is_empty());
}
#[test]
fn a_record_let_go_counts_for_every_topic_a_peer_did_not_hear_of_it_by() {
let mgr = RecoveryManager::new(RecoveryConfig {
history_ttl_secs: 0,
global_memory_budget: 0,
..RecoveryConfig::default()
});
let heard = mgr.arrived_through();
assert!(mgr.push_stamped("news", |_, _| make_data("x")).is_none());
std::thread::sleep(Duration::from_millis(5));
mgr.cleanup();
assert!(!mgr.removed_through.contains_key("news"));
assert_eq!(mgr.lost_after("other", heard), ["other"]);
assert!(mgr.lost_after("other", mgr.arrived_through()).is_empty());
}
#[test]
fn a_buffer_removed_is_told_to_peers_when_they_had_some_of_it() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
let heard = mgr.arrived_through();
mgr.push("news", make_data("x"));
mgr.push_stamped_local("mine", |_, _| make_data("x"));
let mgr = with_budget(mgr, 0);
mgr.cleanup();
assert_eq!(mgr.topic_count(), 0);
assert_eq!(mgr.lost_after("news", heard), ["news"]);
assert!(mgr.lost_after("mine", heard).is_empty());
}
#[test]
fn what_was_published_to_this_nodes_subscribers_only_is_a_stream_of_its_own() {
let mgr = RecoveryManager::new(RecoveryConfig {
buffer_size_bits: 1,
..RecoveryConfig::default()
});
mgr.push("news", make_data("s0"));
let (shared, _) = mgr.get_position("news").unwrap();
for text in ["l0", "l1", "l2"] {
mgr.push_stamped_local("news", |_, _| make_data(text));
}
mgr.push("news", make_data("s1"));
let streams = mgr.streams("news");
assert_eq!(streams.len(), 2);
assert!(streams.contains(&(shared, 1)));
let (local, _) = *streams.iter().find(|(e, _)| *e != shared).unwrap();
assert_eq!(
mgr.published_after("news", shared, 0),
vec![(1, make_data("s1"))]
);
assert!(mgr.published_after("news", local, 0).is_empty());
let (epoch, all) = mgr.published_unheard("news", 0, |_| false).unwrap();
assert_eq!(epoch, shared);
assert_eq!(all, vec![(0, make_data("s0")), (1, make_data("s1"))]);
assert!(not_recovered(&mgr.recover("news", shared, 0)));
let named = [(shared, 0), (local, 1)];
let RecoveryResult::Recovered { publications, .. } =
mgr.recover_streams("news", (shared, 0), &named)
else {
panic!("not recovered");
};
assert_eq!(publications, vec![make_data("l2"), make_data("s1")]);
}
#[test]
fn a_topic_not_kept_with_no_room_to_name_it_counts_for_every_topic() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
for n in 0..MAX_UNKEPT_TOPICS {
mgr.removed_through.insert(format!("t{n}"), Removed::none());
}
mgr.push("room", make_data("l0"));
let (local, _) = mgr.get_position("room").unwrap();
let heard = mgr.arrived_through();
mgr.not_kept("unnamed");
assert!(!mgr.removed_through.contains_key("unnamed"));
assert!(not_recovered(&mgr.recover("room", local, 0)));
assert!(mgr.lost_after("other", heard).is_empty());
let mgr = with_budget(mgr, 0);
assert!(mgr.push_stamped("unnamed", |_, _| make_data("x")).is_none());
assert_eq!(mgr.lost_after("other", heard), ["other"]);
assert_eq!(mgr.lost_after("prices:*", heard), ["prices:*"]);
}
#[test]
fn a_peer_saying_a_pattern_lost_marks_each_topic_here_it_matches() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.push("prices:a", make_data("a0"));
mgr.push_foreign("prices:b", make_data("b0"), 0xf, 0);
mgr.interest_began("prices:c");
mgr.push("other", make_data("o0"));
let (local, _) = mgr.get_position("prices:a").unwrap();
let (other, _) = mgr.get_position("other").unwrap();
mgr.lost("prices:*");
assert!(not_recovered(&mgr.recover("prices:a", local, 0)));
assert!(not_recovered(&mgr.recover("prices:b", 0xf, 0)));
assert!(mgr.removed_through.contains_key("prices:c"));
assert!(!mgr.removed_through.contains_key("prices:*"));
assert!(!not_recovered(&mgr.recover("other", other, 0)));
mgr.lost("other");
assert!(not_recovered(&mgr.recover("other", other, 0)));
}
#[test]
fn a_pattern_matches_the_topics_of_this_nodes_own_streams() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
for topic in ["prices:a", "prices:b", "other"] {
mgr.push(topic, make_data("x"));
}
mgr.push_foreign("prices:c", make_data("f"), 0xf, 0);
let mut matched = mgr.own_topics_matching("prices:*");
matched.sort();
assert_eq!(matched, ["prices:a", "prices:b"]);
assert!(mgr.own_topics_matching("none:*").is_empty());
}
#[test]
fn a_peer_gets_what_this_node_published_after_what_it_heard_of() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.push("news", make_data("old"));
let (epoch, _) = mgr.get_position("news").unwrap();
let minute_ago = Instant::now().checked_sub(Duration::from_secs(60)).unwrap();
mgr.marks
.lock()
.push_back((minute_ago, mgr.arrival.load(Ordering::Relaxed)));
let heard = mgr.arrived_through();
mgr.push("news", make_data("new"));
assert_eq!(mgr.arrived_before(Duration::from_secs(30)), heard);
assert_eq!(mgr.arrived_before(Duration::from_secs(120)), 0);
let (sent_epoch, sent) = mgr.published_unheard("news", heard, |_| false).unwrap();
assert_eq!(sent_epoch, epoch);
assert_eq!(sent, vec![(1, make_data("new"))]);
let (_, all) = mgr.published_unheard("news", 0, |_| false).unwrap();
assert_eq!(all.len(), 2);
assert!(mgr.published_unheard("news", 0, |e| e == epoch).is_none());
assert!(mgr.published_unheard("other", 0, |_| false).is_none());
}
#[test]
fn the_marks_go_back_as_far_as_this_node_holds_its_messages() {
let mgr = RecoveryManager::new(RecoveryConfig {
buffer_size_bits: 1,
..RecoveryConfig::default()
});
for text in ["a", "b", "c"] {
mgr.mark();
mgr.push("news", make_data(text));
}
mgr.mark();
mgr.mark();
let marks = |mgr: &RecoveryManager| -> Vec<u64> {
mgr.marks.lock().iter().map(|(_, next)| *next).collect()
};
assert_eq!(marks(&mgr), [1, 2, 3, 4], "none while nothing came");
mgr.cleanup();
assert_eq!(marks(&mgr), [2, 3, 4]);
}
#[test]
fn more_than_the_recovery_limit_is_not_recovered() {
let mgr = RecoveryManager::new(RecoveryConfig {
max_recovery_messages: 2,
..RecoveryConfig::default()
});
mgr.interest_began("room");
for i in 0..2 {
mgr.push_foreign("room", make_data("a"), 0xa, i);
mgr.push_foreign("room", make_data("b"), 0xb, i);
}
assert_eq!(
replayed(mgr.recover_streams("room", (0xa, 0), &[(0xa, 0), (0xb, 0)])),
Some(vec!["a".to_owned(), "b".to_owned()])
);
mgr.push_foreign("room", make_data("b"), 0xb, 2);
assert_eq!(
replayed(mgr.recover_streams("room", (0xa, 0), &[(0xa, 0), (0xb, 0)])),
None
);
}
#[test]
fn a_named_stream_relayed_before_the_topic_came_back_here_is_not_recovered() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.interest_began("room");
mgr.push_foreign("room", make_data("a0"), 0xa, 0);
mgr.push_foreign("room", make_data("a1"), 0xa, 1);
assert!(replayed(mgr.recover_streams("room", (0xa, 1), &[(0xa, 1)])).is_some());
mgr.interest_ended("room");
mgr.interest_began("room");
assert_eq!(
replayed(mgr.recover_streams("room", (0xa, 1), &[(0xa, 1)])),
None
);
assert_eq!(
replayed(mgr.recover_streams("room", (0xa, 0), &[(0xa, 0)])),
None
);
}
#[test]
fn a_stream_relayed_out_of_order_is_replayed_in_its_own_order() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.interest_began("room");
mgr.push_foreign("room", make_data("a0"), 0xa, 0);
mgr.push_foreign("room", make_data("b0"), 0xb, 0);
mgr.push_foreign("room", make_data("b2"), 0xb, 2);
mgr.push_foreign("room", make_data("a1"), 0xa, 1);
mgr.push_foreign("room", make_data("b1"), 0xb, 1);
assert_eq!(
replayed(mgr.recover_streams("room", (0xa, 0), &[(0xa, 0), (0xb, 0)])),
Some(vec!["a1".to_owned(), "b1".to_owned(), "b2".to_owned()])
);
}
#[test]
fn the_streams_of_a_topic_are_what_this_node_holds_at_their_last_offsets() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.interest_began("room");
assert!(mgr.streams("room").is_empty());
mgr.push("room", make_data("l0"));
mgr.push("room", make_data("l1"));
mgr.push_foreign("room", make_data("f3"), 7, 3);
let (local, _) = mgr.get_position("room").unwrap();
let mut streams = mgr.streams("room");
streams.sort_unstable();
let mut expected = vec![(local, 1), (7, 3)];
expected.sort_unstable();
assert_eq!(streams, expected);
}
#[test]
fn test_foreign_buffer_overflow() {
let config = RecoveryConfig {
buffer_size_bits: 2, ..RecoveryConfig::default()
};
let mgr = RecoveryManager::new(config);
mgr.interest_began("topic1");
let epoch: u32 = 50;
for i in 0u64..10 {
mgr.push_foreign("topic1", make_data(&format!("fm{i}")), epoch, i);
}
match mgr.recover("topic1", epoch, 4) {
RecoveryResult::NotRecovered { .. } => {}
_ => panic!("expected NotRecovered for gap too large"),
}
match mgr.recover("topic1", epoch, 5) {
RecoveryResult::Recovered { publications, .. } => {
assert_eq!(publications.len(), 4);
assert_eq!(&publications[0][..], b"fm6");
}
_ => panic!("expected Recovered at boundary"),
}
match mgr.recover("topic1", epoch, 7) {
RecoveryResult::Recovered { publications, .. } => {
assert_eq!(publications.len(), 2);
assert_eq!(&publications[0][..], b"fm8");
assert_eq!(&publications[1][..], b"fm9");
}
_ => panic!("expected Recovered"),
}
}
#[test]
fn foreign_offset_jump_is_bounded() {
let mgr = RecoveryManager::new(RecoveryConfig::default());
mgr.interest_began("t");
mgr.push_foreign("t", make_data("a"), 7, 0);
let started = Instant::now();
mgr.push_foreign("t", make_data("b"), 7, 1u64 << 62);
assert!(started.elapsed() < Duration::from_secs(1));
match mgr.recover("t", 7, (1u64 << 62) - 1) {
RecoveryResult::Recovered { publications, .. } => {
assert_eq!(publications.len(), 1);
assert_eq!(&publications[0][..], b"b");
}
_ => panic!("expected Recovered"),
}
assert!(matches!(
mgr.recover("t", 7, 0),
RecoveryResult::NotRecovered { .. }
));
}
#[test]
fn local_buffer_memory_grows_with_use() {
let cfg = RecoveryConfig {
buffer_size_bits: 16, ..RecoveryConfig::default()
};
let mgr = RecoveryManager::new(cfg);
mgr.push("room:1", make_data("hello"));
assert!(
mgr.total_bytes() < 4096,
"charged {} bytes",
mgr.total_bytes()
);
}
#[test]
fn budget_accounting_returns_to_zero() {
let cfg = RecoveryConfig {
history_ttl_secs: 0,
..RecoveryConfig::default()
};
let mgr = RecoveryManager::new(cfg);
for i in 0..200 {
mgr.push(&format!("topic-{}", i % 7), make_data("payload"));
mgr.push_foreign(&format!("f-{}", i % 5), make_data("payload"), 9, i);
}
assert!(mgr.total_bytes() > 0);
std::thread::sleep(Duration::from_millis(5));
mgr.cleanup();
assert_eq!(mgr.topic_count(), 0);
assert_eq!(mgr.foreign_buffer_count(), 0);
assert_eq!(mgr.total_bytes(), 0);
}
#[test]
fn ttl_longer_than_uptime_does_not_panic() {
let cfg = RecoveryConfig {
history_ttl_secs: u64::MAX / 4,
..RecoveryConfig::default()
};
let mgr = RecoveryManager::new(cfg);
mgr.push("t", make_data("x"));
mgr.cleanup();
assert_eq!(mgr.topic_count(), 1);
}
mod properties {
use super::*;
use proptest::prelude::*;
proptest! {
#![proptest_config(ProptestConfig::with_cases(1000))]
#[test]
fn recovery_returns_exactly_the_missing_suffix(
bits in 1u32..6,
pushed in 0usize..200,
after in 0u64..210,
max_messages in 1usize..300,
) {
let cfg = RecoveryConfig {
buffer_size_bits: bits,
max_recovery_messages: max_messages,
..RecoveryConfig::default()
};
let mgr = RecoveryManager::new(cfg);
for i in 0..pushed {
mgr.push("t", make_data(&format!("m{i}")));
}
let Some((epoch, head)) = mgr.get_position("t") else {
prop_assert_eq!(pushed, 0);
return Ok(());
};
prop_assert_eq!(head, pushed as u64);
let capacity = 1u64 << bits;
let tail = head.saturating_sub(capacity);
match mgr.recover("t", epoch, after) {
RecoveryResult::Recovered { publications, offset, .. } => {
let start = after + 1;
prop_assert!(start >= tail);
prop_assert_eq!(offset, head - 1);
let expected: Vec<String> =
(start..head).map(|o| format!("m{o}")).collect();
let got: Vec<String> = publications
.iter()
.map(|b| String::from_utf8(b.to_vec()).unwrap())
.collect();
prop_assert_eq!(got, expected);
}
RecoveryResult::NotRecovered { .. } => {
let missing = head.saturating_sub(after + 1);
prop_assert!(after + 1 < tail || missing > max_messages as u64);
}
RecoveryResult::NoHistory => prop_assert!(false, "history exists"),
}
}
}
}
}