use std::hash::Hash;
use std::ops::Bound;
use std::path::{Path, PathBuf};
use std::sync::Arc;
use std::sync::atomic::{AtomicBool, AtomicU64, Ordering};
use super::config::{Limits, SegConfig};
use super::fs::SegFs;
use super::hash::{cmp_hk, key_hash, shard_for_hash};
use super::manifest::{GenRecord, GenState};
use super::sidecar::OrderKind;
use crate::disk_loc::DiskLoc;
use crate::engine::Engine;
use crate::entry::{EntryHeader, entry_size};
use crate::error::{DbError, DbResult};
use crate::key::Key;
use crate::map_index::{Dir, OrdKey, ShardIndex, key_index_batch};
use crate::meta::{Backend, DbMeta};
use crate::sync::{self, Mutex, MutexGuard};
mod locks;
pub(crate) use locks::GenerationLocks;
pub(crate) struct CollectionFence {
pub name: &'static str,
pub reason: Mutex<Option<String>>,
pub fenced: AtomicBool,
}
impl CollectionFence {
pub(crate) fn new(name: &'static str) -> Self {
Self {
name,
reason: Mutex::new(None),
fenced: AtomicBool::new(false),
}
}
pub(crate) fn check(&self) -> DbResult<()> {
if !self.fenced.load(Ordering::Acquire) {
return Ok(());
}
Err(DbError::CollectionFenced {
collection: self.name,
reason: sync::lock(&self.reason).clone().unwrap_or_default(),
})
}
}
pub(crate) const GEN_DIR: &str = "gen";
pub(crate) fn gen_dir_name(gen_id: u64) -> String {
format!("{gen_id:016x}")
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct GenLoc {
pub loc: DiskLoc,
pub tombstone: bool,
}
pub(crate) struct Generation<K: Key + Hash + Eq + Send + Sync> {
id: u64,
dir: PathBuf,
gen_root: PathBuf,
shard_count: usize,
order: OrderKind,
opened_at_ms: u64,
frozen_at_ms: AtomicU64,
min_gsn: AtomicU64,
max_gsn: AtomicU64,
engine: Option<Engine>,
indexes: Vec<Mutex<ShardIndex<K, GenLoc>>>,
#[cfg(test)]
index_lock_attempt: Mutex<Option<std::sync::mpsc::Sender<()>>>,
collection_fence: Option<Arc<CollectionFence>>,
frozen: AtomicBool,
full: AtomicBool,
keys: AtomicU64,
live: AtomicU64,
bytes: AtomicU64,
doomed: AtomicBool,
fs: Arc<dyn SegFs>,
}
fn missing(rec: &GenRecord, path: &Path, reason: impl Into<String>) -> DbError {
DbError::GenerationMissing {
gen_id: rec.gen_id,
path: path.to_path_buf(),
reason: reason.into(),
}
}
impl<K: Key + Hash + Eq + Send + Sync> Generation<K> {
fn assemble(
fs: Arc<dyn SegFs>,
gen_root: &Path,
dir: PathBuf,
gen_id: u64,
opened_at_ms: u64,
engine: Engine,
order: OrderKind,
) -> Self {
let shard_count = engine.shards().len();
Self {
id: gen_id,
dir,
gen_root: gen_root.to_path_buf(),
shard_count,
order,
opened_at_ms,
frozen_at_ms: AtomicU64::new(0),
min_gsn: AtomicU64::new(1),
max_gsn: AtomicU64::new(0),
engine: Some(engine),
indexes: (0..shard_count)
.map(|_| Mutex::new(ShardIndex::new(order == OrderKind::ByKey)))
.collect(),
collection_fence: None,
#[cfg(test)]
index_lock_attempt: Mutex::new(None),
frozen: AtomicBool::new(false),
full: AtomicBool::new(false),
keys: AtomicU64::new(0),
live: AtomicU64::new(0),
bytes: AtomicU64::new(0),
doomed: AtomicBool::new(false),
fs,
}
}
pub(crate) fn create(
fs: Arc<dyn SegFs>,
gen_root: &Path,
gen_id: u64,
config: &SegConfig,
opened_at_ms: u64,
order: OrderKind,
) -> DbResult<Self> {
let dir = gen_root.join(gen_dir_name(gen_id));
if dir.exists() {
return Err(DbError::Internal(
"a directory already exists under a freshly reserved generation id",
));
}
let built = (|| -> DbResult<Engine> {
let engine = Engine::open(&dir, config.journal(config.shard_count))?;
if engine.hints() {
for shard in engine.shards().iter() {
shard.set_key_len(size_of::<K>());
}
}
fs.sync_dir(&dir)?;
fs.sync_dir(gen_root)?;
Ok(engine)
})();
match built {
Ok(engine) => Ok(Self::assemble(
fs,
gen_root,
dir,
gen_id,
opened_at_ms,
engine,
order,
)),
Err(e) => {
if let Err(cleanup) = fs.remove_dir_all(&dir) {
tracing::warn!(error = %cleanup, path = %dir.display(), "could not remove a half-created generation");
}
Err(e)
}
}
}
pub(crate) fn check_existing(gen_root: &Path, rec: &GenRecord) -> DbResult<()> {
let dir = gen_root.join(gen_dir_name(rec.gen_id));
if !dir.is_dir() {
return Err(missing(rec, &dir, "the generation directory is missing"));
}
let meta_path = dir.join("db.meta");
let bytes = match std::fs::read(&meta_path) {
Ok(bytes) => bytes,
Err(e) if e.kind() == std::io::ErrorKind::NotFound => {
return Err(missing(rec, &meta_path, "db.meta is missing"));
}
Err(e) => return Err(e.into()),
};
let meta = DbMeta::decode(&bytes)
.map_err(|e| missing(rec, &meta_path, format!("db.meta is unreadable: {e}")))?;
if meta.backend != Backend::Bitcask {
return Err(missing(rec, &meta_path, "db.meta names another backend"));
}
if meta.flags != 0 {
return Err(missing(
rec,
&meta_path,
"the generation journal must be plaintext",
));
}
if meta.shard_count != rec.shard_count {
return Err(missing(
rec,
&meta_path,
format!(
"shard count {} differs from the {} the manifest records",
meta.shard_count, rec.shard_count
),
));
}
if meta.shard_prefix_bits != 0 {
return Err(missing(
rec,
&meta_path,
"the generation routes by key prefix",
));
}
for i in 0..rec.shard_count {
let name = format!("shard_{i:03}");
let shard_dir = dir.join(&name);
if !shard_dir.is_dir() {
return Err(missing(rec, &shard_dir, format!("{name} is missing")));
}
let mut has_journal = false;
for entry in std::fs::read_dir(&shard_dir)? {
let entry = entry?;
let filename = entry.file_name();
let Some(filename) = filename.to_str() else {
continue;
};
let Some(file_id) = filename
.strip_suffix(".data")
.and_then(|stem| stem.parse::<u32>().ok())
else {
continue;
};
if filename != format!("{file_id:06}.data") || !entry.file_type()?.is_file() {
return Err(missing(
rec,
&entry.path(),
"not a journal file, but named like one",
));
}
has_journal = true;
}
if !has_journal {
return Err(missing(
rec,
&shard_dir,
format!("{name} holds no journal file"),
));
}
}
Ok(())
}
pub(crate) fn open_existing(
fs: Arc<dyn SegFs>,
gen_root: &Path,
rec: &GenRecord,
config: &SegConfig,
order: OrderKind,
) -> DbResult<Self> {
Self::check_existing(gen_root, rec)?;
let dir = gen_root.join(gen_dir_name(rec.gen_id));
let engine = Engine::open(&dir, config.journal(rec.shard_count as usize))?;
let generation = Self::assemble(
fs,
gen_root,
dir,
rec.gen_id,
rec.opened_at_ms,
engine,
order,
);
generation.recover()?;
generation.full.store(
generation.keys() > 0
&& (generation.keys() >= config.seal_max_keys
|| generation.bytes() >= config.seal_max_bytes),
Ordering::Release,
);
generation.min_gsn.store(rec.min_gsn, Ordering::Release);
let recovered_max = generation.next_gsn().saturating_sub(1);
if rec.state == GenState::Frozen && generation.keys() > 0 && recovered_max > rec.max_gsn {
return Err(missing(
rec,
&generation.dir,
format!(
"the journal holds GSN {recovered_max}, past the {} the freeze recorded",
rec.max_gsn
),
));
}
if rec.state == GenState::Frozen {
generation.max_gsn.store(rec.max_gsn, Ordering::Release);
generation
.frozen_at_ms
.store(rec.frozen_at_ms, Ordering::Release);
generation.frozen.store(true, Ordering::Release);
generation.full.store(true, Ordering::Release);
}
Ok(generation)
}
fn recover(&self) -> DbResult<()> {
let engine = self.engine();
let shard_dirs = engine.shard_dirs();
let shard_dir_refs = Engine::shard_dir_refs(&shard_dirs);
let shard_ids = engine.shard_ids();
let hints = engine.hints();
let outcome = crate::recovery::recover_seg_generation::<K>(
&shard_dir_refs,
&shard_ids,
&self.indexes,
hints,
self.order,
)?;
for tail in &outcome.active_tails {
engine.shards()[tail.shard_idx].apply_recovery_tail(tail)?;
}
for (shard_idx, dead) in outcome.shard_dead_bytes {
engine.shards()[shard_idx].install_dead_bytes(dead);
}
for (shard_idx, file_seqs) in outcome.shard_file_seqs {
engine.shards()[shard_idx].install_recovery_file_seqs(file_seqs);
}
for (shard_idx, max_gsn) in &outcome.shard_max_gsns {
engine.shards()[*shard_idx].set_durable_recovered_gsn(*max_gsn);
}
engine
.gsn()
.fetch_max(outcome.max_gsn + 1, Ordering::Relaxed);
if hints {
for shard in engine.shards().iter() {
shard.set_key_len(size_of::<K>());
}
}
let mut keys = 0u64;
let mut live = 0u64;
for index in &self.indexes {
let index = sync::lock(index);
keys += index.len() as u64;
live += index.values().filter(|g| !g.tombstone).count() as u64;
}
let bytes: u64 = engine
.shards()
.iter()
.flat_map(|shard| shard.file_sizes())
.map(|(_, size)| size)
.sum();
self.keys.store(keys, Ordering::Release);
self.live.store(live, Ordering::Release);
self.bytes.store(bytes, Ordering::Release);
tracing::info!(gen_id = self.id, keys, live, "generation recovered");
Ok(())
}
pub(crate) fn bind_fence(&mut self, fence: Arc<CollectionFence>) {
self.collection_fence = Some(fence);
}
fn check_collection_fence(&self) -> DbResult<()> {
self.collection_fence.as_ref().map_or(Ok(()), |f| f.check())
}
pub(crate) fn engine(&self) -> &Engine {
self.engine
.as_ref()
.expect("the engine lives until the generation is dropped")
}
pub(crate) fn id(&self) -> u64 {
self.id
}
pub(crate) fn shard_count(&self) -> usize {
self.shard_count
}
#[cfg(test)]
pub(crate) fn dir(&self) -> &Path {
&self.dir
}
pub(crate) fn opened_at_ms(&self) -> u64 {
self.opened_at_ms
}
pub(crate) fn set_opened_at_ms(&mut self, opened_at_ms: u64) {
self.opened_at_ms = opened_at_ms;
}
pub(crate) fn keys(&self) -> u64 {
self.keys.load(Ordering::Acquire)
}
pub(crate) fn live(&self) -> u64 {
self.live.load(Ordering::Acquire)
}
pub(crate) fn bytes(&self) -> u64 {
self.bytes.load(Ordering::Acquire)
}
pub(crate) fn next_gsn(&self) -> u64 {
self.engine().gsn().load(Ordering::Acquire)
}
pub(crate) fn seed_gsn(&self, next: u64) {
self.engine().gsn().fetch_max(next, Ordering::AcqRel);
self.min_gsn.store(next, Ordering::Release);
}
pub(crate) fn min_gsn(&self) -> u64 {
self.min_gsn.load(Ordering::Acquire)
}
pub(crate) fn doom(&self) {
self.doomed.store(true, Ordering::Release);
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum Append {
Done { crossed: bool },
Frozen,
Full,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum InsertStep {
Done {
crossed: bool,
},
Exists,
Frozen,
Full,
NeedLower,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) enum GenLookup {
Live(Vec<u8>),
Tombstone,
Absent,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum GenProbe {
Live,
Tombstone,
Absent,
}
const ENTRY_HEADER_LEN: u32 = size_of::<EntryHeader>() as u32;
impl<K: Key + Hash + Eq + Send + Sync> Generation<K> {
fn shard_of(&self, h: u64) -> usize {
shard_for_hash(h, self.shard_count)
}
pub(crate) fn is_full(&self) -> bool {
self.full.load(Ordering::Acquire)
}
pub(crate) fn is_frozen(&self) -> bool {
self.frozen.load(Ordering::Acquire)
}
pub(crate) fn frozen_at_ms(&self) -> u64 {
self.frozen_at_ms.load(Ordering::Acquire)
}
pub(crate) fn max_gsn(&self) -> u64 {
self.max_gsn.load(Ordering::Acquire)
}
pub(crate) fn raise_gsn(&self, next: u64) {
self.engine().gsn().fetch_max(next, Ordering::AcqRel);
}
pub(crate) fn lock_all(&self) -> Vec<MutexGuard<'_, ShardIndex<K, GenLoc>>> {
#[cfg(test)]
self.notify_index_lock_attempt();
self.indexes.iter().map(sync::lock).collect()
}
#[cfg(test)]
pub(crate) fn observe_index_lock_attempt(&self) -> std::sync::mpsc::Receiver<()> {
let (sender, receiver) = std::sync::mpsc::channel();
*sync::lock(&self.index_lock_attempt) = Some(sender);
receiver
}
#[cfg(test)]
fn notify_index_lock_attempt(&self) {
if let Some(sender) = sync::lock(&self.index_lock_attempt).take() {
let _ = sender.send(());
}
}
pub(crate) fn mark_frozen(&self, frozen_at_ms: u64, max_gsn: u64) {
self.frozen_at_ms.store(frozen_at_ms, Ordering::Release);
self.max_gsn.store(max_gsn, Ordering::Release);
self.frozen.store(true, Ordering::Release);
}
pub(crate) fn unmark_frozen(&self) {
self.frozen.store(false, Ordering::Release);
self.frozen_at_ms.store(0, Ordering::Release);
self.max_gsn.store(0, Ordering::Release);
}
fn append_locked(
&self,
shard: usize,
index: &mut ShardIndex<K, GenLoc>,
key: &K,
value: Option<&[u8]>,
limits: Limits,
) -> DbResult<(bool, bool)> {
let tombstone = value.is_none();
let bytes = value.unwrap_or(&[]);
let (loc, should_sync) = {
let mut inner = self.engine().shards()[shard].lock();
let (loc, _gsn) = inner.append_entry(shard as u8, key.as_bytes(), bytes, tombstone)?;
(loc, inner.should_sync())
};
match index.upsert(*key, GenLoc { loc, tombstone }) {
None => {
self.keys.fetch_add(1, Ordering::AcqRel);
if !tombstone {
self.live.fetch_add(1, Ordering::AcqRel);
}
}
Some(previous) => match (previous.tombstone, tombstone) {
(true, false) => {
self.live.fetch_add(1, Ordering::AcqRel);
}
(false, true) => {
self.live.fetch_sub(1, Ordering::AcqRel);
}
_ => {}
},
}
let size = entry_size(size_of::<K>(), bytes.len() as u32);
let total = self.bytes.fetch_add(size, Ordering::AcqRel) + size;
let crossed = self.keys() >= limits.max_keys || total >= limits.max_bytes;
if crossed {
self.full.store(true, Ordering::Release);
}
Ok((crossed, should_sync))
}
fn sync_if_asked(&self, shard: usize, should_sync: bool) -> DbResult<()> {
if should_sync {
self.engine().shards()[shard].flush()?;
}
Ok(())
}
pub(crate) fn append(
&self,
h: u64,
key: &K,
value: Option<&[u8]>,
limits: Limits,
) -> DbResult<Append> {
let shard = self.shard_of(h);
let (crossed, should_sync) = {
#[cfg(test)]
self.notify_index_lock_attempt();
let mut index = sync::lock(&self.indexes[shard]);
self.check_collection_fence()?;
if self.is_frozen() {
return Ok(Append::Frozen);
}
if self.is_full() {
return Ok(Append::Full);
}
self.append_locked(shard, &mut index, key, value, limits)?
};
self.sync_if_asked(shard, should_sync)?;
Ok(Append::Done { crossed })
}
pub(crate) fn insert(
&self,
h: u64,
key: &K,
value: &[u8],
lower: Option<bool>,
limits: Limits,
) -> DbResult<InsertStep> {
let shard = self.shard_of(h);
let (crossed, should_sync) = {
#[cfg(test)]
self.notify_index_lock_attempt();
let mut index = sync::lock(&self.indexes[shard]);
self.check_collection_fence()?;
if self.is_frozen() {
return Ok(InsertStep::Frozen);
}
match index.get(key).copied() {
Some(found) if !found.tombstone => return Ok(InsertStep::Exists),
Some(_) => {}
None => match lower {
None => return Ok(InsertStep::NeedLower),
Some(true) => return Ok(InsertStep::Exists),
Some(false) => {}
},
}
if self.is_full() {
return Ok(InsertStep::Full);
}
self.append_locked(shard, &mut index, key, Some(value), limits)?
};
self.sync_if_asked(shard, should_sync)?;
Ok(InsertStep::Done { crossed })
}
pub(crate) fn probe(&self, h: u64, key: &K) -> GenProbe {
let index = sync::lock(&self.indexes[self.shard_of(h)]);
match index.get(key) {
None => GenProbe::Absent,
Some(found) if found.tombstone => GenProbe::Tombstone,
Some(_) => GenProbe::Live,
}
}
pub(crate) fn lookup(&self, h: u64, key: &K) -> DbResult<GenLookup> {
let found = {
let index = sync::lock(&self.indexes[self.shard_of(h)]);
index.get(key).copied()
};
Ok(match found {
None => GenLookup::Absent,
Some(found) if found.tombstone => GenLookup::Tombstone,
Some(found) => GenLookup::Live(self.read_value(h, &found.loc)?),
})
}
fn read_bytes(&self, shard: usize, loc: &DiskLoc) -> DbResult<Vec<u8>> {
if loc.len == 0 {
return Ok(Vec::new());
}
let shard = &self.engine().shards()[shard];
{
let inner = shard.lock();
if inner.active.file_id == loc.file_id {
if let Some(bytes) = inner
.write_buf
.read(u64::from(loc.offset), loc.len as usize)
{
return Ok(bytes.to_vec());
}
if inner.straddles_write_buf(loc) {
return inner.read_straddling_value_locked(loc);
}
}
}
shard.read_value(loc.file_id, loc.offset, loc.len as usize)
}
pub(crate) fn read_value(&self, h: u64, loc: &DiskLoc) -> DbResult<Vec<u8>> {
self.read_bytes(self.shard_of(h), loc)
}
pub(crate) fn read_entry(&self, h: u64, loc: &DiskLoc) -> DbResult<Vec<u8>> {
let key_len = size_of::<K>();
let start = loc.offset - ENTRY_HEADER_LEN - key_len as u32;
let len = entry_size(key_len, loc.len) as u32;
self.read_bytes(self.shard_of(h), &DiskLoc::new(loc.file_id, start, len))
}
pub(crate) fn ordered_batch(
&self,
shard: usize,
lo: Bound<&K>,
hi: Bound<&K>,
dir: Dir,
limit: usize,
) -> Vec<(K, GenLoc)> {
let index = sync::lock(&self.indexes[shard]);
let keys = index
.key_index()
.expect("ordered batches require a ByKey generation");
key_index_batch(
keys,
None,
dir,
limit,
lo.map(|k| OrdKey(*k)),
hi.map(|k| OrdKey(*k)),
)
.into_iter()
.map(|k| (k, *index.get(&k).expect("companion key has a location")))
.collect()
}
pub(crate) fn snapshot_range(&self, lo: u64, hi: u64, seed: u64) -> Vec<(u64, K, GenLoc)> {
let mut out = Vec::new();
for shard in self.shard_of(lo)..=self.shard_of(hi) {
let index = sync::lock(&self.indexes[shard]);
out.extend(index.iter().filter_map(|(key, loc)| {
let h = key_hash(key.as_bytes(), seed);
(lo..=hi).contains(&h).then_some((h, *key, *loc))
}));
}
out.sort_unstable_by(|a, b| cmp_hk(a.0, a.1.as_bytes(), b.0, b.1.as_bytes()));
out
}
pub(crate) fn flush_buffers(&self) -> DbResult<()> {
self.engine().flush_buffers()
}
pub(crate) fn durable_flush(&self) -> DbResult<()> {
self.engine().flush()
}
pub(crate) fn dirty_shards(&self) -> usize {
self.engine().dirty_shards()
}
pub(crate) fn write_hints(&self) -> DbResult<()> {
if !self.engine().hints() {
return Ok(());
}
let mut first = None;
for shard in self.engine().shards().iter() {
if let Err(e) = shard.write_active_hint(size_of::<K>())
&& first.is_none()
{
first = Some(e);
}
}
first.map_or(Ok(()), Err)
}
pub(crate) fn close(&self) -> DbResult<()> {
self.engine().close()
}
}
impl<K: Key + Hash + Eq + Send + Sync> Drop for Generation<K> {
fn drop(&mut self) {
let doomed = self.doomed.load(Ordering::Acquire);
if doomed && let Some(engine) = &self.engine {
for shard in engine.shards().iter() {
shard.clear_key_len();
}
}
self.engine = None;
if !doomed {
return;
}
if let Err(e) = self.fs.remove_dir_all(&self.dir) {
tracing::warn!(error = %e, path = %self.dir.display(), "could not remove a retired generation");
}
if let Err(e) = self.fs.sync_dir(&self.gen_root) {
tracing::warn!(error = %e, "could not sync the generation root after a removal");
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::error::DbError;
use crate::seg::config::SegConfig;
use crate::seg::fs::{FsOpKind, TraceFs, real};
use crate::seg::manifest::{GenRecord, GenState};
use crate::seg::testkit::TestKey;
fn gen_root(dir: &tempfile::TempDir) -> std::path::PathBuf {
let root = dir.path().join(GEN_DIR);
std::fs::create_dir_all(&root).unwrap();
root
}
fn record(gen_id: u64, shard_count: u8) -> GenRecord {
GenRecord {
gen_id,
state: GenState::Active,
shard_count,
opened_at_ms: 100,
frozen_at_ms: 0,
min_gsn: 1,
max_gsn: 0,
}
}
fn create(root: &std::path::Path, gen_id: u64) -> Generation<TestKey> {
Generation::create(
real(),
root,
gen_id,
&SegConfig::test(),
100,
OrderKind::ByHash,
)
.unwrap()
}
#[test]
fn held_reads_append_and_accounting_bypass_replay_admission() {
let dir = tempfile::tempdir().unwrap();
let g = Arc::new(create(&gen_root(&dir), 1));
let key = [3u8; 32];
let limits = Limits {
max_keys: 1,
max_bytes: 1,
};
let mut held = g.lock_owned(&[1, 0, 1]).unwrap();
assert!(Arc::ptr_eq(held.generation(), &g));
assert_eq!(held.probe(0, &key).unwrap(), GenProbe::Absent);
held.append(0, &key, Some(b"old"), limits).unwrap();
assert_eq!(
held.lookup(0, &key).unwrap(),
GenLookup::Live(b"old".to_vec())
);
g.mark_frozen(10, 1);
let bytes = g.bytes();
held.append(0, &key, None, limits).unwrap();
assert_eq!(held.lookup(0, &key).unwrap(), GenLookup::Tombstone);
assert_eq!(g.keys(), 1);
assert_eq!(g.live(), 0);
assert!(g.bytes() > bytes);
held.append(0, &key, Some(b"new"), limits).unwrap();
assert_eq!(g.live(), 1);
assert_eq!(g.next_gsn(), 4);
drop(held);
assert_eq!(g.lookup(0, &key).unwrap(), GenLookup::Live(b"new".to_vec()));
}
#[test]
fn held_append_bypasses_collection_fence_but_keeps_physical_fence() {
let dir = tempfile::tempdir().unwrap();
let mut g = create(&gen_root(&dir), 1);
let fence = Arc::new(CollectionFence::new("held replay"));
g.bind_fence(fence.clone());
let g = Arc::new(g);
let mut held = g.lock_owned(&[0]).unwrap();
*sync::lock(&fence.reason) = Some("logged debt".into());
fence.fenced.store(true, Ordering::Release);
held.append(0, &[0; 32], Some(b"logged"), SegConfig::test().limits())
.unwrap();
assert_eq!(g.keys(), 1);
g.engine().shards()[0].lock().fence(2);
assert!(matches!(
held.append(0, &[1; 32], Some(b"blocked"), SegConfig::test().limits()),
Err(DbError::ShardFenced { .. })
));
assert_eq!(g.keys(), 1);
}
#[test]
fn held_guards_pin_owner_and_release_on_panic() {
let dir = tempfile::tempdir().unwrap();
let g = Arc::new(create(&gen_root(&dir), 1));
let weak = Arc::downgrade(&g);
let held = g.lock_owned(&[1, 0, 1]).unwrap();
drop(g);
assert!(weak.upgrade().is_some());
assert!(
std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
let _held = held;
panic!("unwind held guards");
}))
.is_err()
);
assert!(weak.upgrade().is_none());
let g = Arc::new(create(&gen_root(&dir), 2));
assert!(g.lock_owned(&[0, 2]).is_err());
let held = g.lock_owned(&[0]).unwrap();
assert!(held.lookup(u64::MAX, &[0; 32]).is_err());
drop(held);
assert!(
std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
let _held = g.lock_owned(&[0, 1]).unwrap();
panic!("poison adapter test");
}))
.is_err()
);
drop(g.lock_owned(&[0, 1]).unwrap());
}
#[test]
fn reopening_preserves_tombstones_and_recovers_counts_and_gsn() {
use crate::seg::testkit::key_of;
for hints in [false, true] {
let dir = tempfile::tempdir().unwrap();
let root = gen_root(&dir);
let config = SegConfig {
hints,
..SegConfig::test()
};
let g: Generation<TestKey> =
Generation::create(real(), &root, 1, &config, 100, OrderKind::ByHash).unwrap();
g.seed_gsn(50);
let shard = &g.engine().shards()[0];
let live_key = key_of(1);
let deleted_key = key_of(2);
{
let mut inner = shard.lock();
inner
.append_entry(shard.id, &live_key, b"live", false)
.unwrap();
inner
.append_entry(shard.id, &deleted_key, b"old", false)
.unwrap();
inner
.append_entry(shard.id, &deleted_key, &[], true)
.unwrap();
}
g.engine().flush().unwrap();
if hints {
shard.write_active_hint(size_of::<TestKey>()).unwrap();
}
drop(g);
let mut rec = record(1, 2);
rec.min_gsn = 50;
let g: Generation<TestKey> =
Generation::open_existing(real(), &root, &rec, &config, OrderKind::ByHash).unwrap();
assert_eq!(g.keys(), 2, "hints={hints}");
assert_eq!(g.live(), 1, "hints={hints}");
assert!(g.bytes() > 0);
assert_eq!(g.next_gsn(), 53);
assert_eq!(g.min_gsn(), 50);
assert_eq!(g.opened_at_ms(), 100);
let index = sync::lock(&g.indexes[0]);
assert!(!index.get(&live_key).unwrap().tombstone);
assert!(index.get(&deleted_key).unwrap().tombstone);
}
}
#[test]
fn a_generation_lives_in_a_directory_named_by_its_id() {
let dir = tempfile::tempdir().unwrap();
let root = gen_root(&dir);
let g = create(&root, 0x2a);
assert_eq!(g.id(), 0x2a);
assert_eq!(g.shard_count(), 2);
assert_eq!(g.dir(), root.join("000000000000002a"));
assert!(g.dir().join("db.meta").is_file());
assert!(g.dir().join("shard_000").is_dir());
assert!(g.dir().join("shard_001").is_dir());
assert_eq!(g.keys(), 0);
assert_eq!(g.next_gsn(), 1);
}
#[test]
fn two_generations_are_open_side_by_side() {
let dir = tempfile::tempdir().unwrap();
let root = gen_root(&dir);
let a = create(&root, 1);
let b = create(&root, 2);
assert_ne!(a.dir(), b.dir());
b.seed_gsn(500);
assert_eq!(a.next_gsn(), 1, "generations do not share a GSN counter");
assert_eq!(b.next_gsn(), 500);
}
#[test]
fn creating_over_an_existing_directory_is_refused() {
let dir = tempfile::tempdir().unwrap();
let root = gen_root(&dir);
let g = create(&root, 1);
drop(g);
assert!(
Generation::<TestKey>::create(
real(),
&root,
1,
&SegConfig::test(),
100,
OrderKind::ByHash
)
.is_err()
);
}
#[test]
fn directory_entries_are_durable_before_create_returns() {
let dir = tempfile::tempdir().unwrap();
let root = gen_root(&dir);
let fs = TraceFs::new();
let g: Generation<TestKey> = Generation::create(
fs.clone(),
&root,
1,
&SegConfig::test(),
100,
OrderKind::ByHash,
)
.unwrap();
let own = fs
.position(FsOpKind::SyncDir, "0000000000000001")
.expect("the generation directory is synced");
let parent = fs
.ops()
.iter()
.position(|op| op.kind() == FsOpKind::SyncDir && op.target() == root)
.expect("the parent directory is synced");
assert!(own < parent);
drop(g);
}
#[test]
fn a_failed_create_leaves_no_directory() {
let dir = tempfile::tempdir().unwrap();
let root = gen_root(&dir);
let fs = TraceFs::new();
fs.fail_on(FsOpKind::SyncDir, "", 0);
assert!(
Generation::<TestKey>::create(fs, &root, 1, &SegConfig::test(), 100, OrderKind::ByHash)
.is_err()
);
assert!(!root.join("0000000000000001").exists());
}
#[test]
fn an_existing_generation_is_opened_with_its_recorded_shard_count() {
let dir = tempfile::tempdir().unwrap();
let root = gen_root(&dir);
drop(create(&root, 1));
let config = SegConfig {
shard_count: 8,
..SegConfig::test()
};
let g: Generation<TestKey> =
Generation::open_existing(real(), &root, &record(1, 2), &config, OrderKind::ByHash)
.unwrap();
assert_eq!(g.shard_count(), 2);
}
fn missing_reason(result: DbResult<()>) -> String {
match result.unwrap_err() {
DbError::GenerationMissing {
gen_id: 1, reason, ..
} => reason,
other => panic!("{other:?}"),
}
}
#[test]
fn a_damaged_generation_is_reported_and_nothing_is_created() {
let dir = tempfile::tempdir().unwrap();
let root = gen_root(&dir);
let check =
|root: &std::path::Path| Generation::<TestKey>::check_existing(root, &record(1, 2));
assert!(missing_reason(check(&root)).contains("directory"));
assert!(
!root.join("0000000000000001").exists(),
"the check created it"
);
drop(create(&root, 1));
let g = root.join("0000000000000001");
check(&root).unwrap();
std::fs::remove_file(g.join("db.meta")).unwrap();
assert!(missing_reason(check(&root)).contains("db.meta"));
std::fs::remove_dir_all(&g).unwrap();
drop(create(&root, 1));
std::fs::remove_dir_all(g.join("shard_001")).unwrap();
assert!(missing_reason(check(&root)).contains("shard_001"));
assert!(!g.join("shard_001").exists(), "the check created it");
std::fs::remove_dir_all(&g).unwrap();
drop(create(&root, 1));
for entry in std::fs::read_dir(g.join("shard_000")).unwrap() {
let path = entry.unwrap().path();
if path.extension().is_some_and(|e| e == "data") {
std::fs::remove_file(path).unwrap();
}
}
assert!(missing_reason(check(&root)).contains("no journal file"));
}
#[test]
fn misleading_data_entries_do_not_replace_missing_journals() {
fn snapshot(dir: &Path) -> Vec<(PathBuf, Option<Vec<u8>>)> {
fn visit(dir: &Path, entries: &mut Vec<(PathBuf, Option<Vec<u8>>)>) {
for entry in std::fs::read_dir(dir).unwrap() {
let entry = entry.unwrap();
let path = entry.path();
if entry.file_type().unwrap().is_dir() {
entries.push((path.clone(), None));
visit(&path, entries);
} else {
entries.push((path.clone(), Some(std::fs::read(path).unwrap())));
}
}
}
let mut entries = Vec::new();
visit(dir, &mut entries);
entries.sort();
entries
}
for (name, directory) in [
("notes.data", false),
("000001.data", true),
("1.data", false),
("0000001.data", false),
] {
for open in [false, true] {
let dir = tempfile::tempdir().unwrap();
let root = gen_root(&dir);
drop(create(&root, 1));
let generation_dir = root.join("0000000000000001");
let shard_dir = generation_dir.join("shard_000");
for entry in std::fs::read_dir(&shard_dir).unwrap() {
let path = entry.unwrap().path();
if path.extension().is_some_and(|ext| ext == "data") {
std::fs::remove_file(path).unwrap();
}
}
let misleading = shard_dir.join(name);
if directory {
std::fs::create_dir(&misleading).unwrap();
std::fs::write(misleading.join("keep"), b"directory contents").unwrap();
} else {
std::fs::write(&misleading, b"misleading journal contents").unwrap();
}
std::fs::write(shard_dir.join("000002.data.tmp"), b"keep garbage").unwrap();
let before = snapshot(&root);
let result = if open {
Generation::<TestKey>::open_existing(
real(),
&root,
&record(1, 2),
&SegConfig::test(),
OrderKind::ByHash,
)
.map(drop)
} else {
Generation::<TestKey>::check_existing(&root, &record(1, 2))
};
assert!(
matches!(result, Err(DbError::GenerationMissing { gen_id: 1, .. })),
"{name}, open={open}: {result:?}"
);
assert_eq!(snapshot(&root), before, "{name}, open={open}");
}
}
}
#[test]
fn a_misleading_journal_name_beside_a_real_journal_is_refused() {
let dir = tempfile::tempdir().unwrap();
let root = gen_root(&dir);
drop(create(&root, 1));
let shard_dir = root.join("0000000000000001").join("shard_000");
assert!(shard_dir.join("000001.data").is_file());
std::fs::write(shard_dir.join("2.data"), b"stray").unwrap();
let reason = missing_reason(Generation::<TestKey>::check_existing(&root, &record(1, 2)));
assert!(reason.contains("named like one"), "{reason}");
assert!(!shard_dir.join("000002.data").exists());
}
#[test]
fn a_recorded_shard_count_that_disagrees_with_the_directory_is_refused() {
let dir = tempfile::tempdir().unwrap();
let root = gen_root(&dir);
drop(create(&root, 1));
let reason = missing_reason(Generation::<TestKey>::check_existing(&root, &record(1, 4)));
assert!(reason.contains("shard count"), "{reason}");
}
#[test]
fn opening_a_damaged_generation_fails_before_the_engine_touches_it() {
let dir = tempfile::tempdir().unwrap();
let root = gen_root(&dir);
let result: DbResult<Generation<TestKey>> = Generation::open_existing(
real(),
&root,
&record(1, 2),
&SegConfig::test(),
OrderKind::ByHash,
);
assert!(matches!(result, Err(DbError::GenerationMissing { .. })));
assert!(!root.join("0000000000000001").exists());
}
#[test]
fn a_doomed_generation_takes_its_directory_with_it() {
let dir = tempfile::tempdir().unwrap();
let root = gen_root(&dir);
let g = create(&root, 1);
let path = g.dir().to_path_buf();
drop(g);
assert!(path.exists());
let g: Generation<TestKey> = Generation::open_existing(
real(),
&root,
&record(1, 2),
&SegConfig::test(),
OrderKind::ByHash,
)
.unwrap();
g.doom();
assert!(
path.exists(),
"the directory stays while the generation is alive"
);
drop(g);
assert!(!path.exists());
}
use crate::seg::config::Limits;
use crate::seg::hash::{key_hash, shard_range};
use crate::seg::testkit::{SEED, key_of};
const ROOMY: Limits = Limits {
max_keys: u64::MAX,
max_bytes: u64::MAX,
};
fn h(key: &TestKey) -> u64 {
key_hash(key, SEED)
}
fn put(g: &Generation<TestKey>, i: u64, value: &[u8]) {
let key = key_of(i);
assert!(matches!(
g.append(h(&key), &key, Some(value), ROOMY).unwrap(),
Append::Done { crossed: false }
));
}
fn del(g: &Generation<TestKey>, i: u64) {
let key = key_of(i);
assert!(matches!(
g.append(h(&key), &key, None, ROOMY).unwrap(),
Append::Done { .. }
));
}
fn get(g: &Generation<TestKey>, i: u64) -> GenLookup {
let key = key_of(i);
g.lookup(h(&key), &key).unwrap()
}
#[test]
fn writes_are_readable_before_and_after_a_flush() {
let dir = tempfile::tempdir().unwrap();
let g = create(&gen_root(&dir), 1);
put(&g, 1, b"one");
put(&g, 2, b"");
assert_eq!(get(&g, 1), GenLookup::Live(b"one".to_vec()));
assert_eq!(get(&g, 2), GenLookup::Live(Vec::new()));
assert_eq!(get(&g, 3), GenLookup::Absent);
g.durable_flush().unwrap();
assert_eq!(g.dirty_shards(), 0);
assert_eq!(get(&g, 1), GenLookup::Live(b"one".to_vec()));
assert_eq!(get(&g, 2), GenLookup::Live(Vec::new()));
}
#[test]
fn a_tombstone_stays_in_the_index() {
let dir = tempfile::tempdir().unwrap();
let g = create(&gen_root(&dir), 1);
put(&g, 1, b"one");
del(&g, 1);
del(&g, 2);
assert_eq!(get(&g, 1), GenLookup::Tombstone);
assert_eq!(get(&g, 2), GenLookup::Tombstone);
assert_eq!(g.probe(h(&key_of(2)), &key_of(2)), GenProbe::Tombstone);
assert_eq!(g.keys(), 2);
assert_eq!(g.live(), 0);
put(&g, 1, b"again");
assert_eq!(get(&g, 1), GenLookup::Live(b"again".to_vec()));
assert_eq!(g.live(), 1);
}
#[test]
fn recovery_restores_tombstones_and_counters() {
let dir = tempfile::tempdir().unwrap();
let root = gen_root(&dir);
{
let g = create(&root, 1);
for i in 0..100 {
put(&g, i, b"value");
}
for i in 0..10 {
del(&g, i);
}
put(&g, 50, b"newer");
g.write_hints().unwrap();
g.close().unwrap();
}
let g: Generation<TestKey> = Generation::open_existing(
real(),
&root,
&record(1, 2),
&SegConfig::test(),
OrderKind::ByHash,
)
.unwrap();
assert_eq!(g.keys(), 100);
assert_eq!(g.live(), 90);
assert!(g.bytes() > 0);
assert_eq!(g.next_gsn(), 112, "100 puts, 10 deletes and one overwrite");
assert_eq!(get(&g, 5), GenLookup::Tombstone);
assert_eq!(get(&g, 50), GenLookup::Live(b"newer".to_vec()));
assert_eq!(get(&g, 99), GenLookup::Live(b"value".to_vec()));
}
#[test]
fn crossing_a_threshold_closes_the_generation_to_later_writes() {
let dir = tempfile::tempdir().unwrap();
let g = create(&gen_root(&dir), 1);
let limits = Limits {
max_keys: 3,
max_bytes: u64::MAX,
};
for i in 0..2u64 {
let key = key_of(i);
assert!(matches!(
g.append(h(&key), &key, Some(b"v"), limits).unwrap(),
Append::Done { crossed: false }
));
}
let key = key_of(2);
assert!(matches!(
g.append(h(&key), &key, Some(b"v"), limits).unwrap(),
Append::Done { crossed: true }
));
assert!(g.is_full());
assert_eq!(get(&g, 2), GenLookup::Live(b"v".to_vec()));
let key = key_of(3);
assert!(matches!(
g.append(h(&key), &key, Some(b"v"), limits).unwrap(),
Append::Full
));
assert_eq!(
get(&g, 3),
GenLookup::Absent,
"a refused write leaves nothing"
);
assert_eq!(g.keys(), 3);
}
#[test]
fn the_byte_threshold_closes_the_generation_too() {
let dir = tempfile::tempdir().unwrap();
let g = create(&gen_root(&dir), 1);
let limits = Limits {
max_keys: u64::MAX,
max_bytes: 200,
};
let key = key_of(1);
assert!(matches!(
g.append(h(&key), &key, Some(&[0u8; 300]), limits).unwrap(),
Append::Done { crossed: true }
));
assert!(g.is_full());
}
#[test]
fn a_frozen_generation_refuses_writes() {
let dir = tempfile::tempdir().unwrap();
let g = create(&gen_root(&dir), 1);
put(&g, 1, b"one");
{
let guards = g.lock_all();
assert_eq!(guards.len(), 2);
g.mark_frozen(5_000, g.next_gsn() - 1);
}
assert!(g.is_frozen());
assert_eq!(g.frozen_at_ms(), 5_000);
assert_eq!(g.max_gsn(), 1);
let key = key_of(2);
assert!(matches!(
g.append(h(&key), &key, Some(b"v"), ROOMY).unwrap(),
Append::Frozen
));
assert!(matches!(
g.insert(h(&key), &key, b"v", Some(false), ROOMY).unwrap(),
InsertStep::Frozen
));
assert_eq!(get(&g, 2), GenLookup::Absent);
assert_eq!(get(&g, 1), GenLookup::Live(b"one".to_vec()));
{
let _guards = g.lock_all();
g.unmark_frozen();
}
put(&g, 2, b"two");
}
#[test]
fn insert_decides_in_the_active_layer_when_it_can() {
let dir = tempfile::tempdir().unwrap();
let g = create(&gen_root(&dir), 1);
put(&g, 1, b"one");
del(&g, 2);
let live = key_of(1);
let dead = key_of(2);
let unknown = key_of(3);
for lower in [None, Some(false), Some(true)] {
assert!(matches!(
g.insert(h(&live), &live, b"x", lower, ROOMY).unwrap(),
InsertStep::Exists
));
}
assert!(matches!(
g.insert(h(&dead), &dead, b"reborn", Some(true), ROOMY)
.unwrap(),
InsertStep::Done { .. }
));
assert_eq!(get(&g, 2), GenLookup::Live(b"reborn".to_vec()));
assert!(matches!(
g.insert(h(&unknown), &unknown, b"x", None, ROOMY).unwrap(),
InsertStep::NeedLower
));
assert_eq!(get(&g, 3), GenLookup::Absent);
assert!(matches!(
g.insert(h(&unknown), &unknown, b"x", Some(true), ROOMY)
.unwrap(),
InsertStep::Exists
));
assert!(matches!(
g.insert(h(&unknown), &unknown, b"x", Some(false), ROOMY)
.unwrap(),
InsertStep::Done { .. }
));
assert_eq!(get(&g, 3), GenLookup::Live(b"x".to_vec()));
}
#[test]
fn a_snapshot_is_sorted_and_bounded() {
let dir = tempfile::tempdir().unwrap();
let g = create(&gen_root(&dir), 1);
for i in 0..500 {
put(&g, i, b"v");
}
del(&g, 7);
let all = g.snapshot_range(0, u64::MAX, SEED);
assert_eq!(all.len(), 500);
assert!(all.windows(2).all(|w| (w[0].0, w[0].1) < (w[1].0, w[1].1)));
assert_eq!(all.iter().filter(|(_, _, loc)| loc.tombstone).count(), 1);
let (lo, hi) = shard_range(1, 2);
let upper = g.snapshot_range(lo, hi, SEED);
assert!(!upper.is_empty() && upper.len() < 500);
assert!(upper.iter().all(|(h, _, _)| (lo..=hi).contains(h)));
let lower = g.snapshot_range(0, lo - 1, SEED);
assert_eq!(lower.len() + upper.len(), 500);
}
#[test]
fn an_entry_is_read_back_byte_for_byte() {
let dir = tempfile::tempdir().unwrap();
let g = create(&gen_root(&dir), 1);
put(&g, 1, b"payload");
del(&g, 2);
g.durable_flush().unwrap();
for (hash, key, loc) in g.snapshot_range(0, u64::MAX, SEED) {
let entry = g.read_entry(hash, &loc.loc).unwrap();
let gsn = if key == key_of(1) { 1 } else { 2 };
let expected = if loc.tombstone {
crate::entry::serialize_entry(gsn, &key, &[], true)
} else {
crate::entry::serialize_entry(gsn, &key, b"payload", false)
};
assert_eq!(entry, expected);
}
}
#[test]
fn the_gsn_counter_can_only_go_up() {
let dir = tempfile::tempdir().unwrap();
let g = create(&gen_root(&dir), 1);
g.seed_gsn(100);
assert_eq!(g.min_gsn(), 100);
g.raise_gsn(50);
assert_eq!(g.next_gsn(), 100);
g.raise_gsn(200);
assert_eq!(g.next_gsn(), 200);
assert_eq!(
g.min_gsn(),
100,
"raising the counter does not move the first GSN"
);
}
#[test]
fn tree_generation_orders_keys_after_append_and_recovery() {
use crate::map_index::Dir;
use crate::seg::sidecar::OrderKind;
use crate::seg::testkit::ordered_key;
use std::ops::Bound;
for hints in [false, true] {
let dir = tempfile::tempdir().unwrap();
let root = gen_root(&dir);
let config = SegConfig {
hints,
..SegConfig::test()
};
let g: Generation<TestKey> =
Generation::create(real(), &root, 1, &config, 100, OrderKind::ByKey).unwrap();
for i in [256, 3, 1, 255, 2, 257] {
let k = ordered_key(i);
g.append(h(&k), &k, Some(b"old"), ROOMY).unwrap();
}
let deleted = ordered_key(3);
g.append(h(&deleted), &deleted, None, ROOMY).unwrap();
let newest = ordered_key(256);
g.append(h(&newest), &newest, Some(b"newest"), ROOMY)
.unwrap();
let check = |g: &Generation<TestKey>| {
for shard in 0..g.shard_count() {
let mut expected: Vec<_> = [1, 2, 3, 255, 256, 257]
.into_iter()
.map(ordered_key)
.filter(|k| g.shard_of(h(k)) == shard)
.collect();
expected.sort_by(|a, b| a.as_bytes().cmp(b.as_bytes()));
let rows =
g.ordered_batch(shard, Bound::Unbounded, Bound::Unbounded, Dir::Asc, 100);
assert_eq!(rows.iter().map(|(k, _)| *k).collect::<Vec<_>>(), expected);
assert_eq!(
rows.iter().filter(|(_, loc)| loc.tombstone).count(),
usize::from(expected.contains(&deleted))
);
expected.reverse();
assert_eq!(
g.ordered_batch(shard, Bound::Unbounded, Bound::Unbounded, Dir::Desc, 2)
.iter()
.map(|(k, _)| *k)
.collect::<Vec<_>>(),
expected.into_iter().take(2).collect::<Vec<_>>()
);
let lo = ordered_key(2);
let hi = ordered_key(256);
let bounded = g.ordered_batch(
shard,
Bound::Excluded(&lo),
Bound::Included(&hi),
Dir::Asc,
100,
);
let expected_bounded: Vec<_> = [3, 255, 256]
.into_iter()
.map(ordered_key)
.filter(|k| g.shard_of(h(k)) == shard)
.collect();
assert_eq!(
bounded.iter().map(|(k, _)| *k).collect::<Vec<_>>(),
expected_bounded
);
assert!(
g.ordered_batch(
shard,
Bound::Included(&hi),
Bound::Included(&lo),
Dir::Asc,
100
)
.is_empty()
);
assert!(
g.ordered_batch(shard, Bound::Unbounded, Bound::Unbounded, Dir::Asc, 0)
.is_empty()
);
}
assert_eq!(
g.lookup(h(&newest), &newest).unwrap(),
GenLookup::Live(b"newest".to_vec())
);
assert_eq!(
g.lookup(h(&deleted), &deleted).unwrap(),
GenLookup::Tombstone
);
};
check(&g);
g.durable_flush().unwrap();
g.write_hints().unwrap();
g.close().unwrap();
drop(g);
let changed = SegConfig {
shard_count: 8,
..config
};
let g: Generation<TestKey> =
Generation::open_existing(real(), &root, &record(1, 2), &changed, OrderKind::ByKey)
.unwrap();
assert_eq!(g.shard_count(), 2);
check(&g);
}
}
}