fv-streams-ops 0.2.0

Stateful streaming operators for FusionVault Streams: event-time tumbling and sliding windows with keyed incremental aggregation, session windows, stream joins, top-N and last-N, watermarks and snapshots. Pure and synchronous — no I/O, no runtime.
Documentation
//! Stream-stream INTERVAL JOIN — the stateful operator behind Nexmark Q3.
//!
//! Two event-time streams (`left`, `right`) equi-joined on a key: a left row `L` joins every buffered
//! right row `R` with the same key whose event time is within `|L.ts − R.ts| ≤ window` (and
//! symmetrically). Both sides are buffered in keyed state; the watermark (min across partitions, minus
//! lateness — the same rule the windowed aggregator uses) drives **eviction** so state stays bounded:
//! a buffered row that can no longer be joined by any future row (its `ts + window < watermark`) is
//! dropped. Pure + synchronous, so it unit-tests in isolation; the two-input stream worker
//! feeds it `push(side, …)` per row and `evict()` after each batch.
//!
//! Correctness (like the windowed operator) needs both sides **co-partitioned by the join key** so all
//! of a key's rows from both streams land on one consumer; a keyBy shuffle lifts that later.

use std::collections::HashMap;

use fv_value::Value;

use crate::acc::value_key;
use crate::watermark::Watermark;

/// Which input stream a row came from.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Side {
    Left,
    Right,
}

/// A buffered row: its event time and columns.
type Buffered = (i64, Vec<(String, Value)>);

/// An event-time interval equi-join. Feed rows with [`push`](Self::push) (which returns the joins that
/// row produces against the opposite side); call [`evict`](Self::evict) after each batch to bound state.
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 {
    /// Join on `join_key` (present in both streams) within `±window_ms` of event time. `window_ms` ≥ 0.
    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,
        }
    }

    /// Enable bounded idleness: a partition silent longer than `idle_timeout_ms` (processing time)
    /// stops holding the watermark back. `<= 0` leaves it disabled. See `Watermark`.
    pub fn with_idle_timeout(mut self, idle_timeout_ms: i64) -> Self {
        self.wm = self.wm.with_idle_timeout(idle_timeout_ms);
        self
    }

    /// Register the partitions this operator reads at processing time `now_ms` so the watermark holds
    /// until each has reported (see `Watermark::expect`).
    pub fn expect_partitions(&mut self, partitions: &[i32], now_ms: i64) {
        self.wm.expect(partitions, now_ms);
    }

    /// Watermark at processing time `now_ms` (min across ACTIVE partitions − lateness); `i64::MIN` until
    /// every seen/assigned partition has an event, or when all are idle. See `Watermark`.
    pub fn watermark(&self, now_ms: i64) -> i64 {
        self.wm.current(now_ms)
    }

    pub fn late_dropped(&self) -> u64 {
        self.late_dropped
    }

    /// Push one row from `side` at `event_ms`. Returns every joined row it produces against the
    /// opposite side's current buffer (each output is left-columns then right-columns, regardless of
    /// which side arrived), and buffers this row for future partners. A row whose partners are all
    /// already past the eviction horizon (`ts + window < watermark`) is dropped and counted.
    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(); // no join key → cannot join
        };

        // Too old to ever be joined by a future row AND its past partners are gone → drop. Uses the
        // watermark as of the last `evict` tick (one batch stale — fine for a late-drop heuristic).
        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),  // this=left, partner=right
                        Side::Right => merge(their_row, row), // partner=left, this=right
                    });
                }
            }
        }
        mine.entry(key).or_default().push((event_ms, row.to_vec()));
        out
    }

    /// Drop buffered rows that can no longer join any future row (`ts + window < watermark`), keeping
    /// state bounded to roughly one window behind the watermark. `now_ms` advances the bounded-idleness
    /// timers (so a silent partition stops holding eviction back). Call once per batch.
    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()
            });
        }
    }

    // ── snapshot/restore (see `snapshot` module). ──

    fn cfg_fingerprint(&self) -> String {
        format!(
            "join_key={};window={};{}",
            self.join_key,
            self.window_ms,
            self.wm.cfg_fingerprint()
        )
    }

    /// Serialize the DYNAMIC state: both buffered sides, watermark timers, late count.
    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,
            }),
        )
    }

    /// Restore dynamic state into this freshly-configured join (config mismatch refused).
    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(())
    }
}

/// Merge a left row with a right row: all of left, then right's columns not already present (so the
/// join key isn't duplicated). Output column order is stable (left then right).
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() {
        // Left (auction) arrives, then right (person) with the same id within the window → one join.
        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")));
        // And a later left for the same id joins the buffered right.
        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);
        // right at ts 2000 → |2000-100| = 1900 > 1000 → no join.
        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);
        // A far-future event advances the watermark well past the buffered left's join range.
        j.push(0, Side::Right, 10_000, &row(&[("pid", s("p2")), ("name", s("Z"))]), 0);
        j.evict(0); // horizon = 10000 - 1000 = 9000 → the ts-100 left row is evicted.
                    // A right for p1 now finds nothing buffered (the old left is gone).
        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); // partition 0 races ahead
        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() {
        // Buffered-but-unjoined rows are exactly what a crash would lose — snapshot carries them, and
        // rights arriving after restore must join them just as they would have uninterrupted.
        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");
        // Eviction after restore behaves identically too (watermark state preserved).
        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"
            );
        }
        // A join snapshot refuses a re-configured join.
        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() {
        // Partition 1 goes silent after one event; partition 0 advances far. Without an idle timeout the
        // watermark is pinned at partition 1's stale max, so nothing evicts and a stale left row still
        // joins. With one, partition 1 goes idle, eviction advances, and the stale left row is gone.
        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); // partition 1's only event
            j.evict(0); // stamp both active at processing-time 0
            j.push(0, Side::Left, 10_000, &row(&[("pid", s("p3"))]), 5000); // partition 0 advances; partition 1 silent
            j.evict(5000);
            j
        };
        // Without idleness: wm pinned at 200 → the ts-100 p1 left row is still buffered → a p1 right joins.
        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"
        );
        // With idleness: partition 1 idle → eviction advanced to ~10000, horizon 9000 → the p1 left is gone.
        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"
        );
    }
}