use std::collections::HashMap;
use std::sync::Arc;
use arrow::array::{Array, ArrayRef, BooleanArray, Int64Array, RecordBatch, UInt32Array};
use arrow::compute::{filter_record_batch, interleave, is_not_null, take};
use arrow::datatypes::{DataType, Field, Schema, SchemaRef};
use arrow::ipc::reader::StreamReader;
use arrow::ipc::writer::StreamWriter;
use arrow::row::{RowConverter, SortField};
use crate::watermark::Watermark;
use crate::Side;
pub const SNAPSHOT_VERSION: i64 = 3;
const TS: &str = "__fv_ts";
fn append_ts(batch: &RecordBatch, times: &[i64]) -> RecordBatch {
let mut fields: Vec<Field> = batch.schema().fields().iter().map(|f| f.as_ref().clone()).collect();
fields.push(Field::new(TS, DataType::Int64, false));
let mut cols = batch.columns().to_vec();
cols.push(Arc::new(Int64Array::from(times.to_vec())));
RecordBatch::try_new(Arc::new(Schema::new(fields)), cols).expect("append ts")
}
fn split_ts(batch: &RecordBatch) -> (RecordBatch, Vec<i64>) {
let ts_idx = batch.schema().index_of(TS).expect("frozen file carries its times");
let times = batch
.column(ts_idx)
.as_any()
.downcast_ref::<Int64Array>()
.expect("ts i64")
.values()
.to_vec();
let data_idx: Vec<usize> = (0..batch.num_columns()).filter(|i| *i != ts_idx).collect();
(batch.project(&data_idx).expect("project data off ts"), times)
}
enum Slot {
Hot(RecordBatch),
Frozen(std::path::PathBuf),
}
struct Stored {
slot: Slot,
times: Vec<i64>,
keys: Vec<Vec<u8>>,
bytes: usize,
charged: bool,
}
#[derive(Default)]
struct SideBuf {
stored: Vec<Stored>,
index: HashMap<Vec<u8>, Vec<(u32, u32)>>,
schema: Option<SchemaRef>,
}
impl SideBuf {
fn rows(&self) -> usize {
self.stored.iter().map(|s| s.times.len()).sum()
}
fn rebuild_index(&mut self) {
self.index.clear();
for (si, s) in self.stored.iter().enumerate() {
for (ri, k) in s.keys.iter().enumerate() {
self.index.entry(k.clone()).or_default().push((si as u32, ri as u32));
}
}
}
}
struct Spill {
dir: std::path::PathBuf,
reservation: datafusion::execution::memory_pool::MemoryReservation,
cache: Vec<(std::path::PathBuf, RecordBatch)>,
cache_cap: usize,
seq: u64,
pub frozen_batches: u64,
}
impl Spill {
fn read(&mut self, path: &std::path::Path) -> RecordBatch {
if let Some(pos) = self.cache.iter().position(|(p, _)| p == path) {
return self.cache[pos].1.clone();
}
let full = Self::read_file(path);
let b = if full.schema().index_of(TS).is_ok() {
split_ts(&full).0
} else {
full
};
if self.cache.len() >= self.cache_cap {
self.cache.remove(0);
}
self.cache.push((path.to_path_buf(), b.clone()));
b
}
fn read_file(path: &std::path::Path) -> RecordBatch {
let f = std::fs::File::open(path).expect("frozen batch file");
let mut r = StreamReader::try_new(std::io::BufReader::new(f), None).expect("frozen batch stream");
r.next().expect("frozen batch").expect("frozen batch decodes")
}
fn read_with_times(path: &std::path::Path) -> (RecordBatch, Vec<i64>) {
split_ts(&Self::read_file(path))
}
fn forget(&mut self, path: &std::path::Path) {
self.cache.retain(|(p, _)| p != path);
let _ = std::fs::remove_file(path);
}
}
pub struct StreamJoinBatch {
join_key: String,
window_ms: i64,
left: SideBuf,
right: SideBuf,
wm: Watermark,
delivered: Option<i64>,
in_band: bool,
late_dropped: u64,
horizon: i64,
spill: Option<Spill>,
}
#[derive(Clone, Debug)]
pub struct FrozenFile {
pub name: String,
pub path: std::path::PathBuf,
pub min_time: i64,
pub max_time: i64,
}
impl StreamJoinBatch {
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");
StreamJoinBatch {
join_key: join_key.into(),
window_ms,
left: SideBuf::default(),
right: SideBuf::default(),
wm: Watermark::new(allowed_lateness_ms),
delivered: None,
in_band: false,
late_dropped: 0,
horizon: i64::MIN,
spill: None,
}
}
pub fn set_watermark(&mut self, watermark_ms: i64) {
self.delivered = Some(self.delivered.map_or(watermark_ms, |d| d.max(watermark_ms)));
}
pub fn with_in_band_time(mut self) -> Self {
self.in_band = true;
self
}
fn time(&self, now_ms: i64) -> i64 {
if self.in_band {
self.delivered.map_or(i64::MIN, |d| self.wm.after_lateness(d))
} else {
self.wm.current(now_ms)
}
}
pub fn with_spill(
mut self,
dir: &std::path::Path,
pool: &Arc<dyn datafusion::execution::memory_pool::MemoryPool>,
cache_batches: usize,
) -> Self {
std::fs::create_dir_all(dir).expect("state dir");
let reservation = datafusion::execution::memory_pool::MemoryConsumer::new("stream-join").register(pool);
self.spill = Some(Spill {
dir: dir.to_path_buf(),
reservation,
cache: Vec::new(),
cache_cap: cache_batches.max(1),
seq: 0,
frozen_batches: 0,
});
self
}
pub fn frozen_batches(&self) -> u64 {
self.spill.as_ref().map(|s| s.frozen_batches).unwrap_or(0)
}
pub fn hot_bytes(&self) -> usize {
self.spill
.as_ref()
.map(|s| s.reservation.size())
.unwrap_or_else(|| self.state_bytes())
}
fn charge(&mut self, is_left: bool, idx: usize) {
let Some(spill) = self.spill.as_mut() else { return };
let bytes = if is_left { &self.left } else { &self.right }.stored[idx].bytes;
while spill.reservation.try_grow(bytes).is_err() {
let mut coldest: Option<(bool, usize, i64)> = None;
for (l, side) in [(true, &self.left), (false, &self.right)] {
for (i, s) in side.stored.iter().enumerate() {
if let Slot::Hot(_) = s.slot {
let t = s.times.iter().copied().min().unwrap_or(i64::MAX);
if coldest.is_none_or(|(_, _, ct)| t < ct) {
coldest = Some((l, i, t));
}
}
}
}
let Some((l, i, _)) = coldest else {
spill.reservation.grow(bytes);
break;
};
let side = if l { &mut self.left } else { &mut self.right };
let s = &mut side.stored[i];
let Slot::Hot(b) = &s.slot else { unreachable!() };
spill.seq += 1;
let path = spill.dir.join(format!("join-{}.arrow", spill.seq));
let framed = append_ts(b, &s.times);
let f = std::fs::File::create(&path).expect("freeze file");
let mut w = StreamWriter::try_new(std::io::BufWriter::new(f), &framed.schema()).expect("freeze writer");
w.write(&framed).expect("freeze write");
w.finish().expect("freeze finish");
if s.charged {
spill.reservation.shrink(s.bytes);
s.charged = false;
}
spill.frozen_batches += 1;
s.slot = Slot::Frozen(path);
if l == is_left && i == idx {
return;
}
}
if is_left { &mut self.left } else { &mut self.right }.stored[idx].charged = true;
}
fn slot_batch(spill: &mut Option<Spill>, s: &Stored) -> RecordBatch {
match &s.slot {
Slot::Hot(b) => b.clone(),
Slot::Frozen(path) => spill.as_mut().expect("frozen without a spill tier").read(path),
}
}
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.time(now_ms)
}
pub fn late_dropped(&self) -> u64 {
self.late_dropped
}
pub fn buffered_rows(&self) -> (usize, usize) {
(self.left.rows(), self.right.rows())
}
pub fn state_bytes(&self) -> usize {
[&self.left, &self.right]
.iter()
.flat_map(|s| s.stored.iter())
.filter(|s| matches!(s.slot, Slot::Hot(_)))
.map(|s| s.bytes)
.sum()
}
fn cfg_fingerprint(&self) -> String {
format!(
"v3;join_key={};window={};{}",
self.join_key,
self.window_ms,
self.wm.cfg_fingerprint()
)
}
fn key_bytes(&self, batch: &RecordBatch) -> Vec<Option<Vec<u8>>> {
let n = batch.num_rows();
let Some(col) = batch.column_by_name(&self.join_key) else {
return vec![None; n];
};
let canonical: DataType = match col.data_type() {
DataType::Boolean => DataType::Boolean,
t if t.is_numeric() => DataType::Float64,
_ => DataType::Utf8,
};
let col = if col.data_type() == &canonical {
Arc::clone(col)
} else {
match arrow::compute::cast(col, &canonical) {
Ok(c) => c,
Err(_) => return vec![None; n],
}
};
let conv = RowConverter::new(vec![SortField::new(canonical)]).expect("converter");
let rows = conv.convert_columns(std::slice::from_ref(&col)).expect("convert");
(0..n)
.map(|i| {
if col.is_null(i) {
None
} else {
Some(rows.row(i).as_ref().to_vec())
}
})
.collect()
}
pub fn push_batch(
&mut self,
partition: i32,
side: Side,
batch: &RecordBatch,
event_ms: &[i64],
now_ms: i64,
) -> Option<RecordBatch> {
if batch.num_rows() == 0 {
return None;
}
let keys = self.key_bytes(batch);
let live: Vec<bool> = event_ms
.iter()
.map(|&t| {
self.wm.observe(partition, t);
let wm = self.time(now_ms);
!(wm != i64::MIN && t + self.window_ms < wm)
})
.collect();
let late = live.iter().filter(|l| !**l).count();
self.late_dropped += late as u64;
let (batch, event_ms, keys): (RecordBatch, Vec<i64>, Vec<Option<Vec<u8>>>) = if late > 0 {
let mask = BooleanArray::from(live.clone());
let b = filter_record_batch(batch, &mask).expect("filter");
let t = event_ms
.iter()
.zip(&live)
.filter(|(_, l)| **l)
.map(|(t, _)| *t)
.collect();
let k = keys
.into_iter()
.zip(&live)
.filter(|(_, l)| **l)
.map(|(k, _)| k)
.collect();
(b, t, k)
} else {
(batch.clone(), event_ms.to_vec(), keys)
};
if batch.num_rows() == 0 {
return None;
}
let (mine, theirs) = match side {
Side::Left => (&mut self.left, &self.right),
Side::Right => (&mut self.right, &self.left),
};
if mine.schema.is_none() {
mine.schema = Some(batch.schema());
}
let mut my_idx: Vec<u32> = Vec::new();
let mut their_idx: Vec<(usize, usize)> = Vec::new();
for (i, k) in keys.iter().enumerate() {
let Some(k) = k else { continue };
let Some(positions) = theirs.index.get(k) else { continue };
let t = event_ms[i];
for &(si, ri) in positions {
let ts = theirs.stored[si as usize].times[ri as usize];
if (t - ts).abs() <= self.window_ms && ts >= self.horizon {
my_idx.push(i as u32);
their_idx.push((si as usize, ri as usize));
}
}
}
let si = mine.stored.len() as u32;
for (ri, k) in keys.iter().enumerate() {
if let Some(k) = k {
mine.index.entry(k.clone()).or_default().push((si, ri as u32));
}
}
let bytes = batch.get_array_memory_size()
+ event_ms.len() * 8
+ keys
.iter()
.map(|k| k.as_ref().map(|k| k.len()).unwrap_or(0))
.sum::<usize>();
mine.stored.push(Stored {
slot: Slot::Hot(batch.clone()),
times: event_ms,
keys: keys.into_iter().map(|k| k.unwrap_or_default()).collect(),
bytes,
charged: false,
});
self.charge(matches!(side, Side::Left), si as usize);
if my_idx.is_empty() {
return None;
}
let my_cols: Vec<ArrayRef> = batch
.columns()
.iter()
.map(|c| take(c.as_ref(), &UInt32Array::from(my_idx.clone()), None).expect("take"))
.collect();
let theirs = match side {
Side::Left => &self.right,
Side::Right => &self.left,
};
let their_schema = Arc::clone(theirs.schema.as_ref().expect("partners exist"));
let mut used: Vec<usize> = their_idx.iter().map(|(si, _)| *si).collect();
used.sort_unstable();
used.dedup();
let mut materialised: Vec<RecordBatch> = Vec::with_capacity(used.len());
for si in &used {
let b = Self::slot_batch(&mut self.spill, &theirs.stored[*si]);
materialised.push(b);
}
let remap: HashMap<usize, usize> = used.iter().enumerate().map(|(pos, si)| (*si, pos)).collect();
let compact_idx: Vec<(usize, usize)> = their_idx.iter().map(|(si, ri)| (remap[si], *ri)).collect();
let their_cols: Vec<ArrayRef> = (0..their_schema.fields().len())
.map(|c| {
let arrays: Vec<&dyn Array> = materialised.iter().map(|b| b.column(c).as_ref()).collect();
interleave(&arrays, &compact_idx).expect("interleave")
})
.collect();
let their_schema = &their_schema;
let (left_schema, left_cols, right_schema, right_cols) = match side {
Side::Left => (batch.schema(), my_cols, Arc::clone(their_schema), their_cols),
Side::Right => (Arc::clone(their_schema), their_cols, batch.schema(), my_cols),
};
Some(merge_columns(&left_schema, left_cols, &right_schema, right_cols))
}
pub fn evict(&mut self, now_ms: i64) {
self.wm.tick(now_ms);
let wm = self.time(now_ms);
if wm == i64::MIN {
return;
}
let horizon = wm - self.window_ms;
self.horizon = horizon;
let spill = &mut self.spill;
for side in [&mut self.left, &mut self.right] {
let mut changed = false;
let mut kept: Vec<Stored> = Vec::with_capacity(side.stored.len());
for s in side.stored.drain(..) {
if s.times.iter().all(|t| *t >= horizon) {
kept.push(s);
continue;
}
changed = true;
let live: Vec<bool> = s.times.iter().map(|t| *t >= horizon).collect();
let any_live = live.iter().any(|l| *l);
match s.slot {
Slot::Frozen(ref path) => {
if any_live {
kept.push(s);
} else if let Some(sp) = spill.as_mut() {
sp.forget(path);
}
continue;
}
Slot::Hot(ref b) => {
if let (Some(sp), true) = (spill.as_mut(), s.charged) {
sp.reservation.shrink(s.bytes);
}
if !any_live {
continue;
}
let mask = BooleanArray::from(live.clone());
let batch = filter_record_batch(b, &mask).expect("filter");
let times: Vec<i64> = s
.times
.iter()
.zip(&live)
.filter(|(_, l)| **l)
.map(|(t, _)| *t)
.collect();
let keys: Vec<Vec<u8>> = s
.keys
.into_iter()
.zip(&live)
.filter(|(_, l)| **l)
.map(|(k, _)| k)
.collect();
let bytes = batch.get_array_memory_size()
+ times.len() * 8
+ keys.iter().map(|k| k.len()).sum::<usize>();
if let Some(sp) = spill.as_mut() {
sp.reservation.grow(bytes);
}
kept.push(Stored {
slot: Slot::Hot(batch),
times,
keys,
bytes,
charged: spill.is_some(),
});
}
}
}
side.stored = kept;
if changed {
side.rebuild_index();
}
}
}
pub fn snapshot(&self) -> Vec<u8> {
let mut bytes = Vec::new();
let frame = |bytes: &mut Vec<u8>, stream: Vec<u8>| {
bytes.extend_from_slice(&(stream.len() as u32).to_le_bytes());
bytes.extend_from_slice(&stream);
};
let header_schema = Arc::new(
Schema::empty().with_metadata(
[
("v".to_string(), SNAPSHOT_VERSION.to_string()),
("cfg".to_string(), self.cfg_fingerprint()),
("late_dropped".to_string(), self.late_dropped.to_string()),
("horizon".to_string(), self.horizon.to_string()),
("wm".to_string(), self.wm.state_to_json().to_string()),
("left".to_string(), self.left.stored.len().to_string()),
("right".to_string(), self.right.stored.len().to_string()),
]
.into_iter()
.collect(),
),
);
let mut hb = Vec::new();
let mut w = StreamWriter::try_new(&mut hb, &header_schema).expect("writer");
w.finish().expect("finish");
drop(w);
frame(&mut bytes, hb);
for side in [&self.left, &self.right] {
for s in &side.stored {
let batch = match &s.slot {
Slot::Hot(b) => b.clone(),
Slot::Frozen(path) => split_ts(&Spill::read_file(path)).0,
};
let mut fields: Vec<Field> = batch.schema().fields().iter().map(|f| f.as_ref().clone()).collect();
fields.push(Field::new(TS, DataType::Int64, false));
let mut cols = batch.columns().to_vec();
cols.push(Arc::new(Int64Array::from(s.times.clone())));
let schema = Arc::new(Schema::new(fields));
let b = RecordBatch::try_new(Arc::clone(&schema), cols).expect("stored batch");
let mut sb = Vec::new();
let mut w = StreamWriter::try_new(&mut sb, &schema).expect("writer");
w.write(&b).expect("write");
w.finish().expect("finish");
drop(w);
frame(&mut bytes, sb);
}
}
bytes
}
pub fn load_snapshot(&mut self, bytes: &[u8]) -> Result<(), String> {
let mut frames: Vec<&[u8]> = Vec::new();
let mut pos = 0usize;
while pos + 4 <= bytes.len() {
let len = u32::from_le_bytes(bytes[pos..pos + 4].try_into().map_err(|_| "snapshot: frame")?) as usize;
pos += 4;
if pos + len > bytes.len() {
return Err("snapshot: truncated frame".into());
}
frames.push(&bytes[pos..pos + len]);
pos += len;
}
let mut frames = frames.into_iter();
let hb = frames.next().ok_or("snapshot: empty")?;
let r = StreamReader::try_new(hb, None).map_err(|e| format!("snapshot: {e}"))?;
let md = r.schema().metadata().clone();
let v: i64 = md
.get("v")
.and_then(|s| s.parse().ok())
.ok_or("snapshot: missing version")?;
if v != SNAPSHOT_VERSION {
return Err(format!("snapshot: version {v} != supported {SNAPSHOT_VERSION}"));
}
if md.get("cfg").map(String::as_str) != Some(self.cfg_fingerprint().as_str()) {
return Err("snapshot: config mismatch (join key, window or lateness differ)".into());
}
self.late_dropped = md.get("late_dropped").and_then(|s| s.parse().ok()).unwrap_or(0);
self.horizon = md.get("horizon").and_then(|s| s.parse().ok()).unwrap_or(i64::MIN);
if let Some(w) = md.get("wm") {
let j: serde_json::Value = serde_json::from_str(w).map_err(|e| e.to_string())?;
self.wm.load_state(&j)?;
}
let n_left: usize = md.get("left").and_then(|s| s.parse().ok()).unwrap_or(0);
let n_right: usize = md.get("right").and_then(|s| s.parse().ok()).unwrap_or(0);
if let Some(sp) = self.spill.as_mut() {
for side in [&self.left, &self.right] {
for s in &side.stored {
if let Slot::Frozen(path) = &s.slot {
sp.forget(path);
}
}
}
let held = sp.reservation.size();
sp.reservation.shrink(held);
}
self.left = SideBuf::default();
self.right = SideBuf::default();
for (side, n) in [(Side::Left, n_left), (Side::Right, n_right)] {
for _ in 0..n {
let sb = frames.next().ok_or("snapshot: stored frame missing")?;
let mut r = StreamReader::try_new(sb, None).map_err(|e| format!("snapshot stored: {e}"))?;
let b = r
.next()
.ok_or("snapshot: stored batch missing")?
.map_err(|e| e.to_string())?;
let ts_idx = b.schema().index_of(TS).map_err(|e| e.to_string())?;
let times: Vec<i64> = b
.column(ts_idx)
.as_any()
.downcast_ref::<Int64Array>()
.ok_or("snapshot: times")?
.values()
.to_vec();
let data_idx: Vec<usize> = (0..b.num_columns()).filter(|i| *i != ts_idx).collect();
let batch = b.project(&data_idx).map_err(|e| e.to_string())?;
let keys: Vec<Vec<u8>> = self
.key_bytes(&batch)
.into_iter()
.map(|k| k.unwrap_or_default())
.collect();
let bytes = batch.get_array_memory_size()
+ times.len() * 8
+ keys.iter().map(|k: &Vec<u8>| k.len()).sum::<usize>();
let buf = match side {
Side::Left => &mut self.left,
Side::Right => &mut self.right,
};
if buf.schema.is_none() {
buf.schema = Some(batch.schema());
}
buf.stored.push(Stored {
slot: Slot::Hot(batch),
times,
keys,
bytes,
charged: false,
});
let idx = buf.stored.len() - 1;
self.charge(matches!(side, Side::Left), idx);
}
}
for buf in [&mut self.left, &mut self.right] {
buf.rebuild_index();
buf.index.remove(&Vec::new());
}
Ok(())
}
pub fn frozen_files(&self) -> Vec<FrozenFile> {
let mut out = Vec::new();
for side in [&self.left, &self.right] {
for s in &side.stored {
if let Slot::Frozen(path) = &s.slot {
let name = path
.file_name()
.map(|n| n.to_string_lossy().into_owned())
.unwrap_or_default();
let (min_time, max_time) = s
.times
.iter()
.fold((i64::MAX, i64::MIN), |(a, b), &t| (a.min(t), b.max(t)));
out.push(FrozenFile {
name,
path: path.clone(),
min_time,
max_time,
});
}
}
}
out
}
pub fn snapshot_head(&self) -> Vec<u8> {
let mut bytes = Vec::new();
let frame = |bytes: &mut Vec<u8>, stream: Vec<u8>| {
bytes.extend_from_slice(&(stream.len() as u32).to_le_bytes());
bytes.extend_from_slice(&stream);
};
let slot_list = |side: &SideBuf| {
side.stored
.iter()
.map(|s| match &s.slot {
Slot::Hot(_) => "H".to_string(),
Slot::Frozen(path) => format!(
"F:{}",
path.file_name()
.map(|n| n.to_string_lossy().into_owned())
.unwrap_or_default()
),
})
.collect::<Vec<_>>()
.join(",")
};
let header_schema = Arc::new(
Schema::empty().with_metadata(
[
("v".to_string(), SNAPSHOT_VERSION.to_string()),
("cfg".to_string(), self.cfg_fingerprint()),
("late_dropped".to_string(), self.late_dropped.to_string()),
("horizon".to_string(), self.horizon.to_string()),
("wm".to_string(), self.wm.state_to_json().to_string()),
("left_slots".to_string(), slot_list(&self.left)),
("right_slots".to_string(), slot_list(&self.right)),
]
.into_iter()
.collect(),
),
);
let mut hb = Vec::new();
{
let mut w = StreamWriter::try_new(&mut hb, &header_schema).expect("writer");
w.finish().expect("finish");
}
frame(&mut bytes, hb);
for side in [&self.left, &self.right] {
for s in &side.stored {
if let Slot::Hot(b) = &s.slot {
let framed = append_ts(b, &s.times);
let mut sb = Vec::new();
{
let mut w = StreamWriter::try_new(&mut sb, &framed.schema()).expect("writer");
w.write(&framed).expect("write");
w.finish().expect("finish");
}
frame(&mut bytes, sb);
}
}
}
bytes
}
pub fn restore_incremental(
&mut self,
head: &[u8],
files: &std::collections::HashMap<String, std::path::PathBuf>,
) -> Result<(), String> {
let mut frames: Vec<&[u8]> = Vec::new();
let mut pos = 0usize;
while pos + 4 <= head.len() {
let len = u32::from_le_bytes(head[pos..pos + 4].try_into().map_err(|_| "head: frame")?) as usize;
pos += 4;
if pos + len > head.len() {
return Err("head: truncated frame".into());
}
frames.push(&head[pos..pos + len]);
pos += len;
}
let mut frames = frames.into_iter();
let hb = frames.next().ok_or("head: empty")?;
let r = StreamReader::try_new(hb, None).map_err(|e| format!("head: {e}"))?;
let md = r.schema().metadata().clone();
let v: i64 = md
.get("v")
.and_then(|s| s.parse().ok())
.ok_or("head: missing version")?;
if v != SNAPSHOT_VERSION {
return Err(format!("head: version {v} != supported {SNAPSHOT_VERSION}"));
}
if md.get("cfg").map(String::as_str) != Some(self.cfg_fingerprint().as_str()) {
return Err("head: config mismatch (join key, window or lateness differ)".into());
}
self.late_dropped = md.get("late_dropped").and_then(|s| s.parse().ok()).unwrap_or(0);
self.horizon = md.get("horizon").and_then(|s| s.parse().ok()).unwrap_or(i64::MIN);
if let Some(w) = md.get("wm") {
let j: serde_json::Value = serde_json::from_str(w).map_err(|e| e.to_string())?;
self.wm.load_state(&j)?;
}
let parse_slots = |s: Option<&String>| -> Vec<String> {
match s {
Some(s) if !s.is_empty() => s.split(',').map(|x| x.to_string()).collect(),
_ => Vec::new(),
}
};
let left_slots = parse_slots(md.get("left_slots"));
let right_slots = parse_slots(md.get("right_slots"));
if let Some(sp) = self.spill.as_mut() {
for side in [&self.left, &self.right] {
for s in &side.stored {
if let Slot::Frozen(path) = &s.slot {
sp.forget(path);
}
}
}
let held = sp.reservation.size();
sp.reservation.shrink(held);
}
self.left = SideBuf::default();
self.right = SideBuf::default();
let seq_of = |name: &str| -> u64 {
name.strip_prefix("join-")
.and_then(|s| s.strip_suffix(".arrow"))
.and_then(|s| s.parse().ok())
.unwrap_or(0)
};
let max_seq = left_slots
.iter()
.chain(right_slots.iter())
.filter_map(|s| s.strip_prefix("F:").map(seq_of))
.max()
.unwrap_or(0);
if let Some(sp) = self.spill.as_mut() {
sp.seq = sp.seq.max(max_seq);
}
for (side, slots) in [(Side::Left, &left_slots), (Side::Right, &right_slots)] {
let is_left = matches!(side, Side::Left);
for slot in slots {
if slot == "H" {
let sb = frames.next().ok_or("head: hot frame missing")?;
let mut r = StreamReader::try_new(sb, None).map_err(|e| format!("head hot: {e}"))?;
let b = r.next().ok_or("head: hot batch missing")?.map_err(|e| e.to_string())?;
let (batch, times) = split_ts(&b);
self.push_restored(is_left, batch, times, None);
} else if let Some(name) = slot.strip_prefix("F:") {
let path = files
.get(name)
.ok_or_else(|| format!("restore: frozen file {name} not provided"))?;
let (batch, times) = Spill::read_with_times(path);
self.push_restored(is_left, batch, times, Some(path.clone()));
} else {
return Err(format!("head: bad slot tag {slot}"));
}
}
}
for buf in [&mut self.left, &mut self.right] {
buf.rebuild_index();
buf.index.remove(&Vec::new());
}
Ok(())
}
fn push_restored(
&mut self,
is_left: bool,
batch: RecordBatch,
times: Vec<i64>,
frozen: Option<std::path::PathBuf>,
) {
let keys: Vec<Vec<u8>> = self
.key_bytes(&batch)
.into_iter()
.map(|k| k.unwrap_or_default())
.collect();
let bytes =
batch.get_array_memory_size() + times.len() * 8 + keys.iter().map(|k: &Vec<u8>| k.len()).sum::<usize>();
let buf = if is_left { &mut self.left } else { &mut self.right };
if buf.schema.is_none() {
buf.schema = Some(batch.schema());
}
let slot = match &frozen {
Some(path) => Slot::Frozen(path.clone()),
None => Slot::Hot(batch),
};
buf.stored.push(Stored {
slot,
times,
keys,
bytes,
charged: false,
});
let idx = buf.stored.len() - 1;
if frozen.is_none() {
self.charge(is_left, idx);
}
}
}
fn merge_columns(
left: &SchemaRef,
left_cols: Vec<ArrayRef>,
right: &SchemaRef,
right_cols: Vec<ArrayRef>,
) -> RecordBatch {
let mut fields: Vec<Field> = Vec::with_capacity(left.fields().len() + right.fields().len());
let mut cols: Vec<ArrayRef> = Vec::with_capacity(fields.capacity());
for (i, f) in left.fields().iter().enumerate() {
let col = match right.index_of(f.name()) {
Ok(ri) if right.field(ri).data_type() == f.data_type() => {
let present = is_not_null(left_cols[i].as_ref()).expect("is_not_null");
arrow::compute::kernels::zip::zip(&present, &left_cols[i], &right_cols[ri]).expect("zip")
}
_ => Arc::clone(&left_cols[i]),
};
fields.push(f.as_ref().clone().with_nullable(true));
cols.push(col);
}
for (i, f) in right.fields().iter().enumerate() {
if left.index_of(f.name()).is_ok() {
continue;
}
fields.push(f.as_ref().clone().with_nullable(true));
cols.push(Arc::clone(&right_cols[i]));
}
RecordBatch::try_new(Arc::new(Schema::new(fields)), cols).expect("joined batch")
}
#[cfg(test)]
mod tests {
use super::*;
use arrow::array::{Float64Array, StringArray};
fn side(rows: &[(f64, &str, i64)]) -> (RecordBatch, Vec<i64>) {
let schema = Arc::new(Schema::new(vec![
Field::new("auction", DataType::Float64, true),
Field::new("v", DataType::Utf8, true),
]));
let a: Float64Array = rows.iter().map(|r| r.0).collect::<Vec<_>>().into();
let v: StringArray = rows.iter().map(|r| r.1).collect::<Vec<_>>().into();
(
RecordBatch::try_new(schema, vec![Arc::new(a), Arc::new(v)]).unwrap(),
rows.iter().map(|r| r.2).collect(),
)
}
fn strs(b: &RecordBatch, name: &str) -> Vec<Option<String>> {
let a = b.column_by_name(name).unwrap();
let a = a.as_any().downcast_ref::<StringArray>().unwrap();
(0..a.len())
.map(|i| {
if a.is_null(i) {
None
} else {
Some(a.value(i).to_string())
}
})
.collect()
}
#[test]
fn joins_within_the_window_in_both_directions_with_left_columns_first() {
let mut j = StreamJoinBatch::new("auction", 1000, 0);
j.expect_partitions(&[0, 1], 0);
let (l, lt) = side(&[(1.0, "L1", 100), (2.0, "L2", 200)]);
assert!(
j.push_batch(0, Side::Left, &l, <, 0).is_none(),
"nothing buffered yet"
);
let (r, rt) = side(&[(1.0, "R1", 500), (1.0, "R1b", 5000), (3.0, "R3", 300)]);
let out = j.push_batch(1, Side::Right, &r, &rt, 0).unwrap();
assert_eq!(out.num_rows(), 1);
assert_eq!(strs(&out, "v"), vec![Some("L1".into())]);
let (l2, l2t) = side(&[(1.0, "L1c", 900)]);
let out = j.push_batch(0, Side::Left, &l2, &l2t, 0).unwrap();
assert_eq!(out.num_rows(), 1);
assert_eq!(strs(&out, "v"), vec![Some("L1c".into())]);
assert_eq!(j.buffered_rows(), (3, 3));
}
#[test]
fn shared_columns_coalesce_left_then_right() {
let mut j = StreamJoinBatch::new("k", 10, 0);
let ls = Arc::new(Schema::new(vec![
Field::new("k", DataType::Float64, true),
Field::new("x", DataType::Utf8, true),
]));
let rs = Arc::new(Schema::new(vec![
Field::new("k", DataType::Float64, true),
Field::new("x", DataType::Utf8, true),
Field::new("y", DataType::Utf8, true),
]));
let l = RecordBatch::try_new(
ls,
vec![
Arc::new(Float64Array::from(vec![1.0, 2.0])),
Arc::new(StringArray::from(vec![Some("lx"), None])),
],
)
.unwrap();
let r = RecordBatch::try_new(
rs,
vec![
Arc::new(Float64Array::from(vec![1.0, 2.0])),
Arc::new(StringArray::from(vec!["rx1", "rx2"])),
Arc::new(StringArray::from(vec!["y1", "y2"])),
],
)
.unwrap();
j.push_batch(0, Side::Right, &r, &[1, 2], 0);
let out = j.push_batch(0, Side::Left, &l, &[1, 2], 0).unwrap();
let names: Vec<String> = out.schema().fields().iter().map(|f| f.name().clone()).collect();
assert_eq!(names, vec!["k", "x", "y"]);
assert_eq!(strs(&out, "x"), vec![Some("lx".into()), Some("rx2".into())]);
assert_eq!(strs(&out, "y"), vec![Some("y1".into()), Some("y2".into())]);
}
#[test]
fn eviction_and_late_rows_follow_the_row_operator() {
let mut j = StreamJoinBatch::new("auction", 100, 0);
j.expect_partitions(&[0], 0);
let (l, lt) = side(&[(1.0, "old", 100), (1.0, "new", 5000)]);
j.push_batch(0, Side::Left, &l, <, 0);
j.evict(0); assert_eq!(j.buffered_rows().0, 1);
let (r, rt) = side(&[(1.0, "late", 150)]);
assert!(j.push_batch(0, Side::Right, &r, &rt, 0).is_none());
assert_eq!(j.late_dropped(), 1);
let (r2, r2t) = side(&[(1.0, "ok", 4950)]);
assert_eq!(j.push_batch(0, Side::Right, &r2, &r2t, 0).unwrap().num_rows(), 1);
}
#[test]
fn in_band_time_lets_a_slow_side_keep_its_partners_and_still_bounds_the_state() {
let mut j = StreamJoinBatch::new("auction", 100, 0).with_in_band_time();
j.expect_partitions(&[0, 1], 0);
let (l, lt) = side(&[(1.0, "old", 100), (1.0, "new", 5000)]);
j.push_batch(0, Side::Left, &l, <, 0);
j.evict(0);
assert_eq!(j.buffered_rows().0, 2, "no watermark yet: nothing is evicted");
assert_eq!(j.watermark(0), i64::MIN);
j.set_watermark(120);
j.evict(0);
assert_eq!(j.buffered_rows().0, 2, "watermark 120: nothing is past the horizon");
let (r, rt) = side(&[(1.0, "partner", 150)]);
assert_eq!(
j.push_batch(1, Side::Right, &r, &rt, 0).unwrap().num_rows(),
1,
"150 joins the old 100: not late under the delivered time"
);
assert_eq!(j.late_dropped(), 0);
j.set_watermark(5000);
j.evict(0);
assert_eq!(
j.buffered_rows().0,
1,
"watermark 5000 → horizon 4900: the old row goes"
);
let (late, latet) = side(&[(1.0, "late", 150)]);
assert!(j.push_batch(1, Side::Right, &late, &latet, 0).is_none());
assert_eq!(j.late_dropped(), 1, "now genuinely late");
j.set_watermark(10);
assert_eq!(j.watermark(0), 5000, "a delivered watermark never moves backwards");
}
#[test]
fn a_pool_a_tenth_of_the_state_still_joins_exactly_and_bounds_memory() {
use datafusion::execution::memory_pool::{GreedyMemoryPool, MemoryPool};
let mk_side = |base: i64| -> Vec<(RecordBatch, Vec<i64>)> {
(0..200)
.map(|b| {
let rows: Vec<(f64, String, i64)> = (0..50)
.map(|i| ((b * 50 + i) as f64 % 997.0, format!("v{b}-{i}"), base + b * 100 + i))
.collect();
let a: Float64Array = rows.iter().map(|r| r.0).collect::<Vec<_>>().into();
let v: StringArray = rows.iter().map(|r| r.1.as_str()).collect::<Vec<_>>().into();
let schema = Arc::new(Schema::new(vec![
Field::new("auction", DataType::Float64, true),
Field::new("v", DataType::Utf8, true),
]));
(
RecordBatch::try_new(schema, vec![Arc::new(a), Arc::new(v)]).unwrap(),
rows.iter().map(|r| r.2).collect(),
)
})
.collect()
};
let left = mk_side(0);
let right = mk_side(10);
let one = left[0].0.get_array_memory_size() + 50 * 8 + 50 * 9;
let limit = one * 400 / 10;
let run = |pool: Option<Arc<dyn MemoryPool>>| -> (Vec<usize>, u64, usize) {
let dir = tempfile::tempdir().unwrap();
let mut j = StreamJoinBatch::new("auction", 1_000_000, 0);
if let Some(p) = &pool {
j = j.with_spill(dir.path(), p, 4);
}
j.expect_partitions(&[0, 1], 0);
let mut counts = Vec::new();
let mut peak = 0usize;
for i in 0..200 {
let (lb, lt) = &left[i];
let (rb, rt) = &right[i];
counts.push(
j.push_batch(0, Side::Left, lb, lt, 0)
.map(|b| b.num_rows())
.unwrap_or(0),
);
counts.push(
j.push_batch(1, Side::Right, rb, rt, 0)
.map(|b| b.num_rows())
.unwrap_or(0),
);
j.evict(0);
peak = peak.max(j.hot_bytes());
}
(counts, j.frozen_batches(), peak)
};
let (unbounded, _, _) = run(None);
let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(limit));
let (bounded, frozen, peak) = run(Some(pool));
assert_eq!(bounded, unbounded, "the pooled join produces the same rows");
assert!(unbounded.iter().sum::<usize>() > 0);
assert!(frozen >= 300, "most batches froze: {frozen}");
assert!(peak <= limit, "hot state {peak} stayed under the limit {limit}");
}
#[test]
fn eviction_deletes_frozen_files_once_wholly_past_the_horizon() {
use datafusion::execution::memory_pool::{GreedyMemoryPool, MemoryPool};
let dir = tempfile::tempdir().unwrap();
let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(1)); let mut j = StreamJoinBatch::new("auction", 100, 0).with_spill(dir.path(), &pool, 2);
j.expect_partitions(&[0], 0);
let (l, lt) = side(&[(1.0, "old", 100), (1.0, "old2", 150)]);
j.push_batch(0, Side::Left, &l, <, 0);
let (l2, l2t) = side(&[(1.0, "new", 5000)]);
j.push_batch(0, Side::Left, &l2, &l2t, 0);
assert_eq!(j.frozen_batches(), 2);
assert_eq!(std::fs::read_dir(dir.path()).unwrap().count(), 2);
j.evict(0); assert_eq!(std::fs::read_dir(dir.path()).unwrap().count(), 1);
assert_eq!(j.buffered_rows().0, 1);
let (r, rt) = side(&[(1.0, "ok", 4950)]);
assert_eq!(j.push_batch(0, Side::Right, &r, &rt, 0).unwrap().num_rows(), 1);
}
#[test]
fn snapshot_restore_joins_identically() {
let (l, lt) = side(&[(1.0, "L1", 100), (2.0, "L2", 200)]);
let (r, rt) = side(&[(1.0, "R1", 300), (2.0, "R2", 250)]);
let run = |restore: bool| -> Vec<Option<String>> {
let mut j = StreamJoinBatch::new("auction", 1000, 0);
j.expect_partitions(&[0], 0);
j.push_batch(0, Side::Left, &l, <, 0);
let mut j = if restore {
let snap = j.snapshot();
let mut fresh = StreamJoinBatch::new("auction", 1000, 0);
fresh.load_snapshot(&snap).unwrap();
fresh
} else {
j
};
let out = j.push_batch(0, Side::Right, &r, &rt, 0).unwrap();
strs(&out, "v")
};
assert_eq!(run(false), run(true));
assert_eq!(run(false).len(), 2);
let mut other = StreamJoinBatch::new("auction", 999, 0);
let mut j = StreamJoinBatch::new("auction", 1000, 0);
j.push_batch(0, Side::Left, &l, <, 0);
assert!(other.load_snapshot(&j.snapshot()).is_err());
}
#[test]
fn the_incremental_head_and_frozen_files_restore_the_join_exactly() {
use datafusion::execution::memory_pool::{GreedyMemoryPool, MemoryPool};
let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(1)); let dir = tempfile::tempdir().unwrap();
let mut j = StreamJoinBatch::new("auction", 10_000, 0).with_spill(dir.path(), &pool, 8);
j.expect_partitions(&[0], 0);
for i in 0..4 {
let (l, lt) = side(&[(i as f64, "L", 1000 + i * 10)]);
j.push_batch(0, Side::Left, &l, <, 0);
}
assert!(!j.frozen_files().is_empty(), "expected some frozen files");
let head = j.snapshot_head();
let whole = j.snapshot();
assert!(
head.len() < whole.len(),
"head {} should be < whole {}",
head.len(),
whole.len()
);
let files = j.frozen_files();
let dir2 = tempfile::tempdir().unwrap();
let mut map = std::collections::HashMap::new();
for f in &files {
let dest = dir2.path().join(&f.name);
std::fs::copy(&f.path, &dest).unwrap();
map.insert(f.name.clone(), dest);
}
let pool2: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(1 << 30));
let mut j2 = StreamJoinBatch::new("auction", 10_000, 0).with_spill(dir2.path(), &pool2, 8);
j2.expect_partitions(&[0], 0);
j2.restore_incremental(&head, &map).unwrap();
let (r, rt) = side(&[(2.0, "R", 1500)]);
let a = j.push_batch(0, Side::Right, &r.clone(), &rt.clone(), 0);
let b = j2.push_batch(0, Side::Right, &r, &rt, 0);
assert_eq!(
a.as_ref().map(|x| x.num_rows()),
b.as_ref().map(|x| x.num_rows()),
"restored join matched a different number of rows"
);
assert_eq!(
a.map(|x| x.num_rows()).unwrap_or(0),
1,
"the auction=2 pair should join"
);
}
#[test]
fn file_backed_restore_matches_the_whole_snapshot_row_for_row() {
use datafusion::execution::memory_pool::{GreedyMemoryPool, MemoryPool};
let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(4096));
let dir = tempfile::tempdir().unwrap();
let mut j = StreamJoinBatch::new("auction", 1_000_000, 0).with_spill(dir.path(), &pool, 4);
j.expect_partitions(&[0], 0);
for i in 0..200i64 {
let (l, lt) = side(&[(i as f64, "L", 1000 + i)]);
j.push_batch(0, Side::Left, &l, <, 0);
}
assert!(
j.frozen_files().len() >= 2,
"want several frozen files, got {}",
j.frozen_files().len()
);
let whole = j.snapshot();
let dw = tempfile::tempdir().unwrap();
let pw: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(1 << 30));
let mut jw = StreamJoinBatch::new("auction", 1_000_000, 0).with_spill(dw.path(), &pw, 4);
jw.expect_partitions(&[0], 0);
jw.load_snapshot(&whole).unwrap();
let head = j.snapshot_head();
let df = tempfile::tempdir().unwrap();
let mut map = std::collections::HashMap::new();
for f in j.frozen_files() {
let dest = df.path().join(&f.name);
std::fs::copy(&f.path, &dest).unwrap();
map.insert(f.name, dest);
}
let pf: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(1 << 30));
let mut jf = StreamJoinBatch::new("auction", 1_000_000, 0).with_spill(df.path(), &pf, 4);
jf.expect_partitions(&[0], 0);
jf.restore_incremental(&head, &map).unwrap();
let mut total_w = 0usize;
let mut total_f = 0usize;
for i in 0..200i64 {
let (r, rt) = side(&[(i as f64, "R", 1500 + i)]);
let w = jw
.push_batch(0, Side::Right, &r.clone(), &rt.clone(), 0)
.map(|b| b.num_rows())
.unwrap_or(0);
let fb = jf
.push_batch(0, Side::Right, &r, &rt, 0)
.map(|b| b.num_rows())
.unwrap_or(0);
assert_eq!(w, fb, "key {i}: whole joined {w}, file-backed joined {fb}");
total_w += w;
total_f += fb;
}
assert_eq!(total_w, total_f);
assert_eq!(total_w, 200, "every left key should have joined its right probe");
}
#[test]
fn file_backed_restore_all_hot_matches_the_whole_snapshot() {
use datafusion::execution::memory_pool::{GreedyMemoryPool, MemoryPool};
let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(1 << 30));
let dir = tempfile::tempdir().unwrap();
let mut j = StreamJoinBatch::new("auction", 1_000_000, 0).with_spill(dir.path(), &pool, 4);
j.expect_partitions(&[0], 0);
for i in 0..300i64 {
let (l, lt) = side(&[(i as f64, "L", 1000 + i)]);
j.push_batch(0, Side::Left, &l, <, 0);
}
assert_eq!(j.frozen_files().len(), 0, "nothing should freeze under a huge pool");
let head = j.snapshot_head();
let map = std::collections::HashMap::new(); let pf: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(1 << 30));
let df = tempfile::tempdir().unwrap();
let mut jf = StreamJoinBatch::new("auction", 1_000_000, 0).with_spill(df.path(), &pf, 4);
jf.expect_partitions(&[0], 0);
jf.restore_incremental(&head, &map).unwrap();
let mut total = 0usize;
for i in 0..300i64 {
let (r, rt) = side(&[(i as f64, "R", 1500 + i)]);
total += jf
.push_batch(0, Side::Right, &r, &rt, 0)
.map(|b| b.num_rows())
.unwrap_or(0);
}
assert_eq!(total, 300, "every left key should have joined its right probe");
}
}