use std::cmp::Ordering;
use std::collections::HashSet;
use std::hash::Hash;
use std::sync::Arc;
use durability::checkpoint::CheckpointFile;
use durability::recordlog::{RecordLogReadMode, RecordLogReader, RecordLogWriter};
use durability::{Directory, PersistenceError, PersistenceResult};
use serde::{de::DeserializeOwned, Deserialize, Serialize};
const WAL_PREFIX: &str = "segstore.wal.";
const LEGACY_WAL_PATH: &str = "segstore.wal";
const CKPT_PATH: &str = "segstore.ckpt";
fn wal_path(epoch: u64) -> String {
format!("{WAL_PREFIX}{epoch}")
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SyncPolicy {
Flush,
Fsync,
}
#[derive(Debug, Clone, Copy)]
pub struct TierConfig {
pub min_merge: usize,
pub max_merge: usize,
pub bucket_low: f64,
pub bucket_high: f64,
pub max_merged_len: usize,
}
impl Default for TierConfig {
fn default() -> Self {
Self {
min_merge: 4,
max_merge: 32,
bucket_low: 0.5,
bucket_high: 1.5,
max_merged_len: 10_000_000,
}
}
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct CompactionStats {
pub merges: usize,
pub segments_before: usize,
pub segments_after: usize,
pub items_merged: usize,
}
#[derive(Debug, Clone, Copy)]
pub struct Options {
pub flush_threshold: usize,
pub sync: SyncPolicy,
pub tiering: TierConfig,
pub auto_compact: bool,
}
impl Options {
pub fn new(flush_threshold: usize) -> Self {
Self {
flush_threshold,
sync: SyncPolicy::Flush,
tiering: TierConfig::default(),
auto_compact: false,
}
}
}
pub trait Store {
type Id: Clone + Eq + Hash + Serialize + DeserializeOwned;
type Item: Clone + Serialize + DeserializeOwned;
type Segment: Clone + Serialize + DeserializeOwned;
fn build_segment(&self, batch: &[(Self::Id, Self::Item)]) -> Self::Segment;
fn merge_segments(
&self,
segments: &[Self::Segment],
live: &dyn Fn(&Self::Id) -> bool,
) -> Self::Segment;
fn segment_len(&self, segment: &Self::Segment) -> usize;
fn live_len(
&self,
_segment: &Self::Segment,
_live: &dyn Fn(&Self::Id) -> bool,
) -> Option<usize> {
None
}
}
#[derive(Serialize, Deserialize)]
enum Op<Id, Item> {
Add(Id, Item),
Delete(Id),
}
#[derive(Serialize, Deserialize)]
struct Snapshot<Id, Seg> {
segments: Vec<Seg>,
tombstones: Vec<Id>,
}
struct PubState<S: Store> {
segments: Arc<Vec<Arc<S::Segment>>>,
tombstones: Arc<HashSet<S::Id>>,
}
pub struct View<S: Store> {
segments: Arc<Vec<Arc<S::Segment>>>,
tombstones: Arc<HashSet<S::Id>>,
}
impl<S: Store> View<S> {
pub fn segments(&self) -> &[Arc<S::Segment>] {
&self.segments
}
pub fn is_live(&self, id: &S::Id) -> bool {
!self.tombstones.contains(id)
}
pub fn segment_count(&self) -> usize {
self.segments.len()
}
}
pub struct Reader<S: Store> {
published: Arc<std::sync::RwLock<Arc<PubState<S>>>>,
}
impl<S: Store> Clone for Reader<S> {
fn clone(&self) -> Self {
Reader {
published: self.published.clone(),
}
}
}
impl<S: Store> Reader<S> {
pub fn view(&self) -> View<S> {
let state = self.published.read().unwrap().clone();
View {
segments: state.segments.clone(),
tombstones: state.tombstones.clone(),
}
}
}
pub struct SegmentedStore<S: Store> {
store: S,
dir: Arc<dyn Directory>,
buffer: Vec<(S::Id, S::Item)>,
segments: Vec<Arc<S::Segment>>,
tombstones: HashSet<S::Id>,
published: Arc<std::sync::RwLock<Arc<PubState<S>>>>,
wal: RecordLogWriter,
epoch: u64,
sync: SyncPolicy,
flush_threshold: usize,
tiering: TierConfig,
auto_compact: bool,
}
impl<S: Store> SegmentedStore<S> {
pub fn open(
dir: Arc<dyn Directory>,
store: S,
flush_threshold: usize,
) -> PersistenceResult<Self> {
Self::open_with_options(dir, store, Options::new(flush_threshold))
}
pub fn open_with_options(
dir: Arc<dyn Directory>,
store: S,
opts: Options,
) -> PersistenceResult<Self> {
let Options {
flush_threshold,
sync,
tiering,
auto_compact,
} = opts;
if sync == SyncPolicy::Fsync && dir.file_path(CKPT_PATH).is_none() {
return Err(PersistenceError::InvalidConfig(
"SyncPolicy::Fsync requires a filesystem-backed Directory".into(),
));
}
if dir.exists(LEGACY_WAL_PATH) {
return Err(PersistenceError::InvalidConfig(
"segstore 0.1 on-disk store detected (unsuffixed segstore.wal); the 0.2 \
on-disk format is epoch-suffixed and cannot read it"
.into(),
));
}
let mut segments: Vec<Arc<S::Segment>> = Vec::new();
let mut tombstones: HashSet<S::Id> = HashSet::new();
let mut epoch = 0u64;
if dir.exists(CKPT_PATH) {
let ckpt = CheckpointFile::new(dir.clone());
let (e, snap): (u64, Snapshot<S::Id, S::Segment>) = ckpt.read_postcard(CKPT_PATH)?;
epoch = e;
segments = snap.segments.into_iter().map(Arc::new).collect();
tombstones = snap.tombstones.into_iter().collect();
}
let mut buffer: Vec<(S::Id, S::Item)> = Vec::new();
let live_wal = wal_path(epoch);
if dir.exists(&live_wal) {
let reader = RecordLogReader::new(dir.clone(), live_wal.clone());
let ops: Vec<Op<S::Id, S::Item>> =
reader.read_all_postcard(RecordLogReadMode::BestEffort)?;
for op in ops {
apply(&mut buffer, &mut tombstones, op);
}
}
if let Ok(names) = dir.list_dir("") {
for name in names {
if let Some(k) = name
.strip_prefix(WAL_PREFIX)
.and_then(|s| s.parse::<u64>().ok())
{
if k != epoch {
let _ = dir.delete(&name);
}
}
}
}
let wal = RecordLogWriter::new(dir.clone(), live_wal);
let published = Arc::new(std::sync::RwLock::new(Arc::new(PubState {
segments: Arc::new(segments.clone()),
tombstones: Arc::new(tombstones.clone()),
})));
Ok(Self {
store,
dir,
buffer,
segments,
tombstones,
wal,
epoch,
sync,
flush_threshold,
tiering,
auto_compact,
published,
})
}
pub fn reader(&self) -> Reader<S> {
Reader {
published: self.published.clone(),
}
}
fn republish(&self) {
let state = Arc::new(PubState {
segments: Arc::new(self.segments.clone()),
tombstones: Arc::new(self.tombstones.clone()),
});
*self.published.write().unwrap() = state;
}
pub fn add(&mut self, id: S::Id, item: S::Item) -> PersistenceResult<()> {
self.wal
.append_postcard(&Op::Add(id.clone(), item.clone()))?;
self.sync_wal()?;
apply(&mut self.buffer, &mut self.tombstones, Op::Add(id, item));
if self.buffer.len() >= self.flush_threshold {
self.flush_buffer();
if self.auto_compact && self.has_eligible_tier() {
self.compact_tiers()?;
}
}
Ok(())
}
pub fn extend(
&mut self,
items: impl IntoIterator<Item = (S::Id, S::Item)>,
) -> PersistenceResult<()> {
let mut any = false;
for (id, item) in items {
self.wal
.append_postcard(&Op::Add(id.clone(), item.clone()))?;
apply(&mut self.buffer, &mut self.tombstones, Op::Add(id, item));
any = true;
if self.buffer.len() >= self.flush_threshold {
self.flush_buffer();
if self.auto_compact && self.has_eligible_tier() {
self.sync_wal()?; self.compact_tiers()?;
}
}
}
if any {
self.sync_wal()?;
}
Ok(())
}
pub fn delete(&mut self, id: S::Id) -> PersistenceResult<()> {
self.wal
.append_postcard::<Op<S::Id, S::Item>>(&Op::Delete(id.clone()))?;
self.sync_wal()?;
apply(&mut self.buffer, &mut self.tombstones, Op::Delete(id));
Ok(())
}
fn sync_wal(&mut self) -> PersistenceResult<()> {
match self.sync {
SyncPolicy::Flush => self.wal.flush(),
SyncPolicy::Fsync => self.wal.flush_and_sync(),
}
}
fn flush_buffer(&mut self) {
if self.buffer.is_empty() {
return;
}
let seg = self.store.build_segment(&self.buffer);
self.segments.push(Arc::new(seg));
self.buffer.clear();
}
pub fn compact(&mut self) -> PersistenceResult<CompactionStats> {
self.flush_buffer();
let before = self.segments.len();
let mut stats = CompactionStats {
segments_before: before,
..Default::default()
};
if before > 1 || (before == 1 && !self.tombstones.is_empty()) {
let tombstones = std::mem::take(&mut self.tombstones);
let owned: Vec<S::Segment> = self.segments.iter().map(|a| (**a).clone()).collect();
let merged = self
.store
.merge_segments(&owned, &|id| !tombstones.contains(id));
stats.merges = 1;
stats.items_merged = self.store.segment_len(&merged);
self.segments = if stats.items_merged > 0 {
vec![Arc::new(merged)]
} else {
vec![]
};
}
self.tombstones.clear();
self.checkpoint()?;
stats.segments_after = self.segments.len();
Ok(stats)
}
pub fn compact_tiers(&mut self) -> PersistenceResult<CompactionStats> {
self.flush_buffer();
let mut stats = CompactionStats {
segments_before: self.segments.len(),
..Default::default()
};
while let Some(group) = self.next_merge_group() {
stats.items_merged += self.merge_group(group);
stats.merges += 1;
}
if stats.merges > 0 {
self.checkpoint()?;
}
stats.segments_after = self.segments.len();
Ok(stats)
}
pub fn force_merge_to(&mut self, max_segments: usize) -> PersistenceResult<CompactionStats> {
if max_segments <= 1 {
return self.compact();
}
self.flush_buffer();
let mut stats = CompactionStats {
segments_before: self.segments.len(),
..Default::default()
};
while self.segments.len() > max_segments {
let mut idx: Vec<usize> = (0..self.segments.len()).collect();
idx.sort_by_key(|&i| self.store.segment_len(&self.segments[i]));
let over = self.segments.len() - max_segments;
let k = (over + 1)
.min(self.tiering.max_merge.max(2))
.min(self.segments.len());
let group: Vec<usize> = idx.into_iter().take(k).collect();
stats.items_merged += self.merge_group(group);
stats.merges += 1;
}
if stats.merges > 0 {
self.checkpoint()?;
}
stats.segments_after = self.segments.len();
Ok(stats)
}
fn merge_group(&mut self, indices: Vec<usize>) -> usize {
let segs: Vec<S::Segment> = indices
.iter()
.map(|&i| (*self.segments[i]).clone())
.collect();
let merged = {
let tombstones = &self.tombstones;
self.store
.merge_segments(&segs, &|id| !tombstones.contains(id))
};
let n = self.store.segment_len(&merged);
let mut merged_idx = indices;
merged_idx.sort_unstable();
let old = std::mem::take(&mut self.segments);
self.segments = old
.into_iter()
.enumerate()
.filter(|(i, _)| merged_idx.binary_search(i).is_err())
.map(|(_, seg)| seg)
.collect();
if n > 0 {
self.segments.push(Arc::new(merged));
}
n
}
pub fn has_eligible_tier(&self) -> bool {
self.next_merge_group().is_some()
}
fn next_merge_group(&self) -> Option<Vec<usize>> {
let cfg = self.tiering;
let min_merge = cfg.min_merge.max(2);
let floor = self.flush_threshold.max(1);
let cap_half = cfg.max_merged_len / 2;
let mut elig: Vec<(usize, f64, usize)> = self
.segments
.iter()
.enumerate()
.map(|(i, s)| {
let raw = self.store.segment_len(s);
(raw, raw.max(floor) as f64, i)
})
.filter(|&(raw, _, _)| raw <= cap_half)
.collect();
if elig.len() < min_merge {
return None;
}
elig.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(Ordering::Equal));
let mut buckets: Vec<(f64, Vec<(usize, usize)>)> = Vec::new();
'item: for &(raw, sz, idx) in &elig {
for b in buckets.iter_mut() {
if sz > b.0 * cfg.bucket_low && sz < b.0 * cfg.bucket_high {
let n = b.1.len() as f64;
b.0 = (b.0 * n + sz) / (n + 1.0);
b.1.push((raw, idx));
continue 'item;
}
}
buckets.push((sz, vec![(raw, idx)]));
}
buckets.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(Ordering::Equal));
for (_, mut members) in buckets {
if members.len() < min_merge {
continue;
}
members.sort_by_key(|&(raw, _)| raw); let mut chosen = Vec::new();
let mut total = 0usize;
for &(raw, idx) in &members {
if chosen.len() >= cfg.max_merge {
break;
}
if !chosen.is_empty() && total + raw > cfg.max_merged_len {
break;
}
total += raw;
chosen.push(idx);
}
if chosen.len() >= min_merge {
return Some(chosen);
}
}
None
}
pub fn stored_len(&self) -> usize {
let in_segments: usize = self
.segments
.iter()
.map(|s| self.store.segment_len(s))
.sum();
in_segments + self.buffer.len()
}
pub fn epoch(&self) -> u64 {
self.epoch
}
pub fn space_amplification(&self) -> Option<f64> {
let mut stored = 0usize;
let mut live = 0usize;
for seg in &self.segments {
let l = self
.store
.live_len(seg, &|id| !self.tombstones.contains(id))?;
stored += self.store.segment_len(seg);
live += l;
}
stored += self.buffer.len();
live += self.buffer.len();
if live == 0 {
return Some(if stored == 0 { 1.0 } else { f64::INFINITY });
}
Some(stored as f64 / live as f64)
}
pub fn reclaim_tombstones(
&mut self,
min_live_ratio: f64,
) -> PersistenceResult<CompactionStats> {
self.flush_buffer();
let mut stats = CompactionStats {
segments_before: self.segments.len(),
..Default::default()
};
let mut targets = Vec::new();
for (i, seg) in self.segments.iter().enumerate() {
let total = self.store.segment_len(seg);
if total == 0 {
continue;
}
let live = match self
.store
.live_len(seg, &|id| !self.tombstones.contains(id))
{
Some(l) => l,
None => {
stats.segments_after = self.segments.len();
return Ok(stats);
}
};
if (live as f64) < min_live_ratio * total as f64 {
targets.push(i);
}
}
if targets.is_empty() {
stats.segments_after = self.segments.len();
return Ok(stats);
}
stats.items_merged += self.merge_group(targets);
stats.merges = 1;
self.checkpoint()?;
stats.segments_after = self.segments.len();
Ok(stats)
}
pub fn segment_sizes(&self) -> Vec<usize> {
self.segments
.iter()
.map(|s| self.store.segment_len(s))
.collect()
}
pub fn checkpoint(&mut self) -> PersistenceResult<()> {
self.flush_buffer();
let new_epoch = self.epoch + 1;
let snap = Snapshot {
segments: self.segments.iter().map(|a| (**a).clone()).collect(),
tombstones: self.tombstones.iter().cloned().collect::<Vec<_>>(),
};
let ckpt = CheckpointFile::new(self.dir.clone());
if self.dir.file_path(CKPT_PATH).is_some() {
ckpt.write_postcard_durable(CKPT_PATH, new_epoch, &snap)?;
} else {
ckpt.write_postcard(CKPT_PATH, new_epoch, &snap)?;
}
let old_epoch = self.epoch;
self.wal = RecordLogWriter::new(self.dir.clone(), wal_path(new_epoch));
self.epoch = new_epoch;
let _ = self.dir.delete(&wal_path(old_epoch));
self.republish();
Ok(())
}
pub fn segments(&self) -> &[Arc<S::Segment>] {
&self.segments
}
pub fn buffer(&self) -> &[(S::Id, S::Item)] {
&self.buffer
}
pub fn is_live(&self, id: &S::Id) -> bool {
!self.tombstones.contains(id)
}
pub fn segment_count(&self) -> usize {
self.segments.len()
}
pub fn tombstone_count(&self) -> usize {
self.tombstones.len()
}
}
fn apply<Id: Clone + Eq + Hash, Item>(
buffer: &mut Vec<(Id, Item)>,
tombstones: &mut HashSet<Id>,
op: Op<Id, Item>,
) {
match op {
Op::Add(id, item) => {
tombstones.remove(&id);
buffer.push((id, item));
}
Op::Delete(id) => {
buffer.retain(|(bid, _)| bid != &id);
tombstones.insert(id);
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use durability::MemoryDirectory;
struct Kv;
impl Store for Kv {
type Id = u32;
type Item = String;
type Segment = Vec<(u32, String)>;
fn build_segment(&self, batch: &[(u32, String)]) -> Vec<(u32, String)> {
batch.to_vec()
}
fn merge_segments(
&self,
segs: &[Vec<(u32, String)>],
live: &dyn Fn(&u32) -> bool,
) -> Vec<(u32, String)> {
segs.iter()
.flatten()
.filter(|(id, _)| live(id))
.cloned()
.collect()
}
fn segment_len(&self, seg: &Vec<(u32, String)>) -> usize {
seg.len()
}
fn live_len(&self, seg: &Vec<(u32, String)>, live: &dyn Fn(&u32) -> bool) -> Option<usize> {
Some(seg.iter().filter(|(id, _)| live(id)).count())
}
}
struct OpaqueKv;
impl Store for OpaqueKv {
type Id = u32;
type Item = String;
type Segment = Vec<(u32, String)>;
fn build_segment(&self, batch: &[(u32, String)]) -> Vec<(u32, String)> {
batch.to_vec()
}
fn merge_segments(
&self,
segs: &[Vec<(u32, String)>],
live: &dyn Fn(&u32) -> bool,
) -> Vec<(u32, String)> {
segs.iter()
.flatten()
.filter(|(id, _)| live(id))
.cloned()
.collect()
}
fn segment_len(&self, seg: &Vec<(u32, String)>) -> usize {
seg.len()
}
}
struct FaultDir {
inner: Arc<dyn Directory>,
countdown: std::sync::atomic::AtomicUsize,
}
impl FaultDir {
fn arc(inner: Arc<dyn Directory>, fail_after: usize) -> Arc<dyn Directory> {
Arc::new(FaultDir {
inner,
countdown: std::sync::atomic::AtomicUsize::new(fail_after),
})
}
fn gate(&self) -> PersistenceResult<()> {
use std::sync::atomic::Ordering::Relaxed;
let n = self.countdown.load(Relaxed);
if n == 0 {
return Err(PersistenceError::InvalidState("injected IO fault".into()));
}
self.countdown.store(n - 1, Relaxed);
Ok(())
}
}
impl Directory for FaultDir {
fn create_file(&self, p: &str) -> PersistenceResult<Box<dyn std::io::Write + Send>> {
self.gate()?;
self.inner.create_file(p)
}
fn open_file(&self, p: &str) -> PersistenceResult<Box<dyn std::io::Read + Send>> {
self.inner.open_file(p)
}
fn exists(&self, p: &str) -> bool {
self.inner.exists(p)
}
fn delete(&self, p: &str) -> PersistenceResult<()> {
self.gate()?;
self.inner.delete(p)
}
fn atomic_rename(&self, a: &str, b: &str) -> PersistenceResult<()> {
self.gate()?;
self.inner.atomic_rename(a, b)
}
fn create_dir_all(&self, p: &str) -> PersistenceResult<()> {
self.inner.create_dir_all(p)
}
fn list_dir(&self, p: &str) -> PersistenceResult<Vec<String>> {
self.inner.list_dir(p)
}
fn append_file(&self, p: &str) -> PersistenceResult<Box<dyn std::io::Write + Send>> {
self.gate()?;
self.inner.append_file(p)
}
fn atomic_write(&self, p: &str, d: &[u8]) -> PersistenceResult<()> {
self.gate()?;
self.inner.atomic_write(p, d)
}
fn file_path(&self, p: &str) -> Option<std::path::PathBuf> {
self.inner.file_path(p)
}
}
fn live_set(s: &SegmentedStore<Kv>) -> Vec<(u32, String)> {
let mut out: Vec<(u32, String)> = Vec::new();
for seg in s.segments() {
for (id, it) in seg.iter() {
if s.is_live(id) {
out.push((*id, it.clone()));
}
}
}
for (id, it) in s.buffer() {
if s.is_live(id) {
out.push((*id, it.clone()));
}
}
out.sort();
out
}
#[test]
fn buffer_flushes_into_a_segment_at_threshold() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
s.add(1, "a".into()).unwrap();
assert_eq!(
s.segment_count(),
0,
"one add stays buffered below threshold"
);
s.add(2, "b".into()).unwrap();
assert_eq!(
s.segment_count(),
1,
"second add hits threshold 2 and flushes"
);
assert!(s.buffer().is_empty());
}
#[test]
fn delete_tombstones_and_hides_from_live_set() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
s.add(1, "a".into()).unwrap();
s.add(2, "b".into()).unwrap();
s.delete(2).unwrap();
assert!(s.is_live(&1) && !s.is_live(&2));
assert_eq!(live_set(&s), vec![(1, "a".into())]);
}
#[test]
fn compaction_physically_drops_tombstoned_ids() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
s.add(1, "a".into()).unwrap();
s.add(2, "b".into()).unwrap();
s.add(3, "c".into()).unwrap();
s.delete(2).unwrap();
s.compact().unwrap();
assert_eq!(s.segment_count(), 1, "compaction merges into one segment");
assert_eq!(s.tombstone_count(), 0, "compaction purges tombstones");
let flat: Vec<u32> = s.segments()[0].iter().map(|(id, _)| *id).collect();
assert!(!flat.contains(&2));
assert_eq!(live_set(&s), vec![(1, "a".into()), (3, "c".into())]);
}
#[test]
fn recovers_from_checkpoint_plus_wal_replay() {
let dir = MemoryDirectory::arc();
{
let mut s = SegmentedStore::open(dir.clone(), Kv, 2).unwrap();
s.add(1, "a".into()).unwrap();
s.add(2, "b".into()).unwrap(); s.checkpoint().unwrap(); s.add(3, "c".into()).unwrap(); s.delete(2).unwrap(); }
let s2 = SegmentedStore::open(dir, Kv, 2).unwrap();
assert_eq!(live_set(&s2), vec![(1, "a".into()), (3, "c".into())]);
assert!(!s2.is_live(&2));
}
fn temp_root(tag: &str) -> std::path::PathBuf {
let mut p = std::env::temp_dir();
p.push(format!("segstore-test-{}-{}", std::process::id(), tag));
let _ = std::fs::remove_dir_all(&p);
p
}
#[test]
fn recovers_on_real_disk_via_fs_directory() {
let root = temp_root("fs-recover");
{
let dir = durability::FsDirectory::arc(&root).unwrap();
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
s.add(1, "a".into()).unwrap();
s.add(2, "b".into()).unwrap(); s.checkpoint().unwrap();
s.add(3, "c".into()).unwrap(); s.delete(2).unwrap();
}
let dir = durability::FsDirectory::arc(&root).unwrap();
let s2 = SegmentedStore::open(dir, Kv, 2).unwrap();
assert_eq!(live_set(&s2), vec![(1, "a".into()), (3, "c".into())]);
assert!(!s2.is_live(&2));
let _ = std::fs::remove_dir_all(&root);
}
#[test]
fn torn_wal_tail_is_dropped_not_fatal() {
let root = temp_root("torn-wal");
{
let dir = durability::FsDirectory::arc(&root).unwrap();
let mut s = SegmentedStore::open(dir, Kv, 100).unwrap();
s.add(1, "aaaa".into()).unwrap();
s.add(2, "bbbb".into()).unwrap();
s.add(3, "cccc".into()).unwrap();
s.add(4, "dddd".into()).unwrap(); }
let wal = root.join(wal_path(0));
let bytes = std::fs::read(&wal).unwrap();
assert!(bytes.len() > 3, "WAL should hold four records");
std::fs::write(&wal, &bytes[..bytes.len() - 3]).unwrap();
let dir = durability::FsDirectory::arc(&root).unwrap();
let s2 = SegmentedStore::open(dir, Kv, 100).unwrap();
assert_eq!(
live_set(&s2),
vec![(1, "aaaa".into()), (2, "bbbb".into()), (3, "cccc".into())],
"the torn final record is dropped; the prefix survives"
);
let _ = std::fs::remove_dir_all(&root);
}
#[test]
fn wal_is_bounded_to_one_generation_across_checkpoints() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir.clone(), Kv, 100).unwrap();
for i in 0..10u32 {
s.add(i, format!("v{i}")).unwrap();
s.checkpoint().unwrap();
}
let wals: Vec<String> = dir
.list_dir("")
.unwrap()
.into_iter()
.filter(|n| n.starts_with(WAL_PREFIX))
.collect();
assert!(
wals.len() <= 1,
"rotation bounds the WAL to the current generation, got {wals:?}"
);
}
#[test]
fn stale_wal_generation_is_ignored_and_gced() {
let dir = MemoryDirectory::arc();
{
let mut s = SegmentedStore::open(dir.clone(), Kv, 100).unwrap();
s.add(1, "a".into()).unwrap();
s.add(2, "b".into()).unwrap();
s.add(3, "c".into()).unwrap();
s.checkpoint().unwrap(); }
{
let mut ghost = RecordLogWriter::new(dir.clone(), wal_path(0));
ghost
.append_postcard(&Op::Add(99u32, "ghost".to_string()))
.unwrap();
ghost.flush().unwrap();
}
assert!(dir.exists(&wal_path(0)), "the stale WAL exists pre-open");
let s2 = SegmentedStore::open(dir.clone(), Kv, 100).unwrap();
assert_eq!(
live_set(&s2),
vec![(1, "a".into()), (2, "b".into()), (3, "c".into())],
"the ghost op in the stale epoch is never replayed"
);
assert!(
!dir.exists(&wal_path(0)),
"the stale WAL generation is GC'd on open"
);
}
#[test]
fn fsync_policy_round_trips_on_filesystem() {
let root = temp_root("fsync");
{
let dir = durability::FsDirectory::arc(&root).unwrap();
let opts = Options {
sync: SyncPolicy::Fsync,
..Options::new(2)
};
let mut s = SegmentedStore::open_with_options(dir, Kv, opts).unwrap();
s.add(1, "a".into()).unwrap();
s.add(2, "b".into()).unwrap(); s.checkpoint().unwrap();
s.add(3, "c".into()).unwrap();
s.delete(2).unwrap();
}
let dir = durability::FsDirectory::arc(&root).unwrap();
let opts = Options {
sync: SyncPolicy::Fsync,
..Options::new(2)
};
let s2 = SegmentedStore::open_with_options(dir, Kv, opts).unwrap();
assert_eq!(live_set(&s2), vec![(1, "a".into()), (3, "c".into())]);
assert!(!s2.is_live(&2));
let _ = std::fs::remove_dir_all(&root);
}
#[test]
fn fsync_policy_rejected_without_filesystem_backend() {
let dir = MemoryDirectory::arc();
let opts = Options {
sync: SyncPolicy::Fsync,
..Options::new(2)
};
let err = SegmentedStore::open_with_options(dir, Kv, opts);
assert!(
matches!(err, Err(PersistenceError::InvalidConfig(_))),
"Fsync on an in-memory directory is a config error"
);
}
#[test]
fn legacy_v01_unsuffixed_wal_is_rejected() {
let dir = MemoryDirectory::arc();
{
let mut legacy = RecordLogWriter::new(dir.clone(), LEGACY_WAL_PATH);
legacy
.append_postcard(&Op::Add(1u32, "x".to_string()))
.unwrap();
legacy.flush().unwrap();
}
let err = SegmentedStore::open(dir, Kv, 2);
assert!(
matches!(err, Err(PersistenceError::InvalidConfig(_))),
"a 0.1 on-disk store is rejected, not misread"
);
}
fn live_multiset(s: &SegmentedStore<Kv>) -> Vec<(u32, String)> {
live_set(s)
}
fn tier_opts(flush: usize, cfg: TierConfig, auto: bool) -> Options {
Options {
tiering: cfg,
auto_compact: auto,
..Options::new(flush)
}
}
#[test]
fn compact_tiers_merges_a_full_bucket_and_is_idempotent() {
let dir = MemoryDirectory::arc();
let cfg = TierConfig {
min_merge: 4,
..Default::default()
};
let mut s = SegmentedStore::open_with_options(dir, Kv, tier_opts(2, cfg, false)).unwrap();
for i in 0..8u32 {
s.add(i, format!("v{i}")).unwrap();
}
assert_eq!(
s.segment_count(),
4,
"four size-2 segments before compaction"
);
let stats = s.compact_tiers().unwrap();
assert_eq!(stats.merges, 1, "the full bucket merges once");
assert_eq!(s.segment_count(), 1, "into a single segment");
assert_eq!(stats.items_merged, 8);
assert!(!s.has_eligible_tier());
let again = s.compact_tiers().unwrap();
assert_eq!(again.merges, 0, "second call is a no-op");
}
#[test]
fn tier_merge_respects_max_merged_len_cap() {
let dir = MemoryDirectory::arc();
let cfg = TierConfig {
min_merge: 4,
max_merged_len: 8,
..Default::default()
};
let mut s = SegmentedStore::open_with_options(dir, Kv, tier_opts(2, cfg, true)).unwrap();
for i in 0..64u32 {
s.add(i, format!("v{i}")).unwrap();
}
s.compact_tiers().unwrap();
for seg in s.segments() {
assert!(
seg.len() <= cfg.max_merged_len,
"no segment exceeds the cap; got {}",
seg.len()
);
}
}
#[test]
fn auto_compact_bounds_segment_count() {
let dir = MemoryDirectory::arc();
let cfg = TierConfig::default(); let mut s = SegmentedStore::open_with_options(dir, Kv, tier_opts(2, cfg, true)).unwrap();
for i in 0..200u32 {
s.add(i, format!("v{i}")).unwrap();
}
s.compact_tiers().unwrap();
assert!(
s.segment_count() <= 20,
"tiering bounds segment count well below the uncompacted 100; got {}",
s.segment_count()
);
assert_eq!(live_multiset(&s).len(), 200);
}
#[test]
fn tier_merge_preserves_live_set_and_keeps_tombstones() {
let dir = MemoryDirectory::arc();
let cfg = TierConfig {
min_merge: 4,
max_merged_len: 8, ..Default::default()
};
let mut s = SegmentedStore::open_with_options(dir, Kv, tier_opts(2, cfg, false)).unwrap();
let mut expect: std::collections::BTreeMap<u32, String> = Default::default();
for i in 0..40u32 {
s.add(i, format!("v{i}")).unwrap();
expect.insert(i, format!("v{i}"));
}
for i in (0..40u32).step_by(5) {
s.delete(i).unwrap();
expect.remove(&i);
}
s.compact_tiers().unwrap();
let want: Vec<(u32, String)> = expect.into_iter().collect();
assert_eq!(live_multiset(&s), want, "tier merge preserves the live set");
assert!(
s.tombstone_count() > 0,
"partial tier merge keeps the tombstone set (ids may live in frozen segments)"
);
s.compact().unwrap();
assert_eq!(s.tombstone_count(), 0, "full compact purges tombstones");
assert_eq!(live_multiset(&s), want, "and preserves the live set");
}
#[test]
fn min_merge_below_two_terminates() {
let dir = MemoryDirectory::arc();
let cfg = TierConfig {
min_merge: 1, ..Default::default()
};
let mut s = SegmentedStore::open_with_options(dir, Kv, tier_opts(1, cfg, false)).unwrap();
for i in 0..8u32 {
s.add(i, format!("v{i}")).unwrap();
}
let stats = s.compact_tiers().unwrap();
assert!(stats.segments_after <= stats.segments_before);
assert_eq!(live_multiset(&s).len(), 8);
}
#[test]
fn large_scale_random_simulation_holds_invariants() {
let dir = MemoryDirectory::arc();
let cfg = TierConfig {
min_merge: 4,
max_merge: 8,
max_merged_len: 64,
..Default::default()
};
let mut s = SegmentedStore::open_with_options(dir, Kv, tier_opts(3, cfg, true)).unwrap();
let mut expect: std::collections::BTreeMap<u32, String> = Default::default();
let mut live_ids: Vec<u32> = Vec::new();
let mut next_id = 0u32;
let mut state: u64 = 0x9E3779B97F4A7C15;
let mut next = || {
state = state
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
(state >> 33) as u32
};
for _ in 0..2000 {
if next() % 4 == 0 && !live_ids.is_empty() {
let pos = (next() as usize) % live_ids.len();
let id = live_ids.swap_remove(pos);
s.delete(id).unwrap();
expect.remove(&id);
} else {
let id = next_id;
next_id += 1;
let v = format!("v{id}");
s.add(id, v.clone()).unwrap();
expect.insert(id, v);
live_ids.push(id);
}
if next() % 50 == 0 {
s.compact_tiers().unwrap();
}
for seg in s.segments() {
assert!(
seg.len() <= cfg.max_merged_len,
"seg size {} exceeds cap {}",
seg.len(),
cfg.max_merged_len
);
}
}
s.compact().unwrap();
let want: Vec<(u32, String)> = expect.into_iter().collect();
assert_eq!(
live_multiset(&s),
want,
"after a long random run, the live set matches the reference"
);
}
#[test]
fn segment_sizes_reports_per_segment_counts() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
for i in 0..6u32 {
s.add(i, format!("v{i}")).unwrap(); }
assert_eq!(s.segment_sizes(), vec![2, 2, 2]);
assert_eq!(s.stored_len(), 6);
}
#[test]
fn store_is_send() {
fn assert_send<T: Send>() {}
assert_send::<SegmentedStore<Kv>>();
}
#[test]
fn corrupt_checkpoint_is_rejected_not_misread() {
let root = temp_root("corrupt-ckpt");
{
let dir = durability::FsDirectory::arc(&root).unwrap();
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
s.add(1, "a".into()).unwrap();
s.add(2, "b".into()).unwrap();
s.checkpoint().unwrap();
}
let ckpt = root.join(CKPT_PATH);
let mut bytes = std::fs::read(&ckpt).unwrap();
let mid = bytes.len() / 2;
bytes[mid] ^= 0xFF;
std::fs::write(&ckpt, &bytes).unwrap();
let dir = durability::FsDirectory::arc(&root).unwrap();
let res = SegmentedStore::open(dir, Kv, 2);
assert!(
res.is_err(),
"a CRC-corrupt checkpoint is an error, not silently misread"
);
let _ = std::fs::remove_dir_all(&root);
}
#[test]
fn stale_checkpoint_tmp_is_ignored() {
let root = temp_root("stale-tmp");
{
let dir = durability::FsDirectory::arc(&root).unwrap();
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
s.add(1, "a".into()).unwrap();
s.add(2, "b".into()).unwrap();
s.checkpoint().unwrap();
}
std::fs::write(root.join(format!("{CKPT_PATH}.tmp")), b"garbage").unwrap();
let dir = durability::FsDirectory::arc(&root).unwrap();
let s2 = SegmentedStore::open(dir, Kv, 2).unwrap();
assert_eq!(live_set(&s2), vec![(1, "a".into()), (2, "b".into())]);
let _ = std::fs::remove_dir_all(&root);
}
#[test]
fn recovers_consistently_from_io_fault_at_every_step() {
for fail_after in 0..30usize {
let mem = MemoryDirectory::arc();
let dir = FaultDir::arc(mem.clone(), fail_after);
let mut acked: Vec<u32> = Vec::new();
if let Ok(mut s) = SegmentedStore::open(dir, Kv, 2) {
for i in 0..10u32 {
if s.add(i, format!("v{i}")).is_err() {
break;
}
acked.push(i);
if i % 3 == 0 && s.compact_tiers().is_err() {
break;
}
}
}
let s2 = SegmentedStore::open(mem, Kv, 2)
.expect("recovery after an injected IO fault must not fail");
let mut live: Vec<u32> = live_set(&s2).into_iter().map(|(id, _)| id).collect();
live.sort_unstable();
assert_eq!(
live, acked,
"fail_after={fail_after}: recovered set must be exactly the durably-acked adds"
);
}
}
#[test]
fn no_space_leak_across_crash_recovery_cycles() {
let mem = MemoryDirectory::arc();
for cycle in 0..20u32 {
let dir = FaultDir::arc(mem.clone(), (cycle as usize % 5) + 1);
if let Ok(mut s) = SegmentedStore::open(dir, Kv, 2) {
for j in 0..4u32 {
let id = cycle * 100 + j;
let _ = s.add(id, format!("v{id}"));
let _ = s.compact_tiers();
}
}
let _ = SegmentedStore::open(mem.clone(), Kv, 2).unwrap();
}
let mut s = SegmentedStore::open(mem.clone(), Kv, 2).unwrap();
let live: Vec<u32> = live_set(&s).into_iter().map(|(id, _)| id).collect();
for id in live {
s.delete(id).unwrap();
}
s.compact().unwrap();
assert_eq!(
s.segment_count(),
0,
"no leaked segments after delete-all + compact"
);
assert_eq!(s.stored_len(), 0, "no leaked stored items");
assert_eq!(s.tombstone_count(), 0, "compact purged the tombstone set");
let wals: Vec<String> = mem
.list_dir("")
.unwrap()
.into_iter()
.filter(|n| n.starts_with(WAL_PREFIX))
.collect();
assert!(wals.len() <= 1, "no leaked WAL generations: {wals:?}");
}
#[test]
fn space_amplification_tracks_dead_data() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
for i in 0..10u32 {
s.add(i, format!("v{i}")).unwrap();
}
assert_eq!(
s.space_amplification(),
Some(1.0),
"no deletes, no dead data"
);
for i in 0..5u32 {
s.delete(i).unwrap();
}
assert_eq!(s.space_amplification(), Some(2.0));
s.compact().unwrap();
assert_eq!(s.space_amplification(), Some(1.0), "compaction reclaims it");
}
#[test]
fn space_amplification_is_none_without_live_len() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, OpaqueKv, 2).unwrap();
s.add(1, "a".into()).unwrap();
s.add(2, "b".into()).unwrap();
assert_eq!(
s.space_amplification(),
None,
"a store without live_len cannot report it"
);
}
#[test]
fn reclaim_tombstones_rewrites_only_heavy_segments() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
for i in 0..10u32 {
s.add(i, format!("v{i}")).unwrap();
}
for i in 0..4u32 {
s.delete(i).unwrap();
}
let before_stored = s.stored_len();
let stats = s.reclaim_tombstones(0.5).unwrap();
assert!(stats.merges > 0, "the dead segments were reclaimed");
assert!(
s.stored_len() < before_stored,
"dead data dropped: {} < {}",
s.stored_len(),
before_stored
);
let live: Vec<u32> = live_set(&s).into_iter().map(|(id, _)| id).collect();
assert_eq!(live, (4..10).collect::<Vec<_>>());
}
#[test]
fn reclaim_tombstones_is_noop_without_live_len() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, OpaqueKv, 2).unwrap();
for i in 0..6u32 {
s.add(i, format!("v{i}")).unwrap();
}
s.delete(0).unwrap();
let before = s.segment_count();
let stats = s.reclaim_tombstones(0.9).unwrap();
assert_eq!(stats.merges, 0, "no live_len -> reclaim is a no-op");
assert_eq!(s.segment_count(), before);
}
#[test]
fn reclaim_drops_a_fully_dead_segment() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
for i in 0..4u32 {
s.add(i, format!("v{i}")).unwrap(); }
assert_eq!(s.segment_count(), 2);
s.delete(0).unwrap();
s.delete(1).unwrap(); s.reclaim_tombstones(0.5).unwrap();
assert_eq!(s.segment_count(), 1, "the fully-dead segment is dropped");
assert_eq!(s.stored_len(), 2, "only the live segment remains");
}
#[test]
fn force_merge_to_consolidates_without_data_loss() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
for i in 0..20u32 {
s.add(i, format!("v{i}")).unwrap(); }
assert_eq!(s.segment_count(), 10);
let stats = s.force_merge_to(3).unwrap();
assert_eq!(s.segment_count(), 3, "consolidated to exactly 3");
assert_eq!(stats.merges, 1, "one merge suffices (minimum work)");
assert!(stats.items_merged > 0, "merged work is reported");
assert_eq!(live_multiset(&s).len(), 20, "no data lost");
}
#[test]
fn force_merge_to_one_purges_tombstones() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
for i in 0..10u32 {
s.add(i, format!("v{i}")).unwrap();
}
for i in 0..5u32 {
s.delete(i).unwrap();
}
s.force_merge_to(1).unwrap();
assert_eq!(s.segment_count(), 1);
assert_eq!(s.tombstone_count(), 0, "merge to one purges tombstones");
let live: Vec<u32> = live_set(&s).into_iter().map(|(id, _)| id).collect();
assert_eq!(live, (5..10).collect::<Vec<_>>());
}
#[test]
fn force_merge_to_is_noop_when_already_small() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
for i in 0..4u32 {
s.add(i, format!("v{i}")).unwrap(); }
let e = s.epoch();
let stats = s.force_merge_to(5).unwrap();
assert_eq!(stats.merges, 0, "already at/below target, nothing to merge");
assert_eq!(s.segment_count(), 2);
assert_eq!(s.epoch(), e, "no merge -> no checkpoint");
}
#[test]
fn force_merge_persists_across_reopen() {
let dir = MemoryDirectory::arc();
{
let mut s = SegmentedStore::open(dir.clone(), Kv, 2).unwrap();
for i in 0..20u32 {
s.add(i, format!("v{i}")).unwrap(); }
s.force_merge_to(2).unwrap();
assert_eq!(s.segment_count(), 2);
}
let s = SegmentedStore::open(dir, Kv, 2).unwrap();
assert_eq!(s.segment_count(), 2, "force-merge result was checkpointed");
assert_eq!(live_multiset(&s).len(), 20);
}
#[test]
fn tiered_write_amplification_is_subquadratic() {
let dir = MemoryDirectory::arc();
let cfg = TierConfig::default(); let mut s = SegmentedStore::open_with_options(dir, Kv, tier_opts(4, cfg, false)).unwrap();
let n: u32 = 4000;
let mut total_merged = 0usize;
for i in 0..n {
s.add(i, format!("v{i}")).unwrap();
if i % 16 == 0 {
total_merged += s.compact_tiers().unwrap().items_merged;
}
}
total_merged += s.compact_tiers().unwrap().items_merged;
let n = n as usize;
assert!(total_merged > 0, "compaction actually ran");
assert!(
total_merged < 20 * n,
"tiered merge work {total_merged} is ~O(N log N) (< 20*N = {}), not O(N^2={})",
20 * n,
n * n
);
assert_eq!(live_multiset(&s).len(), n, "no data lost");
}
#[test]
fn epoch_advances_per_checkpoint() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
assert_eq!(s.epoch(), 0);
s.add(1, "a".into()).unwrap();
s.checkpoint().unwrap();
assert_eq!(s.epoch(), 1);
s.checkpoint().unwrap();
assert_eq!(s.epoch(), 2);
}
#[test]
fn stored_len_and_space_amp_count_the_buffer() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, Kv, 100).unwrap(); s.add(1, "a".into()).unwrap();
s.add(2, "b".into()).unwrap();
assert_eq!(s.segment_count(), 0, "all buffered");
assert_eq!(s.stored_len(), 2, "stored_len counts the buffer");
assert_eq!(
s.space_amplification(),
Some(1.0),
"buffered items are live"
);
}
#[test]
fn space_amp_of_empty_store_is_one() {
let dir = MemoryDirectory::arc();
let s = SegmentedStore::open(dir, Kv, 2).unwrap();
assert_eq!(s.space_amplification(), Some(1.0));
}
#[test]
fn space_amp_is_infinite_when_all_dead() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
s.add(1, "a".into()).unwrap();
s.add(2, "b".into()).unwrap(); s.delete(1).unwrap();
s.delete(2).unwrap(); assert!(
s.space_amplification().unwrap().is_infinite(),
"an all-dead segment is infinite amplification"
);
}
#[test]
fn has_eligible_tier_is_true_when_a_bucket_is_full() {
let dir = MemoryDirectory::arc();
let cfg = TierConfig {
min_merge: 4,
..Default::default()
};
let mut s = SegmentedStore::open_with_options(dir, Kv, tier_opts(2, cfg, false)).unwrap();
for i in 0..8u32 {
s.add(i, format!("v{i}")).unwrap(); }
assert!(s.has_eligible_tier());
}
#[test]
fn compact_merges_only_when_there_is_work() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
s.add(1, "a".into()).unwrap();
s.add(2, "b".into()).unwrap(); assert_eq!(
s.compact().unwrap().merges,
0,
"a single clean segment: nothing to merge"
);
s.delete(1).unwrap();
assert_eq!(
s.compact().unwrap().merges,
1,
"a tombstone present: merge to purge it"
);
}
#[test]
fn reclaim_respects_the_live_ratio_threshold() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, Kv, 4).unwrap();
for i in 0..12u32 {
s.add(i, format!("v{i}")).unwrap(); }
for i in [0u32, 1, 2, 4, 8, 9] {
s.delete(i).unwrap();
}
let stats = s.reclaim_tombstones(0.5).unwrap();
assert_eq!(
stats.merges, 1,
"only the sub-threshold segment is reclaimed"
);
assert_eq!(stats.items_merged, 1, "A's single live item is rewritten");
assert_eq!(
s.segment_count(),
3,
"A rewritten in place; B and C untouched"
);
assert_eq!(s.stored_len(), 1 + 4 + 4, "only A's dead entries dropped");
}
#[test]
fn compact_tiers_persists_across_reopen() {
let dir = MemoryDirectory::arc();
let cfg = TierConfig {
min_merge: 4,
..Default::default()
};
{
let mut s =
SegmentedStore::open_with_options(dir.clone(), Kv, tier_opts(2, cfg, false))
.unwrap();
for i in 0..8u32 {
s.add(i, format!("v{i}")).unwrap();
}
assert_eq!(s.compact_tiers().unwrap().merges, 1);
assert_eq!(s.segment_count(), 1);
}
let s = SegmentedStore::open_with_options(dir, Kv, tier_opts(2, cfg, false)).unwrap();
assert_eq!(s.segment_count(), 1, "the tier merge was checkpointed");
assert_eq!(live_multiset(&s).len(), 8);
}
#[test]
fn compact_tiers_without_eligible_bucket_does_not_checkpoint() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, Kv, 100).unwrap();
s.add(1, "a".into()).unwrap();
let e = s.epoch();
assert_eq!(s.compact_tiers().unwrap().merges, 0);
assert_eq!(s.epoch(), e, "no merge -> no checkpoint -> epoch unchanged");
}
#[test]
fn cap_freezes_large_segments_from_tier_merges() {
let dir = MemoryDirectory::arc();
let cfg = TierConfig {
min_merge: 4,
max_merged_len: 8,
..Default::default()
};
let mut s = SegmentedStore::open_with_options(dir, Kv, tier_opts(2, cfg, false)).unwrap();
for i in 0..8u32 {
s.add(i, format!("v{i}")).unwrap();
}
s.force_merge_to(1).unwrap(); assert_eq!(s.segment_sizes(), vec![8]);
for i in 8..20u32 {
s.add(i, format!("v{i}")).unwrap(); }
s.compact_tiers().unwrap();
assert!(
s.segment_sizes().contains(&8),
"the frozen segment is never selected for a tier merge"
);
for sz in s.segment_sizes() {
assert!(sz <= cfg.max_merged_len, "no segment exceeds the cap");
}
assert_eq!(live_multiset(&s).len(), 20, "no data lost");
}
#[test]
fn without_compaction_fan_out_grows_then_collapses() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
for i in 0..40u32 {
s.add(i, format!("v{i}")).unwrap();
}
assert_eq!(
s.segment_count(),
20,
"no compaction: 40 adds / flush 2 = 20 segments to scan per query"
);
s.compact_tiers().unwrap();
assert!(
s.segment_count() < 20,
"tiered compaction collapses the fan-out, got {}",
s.segment_count()
);
assert_eq!(live_multiset(&s).len(), 40, "without losing data");
}
#[test]
fn view_reflects_segments_minus_tombstones() {
let mut s = SegmentedStore::open(MemoryDirectory::arc(), Kv, 2).unwrap();
for i in 0..6u32 {
s.add(i, format!("v{i}")).unwrap();
}
s.delete(2).unwrap();
s.checkpoint().unwrap(); let v = s.reader().view();
let mut live: Vec<u32> = Vec::new();
for seg in v.segments() {
for (id, _) in seg.iter() {
if v.is_live(id) {
live.push(*id);
}
}
}
live.sort_unstable();
assert_eq!(
live,
vec![0, 1, 3, 4, 5],
"view = checkpointed segments minus tombstones"
);
}
#[test]
fn view_is_a_stable_snapshot_across_writes() {
let mut s = SegmentedStore::open(MemoryDirectory::arc(), Kv, 2).unwrap();
for i in 0..6u32 {
s.add(i, format!("v{i}")).unwrap(); }
s.checkpoint().unwrap(); let reader = s.reader();
let v1 = reader.view();
let before = v1.segment_count();
assert_eq!(before, 3);
for i in 6..30u32 {
s.add(i, format!("v{i}")).unwrap();
}
s.compact().unwrap();
assert_eq!(v1.segment_count(), before, "the held view never changes");
assert_eq!(
reader.view().segment_count(),
1,
"a fresh view sees the compacted state"
);
}
#[test]
fn unchanged_segments_keep_arc_identity_across_checkpoints() {
let mut s = SegmentedStore::open(MemoryDirectory::arc(), Kv, 2).unwrap();
for i in 0..6u32 {
s.add(i, format!("v{i}")).unwrap(); }
s.checkpoint().unwrap();
let r = s.reader();
let ptrs1: Vec<*const _> = r.view().segments().iter().map(Arc::as_ptr).collect();
assert_eq!(ptrs1.len(), 3);
s.checkpoint().unwrap();
let ptrs2: Vec<*const _> = r.view().segments().iter().map(Arc::as_ptr).collect();
assert_eq!(
ptrs1, ptrs2,
"a no-op checkpoint keeps all segment identities"
);
s.add(10, "x".into()).unwrap();
s.add(11, "y".into()).unwrap(); s.checkpoint().unwrap();
let ptrs3: Vec<*const _> = r.view().segments().iter().map(Arc::as_ptr).collect();
assert_eq!(ptrs3.len(), 4);
assert_eq!(
&ptrs3[..3],
&ptrs1[..],
"the original segments keep identity; only the new one is fresh"
);
}
#[test]
fn concurrent_reader_during_writes_stays_consistent() {
use std::sync::atomic::{AtomicBool, Ordering};
let mut s = SegmentedStore::open_with_options(
MemoryDirectory::arc(),
Kv,
Options {
tiering: TierConfig {
min_merge: 4,
..Default::default()
},
..Options::new(4)
},
)
.unwrap();
for i in 0..40u32 {
s.add(i, format!("v{i}")).unwrap();
}
let reader = s.reader();
let stop = Arc::new(AtomicBool::new(false));
let stop2 = stop.clone();
let handle = std::thread::spawn(move || {
let mut iters = 0u64;
while !stop2.load(Ordering::Relaxed) {
let v = reader.view();
let mut count = 0usize;
for seg in v.segments() {
for (id, _) in seg.iter() {
if v.is_live(id) {
count += 1;
}
}
}
std::hint::black_box(count);
iters += 1;
}
iters
});
for i in 40..400u32 {
s.add(i, format!("v{i}")).unwrap();
if i % 20 == 0 {
s.compact_tiers().unwrap();
}
}
s.compact().unwrap();
stop.store(true, Ordering::Relaxed);
handle.join().unwrap();
let v = s.reader().view();
let mut live = 0usize;
for seg in v.segments() {
for (id, _) in seg.iter() {
if v.is_live(id) {
live += 1;
}
}
}
assert_eq!(live, 400, "all 400 items live after the concurrent run");
}
#[test]
fn extend_matches_individual_adds() {
let mut s1 = SegmentedStore::open(MemoryDirectory::arc(), Kv, 2).unwrap();
let mut s2 = SegmentedStore::open(MemoryDirectory::arc(), Kv, 2).unwrap();
for i in 0..20u32 {
s1.add(i, format!("v{i}")).unwrap();
}
s2.extend((0..20u32).map(|i| (i, format!("v{i}")))).unwrap();
assert_eq!(live_set(&s1), live_set(&s2), "extend == individual adds");
assert_eq!(s1.segment_count(), s2.segment_count());
}
#[test]
fn extend_is_durable_across_reopen() {
let dir = MemoryDirectory::arc();
{
let mut s = SegmentedStore::open(dir.clone(), Kv, 4).unwrap();
s.extend((0..20u32).map(|i| (i, format!("v{i}")))).unwrap();
}
let s = SegmentedStore::open(dir, Kv, 4).unwrap();
assert_eq!(
live_set(&s).len(),
20,
"the whole batch is durable after sync"
);
}
#[test]
fn garbled_wal_record_is_caught_by_crc() {
let root = temp_root("garble-wal");
{
let dir = durability::FsDirectory::arc(&root).unwrap();
let mut s = SegmentedStore::open(dir, Kv, 100).unwrap(); for i in 1..=6u32 {
s.add(i, format!("v{i}")).unwrap();
}
}
let wal = root.join(wal_path(0));
let mut bytes = std::fs::read(&wal).unwrap();
let mid = bytes.len() / 2;
bytes[mid] ^= 0xFF; std::fs::write(&wal, &bytes).unwrap();
let dir = durability::FsDirectory::arc(&root).unwrap();
match SegmentedStore::open(dir, Kv, 100) {
Ok(s2) => {
let mut live: Vec<u32> = live_set(&s2).into_iter().map(|(id, _)| id).collect();
live.sort_unstable();
assert!(
live.len() < 6,
"the corrupted record + tail are dropped: {live:?}"
);
assert_eq!(
live,
(1..=live.len() as u32).collect::<Vec<_>>(),
"survivors are the contiguous prefix before the corruption: {live:?}"
);
}
Err(_) => { }
}
let _ = std::fs::remove_dir_all(&root);
}
use proptest::prelude::*;
#[derive(Debug, Clone)]
enum SimOp {
Add,
Delete(usize),
Compact,
CompactTiers,
Reopen,
}
fn op_strategy() -> impl Strategy<Value = SimOp> {
prop_oneof![
3 => Just(SimOp::Add),
2 => (0usize..100).prop_map(SimOp::Delete),
1 => Just(SimOp::Compact),
1 => Just(SimOp::CompactTiers),
1 => Just(SimOp::Reopen),
]
}
proptest! {
#![proptest_config(ProptestConfig::with_cases(512))]
#[test]
fn live_set_matches_reference_under_random_ops(
ops in proptest::collection::vec(op_strategy(), 0..200)
) {
let dir = MemoryDirectory::arc();
let cfg = TierConfig {
min_merge: 4,
max_merge: 8,
max_merged_len: 64,
..Default::default()
};
let mk = || Options { tiering: cfg, ..Options::new(3) };
let mut s = SegmentedStore::open_with_options(dir.clone(), Kv, mk()).unwrap();
let mut model: std::collections::BTreeMap<u32, String> = Default::default();
let mut live_ids: Vec<u32> = Vec::new();
let mut next_id = 0u32;
for op in ops {
match op {
SimOp::Add => {
let id = next_id;
next_id += 1;
let v = format!("v{id}");
s.add(id, v.clone()).unwrap();
model.insert(id, v);
live_ids.push(id);
}
SimOp::Delete(k) => {
if !live_ids.is_empty() {
let id = live_ids.swap_remove(k % live_ids.len());
s.delete(id).unwrap();
model.remove(&id);
}
}
SimOp::Compact => {
s.compact().unwrap();
}
SimOp::CompactTiers => {
s.compact_tiers().unwrap();
}
SimOp::Reopen => {
s = SegmentedStore::open_with_options(dir.clone(), Kv, mk()).unwrap();
}
}
for sz in s.segment_sizes() {
prop_assert!(sz <= cfg.max_merged_len);
}
}
let want: Vec<(u32, String)> = model.into_iter().collect();
prop_assert_eq!(live_set(&s), want);
}
}
}