use std::collections::{BTreeMap, HashMap, HashSet};
use std::io::BufWriter;
use std::path::{Path, PathBuf};
use std::time::SystemTime;
use crate::error::{Error, Result};
use crate::format::del::Bitmap;
use crate::format::doc::{self, DocIn, DocKind, DocTableView};
use crate::format::envelope;
use crate::format::idx::{self, IdxSummary};
use crate::format::manifest::SegmentEntry;
use crate::fs::Fs;
use crate::index::memory::{MemPostingList, MemTermStore};
use crate::index::{DocId, DocMeta, IndexReader, PostingCursor, PostingList, SegmentReader};
use super::reader::{open, Index, OpenOptions};
use super::segment::time_to_nanos;
use super::writer::{commit, relative_path, take_lock, write_whole};
use super::{del_name, doc_name, idx_name, index_dir, segment_files, tmp_name, MANIFEST};
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct MergePolicy {
pub tier_size: usize,
pub max_merge: usize,
pub max_segment_bytes: u64,
pub del_fraction_threshold: f32,
}
impl Default for MergePolicy {
fn default() -> Self {
Self { tier_size: 4, max_merge: 10, max_segment_bytes: 512 << 20, del_fraction_threshold: 0.3 }
}
}
pub fn plan_merges(segments: &[SegmentEntry], policy: &MergePolicy) -> Vec<Vec<u32>> {
let mut groups = Vec::new();
let mut used: HashSet<u32> = HashSet::new();
for s in segments {
if s.num_docs > 0 && s.deleted_fraction() > policy.del_fraction_threshold && s.total_bytes() <= policy.max_segment_bytes {
groups.push(vec![s.segment_id]);
used.insert(s.segment_id);
}
}
let mut tiers: BTreeMap<i32, Vec<u32>> = BTreeMap::new();
for s in segments {
if used.contains(&s.segment_id) || s.total_bytes() > policy.max_segment_bytes {
continue;
}
let live_fraction = if s.num_docs == 0 { 0.0 } else { s.live_docs() as f64 / s.num_docs as f64 };
let live_bytes = ((s.total_bytes() as f64) * live_fraction).max((1u64 << 20) as f64);
let tier = live_bytes.log2().floor() as i32;
tiers.entry(tier).or_default().push(s.segment_id);
}
for (_, mut ids) in tiers {
if ids.len() < policy.tier_size {
continue;
}
ids.sort_unstable();
for chunk in ids.chunks(policy.max_merge.max(2)) {
if chunk.len() >= 2 {
groups.push(chunk.to_vec());
}
}
}
groups
}
fn corrupt(path: &Path, reason: impl std::fmt::Display) -> Error {
Error::Corrupt { path: path.to_path_buf(), reason: reason.to_string() }
}
pub struct PreparedMerge {
source_ids: Vec<u32>,
snapshot_del_gen: HashMap<u32, u32>,
old_to_new: HashMap<(u32, DocId), DocId>,
num_docs: u32,
idx_tmp: PathBuf,
doc_tmp: PathBuf,
idx_summary: IdxSummary,
doc_crc: u32,
doc_len: u64,
}
impl PreparedMerge {
pub fn source_ids(&self) -> &[u32] {
&self.source_ids
}
pub fn num_docs(&self) -> u32 {
self.num_docs
}
pub fn discard(self, fs: &dyn Fs) {
let _ = fs.remove_file(&self.idx_tmp);
let _ = fs.remove_file(&self.doc_tmp);
}
}
pub fn prepare_merge(fs: &dyn Fs, root: &Path, dir: &Path, index: &Index, segment_ids: &[u32]) -> Result<PreparedMerge> {
let segs: Vec<&super::Segment> = segment_ids
.iter()
.map(|&id| {
index
.segment_list()
.iter()
.find(|s| s.entry().segment_id == id)
.unwrap_or_else(|| panic!("segment {id} named in a merge plan not found in the index"))
})
.collect();
let snapshot_del_gen = segs.iter().map(|s| (s.entry().segment_id, s.entry().del_gen)).collect();
let mut old_to_new: HashMap<(u32, DocId), DocId> = HashMap::new();
let mut metas: Vec<(String, DocMeta)> = Vec::new();
for seg in &segs {
let seg_id = seg.entry().segment_id;
for local in 0..seg.num_docs() {
if seg.is_deleted(local) {
continue;
}
let global = seg.base() + local;
if let Some(meta) = index.doc(global) {
old_to_new.insert((seg_id, local), metas.len() as DocId);
let rel = relative_path(root, &meta.path);
metas.push((rel, meta));
}
}
}
let mut terms: HashMap<String, MemPostingList> = HashMap::new();
let mut num_tokens = 0u64;
for seg in &segs {
let seg_id = seg.entry().segment_id;
let view = seg.idx();
let mut it = view.terms();
loop {
let next = it.try_next().map_err(|e| corrupt(&dir.join(idx_name(seg_id)), e))?;
let Some((term, _df, list)) = next else { break };
let mut cur = list.cursor();
while let Some(local) = cur.doc() {
if let Some(&new_id) = old_to_new.get(&(seg_id, local)) {
let positions = cur.positions();
num_tokens += positions.len() as u64;
let entry = terms.entry(term.clone()).or_default();
for &pos in positions {
entry.push(new_id, pos);
}
}
cur.advance();
}
}
}
let mut store = MemTermStore::default();
store.merge_shard(terms);
let staging = super::staging_dir(root);
fs.create_dir_all(&staging)?;
let tag = format!("merge-{:x}", std::process::id() as u64 ^ (SystemTime::now().duration_since(SystemTime::UNIX_EPOCH).map(|d| d.as_nanos() as u64).unwrap_or(0)));
let idx_tmp = staging.join(format!("{tag}.idx.tmp"));
let doc_tmp = staging.join(format!("{tag}.doc.tmp"));
let mut term_list: Vec<(&str, &MemPostingList)> = store.iter().collect();
term_list.sort_unstable_by(|a, b| a.0.as_bytes().cmp(b.0.as_bytes()));
let idx_summary = {
let file = fs.create(&idx_tmp)?;
let (w, summary) = idx::write(BufWriter::with_capacity(256 << 10, file), &term_list)?;
let mut file = w.into_inner().map_err(|e| e.into_error())?;
file.sync_all()?;
summary
};
drop(term_list);
debug_assert_eq!(idx_summary.num_tokens, num_tokens);
let rel_refs: Vec<&str> = metas.iter().map(|(r, _)| r.as_str()).collect();
let bytes = doc::encode(metas.iter().zip(&rel_refs).map(|((_, m), path)| DocIn {
path,
inode: m.inode,
mtime_nanos: time_to_nanos(m.mtime),
size: m.size,
len: m.len,
kind: DocKind::from(m.status),
content_hash: m.content_hash,
}))?;
let doc_crc = DocTableView::parse(&bytes)?.crc();
write_whole(fs, &doc_tmp, &bytes)?;
Ok(PreparedMerge {
source_ids: segment_ids.to_vec(),
snapshot_del_gen,
old_to_new,
num_docs: metas.len() as u32,
idx_tmp,
doc_tmp,
idx_summary,
doc_crc,
doc_len: bytes.len() as u64,
})
}
pub fn commit_merges(fs: &dyn Fs, root: &Path, prepared: Vec<PreparedMerge>) -> Result<Index> {
if prepared.is_empty() {
return open(fs, root, &OpenOptions::default())?.ok_or_else(|| Error::NoIndex(index_dir(root)));
}
let dir = index_dir(root);
let lock = take_lock(fs, &dir)?;
let cur = match open(fs, root, &OpenOptions::default()) {
Ok(Some(i)) => i,
Ok(None) => {
for p in prepared {
p.discard(fs);
}
return Err(Error::NoIndex(dir));
}
Err(e) => {
for p in prepared {
p.discard(fs);
}
return Err(e);
}
};
let mut manifest = cur.manifest().clone();
let mut new_files: Vec<PathBuf> = Vec::new();
let mut merged_ids: HashSet<u32> = HashSet::new();
let mut retired: Vec<PathBuf> = Vec::new();
let result = (|| -> Result<()> {
let mut new_entries = Vec::new();
let mut next_base = manifest.segments.iter().map(|s| s.end_doc()).max().unwrap_or(0) as DocId;
for p in &prepared {
for &id in &p.source_ids {
if !manifest.segments.iter().any(|s| s.segment_id == id) {
return Err(corrupt(&dir, format!("segment {id} no longer exists; merge aborted")));
}
}
let entry = finish_one(fs, &dir, &mut manifest, cur.segment_list(), p, next_base, &mut new_files)?;
next_base += entry.num_docs;
for &id in &p.source_ids {
merged_ids.insert(id);
let old = cur.manifest().segments.iter().find(|s| s.segment_id == id).unwrap();
retired.extend(segment_files(old).into_iter().map(|n| dir.join(n)));
}
new_entries.push(entry);
}
manifest.segments.retain(|s| !merged_ids.contains(&s.segment_id));
manifest.segments.extend(new_entries);
manifest.segments.sort_unstable_by_key(|s| s.base_doc);
manifest.generation += 1;
manifest.committed_unix_nanos = time_to_nanos(SystemTime::now());
commit(fs, &dir, &manifest, &retired)
})();
if let Err(e) = result {
for p in &new_files {
let _ = fs.remove_file(p);
}
return Err(e);
}
drop(lock);
open(fs, root, &OpenOptions::default())?.ok_or_else(|| Error::Corrupt { path: dir.join(MANIFEST), reason: "manifest unreadable right after commit".into() })
}
fn finish_one(
fs: &dyn Fs,
dir: &Path,
manifest: &mut crate::format::manifest::Manifest,
current_segments: &[super::Segment],
prepared: &PreparedMerge,
base_doc: DocId,
new_files: &mut Vec<PathBuf>,
) -> Result<SegmentEntry> {
let segment_id = manifest.next_segment_id;
manifest.next_segment_id += 1;
let idx_final = dir.join(idx_name(segment_id));
let doc_final = dir.join(doc_name(segment_id));
new_files.push(idx_final.clone());
fs.rename(&prepared.idx_tmp, &idx_final)?;
new_files.push(doc_final.clone());
fs.rename(&prepared.doc_tmp, &doc_final)?;
let mut carry = Bitmap::new(prepared.num_docs);
for &src_id in &prepared.source_ids {
let current_entry = manifest.segments.iter().find(|s| s.segment_id == src_id).unwrap();
if current_entry.del_gen == prepared.snapshot_del_gen[&src_id] {
continue; }
let seg = current_segments.iter().find(|s| s.entry().segment_id == src_id).unwrap();
let Some(bitmap) = seg.deletions() else { continue };
for (&(seg_id, old_local), &new_local) in &prepared.old_to_new {
if seg_id == src_id && bitmap.get(old_local) {
carry.set(new_local);
}
}
}
let (del_gen, del_len, del_crc, num_deleted) = if carry.count() > 0 {
let bytes = carry.encode();
let final_path = dir.join(del_name(segment_id, 1));
let tmp = dir.join(tmp_name(&del_name(segment_id, 1)));
new_files.push(tmp.clone());
write_whole(fs, &tmp, &bytes)?;
new_files.push(final_path.clone());
fs.rename(&tmp, &final_path)?;
let crc = envelope::parse(envelope::Kind::Del, &bytes)?.crc;
(1u32, bytes.len() as u64, crc, carry.count())
} else {
(0, 0, 0, 0)
};
Ok(SegmentEntry {
segment_id,
del_gen,
base_doc,
num_docs: prepared.num_docs,
num_deleted,
idx_crc: prepared.idx_summary.crc,
doc_crc: prepared.doc_crc,
del_crc,
idx_len: prepared.idx_summary.len,
doc_len: prepared.doc_len,
del_len,
num_tokens: prepared.idx_summary.num_tokens,
num_postings: prepared.idx_summary.num_postings,
num_terms: prepared.idx_summary.num_terms,
})
}
pub fn merge_index(fs: &dyn Fs, root: &Path, policy: &MergePolicy) -> Result<Index> {
let dir = index_dir(root);
super::clear_staging(fs, root)?;
let prev = open(fs, root, &OpenOptions::default())?.ok_or_else(|| Error::NoIndex(dir.clone()))?;
let groups = plan_merges(&prev.manifest().segments, policy);
if groups.is_empty() {
return Ok(prev);
}
let mut prepared = Vec::with_capacity(groups.len());
for group in &groups {
match prepare_merge(fs, root, &dir, &prev, group) {
Ok(p) => prepared.push(p),
Err(e) => {
for p in prepared {
p.discard(fs);
}
return Err(e);
}
}
}
commit_merges(fs, root, prepared)
}
#[cfg(test)]
mod tests {
use super::*;
fn seg(id: u32, num_docs: u32, num_deleted: u32, bytes: u64) -> SegmentEntry {
SegmentEntry { segment_id: id, base_doc: 0, num_docs, num_deleted, idx_len: bytes, ..Default::default() }
}
#[test]
fn small_tiers_do_not_merge() {
let segs = vec![seg(0, 10, 0, 1000), seg(1, 10, 0, 1000)];
assert!(plan_merges(&segs, &MergePolicy::default()).is_empty());
}
#[test]
fn a_full_tier_merges() {
let segs: Vec<_> = (0..4).map(|i| seg(i, 10, 0, 1_000_000)).collect(); let groups = plan_merges(&segs, &MergePolicy::default());
assert_eq!(groups.len(), 1);
let mut ids = groups[0].clone();
ids.sort();
assert_eq!(ids, vec![0, 1, 2, 3]);
}
#[test]
fn different_tiers_do_not_mix() {
let mut segs: Vec<_> = (0..4).map(|i| seg(i, 10, 0, 1_000_000)).collect(); segs.extend((4..8).map(|i| seg(i, 10, 0, 100_000_000))); let groups = plan_merges(&segs, &MergePolicy::default());
assert_eq!(groups.len(), 2);
for g in &groups {
assert!(g.iter().all(|id| *id < 4) || g.iter().all(|id| *id >= 4));
}
}
#[test]
fn oversized_segments_are_never_merged() {
let mut segs: Vec<_> = (0..5).map(|i| seg(i, 10, 0, 1_000_000)).collect();
segs.push(seg(5, 10, 0, 600 << 20)); let groups = plan_merges(&segs, &MergePolicy::default());
assert!(groups.iter().flatten().all(|&id| id != 5));
}
#[test]
fn heavily_deleted_segment_is_rewritten_alone() {
let segs = vec![seg(0, 100, 40, 1_000_000), seg(1, 10, 0, 1_000_000)];
let groups = plan_merges(&segs, &MergePolicy::default());
assert!(groups.contains(&vec![0]));
assert_eq!(groups.len(), 1);
}
#[test]
fn a_deletion_driven_segment_is_not_also_tier_merged() {
let mut segs = vec![seg(0, 100, 40, 1_000_000)]; segs.extend((1..4).map(|i| seg(i, 10, 0, 1_000_000))); let groups = plan_merges(&segs, &MergePolicy::default());
assert_eq!(groups, vec![vec![0]]); }
#[test]
fn tier_larger_than_max_merge_is_chunked() {
let segs: Vec<_> = (0..25).map(|i| seg(i, 10, 0, 1_000_000)).collect();
let groups = plan_merges(&segs, &MergePolicy::default());
assert!(groups.iter().all(|g| g.len() <= 10));
let total: usize = groups.iter().map(|g| g.len()).sum();
assert_eq!(total, 25);
}
#[test]
fn empty_input_plans_nothing() {
assert!(plan_merges(&[], &MergePolicy::default()).is_empty());
}
}