use std::collections::HashMap;
use fv_value::Value;
use crate::acc::value_key;
use crate::watermark::Watermark;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Side {
Left,
Right,
}
type Buffered = (i64, Vec<(String, Value)>);
pub struct StreamJoin {
join_key: String,
window_ms: i64,
left: HashMap<String, Vec<Buffered>>,
right: HashMap<String, Vec<Buffered>>,
wm: Watermark,
late_dropped: u64,
}
impl StreamJoin {
pub fn new(join_key: impl Into<String>, window_ms: i64, allowed_lateness_ms: i64) -> Self {
assert!(window_ms >= 0, "join window must be ≥ 0");
Self {
join_key: join_key.into(),
window_ms,
left: HashMap::new(),
right: HashMap::new(),
wm: Watermark::new(allowed_lateness_ms),
late_dropped: 0,
}
}
pub fn with_idle_timeout(mut self, idle_timeout_ms: i64) -> Self {
self.wm = self.wm.with_idle_timeout(idle_timeout_ms);
self
}
pub fn expect_partitions(&mut self, partitions: &[i32], now_ms: i64) {
self.wm.expect(partitions, now_ms);
}
pub fn watermark(&self, now_ms: i64) -> i64 {
self.wm.current(now_ms)
}
pub fn late_dropped(&self) -> u64 {
self.late_dropped
}
pub fn push(
&mut self,
partition: i32,
side: Side,
event_ms: i64,
row: &[(String, Value)],
now_ms: i64,
) -> Vec<Vec<(String, Value)>> {
self.wm.observe(partition, event_ms);
let Some(key) = row
.iter()
.find(|(k, _)| k == &self.join_key)
.map(|(_, v)| value_key(Some(v)))
else {
return Vec::new(); };
let wm = self.watermark(now_ms);
if wm != i64::MIN && event_ms + self.window_ms < wm {
self.late_dropped += 1;
return Vec::new();
}
let (mine, theirs) = match side {
Side::Left => (&mut self.left, &self.right),
Side::Right => (&mut self.right, &self.left),
};
let mut out = Vec::new();
if let Some(partners) = theirs.get(&key) {
for (their_ts, their_row) in partners {
if (event_ms - their_ts).abs() <= self.window_ms {
out.push(match side {
Side::Left => merge(row, their_row), Side::Right => merge(their_row, row), });
}
}
}
mine.entry(key).or_default().push((event_ms, row.to_vec()));
out
}
pub fn evict(&mut self, now_ms: i64) {
self.wm.tick(now_ms);
let wm = self.wm.current(now_ms);
if wm == i64::MIN {
return;
}
let horizon = wm - self.window_ms;
for buf in [&mut self.left, &mut self.right] {
buf.retain(|_, rows| {
rows.retain(|(ts, _)| *ts >= horizon);
!rows.is_empty()
});
}
}
fn cfg_fingerprint(&self) -> String {
format!(
"join_key={};window={};{}",
self.join_key,
self.window_ms,
self.wm.cfg_fingerprint()
)
}
pub fn snapshot(&self) -> Vec<u8> {
use serde_json::json;
let side = |m: &HashMap<String, Vec<Buffered>>| -> Vec<serde_json::Value> {
m.iter()
.map(|(k, rows)| {
let r: Vec<serde_json::Value> = rows
.iter()
.map(|(ts, row)| json!([ts, crate::snapshot::row_to_json(row)]))
.collect();
json!([k, r])
})
.collect()
};
crate::snapshot::envelope(
"join",
&self.cfg_fingerprint(),
json!({
"left": side(&self.left),
"right": side(&self.right),
"wm": self.wm.state_to_json(),
"late_dropped": self.late_dropped,
}),
)
}
pub fn load_snapshot(&mut self, bytes: &[u8]) -> Result<(), String> {
let s = crate::snapshot::open_envelope("join", &self.cfg_fingerprint(), bytes)?;
let side = |j: &serde_json::Value, name: &str| -> Result<HashMap<String, Vec<Buffered>>, String> {
let mut m = HashMap::new();
for e in j
.as_array()
.ok_or_else(|| format!("join snapshot: {name} not an array"))?
{
let a = e
.as_array()
.filter(|a| a.len() == 2)
.ok_or("join snapshot: bad side entry")?;
let key = a[0].as_str().ok_or("join snapshot: bad key")?.to_string();
let rows: Vec<Buffered> = a[1]
.as_array()
.ok_or("join snapshot: bad rows")?
.iter()
.map(|re| {
let t = re
.as_array()
.filter(|t| t.len() == 2)
.ok_or("join snapshot: bad buffered row")?;
Ok((
t[0].as_i64().ok_or("join snapshot: bad ts")?,
crate::snapshot::row_from_json(&t[1])?,
))
})
.collect::<Result<_, String>>()?;
m.insert(key, rows);
}
Ok(m)
};
self.left = side(&s["left"], "left")?;
self.right = side(&s["right"], "right")?;
self.wm.load_state(&s["wm"])?;
self.late_dropped = s["late_dropped"]
.as_u64()
.ok_or("join snapshot: missing late_dropped")?;
Ok(())
}
}
fn merge(left: &[(String, Value)], right: &[(String, Value)]) -> Vec<(String, Value)> {
let mut out: Vec<(String, Value)> = left.to_vec();
for (k, v) in right {
if !left.iter().any(|(lk, _)| lk == k) {
out.push((k.clone(), v.clone()));
}
}
out
}
#[cfg(test)]
mod tests {
use super::*;
fn row(pairs: &[(&str, Value)]) -> Vec<(String, Value)> {
pairs.iter().map(|(k, v)| (k.to_string(), v.clone())).collect()
}
fn s(v: &str) -> Value {
Value::Str(v.into())
}
fn get<'a>(r: &'a [(String, Value)], k: &str) -> Option<&'a Value> {
r.iter().find(|(kk, _)| kk == k).map(|(_, v)| v)
}
#[test]
fn equi_join_within_window_both_directions() {
let mut j = StreamJoin::new("pid", 1000, 0);
assert!(
j.push(0, Side::Left, 100, &row(&[("pid", s("p1")), ("auction", s("a1"))]), 0)
.is_empty(),
"no right yet"
);
let out = j.push(0, Side::Right, 500, &row(&[("pid", s("p1")), ("name", s("Ann"))]), 0);
assert_eq!(out.len(), 1, "right joins the buffered left");
assert_eq!(get(&out[0], "auction"), Some(&s("a1")));
assert_eq!(get(&out[0], "name"), Some(&s("Ann")));
let out2 = j.push(0, Side::Left, 900, &row(&[("pid", s("p1")), ("auction", s("a2"))]), 0);
assert_eq!(out2.len(), 1);
assert_eq!(get(&out2[0], "auction"), Some(&s("a2")));
assert_eq!(get(&out2[0], "name"), Some(&s("Ann")));
}
#[test]
fn different_keys_do_not_join() {
let mut j = StreamJoin::new("pid", 1000, 0);
j.push(0, Side::Left, 100, &row(&[("pid", s("p1")), ("auction", s("a1"))]), 0);
assert!(j
.push(0, Side::Right, 200, &row(&[("pid", s("p2")), ("name", s("Bob"))]), 0)
.is_empty());
}
#[test]
fn outside_the_window_does_not_join() {
let mut j = StreamJoin::new("pid", 1000, 0);
j.push(0, Side::Left, 100, &row(&[("pid", s("p1")), ("auction", s("a1"))]), 0);
assert!(j
.push(0, Side::Right, 2000, &row(&[("pid", s("p1")), ("name", s("Ann"))]), 0)
.is_empty());
}
#[test]
fn one_left_joins_many_rights_in_window() {
let mut j = StreamJoin::new("pid", 1000, 0);
j.push(0, Side::Right, 100, &row(&[("pid", s("p1")), ("name", s("A"))]), 0);
j.push(0, Side::Right, 200, &row(&[("pid", s("p1")), ("name", s("B"))]), 0);
let out = j.push(0, Side::Left, 300, &row(&[("pid", s("p1")), ("auction", s("a1"))]), 0);
assert_eq!(out.len(), 2, "the left joins both buffered rights");
}
#[test]
fn eviction_bounds_state_and_drops_unjoinable_late_rows() {
let mut j = StreamJoin::new("pid", 1000, 0);
j.push(0, Side::Left, 100, &row(&[("pid", s("p1")), ("auction", s("a1"))]), 0);
j.push(0, Side::Right, 10_000, &row(&[("pid", s("p2")), ("name", s("Z"))]), 0);
j.evict(0); assert!(j
.push(0, Side::Right, 10_050, &row(&[("pid", s("p1")), ("name", s("Ann"))]), 0)
.is_empty());
}
#[test]
fn multi_partition_watermark_is_the_min() {
let mut j = StreamJoin::new("pid", 1000, 0);
j.expect_partitions(&[0, 1], 0);
j.push(0, Side::Left, 5000, &row(&[("pid", s("p1"))]), 0); assert_eq!(j.watermark(0), i64::MIN, "partition 1 unseen → watermark pinned");
j.push(1, Side::Right, 100, &row(&[("pid", s("p2"))]), 0);
assert_eq!(j.watermark(0), 100, "min across partitions = 100");
}
#[test]
fn snapshot_restore_joins_identically_to_the_uninterrupted_run() {
let mk = || {
let mut j = StreamJoin::new("pid", 1000, 0);
j.expect_partitions(&[0], 0);
j.push(0, Side::Left, 100, &row(&[("pid", s("p1")), ("auction", s("a1"))]), 0);
j.push(0, Side::Left, 300, &row(&[("pid", s("p2")), ("auction", s("a2"))]), 0);
j
};
let drive = |j: &mut StreamJoin| {
let mut out = j.push(0, Side::Right, 500, &row(&[("pid", s("p1")), ("name", s("Ann"))]), 0);
out.extend(j.push(0, Side::Right, 700, &row(&[("pid", s("p2")), ("name", s("Bob"))]), 0));
out
};
let mut a = mk();
let out_a = drive(&mut a);
let snap = mk().snapshot();
let mut b = StreamJoin::new("pid", 1000, 0);
b.load_snapshot(&snap).expect("restore");
let out_b = drive(&mut b);
assert_eq!(out_a, out_b, "restored joins byte-identical");
assert_eq!(out_b.len(), 2, "both restored buffered lefts joined");
for j in [&mut a, &mut b] {
j.push(0, Side::Left, 10_000, &row(&[("pid", s("p9"))]), 0);
j.evict(0);
assert!(
j.push(0, Side::Right, 10_050, &row(&[("pid", s("p1")), ("name", s("Z"))]), 0)
.is_empty(),
"old left evicted on both sides of the crash"
);
}
let mut other = StreamJoin::new("pid", 2000, 0);
assert!(other.load_snapshot(&snap).unwrap_err().contains("config changed"));
}
#[test]
fn bounded_idleness_lets_eviction_advance_past_a_silent_partition() {
let build = |idle_ms: i64| {
let mut j = StreamJoin::new("pid", 1000, 0);
if idle_ms > 0 {
j = j.with_idle_timeout(idle_ms);
}
j.expect_partitions(&[0, 1], 0);
j.push(0, Side::Left, 100, &row(&[("pid", s("p1")), ("auction", s("a1"))]), 0);
j.push(1, Side::Right, 200, &row(&[("pid", s("p2")), ("name", s("Z"))]), 0); j.evict(0); j.push(0, Side::Left, 10_000, &row(&[("pid", s("p3"))]), 5000); j.evict(5000);
j
};
let mut no_idle = build(0);
assert!(
!no_idle
.push(0, Side::Right, 150, &row(&[("pid", s("p1")), ("name", s("Ann"))]), 5000)
.is_empty(),
"no idle timeout → stale left row still buffered and joins"
);
let mut idle = build(1000);
assert!(
idle.push(
0,
Side::Right,
10_050,
&row(&[("pid", s("p1")), ("name", s("Ann"))]),
5000
)
.is_empty(),
"idle partition released eviction → stale left row evicted, nothing to join"
);
}
}