use std::fs;
use std::sync::Arc;
use std::time::Duration;
use zerocopy::FromBytes;
use crate::Key;
use crate::disk_loc::DiskLoc;
use crate::entry::{EntryHeader, entry_size};
use crate::error::DbResult;
use crate::hint;
use crate::io::direct;
use crate::shard::{FileSeqs, ImmutableFile, MinSeq, Shard};
#[cfg(any(test, feature = "test-faults"))]
pub mod failpoints {
use std::sync::atomic::{AtomicU8, Ordering};
pub const NONE: u8 = 0;
pub const AFTER_FIRST_SEALED_PAGE: u8 = 1;
pub static STAGE: AtomicU8 = AtomicU8::new(NONE);
pub fn hit(stage: u8) {
if STAGE.load(Ordering::SeqCst) == stage {
std::process::exit(9);
}
}
}
#[cfg(all(feature = "encryption", not(any(test, feature = "test-faults"))))]
mod failpoints {
pub const AFTER_FIRST_SEALED_PAGE: u8 = 1;
pub fn hit(_: u8) {}
}
type ReadFn = dyn Fn(&std::fs::File, u64, usize) -> DbResult<Vec<u8>>;
struct CompactionLease<'a> {
flag: &'a std::sync::atomic::AtomicBool,
}
impl<'a> CompactionLease<'a> {
fn try_acquire(shard: &'a Shard) -> Option<Self> {
shard
.compacting
.compare_exchange(
false,
true,
std::sync::atomic::Ordering::Acquire,
std::sync::atomic::Ordering::Relaxed,
)
.ok()
.map(|_| Self {
flag: &shard.compacting,
})
}
}
impl Drop for CompactionLease<'_> {
fn drop(&mut self) {
self.flag.store(false, std::sync::atomic::Ordering::Release);
}
}
#[cfg(feature = "encryption")]
use crate::crypto::{FileKeys, PageCipher};
#[cfg(feature = "encryption")]
use crate::io::keys::{KeyFile, KeyRecord, keys_path_for_data};
#[cfg(feature = "encryption")]
use crate::io::tags::{self, TagFile};
fn dir_fsync(dir: &std::path::Path) -> DbResult<()> {
direct::sync_dir(dir)
}
pub trait CompactionIndex<K: Key>: Send + Sync {
fn update_if_match(&self, key: &K, old_loc: DiskLoc, new_loc: DiskLoc) -> bool;
fn invalidate_blocks(&self, _shard_id: u8, _file_id: u32, _total_bytes: u64) {}
fn contains_key(&self, key: &K) -> bool;
fn is_live(&self, shard_id: u8, key: &K, loc: DiskLoc) -> bool;
}
#[cfg(feature = "replication")]
pub trait CompactionGuard: Send + Sync {
fn min_replicated_gsn(&self, shard_id: u8) -> u64;
}
#[cfg(feature = "replication")]
pub struct NoReplicationGuard;
#[cfg(feature = "replication")]
impl CompactionGuard for NoReplicationGuard {
fn min_replicated_gsn(&self, _shard_id: u8) -> u64 {
u64::MAX
}
}
fn should_rotate_output(write_offset: u64, needed: u64, max_file_size: u64) -> bool {
write_offset + needed > max_file_size
}
pub fn compact_shard<K: Key, I: CompactionIndex<K>>(
shard: &Shard,
index: &I,
threshold: f64,
) -> DbResult<usize> {
compact_shard_inner::<K, I>(shard, index, threshold, u64::MAX)
}
#[cfg(feature = "replication")]
pub fn compact_shard_guarded<K: Key, I: CompactionIndex<K>>(
shard: &Shard,
index: &I,
threshold: f64,
guard: &dyn CompactionGuard,
) -> DbResult<usize> {
if !shard.hints_enabled() {
return Err(crate::error::DbError::GuardedCompactionRequiresHints { shard: shard.id });
}
let min_gsn = guard.min_replicated_gsn(shard.id);
compact_shard_inner::<K, I>(shard, index, threshold, min_gsn)
}
struct OutputState {
file_id: u32,
tmp_file: fs::File,
write_offset: u64,
seqs: FileSeqs,
#[cfg(feature = "encryption")]
enc_state: Option<EncryptionState>,
}
#[cfg(feature = "encryption")]
struct EncryptionState {
cipher: Arc<PageCipher>,
page_buf: Box<[u8; 4096]>,
page_offset: usize,
pages_written: u64,
tag_list: Vec<[u8; 16]>,
}
#[cfg(feature = "encryption")]
impl EncryptionState {
fn flush_page(&mut self, file: &fs::File, file_id: u32) -> DbResult<()> {
let tag = self
.cipher
.encrypt_page(file_id, self.pages_written, &mut *self.page_buf)?;
direct::pwrite_at(file, &*self.page_buf, self.pages_written * 4096)?;
failpoints::hit(failpoints::AFTER_FIRST_SEALED_PAGE);
self.tag_list.push(tag);
self.pages_written += 1;
self.page_buf.fill(0);
self.page_offset = 0;
Ok(())
}
fn write_bytes(&mut self, file: &fs::File, file_id: u32, data: &[u8]) -> DbResult<()> {
let mut remaining = data;
while !remaining.is_empty() {
let space = 4096 - self.page_offset;
let chunk = remaining.len().min(space);
self.page_buf[self.page_offset..self.page_offset + chunk]
.copy_from_slice(&remaining[..chunk]);
self.page_offset += chunk;
remaining = &remaining[chunk..];
if self.page_offset == 4096 {
self.flush_page(file, file_id)?;
}
}
Ok(())
}
}
struct FinalizedOutput {
file_id: u32,
total_bytes: u64,
seqs: FileSeqs,
final_data_path: std::path::PathBuf,
#[cfg(feature = "encryption")]
final_tag_path: Option<std::path::PathBuf>,
#[cfg(feature = "encryption")]
keys: Option<Arc<FileKeys>>,
}
struct OutputGuard {
dir: std::path::PathBuf,
finalized_ids: Vec<u32>,
current_tmp_id: Option<u32>,
armed: bool,
}
impl OutputGuard {
fn new(dir: std::path::PathBuf) -> Self {
Self {
dir,
finalized_ids: Vec::new(),
current_tmp_id: None,
armed: true,
}
}
fn set_current(&mut self, file_id: u32) {
self.current_tmp_id = Some(file_id);
}
fn mark_finalized(&mut self, file_id: u32) {
self.current_tmp_id = None;
self.finalized_ids.push(file_id);
}
fn clear_current(&mut self) {
self.current_tmp_id = None;
}
fn disarm(&mut self) {
self.armed = false;
}
}
impl Drop for OutputGuard {
fn drop(&mut self) {
if !self.armed {
return;
}
fn remove_logged(path: std::path::PathBuf) {
match fs::remove_file(&path) {
Ok(()) => {}
Err(e) if e.kind() == std::io::ErrorKind::NotFound => {}
Err(e) => {
tracing::warn!(?path, err = %e, "compaction cleanup failed to remove orphan")
}
}
}
let ids = self
.finalized_ids
.iter()
.copied()
.chain(self.current_tmp_id);
for fid in ids.clone() {
remove_logged(self.dir.join(format!("{fid:06}.data")));
remove_logged(self.dir.join(format!("{fid:06}.data.tmp")));
}
#[cfg(feature = "encryption")]
{
let _ = dir_fsync(&self.dir);
for fid in ids {
for suffix in ["tags", "tags.tmp", "keys", "keys.tmp"] {
remove_logged(self.dir.join(format!("{fid:06}.{suffix}")));
}
}
let _ = dir_fsync(&self.dir);
}
}
}
#[cfg(test)]
thread_local! {
static CRASH_BETWEEN_RENAMES: std::cell::Cell<bool> = const { std::cell::Cell::new(false) };
static OPEN_OUTPUT_CALLS: std::cell::Cell<u32> = const { std::cell::Cell::new(0) };
static FAIL_OPEN_OUTPUT_AT: std::cell::Cell<u32> = const { std::cell::Cell::new(0) };
static BEFORE_DEFERRED_CAS_HOOK: std::cell::RefCell<Option<Box<dyn FnOnce()>>> = const { std::cell::RefCell::new(None) };
static AFTER_PASS_ACQUIRE_HOOK: std::cell::RefCell<Option<Box<dyn FnOnce()>>> = const { std::cell::RefCell::new(None) };
}
#[cfg(test)]
pub(crate) fn test_pause_after_pass_acquire(
entered: std::sync::mpsc::SyncSender<()>,
resume: std::sync::mpsc::Receiver<()>,
) {
AFTER_PASS_ACQUIRE_HOOK.with(|hook| {
*hook.borrow_mut() = Some(Box::new(move || {
entered
.send(())
.expect("compaction test must receive pause");
resume.recv().expect("compaction test must resume");
}));
});
}
#[cfg(test)]
pub(crate) fn test_panic_after_pass_acquire() {
AFTER_PASS_ACQUIRE_HOOK.with(|hook| {
*hook.borrow_mut() = Some(Box::new(|| panic!("test: panic after compaction lease")));
});
}
#[cfg(test)]
pub(crate) struct OutputOpenFaultGuard;
#[cfg(test)]
impl Drop for OutputOpenFaultGuard {
fn drop(&mut self) {
OPEN_OUTPUT_CALLS.with(|calls| calls.set(0));
FAIL_OPEN_OUTPUT_AT.with(|at| at.set(0));
}
}
#[cfg(test)]
#[must_use = "the injected fault stays armed until this guard is dropped"]
pub(crate) fn test_fail_next_output_open() -> OutputOpenFaultGuard {
OPEN_OUTPUT_CALLS.with(|calls| calls.set(0));
FAIL_OPEN_OUTPUT_AT.with(|at| at.set(1));
OutputOpenFaultGuard
}
#[cfg(test)]
fn run_after_pass_acquire_hook() {
AFTER_PASS_ACQUIRE_HOOK.with(|hook| {
if let Some(hook) = hook.borrow_mut().take() {
hook();
}
});
}
#[cfg(test)]
pub(crate) fn test_pause_before_deferred_cas(
entered: std::sync::mpsc::SyncSender<()>,
resume: std::sync::mpsc::Receiver<()>,
) {
BEFORE_DEFERRED_CAS_HOOK.with(|hook| {
*hook.borrow_mut() = Some(Box::new(move || {
entered
.send(())
.expect("compaction test must receive pause");
resume.recv().expect("compaction test must resume");
}));
});
}
#[cfg(test)]
fn run_before_deferred_cas_hook() {
BEFORE_DEFERRED_CAS_HOOK.with(|hook| {
if let Some(hook) = hook.borrow_mut().take() {
hook();
}
});
}
struct CompactionSelection {
files: Vec<Arc<ImmutableFile>>,
drop_floor: u64,
max_file_size: u64,
}
fn select_compaction_files(
shard: &Shard,
threshold: f64,
min_replicated_gsn: u64,
) -> CompactionSelection {
let mut inner = shard.lock();
let max_file_size = inner.max_file_size;
let cooldown_ids = std::mem::take(&mut inner.last_compaction_output_ids);
struct Candidate {
file: Arc<ImmutableFile>,
dead_ratio: f64,
guard_blocked: bool,
}
let guarded = min_replicated_gsn < u64::MAX;
let mut candidates: Vec<Candidate> = inner
.immutable
.iter()
.map(|file| {
let guard_blocked = guarded && {
let hint_path = shard.dir().join(format!("{:06}.hint", file.file_id));
file_max_seq(&hint_path).is_none_or(|max_seq| max_seq >= min_replicated_gsn)
};
let dead = inner.dead_bytes.get(&file.file_id).copied().unwrap_or(0);
Candidate {
file: file.clone(),
dead_ratio: if file.total_bytes == 0 {
0.0
} else {
dead as f64 / file.total_bytes as f64
},
guard_blocked,
}
})
.collect();
let hints = inner.hints;
let max_files_per_pass = inner.compaction_max_files_per_pass;
let active_floor = inner.active.seqs.floor();
let is_cooldown = |file_id| cooldown_ids.contains(&file_id);
let mut selected_ids = std::collections::HashSet::new();
let mut selected: Vec<Arc<ImmutableFile>> = candidates
.iter()
.filter(|candidate| {
candidate.dead_ratio > threshold
&& !is_cooldown(candidate.file.file_id)
&& !candidate.guard_blocked
})
.map(|candidate| candidate.file.clone())
.collect();
selected.sort_by_key(|file| file.file_id);
if max_files_per_pass > 0 {
selected.truncate(max_files_per_pass);
}
selected_ids.extend(selected.iter().map(|file| file.file_id));
let mut drop_floor = 0;
if hints {
let max_tombstone_seq = candidates
.iter()
.filter(|candidate| {
selected_ids.contains(&candidate.file.file_id)
|| (candidate.dead_ratio <= threshold
&& !is_cooldown(candidate.file.file_id)
&& !candidate.guard_blocked
&& !matches!(candidate.file.seqs.min, MinSeq::Unknown))
})
.filter_map(|candidate| candidate.file.seqs.tombstones.max())
.max();
if let Some(s_max) = max_tombstone_seq {
candidates
.sort_by_key(|candidate| (candidate.file.seqs.floor(), candidate.file.file_id));
let initial_ids = selected_ids.clone();
for candidate in &candidates {
if selected_ids.contains(&candidate.file.file_id)
|| candidate.file.seqs.floor() > s_max
{
continue;
}
if active_floor <= s_max && candidate.file.seqs.floor() >= active_floor {
break;
}
if is_cooldown(candidate.file.file_id)
|| candidate.guard_blocked
|| matches!(candidate.file.seqs.min, MinSeq::Unknown)
|| (max_files_per_pass > 0 && selected.len() >= max_files_per_pass)
{
break;
}
selected_ids.insert(candidate.file.file_id);
selected.push(candidate.file.clone());
}
let floor_of = |ids: &std::collections::HashSet<u32>| {
let mut floor = active_floor;
for candidate in &candidates {
if !ids.contains(&candidate.file.file_id) {
floor = floor.min(candidate.file.seqs.floor());
}
}
floor
};
drop_floor = floor_of(&selected_ids);
if selected_ids.len() > initial_ids.len()
&& !selected.iter().any(|file| {
file.seqs
.tombstones
.min()
.is_some_and(|min| min < drop_floor)
})
{
selected.retain(|file| initial_ids.contains(&file.file_id));
selected_ids = initial_ids;
drop_floor = floor_of(&selected_ids);
}
}
}
selected.sort_by_key(|file| file.file_id);
CompactionSelection {
files: selected,
drop_floor,
max_file_size,
}
}
fn compact_shard_inner<K: Key, I: CompactionIndex<K>>(
shard: &Shard,
index: &I,
threshold: f64,
min_replicated_gsn: u64,
) -> DbResult<usize> {
let Some(_lease) = CompactionLease::try_acquire(shard) else {
tracing::debug!(
shard_id = shard.id,
"compaction pass skipped: another pass holds this shard's lease"
);
return Ok(0);
};
#[cfg(test)]
run_after_pass_acquire_hook();
let selection = select_compaction_files(shard, threshold, min_replicated_gsn);
let files_to_compact = selection.files;
if files_to_compact.is_empty() {
return Ok(0);
}
let max_file_size = selection.max_file_size;
let compact_start = std::time::Instant::now();
let old_file_ids: Vec<u32> = files_to_compact.iter().map(|f| f.file_id).collect();
let first_file_id = {
let mut inner = shard.lock();
inner.allocate_file_id()?
};
let mut cleanup = OutputGuard::new(shard.dir().to_path_buf());
cleanup.set_current(first_file_id);
let mut output = open_output(shard, first_file_id)?;
let serving_direct = shard.effective_direct_io();
const BATCH_SIZE: usize = 256;
struct BatchEntry<K> {
key: K,
gsn: u64,
crc32: u32,
old_loc: DiskLoc,
new_loc: DiskLoc,
is_tombstone: bool,
}
let mut batch: Vec<BatchEntry<K>> = Vec::with_capacity(BATCH_SIZE);
let mut pending_outputs: Vec<FinalizedOutput> = Vec::new();
for old_arc in &files_to_compact {
let data_path = shard.dir().join(format!("{:06}.data", old_arc.file_id));
let scan_file = direct::open_bulk_read(&data_path)?;
let file = &scan_file;
let file_len = old_arc.total_bytes;
let mut offset: u64 = 0;
#[cfg(feature = "encryption")]
let read_fn: Box<ReadFn> =
if let (Some(cipher), Some(_tag_file)) = (&old_arc.keys, &old_arc.tag_file) {
let c = cipher.clone();
let fid = old_arc.file_id;
let tp = tags::tags_path_for_data(&old_arc.path);
let tf = Arc::new(TagFile::open_read(&tp)?);
Box::new(move |f, o, l| direct::pread_value_encrypted(f, &tf, &c, fid, o, l))
} else {
Box::new(direct::pread_value)
};
#[cfg(not(feature = "encryption"))]
let read_fn: Box<ReadFn> = Box::new(direct::pread_value);
while offset + size_of::<EntryHeader>() as u64 <= file_len {
let header_bytes = match read_fn(file, offset, size_of::<EntryHeader>()) {
Ok(b) => b,
Err(_) => return Err(crate::error::DbError::CorruptedEntry { offset }),
};
let header = match EntryHeader::read_from_bytes(&header_bytes) {
Ok(h) => h,
Err(_) => return Err(crate::error::DbError::CorruptedEntry { offset }),
};
if crate::entry::is_padding_header(&header, offset) {
if crate::entry::padding_rest_is_clean(file, offset, read_fn.as_ref())? {
let next_page = crate::entry::padding_page_end(offset);
if next_page >= file_len {
break; }
offset = next_page;
continue;
}
return Err(crate::error::DbError::CorruptedEntry { offset });
}
let total = entry_size(size_of::<K>(), header.value_len);
if offset + total > file_len {
return Err(crate::error::DbError::CorruptedEntry { offset });
}
let old_loc = DiskLoc::new(
old_arc.file_id,
(offset + size_of::<EntryHeader>() as u64 + size_of::<K>() as u64) as u32,
header.value_len,
);
let entry_bytes = read_fn(file, offset, total as usize)?;
let key_start = size_of::<EntryHeader>();
let key_end = key_start + size_of::<K>();
let val_end = key_end + header.value_len as usize;
let computed_crc = crate::entry::compute_crc32(
header.gsn,
header.value_len,
&entry_bytes[key_start..key_end],
&entry_bytes[key_end..val_end],
);
if computed_crc != header.crc32 {
return Err(crate::error::DbError::CrcMismatch {
expected: header.crc32,
actual: computed_crc,
});
}
let key: K = K::from_bytes(&entry_bytes[key_start..key_end]);
let is_tombstone = header.is_tombstone();
let live = if is_tombstone {
header.sequence() >= selection.drop_floor && !index.contains_key(&key)
} else {
index.is_live(shard.id, &key, old_loc)
};
if !live {
offset += total;
continue;
}
if output.write_offset > 0
&& should_rotate_output(output.write_offset, total, max_file_size)
{
let next_file_id = {
let mut inner = shard.lock();
inner.allocate_file_id()?
};
let finished = finalize_output(shard, output)?;
cleanup.mark_finalized(finished.file_id);
pending_outputs.push(finished);
cleanup.set_current(next_file_id);
output = open_output(shard, next_file_id)?;
}
#[cfg(feature = "encryption")]
if let Some(ref mut enc) = output.enc_state {
enc.write_bytes(&output.tmp_file, output.file_id, &entry_bytes)?;
} else {
direct::pwrite_at(&output.tmp_file, &entry_bytes, output.write_offset)?;
}
#[cfg(not(feature = "encryption"))]
direct::pwrite_at(&output.tmp_file, &entry_bytes, output.write_offset)?;
output.seqs.observe(header.sequence(), is_tombstone);
let value_offset =
output.write_offset + size_of::<EntryHeader>() as u64 + size_of::<K>() as u64;
debug_assert!(value_offset <= u32::MAX as u64);
let new_loc = DiskLoc::new(output.file_id, value_offset as u32, header.value_len);
batch.push(BatchEntry {
key,
gsn: header.gsn,
crc32: header.crc32,
old_loc,
new_loc,
is_tombstone,
});
output.write_offset += total;
offset += total;
}
direct::fadvise_dontneed(&scan_file, 0, file_len);
}
if output.write_offset > 0 {
let last_output = finalize_output(shard, output)?;
cleanup.mark_finalized(last_output.file_id);
pending_outputs.push(last_output);
} else {
let tmp_data_path = shard.dir().join(format!("{:06}.data.tmp", output.file_id));
let _ = std::fs::remove_file(&tmp_data_path);
#[cfg(feature = "encryption")]
{
let tmp_tags_path = shard.dir().join(format!("{:06}.tags.tmp", output.file_id));
let _ = std::fs::remove_file(&tmp_tags_path);
let _ = std::fs::remove_file(keys_path_for_data(&tmp_data_path));
}
cleanup.clear_current();
}
#[cfg(feature = "encryption")]
let new_immutables: Vec<Arc<ImmutableFile>> = pending_outputs
.iter()
.map(|out| {
let final_file = direct::open_serving_read(&out.final_data_path, serving_direct)?;
let final_tag_file = if let Some(ref tp) = out.final_tag_path {
Some(Arc::new(TagFile::open_read(tp)?))
} else {
None
};
Ok(Arc::new(ImmutableFile {
file: final_file,
file_id: out.file_id,
path: out.final_data_path.clone(),
total_bytes: out.total_bytes,
seqs: out.seqs,
tag_file: final_tag_file,
keys: out.keys.clone(),
}))
})
.collect::<DbResult<Vec<_>>>()?;
#[cfg(not(feature = "encryption"))]
let new_immutables: Vec<Arc<ImmutableFile>> = pending_outputs
.iter()
.map(|out| {
let final_file = direct::open_serving_read(&out.final_data_path, serving_direct)?;
Ok(Arc::new(ImmutableFile {
file: final_file,
file_id: out.file_id,
total_bytes: out.total_bytes,
seqs: out.seqs,
}))
})
.collect::<DbResult<Vec<_>>>()?;
{
let mut inner = shard.lock();
inner.immutable.extend(new_immutables);
inner.immutable.sort_by_key(|f| f.file_id);
inner.last_compaction_output_ids = pending_outputs.iter().map(|o| o.file_id).collect();
}
cleanup.disarm();
let mut compacted_entries = 0;
let key_len = size_of::<K>();
let mut physical_hint_data: std::collections::HashMap<u32, Vec<u8>> = pending_outputs
.iter()
.map(|o| (o.file_id, Vec::new()))
.collect();
for entry in &batch {
let buffer = physical_hint_data
.get_mut(&entry.new_loc.file_id)
.expect("every batch entry belongs to a finalized output");
append_hint_entry(
buffer,
entry.gsn,
&entry.key,
entry.new_loc.offset as u64,
entry.new_loc.len,
entry.crc32,
key_len,
);
}
#[cfg(test)]
run_before_deferred_cas_hook();
for chunk in batch.chunks(BATCH_SIZE) {
let mut inner = shard.lock();
for entry in chunk {
if entry.is_tombstone {
if index.contains_key(&entry.key) {
inner.add_dead_bytes(
entry.new_loc.file_id,
entry_size(size_of::<K>(), entry.new_loc.len),
);
} else {
compacted_entries += 1;
}
} else if index.update_if_match(&entry.key, entry.old_loc, entry.new_loc) {
compacted_entries += 1;
} else {
inner.add_dead_bytes(
entry.new_loc.file_id,
entry_size(size_of::<K>(), entry.new_loc.len),
);
}
}
}
{
let mut inner = shard.lock();
inner
.immutable
.retain(|f| !old_file_ids.contains(&f.file_id));
for fid in &old_file_ids {
inner.dead_bytes.remove(fid);
}
}
for old_arc in &files_to_compact {
index.invalidate_blocks(shard.id, old_arc.file_id, old_arc.total_bytes);
direct::fadvise_dontneed(&old_arc.file, 0, old_arc.total_bytes);
}
for out in &pending_outputs {
let entries = physical_hint_data.remove(&out.file_id).unwrap_or_default();
let hint_data = hint::hint_file_bytes(&entries, out.total_bytes, size_of::<K>())?;
let hint_path = shard.dir().join(format!("{:06}.hint", out.file_id));
hint::write_hint_file(&hint_path, &hint_data)?;
}
dir_fsync(shard.dir())?;
shard.flush()?;
for fid in &old_file_ids {
let _ = fs::remove_file(shard.dir().join(format!("{fid:06}.data")));
}
#[cfg(feature = "encryption")]
if shard.lock().key_domain.is_some() {
dir_fsync(shard.dir())?;
}
for fid in &old_file_ids {
let _ = fs::remove_file(shard.dir().join(format!("{fid:06}.hint")));
#[cfg(feature = "encryption")]
for suffix in ["tags", "keys", "keys.tmp"] {
let _ = fs::remove_file(shard.dir().join(format!("{fid:06}.{suffix}")));
}
}
dir_fsync(shard.dir())?;
let elapsed = compact_start.elapsed().as_secs_f64();
metrics::counter!("armdb.compaction.runs").increment(1);
metrics::counter!("armdb.compaction.entries").increment(compacted_entries as u64);
metrics::histogram!("armdb.compaction.duration_seconds").record(elapsed);
tracing::info!(
entries = compacted_entries,
files = old_file_ids.len(),
elapsed_ms = (elapsed * 1000.0) as u64,
"compaction complete"
);
Ok(compacted_entries)
}
fn open_output(shard: &Shard, file_id: u32) -> DbResult<OutputState> {
#[cfg(test)]
OPEN_OUTPUT_CALLS.with(|calls| calls.set(calls.get() + 1));
let tmp_path = shard.dir().join(format!("{file_id:06}.data.tmp"));
match fs::remove_file(&tmp_path) {
Ok(()) => {}
Err(e) if e.kind() == std::io::ErrorKind::NotFound => {}
Err(e) => return Err(e.into()),
}
#[cfg(feature = "encryption")]
let domain = shard.lock().key_domain.clone();
#[cfg(feature = "encryption")]
let output_cipher = match domain.as_deref() {
Some(domain) => {
let (salt, cipher) = domain.new_range()?;
KeyFile::create(
&keys_path_for_data(&tmp_path),
KeyRecord {
first_page: 0,
salt,
},
)?;
Some(Arc::new(cipher))
}
None => None,
};
#[cfg(test)]
if FAIL_OPEN_OUTPUT_AT
.with(|at| at.get() != 0 && at.get() == OPEN_OUTPUT_CALLS.with(|n| n.get()))
{
return Err(crate::error::DbError::Internal("test: open_output fault"));
}
let tmp_file = direct::open_bulk_write(&tmp_path)?;
Ok(OutputState {
file_id,
tmp_file,
write_offset: 0,
seqs: FileSeqs::EMPTY,
#[cfg(feature = "encryption")]
enc_state: output_cipher.map(|cipher| EncryptionState {
cipher,
page_buf: Box::new([0u8; 4096]),
page_offset: 0,
pages_written: 0,
tag_list: Vec::new(),
}),
})
}
fn finalize_output(shard: &Shard, output: OutputState) -> DbResult<FinalizedOutput> {
let file_id = output.file_id;
let tmp_path = shard.dir().join(format!("{file_id:06}.data.tmp"));
let final_data_path = shard.dir().join(format!("{file_id:06}.data"));
#[cfg(feature = "encryption")]
let (total_bytes, final_tag_path, keys) = match output.enc_state {
Some(mut enc) => {
if enc.page_offset > 0 {
enc.flush_page(&output.tmp_file, file_id)?;
}
let tp = shard.dir().join(format!("{file_id:06}.tags.tmp"));
match fs::remove_file(&tp) {
Ok(()) => {}
Err(e) if e.kind() == std::io::ErrorKind::NotFound => {}
Err(e) => return Err(e.into()),
}
let tf = TagFile::open_write(&tp)?;
tf.write_tags(0, &enc.tag_list)?;
tf.sync()?;
let final_tags_path = shard.dir().join(format!("{file_id:06}.tags"));
direct::fsync(&output.tmp_file)?;
fs::rename(&tp, &final_tags_path)?;
fs::rename(
keys_path_for_data(&tmp_path),
keys_path_for_data(&final_data_path),
)?;
dir_fsync(shard.dir())?;
#[cfg(test)]
if CRASH_BETWEEN_RENAMES.with(|c| c.get()) {
return Err(crate::error::DbError::Internal(
"test: crash between finalize renames",
));
}
fs::rename(&tmp_path, &final_data_path)?;
dir_fsync(shard.dir())?;
(
enc.pages_written * 4096,
Some(final_tags_path),
Some(Arc::new(FileKeys::single(0, enc.cipher))),
)
}
None => {
direct::fsync(&output.tmp_file)?;
fs::rename(&tmp_path, &final_data_path)?;
dir_fsync(shard.dir())?;
(output.write_offset, None, None)
}
};
#[cfg(not(feature = "encryption"))]
{
direct::fsync(&output.tmp_file)?;
fs::rename(&tmp_path, &final_data_path)?;
dir_fsync(shard.dir())?;
}
Ok(FinalizedOutput {
file_id,
#[cfg(feature = "encryption")]
total_bytes,
#[cfg(not(feature = "encryption"))]
total_bytes: output.write_offset,
seqs: output.seqs,
final_data_path,
#[cfg(feature = "encryption")]
final_tag_path,
#[cfg(feature = "encryption")]
keys,
})
}
pub struct Compactor {
stop: crate::shutdown::ShutdownSignal,
handle: Option<std::thread::JoinHandle<()>>,
}
impl Compactor {
pub fn start(
compact_fn: impl Fn() -> DbResult<usize> + Send + 'static,
interval: Duration,
) -> Self {
Self::start_with_signal(compact_fn, interval, crate::shutdown::ShutdownSignal::new())
}
pub fn start_with_signal(
compact_fn: impl Fn() -> DbResult<usize> + Send + 'static,
interval: Duration,
signal: crate::shutdown::ShutdownSignal,
) -> Self {
let stop = signal.clone();
let handle = std::thread::spawn(move || {
while !stop.is_shutdown() {
if stop.wait_timeout(interval) {
break;
}
match compact_fn() {
Ok(n) if n > 0 => tracing::info!(entries = n, "compaction cycle"),
Err(e) => tracing::error!(error = %e, "compaction error"),
_ => {}
}
}
});
Self {
stop: signal,
handle: Some(handle),
}
}
pub fn stop(&mut self) {
self.stop.shutdown();
if let Some(h) = self.handle.take() {
let _ = h.join();
}
}
}
impl Drop for Compactor {
fn drop(&mut self) {
self.stop();
}
}
fn append_hint_entry<K: Key>(
buf: &mut Vec<u8>,
gsn: u64,
key: &K,
value_offset: u64,
value_len: u32,
crc32: u32,
_key_len: usize,
) {
buf.extend_from_slice(&gsn.to_ne_bytes());
buf.extend_from_slice(key.as_bytes());
buf.extend_from_slice(&value_offset.to_ne_bytes());
buf.extend_from_slice(&value_len.to_ne_bytes());
buf.extend_from_slice(&crc32.to_ne_bytes());
}
fn file_max_seq(hint_path: &std::path::Path) -> Option<u64> {
let header = hint::read_hint_header(hint_path).ok()??;
Some(header.max_gsn & crate::entry::SEQUENCE_MASK)
}
#[cfg(test)]
pub(crate) fn selected_file_ids_for_test(shard: &Shard, threshold: f64) -> Vec<u32> {
select_compaction_files(shard, threshold, u64::MAX)
.files
.into_iter()
.map(|file| file.file_id)
.collect()
}
#[cfg(test)]
mod compaction_output_rotation_tests {
use super::*;
#[test]
fn output_should_rotate_when_offset_plus_needed_exceeds_limit() {
assert!(!should_rotate_output(0, 4096, 64 * 4096));
assert!(!should_rotate_output(60 * 4096, 4096, 64 * 4096));
assert!(should_rotate_output(63 * 4096, 4096 + 1, 64 * 4096));
assert!(should_rotate_output(
u32::MAX as u64 - 10,
100,
u32::MAX as u64
));
}
}
#[cfg(test)]
mod compaction_padding_tests {
use super::*;
use crate::Config;
use crate::ConstTree;
use crate::entry::serialize_entry;
use crate::hint::{generate_hint_data_dyn, hint_path_for_data, write_hint_file};
use tempfile::tempdir;
fn install_padded_immutable_file(shard_dir: &std::path::Path) -> u64 {
let key_a = 1u64.to_be_bytes();
let key_b = 2u64.to_be_bytes();
let val_a_old = [0xAAu8; 8];
let val_a_new = [0xCCu8; 8];
let val_b = [0xBBu8; 8];
let e1 = serialize_entry(1, &key_a, &val_a_old, false);
let e2 = serialize_entry(3, &key_a, &val_a_new, false);
let e3 = serialize_entry(4, &key_b, &val_b, false);
let mut file_bytes = Vec::new();
file_bytes.extend_from_slice(&e1);
let pad = 4096 - (file_bytes.len() % 4096);
file_bytes.extend(std::iter::repeat_n(0u8, pad));
file_bytes.extend_from_slice(&e2);
file_bytes.extend_from_slice(&e3);
let file_len = file_bytes.len() as u64;
let path = shard_dir.join("000001.data");
let f = direct::open_bulk_write(&path).unwrap();
direct::pwrite_at(&f, &file_bytes, 0).unwrap();
direct::fsync(&f).unwrap();
drop(f);
let rf = direct::open_bulk_read(&path).unwrap();
let hint_data = generate_hint_data_dyn(&rf, file_len, size_of::<[u8; 8]>()).unwrap();
write_hint_file(&hint_path_for_data(&path), &hint_data).unwrap();
let path2 = shard_dir.join("000002.data");
drop(direct::open_serving_write(&path2, false).unwrap());
file_len
}
#[test]
fn compaction_skips_mid_file_padding() {
let dir = tempdir().unwrap();
let mut config = Config::test();
config.shard_count = 1;
config.compaction_threshold = 0.0;
{
let tree = ConstTree::<[u8; 8], 8>::open(dir.path(), config.clone()).unwrap();
drop(tree);
}
let shard_dir = dir.path().join("shard_000");
let _file_len = install_padded_immutable_file(&shard_dir);
let tree = ConstTree::<[u8; 8], 8>::open(dir.path(), config).unwrap();
assert_eq!(tree.len(), 2);
let compacted = tree.compact().unwrap();
assert!(
compacted > 0,
"compaction should run on padded immutable file"
);
let key_a = 1u64.to_be_bytes();
let key_b = 2u64.to_be_bytes();
assert_eq!(tree.get(&key_a), Some([0xCC; 8]));
assert_eq!(tree.get(&key_b), Some([0xBB; 8]));
let hint_path = shard_dir.join("000003.hint");
if hint_path.exists() {
let data = std::fs::read(&hint_path).unwrap();
let entry_sz = crate::hint::hint_entry_size(size_of::<[u8; 8]>());
let (_, entries) = crate::hint::parse_hint_header(&data).expect("v3 hint header");
assert!(
!entries.is_empty() && entries.len().is_multiple_of(entry_sz),
"compaction hint entries {} not aligned to entry size {entry_sz}",
entries.len()
);
let parsed: Vec<_> = crate::hint::parse_hint_entries::<[u8; 8]>(&data).collect();
assert!(!parsed.is_empty());
}
}
fn padding_reopen_config(hints: bool) -> Config {
let mut config = Config::test();
config.shard_count = 1;
config.max_file_size = 8192;
config.write_buffer_size = 8192;
config.direct_io = true;
config.hints = Some(hints);
config.compaction_threshold = 0.30;
#[cfg(feature = "encryption")]
{
config.encryption_key = Some([0x5A; 32]);
}
config
}
fn data_ids(shard_dir: &std::path::Path) -> std::collections::BTreeSet<u32> {
std::fs::read_dir(shard_dir)
.unwrap()
.filter_map(|entry| entry.ok())
.filter_map(|entry| {
let name = entry.file_name();
let name = name.to_str()?;
name.strip_suffix(".data")?.parse().ok()
})
.collect()
}
fn make_padding_immutable(tree: &ConstTree<[u8; 8], 8>) -> u32 {
tree.put(&1u64.to_be_bytes(), &[1; 8]).unwrap();
tree.durable_flush().unwrap();
for key in 2u64..=130 {
tree.put(&key.to_be_bytes(), &[key as u8; 8]).unwrap();
}
1
}
#[test]
fn padding_dead_reopen_keeps_immutable_file_selectable_with_and_without_hints() {
for hints in [false, true] {
let dir = tempdir().unwrap();
let config = padding_reopen_config(hints);
let padded_file_id = {
let tree = ConstTree::<[u8; 8], 8>::open(dir.path(), config.clone()).unwrap();
let file_id = make_padding_immutable(&tree);
assert!(
tree.selected_compaction_file_ids_for_test()
.contains(&file_id),
"runtime padding must select its immutable file (hints={hints})"
);
tree.close().unwrap();
file_id
};
let data_path = dir.path().join("shard_000/000001.data");
let scans = std::sync::Arc::new(std::sync::atomic::AtomicUsize::new(0));
let _probe = crate::recovery::observe_full_scans_for(data_path, scans.clone());
let tree = ConstTree::<[u8; 8], 8>::open(dir.path(), config).unwrap();
assert!(
tree.selected_compaction_file_ids_for_test()
.contains(&padded_file_id),
"recovery must select the same padding-heavy file (hints={hints})"
);
assert_eq!(
scans.load(std::sync::atomic::Ordering::Relaxed),
usize::from(!hints),
"hints={hints} must use its intended recovery path"
);
tree.close().unwrap();
}
}
#[test]
fn padding_dead_compaction_output_recovery_is_exact() {
for hints in [false, true] {
let dir = tempdir().unwrap();
let config = padding_reopen_config(hints);
let shard_dir = dir.path().join("shard_000");
let output_id = {
let tree = ConstTree::<[u8; 8], 8>::open(dir.path(), config.clone()).unwrap();
let input_id = make_padding_immutable(&tree);
assert!(
tree.selected_compaction_file_ids_for_test()
.contains(&input_id)
);
let before = data_ids(&shard_dir);
assert!(tree.compact().unwrap() > 0);
let after = data_ids(&shard_dir);
let output_id = *after.difference(&before).next().expect("compaction output");
tree.close().unwrap();
output_id
};
let tree = ConstTree::<[u8; 8], 8>::open(dir.path(), config).unwrap();
#[cfg(feature = "encryption")]
let expected_padding = 4096 - crate::entry::entry_size(8, 8);
#[cfg(not(feature = "encryption"))]
let expected_padding = 0;
assert_eq!(
tree.dead_bytes_for_test(output_id),
expected_padding as u64,
"recovery must restore padding for the exact compaction output {output_id} (hints={hints})"
);
tree.close().unwrap();
}
}
}
#[cfg(test)]
mod compaction_file_max_seq_tests {
use super::*;
use tempfile::tempdir;
fn write_hint_entries(path: &std::path::Path, gsns: &[u64]) {
let key_len = 8usize;
let entry_size = crate::hint::hint_entry_size(key_len);
let mut entries = vec![0u8; entry_size * gsns.len()];
for (index, gsn) in gsns.iter().enumerate() {
let start = index * entry_size;
entries[start..start + 8].copy_from_slice(&gsn.to_ne_bytes());
}
let bytes = crate::hint::hint_file_bytes(&entries, 0, key_len).unwrap();
std::fs::write(path, bytes).unwrap();
}
#[test]
fn file_max_seq_uses_sequence_bits() {
let dir = tempdir().unwrap();
let hint_path = dir.path().join("000001.hint");
write_hint_entries(&hint_path, &[300 | crate::entry::TOMBSTONE_BIT, 100, 200]);
assert_eq!(file_max_seq(&hint_path), Some(300));
}
#[test]
fn file_max_seq_returns_none_for_missing_file() {
let dir = tempdir().unwrap();
assert_eq!(file_max_seq(&dir.path().join("000002.hint")), None);
}
#[test]
fn file_max_seq_returns_none_for_a_corrupt_header() {
let dir = tempdir().unwrap();
let hint_path = dir.path().join("000003.hint");
write_hint_entries(&hint_path, &[10, 20]);
let mut bytes = std::fs::read(&hint_path).unwrap();
bytes[8] ^= 0xff; std::fs::write(&hint_path, bytes).unwrap();
assert_eq!(file_max_seq(&hint_path), None);
}
#[test]
fn file_max_seq_returns_none_for_a_header_shorter_than_the_format() {
let dir = tempdir().unwrap();
let hint_path = dir.path().join("000004.hint");
std::fs::write(&hint_path, [0u8; 8]).unwrap();
assert_eq!(file_max_seq(&hint_path), None);
}
#[test]
fn file_max_seq_reads_the_header_without_the_payload() {
let dir = tempdir().unwrap();
let hint_path = dir.path().join("000005.hint");
write_hint_entries(&hint_path, &[10, 20]);
let mut bytes = std::fs::read(&hint_path).unwrap();
bytes[crate::hint::HINT_HEADER_SIZE] ^= 0xff;
std::fs::write(&hint_path, bytes).unwrap();
assert_eq!(file_max_seq(&hint_path), Some(20));
}
}
#[cfg(test)]
mod compaction_data_loss_tests {
use super::*;
use crate::Config;
use crate::ConstTree;
use crate::entry::{EntryHeader, compute_crc32, serialize_entry};
use crate::hint::{hint_path_for_data, write_hint_file};
use std::path::Path;
use tempfile::tempdir;
use zerocopy::IntoBytes;
fn install_corrupt_immutable_file(
shard_dir: &std::path::Path,
key_a: &[u8; 8],
val_a_new: &[u8; 8],
key_b: &[u8; 8],
val_b: &[u8; 8],
) {
let val_a_old = [0xAAu8; 8];
let e_a_stale = serialize_entry(1, key_a, &val_a_old, false); let e_a_live = serialize_entry(3, key_a, val_a_new, false); let poison = EntryHeader {
gsn: 7,
crc32: 0x1,
value_len: 0xFFFF_FF00, };
let e_b = serialize_entry(4, key_b, val_b, false);
let mut file_bytes = Vec::new();
file_bytes.extend_from_slice(&e_a_stale);
file_bytes.extend_from_slice(&e_a_live);
file_bytes.extend_from_slice(poison.as_bytes()); let b_off = file_bytes.len(); file_bytes.extend_from_slice(&e_b);
let file_len = file_bytes.len() as u64;
let path = shard_dir.join("000001.data");
let f = direct::open_bulk_write(&path).unwrap();
direct::pwrite_at(&f, &file_bytes, 0).unwrap();
direct::fsync(&f).unwrap();
drop(f);
let mut hint = Vec::new();
append_hint_entry::<[u8; 8]>(
&mut hint,
1,
key_a,
24,
8,
compute_crc32(1, 8, key_a, &val_a_old),
8,
);
append_hint_entry::<[u8; 8]>(
&mut hint,
3,
key_a,
56,
8,
compute_crc32(3, 8, key_a, val_a_new),
8,
);
append_hint_entry::<[u8; 8]>(
&mut hint,
4,
key_b,
(b_off + 24) as u64,
8,
compute_crc32(4, 8, key_b, val_b),
8,
);
write_hint_file(
&hint_path_for_data(&path),
&hint::hint_file_bytes(&hint, file_len, 8).unwrap(),
)
.unwrap();
let path2 = shard_dir.join("000002.data");
drop(direct::open_serving_write(&path2, false).unwrap());
}
#[test]
fn compaction_aborts_on_corruption_and_preserves_live_tail() {
let dir = tempdir().unwrap();
let mut config = Config::test();
config.shard_count = 1;
config.compaction_threshold = 0.0;
{
let tree = ConstTree::<[u8; 8], 8>::open(dir.path(), config.clone()).unwrap();
drop(tree);
}
let shard_dir = dir.path().join("shard_000");
let key_a = 1u64.to_be_bytes();
let key_b = 2u64.to_be_bytes();
let val_a_new = [0xCCu8; 8];
let val_b = [0xBBu8; 8];
install_corrupt_immutable_file(&shard_dir, &key_a, &val_a_new, &key_b, &val_b);
let tree = ConstTree::<[u8; 8], 8>::open(dir.path(), config.clone()).unwrap();
assert_eq!(tree.len(), 2, "both live entries recovered from the hint");
assert_eq!(tree.get(&key_b), Some(val_b));
let result = tree.compact();
assert!(
result.is_err(),
"compaction must abort on the corrupt entry, got {result:?}"
);
assert!(
shard_dir.join("000001.data").exists(),
"source file must be preserved on abort (holds live tail entry B)"
);
drop(tree);
let tree = ConstTree::<[u8; 8], 8>::open(dir.path(), config).unwrap();
assert_eq!(
tree.get(&key_b),
Some(val_b),
"live tail entry B must survive a corruption-aborted compaction"
);
assert_eq!(tree.get(&key_a), Some(val_a_new));
}
fn count_data_files(dir: &std::path::Path) -> (usize, usize) {
let mut data = 0;
let mut tmp = 0;
for e in std::fs::read_dir(dir).unwrap() {
let name = e.unwrap().file_name();
let name = name.to_string_lossy();
if name.ends_with(".data.tmp") {
tmp += 1;
} else if name.ends_with(".data") {
data += 1;
}
}
(data, tmp)
}
fn file_id_highest_data(shard_dir: &Path) -> u32 {
fs::read_dir(shard_dir)
.unwrap()
.filter_map(|entry| {
let path = entry.unwrap().path();
(path.extension()?.to_str()? == "data")
.then(|| path.file_stem()?.to_str()?.parse().ok())
.flatten()
})
.max()
.unwrap()
}
fn file_id_write_until_rotation(
tree: &ConstTree<[u8; 8], 8>,
shard_dir: &Path,
first_key: u64,
) -> u32 {
let before = file_id_highest_data(shard_dir);
for key in first_key..first_key + 10_000 {
tree.put(&key.to_be_bytes(), &key.to_be_bytes()).unwrap();
let highest = file_id_highest_data(shard_dir);
if highest > before {
return highest;
}
}
panic!("writes did not rotate");
}
#[cfg(feature = "encryption")]
#[test]
fn file_id_failed_pass_does_not_let_reopen_reissue_its_output_ids() {
let dir = tempdir().unwrap();
let mut config = Config::test();
config.shard_count = 1;
config.max_file_size = 8192;
config.write_buffer_size = 8192;
config.compaction_threshold = 0.1;
config.encryption_key = Some([0x42; 32]);
let tree = ConstTree::<[u8; 8], 8>::open(dir.path(), config.clone()).unwrap();
for i in 0..512u64 {
tree.put(&i.to_be_bytes(), &i.to_be_bytes()).unwrap();
}
for i in (0..512u64).step_by(4) {
tree.put(&i.to_be_bytes(), &(i + 1_000_000).to_be_bytes())
.unwrap();
}
tree.flush().unwrap();
let shard_dir = dir.path().join("shard_000");
let a = file_id_highest_data(&shard_dir);
OPEN_OUTPUT_CALLS.with(|c| c.set(0));
FAIL_OPEN_OUTPUT_AT.with(|c| c.set(2));
let result = tree.compact();
FAIL_OPEN_OUTPUT_AT.with(|c| c.set(0));
assert!(result.is_err());
assert!(
OPEN_OUTPUT_CALLS.with(|c| c.get()) >= 2,
"test precondition: output rotation"
);
drop(tree);
let tree = ConstTree::<[u8; 8], 8>::open(dir.path(), config).unwrap();
assert!(file_id_write_until_rotation(&tree, &shard_dir, 1_000_000) >= a + 3);
}
#[test]
fn file_id_empty_output_pass_then_clean_reopen_does_not_reissue_its_id() {
let dir = tempdir().unwrap();
let mut config = Config::test();
config.shard_count = 1;
config.max_file_size = 4096;
config.write_buffer_size = 4096;
config.compaction_threshold = 0.99;
let tree = ConstTree::<[u8; 8], 8>::open(dir.path(), config.clone()).unwrap();
for i in 0..512u64 {
tree.put(&i.to_be_bytes(), &i.to_be_bytes()).unwrap();
}
for i in 0..512u64 {
tree.put(&i.to_be_bytes(), &(i + 1_000_000).to_be_bytes())
.unwrap();
}
tree.flush().unwrap();
let shard_dir = dir.path().join("shard_000");
let a = file_id_highest_data(&shard_dir);
OPEN_OUTPUT_CALLS.with(|c| c.set(0));
tree.compact().unwrap();
assert!(
OPEN_OUTPUT_CALLS.with(|c| c.get()) >= 1,
"test precondition: an output was opened"
);
assert_eq!(
file_id_highest_data(&shard_dir),
a,
"test precondition: output was empty and removed"
);
drop(tree);
let tree = ConstTree::<[u8; 8], 8>::open(dir.path(), config).unwrap();
assert!(file_id_write_until_rotation(&tree, &shard_dir, 1_000_000) >= a + 2);
}
#[test]
fn compaction_rotation_failure_leaves_no_orphan_outputs() {
let dir = tempdir().unwrap();
let mut config = Config::test();
config.shard_count = 1;
config.max_file_size = 4096;
config.write_buffer_size = 4096;
config.compaction_threshold = 0.1;
let tree = ConstTree::<[u8; 8], 8>::open(dir.path(), config).unwrap();
for i in 0..512u64 {
tree.put(&i.to_be_bytes(), &i.to_be_bytes()).unwrap();
}
for i in (0..512u64).step_by(4) {
tree.put(&i.to_be_bytes(), &(i + 1_000_000).to_be_bytes())
.unwrap();
}
tree.flush().unwrap();
let shard_dir = dir.path().join("shard_000");
let (data_before, _) = count_data_files(&shard_dir);
OPEN_OUTPUT_CALLS.with(|c| c.set(0));
FAIL_OPEN_OUTPUT_AT.with(|c| c.set(2));
let result = tree.compact();
FAIL_OPEN_OUTPUT_AT.with(|c| c.set(0));
assert!(
result.is_err(),
"the injected rotation-open fault must surface, got {result:?}"
);
assert!(
OPEN_OUTPUT_CALLS.with(|c| c.get()) >= 2,
"test precondition: compaction must rotate the output at least once"
);
let (data_after, tmp_after) = count_data_files(&shard_dir);
assert_eq!(
tmp_after, 0,
"no leftover .data.tmp after the aborted compaction"
);
assert_eq!(
data_after, data_before,
"OutputGuard must remove the finalized-but-unregistered orphan output"
);
}
}
#[cfg(test)]
#[cfg(feature = "encryption")]
mod compaction_encrypted_crash_tests {
use super::*;
use crate::Config;
use crate::ConstTree;
use tempfile::tempdir;
use std::collections::BTreeMap;
use std::path::Path;
use std::sync::Mutex;
use std::sync::atomic::AtomicU64;
#[derive(Default)]
struct Index(Mutex<BTreeMap<[u8; 8], DiskLoc>>);
impl CompactionIndex<[u8; 8]> for Index {
fn update_if_match(&self, key: &[u8; 8], old: DiskLoc, new: DiskLoc) -> bool {
let mut index = self.0.lock().unwrap();
if index.get(key) != Some(&old) {
return false;
}
index.insert(*key, new);
true
}
fn contains_key(&self, key: &[u8; 8]) -> bool {
self.0.lock().unwrap().contains_key(key)
}
fn is_live(&self, _: u8, key: &[u8; 8], loc: DiskLoc) -> bool {
self.0.lock().unwrap().get(key) == Some(&loc)
}
}
fn range_shard(dir: &Path, gsn: Arc<AtomicU64>) -> Shard {
Shard::open_encrypted(
0,
dir,
8192,
8192,
false,
false,
false,
crate::config::IoBackend::default(),
Some(Arc::new(
crate::crypto::KeyDomain::new(&[0x42; 32], &[0x24; 16], None, 0).unwrap(),
)),
gsn,
)
.unwrap()
}
fn mixed_sources(dir: &Path) -> (Shard, Index, Arc<AtomicU64>) {
let gsn = Arc::new(AtomicU64::new(0));
let index = Index::default();
for session in 0..4u64 {
let shard = range_shard(dir, gsn.clone());
{
let mut inner = shard.lock();
for key in session * 128..(session + 1) * 128 {
let loc = inner
.append_entry(0, &key.to_be_bytes(), &(key + 1000).to_be_bytes(), false)
.unwrap()
.0;
index.0.lock().unwrap().insert(key.to_be_bytes(), loc);
}
}
shard.flush().unwrap();
if session == 3 {
shard.rotate_active_for_test(8).unwrap();
}
}
let shard = range_shard(dir, gsn.clone());
for key in [0u64, 256] {
let old = index.0.lock().unwrap().remove(&key.to_be_bytes()).unwrap();
shard.lock().dead_bytes.insert(old.file_id, 32);
}
for id in source_ids(&shard) {
assert_eq!(
KeyFile::open(&dir.join(format!("{id:06}.keys")))
.unwrap()
.1
.len(),
2
);
}
(shard, index, gsn)
}
fn source_ids(shard: &Shard) -> Vec<u32> {
let ids: Vec<_> = shard
.lock()
.immutable
.iter()
.map(|file| file.file_id)
.collect();
assert_eq!(ids.len(), 2);
ids
}
fn assert_no_orphan_keys(dir: &Path) {
for entry in fs::read_dir(dir).unwrap() {
let name = entry.unwrap().file_name().into_string().unwrap();
if let Some(id) = name.strip_suffix(".keys") {
assert!(dir.join(format!("{id}.data")).exists(), "orphan {name}");
}
assert!(!name.ends_with(".keys.tmp"), "orphan {name}");
}
}
#[test]
fn keyrange_compaction_output_gets_its_own_range_and_reads_mixed_sources() {
let dir = tempdir().unwrap();
let (shard, index, gsn) = mixed_sources(dir.path());
let source_salts: Vec<_> = source_ids(&shard)
.into_iter()
.flat_map(|id| {
KeyFile::open(&dir.path().join(format!("{id:06}.keys")))
.unwrap()
.1
.into_iter()
.map(|record| record.salt)
})
.collect();
assert_eq!(compact_shard(&shard, &index, 0.0).unwrap(), 510);
let outputs: Vec<_> = shard
.lock()
.immutable
.iter()
.map(|file| file.file_id)
.collect();
assert!(!outputs.is_empty());
for id in outputs {
let records = KeyFile::open(&dir.path().join(format!("{id:06}.keys")))
.unwrap()
.1;
assert_eq!(records.len(), 1);
assert_eq!(records[0].first_page, 0);
assert!(!source_salts.contains(&records[0].salt));
}
drop(shard);
let reopened = range_shard(dir.path(), gsn);
for (key, loc) in index.0.lock().unwrap().iter() {
let key = u64::from_be_bytes(*key);
assert_eq!(
reopened.lock().read_value_from_disk_locked(loc).unwrap(),
(key + 1000).to_be_bytes()
);
}
}
#[test]
fn keyrange_compaction_failure_removes_keys_tmp() {
for (fail_open_at, between_renames) in [(1, false), (2, false), (0, true)] {
let dir = tempdir().unwrap();
let (shard, index, _) = mixed_sources(dir.path());
OPEN_OUTPUT_CALLS.with(|cell| cell.set(0));
FAIL_OPEN_OUTPUT_AT.with(|cell| cell.set(fail_open_at));
CRASH_BETWEEN_RENAMES.with(|cell| cell.set(between_renames));
let result = compact_shard(&shard, &index, 0.0);
FAIL_OPEN_OUTPUT_AT.with(|cell| cell.set(0));
CRASH_BETWEEN_RENAMES.with(|cell| cell.set(false));
assert!(result.is_err());
for id in source_ids(&shard) {
assert!(dir.path().join(format!("{id:06}.data")).exists());
assert!(dir.path().join(format!("{id:06}.keys")).exists());
}
assert_no_orphan_keys(dir.path());
}
}
#[test]
fn keyrange_compaction_source_delete_removes_its_keys() {
let dir = tempdir().unwrap();
let (shard, index, _) = mixed_sources(dir.path());
let sources = source_ids(&shard);
assert_eq!(compact_shard(&shard, &index, 0.0).unwrap(), 510);
for id in sources {
for suffix in ["data", "tags", "keys"] {
assert!(
!dir.path().join(format!("{id:06}.{suffix}")).exists(),
"source {id}.{suffix} survived"
);
}
}
assert_no_orphan_keys(dir.path());
}
#[test]
fn keyrange_compaction_empty_output_removes_keys_tmp() {
let dir = tempdir().unwrap();
let (shard, index, _) = mixed_sources(dir.path());
index.0.lock().unwrap().clear();
assert_eq!(compact_shard(&shard, &index, 0.0).unwrap(), 0);
assert_no_orphan_keys(dir.path());
}
#[cfg(feature = "replication")]
#[test]
fn keyrange_catchup_snapshot_survives_compaction_unlink() {
let dir = tempdir().unwrap();
let (shard, index, _) = mixed_sources(dir.path());
let sources = source_ids(&shard);
let snapshot = shard.catchup_snapshot().unwrap();
assert_eq!(compact_shard(&shard, &index, 0.0).unwrap(), 510);
for id in &sources {
for suffix in ["data", "tags", "keys"] {
assert!(!dir.path().join(format!("{id:06}.{suffix}")).exists());
}
}
let mut seen = Vec::new();
for file in &snapshot.files {
if !sources.contains(&file.file_id) {
continue;
}
assert_eq!(file.readable_end, 8192);
for row in 0..256u64 {
let entry = file.read_exact_at(row * 32, 32).unwrap();
let key = u64::from_be_bytes(entry[16..24].try_into().unwrap());
assert_eq!(entry[24..32], (key + 1000).to_be_bytes());
seen.push(key);
}
}
assert_eq!(seen, (0..512).collect::<Vec<_>>());
}
#[test]
fn crash_between_finalize_renames_reopens_cleanly() {
let dir = tempdir().unwrap();
let key = [0x42u8; 32];
let mut config = Config::test();
config.encryption_key = Some(key);
config.shard_count = 1;
config.max_file_size = 8192;
config.write_buffer_size = 8192;
config.compaction_threshold = 0.1;
let tree = ConstTree::<[u8; 8], 8>::open(dir.path(), config.clone()).unwrap();
for i in 0..500u64 {
tree.put(&i.to_be_bytes(), &i.to_be_bytes()).unwrap();
}
for i in 0..250u64 {
tree.put(&i.to_be_bytes(), &(i + 1000).to_be_bytes())
.unwrap();
}
CRASH_BETWEEN_RENAMES.with(|c| c.set(true));
let result = tree.compact();
CRASH_BETWEEN_RENAMES.with(|c| c.set(false));
assert!(
result.is_err(),
"the injected crash must surface, got {result:?}"
);
for i in 1000..1400u64 {
tree.put(&i.to_be_bytes(), &i.to_be_bytes()).unwrap();
}
drop(tree);
let tree = ConstTree::<[u8; 8], 8>::open(dir.path(), config)
.expect("DB must reopen after a crash between finalize renames");
for i in 0..500u64 {
let expected = if i < 250 {
(i + 1000).to_be_bytes()
} else {
i.to_be_bytes()
};
assert_eq!(
tree.get(&i.to_be_bytes()).unwrap(),
expected,
"post-crash reopen mismatch at key {i}"
);
}
}
}