use std::hash::Hash;
use std::sync::Arc;
use std::sync::atomic::Ordering;
use std::time::{Duration, Instant};
use super::block::BLOCK_HEADER_LEN;
use super::config::SegConfig;
use super::core::{SegCore, View};
use super::generation::{Append, Generation, InsertStep};
use super::hash::key_hash;
use super::manifest::{self, GenRecord, GenState, Manifest, PublishError};
use crate::entry::entry_size;
use crate::error::{DbError, DbResult};
use crate::key::Key;
use crate::sync;
const WAIT_SLICE: Duration = Duration::from_millis(20);
#[derive(Debug, Clone, Copy)]
pub(crate) enum Admission {
Deadline(Instant),
UntilSealFails { fallback: Instant },
}
impl Admission {
pub(crate) fn deadline(config: &SegConfig) -> DbResult<Self> {
Ok(Self::Deadline(config.seal_deadline()?))
}
pub(crate) fn until_seal_fails(config: &SegConfig) -> DbResult<Self> {
Ok(Self::UntilSealFails {
fallback: config.seal_deadline()?,
})
}
}
pub(crate) fn check_entry_size(key_len: usize, value_len: usize) -> DbResult<()> {
let fits = u32::try_from(value_len).is_ok_and(|value_len| {
BLOCK_HEADER_LEN as u64 + entry_size(key_len, value_len) <= u64::from(u32::MAX)
});
if fits {
Ok(())
} else {
Err(DbError::Client(
"the entry is too large for a segment block",
))
}
}
impl<K: Key + Hash + Eq + Send + Sync + 'static> SegCore<K> {
pub(crate) fn put(&self, key: &K, value: &[u8]) -> DbResult<()> {
self.put_with(key, value, Admission::deadline(&self.config)?)
}
pub(crate) fn put_with(&self, key: &K, value: &[u8], admission: Admission) -> DbResult<()> {
metrics::counter!("armdb.ops", "op" => "put", "tree" => "seg_map").increment(1);
self.write(key, Some(value), admission)
}
pub(crate) fn insert(&self, key: &K, value: &[u8]) -> DbResult<()> {
self.insert_since(key, value, None)
}
pub(crate) fn insert_since(
&self,
key: &K,
value: &[u8],
since_ms: Option<u64>,
) -> DbResult<()> {
metrics::counter!("armdb.ops", "op" => "insert", "tree" => "seg_map").increment(1);
check_entry_size(size_of::<K>(), value.len())?;
let h = key_hash(key.as_bytes(), self.seed);
let admission = Admission::deadline(&self.config)?;
let limits = self.config.limits();
loop {
self.check_writable()?;
let view = self.view();
let active = &view.active;
let mut step = active.insert(h, key, value, None, limits)?;
if step == InsertStep::NeedLower {
let lower = self.exists_in(&view, h, key, false, since_ms);
step = active.insert(h, key, value, lower.as_ref().ok().copied(), limits)?;
if step == InsertStep::NeedLower {
return Err(lower.expect_err("an answer from below never leaves NeedLower"));
}
}
match step {
InsertStep::Done { crossed } => {
if crossed {
self.signal.wake();
}
return Ok(());
}
InsertStep::Exists => return Err(DbError::KeyExists),
InsertStep::Frozen => {}
InsertStep::Full => self.make_room(active, admission)?,
InsertStep::NeedLower => {
return Err(DbError::Internal("insert left NeedLower unresolved"));
}
}
}
}
pub(crate) fn delete(&self, key: &K) -> DbResult<()> {
self.delete_with(key, Admission::deadline(&self.config)?)
}
pub(crate) fn delete_with(&self, key: &K, admission: Admission) -> DbResult<()> {
metrics::counter!("armdb.ops", "op" => "delete", "tree" => "seg_map").increment(1);
self.write(key, None, admission)
}
fn write(&self, key: &K, value: Option<&[u8]>, admission: Admission) -> DbResult<()> {
if let Some(value) = value {
check_entry_size(size_of::<K>(), value.len())?;
}
let h = key_hash(key.as_bytes(), self.seed);
loop {
self.check_writable()?;
let view = self.view();
match view.active.append(h, key, value, self.config.limits())? {
Append::Done { crossed } => {
if crossed {
self.signal.wake();
}
return Ok(());
}
Append::Frozen => {}
Append::Full => self.make_room(&view.active, admission)?,
}
}
}
pub(crate) fn backpressure(&self) -> DbError {
if !self.shut_down.load(Ordering::Acquire) {
metrics::counter!("armdb.seg.backpressure_timeouts", "collection" => self.meta.name)
.increment(1);
}
DbError::SealBackpressure {
collection: self.meta.name,
}
}
fn wait_for_seal(&self, admission: Admission, failures: u64) -> DbResult<()> {
if self.shut_down.load(Ordering::Acquire) {
return Err(self.backpressure());
}
let deadline = match admission {
Admission::UntilSealFails { .. } if self.worker_running() => None,
Admission::Deadline(at) | Admission::UntilSealFails { fallback: at } => Some(at),
};
let now = Instant::now();
let state = sync::lock(&self.seal);
let slice = match deadline {
Some(at) if now >= at => return Err(self.backpressure()),
Some(at) => WAIT_SLICE.min(at - now),
None if state.failures != failures => return Err(self.backpressure()),
None => WAIT_SLICE,
};
metrics::counter!("armdb.seg.backpressure_waits", "collection" => self.meta.name)
.increment(1);
drop(sync::cv_wait_timeout(
&self.seal_cv,
&self.seal,
state,
slice,
));
Ok(())
}
pub(crate) fn make_room(
&self,
full: &Arc<Generation<K>>,
admission: Admission,
) -> DbResult<()> {
let failures = sync::lock(&self.seal).failures;
loop {
self.check_writable()?;
if !Arc::ptr_eq(&self.view().active, full) {
return Ok(());
}
{
let mut manifest = sync::lock(&self.manifest);
if !Arc::ptr_eq(&self.view().active, full) {
return Ok(());
}
if !self.shut_down.load(Ordering::Acquire)
&& manifest.frozen_count() < self.config.max_frozen_generations
{
return self.freeze_locked(&mut manifest);
}
}
self.wait_for_seal(admission, failures)?;
}
}
pub(crate) fn admit_tx(&self) -> DbResult<()> {
self.check_writable()?;
let active = self.view().active.clone();
if active.is_full() && !active.is_frozen() {
self.make_room(&active, Admission::deadline(&self.config)?)?;
}
Ok(())
}
pub(crate) fn seal(&self) -> DbResult<()> {
let admission = Admission::deadline(&self.config)?;
let target = self.view().active.clone();
if target.keys() == 0 {
self.check_writable()?;
return Ok(());
}
self.make_room(&target, admission)
}
pub(crate) fn freeze_locked(&self, manifest: &mut Manifest) -> DbResult<()> {
self.check_writable()?;
let view = self.view();
let old = view.active.clone();
if old.keys() == 0 {
return Ok(());
}
if self.shut_down.load(Ordering::Acquire) {
return Err(self.backpressure());
}
let (reserved, gen_id) = manifest.reserve_gen_id()?;
self.publish_next(manifest, reserved)?;
super::failpoint!(GENERATION_ID_RESERVED);
let mut new = Generation::create(
self.fs.clone(),
&self.gen_root,
gen_id,
&self.config,
0,
self.order,
)?;
new.bind_fence(self.collection_fence.clone());
super::failpoint!(GENERATION_CREATED);
let guards = old.lock_all();
if let Err(e) = self.check_writable() {
new.doom();
return Err(e);
}
let frozen_at_ms = manifest.monotone_time(self.now_ms());
new.set_opened_at_ms(frozen_at_ms);
let next_gsn = old.next_gsn();
let max_gsn = next_gsn - 1;
old.mark_frozen(frozen_at_ms, max_gsn);
new.seed_gsn(next_gsn);
let record = GenRecord {
gen_id,
state: GenState::Active,
shard_count: new.shard_count() as u8,
opened_at_ms: frozen_at_ms,
frozen_at_ms: 0,
min_gsn: next_gsn,
max_gsn: 0,
};
let rollback = |e: DbError| {
old.unmark_frozen();
new.doom();
e
};
let next = match manifest.with_freeze(frozen_at_ms, max_gsn, record) {
Ok(next) => next,
Err(e) => return Err(rollback(e)),
};
match manifest::publish(&*self.fs, &self.dir, &next) {
Ok(()) => {
*manifest = next;
super::failpoint!(FREEZE_PUBLISHED);
}
Err(PublishError::NotPublished(e)) => return Err(rollback(e)),
Err(PublishError::Indeterminate(e)) => {
return Err(self.fence(format!(
"the outcome of the freeze of generation {:#x} is unknown: {e}",
old.id()
)));
}
}
let mut frozen = Vec::with_capacity(view.frozen.len() + 1);
frozen.push(old.clone());
frozen.extend(view.frozen.iter().cloned());
self.set_view(View {
active: Arc::new(new),
frozen,
sealed: view.sealed.clone(),
});
drop(guards);
metrics::counter!("armdb.seg.freezes", "collection" => self.meta.name).increment(1);
self.signal.wake();
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::error::DbError;
use crate::seg::config::SegConfig;
use crate::seg::fs::{FsOpKind, TraceFs};
use crate::seg::manifest::{GenState, MANIFEST_NAME, load};
use crate::seg::seal::sdat_name;
use crate::seg::testkit::{
TestClock, build_collection, key_of, open_core, try_open_core, value,
};
use std::time::Duration;
#[test]
fn fence_stops_append_and_insert_waiting_on_generation_locks() {
for insert in [false, true] {
let dir = tempfile::tempdir().unwrap();
let core = open_core(dir.path(), roomy());
let active = core.view().active.clone();
let guards = active.lock_all();
let waiting = active.observe_index_lock_attempt();
let key = key_of(12);
let h = key_hash(&key, core.seed);
std::thread::scope(|scope| {
let guards = guards;
let active = &active;
let core = &core;
let waiter = scope.spawn(move || {
if insert {
active
.insert(h, &key, b"refused", Some(false), core.config.limits())
.map(drop)
} else {
active
.append(h, &key, Some(b"refused"), core.config.limits())
.map(drop)
}
});
waiting
.recv_timeout(Duration::from_secs(5))
.expect("mutation never reached its index acquisition boundary");
core.fence("waiting operation".into());
drop(guards);
assert!(matches!(
waiter.join().unwrap(),
Err(DbError::CollectionFenced { .. })
));
});
assert_eq!(active.keys(), 0);
assert_eq!(active.next_gsn(), 1);
}
}
#[test]
fn fence_stops_freeze_waiting_on_generation_locks() {
let dir = tempfile::tempdir().unwrap();
let core = open_core(dir.path(), roomy());
core.put(&key_of(1), b"old").unwrap();
let active = core.view().active.clone();
let guards = active.lock_all();
let waiting = active.observe_index_lock_attempt();
std::thread::scope(|scope| {
let guards = guards;
let waiter = scope.spawn(|| core.seal());
waiting
.recv_timeout(Duration::from_secs(5))
.expect("freeze never reached its index acquisition boundary");
let manifest_before = std::fs::read(dir.path().join(MANIFEST_NAME)).unwrap();
core.fence("waiting freeze".into());
drop(guards);
assert!(matches!(
waiter.join().unwrap(),
Err(DbError::CollectionFenced { .. })
));
assert_eq!(
std::fs::read(dir.path().join(MANIFEST_NAME)).unwrap(),
manifest_before
);
});
assert_eq!(core.view().active.id(), 1);
assert!(!active.is_frozen());
assert!(core.view().frozen.is_empty());
assert!(!dir.path().join("gen/0000000000000002").exists());
}
#[test]
fn an_entry_no_block_can_hold_is_refused() {
let largest = (u32::MAX as usize - BLOCK_HEADER_LEN) & !7;
let value_max = largest - 16 - 8;
check_entry_size(8, value_max).unwrap();
assert!(matches!(
check_entry_size(8, value_max + 1),
Err(DbError::Client(_))
));
assert!(matches!(
check_entry_size(8, u32::MAX as usize + 1),
Err(DbError::Client(_))
));
check_entry_size(8, 0).unwrap();
}
fn roomy() -> SegConfig {
SegConfig {
seal_max_keys: 1_000_000,
max_frozen_generations: 64,
..SegConfig::test()
}
}
#[test]
fn writes_are_read_back() {
let dir = tempfile::tempdir().unwrap();
let core = open_core(dir.path(), roomy());
for i in 0..100 {
core.put(&key_of(i), &value(i)).unwrap();
}
core.put(&key_of(7), b"again").unwrap();
core.delete(&key_of(8)).unwrap();
assert_eq!(core.get(&key_of(1)).unwrap(), Some(value(1)));
assert_eq!(core.get(&key_of(7)).unwrap(), Some(b"again".to_vec()));
assert_eq!(core.get(&key_of(8)).unwrap(), None);
assert_eq!(core.len(), 99);
}
#[test]
fn a_delete_masks_a_value_in_an_older_layer() {
let dir = tempfile::tempdir().unwrap();
build_collection(dir.path());
let core = open_core(dir.path(), roomy());
assert!(core.get(&key_of(50)).unwrap().is_some());
core.delete(&key_of(50)).unwrap();
assert_eq!(core.get(&key_of(50)).unwrap(), None);
assert!(!core.contains(&key_of(50)).unwrap());
core.put(&key_of(50), b"back").unwrap();
assert_eq!(core.get(&key_of(50)).unwrap(), Some(b"back".to_vec()));
}
#[test]
fn a_freeze_opens_a_new_generation() {
let dir = tempfile::tempdir().unwrap();
let core = open_core(dir.path(), roomy());
for i in 0..50 {
core.put(&key_of(i), &value(i)).unwrap();
}
core.seal().unwrap();
let view = core.view();
assert_eq!(view.active.id(), 2);
assert_eq!(view.active.keys(), 0);
assert_eq!(view.frozen.len(), 1);
assert_eq!(view.frozen[0].id(), 1);
assert!(view.frozen[0].is_frozen());
core.put(&key_of(100), b"new").unwrap();
assert_eq!(
view.frozen[0].keys(),
50,
"the frozen generation takes no write"
);
assert_eq!(core.view().active.keys(), 1);
for i in 0..50 {
assert_eq!(core.get(&key_of(i)).unwrap(), Some(value(i)));
}
let manifest = load(dir.path()).unwrap().unwrap();
assert_eq!(manifest.generations.len(), 2);
assert_eq!(manifest.generations[0].state, GenState::Frozen);
assert_eq!(manifest.generations[0].max_gsn, 50);
assert_eq!(manifest.generations[1].state, GenState::Active);
assert_eq!(manifest.generations[1].min_gsn, 51);
assert_eq!(manifest.gsn_floor, 50);
}
#[test]
fn sealing_an_empty_generation_does_nothing() {
let dir = tempfile::tempdir().unwrap();
let core = open_core(dir.path(), roomy());
let version = load(dir.path()).unwrap().unwrap().manifest_version;
core.seal().unwrap();
assert_eq!(core.view().active.id(), 1);
assert_eq!(load(dir.path()).unwrap().unwrap().manifest_version, version);
}
#[test]
fn gsn_ranges_of_layers_never_overlap() {
let dir = tempfile::tempdir().unwrap();
let core = open_core(dir.path(), roomy());
for round in 0..5u64 {
for i in 0..20 {
core.put(&key_of(round * 100 + i), b"v").unwrap();
}
core.seal().unwrap();
}
let manifest = load(dir.path()).unwrap().unwrap();
manifest.check().unwrap();
assert_eq!(manifest.generations.len(), 6);
for pair in manifest.generations.windows(2) {
assert_eq!(pair[0].max_gsn + 1, pair[1].min_gsn);
}
}
#[test]
fn freeze_times_never_go_back() {
let dir = tempfile::tempdir().unwrap();
let clock = TestClock::new(10_000);
let core = try_open_core(dir.path(), roomy(), crate::seg::fs::real(), &clock).unwrap();
core.put(&key_of(1), b"v").unwrap();
core.seal().unwrap();
clock.set(5_000);
core.put(&key_of(2), b"v").unwrap();
core.seal().unwrap();
let manifest = load(dir.path()).unwrap().unwrap();
assert_eq!(manifest.generations[0].frozen_at_ms, 10_000);
assert_eq!(manifest.generations[1].frozen_at_ms, 10_000);
assert_eq!(core.view().frozen[0].frozen_at_ms(), 10_000);
}
struct LateWriteFs {
inner: Arc<dyn crate::seg::fs::SegFs>,
clock: TestClock,
core: std::sync::Mutex<Option<std::sync::Weak<SegCore<crate::seg::testkit::TestKey>>>>,
}
impl crate::seg::fs::SegFs for LateWriteFs {
fn create(&self, path: &std::path::Path) -> std::io::Result<std::fs::File> {
self.inner.create(path)
}
fn create_new(&self, path: &std::path::Path) -> std::io::Result<std::fs::File> {
self.inner.create_new(path)
}
fn write_all(
&self,
out: &mut dyn std::io::Write,
path: &std::path::Path,
bytes: &[u8],
) -> std::io::Result<()> {
self.inner.write_all(out, path, bytes)
}
fn sync_file(&self, file: &std::fs::File, path: &std::path::Path) -> std::io::Result<()> {
self.inner.sync_file(file, path)
}
fn rename(&self, from: &std::path::Path, to: &std::path::Path) -> std::io::Result<()> {
self.inner.rename(from, to)
}
fn sync_dir(&self, dir: &std::path::Path) -> std::io::Result<()> {
if dir.ends_with("0000000000000002") {
let core = self.core.lock().unwrap().take();
if let Some(core) = core.and_then(|core| core.upgrade()) {
self.clock.set(2_000);
core.put(&key_of(7), b"late").unwrap();
}
}
self.inner.sync_dir(dir)
}
fn create_dir_all(&self, dir: &std::path::Path) -> std::io::Result<()> {
self.inner.create_dir_all(dir)
}
fn remove_file(&self, path: &std::path::Path) -> std::io::Result<()> {
self.inner.remove_file(path)
}
fn remove_dir_all(&self, dir: &std::path::Path) -> std::io::Result<()> {
self.inner.remove_dir_all(dir)
}
}
#[test]
fn a_layer_is_not_frozen_before_a_write_it_holds() {
let dir = tempfile::tempdir().unwrap();
let clock = TestClock::new(1_000);
let fs = Arc::new(LateWriteFs {
inner: crate::seg::fs::real(),
clock: clock.clone(),
core: std::sync::Mutex::new(None),
});
let core = try_open_core(dir.path(), roomy(), fs.clone(), &clock).unwrap();
core.put(&key_of(1), b"v").unwrap();
*fs.core.lock().unwrap() = Some(Arc::downgrade(&core));
core.seal().unwrap();
let view = core.view();
assert_eq!(view.frozen.len(), 1);
assert!(fs.core.lock().unwrap().is_none(), "the late write ran");
assert_eq!(view.frozen[0].frozen_at_ms(), 2_000);
assert_eq!(view.active.opened_at_ms(), 2_000);
let manifest = load(dir.path()).unwrap().unwrap();
assert_eq!(manifest.generations[0].frozen_at_ms, 2_000);
assert_eq!(manifest.generations[1].opened_at_ms, 2_000);
assert_eq!(
core.get_pruned(&key_of(7), Some(2_000)).unwrap(),
Some(b"late".to_vec())
);
}
#[test]
fn an_id_is_reserved_before_anything_is_written_under_it() {
let dir = tempfile::tempdir().unwrap();
let fs = TraceFs::new();
let core = try_open_core(dir.path(), roomy(), fs.clone(), &TestClock::new(1)).unwrap();
core.put(&key_of(1), b"v").unwrap();
fs.clear();
core.seal().unwrap();
let ops = fs.ops();
let publications: Vec<usize> = ops
.iter()
.enumerate()
.filter(|(_, op)| op.kind() == FsOpKind::Rename && op.target().ends_with(MANIFEST_NAME))
.map(|(i, _)| i)
.collect();
assert_eq!(publications.len(), 2, "one reservation, one freeze");
let generation = fs.position(FsOpKind::SyncDir, "0000000000000002").unwrap();
assert!(publications[0] < generation, "the id is reserved first");
assert!(
generation < publications[1],
"the directory is durable before it is named"
);
}
#[test]
fn a_full_generation_is_frozen_by_the_next_write() {
let dir = tempfile::tempdir().unwrap();
let config = SegConfig {
seal_max_keys: 10,
max_frozen_generations: 4,
..SegConfig::test()
};
let core = open_core(dir.path(), config);
for i in 0..10 {
core.put(&key_of(i), &value(i)).unwrap();
}
assert!(core.view().active.is_full());
assert_eq!(
core.view().active.id(),
1,
"the crossing write does not freeze"
);
core.put(&key_of(10), &value(10)).unwrap();
let view = core.view();
assert_eq!(view.active.id(), 2);
assert_eq!(view.active.keys(), 1);
assert_eq!(view.frozen[0].keys(), 10);
for i in 0..11 {
assert_eq!(core.get(&key_of(i)).unwrap(), Some(value(i)));
}
}
#[test]
fn a_write_without_room_fails_and_changes_nothing() {
let dir = tempfile::tempdir().unwrap();
let config = SegConfig {
seal_max_keys: 5,
max_frozen_generations: 1,
seal_wait_timeout: Duration::from_millis(100),
..SegConfig::test()
};
let core = open_core(dir.path(), config);
for i in 0..10 {
core.put(&key_of(i), &value(i)).unwrap();
}
assert_eq!(core.view().frozen.len(), 1);
assert!(core.view().active.is_full());
let len = core.len();
let started = std::time::Instant::now();
let err = core.put(&key_of(10), b"refused").unwrap_err();
assert!(matches!(
err,
DbError::SealBackpressure {
collection: "test_seg"
}
));
assert!(started.elapsed() >= Duration::from_millis(100));
assert_eq!(
core.get(&key_of(10)).unwrap(),
None,
"the write was not applied"
);
assert_eq!(core.len(), len);
assert_eq!(core.view().active.keys(), 5);
assert!(matches!(
core.delete(&key_of(1)),
Err(DbError::SealBackpressure { .. })
));
assert_eq!(core.get(&key_of(1)).unwrap(), Some(value(1)));
assert!(matches!(core.seal(), Err(DbError::SealBackpressure { .. })));
}
#[test]
fn writers_racing_a_freeze_lose_nothing() {
let dir = tempfile::tempdir().unwrap();
let core = open_core(dir.path(), roomy());
const WRITERS: u64 = 4;
const PER_WRITER: u64 = 2_000;
let populated = std::sync::Barrier::new(WRITERS as usize + 1);
std::thread::scope(|scope| {
for w in 0..WRITERS {
let (core, populated) = (&core, &populated);
scope.spawn(move || {
for i in 0..PER_WRITER {
let n = w * 1_000_000 + i;
core.put(&key_of(n), &value(n)).unwrap();
if i == 0 {
populated.wait();
}
}
});
}
populated.wait();
for _ in 0..20 {
core.seal().unwrap();
std::thread::yield_now();
}
});
for w in 0..WRITERS {
for i in 0..PER_WRITER {
let n = w * 1_000_000 + i;
assert_eq!(core.get(&key_of(n)).unwrap(), Some(value(n)), "key {n}");
}
}
let manifest = load(dir.path()).unwrap().unwrap();
manifest.check().unwrap();
let view = core.view();
let written: u64 = view.active.keys() + view.frozen.iter().map(|g| g.keys()).sum::<u64>();
assert_eq!(
written,
WRITERS * PER_WRITER,
"no write landed in two generations"
);
assert!(
!view.frozen.is_empty(),
"at least one populated freeze occurred"
);
for (generation, rec) in view.frozen.iter().rev().zip(&manifest.generations) {
assert_eq!(generation.id(), rec.gen_id);
assert_eq!(generation.next_gsn() - 1, rec.max_gsn);
}
}
#[test]
fn a_freeze_that_was_not_published_is_rolled_back() {
let dir = tempfile::tempdir().unwrap();
let fs = TraceFs::new();
let core = try_open_core(dir.path(), roomy(), fs.clone(), &TestClock::new(1)).unwrap();
core.put(&key_of(1), b"v").unwrap();
fs.fail_on(FsOpKind::Rename, MANIFEST_NAME, 1);
assert!(core.seal().is_err());
let view = core.view();
assert_eq!(view.active.id(), 1);
assert!(!view.active.is_frozen());
assert!(view.frozen.is_empty());
assert!(!dir.path().join("gen/0000000000000002").exists());
core.check_writable().unwrap();
core.put(&key_of(2), b"v").unwrap();
assert_eq!(core.view().active.keys(), 2);
let manifest = load(dir.path()).unwrap().unwrap();
assert_eq!(manifest.generations.len(), 1);
assert_eq!(manifest.next_gen_id, 3, "the reserved id stays burned");
core.seal().unwrap();
assert_eq!(core.view().active.id(), 3);
}
#[test]
fn a_generation_that_cannot_be_made_durable_fails_the_write() {
let dir = tempfile::tempdir().unwrap();
let fs = TraceFs::new();
let config = SegConfig {
seal_max_keys: 3,
max_frozen_generations: 4,
..SegConfig::test()
};
let core = try_open_core(dir.path(), config, fs.clone(), &TestClock::new(1)).unwrap();
for i in 0..3 {
core.put(&key_of(i), &value(i)).unwrap();
}
fs.fail_on(FsOpKind::SyncDir, "0000000000000002", 0);
let err = core.put(&key_of(3), b"refused").unwrap_err();
assert!(matches!(err, DbError::Io(_)), "{err:?}");
assert_eq!(
core.get(&key_of(3)).unwrap(),
None,
"the write was not applied"
);
let view = core.view();
assert_eq!(view.active.id(), 1);
assert!(!view.active.is_frozen());
assert!(view.frozen.is_empty());
assert!(!dir.path().join("gen/0000000000000002").exists());
core.check_writable().unwrap();
let manifest = load(dir.path()).unwrap().unwrap();
assert_eq!(manifest.next_gen_id, 3, "the reserved id stays burned");
assert_eq!(manifest.generations.len(), 1);
assert_eq!(manifest.generations[0].gen_id, 1);
for i in 0..3 {
assert_eq!(core.get(&key_of(i)).unwrap(), Some(value(i)));
}
core.put(&key_of(3), &value(3)).unwrap();
assert_eq!(core.view().active.id(), 3);
assert_eq!(core.get(&key_of(3)).unwrap(), Some(value(3)));
}
#[test]
fn a_fenced_collection_refuses_changes_and_keeps_its_barriers() {
let dir = tempfile::tempdir().unwrap();
build_collection(dir.path());
let core = open_core(dir.path(), roomy());
core.put(&key_of(900), b"before the fence").unwrap();
let layer_keys = [key_of(50), key_of(150), key_of(250)];
let values = layer_keys.map(|key| core.get(&key).unwrap().unwrap());
core.fence("test".into());
let fenced = |result: DbResult<()>| {
assert!(
matches!(result, Err(DbError::CollectionFenced { .. })),
"{result:?}"
);
};
fenced(core.put(&key_of(901), b"v"));
fenced(core.delete(&key_of(900)));
fenced(core.insert(&key_of(902), b"v"));
fenced(core.seal());
fenced(core.seal_oldest().map(drop));
fenced(core.drop_segments_before(u64::MAX).map(drop));
fenced(core.wait_sealed(Duration::from_millis(10)).map(drop));
core.flush().unwrap();
core.durable_flush().unwrap();
assert_eq!(core.dirty_shards(), 0);
assert_eq!(
core.get(&key_of(900)).unwrap(),
Some(b"before the fence".to_vec())
);
assert_eq!(core.get(&key_of(901)).unwrap(), None);
assert_eq!(core.get(&key_of(902)).unwrap(), None);
for (key, expected) in layer_keys.iter().zip(values) {
assert_eq!(core.get(key).unwrap(), Some(expected));
}
assert_eq!(core.view().sealed.len(), 1);
assert_eq!(core.view().frozen.len(), 1);
}
#[test]
fn a_freeze_with_an_unknown_outcome_fences_the_collection() {
let dir = tempfile::tempdir().unwrap();
let fs = TraceFs::new();
let core = try_open_core(dir.path(), roomy(), fs.clone(), &TestClock::new(1)).unwrap();
for i in 0..10 {
core.put(&key_of(i), &value(i)).unwrap();
}
fs.fail_on(FsOpKind::SyncDir, "", 3);
assert!(matches!(core.seal(), Err(DbError::CollectionFenced { .. })));
assert!(matches!(
core.put(&key_of(99), b"v"),
Err(DbError::CollectionFenced { .. })
));
assert!(matches!(core.seal(), Err(DbError::CollectionFenced { .. })));
assert_eq!(core.get(&key_of(3)).unwrap(), Some(value(3)));
assert!(dir.path().join("gen/0000000000000001").exists());
assert!(dir.path().join("gen/0000000000000002").exists());
drop(core);
let core = open_core(dir.path(), roomy());
core.check_writable().unwrap();
for i in 0..10 {
assert_eq!(core.get(&key_of(i)).unwrap(), Some(value(i)));
}
core.put(&key_of(99), b"v").unwrap();
}
#[test]
fn shutdown_blocks_a_freeze_waiting_for_the_manifest() {
let dir = tempfile::tempdir().unwrap();
let fs = TraceFs::new();
let core = try_open_core(dir.path(), roomy(), fs.clone(), &TestClock::new(1)).unwrap();
core.put(&key_of(1), b"v").unwrap();
let manifest = sync::lock(&core.manifest);
fs.clear();
std::thread::scope(|scope| {
let (started, waiting) = std::sync::mpsc::channel();
let core = &core;
let seal = scope.spawn(move || {
started.send(()).unwrap();
core.seal()
});
waiting.recv().unwrap();
std::thread::sleep(Duration::from_millis(100));
core.shut_down.store(true, Ordering::Release);
drop(manifest);
assert!(matches!(
seal.join().unwrap(),
Err(DbError::SealBackpressure { .. })
));
});
assert!(fs.ops().is_empty(), "shutdown prevents even id reservation");
assert_eq!(core.view().active.id(), 1);
assert!(!core.view().active.is_frozen());
assert_eq!(core.get(&key_of(1)).unwrap(), Some(b"v".to_vec()));
}
#[test]
fn freeze_locked_rechecks_shutdown_before_reserving_an_id() {
let dir = tempfile::tempdir().unwrap();
let fs = TraceFs::new();
let core = try_open_core(dir.path(), roomy(), fs.clone(), &TestClock::new(1)).unwrap();
core.put(&key_of(1), b"v").unwrap();
let mut manifest = sync::lock(&core.manifest);
core.shut_down.store(true, Ordering::Release);
fs.clear();
assert!(matches!(
core.freeze_locked(&mut manifest),
Err(DbError::SealBackpressure { .. })
));
assert_eq!(manifest.next_gen_id, 2);
assert!(fs.ops().is_empty());
assert!(!core.view().active.is_frozen());
}
#[test]
fn shutdown_allows_writes_with_room_and_refuses_the_next_write() {
let dir = tempfile::tempdir().unwrap();
let config = SegConfig {
seal_max_keys: 2,
..roomy()
};
let core = open_core(dir.path(), config);
{
let _manifest = sync::lock(&core.manifest);
core.shut_down.store(true, Ordering::Release);
}
core.put(&key_of(1), b"v").unwrap();
core.delete(&key_of(1)).unwrap();
core.put(&key_of(2), b"v").unwrap();
assert!(core.view().active.is_full());
assert!(matches!(
core.put(&key_of(3), b"v"),
Err(DbError::SealBackpressure { .. })
));
assert_eq!(core.get(&key_of(3)).unwrap(), None);
assert_eq!(core.get(&key_of(1)).unwrap(), None);
assert_eq!(core.view().active.id(), 1);
assert!(core.view().frozen.is_empty());
}
#[test]
fn a_byte_threshold_crossing_write_is_applied_before_freezing() {
let dir = tempfile::tempdir().unwrap();
let config = SegConfig {
seal_max_bytes: 1,
..roomy()
};
let core = open_core(dir.path(), config);
core.put(&key_of(1), b"crossing").unwrap();
assert!(core.view().active.is_full());
assert_eq!(core.view().active.id(), 1);
assert_eq!(core.get(&key_of(1)).unwrap(), Some(b"crossing".to_vec()));
core.put(&key_of(2), b"next").unwrap();
assert_eq!(core.view().active.id(), 2);
assert_eq!(core.view().frozen[0].keys(), 1);
assert_eq!(core.get(&key_of(2)).unwrap(), Some(b"next".to_vec()));
}
#[test]
fn a_reservation_failure_creates_no_generation() {
let dir = tempfile::tempdir().unwrap();
let fs = TraceFs::new();
let core = try_open_core(dir.path(), roomy(), fs.clone(), &TestClock::new(1)).unwrap();
core.put(&key_of(1), b"v").unwrap();
fs.fail_on(FsOpKind::Rename, MANIFEST_NAME, 0);
assert!(core.seal().is_err());
assert!(!dir.path().join("gen/0000000000000002").exists());
assert!(!core.view().active.is_frozen());
assert_eq!(load(dir.path()).unwrap().unwrap().next_gen_id, 2);
core.put(&key_of(2), b"still writable").unwrap();
core.seal().unwrap();
assert_eq!(core.view().active.id(), 2);
}
#[test]
fn insert_refuses_a_key_that_is_live_in_any_layer() {
let dir = tempfile::tempdir().unwrap();
build_collection(dir.path());
let core = open_core(dir.path(), roomy());
for i in [250u64, 150, 50] {
assert!(
matches!(core.insert(&key_of(i), b"x"), Err(DbError::KeyExists)),
"key {i}"
);
}
assert_eq!(
core.get(&key_of(50)).unwrap(),
Some(crate::seg::testkit::value_of(50))
);
for i in [205u64, 105, 9] {
core.insert(&key_of(i), b"reborn").unwrap();
assert_eq!(
core.get(&key_of(i)).unwrap(),
Some(b"reborn".to_vec()),
"key {i}"
);
}
core.insert(&key_of(5_000), b"new").unwrap();
assert!(matches!(
core.insert(&key_of(5_000), b"again"),
Err(DbError::KeyExists)
));
assert_eq!(core.get(&key_of(5_000)).unwrap(), Some(b"new".to_vec()));
}
#[test]
fn a_newer_tombstone_wins_over_an_older_value() {
let dir = tempfile::tempdir().unwrap();
build_collection(dir.path());
let core = open_core(dir.path(), roomy());
core.delete(&key_of(50)).unwrap();
core.insert(&key_of(50), b"fresh").unwrap();
assert_eq!(core.get(&key_of(50)).unwrap(), Some(b"fresh".to_vec()));
}
#[test]
fn a_damaged_older_layer_matters_only_when_the_answer_depends_on_it() {
let dir = tempfile::tempdir().unwrap();
build_collection(dir.path());
let core = open_core(dir.path(), roomy());
core.put(&key_of(50), b"live above").unwrap();
core.delete(&key_of(51)).unwrap();
let sdat = dir.path().join("seg").join(sdat_name(1, 1));
std::fs::OpenOptions::new()
.write(true)
.open(&sdat)
.unwrap()
.set_len(64)
.unwrap();
assert!(matches!(
core.insert(&key_of(50), b"x"),
Err(DbError::KeyExists)
));
core.insert(&key_of(51), b"reborn").unwrap();
assert!(matches!(
core.insert(&key_of(52), b"x"),
Err(DbError::SegmentCorrupt { segment_id: 1, .. })
));
assert_eq!(
core.view().active.probe(
crate::seg::hash::key_hash(key_of(52).as_slice(), core.seed),
&key_of(52)
),
crate::seg::generation::GenProbe::Absent,
"a failed insert writes nothing"
);
}
#[test]
fn one_of_many_concurrent_inserts_wins() {
let dir = tempfile::tempdir().unwrap();
let core = open_core(dir.path(), roomy());
let wins = std::sync::atomic::AtomicUsize::new(0);
std::thread::scope(|scope| {
for t in 0..8u64 {
let (core, wins) = (&core, &wins);
scope.spawn(move || {
for i in 0..200u64 {
match core.insert(&key_of(i), &value(t)) {
Ok(()) => {
wins.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
}
Err(DbError::KeyExists) => {}
Err(other) => panic!("{other:?}"),
}
}
});
}
});
assert_eq!(wins.load(std::sync::atomic::Ordering::Relaxed), 200);
assert_eq!(core.len(), 200);
}
#[test]
fn inserts_racing_a_freeze_land_exactly_once() {
let dir = tempfile::tempdir().unwrap();
let core = open_core(dir.path(), roomy());
let populated = std::sync::Barrier::new(5);
std::thread::scope(|scope| {
for t in 0..4u64 {
let (core, populated) = (&core, &populated);
scope.spawn(move || {
for i in 0..1_000u64 {
core.insert(&key_of(t * 1_000_000 + i), b"v").unwrap();
if i == 0 {
populated.wait();
}
}
});
}
populated.wait();
for _ in 0..20 {
core.seal().unwrap();
std::thread::yield_now();
}
});
let view = core.view();
assert!(!view.frozen.is_empty(), "a populated freeze occurred");
let written: u64 = view.active.keys() + view.frozen.iter().map(|g| g.keys()).sum::<u64>();
assert_eq!(written, 4_000);
for t in 0..4u64 {
assert!(matches!(
core.insert(&key_of(t * 1_000_000 + 7), b"x"),
Err(DbError::KeyExists)
));
}
}
#[test]
fn an_insert_without_room_changes_nothing() {
let dir = tempfile::tempdir().unwrap();
let config = SegConfig {
seal_max_keys: 5,
max_frozen_generations: 1,
seal_wait_timeout: Duration::from_millis(50),
..SegConfig::test()
};
let core = open_core(dir.path(), config);
for i in 0..10 {
core.insert(&key_of(i), &value(i)).unwrap();
}
assert!(matches!(
core.insert(&key_of(10), b"refused"),
Err(DbError::SealBackpressure { .. })
));
assert_eq!(core.get(&key_of(10)).unwrap(), None);
assert!(matches!(
core.insert(&key_of(3), b"x"),
Err(DbError::KeyExists)
));
}
#[test]
fn shared_key_delete_insert_and_populated_freeze_have_linearized_outcomes() {
let dir = tempfile::tempdir().unwrap();
let core = open_core(dir.path(), roomy());
let key = key_of(7);
for round in 0..24 {
core.put(&key, b"before").unwrap();
let before = core.view().active.id();
let start = std::sync::Barrier::new(3);
let inserted = std::thread::scope(|scope| {
let deleted = scope.spawn(|| {
start.wait();
core.delete(&key).unwrap();
});
let inserted = scope.spawn(|| {
start.wait();
core.insert(&key, b"after")
});
let frozen = scope.spawn(|| {
start.wait();
core.seal().unwrap();
});
deleted.join().unwrap();
frozen.join().unwrap();
inserted.join().unwrap()
});
let view = core.view();
assert_ne!(view.active.id(), before, "round {round}");
assert!(view.frozen.iter().any(|g| g.id() == before && g.keys() > 0));
match inserted {
Ok(()) => assert_eq!(core.get(&key).unwrap(), Some(b"after".to_vec())),
Err(DbError::KeyExists) => assert_eq!(core.get(&key).unwrap(), None),
Err(other) => panic!("round {round}: {other:?}"),
}
}
}
}