use std::cmp::Ordering;
use std::collections::HashSet;
use std::hash::Hash;
use std::io::Read;
use std::marker::PhantomData;
use std::sync::Arc;
use durability::checkpoint::{CheckpointFile, MAX_CHECKPOINT_PAYLOAD_BYTES};
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 LEGACY_CKPT_PATH: &str = "segstore.ckpt";
const MANIFEST_PATH: &str = "segstore.manifest";
const SEG_PREFIX: &str = "segstore.seg.";
const CHECKPOINT_MAGIC: [u8; 4] = *b"VCKP";
const CHECKPOINT_FORMAT_VERSION_V1: u32 = 1;
const CHECKPOINT_FORMAT_VERSION_V2: u32 = 2;
const CHECKPOINT_HEADER_BYTES: u64 = 4 + 4 + 8 + 8 + 4;
const SIDECAR_ENVELOPE_HEADER_BYTES: usize = 8 + 4 + 8 + 4 + 4;
fn wal_path(epoch: u64) -> String {
format!("{WAL_PREFIX}{epoch}")
}
fn seg_path(id: u64) -> String {
format!("{SEG_PREFIX}{id}")
}
fn size_cap_context(e: PersistenceError, what: &str) -> PersistenceError {
match &e {
PersistenceError::Format(msg) if msg.contains("payload too large") => {
PersistenceError::Format(format!(
"{what} does not fit the {MAX_CHECKPOINT_PAYLOAD_BYTES}-byte per-blob limit \
(durability::MAX_CHECKPOINT_PAYLOAD_BYTES): {msg}. Each segment and the \
manifest are written as a single checkpoint blob. Keep them under the cap: \
lower TierConfig::max_merged_len (it counts items, not bytes) or the open() \
flush_threshold so segments stay smaller, and run compact() to drop \
tombstones from the manifest."
))
}
_ => e,
}
}
fn reject_legacy_formats(dir: &dyn Directory) -> PersistenceResult<()> {
if dir.exists(LEGACY_WAL_PATH) {
return Err(PersistenceError::InvalidConfig(
"segstore 0.1 on-disk store detected (unsuffixed segstore.wal); the \
on-disk format is epoch-suffixed and cannot read it"
.into(),
));
}
if dir.exists(LEGACY_CKPT_PATH) && !dir.exists(MANIFEST_PATH) {
return Err(PersistenceError::InvalidConfig(
"segstore 0.2 on-disk store detected (monolithic segstore.ckpt); the 0.3 \
on-disk format is a manifest + per-segment files and cannot read it"
.into(),
));
}
Ok(())
}
const IDX_PREFIX: &str = "segstore.idx.";
fn idx_seg_id(name: &str) -> Option<u64> {
let rest = name.strip_prefix(IDX_PREFIX)?;
let (id, kind) = rest.split_once('.')?;
if kind.is_empty() {
return None;
}
id.parse::<u64>().ok()
}
fn validate_index_kind(kind: &str) -> PersistenceResult<()> {
if kind.is_empty() {
return Err(PersistenceError::InvalidConfig(
"index sidecar kind must be non-empty".into(),
));
}
if !kind
.bytes()
.all(|b| b.is_ascii_alphanumeric() || matches!(b, b'_' | b'-'))
{
return Err(PersistenceError::InvalidConfig(format!(
"index sidecar kind must contain only ASCII letters, digits, '_' or '-': {kind:?}"
)));
}
Ok(())
}
fn index_sidecar_name(id: u64, kind: &str) -> PersistenceResult<String> {
validate_index_kind(kind)?;
Ok(format!("{IDX_PREFIX}{id}.{kind}"))
}
fn delete_files_best_effort(dir: &dyn Directory, names: Vec<String>, durable: bool) {
let mut deleted = false;
for name in names {
if dir.exists(&name) && dir.delete(&name).is_ok() {
deleted = true;
}
}
if durable && deleted {
let _ = dir.durable_sync_parent_dir(MANIFEST_PATH);
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct SegmentPayloadInfo {
pub payload_offset: u64,
pub payload_len: usize,
pub payload_crc32: u32,
}
impl SegmentPayloadInfo {
pub fn verify_payload(&self, payload: &[u8]) -> PersistenceResult<()> {
if payload.len() != self.payload_len {
return Err(PersistenceError::Format(format!(
"segment payload length mismatch: got {} bytes, expected {}",
payload.len(),
self.payload_len
)));
}
let actual = crc32fast::hash(payload);
if actual != self.payload_crc32 {
return Err(PersistenceError::CrcMismatch {
expected: self.payload_crc32,
actual,
});
}
Ok(())
}
}
fn read_checkpoint_payload_header<R: Read + ?Sized>(
f: &mut R,
) -> PersistenceResult<CheckpointPayloadHeader> {
let mut buf4 = [0u8; 4];
let mut buf8 = [0u8; 8];
f.read_exact(&mut buf4)?;
if buf4 != CHECKPOINT_MAGIC {
return Err(PersistenceError::Format("invalid checkpoint magic".into()));
}
f.read_exact(&mut buf4)?;
let version = u32::from_le_bytes(buf4);
if !matches!(
version,
CHECKPOINT_FORMAT_VERSION_V1 | CHECKPOINT_FORMAT_VERSION_V2
) {
return Err(PersistenceError::Format(format!(
"checkpoint version mismatch (got {version})"
)));
}
f.read_exact(&mut buf8)?;
let last_applied_id = u64::from_le_bytes(buf8);
f.read_exact(&mut buf8)?;
let payload_len_u64 = u64::from_le_bytes(buf8);
let payload_len = usize::try_from(payload_len_u64)
.map_err(|_| PersistenceError::Format("payload_len overflow".into()))?;
if payload_len > MAX_CHECKPOINT_PAYLOAD_BYTES {
return Err(PersistenceError::Format(format!(
"checkpoint payload too large: {} bytes (max {})",
payload_len, MAX_CHECKPOINT_PAYLOAD_BYTES
)));
}
f.read_exact(&mut buf4)?;
let checksum = u32::from_le_bytes(buf4);
Ok(CheckpointPayloadHeader {
version,
last_applied_id,
payload_len_u64,
payload_len,
checksum,
})
}
#[derive(Debug, Clone, Copy)]
struct CheckpointPayloadHeader {
version: u32,
last_applied_id: u64,
payload_len_u64: u64,
payload_len: usize,
checksum: u32,
}
impl CheckpointPayloadHeader {
fn verify_payload(&self, payload: &[u8]) -> PersistenceResult<()> {
if payload.len() != self.payload_len {
return Err(PersistenceError::Format(format!(
"checkpoint payload truncated: got {} of {} bytes",
payload.len(),
self.payload_len
)));
}
let actual = match self.version {
CHECKPOINT_FORMAT_VERSION_V1 => crc32fast::hash(payload),
CHECKPOINT_FORMAT_VERSION_V2 => {
let mut hasher = crc32fast::Hasher::new();
hasher.update(&CHECKPOINT_MAGIC);
hasher.update(&self.version.to_le_bytes());
hasher.update(&self.last_applied_id.to_le_bytes());
hasher.update(&self.payload_len_u64.to_le_bytes());
hasher.update(payload);
hasher.finalize()
}
_ => unreachable!("checkpoint header version is validated at parse time"),
};
if actual != self.checksum {
return Err(PersistenceError::CrcMismatch {
expected: self.checksum,
actual,
});
}
Ok(())
}
fn payload_info(&self, payload: &[u8]) -> SegmentPayloadInfo {
SegmentPayloadInfo {
payload_offset: CHECKPOINT_HEADER_BYTES,
payload_len: self.payload_len,
payload_crc32: crc32fast::hash(payload),
}
}
}
fn read_checkpoint_payload_info(
dir: &dyn Directory,
path: &str,
) -> PersistenceResult<SegmentPayloadInfo> {
let mut f = dir.open_file(path)?;
let header = read_checkpoint_payload_header(&mut *f)?;
let mut payload = Vec::new();
read_checkpoint_payload_into_reader(&mut *f, &header, &mut payload)?;
Ok(header.payload_info(&payload))
}
fn read_checkpoint_payload_into(
dir: &dyn Directory,
path: &str,
payload: &mut Vec<u8>,
) -> PersistenceResult<()> {
let mut f = dir.open_file(path)?;
let header = read_checkpoint_payload_header(&mut *f)?;
match read_checkpoint_payload_into_reader(&mut *f, &header, payload) {
Ok(()) => Ok(()),
Err(err) => {
payload.clear();
Err(err)
}
}
}
fn read_checkpoint_payload_into_reader<R: Read + ?Sized>(
f: &mut R,
header: &CheckpointPayloadHeader,
payload: &mut Vec<u8>,
) -> PersistenceResult<()> {
payload.clear();
let reserve = header.payload_len.min(1 << 20);
if payload.capacity() < reserve {
payload.reserve(reserve - payload.capacity());
}
let n = std::io::Read::take(&mut *f, header.payload_len as u64).read_to_end(payload)?;
if n < header.payload_len {
return Err(PersistenceError::Format(format!(
"checkpoint payload truncated: got {n} of {} bytes",
header.payload_len
)));
}
header.verify_payload(payload)?;
Ok(())
}
fn read_checkpoint_payload(dir: &dyn Directory, path: &str) -> PersistenceResult<Vec<u8>> {
let mut payload = Vec::new();
read_checkpoint_payload_into(dir, path, &mut payload)?;
Ok(payload)
}
pub fn try_index_name(id: u64, kind: &str) -> PersistenceResult<String> {
index_sidecar_name(id, kind)
}
pub fn index_name(id: u64, kind: &str) -> String {
try_index_name(id, kind).unwrap_or_else(|e| panic!("invalid segstore index kind: {e}"))
}
#[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(Debug, Clone, Copy, Default)]
pub struct DefaultStore<Id, Item> {
_marker: PhantomData<fn() -> (Id, Item)>,
}
impl<Id, Item> DefaultStore<Id, Item> {
pub fn new() -> Self {
Self {
_marker: PhantomData,
}
}
}
impl<Id, Item> Store for DefaultStore<Id, Item>
where
Id: Clone + Eq + Hash + Serialize + DeserializeOwned,
Item: Clone + Serialize + DeserializeOwned,
{
type Id = Id;
type Item = Item;
type Segment = Vec<(Id, Item)>;
fn build_segment(&self, batch: &[(Id, Item)]) -> Self::Segment {
batch.to_vec()
}
fn merge_segments(
&self,
segments: &[&Self::Segment],
live: &dyn Fn(&Id) -> bool,
) -> Self::Segment {
segments
.iter()
.flat_map(|segment| segment.iter())
.filter(|(id, _)| live(id))
.cloned()
.collect()
}
fn segment_len(&self, segment: &Self::Segment) -> usize {
segment.len()
}
fn live_len(&self, segment: &Self::Segment, live: &dyn Fn(&Id) -> bool) -> Option<usize> {
Some(segment.iter().filter(|(id, _)| live(id)).count())
}
}
pub struct SidecarEnvelope;
impl SidecarEnvelope {
pub fn encode(
magic: &[u8; 8],
version: u32,
segment_id: u64,
recipe: &[u8],
payload: &[u8],
) -> PersistenceResult<Vec<u8>> {
let recipe_len = u32::try_from(recipe.len()).map_err(|_| {
PersistenceError::InvalidConfig(format!(
"sidecar recipe too large: {} bytes (max {})",
recipe.len(),
u32::MAX
))
})?;
let mut bytes =
Vec::with_capacity(SIDECAR_ENVELOPE_HEADER_BYTES + recipe.len() + payload.len());
bytes.extend_from_slice(magic);
bytes.extend_from_slice(&version.to_le_bytes());
bytes.extend_from_slice(&segment_id.to_le_bytes());
bytes.extend_from_slice(&recipe_len.to_le_bytes());
bytes.extend_from_slice(&0u32.to_le_bytes());
bytes.extend_from_slice(recipe);
bytes.extend_from_slice(payload);
let crc = sidecar_envelope_crc(&bytes);
bytes[24..28].copy_from_slice(&crc.to_le_bytes());
Ok(bytes)
}
pub fn decode<'a>(
expected_magic: &[u8; 8],
expected_version: u32,
expected_segment_id: u64,
expected_recipe: &[u8],
bytes: &'a [u8],
) -> PersistenceResult<&'a [u8]> {
if bytes.len() < SIDECAR_ENVELOPE_HEADER_BYTES {
return Err(PersistenceError::Format(
"sidecar envelope header is truncated".into(),
));
}
if &bytes[..8] != expected_magic {
return Err(PersistenceError::Format(
"sidecar envelope magic mismatch".into(),
));
}
let version = u32::from_le_bytes(bytes[8..12].try_into().unwrap());
if version != expected_version {
return Err(PersistenceError::Format(format!(
"sidecar envelope version mismatch: got {version}, expected {expected_version}"
)));
}
let segment_id = u64::from_le_bytes(bytes[12..20].try_into().unwrap());
if segment_id != expected_segment_id {
return Err(PersistenceError::Format(format!(
"sidecar envelope segment id mismatch: got {segment_id}, expected {expected_segment_id}"
)));
}
let recipe_len = u32::from_le_bytes(bytes[20..24].try_into().unwrap()) as usize;
let recipe_start = SIDECAR_ENVELOPE_HEADER_BYTES;
let recipe_end = recipe_start
.checked_add(recipe_len)
.ok_or_else(|| PersistenceError::Format("sidecar recipe length overflow".into()))?;
if bytes.len() < recipe_end {
return Err(PersistenceError::Format(
"sidecar envelope recipe is truncated".into(),
));
}
let expected_crc = u32::from_le_bytes(bytes[24..28].try_into().unwrap());
let actual_crc = sidecar_envelope_crc(bytes);
if actual_crc != expected_crc {
return Err(PersistenceError::CrcMismatch {
expected: expected_crc,
actual: actual_crc,
});
}
if &bytes[recipe_start..recipe_end] != expected_recipe {
return Err(PersistenceError::Format(
"sidecar envelope recipe mismatch".into(),
));
}
Ok(&bytes[recipe_end..])
}
}
fn sidecar_envelope_crc(bytes: &[u8]) -> u32 {
let mut hasher = crc32fast::Hasher::new();
hasher.update(&bytes[..24]);
hasher.update(&bytes[28..]);
hasher.finalize()
}
#[derive(Serialize, Deserialize)]
enum Op<Id, Item> {
Add(Id, Item),
Delete(Id),
}
#[derive(Deserialize)]
struct Manifest<Id> {
next_seg_id: u64,
segment_ids: Vec<u64>,
tombstones: Vec<Id>,
}
#[derive(Serialize)]
struct ManifestRef<'a, Id> {
next_seg_id: u64,
segment_ids: &'a [u64],
tombstones: &'a [&'a Id],
}
struct PubState<S: Store> {
segments: Arc<Vec<Arc<S::Segment>>>,
segment_ids: Arc<Vec<u64>>,
tombstones: Arc<HashSet<S::Id>>,
}
pub struct SegmentCatalog<Id> {
dir: Arc<dyn Directory>,
epoch: u64,
next_segment_id: u64,
segment_ids: Vec<u64>,
tombstones: HashSet<Id>,
}
impl<Id> SegmentCatalog<Id>
where
Id: Eq + Hash + DeserializeOwned,
{
pub fn open(dir: Arc<dyn Directory>) -> PersistenceResult<Self> {
reject_legacy_formats(&*dir)?;
let mut epoch = 0u64;
let mut next_segment_id = 0u64;
let mut segment_ids = Vec::new();
let mut tombstones = HashSet::new();
if dir.exists(MANIFEST_PATH) {
let ckpt = CheckpointFile::new(dir.clone());
let (e, manifest): (u64, Manifest<Id>) = ckpt.read_postcard(MANIFEST_PATH)?;
epoch = e;
next_segment_id = manifest.next_seg_id;
segment_ids = manifest.segment_ids;
tombstones = manifest.tombstones.into_iter().collect();
}
Ok(Self {
dir,
epoch,
next_segment_id,
segment_ids,
tombstones,
})
}
pub fn epoch(&self) -> u64 {
self.epoch
}
pub fn next_segment_id(&self) -> u64 {
self.next_segment_id
}
pub fn segment_ids(&self) -> &[u64] {
&self.segment_ids
}
pub fn segment_count(&self) -> usize {
self.segment_ids.len()
}
pub fn tombstone_count(&self) -> usize {
self.tombstones.len()
}
pub fn is_live(&self, id: &Id) -> bool {
!self.tombstones.contains(id)
}
pub fn dir(&self) -> &Arc<dyn Directory> {
&self.dir
}
pub fn segment_name(&self, id: u64) -> PersistenceResult<String> {
self.ensure_segment_id(id)?;
Ok(seg_path(id))
}
pub fn segment_file_path(&self, id: u64) -> PersistenceResult<Option<std::path::PathBuf>> {
Ok(self.dir.file_path(&self.segment_name(id)?))
}
pub fn open_segment_file(&self, id: u64) -> PersistenceResult<Box<dyn std::io::Read + Send>> {
self.dir.open_file(&self.segment_name(id)?)
}
pub fn segment_payload_info(&self, id: u64) -> PersistenceResult<SegmentPayloadInfo> {
read_checkpoint_payload_info(&*self.dir, &self.segment_name(id)?)
}
pub fn read_segment_payload(&self, id: u64) -> PersistenceResult<Vec<u8>> {
read_checkpoint_payload(&*self.dir, &self.segment_name(id)?)
}
pub fn read_segment_payload_into(
&self,
id: u64,
payload: &mut Vec<u8>,
) -> PersistenceResult<()> {
read_checkpoint_payload_into(&*self.dir, &self.segment_name(id)?, payload)
}
pub fn read_segment<Segment>(&self, id: u64) -> PersistenceResult<Segment>
where
Segment: DeserializeOwned,
{
let ckpt = CheckpointFile::new(self.dir.clone());
let (_, segment) = ckpt.read_postcard(&self.segment_name(id)?)?;
Ok(segment)
}
pub fn try_index_name(&self, id: u64, kind: &str) -> PersistenceResult<String> {
self.ensure_segment_id(id)?;
try_index_name(id, kind)
}
pub fn index_name(&self, id: u64, kind: &str) -> String {
self.try_index_name(id, kind)
.unwrap_or_else(|e| panic!("invalid segstore catalog index name: {e}"))
}
fn ensure_segment_id(&self, id: u64) -> PersistenceResult<()> {
if self.segment_ids.binary_search(&id).is_ok() {
Ok(())
} else {
Err(PersistenceError::NotFound(format!(
"segment id {id} is not in the checkpoint manifest"
)))
}
}
}
pub struct View<S: Store> {
segments: Arc<Vec<Arc<S::Segment>>>,
segment_ids: Arc<Vec<u64>>,
tombstones: Arc<HashSet<S::Id>>,
}
impl<S: Store> View<S> {
pub fn segments(&self) -> &[Arc<S::Segment>] {
&self.segments
}
pub fn segment_ids(&self) -> &[u64] {
&self.segment_ids
}
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(),
segment_ids: state.segment_ids.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,
segment_ids: Vec<u64>,
next_seg_id: u64,
persisted_ids: HashSet<u64>,
}
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(MANIFEST_PATH).is_none() {
return Err(PersistenceError::InvalidConfig(
"SyncPolicy::Fsync requires a filesystem-backed Directory".into(),
));
}
reject_legacy_formats(&*dir)?;
let mut segments: Vec<Arc<S::Segment>> = Vec::new();
let mut segment_ids: Vec<u64> = Vec::new();
let mut tombstones: HashSet<S::Id> = HashSet::new();
let mut epoch = 0u64;
let mut next_seg_id = 0u64;
if dir.exists(MANIFEST_PATH) {
let ckpt = CheckpointFile::new(dir.clone());
let (e, manifest): (u64, Manifest<S::Id>) = ckpt.read_postcard(MANIFEST_PATH)?;
epoch = e;
next_seg_id = manifest.next_seg_id;
tombstones = manifest.tombstones.into_iter().collect();
for id in manifest.segment_ids {
let (_, seg): (u64, S::Segment) = ckpt.read_postcard(&seg_path(id))?;
segments.push(Arc::new(seg));
segment_ids.push(id);
}
}
let persisted_ids: HashSet<u64> = segment_ids.iter().copied().collect();
let durable = dir.file_path(MANIFEST_PATH).is_some();
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("") {
let mut garbage = Vec::new();
for name in names {
if let Some(k) = name
.strip_prefix(WAL_PREFIX)
.and_then(|s| s.parse::<u64>().ok())
{
if k != epoch {
garbage.push(name);
}
} else if let Some(k) = name
.strip_prefix(SEG_PREFIX)
.and_then(|s| s.parse::<u64>().ok())
{
if !persisted_ids.contains(&k) {
garbage.push(name);
}
} else if let Some(k) = idx_seg_id(&name) {
if !persisted_ids.contains(&k) {
garbage.push(name);
}
}
}
delete_files_best_effort(&*dir, garbage, durable);
}
let wal = RecordLogWriter::new(dir.clone(), live_wal);
let published = Arc::new(std::sync::RwLock::new(Arc::new(PubState {
segments: Arc::new(segments.clone()),
segment_ids: Arc::new(segment_ids.clone()),
tombstones: Arc::new(tombstones.clone()),
})));
Ok(Self {
store,
dir,
buffer,
segments,
segment_ids,
tombstones,
wal,
epoch,
next_seg_id,
persisted_ids,
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()),
segment_ids: Arc::new(self.segment_ids.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);
let id = self.alloc_id();
self.segments.push(Arc::new(seg));
self.segment_ids.push(id);
self.buffer.clear();
}
fn alloc_id(&mut self) -> u64 {
let id = self.next_seg_id;
self.next_seg_id += 1;
id
}
fn gc_orphan_segments(&mut self, keep: &HashSet<u64>, durable: bool, mut garbage: Vec<String>) {
self.persisted_ids.retain(|id| keep.contains(id));
if let Ok(names) = self.dir.list_dir("") {
for name in names {
if let Some(k) = name
.strip_prefix(SEG_PREFIX)
.and_then(|s| s.parse::<u64>().ok())
{
if !keep.contains(&k) {
garbage.push(name);
}
} else if let Some(k) = idx_seg_id(&name) {
if !keep.contains(&k) {
garbage.push(name);
}
}
}
}
delete_files_best_effort(&*self.dir, garbage, durable);
}
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 refs: Vec<&S::Segment> = self.segments.iter().map(|a| &**a).collect();
let merged = self
.store
.merge_segments(&refs, &|id| !tombstones.contains(id));
stats.merges = 1;
stats.items_merged = self.store.segment_len(&merged);
if stats.items_merged > 0 {
let id = self.alloc_id();
self.segments = vec![Arc::new(merged)];
self.segment_ids = vec![id];
} else {
self.segments = vec![];
self.segment_ids = 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]).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();
let old_ids = std::mem::take(&mut self.segment_ids);
self.segment_ids = old_ids
.into_iter()
.enumerate()
.filter(|(i, _)| merged_idx.binary_search(i).is_err())
.map(|(_, id)| id)
.collect();
if n > 0 {
let id = self.alloc_id();
self.segments.push(Arc::new(merged));
self.segment_ids.push(id);
}
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();
debug_assert_eq!(self.segments.len(), self.segment_ids.len());
let new_epoch = self.epoch + 1;
let durable = self.dir.file_path(MANIFEST_PATH).is_some();
let ckpt = CheckpointFile::new(self.dir.clone());
let to_write: Vec<(usize, u64)> = self
.segment_ids
.iter()
.enumerate()
.filter(|(_, id)| !self.persisted_ids.contains(id))
.map(|(i, &id)| (i, id))
.collect();
for (idx, id) in to_write {
let seg = &*self.segments[idx];
let seg_write = if durable {
ckpt.write_postcard_durable(&seg_path(id), 0, seg)
} else {
ckpt.write_postcard(&seg_path(id), 0, seg)
};
seg_write.map_err(|e| size_cap_context(e, &format!("segment {id}")))?;
self.persisted_ids.insert(id);
}
let tomb_refs: Vec<&S::Id> = self.tombstones.iter().collect();
let manifest = ManifestRef {
next_seg_id: self.next_seg_id,
segment_ids: &self.segment_ids,
tombstones: &tomb_refs,
};
let manifest_write = if durable {
ckpt.write_postcard_durable(MANIFEST_PATH, new_epoch, &manifest)
} else {
ckpt.write_postcard(MANIFEST_PATH, new_epoch, &manifest)
};
manifest_write.map_err(|e| size_cap_context(e, "manifest (segment ids + tombstones)"))?;
let old_epoch = self.epoch;
self.wal = RecordLogWriter::new(self.dir.clone(), wal_path(new_epoch));
self.epoch = new_epoch;
let keep: HashSet<u64> = self.segment_ids.iter().copied().collect();
self.gc_orphan_segments(&keep, durable, vec![wal_path(old_epoch)]);
self.republish();
Ok(())
}
pub fn segments(&self) -> &[Arc<S::Segment>] {
&self.segments
}
pub fn segment_ids(&self) -> &[u64] {
&self.segment_ids
}
pub fn dir(&self) -> &Arc<dyn Directory> {
&self.dir
}
pub fn try_index_name(&self, id: u64, kind: &str) -> PersistenceResult<String> {
try_index_name(id, kind)
}
pub fn index_name(&self, id: u64, kind: &str) -> String {
self.try_index_name(id, kind)
.unwrap_or_else(|e| panic!("invalid segstore index kind: {e}"))
}
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;
#[test]
fn size_cap_context_makes_the_blob_error_actionable() {
let raw = PersistenceError::Format(
"checkpoint payload too large: 300000000 bytes (max 268435456)".into(),
);
let wrapped = size_cap_context(raw, "segment 7");
let msg = wrapped.to_string();
assert!(msg.contains("segment 7"), "names the artifact: {msg}");
assert!(
msg.contains("max_merged_len"),
"names the item-count lever: {msg}"
);
assert!(
msg.contains("checkpoint payload too large"),
"preserves the original detail: {msg}"
);
}
#[test]
fn size_cap_context_passes_unrelated_errors_through() {
let before = PersistenceError::InvalidState("something else".into()).to_string();
let after = size_cap_context(
PersistenceError::InvalidState("something else".into()),
"segment 1",
)
.to_string();
assert_eq!(after, before, "non-cap errors are unchanged");
}
#[test]
fn catalog_payload_reader_rejects_truncated_length_claim() {
use std::io::Read;
let dir = MemoryDirectory::arc();
let seg_id = {
let mut s = SegmentedStore::open(dir.clone(), Kv, 1).unwrap();
s.add(1, "a".into()).unwrap();
s.checkpoint().unwrap();
s.segment_ids()[0]
};
let name = seg_path(seg_id);
let mut file = dir.open_file(&name).unwrap();
let mut bytes = Vec::new();
file.read_to_end(&mut bytes).unwrap();
let len_offset = 4 + 4 + 8;
let claimed = 4_u64 * 1024 * 1024;
bytes[len_offset..len_offset + 8].copy_from_slice(&claimed.to_le_bytes());
dir.atomic_write(&name, &bytes).unwrap();
let catalog = SegmentCatalog::<u32>::open(dir).unwrap();
let err = catalog
.read_segment_payload(seg_id)
.unwrap_err()
.to_string();
assert!(
err.contains("truncated") || err.to_lowercase().contains("eof"),
"expected truncation error, got: {err}"
);
}
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()
.flat_map(|s| s.iter())
.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()
.flat_map(|s| s.iter())
.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 default_store_implements_the_vec_segment_pattern() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, DefaultStore::<u32, String>::new(), 2).unwrap();
s.add(1, "a".into()).unwrap();
s.add(2, "b".into()).unwrap();
assert_eq!(s.segment_count(), 1);
assert_eq!(
s.segments()[0].as_ref(),
&vec![(1, "a".into()), (2, "b".into())]
);
s.delete(2).unwrap();
assert_eq!(
s.space_amplification(),
Some(2.0),
"DefaultStore exposes live_len for tombstone policy"
);
s.compact().unwrap();
assert_eq!(s.tombstone_count(), 0);
assert_eq!(s.segments()[0].as_ref(), &vec![(1, "a".into())]);
}
#[test]
fn sidecar_envelope_round_trips_payload() {
let magic = b"SIDETST1";
let recipe = b"demo-v1";
let payload = b"payload bytes";
let bytes = SidecarEnvelope::encode(magic, 2, 7, recipe, payload).unwrap();
let decoded = SidecarEnvelope::decode(magic, 2, 7, recipe, &bytes).unwrap();
assert_eq!(decoded, payload);
}
#[test]
fn sidecar_envelope_rejects_corrupt_payload_by_crc() {
let magic = b"SIDETST1";
let recipe = b"demo-v1";
let mut bytes = SidecarEnvelope::encode(magic, 2, 7, recipe, b"payload").unwrap();
let last = bytes.len() - 1;
bytes[last] ^= 0xff;
let err = SidecarEnvelope::decode(magic, 2, 7, recipe, &bytes).unwrap_err();
assert!(
matches!(err, PersistenceError::CrcMismatch { .. }),
"corrupt sidecar bytes should fail CRC, got: {err}"
);
}
#[test]
fn sidecar_envelope_distinguishes_stale_recipe_from_corruption() {
let magic = b"SIDETST1";
let bytes = SidecarEnvelope::encode(magic, 2, 7, b"demo-v1", b"payload").unwrap();
let err = SidecarEnvelope::decode(magic, 2, 7, b"demo-v2", &bytes).unwrap_err();
assert!(
err.to_string().contains("recipe mismatch"),
"valid but stale sidecars should be rebuildable mismatches, got: {err}"
);
}
#[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 re_add_of_a_live_id_double_lives_there_is_no_replace() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
s.add(1, "a".into()).unwrap();
s.add(2, "x".into()).unwrap(); s.add(1, "b".into()).unwrap(); let n_live_1 = live_set(&s).iter().filter(|(id, _)| *id == 1).count();
assert_eq!(
n_live_1, 2,
"a re-add double-lives the id; no last-write-wins"
);
s.delete(1).unwrap();
s.add(1, "c".into()).unwrap();
let live_1: Vec<String> = live_set(&s)
.into_iter()
.filter(|(id, _)| *id == 1)
.map(|(_, v)| v)
.collect();
assert_eq!(
live_1,
vec!["a".to_string(), "c".to_string()],
"delete-then-add revived the old value: no replace in the per-id model"
);
}
#[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 manifest = root.join(MANIFEST_PATH);
let mut bytes = std::fs::read(&manifest).unwrap();
let mid = bytes.len() / 2;
bytes[mid] ^= 0xFF;
std::fs::write(&manifest, &bytes).unwrap();
let dir = durability::FsDirectory::arc(&root).unwrap();
let res = SegmentedStore::open(dir, Kv, 2);
assert!(
res.is_err(),
"a CRC-corrupt manifest 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!("{MANIFEST_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);
}
struct CountDir {
inner: Arc<dyn Directory>,
writes: Arc<std::sync::Mutex<Vec<String>>>,
}
impl CountDir {
fn wrap(
inner: Arc<dyn Directory>,
) -> (Arc<dyn Directory>, Arc<std::sync::Mutex<Vec<String>>>) {
let writes = Arc::new(std::sync::Mutex::new(Vec::new()));
let dir: Arc<dyn Directory> = Arc::new(CountDir {
inner,
writes: writes.clone(),
});
(dir, writes)
}
}
impl Directory for CountDir {
fn create_file(&self, p: &str) -> PersistenceResult<Box<dyn std::io::Write + Send>> {
self.writes.lock().unwrap().push(p.to_string());
self.inner.create_file(p)
}
fn atomic_write(&self, p: &str, d: &[u8]) -> PersistenceResult<()> {
self.writes.lock().unwrap().push(p.to_string());
self.inner.atomic_write(p, d)
}
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.inner.delete(p)
}
fn atomic_rename(&self, a: &str, b: &str) -> PersistenceResult<()> {
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.inner.append_file(p)
}
fn file_path(&self, p: &str) -> Option<std::path::PathBuf> {
self.inner.file_path(p)
}
}
fn seg_file_count(dir: &Arc<dyn Directory>) -> usize {
dir.list_dir("")
.unwrap()
.into_iter()
.filter(|n| n.starts_with(SEG_PREFIX))
.count()
}
#[test]
fn checkpoint_writes_only_new_segment_files() {
let (dir, writes) = CountDir::wrap(MemoryDirectory::arc());
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
for i in 0..4u32 {
s.add(i, format!("v{i}")).unwrap(); }
s.checkpoint().unwrap(); writes.lock().unwrap().clear();
s.add(4, "e".into()).unwrap();
s.add(5, "f".into()).unwrap(); s.checkpoint().unwrap();
let w = writes.lock().unwrap();
let seg_writes: Vec<&String> = w.iter().filter(|p| p.starts_with(SEG_PREFIX)).collect();
assert_eq!(
seg_writes.len(),
1,
"only the one new segment file is rewritten, not the unchanged two: {:?}",
*w
);
assert!(
seg_writes[0].ends_with(".2"),
"and it is the new segment's file: {:?}",
seg_writes
);
}
#[test]
fn compaction_gcs_superseded_segment_files() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir.clone(), Kv, 2).unwrap();
for i in 0..8u32 {
s.add(i, format!("v{i}")).unwrap(); }
s.checkpoint().unwrap();
assert_eq!(seg_file_count(&dir), 4, "one file per segment");
s.compact().unwrap(); assert_eq!(s.segment_count(), 1);
assert_eq!(
seg_file_count(&dir),
1,
"the merged-away segment files are GC'd; only the result remains"
);
}
#[test]
fn best_effort_delete_batch_syncs_parent_once() {
struct SyncCountDir {
inner: Arc<dyn Directory>,
syncs: std::sync::atomic::AtomicUsize,
}
impl Directory for SyncCountDir {
fn create_file(&self, p: &str) -> PersistenceResult<Box<dyn std::io::Write + Send>> {
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.inner.delete(p)
}
fn atomic_rename(&self, a: &str, b: &str) -> PersistenceResult<()> {
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.inner.append_file(p)
}
fn atomic_write(&self, p: &str, d: &[u8]) -> PersistenceResult<()> {
self.inner.atomic_write(p, d)
}
fn file_path(&self, p: &str) -> Option<std::path::PathBuf> {
Some(std::path::PathBuf::from("/tmp/segstore-sync-count").join(p))
}
fn durable_sync_parent_dir(&self, _path: &str) -> PersistenceResult<()> {
self.syncs
.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
Ok(())
}
}
let dir = SyncCountDir {
inner: MemoryDirectory::arc(),
syncs: std::sync::atomic::AtomicUsize::new(0),
};
dir.atomic_write("a", b"a").unwrap();
dir.atomic_write("b", b"b").unwrap();
delete_files_best_effort(&dir, vec!["a".into(), "b".into(), "missing".into()], true);
assert!(!dir.exists("a"));
assert!(!dir.exists("b"));
assert_eq!(
dir.syncs.load(std::sync::atomic::Ordering::Relaxed),
1,
"multiple GC deletes share one parent-directory sync"
);
delete_files_best_effort(&dir, vec!["missing".into()], true);
assert_eq!(
dir.syncs.load(std::sync::atomic::Ordering::Relaxed),
1,
"missing files do not force a parent-directory sync"
);
dir.atomic_write("c", b"c").unwrap();
delete_files_best_effort(&dir, vec!["c".into()], false);
assert_eq!(
dir.syncs.load(std::sync::atomic::Ordering::Relaxed),
1,
"non-durable cleanup does not sync"
);
}
#[test]
fn index_sidecars_are_gced_with_their_segments() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir.clone(), Kv, 2).unwrap();
for i in 0..8u32 {
s.add(i, format!("v{i}")).unwrap(); }
s.checkpoint().unwrap();
for &id in s.segment_ids() {
dir.atomic_write(&s.index_name(id, "toy"), b"built-index")
.unwrap();
}
let idx_count = |d: &Arc<dyn Directory>| {
d.list_dir("")
.unwrap()
.into_iter()
.filter(|n| idx_seg_id(n).is_some())
.count()
};
assert_eq!(idx_count(&dir), 4, "one sidecar per segment");
s.compact().unwrap();
assert_eq!(s.segment_count(), 1);
assert_eq!(
idx_count(&dir),
0,
"sidecars of compacted-away segments are GC'd"
);
dir.atomic_write(&s.index_name(9999, "toy"), b"orphan")
.unwrap();
drop(s);
let _ = SegmentedStore::open(dir.clone(), Kv, 2).unwrap();
assert_eq!(idx_count(&dir), 0, "orphan sidecar GC'd on open");
}
#[test]
fn legacy_sidecar_names_are_still_gced() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir.clone(), Kv, 2).unwrap();
for i in 0..4u32 {
s.add(i, format!("v{i}")).unwrap();
}
s.checkpoint().unwrap();
let stale_id = s.segment_ids()[0];
dir.atomic_write(&format!("{IDX_PREFIX}{stale_id}.hnsw.v1"), b"old-index")
.unwrap();
s.compact().unwrap();
assert!(
!dir.exists(&format!("{IDX_PREFIX}{stale_id}.hnsw.v1")),
"legacy dotted-kind sidecar is removed when its segment is compacted away"
);
}
#[test]
fn index_sidecar_kind_is_checked() {
let dir = MemoryDirectory::arc();
let s = SegmentedStore::open(dir, Kv, 2).unwrap();
assert_eq!(
try_index_name(7, "hnsw_v1-fast").unwrap(),
"segstore.idx.7.hnsw_v1-fast"
);
assert_eq!(
s.try_index_name(7, "hnsw_v1-fast").unwrap(),
try_index_name(7, "hnsw_v1-fast").unwrap()
);
assert_eq!(
s.index_name(7, "hnsw_v1-fast"),
index_name(7, "hnsw_v1-fast")
);
for kind in ["", "hnsw.v1", "hnsw/tmp", "../hnsw", ".tmp", "hnsw tmp"] {
assert!(
matches!(
try_index_name(7, kind),
Err(PersistenceError::InvalidConfig(_))
),
"kind {kind:?} should be rejected by the free helper"
);
assert!(
matches!(
s.try_index_name(7, kind),
Err(PersistenceError::InvalidConfig(_))
),
"kind {kind:?} should be rejected"
);
}
}
#[test]
#[should_panic(expected = "invalid segstore index kind")]
fn index_name_panics_on_invalid_kind() {
let _ = index_name(7, "hnsw.v1");
}
#[test]
#[should_panic(expected = "invalid segstore index kind")]
fn store_index_name_panics_on_invalid_kind() {
let dir = MemoryDirectory::arc();
let s = SegmentedStore::open(dir, Kv, 2).unwrap();
let _ = s.index_name(7, "hnsw.v1");
}
#[test]
fn index_sidecar_parser_recognizes_legacy_names_for_gc() {
assert_eq!(idx_seg_id("segstore.idx.7.hnsw_v1-fast"), Some(7));
assert_eq!(
idx_seg_id("segstore.idx.7.hnsw.v1"),
Some(7),
"legacy dotted kind is still classified for cleanup"
);
for name in [
"segstore.idx.7",
"segstore.idx.7.",
"segstore.idx.not-a-number.hnsw",
"segstore.idx..hnsw",
"not-segstore.idx.7.hnsw",
] {
assert_eq!(idx_seg_id(name), None, "{name:?} should not parse");
}
}
#[test]
fn v02_ckpt_format_is_rejected() {
let dir = MemoryDirectory::arc();
dir.atomic_write(LEGACY_CKPT_PATH, b"a 0.2 checkpoint blob")
.unwrap();
let err = SegmentedStore::open(dir, Kv, 2);
assert!(
matches!(err, Err(PersistenceError::InvalidConfig(_))),
"a 0.2 on-disk store is rejected, not misread"
);
}
#[test]
fn corrupt_segment_file_is_rejected() {
let root = temp_root("corrupt-seg");
{
let dir = durability::FsDirectory::arc(&root).unwrap();
let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
s.add(1, "aaaaaaaa".into()).unwrap();
s.add(2, "bbbbbbbb".into()).unwrap(); s.checkpoint().unwrap();
}
let seg = root.join(seg_path(0));
let mut bytes = std::fs::read(&seg).unwrap();
let mid = bytes.len() / 2;
bytes[mid] ^= 0xFF;
std::fs::write(&seg, &bytes).unwrap();
let dir = durability::FsDirectory::arc(&root).unwrap();
let res = SegmentedStore::open(dir, Kv, 2);
assert!(
res.is_err(),
"a CRC-corrupt segment file is an error, not silently misread"
);
let _ = std::fs::remove_dir_all(&root);
}
#[test]
fn segment_catalog_reads_manifest_without_decoding_segments() {
let root = temp_root("segment-catalog");
{
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.add(3, "c".into()).unwrap();
s.add(4, "d".into()).unwrap();
s.delete(2).unwrap();
s.checkpoint().unwrap();
}
let seg = root.join(seg_path(0));
let mut bytes = std::fs::read(&seg).unwrap();
let mid = bytes.len() / 2;
bytes[mid] ^= 0xFF;
std::fs::write(&seg, &bytes).unwrap();
let dir = durability::FsDirectory::arc(&root).unwrap();
let res = SegmentedStore::open(dir.clone(), Kv, 2);
assert!(
res.is_err(),
"full store open decodes segment payloads and rejects corruption"
);
let catalog = SegmentCatalog::<u32>::open(dir.clone()).unwrap();
assert_eq!(catalog.epoch(), 1);
assert_eq!(catalog.segment_ids(), &[0, 1]);
assert_eq!(catalog.segment_count(), 2);
assert_eq!(catalog.tombstone_count(), 1);
assert!(catalog.is_live(&1));
assert!(!catalog.is_live(&2));
assert_eq!(catalog.segment_name(1).unwrap(), seg_path(1));
assert_eq!(
catalog.try_index_name(1, "toy").unwrap(),
"segstore.idx.1.toy"
);
assert!(matches!(
catalog.segment_name(99),
Err(PersistenceError::NotFound(_))
));
assert!(catalog.open_segment_file(1).is_ok());
let payload = catalog.read_segment_payload(1).unwrap();
assert!(
!payload.is_empty(),
"payload bytes are available without decoding"
);
let seg1: Vec<(u32, String)> = catalog.read_segment(1).unwrap();
assert_eq!(seg1, vec![(3, "c".into()), (4, "d".into())]);
assert!(
catalog.read_segment_payload(0).is_err(),
"payload reads still validate the segment checkpoint CRC"
);
assert!(
catalog.read_segment::<Vec<(u32, String)>>(0).is_err(),
"reading the corrupt segment should fail when that segment is requested"
);
let _ = std::fs::remove_dir_all(&root);
}
#[test]
fn segment_catalog_payload_info_points_to_validated_payload_bytes() {
use std::io::{Read, Seek};
let root = temp_root("segment-payload-info");
{
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 dir = durability::FsDirectory::arc(&root).unwrap();
let catalog = SegmentCatalog::<u32>::open(dir).unwrap();
let seg_id = catalog.segment_ids()[0];
let info = catalog.segment_payload_info(seg_id).unwrap();
let payload = catalog.read_segment_payload(seg_id).unwrap();
assert_eq!(info.payload_len, payload.len());
assert_eq!(info.payload_crc32, crc32fast::hash(&payload));
info.verify_payload(&payload).unwrap();
let truncated = &payload[..payload.len() - 1];
assert!(matches!(
info.verify_payload(truncated),
Err(PersistenceError::Format(_))
));
let mut corrupt = payload.clone();
corrupt[0] ^= 0xFF;
assert!(matches!(
info.verify_payload(&corrupt),
Err(PersistenceError::CrcMismatch { .. })
));
let path = catalog.segment_file_path(seg_id).unwrap().unwrap();
let mut file = std::fs::File::open(path).unwrap();
file.seek(std::io::SeekFrom::Start(info.payload_offset))
.unwrap();
let mut from_file = vec![0u8; info.payload_len];
file.read_exact(&mut from_file).unwrap();
assert_eq!(from_file, payload);
let _ = std::fs::remove_dir_all(&root);
}
#[test]
fn segment_catalog_reads_source_payloads_and_exposes_liveness_separately() {
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.delete(2).unwrap();
s.checkpoint().unwrap();
}
let catalog = SegmentCatalog::<u32>::open(dir).unwrap();
let segment_id = catalog.segment_ids()[0];
let segment: Vec<(u32, String)> = catalog.read_segment(segment_id).unwrap();
assert_eq!(segment, vec![(1, "a".into()), (2, "b".into())]);
assert!(catalog.is_live(&1));
assert!(!catalog.is_live(&2));
}
#[test]
fn segment_catalog_payload_into_reuses_buffer_and_clears_on_error() {
use std::io::Read;
let dir = MemoryDirectory::arc();
let seg_id = {
let mut s = SegmentedStore::open(dir.clone(), Kv, 1).unwrap();
s.add(1, "a".into()).unwrap();
s.checkpoint().unwrap();
s.segment_ids()[0]
};
let catalog = SegmentCatalog::<u32>::open(dir.clone()).unwrap();
let mut scratch = Vec::with_capacity(1024);
let ptr = scratch.as_ptr();
catalog
.read_segment_payload_into(seg_id, &mut scratch)
.unwrap();
assert_eq!(
scratch.as_ptr(),
ptr,
"a sufficiently large scratch buffer is reused"
);
let good_payload = scratch.clone();
scratch.extend_from_slice(b"stale suffix");
catalog
.read_segment_payload_into(seg_id, &mut scratch)
.unwrap();
assert_eq!(scratch, good_payload, "the destination is cleared first");
let name = seg_path(seg_id);
let mut bytes = Vec::new();
dir.open_file(&name)
.unwrap()
.read_to_end(&mut bytes)
.unwrap();
let last = bytes.len() - 1;
bytes[last] ^= 0xFF;
dir.atomic_write(&name, &bytes).unwrap();
let err = catalog
.read_segment_payload_into(seg_id, &mut scratch)
.unwrap_err();
assert!(
matches!(err, PersistenceError::CrcMismatch { .. }),
"payload corruption is still detected: {err}"
);
assert!(
scratch.is_empty(),
"partial/corrupt reads do not leak bytes"
);
}
#[test]
fn segment_catalog_rejects_legacy_formats() {
let dir = MemoryDirectory::arc();
dir.atomic_write(LEGACY_CKPT_PATH, b"a 0.2 checkpoint blob")
.unwrap();
let err = SegmentCatalog::<u32>::open(dir);
assert!(
matches!(err, Err(PersistenceError::InvalidConfig(_))),
"legacy monolithic checkpoints are rejected consistently"
);
}
#[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:?}");
assert_eq!(
seg_file_count(&mem),
0,
"no leaked segment files after delete-all + compact"
);
}
#[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 segment_ids_align_and_are_stable_across_checkpoint_and_reopen() {
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir.clone(), Kv, 2).unwrap();
for i in 0..6u32 {
s.add(i, format!("v{i}")).unwrap(); }
s.checkpoint().unwrap();
assert_eq!(s.segment_ids().len(), s.segments().len());
assert_eq!(s.segment_ids().len(), 3);
let ids0: Vec<u64> = s.segment_ids().to_vec();
assert_eq!(s.reader().view().segment_ids(), &ids0[..]);
s.checkpoint().unwrap();
assert_eq!(s.segment_ids(), &ids0[..], "no-op checkpoint keeps ids");
s.add(10, "x".into()).unwrap();
s.add(11, "y".into()).unwrap(); s.checkpoint().unwrap();
assert_eq!(&s.segment_ids()[..3], &ids0[..], "old ids unchanged");
assert_eq!(s.segment_ids().len(), 4);
assert!(
!ids0.contains(&s.segment_ids()[3]),
"the new segment got a fresh, never-reused id"
);
let before: Vec<u64> = s.segment_ids().to_vec();
drop(s);
let s2 = SegmentedStore::open(dir, Kv, 2).unwrap();
assert_eq!(
s2.segment_ids(),
&before[..],
"segment ids are stable across a restart (persisted in the manifest)"
);
}
#[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),
]
}
#[derive(Debug, Clone)]
enum CatalogOp {
Add,
Delete(usize),
Checkpoint,
Compact,
CompactTiers,
Reopen,
}
fn catalog_op_strategy() -> impl Strategy<Value = CatalogOp> {
prop_oneof![
3 => Just(CatalogOp::Add),
2 => (0usize..100).prop_map(CatalogOp::Delete),
2 => Just(CatalogOp::Checkpoint),
1 => Just(CatalogOp::Compact),
1 => Just(CatalogOp::CompactTiers),
1 => Just(CatalogOp::Reopen),
]
}
fn catalog_expectation(
s: &SegmentedStore<Kv>,
) -> (u64, u64, Vec<u64>, std::collections::HashSet<u32>) {
(
s.epoch,
s.next_seg_id,
s.segment_ids.clone(),
s.tombstones.clone(),
)
}
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);
}
prop_assert_eq!(s.segment_ids().len(), s.segment_count());
}
let want: Vec<(u32, String)> = model.into_iter().collect();
prop_assert_eq!(live_set(&s), want);
}
}
proptest! {
#![proptest_config(ProptestConfig::with_cases(256))]
#[test]
fn segment_catalog_matches_last_checkpoint_under_random_ops(
ops in proptest::collection::vec(catalog_op_strategy(), 0..160)
) {
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 checkpointed = catalog_expectation(&s);
let mut live_ids: Vec<u32> = Vec::new();
let mut next_id = 0u32;
for op in ops {
match op {
CatalogOp::Add => {
let id = next_id;
next_id += 1;
s.add(id, format!("v{id}")).unwrap();
live_ids.push(id);
}
CatalogOp::Delete(k) => {
if !live_ids.is_empty() {
let id = live_ids.swap_remove(k % live_ids.len());
s.delete(id).unwrap();
}
}
CatalogOp::Checkpoint => {
s.checkpoint().unwrap();
checkpointed = catalog_expectation(&s);
}
CatalogOp::Compact => {
s.compact().unwrap();
checkpointed = catalog_expectation(&s);
}
CatalogOp::CompactTiers => {
if s.compact_tiers().unwrap().merges > 0 {
checkpointed = catalog_expectation(&s);
}
}
CatalogOp::Reopen => {
s = SegmentedStore::open_with_options(dir.clone(), Kv, mk()).unwrap();
}
}
let catalog = SegmentCatalog::<u32>::open(dir.clone()).unwrap();
prop_assert_eq!(catalog.epoch(), checkpointed.0);
prop_assert_eq!(catalog.next_segment_id(), checkpointed.1);
prop_assert_eq!(catalog.segment_ids(), &checkpointed.2[..]);
prop_assert_eq!(catalog.segment_count(), checkpointed.2.len());
prop_assert_eq!(catalog.tombstone_count(), checkpointed.3.len());
for id in 0..next_id {
prop_assert_eq!(catalog.is_live(&id), !checkpointed.3.contains(&id));
}
for &seg_id in catalog.segment_ids() {
prop_assert_eq!(catalog.segment_name(seg_id).unwrap(), seg_path(seg_id));
prop_assert!(catalog.open_segment_file(seg_id).is_ok());
let _: Vec<(u32, String)> = catalog.read_segment(seg_id).unwrap();
}
prop_assert!(matches!(
catalog.segment_name(u64::MAX),
Err(PersistenceError::NotFound(_))
));
}
}
}
proptest! {
#![proptest_config(ProptestConfig::with_cases(128))]
#[test]
fn segment_catalog_rejects_manifest_corruption_at_any_byte(offset in 0usize..256) {
use std::io::Read;
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.delete(1).unwrap();
s.checkpoint().unwrap();
}
let mut file = dir.open_file(MANIFEST_PATH).unwrap();
let mut bytes = Vec::new();
file.read_to_end(&mut bytes).unwrap();
let header_len = durability::checkpoint::CheckpointHeader::SIZE;
prop_assume!(bytes.len() > header_len);
let i = header_len + (offset % (bytes.len() - header_len));
bytes[i] ^= 0x80;
dir.atomic_write(MANIFEST_PATH, &bytes).unwrap();
prop_assert!(
SegmentCatalog::<u32>::open(dir).is_err(),
"corrupt manifest byte {i} was accepted"
);
}
}
}