use super::{Part, PartMeta};
use crate::fold::Loc;
use crate::types::PieceHash;
use anyhow::{bail, Result};
use std::collections::HashMap;
use std::path::Path;
use std::sync::Arc;
#[derive(Clone, Copy, Debug)]
pub struct MergeStats {
pub inputs: usize,
pub records_in: usize,
pub records_out: usize,
pub superseded: usize,
pub tombstones_kept: usize,
pub tombstones_dropped: usize,
pub fold_bytes_touched: u64,
}
pub fn merge(out: &Path, inputs: &[Arc<Part>], level: i32) -> Result<(PartMeta, MergeStats)> {
merge_opts(out, inputs, level, false)
}
type MergeGroup = (Vec<u8>, usize, usize, usize);
struct KWay<'a> {
cursors: Vec<crate::part::idcol::IdCursor<'a>>,
current: Vec<Option<Vec<u8>>>,
row: Vec<usize>,
}
impl<'a> KWay<'a> {
fn new(streams: &'a [Arc<Vec<u8>>], lens: &[usize]) -> Result<KWay<'a>> {
let mut cursors: Vec<_> = streams
.iter()
.zip(lens)
.map(|(s, &n)| crate::part::idcol::IdCursor::new(s, n))
.collect();
let mut current = Vec::with_capacity(cursors.len());
for c in &mut cursors {
current.push(c.next_id()?.map(|b| b.to_vec()));
}
Ok(KWay { cursors, current, row: vec![0; streams.len()] })
}
fn next_group(&mut self) -> Result<Option<MergeGroup>> {
let min = match self.current.iter().flatten().min() {
Some(m) => m.clone(),
None => return Ok(None),
};
let mut winner = (0usize, 0usize);
let mut holders = 0usize;
for i in 0..self.cursors.len() {
if self.current[i].as_deref() == Some(min.as_slice()) {
winner = (i, self.row[i]);
holders += 1;
self.row[i] += 1;
self.current[i] = self.cursors[i].next_id()?.map(|b| b.to_vec());
}
}
Ok(Some((min, winner.0, winner.1, holders - 1)))
}
}
pub fn merge_opts(
out: &Path,
inputs: &[Arc<Part>],
level: i32,
drop_tombstones: bool,
) -> Result<(PartMeta, MergeStats)> {
merge_opts_with_control(
out,
inputs,
level,
drop_tombstones,
&crate::control::OperationControl::default(),
)
}
pub fn merge_opts_with_control(
out: &Path,
inputs: &[Arc<Part>],
level: i32,
drop_tombstones: bool,
control: &crate::control::OperationControl,
) -> Result<(PartMeta, MergeStats)> {
merge_opts_with_control_and_limits(
out,
inputs,
level,
drop_tombstones,
control,
crate::read_limits::ReadLimits::default(),
)
}
pub fn merge_opts_with_control_and_limits(
out: &Path,
inputs: &[Arc<Part>],
level: i32,
drop_tombstones: bool,
control: &crate::control::OperationControl,
read_limits: crate::read_limits::ReadLimits,
) -> Result<(PartMeta, MergeStats)> {
merge_opts_with_control_for_operation(
out,
inputs,
level,
drop_tombstones,
control,
"part compaction",
read_limits,
)
}
pub(crate) fn merge_opts_with_control_for_operation(
out: &Path,
inputs: &[Arc<Part>],
level: i32,
drop_tombstones: bool,
control: &crate::control::OperationControl,
operation: &'static str,
read_limits: crate::read_limits::ReadLimits,
) -> Result<(PartMeta, MergeStats)> {
let sink = crate::part::FilePartSink::create(out)?;
let (meta, stats, _sink) = merge_into_with_control_for_operation(
sink,
out,
inputs,
level,
drop_tombstones,
control,
operation,
read_limits,
None,
)?;
Ok((meta, stats))
}
#[allow(clippy::too_many_arguments)]
pub(crate) fn merge_into_with_control_for_operation<S: crate::vfs::ArtifactSink>(
sink: S,
spool_base: &Path,
inputs: &[Arc<Part>],
level: i32,
drop_tombstones: bool,
control: &crate::control::OperationControl,
operation: &'static str,
read_limits: crate::read_limits::ReadLimits,
location_is_usable: Option<&dyn Fn(Loc, PieceHash) -> Result<bool>>,
) -> Result<(PartMeta, MergeStats, S)> {
control.check(operation)?;
if inputs.is_empty() {
bail!("merge needs at least one input part");
}
let mut parts: Vec<&Arc<Part>> = inputs.iter().collect();
parts.sort_by_key(|p| p.meta().seq_hi);
for w in parts.windows(2) {
if w[0].meta().seq_hi >= w[1].meta().seq_lo {
bail!(
"merge inputs overlap in sequence: [{},{}] and [{},{}]",
w[0].meta().seq_lo,
w[0].meta().seq_hi,
w[1].meta().seq_lo,
w[1].meta().seq_hi
);
}
}
let seq_lo = parts.first().unwrap().meta().seq_lo;
let seq_hi = parts.last().unwrap().meta().seq_hi;
let mut locs: HashMap<PieceHash, Loc> = HashMap::new();
for p in parts.iter().rev() {
for i in 0..p.piece_count()? {
control.check(operation)?;
let (loc, hash) = p.piece(i)?;
if let Some(is_usable) = location_is_usable {
if !is_usable(loc, hash)? {
continue;
}
}
locs.entry(hash).or_insert(loc);
}
}
let streams: Vec<Arc<Vec<u8>>> =
parts.iter().map(|p| p.section_bytes("ids")).collect::<Result<_>>()?;
let lens: Vec<usize> = parts.iter().map(|p| p.len()).collect();
let records_in: usize = lens.iter().sum();
let mut columns: std::collections::BTreeMap<(String, u8), std::collections::BTreeSet<Vec<u8>>> =
Default::default();
let mut content_names = std::collections::BTreeSet::new();
let mut records_out = 0usize;
let mut superseded = 0usize;
let mut tombs_kept = 0usize;
let mut tombs_dropped = 0usize;
let mut kway = KWay::new(&streams, &lens)?;
while let Some((_, pi, row, shadowed)) = kway.next_group()? {
control.check(operation)?;
superseded += shadowed;
if parts[pi].is_tombstone(row)? {
if drop_tombstones {
tombs_dropped += 1;
} else {
tombs_kept += 1;
records_out += 1;
}
continue;
}
records_out += 1;
for content in parts[pi].contents(row)? {
content_names.insert(content.name);
}
for (k, v) in parts[pi].attrs(row)? {
let e = columns.entry((k, v.type_tag())).or_default();
match v {
crate::types::AttrValue::Str(s) => {
e.insert(s.into_bytes());
}
crate::types::AttrValue::Bytes(bytes) => {
e.insert(bytes);
}
_ => {}
}
}
}
let value_dicts: Vec<Vec<Vec<u8>>> =
columns.values().map(|s| s.iter().cloned().collect()).collect();
let columns: Vec<(String, u8)> = columns.into_keys().collect();
let dict: Vec<(Loc, PieceHash)> = locs.iter().map(|(h, l)| (*l, *h)).collect();
let mut b = crate::part::builder::SinkBuilder::over(
sink,
spool_base,
level,
dict,
content_names.into_iter().collect(),
columns,
value_dicts,
read_limits,
)?;
let mut kway = KWay::new(&streams, &lens)?;
while let Some((id, pi, row, _)) = kway.next_group()? {
control.check(operation)?;
if parts[pi].is_tombstone(row)? {
if !drop_tombstones {
b.push(&id, true, &[], &[])?;
}
continue;
}
b.push(&id, false, &parts[pi].contents(row)?, &parts[pi].attrs(row)?)?;
}
control.check(operation)?;
let (meta, sink) = b.finish(seq_lo, seq_hi)?;
let stats = MergeStats {
inputs: parts.len(),
records_in,
records_out,
superseded,
tombstones_kept: tombs_kept,
tombstones_dropped: tombs_dropped,
fold_bytes_touched: 0,
};
Ok((meta, stats, sink))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::fold::{Fold, FoldCfg};
use crate::types::{AttrValue, Content, ContentOp, Record, BODY_CONTENT};
fn tmpdir(tag: &str) -> std::path::PathBuf {
let n =
std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_nanos();
let d = std::env::temp_dir().join(format!("turndb-merge-{tag}-{}-{n}", std::process::id()));
std::fs::create_dir_all(&d).unwrap();
d
}
fn part_of(
dir: &std::path::Path,
fold: &mut Fold,
name: &str,
seq: u64,
recs: &[(&str, &str)],
) -> Arc<Part> {
let rs: Vec<Record> = recs
.iter()
.map(|(id, body)| {
let p = fold.put(body.as_bytes()).unwrap();
Record {
id: (*id).to_string(),
contents: vec![Content::identified(
BODY_CONTENT,
vec![ContentOp::Piece { hash: p.hash, len: p.loc.raw }],
crate::types::ContentHash(p.hash.0),
)],
attrs: vec![("v".into(), AttrValue::Str((*body).to_string()))],
}
})
.collect();
let path = dir.join(name);
super::super::build(&path, &rs, seq, seq, 3, |h| fold.lookup(*h)).unwrap();
Arc::new(Part::open(&path).unwrap())
}
#[test]
fn merges_and_resolves_newest_wins() {
let d = tmpdir("basic");
let mut fold = Fold::open(&d.join("fold"), FoldCfg::default()).unwrap();
let a = part_of(&d, &mut fold, "a.part", 1, &[("k1", "one"), ("k2", "two")]);
let b = part_of(&d, &mut fold, "b.part", 2, &[("k2", "TWO-NEW"), ("k3", "three")]);
fold.sync().unwrap();
let outp = d.join("m.part");
let (meta, st) = merge(&outp, &[a, b], 3).unwrap();
assert_eq!(meta.n_records, 3, "k1, k2, k3");
assert_eq!((meta.seq_lo, meta.seq_hi), (1, 2), "output must span its inputs' sequences");
assert_eq!(st.superseded, 1);
assert_eq!(st.fold_bytes_touched, 0, "MERGE MUST NOT TOUCH THE FOLD");
let m = Part::open(&outp).unwrap();
assert_eq!(m.reconstruct(m.find("k1").unwrap().unwrap(), &fold).unwrap(), b"one");
assert_eq!(
m.reconstruct(m.find("k2").unwrap().unwrap(), &fold).unwrap(),
b"TWO-NEW",
"the later part's version must win"
);
assert_eq!(m.reconstruct(m.find("k3").unwrap().unwrap(), &fold).unwrap(), b"three");
std::fs::remove_dir_all(&d).ok();
}
#[test]
fn output_is_independent_of_argument_order() {
let d = tmpdir("determinism");
let mut fold = Fold::open(&d.join("fold"), FoldCfg::default()).unwrap();
let a = part_of(&d, &mut fold, "a.part", 1, &[("x", "alpha"), ("y", "beta")]);
let b = part_of(&d, &mut fold, "b.part", 2, &[("y", "BETA2"), ("z", "gamma")]);
fold.sync().unwrap();
let p1 = d.join("m1.part");
let p2 = d.join("m2.part");
merge(&p1, &[a.clone(), b.clone()], 3).unwrap();
merge(&p2, &[b, a], 3).unwrap();
assert_eq!(
crate::vfs::read_file(&p1).unwrap(),
crate::vfs::read_file(&p2).unwrap(),
"a merge must be a pure function of its input SET, not of argument order"
);
std::fs::remove_dir_all(&d).ok();
}
#[test]
fn streaming_merge_matches_the_materialized_oracle_byte_for_byte() {
let d = tmpdir("oracle");
let mut fold = Fold::open(&d.join("fold"), FoldCfg::default()).unwrap();
let a = part_of(&d, &mut fold, "a.part", 1, &[("k1", "one"), ("k2", "two")]);
let b = part_of(&d, &mut fold, "b.part", 2, &[("k2", "TWO-NEW"), ("k3", "three")]);
let tomb_rec = Record { id: "k1".into(), contents: Vec::new(), attrs: Vec::new() };
let cp = d.join("c.part");
super::super::build_full(&cp, &[tomb_rec], &[true], 3, 3, 3, |_| None, &HashMap::new())
.unwrap();
let c = Arc::new(Part::open(&cp).unwrap());
fold.sync().unwrap();
let streamed = d.join("streamed.part");
merge(&streamed, &[a.clone(), b.clone(), c.clone()], 3).unwrap();
let mut locs: HashMap<PieceHash, Loc> = HashMap::new();
for p in [&a, &b, &c] {
for i in 0..p.piece_count().unwrap() {
let (loc, hash) = p.piece(i).unwrap();
locs.entry(hash).or_insert(loc);
}
}
let recs = vec![
Record { id: "k1".into(), contents: Vec::new(), attrs: Vec::new() },
b.record(b.find("k2").unwrap().unwrap()).unwrap(),
b.record(b.find("k3").unwrap().unwrap()).unwrap(),
];
let oracle = d.join("oracle.part");
super::super::build_full(
&oracle,
&recs,
&[true, false, false],
1,
3,
3,
|h| locs.get(h).copied(),
&locs,
)
.unwrap();
assert_eq!(
crate::vfs::read_file(&streamed).unwrap(),
crate::vfs::read_file(&oracle).unwrap(),
"the streaming merge must be byte-identical to the materialized algorithm"
);
std::fs::remove_dir_all(&d).ok();
}
#[test]
fn a_total_merge_of_only_tombstones_yields_a_valid_empty_part() {
let d = tmpdir("allgone");
let r = Record { id: "x".into(), contents: Vec::new(), attrs: Vec::new() };
let p1 = d.join("a.part");
super::super::build_full(&p1, &[r], &[true], 1, 1, 3, |_| None, &HashMap::new()).unwrap();
let a = Arc::new(Part::open(&p1).unwrap());
let out = d.join("m.part");
let (meta, st) = merge_opts(&out, &[a], 3, true).unwrap();
assert_eq!(meta.n_records, 0);
assert_eq!(st.tombstones_dropped, 1);
let m = Part::open(&out).unwrap();
assert_eq!(m.len(), 0);
assert!(m.ids().unwrap().is_empty());
assert!(m.find("x").unwrap().is_none());
std::fs::remove_dir_all(&d).ok();
}
#[test]
fn overlapping_sequence_ranges_are_refused() {
let d = tmpdir("overlap");
let mut fold = Fold::open(&d.join("fold"), FoldCfg::default()).unwrap();
let a = part_of(&d, &mut fold, "a.part", 5, &[("x", "1")]);
let b = part_of(&d, &mut fold, "b.part", 5, &[("y", "2")]);
assert!(merge(&d.join("m.part"), &[a, b], 3).is_err(), "overlapping sequences must refuse");
std::fs::remove_dir_all(&d).ok();
}
}