#![forbid(unsafe_code)]
#![warn(missing_docs)]
#![allow(
clippy::cast_possible_truncation,
clippy::doc_markdown,
clippy::iter_without_into_iter,
clippy::map_unwrap_or,
clippy::missing_const_for_fn,
clippy::missing_errors_doc,
clippy::needless_pass_by_value,
clippy::return_self_not_must_use,
clippy::significant_drop_tightening,
clippy::type_complexity
)]
mod cache;
pub use cache::{CacheOptions, CacheStats, MemoryCache};
use std::collections::{BTreeMap, BTreeSet, HashMap};
use std::fmt::{Display, Formatter};
use std::fs::{self, File, OpenOptions};
use std::io::{self, ErrorKind, Read, Seek, SeekFrom, Write};
use std::ops::{Bound, RangeBounds};
use std::path::{Component, Path, PathBuf};
use std::sync::{
Arc, Mutex, OnceLock, RwLock, Weak,
atomic::{AtomicBool, AtomicU64, Ordering},
mpsc::{self, RecvTimeoutError, SyncSender, TryRecvError},
};
use std::thread;
use std::time::{Duration, Instant};
#[cfg(unix)]
use std::os::unix::fs::FileExt;
#[cfg(feature = "benchmark")]
use arc_swap::ArcSwap;
use crc32fast::Hasher;
use serde::{Deserialize, Serialize};
const WAL_MAGIC: &[u8; 8] = b"TDBWAL01";
const TABLE_MAGIC: &[u8; 8] = b"TDBTAB01";
const TABLE_MAGIC_V2: &[u8; 8] = b"TDBTAB02";
const TABLE_MAGIC_V3: &[u8; 8] = b"TDBTAB03";
const TABLE_FOOTER_MAGIC: &[u8; 8] = b"TDBFTR01";
const TABLE_BLOCK_CACHE_BYTES: usize = 8 * 1024 * 1024;
const FORMAT_VERSION: u32 = 1;
const WAL_FILE: &str = "WAL";
const MANIFEST_FILE: &str = "MANIFEST.json";
const MANIFEST_TEMP_FILE: &str = ".MANIFEST.json.tmp";
const LOCK_FILE: &str = "LOCK";
#[cfg(feature = "benchmark")]
type RamGeneration = HashMap<Arc<str>, Arc<BTreeMap<Vec<u8>, Arc<Vec<u8>>>>>;
#[derive(Clone, Copy)]
enum WalSyncMode {
Data,
#[cfg(feature = "benchmark")]
All,
}
fn sync_wal(file: &File, mode: WalSyncMode) -> io::Result<()> {
match mode {
WalSyncMode::Data => file.sync_data(),
#[cfg(feature = "benchmark")]
WalSyncMode::All => file.sync_all(),
}
}
#[cfg(test)]
thread_local! {
static FAULT_POINT: std::cell::RefCell<Option<&'static str>> = const { std::cell::RefCell::new(None) };
}
#[cfg(test)]
fn set_fault_point(point: Option<&'static str>) {
FAULT_POINT.with(|fault| *fault.borrow_mut() = point);
}
#[cfg(test)]
fn current_fault_point() -> Option<&'static str> {
FAULT_POINT.with(|fault| *fault.borrow())
}
#[cfg(not(test))]
fn current_fault_point() -> Option<&'static str> {
None
}
fn maybe_fail(point: &'static str, fault_point: Option<&'static str>) -> Result<()> {
if fault_point == Some(point) {
Err(Error::message(format!("injected ThingDB fault: {point}")))
} else {
Ok(())
}
}
fn validate_table_name(name: &str) -> Result<()> {
let path = Path::new(name);
if name.is_empty()
|| path.is_absolute()
|| path
.components()
.any(|component| !matches!(component, Component::Normal(_)))
{
return Err(Error::message("invalid ThingDB table filename"));
}
Ok(())
}
fn validate_manifest(manifest: &Manifest) -> Result<()> {
let mut files = BTreeSet::new();
for table_file in &manifest.table_files {
validate_table_name(table_file)?;
if !files.insert(table_file) {
return Err(Error::message("duplicate ThingDB table filename"));
}
}
if let Some(table_file) = &manifest.table_file {
validate_table_name(table_file)?;
if !manifest.table_files.is_empty() && manifest.table_files.last() != Some(table_file) {
return Err(Error::message(
"ThingDB manifest legacy table filename does not match table layers",
));
}
}
let table_files = if manifest.table_files.is_empty() {
manifest.table_file.iter().collect::<Vec<_>>()
} else {
manifest.table_files.iter().collect::<Vec<_>>()
};
if table_files.is_empty() && manifest.table_sequence != 0 {
return Err(Error::message(
"ThingDB manifest has a table sequence without a table",
));
}
if table_files.windows(2).any(|files| files[0] >= files[1]) {
return Err(Error::message(
"ThingDB manifest table layers are not in filename order",
));
}
Ok(())
}
fn cleanup_temporary_files(path: &Path) -> Result<()> {
let entries = fs::read_dir(path)?;
for entry in entries {
let entry = entry?;
let name = entry.file_name();
let name = name.to_string_lossy();
if name == MANIFEST_TEMP_FILE || (name.starts_with(".table-") && name.ends_with(".tdb.tmp"))
{
fs::remove_file(entry.path())?;
}
}
Ok(())
}
pub type Result<T> = std::result::Result<T, Error>;
#[derive(Debug)]
pub struct Error(String);
impl Error {
fn message(message: impl Into<String>) -> Self {
Self(message.into())
}
}
impl Display for Error {
fn fmt(&self, formatter: &mut Formatter<'_>) -> std::fmt::Result {
formatter.write_str(&self.0)
}
}
impl std::error::Error for Error {}
impl From<io::Error> for Error {
fn from(error: io::Error) -> Self {
Self(error.to_string())
}
}
impl From<serde_json::Error> for Error {
fn from(error: serde_json::Error) -> Self {
Self(error.to_string())
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum PersistMode {
SyncAll,
}
#[derive(Clone, Debug, Default, Eq, PartialEq, Serialize)]
pub struct WalDiagnostics {
pub journal_bytes: u64,
pub frame_count: u64,
pub recovery_bytes: u64,
pub recovery_duration_ns: u64,
pub encode_duration_ns: u64,
pub buffer_allocation_duration_ns: u64,
pub buffer_reserved_bytes: u64,
pub encode_outside_lock_duration_ns: u64,
pub append_duration_ns: u64,
pub wal_bytes_appended: u64,
pub sync_duration_ns: u64,
pub wal_lock_wait_duration_ns: u64,
pub wal_lock_held_duration_ns: u64,
pub state_apply_duration_ns: u64,
pub lock_duration_ns: u64,
pub logical_commit_count: u64,
pub physical_sync_count: u64,
pub total_group_size: u64,
pub max_group_size: u64,
pub queue_wait_duration_ns: u64,
pub recovery_required: bool,
pub state_generation_conflict_count: u64,
pub truncation_failure_count: u64,
pub wal_over_budget: bool,
pub memtable_bytes: u64,
pub flush_count: u64,
pub automatic_flush_count: u64,
pub flush_duration_ns: u64,
pub memtable_over_budget: bool,
pub last_error: Option<String>,
pub table_lookup_count: u64,
pub mutable_state_lookup_count: u64,
pub pending_table_lookup_count: u64,
pub immutable_layer_lookup_count: u64,
pub table_layers_consulted: u64,
pub table_bytes_read: u64,
pub table_read_duration_ns: u64,
pub read_lock_wait_duration_ns: u64,
pub read_lock_held_duration_ns: u64,
pub table_reader_wait_duration_ns: u64,
pub table_lookup_duration_ns: u64,
pub file_read_duration_ns: u64,
pub table_open_duration_ns: u64,
pub scan_duration_ns: u64,
pub scan_count: u64,
pub scan_keys_examined: u64,
pub scan_layers_consulted: u64,
pub scan_lock_wait_duration_ns: u64,
pub scan_lock_held_duration_ns: u64,
pub scan_cursor_init_duration_ns: u64,
pub scan_merge_duration_ns: u64,
pub scan_page_capture_count: u64,
pub scan_page_capture_duration_ns: u64,
pub scan_page_capture_fallback_count: u64,
pub scan_page_capture_candidates_copied: u64,
pub scan_page_capture_fallback_candidates_copied: u64,
pub scan_returned_entries: u64,
pub scan_error_count: u64,
pub table_layer_count: u64,
pub compaction_count: u64,
pub compaction_duration_ns: u64,
pub compaction_input_bytes: u64,
pub compaction_output_bytes: u64,
pub table_bytes_written: u64,
pub table_block_cache_capacity_bytes: u64,
pub table_block_cache_resident_bytes: u64,
pub table_block_cache_entries: u64,
pub table_block_cache_hits: u64,
pub table_block_cache_misses: u64,
pub table_block_cache_decoded_hits: u64,
pub table_block_cache_decoded_misses: u64,
pub table_block_cache_evictions: u64,
}
#[derive(Clone, Debug, Default, Eq, PartialEq, Serialize)]
pub struct RamDiagnostics {
pub lookup_count: u64,
pub key_encode_duration_ns: u64,
pub lock_wait_duration_ns: u64,
pub lock_held_duration_ns: u64,
pub lookup_duration_ns: u64,
pub value_clone_duration_ns: u64,
pub value_acquire_duration_ns: u64,
pub mutation_count: u64,
pub mutation_duration_ns: u64,
pub iteration_count: u64,
pub iteration_duration_ns: u64,
pub iteration_entries_examined: u64,
pub iteration_entries_returned: u64,
pub deserialization_duration_ns: u64,
pub serialization_count: u64,
pub serialization_duration_ns: u64,
pub search_count: u64,
pub search_duration_ns: u64,
pub search_index_count: u64,
pub search_index_duration_ns: u64,
pub snapshot_count: u64,
pub snapshot_duration_ns: u64,
}
#[derive(Default)]
struct RamHotDiagnostics {
lookup_count: AtomicU64,
lock_wait_duration_ns: AtomicU64,
lock_held_duration_ns: AtomicU64,
lookup_duration_ns: AtomicU64,
value_clone_duration_ns: AtomicU64,
value_acquire_duration_ns: AtomicU64,
mutation_count: AtomicU64,
mutation_duration_ns: AtomicU64,
deserialization_duration_ns: AtomicU64,
serialization_count: AtomicU64,
serialization_duration_ns: AtomicU64,
}
impl RamHotDiagnostics {
fn add(counter: &AtomicU64, value: u64) {
counter.fetch_add(value, Ordering::Relaxed);
}
fn snapshot_into(&self, diagnostics: &mut RamDiagnostics) {
diagnostics.lookup_count = self.lookup_count.load(Ordering::Relaxed);
diagnostics.lock_wait_duration_ns = self.lock_wait_duration_ns.load(Ordering::Relaxed);
diagnostics.lock_held_duration_ns = self.lock_held_duration_ns.load(Ordering::Relaxed);
diagnostics.lookup_duration_ns = self.lookup_duration_ns.load(Ordering::Relaxed);
diagnostics.value_clone_duration_ns = self.value_clone_duration_ns.load(Ordering::Relaxed);
diagnostics.value_acquire_duration_ns =
self.value_acquire_duration_ns.load(Ordering::Relaxed);
diagnostics.mutation_count = self.mutation_count.load(Ordering::Relaxed);
diagnostics.mutation_duration_ns = self.mutation_duration_ns.load(Ordering::Relaxed);
diagnostics.deserialization_duration_ns =
self.deserialization_duration_ns.load(Ordering::Relaxed);
diagnostics.serialization_count = self.serialization_count.load(Ordering::Relaxed);
diagnostics.serialization_duration_ns =
self.serialization_duration_ns.load(Ordering::Relaxed);
}
}
#[derive(Clone, Copy, Debug, Default)]
pub struct KeyspaceCreateOptions;
impl KeyspaceCreateOptions {
#[allow(non_upper_case_globals)]
pub const default: Self = Self;
}
pub struct DatabaseBuilder {
path: PathBuf,
max_journaling_size: u64,
max_memtable_bytes: u64,
max_table_layers: usize,
wal_sync_mode: WalSyncMode,
}
#[derive(Clone)]
pub struct Database {
inner: Arc<Mutex<Inner>>,
ram_keyspaces: Option<Arc<RwLock<HashMap<Arc<str>, BTreeMap<Vec<u8>, Arc<Vec<u8>>>>>>>,
#[cfg(feature = "benchmark")]
ram_rcu_keyspaces: Option<Arc<ArcSwap<RamGeneration>>>,
ram_diagnostics: Arc<Mutex<RamDiagnostics>>,
ram_hot_diagnostics: Arc<RamHotDiagnostics>,
ram_logical_commit_count: Arc<AtomicU64>,
ram_total_group_size: Arc<AtomicU64>,
ram_state_apply_duration_ns: Arc<AtomicU64>,
writer: Arc<WriterCoordinator>,
commit_gate: Arc<Mutex<()>>,
}
struct Inner {
path: PathBuf,
wal: Option<Arc<File>>,
lock: Option<File>,
in_memory: bool,
state: BTreeMap<Vec<u8>, Vec<u8>>,
sequence: u64,
table_sequence: u64,
table_files: Vec<String>,
table_layers: Vec<TableLayer>,
pending_table: BTreeMap<Vec<u8>, Option<Vec<u8>>>,
pending_table_bytes: u64,
max_journaling_size: u64,
max_memtable_bytes: u64,
max_table_layers: usize,
diagnostics: WalDiagnostics,
table_block_cache: Arc<TableBlockCache>,
recovery_required: bool,
commit_gate: Arc<Mutex<()>>,
wal_io_lock: Arc<Mutex<()>>,
state_generation: u64,
wal_sync_mode: WalSyncMode,
flush_scheduled: Arc<AtomicBool>,
}
#[derive(Clone)]
struct TableLayer {
file: Arc<File>,
path: PathBuf,
entries: Arc<OnceLock<Arc<Vec<TableIndexEntry>>>>,
blocks: Arc<Vec<TableBlock>>,
block_cache: Arc<TableBlockCache>,
is_v2: bool,
}
#[derive(Clone)]
struct TableIndexEntry {
key: Vec<u8>,
offset: u64,
length: u64,
}
#[derive(Clone, Debug)]
struct TableBlock {
offset: u64,
length: u64,
first_key: Vec<u8>,
last_key: Vec<u8>,
checksum: u32,
}
#[derive(Clone, Debug, Eq, Hash, PartialEq)]
struct TableBlockCacheKey {
path: PathBuf,
offset: u64,
}
struct CachedTableBlock {
bytes: Arc<Vec<u8>>,
records: Option<Arc<Vec<TableScanRecord>>>,
decoded_bytes: usize,
last_access: u64,
}
struct TableBlockCacheState {
capacity_bytes: usize,
resident_bytes: usize,
access_clock: u64,
hits: u64,
misses: u64,
decoded_hits: u64,
decoded_misses: u64,
evictions: u64,
entries: HashMap<TableBlockCacheKey, CachedTableBlock>,
lru: BTreeMap<u64, TableBlockCacheKey>,
}
#[derive(Clone, Copy, Debug, Default)]
struct TableBlockCacheDiagnostics {
capacity_bytes: usize,
resident_bytes: usize,
entries: usize,
hits: u64,
misses: u64,
decoded_hits: u64,
decoded_misses: u64,
evictions: u64,
}
struct TableBlockCache {
state: Mutex<TableBlockCacheState>,
}
impl Default for TableBlockCache {
fn default() -> Self {
Self::with_capacity(TABLE_BLOCK_CACHE_BYTES)
}
}
impl TableBlockCache {
fn with_capacity(capacity_bytes: usize) -> Self {
Self {
state: Mutex::new(TableBlockCacheState {
capacity_bytes,
resident_bytes: 0,
access_clock: 0,
hits: 0,
misses: 0,
decoded_hits: 0,
decoded_misses: 0,
evictions: 0,
entries: HashMap::new(),
lru: BTreeMap::new(),
}),
}
}
fn diagnostics(&self) -> TableBlockCacheDiagnostics {
self.state.lock().map_or_else(
|_| TableBlockCacheDiagnostics::default(),
|state| TableBlockCacheDiagnostics {
capacity_bytes: state.capacity_bytes,
resident_bytes: state.resident_bytes,
entries: state.entries.len(),
hits: state.hits,
misses: state.misses,
decoded_hits: state.decoded_hits,
decoded_misses: state.decoded_misses,
evictions: state.evictions,
},
)
}
fn get(&self, key: &TableBlockCacheKey) -> Option<Arc<Vec<u8>>> {
let mut state = self.state.lock().ok()?;
let previous_access = state.entries.get(key).map(|entry| entry.last_access);
let Some(previous_access) = previous_access else {
state.misses = state.misses.saturating_add(1);
return None;
};
state.lru.remove(&previous_access);
state.access_clock = state.access_clock.wrapping_add(1);
let last_access = state.access_clock;
let entry = state.entries.get_mut(key)?;
entry.last_access = last_access;
let bytes = Arc::clone(&entry.bytes);
state.lru.insert(last_access, key.clone());
state.hits = state.hits.saturating_add(1);
Some(bytes)
}
fn get_records(&self, key: &TableBlockCacheKey) -> Option<Arc<Vec<TableScanRecord>>> {
let mut state = self.state.lock().ok()?;
let previous_access = state.entries.get(key).map(|entry| entry.last_access);
let Some(previous_access) = previous_access else {
state.decoded_misses = state.decoded_misses.saturating_add(1);
return None;
};
let records = state
.entries
.get(key)
.and_then(|entry| entry.records.as_ref())
.map(Arc::clone);
let Some(records) = records else {
state.decoded_misses = state.decoded_misses.saturating_add(1);
return None;
};
state.lru.remove(&previous_access);
state.access_clock = state.access_clock.wrapping_add(1);
let last_access = state.access_clock;
if let Some(entry) = state.entries.get_mut(key) {
entry.last_access = last_access;
}
state.lru.insert(last_access, key.clone());
state.decoded_hits = state.decoded_hits.saturating_add(1);
Some(records)
}
fn insert_records(&self, key: &TableBlockCacheKey, records: Arc<Vec<TableScanRecord>>) {
let decoded_bytes = records
.capacity()
.saturating_mul(std::mem::size_of::<TableScanRecord>())
.saturating_add(records.iter().fold(0usize, |bytes, record| {
bytes
.saturating_add(record.key.capacity())
.saturating_add(record.value.as_ref().map_or(0, Vec::capacity))
}));
let Ok(mut state) = self.state.lock() else {
return;
};
if decoded_bytes == 0
|| decoded_bytes > state.capacity_bytes
|| state.entries.get(key).is_none_or(|entry| {
entry.records.is_some()
|| entry.bytes.len().saturating_add(decoded_bytes) > state.capacity_bytes
})
{
return;
}
let mut deferred_current = None;
while state.resident_bytes.saturating_add(decoded_bytes) > state.capacity_bytes {
let Some((access, oldest_key)) = state.lru.pop_first() else {
if let Some((access, deferred_key)) = deferred_current.take() {
state.lru.insert(access, deferred_key);
}
return;
};
if oldest_key == *key {
deferred_current = Some((access, oldest_key));
continue;
}
if let Some(oldest) = state.entries.remove(&oldest_key) {
state.resident_bytes = state
.resident_bytes
.saturating_sub(oldest.bytes.len().saturating_add(oldest.decoded_bytes));
state.evictions = state.evictions.saturating_add(1);
}
}
if let Some((access, deferred_key)) = deferred_current {
state.lru.insert(access, deferred_key);
}
if let Some(entry) = state.entries.get_mut(key)
&& entry.records.is_none()
{
entry.decoded_bytes = decoded_bytes;
entry.records = Some(records);
state.resident_bytes = state.resident_bytes.saturating_add(decoded_bytes);
}
}
fn insert(&self, key: TableBlockCacheKey, bytes: Arc<Vec<u8>>) {
let Ok(mut state) = self.state.lock() else {
return;
};
if bytes.len() > state.capacity_bytes || state.capacity_bytes == 0 {
return;
}
if let Some(previous) = state.entries.remove(&key) {
state.lru.remove(&previous.last_access);
state.resident_bytes = state
.resident_bytes
.saturating_sub(previous.bytes.len().saturating_add(previous.decoded_bytes));
}
while state.resident_bytes.saturating_add(bytes.len()) > state.capacity_bytes {
let Some((access, oldest_key)) = state.lru.pop_first() else {
break;
};
if let Some(oldest) = state.entries.remove(&oldest_key) {
state.resident_bytes = state
.resident_bytes
.saturating_sub(oldest.bytes.len().saturating_add(oldest.decoded_bytes));
state.evictions = state.evictions.saturating_add(1);
} else {
state.lru.remove(&access);
}
}
state.access_clock = state.access_clock.wrapping_add(1);
let last_access = state.access_clock;
state.resident_bytes = state.resident_bytes.saturating_add(bytes.len());
state.entries.insert(
key.clone(),
CachedTableBlock {
bytes: Arc::clone(&bytes),
records: None,
decoded_bytes: 0,
last_access,
},
);
state.lru.insert(last_access, key);
}
}
#[derive(Clone)]
struct TableScanRecord {
key: Vec<u8>,
value: Option<Vec<u8>>,
priority: usize,
}
struct TableScanCursor {
block_index: usize,
legacy_entries: Option<Arc<Vec<TableIndexEntry>>>,
legacy_entry_index: usize,
is_v2: bool,
include_values: bool,
records: Arc<Vec<TableScanRecord>>,
record_index: usize,
priority: usize,
bytes_read: u64,
read_duration_ns: u64,
}
impl TableLayer {
fn loaded_entries(&self) -> Result<Arc<Vec<TableIndexEntry>>> {
if self.entries.get().is_none() {
let (_, entries, _, _) = read_table_index(&self.path)?;
let _ = self.entries.set(Arc::new(entries));
}
Ok(Arc::clone(self.entries.get().ok_or_else(|| {
Error::message("ThingDB table index was not initialized")
})?))
}
fn candidate_entry_range(&self, key: &[u8]) -> std::ops::Range<usize> {
if self.blocks.is_empty() {
let entries = self.entries.get().map_or(0, |entries| entries.len());
return 0..entries;
}
let block_index = self
.blocks
.partition_point(|block| block.last_key.as_slice() < key);
let Some(block) = self.blocks.get(block_index) else {
return 0..0;
};
if block.first_key.as_slice() > key {
return 0..0;
}
let end = block.offset.saturating_add(block.length);
let Some(entries) = self.entries.get() else {
return 0..0;
};
let start_index = entries.partition_point(|entry| entry.offset < block.offset);
let end_index = entries.partition_point(|entry| entry.offset < end);
start_index..end_index
}
fn candidate_block(&self, key: &[u8]) -> Option<&TableBlock> {
if self.blocks.is_empty() {
return None;
}
let index = self
.blocks
.partition_point(|block| block.last_key.as_slice() < key);
self.blocks
.get(index)
.filter(|block| block.first_key.as_slice() <= key && key <= block.last_key.as_slice())
}
}
impl TableScanCursor {
fn new(
layer: &TableLayer,
priority: usize,
lower: &[u8],
upper: Option<&[u8]>,
after: Option<&[u8]>,
include_values: bool,
) -> Result<Self> {
let legacy_entries = if layer.blocks.is_empty() {
layer.entries.get().cloned()
} else {
None
};
let legacy_entry_index = legacy_entries.as_ref().map_or(0, |entries| {
let lower_index = entries.partition_point(|entry| entry.key.as_slice() < lower);
after.map_or(lower_index, |after| {
entries
.partition_point(|entry| entry.key.as_slice() <= after)
.max(lower_index)
})
});
let block_index = layer
.blocks
.partition_point(|block| block.last_key.as_slice() < lower);
let mut cursor = Self {
block_index,
legacy_entries,
legacy_entry_index,
is_v2: layer.is_v2,
include_values,
records: Arc::new(Vec::new()),
record_index: 0,
priority,
bytes_read: 0,
read_duration_ns: 0,
};
if cursor.legacy_entries.is_some() {
cursor.load_next_legacy_entry(layer, lower, upper)?;
} else {
cursor.load_next_block(layer, lower, upper, after)?;
}
Ok(cursor)
}
fn head(&self) -> Option<&TableScanRecord> {
self.records.get(self.record_index)
}
fn advance(&mut self, layer: &TableLayer, lower: &[u8], upper: Option<&[u8]>) -> Result<()> {
self.record_index = self.record_index.saturating_add(1);
if self.record_index < self.records.len() {
return Ok(());
}
if self.legacy_entries.is_some() {
self.load_next_legacy_entry(layer, lower, upper)
} else {
self.load_next_block(layer, lower, upper, None)
}
}
fn load_next_legacy_entry(
&mut self,
layer: &TableLayer,
lower: &[u8],
upper: Option<&[u8]>,
) -> Result<()> {
self.records = Arc::new(Vec::new());
self.record_index = 0;
let Some(entries) = self.legacy_entries.as_ref() else {
return Ok(());
};
let Some(entry) = entries.get(self.legacy_entry_index) else {
return Ok(());
};
if entry.key.as_slice() < lower || upper.is_some_and(|upper| entry.key.as_slice() >= upper)
{
return Ok(());
}
self.legacy_entry_index += 1;
let (value, _, read_duration_ns) = read_table_value_handle(&layer.file, entry, self.is_v2)?;
self.bytes_read = self.bytes_read.saturating_add(entry.length);
self.read_duration_ns = self.read_duration_ns.saturating_add(read_duration_ns);
self.records = Arc::new(vec![TableScanRecord {
key: entry.key.clone(),
value,
priority: self.priority,
}]);
Ok(())
}
fn load_next_block(
&mut self,
layer: &TableLayer,
lower: &[u8],
upper: Option<&[u8]>,
after: Option<&[u8]>,
) -> Result<()> {
self.records = Arc::new(Vec::new());
self.record_index = 0;
while let Some(block) = layer.blocks.get(self.block_index) {
self.block_index += 1;
if block.last_key.as_slice() < lower {
continue;
}
if upper.is_some_and(|upper| block.first_key.as_slice() >= upper) {
break;
}
let (records, bytes_read, read_duration_ns) =
read_table_block_records(layer, block, self.include_values)?;
self.bytes_read = self.bytes_read.saturating_add(bytes_read);
self.read_duration_ns = self.read_duration_ns.saturating_add(read_duration_ns);
let lower_index = records.partition_point(|record| record.key.as_slice() < lower);
let after_index = after.map_or(lower_index, |after| {
let index = records.partition_point(|record| record.key.as_slice() <= after);
index.max(lower_index)
});
let end_index = upper.map_or(records.len(), |upper| {
records.partition_point(|record| record.key.as_slice() < upper)
});
if after_index < end_index {
self.records = records;
self.record_index = after_index;
return Ok(());
}
}
Ok(())
}
}
struct DurableScanPageSnapshot {
state: Vec<TableScanRecord>,
pending: Vec<TableScanRecord>,
state_after: Option<Vec<u8>>,
pending_after: Option<Vec<u8>>,
state_has_more: bool,
pending_has_more: bool,
layers: Vec<TableLayer>,
lower: Vec<u8>,
upper: Option<Vec<u8>>,
after: Option<Vec<u8>>,
generation: u64,
lock_wait_ns: u64,
lock_held_ns: u64,
cursor_init_ns: u64,
}
const DURABLE_SCAN_MEMTABLE_CHUNK_SIZE: usize = 256;
struct DurableMemtableScanChunk {
records: Vec<TableScanRecord>,
after: Option<Vec<u8>>,
has_more: bool,
}
fn capture_durable_memtable_chunk<V, F>(
map: &BTreeMap<Vec<u8>, V>,
lower: &[u8],
upper: Option<&[u8]>,
after: Option<&[u8]>,
priority: usize,
value: F,
) -> DurableMemtableScanChunk
where
F: Fn(&V) -> Option<Vec<u8>>,
{
let lower_bound = after.map_or_else(
|| Bound::Included(lower.to_vec()),
|key| Bound::Excluded(key.to_vec()),
);
let upper_bound = upper.map_or(Bound::Unbounded, |key| Bound::Excluded(key.to_vec()));
let mut records = Vec::with_capacity(DURABLE_SCAN_MEMTABLE_CHUNK_SIZE);
let mut has_more = false;
for (key, stored_value) in map
.range((lower_bound, upper_bound))
.take(DURABLE_SCAN_MEMTABLE_CHUNK_SIZE.saturating_add(1))
{
if records.len() == DURABLE_SCAN_MEMTABLE_CHUNK_SIZE {
has_more = true;
break;
}
records.push(TableScanRecord {
key: key.clone(),
value: value(stored_value),
priority,
});
}
let after = records.last().map(|record| record.key.clone());
DurableMemtableScanChunk {
records,
after,
has_more,
}
}
#[derive(Default)]
struct DurableScanPageCaptureMetrics {
attempted: bool,
duration_ns: u64,
candidates_copied: u64,
fallback: bool,
}
impl DurableScanPageCaptureMetrics {
fn record(&self, diagnostics: &mut WalDiagnostics) {
if !self.attempted {
return;
}
diagnostics.scan_page_capture_count = diagnostics.scan_page_capture_count.saturating_add(1);
diagnostics.scan_page_capture_duration_ns = diagnostics
.scan_page_capture_duration_ns
.saturating_add(self.duration_ns);
diagnostics.scan_page_capture_candidates_copied = diagnostics
.scan_page_capture_candidates_copied
.saturating_add(self.candidates_copied);
if self.fallback {
diagnostics.scan_page_capture_fallback_count = diagnostics
.scan_page_capture_fallback_count
.saturating_add(1);
diagnostics.scan_page_capture_fallback_candidates_copied = diagnostics
.scan_page_capture_fallback_candidates_copied
.saturating_add(self.candidates_copied);
}
}
}
impl Inner {
fn materialize_state(&mut self) -> Result<BTreeMap<Vec<u8>, Vec<u8>>> {
let mut state = BTreeMap::new();
for layer in &mut self.table_layers {
let entries = layer.loaded_entries()?;
for entry in entries.iter() {
match read_table_value_handle(&layer.file, entry, layer.is_v2)?.0 {
Some(value) => {
state.insert(entry.key.clone(), value);
},
None => {
state.remove(&entry.key);
},
}
}
}
for (key, value) in &self.state {
state.insert(key.clone(), value.clone());
}
for (key, value) in &self.pending_table {
match value {
Some(value) => {
state.insert(key.clone(), value.clone());
},
None => {
state.remove(key);
},
}
}
Ok(state)
}
}
#[derive(Debug, Serialize, Deserialize)]
struct Manifest {
format_version: u32,
table_file: Option<String>,
#[serde(default)]
table_files: Vec<String>,
table_sequence: u64,
}
#[derive(Clone)]
pub struct Keyspace {
db: Database,
name: Arc<str>,
namespace: Arc<[u8]>,
}
pub struct Batch {
db: Database,
memory_mode: bool,
operations: Vec<BatchOperation>,
}
struct BatchOperation {
keyspace: Arc<str>,
key: Vec<u8>,
value: Option<Vec<u8>>,
}
#[derive(Clone, Debug)]
enum Operation {
Put { key: Vec<u8>, value: Vec<u8> },
Delete { key: Vec<u8> },
}
struct CommitRequest {
operations: Vec<Operation>,
encoded_bytes: usize,
submitted_at: Instant,
fault_point: Option<&'static str>,
response: mpsc::Sender<Result<()>>,
}
struct WriterCoordinator {
sender: Mutex<Option<SyncSender<CommitRequest>>>,
handle: Mutex<Option<thread::JoinHandle<()>>>,
}
const WRITER_QUEUE_CAPACITY: usize = 1024;
const GROUP_COMMIT_WINDOW: Duration = Duration::from_micros(250);
const MAX_GROUP_OPERATIONS: usize = 4_096;
const MAX_GROUP_BYTES: usize = 4 * 1024 * 1024;
impl WriterCoordinator {
fn new(inner: Weak<Mutex<Inner>>) -> Result<Arc<Self>> {
let (sender, receiver) = mpsc::sync_channel(WRITER_QUEUE_CAPACITY);
let handle = thread::Builder::new()
.name("thingdb-writer".to_string())
.spawn(move || writer_loop(inner, receiver))
.map_err(Error::from)?;
Ok(Arc::new(Self {
sender: Mutex::new(Some(sender)),
handle: Mutex::new(Some(handle)),
}))
}
}
impl Drop for WriterCoordinator {
fn drop(&mut self) {
let _ = self.sender.get_mut().ok().and_then(Option::take);
if let Some(handle) = self.handle.get_mut().ok().and_then(Option::take) {
let _ = handle.join();
}
}
}
fn writer_loop(inner: Weak<Mutex<Inner>>, receiver: mpsc::Receiver<CommitRequest>) {
let mut pending = None;
let mut wal_buffer = Vec::new();
loop {
let Some(first) = pending.take().or_else(|| receiver.recv().ok()) else {
return;
};
let mut group = vec![first];
let mut operation_count = group[0].operations.len();
let mut operation_bytes = group[0].encoded_bytes;
let deadline = match receiver.try_recv() {
Ok(request) => {
let request_operations = request.operations.len();
let request_bytes = request.encoded_bytes;
if operation_count + request_operations <= MAX_GROUP_OPERATIONS
&& operation_bytes + request_bytes <= MAX_GROUP_BYTES
{
operation_count += request_operations;
operation_bytes += request_bytes;
group.push(request);
Some(Instant::now() + GROUP_COMMIT_WINDOW)
} else {
pending = Some(request);
None
}
},
Err(TryRecvError::Empty | TryRecvError::Disconnected) => None,
};
if let Some(deadline) = deadline {
loop {
if operation_count >= MAX_GROUP_OPERATIONS || operation_bytes >= MAX_GROUP_BYTES {
break;
}
let remaining = deadline.saturating_duration_since(Instant::now());
if remaining.is_zero() {
break;
}
match receiver.recv_timeout(remaining) {
Ok(request) => {
let request_operations = request.operations.len();
let request_bytes = request.encoded_bytes;
if operation_count + request_operations > MAX_GROUP_OPERATIONS
|| operation_bytes + request_bytes > MAX_GROUP_BYTES
{
pending = Some(request);
break;
}
operation_count += request_operations;
operation_bytes += request_bytes;
group.push(request);
},
Err(RecvTimeoutError::Timeout | RecvTimeoutError::Disconnected) => break,
}
}
}
process_group(&inner, group, &mut wal_buffer);
}
}
fn schedule_background_flush(inner_arc: &Arc<Mutex<Inner>>, scheduled: Arc<AtomicBool>) -> bool {
if scheduled.swap(true, Ordering::AcqRel) {
return true;
}
let weak_inner = Arc::downgrade(inner_arc);
let worker_scheduled = Arc::clone(&scheduled);
if thread::Builder::new()
.name("thingdb-flush".to_string())
.spawn(move || background_flush_worker(weak_inner, worker_scheduled))
.is_err()
{
scheduled.store(false, Ordering::Release);
return false;
}
true
}
fn background_flush_worker(inner_weak: Weak<Mutex<Inner>>, scheduled: Arc<AtomicBool>) {
loop {
let Some(inner_arc) = inner_weak.upgrade() else {
break;
};
let gate = match inner_arc.lock() {
Ok(inner) => Arc::clone(&inner.commit_gate),
Err(_) => break,
};
let Ok(_gate) = gate.lock() else {
break;
};
let Ok(mut inner) = inner_arc.lock() else {
break;
};
if inner.recovery_required || inner.pending_table.is_empty() {
break;
}
if let Err(error) = flush_table_locked(&mut inner, true, None) {
inner.recovery_required = true;
inner.diagnostics.recovery_required = true;
inner.diagnostics.last_error = Some(error.to_string());
break;
}
inner.diagnostics.automatic_flush_count =
inner.diagnostics.automatic_flush_count.saturating_add(1);
if inner.table_layers.len() >= inner.max_table_layers
&& let Err(error) = compact_tables_locked(&mut inner, true, None)
{
inner.recovery_required = true;
inner.diagnostics.recovery_required = true;
inner.diagnostics.last_error = Some(error.to_string());
break;
}
if inner.pending_table_bytes < inner.max_memtable_bytes {
break;
}
}
scheduled.store(false, Ordering::Release);
let reschedule = inner_weak
.upgrade()
.and_then(|inner_arc| {
inner_arc.lock().ok().map(|inner| {
!inner.recovery_required && inner.pending_table_bytes >= inner.max_memtable_bytes
})
})
.unwrap_or(false);
if reschedule
&& let Some(inner_arc) = inner_weak.upgrade()
&& !schedule_background_flush(&inner_arc, Arc::clone(&scheduled))
&& let Ok(mut inner) = inner_arc.lock()
{
inner.recovery_required = true;
inner.diagnostics.recovery_required = true;
inner.diagnostics.last_error =
Some("ThingDB could not restart its background flush worker".to_string());
}
}
fn request_has_fault(requests: &[CommitRequest], point: &'static str) -> Option<&'static str> {
requests
.iter()
.find_map(|request| (request.fault_point == Some(point)).then_some(point))
}
#[allow(clippy::too_many_lines)]
fn process_group(
inner: &Weak<Mutex<Inner>>,
mut requests: Vec<CommitRequest>,
wal_buffer: &mut Vec<u8>,
) {
let Some(inner_arc) = inner.upgrade() else {
for request in &mut *requests {
let _ = request
.response
.send(Err(Error::message("ThingDB writer is unavailable")));
}
return;
};
let gate = if let Ok(inner) = inner_arc.lock() {
Arc::clone(&inner.commit_gate)
} else {
for request in requests {
let _ = request
.response
.send(Err(Error::message("database lock poisoned")));
}
return;
};
let Ok(_gate) = gate.lock() else {
finish_group_with_error(&mut requests, "ThingDB commit gate poisoned");
return;
};
let Ok(mut inner) = inner_arc.lock() else {
drop(inner_arc);
for request in requests {
let _ = request
.response
.send(Err(Error::message("database lock poisoned")));
}
return;
};
let lock_held_started = Instant::now();
let group_size = requests.len() as u64;
inner.diagnostics.logical_commit_count = inner
.diagnostics
.logical_commit_count
.saturating_add(group_size);
inner.diagnostics.total_group_size = inner
.diagnostics
.total_group_size
.saturating_add(group_size);
inner.diagnostics.max_group_size = inner.diagnostics.max_group_size.max(group_size);
for request in &requests {
inner.diagnostics.queue_wait_duration_ns = inner
.diagnostics
.queue_wait_duration_ns
.saturating_add(elapsed_nanos(request.submitted_at.elapsed()));
}
if inner.recovery_required {
let message = "ThingDB requires reopen and recovery before writing";
inner.diagnostics.last_error = Some(message.to_string());
inner.diagnostics.lock_duration_ns = inner
.diagnostics
.lock_duration_ns
.saturating_add(elapsed_nanos(lock_held_started.elapsed()));
drop(inner);
drop(inner_arc);
finish_group_with_error(&mut requests, message);
return;
}
if !inner.in_memory
&& inner.max_memtable_bytes > 1
&& inner.pending_table_bytes >= inner.max_memtable_bytes.saturating_mul(2)
{
if let Err(error) = flush_table_locked(&mut inner, true, None) {
let message = error.to_string();
inner.recovery_required = true;
inner.diagnostics.recovery_required = true;
inner.diagnostics.last_error = Some(message.clone());
inner.diagnostics.lock_duration_ns = inner
.diagnostics
.lock_duration_ns
.saturating_add(elapsed_nanos(lock_held_started.elapsed()));
drop(inner);
drop(inner_arc);
finish_group_with_error(&mut requests, &message);
return;
}
inner.diagnostics.automatic_flush_count =
inner.diagnostics.automatic_flush_count.saturating_add(1);
}
let wal_start = if inner.in_memory {
0
} else if inner.wal.is_some() {
inner.diagnostics.journal_bytes
} else {
let message = "ThingDB WAL is unavailable";
inner.diagnostics.last_error = Some(message.to_string());
inner.diagnostics.lock_duration_ns = inner
.diagnostics
.lock_duration_ns
.saturating_add(elapsed_nanos(lock_held_started.elapsed()));
drop(inner);
drop(inner_arc);
finish_group_with_error(&mut requests, message);
return;
};
let (result, synced) = if inner.in_memory {
let result = execute_memory_group(&mut inner, &mut requests, group_size);
inner.diagnostics.lock_duration_ns = inner
.diagnostics
.lock_duration_ns
.saturating_add(elapsed_nanos(lock_held_started.elapsed()));
drop(inner);
result
} else {
let expected_sequence = inner.sequence.saturating_add(1);
let expected_generation = inner.state_generation;
let wal_io_lock = Arc::clone(&inner.wal_io_lock);
let wal_file = inner.wal.as_ref().map(Arc::clone);
let wal_sync_mode = inner.wal_sync_mode;
inner.diagnostics.lock_duration_ns = inner
.diagnostics
.lock_duration_ns
.saturating_add(elapsed_nanos(lock_held_started.elapsed()));
drop(inner);
execute_group(
&inner_arc,
&mut requests,
expected_sequence,
expected_generation,
wal_start,
wal_file,
wal_io_lock,
wal_sync_mode,
group_size,
wal_buffer,
)
};
let Ok(mut inner) = inner_arc.lock() else {
finish_group_with_error(&mut requests, "database lock poisoned");
return;
};
let post_lock_held_started = Instant::now();
if let Err(error) = &result {
inner.diagnostics.last_error = Some(error.to_string());
if synced {
inner.recovery_required = true;
inner.diagnostics.recovery_required = true;
}
}
inner.diagnostics.lock_duration_ns = inner
.diagnostics
.lock_duration_ns
.saturating_add(elapsed_nanos(post_lock_held_started.elapsed()));
drop(inner);
match result {
Ok(()) => {
for request in requests {
let _ = request.response.send(Ok(()));
}
},
Err(error) => finish_group_with_error(&mut requests, &error.to_string()),
}
}
fn execute_memory_group(
inner: &mut Inner,
requests: &mut [CommitRequest],
group_size: u64,
) -> (Result<()>, bool) {
let started = Instant::now();
for request in requests.iter_mut() {
for operation in std::mem::take(&mut request.operations) {
apply_operation(&mut inner.state, operation);
}
}
inner.sequence = inner.sequence.saturating_add(group_size);
inner.diagnostics.state_apply_duration_ns = inner
.diagnostics
.state_apply_duration_ns
.saturating_add(elapsed_nanos(started.elapsed()));
inner.diagnostics.journal_bytes = 0;
inner.diagnostics.frame_count = 0;
inner.diagnostics.wal_over_budget = false;
inner.diagnostics.memtable_bytes = 0;
inner.diagnostics.memtable_over_budget = false;
(Ok(()), false)
}
#[allow(clippy::too_many_arguments, clippy::too_many_lines)]
fn execute_group(
inner_arc: &Arc<Mutex<Inner>>,
requests: &mut [CommitRequest],
expected_sequence: u64,
expected_generation: u64,
wal_start: u64,
wal_file: Option<Arc<File>>,
wal_io_lock: Arc<Mutex<()>>,
wal_sync_mode: WalSyncMode,
group_size: u64,
wal_buffer: &mut Vec<u8>,
) -> (Result<()>, bool) {
let allocation_started = Instant::now();
let reserved_bytes = requests.iter().map(|request| request.encoded_bytes).sum();
wal_buffer.clear();
if wal_buffer.capacity() < reserved_bytes {
wal_buffer.reserve(reserved_bytes - wal_buffer.capacity());
}
let allocation_duration_ns = elapsed_nanos(allocation_started.elapsed());
let encode_started = Instant::now();
let mut next_sequence = expected_sequence;
let encode_result = (|| {
for request in requests.iter() {
encode_frame_into(wal_buffer, next_sequence, &request.operations)?;
next_sequence = next_sequence.saturating_add(1);
}
Ok::<(), Error>(())
})();
let encode_duration_ns = elapsed_nanos(encode_started.elapsed());
if let Ok(mut inner) = inner_arc.lock() {
inner.diagnostics.buffer_allocation_duration_ns = inner
.diagnostics
.buffer_allocation_duration_ns
.saturating_add(allocation_duration_ns);
inner.diagnostics.buffer_reserved_bytes = inner
.diagnostics
.buffer_reserved_bytes
.saturating_add(reserved_bytes as u64);
inner.diagnostics.encode_duration_ns = inner
.diagnostics
.encode_duration_ns
.saturating_add(encode_duration_ns);
inner.diagnostics.encode_outside_lock_duration_ns = inner
.diagnostics
.encode_outside_lock_duration_ns
.saturating_add(encode_duration_ns);
}
if let Err(error) = encode_result {
return (Err(error), false);
}
let Some(mut wal_file) = wal_file else {
return (Err(Error::message("ThingDB WAL is unavailable")), false);
};
let mut synced = false;
let mut appended = false;
let mut append_duration_ns = 0;
let mut sync_duration_ns = 0;
let mut wal_lock_wait_ns = 0;
let result: Result<()> = (|| {
if let Some(point) = request_has_fault(requests, "before-wal-append") {
maybe_fail(point, Some(point))?;
}
{
let Ok(mut inner) = inner_arc.lock() else {
return Err(Error::message("database lock poisoned"));
};
if inner.recovery_required
|| inner.sequence.saturating_add(1) != expected_sequence
|| inner.state_generation != expected_generation
{
inner.diagnostics.state_generation_conflict_count = inner
.diagnostics
.state_generation_conflict_count
.saturating_add(1);
return Err(Error::message(
"ThingDB commit state changed while preparing WAL frames",
));
}
}
{
let wal_lock_started = Instant::now();
let Ok(_wal_lock) = wal_io_lock.lock() else {
return Err(Error::message("ThingDB WAL lock poisoned"));
};
wal_lock_wait_ns = elapsed_nanos(wal_lock_started.elapsed());
let started = Instant::now();
wal_file.write_all(wal_buffer)?;
appended = true;
append_duration_ns = elapsed_nanos(started.elapsed());
if let Some(point) = request_has_fault(requests, "after-wal-write-before-sync") {
maybe_fail(point, Some(point))?;
}
let started = Instant::now();
sync_wal(&wal_file, wal_sync_mode)?;
synced = true;
sync_duration_ns = elapsed_nanos(started.elapsed());
}
if let Ok(mut inner) = inner_arc.lock() {
let journal_bytes = wal_start.saturating_add(wal_buffer.len() as u64);
inner.diagnostics.append_duration_ns = inner
.diagnostics
.append_duration_ns
.saturating_add(append_duration_ns);
inner.diagnostics.wal_bytes_appended = inner
.diagnostics
.wal_bytes_appended
.saturating_add(wal_buffer.len() as u64);
inner.diagnostics.journal_bytes = journal_bytes;
inner.diagnostics.wal_over_budget = journal_bytes > inner.max_journaling_size;
if synced {
inner.diagnostics.physical_sync_count =
inner.diagnostics.physical_sync_count.saturating_add(1);
inner.diagnostics.sync_duration_ns = inner
.diagnostics
.sync_duration_ns
.saturating_add(sync_duration_ns);
}
inner.diagnostics.wal_lock_wait_duration_ns = inner
.diagnostics
.wal_lock_wait_duration_ns
.saturating_add(wal_lock_wait_ns);
inner.diagnostics.wal_lock_held_duration_ns = inner
.diagnostics
.wal_lock_held_duration_ns
.saturating_add(append_duration_ns.saturating_add(sync_duration_ns));
}
if let Some(point) = request_has_fault(requests, "after-wal-sync-before-state-apply") {
maybe_fail(point, Some(point))?;
}
let Ok(mut inner) = inner_arc.lock() else {
return Err(Error::message("database lock poisoned"));
};
if inner.recovery_required
|| inner.sequence.saturating_add(1) != expected_sequence
|| inner.state_generation != expected_generation
{
inner.diagnostics.state_generation_conflict_count = inner
.diagnostics
.state_generation_conflict_count
.saturating_add(1);
return Err(Error::message(
"ThingDB commit state changed before state application",
));
}
let started = Instant::now();
let inner = &mut *inner;
for request in requests.iter_mut() {
for operation in std::mem::take(&mut request.operations) {
apply_operation_with_pending(
&mut inner.state,
&mut inner.pending_table,
&mut inner.pending_table_bytes,
operation,
);
}
}
inner.diagnostics.state_apply_duration_ns = inner
.diagnostics
.state_apply_duration_ns
.saturating_add(elapsed_nanos(started.elapsed()));
inner.sequence = next_sequence.saturating_sub(1);
inner.state_generation = inner.state_generation.saturating_add(1);
inner.diagnostics.frame_count = inner.diagnostics.frame_count.saturating_add(group_size);
inner.diagnostics.memtable_bytes = inner.pending_table_bytes;
inner.diagnostics.memtable_over_budget =
inner.pending_table_bytes >= inner.max_memtable_bytes;
let wal_over_budget = inner.max_journaling_size > 0
&& inner.diagnostics.journal_bytes >= inner.max_journaling_size;
if inner.pending_table_bytes >= inner.max_memtable_bytes || wal_over_budget {
let scheduled = Arc::clone(&inner.flush_scheduled);
let synchronous_flush = inner.max_memtable_bytes <= 1
|| request_has_fault(requests, "before-table-write").is_some();
if synchronous_flush {
flush_table_locked(
inner,
true,
request_has_fault(requests, "before-table-write"),
)?;
inner.diagnostics.automatic_flush_count =
inner.diagnostics.automatic_flush_count.saturating_add(1);
if inner.table_layers.len() >= inner.max_table_layers {
compact_tables_locked(inner, true, current_fault_point())?;
}
} else if !schedule_background_flush(inner_arc, scheduled) {
inner.recovery_required = true;
inner.diagnostics.recovery_required = true;
inner.diagnostics.last_error =
Some("ThingDB could not start its background flush worker".to_string());
return Err(Error::message(
"ThingDB could not start its background flush worker",
));
}
}
Ok(())
})();
if result.is_err() && !synced && appended {
if let Ok(_wal_lock) = wal_io_lock.lock()
&& wal_file.set_len(wal_start).is_ok()
{
let _ = wal_file.seek(SeekFrom::End(0));
if let Ok(mut inner) = inner_arc.lock() {
inner.diagnostics.journal_bytes = wal_start;
}
} else if let Ok(mut inner) = inner_arc.lock() {
inner.diagnostics.truncation_failure_count =
inner.diagnostics.truncation_failure_count.saturating_add(1);
}
}
(result, synced)
}
fn finish_group_with_error(requests: &mut [CommitRequest], message: &str) {
for request in requests.iter_mut() {
let _ = request.response.send(Err(Error::message(message)));
}
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Entry {
pub key: Vec<u8>,
pub value: Vec<u8>,
}
pub struct Iter {
entries: std::vec::IntoIter<Entry>,
error: Option<Error>,
}
struct ScanBounds<'a> {
prefix: Option<&'a [u8]>,
start: Option<(Vec<u8>, bool)>,
end: Option<(Vec<u8>, bool)>,
offset: usize,
limit: Option<usize>,
}
impl Iter {
pub fn error(&self) -> Option<&Error> {
self.error.as_ref()
}
pub fn into_result(self) -> Result<Vec<Entry>> {
if let Some(error) = self.error {
return Err(error);
}
Ok(self.entries.collect())
}
}
#[derive(Clone)]
pub struct Snapshot {
state: Arc<BTreeMap<Vec<u8>, Vec<u8>>>,
}
impl Database {
fn update_ram_diagnostics(&self, update: impl FnOnce(&mut RamDiagnostics)) {
if self.ram_keyspaces.is_some()
&& let Ok(mut diagnostics) = self.ram_diagnostics.lock()
{
update(&mut diagnostics);
}
}
fn record_ram_lookup_timing(
&self,
lock_wait: u64,
lock_held: u64,
lookup: u64,
clone: u64,
acquire: u64,
) {
self.record_ram_lookup_batch_timing(1, lock_wait, lock_held, lookup, clone, acquire);
}
fn record_ram_lookup_batch_timing(
&self,
lookup_count: u64,
lock_wait: u64,
lock_held: u64,
lookup: u64,
clone: u64,
acquire: u64,
) {
if self.ram_keyspaces.is_none() {
return;
}
self.ram_hot_diagnostics
.lookup_count
.fetch_add(lookup_count, Ordering::Relaxed);
RamHotDiagnostics::add(&self.ram_hot_diagnostics.lock_wait_duration_ns, lock_wait);
RamHotDiagnostics::add(&self.ram_hot_diagnostics.lock_held_duration_ns, lock_held);
RamHotDiagnostics::add(&self.ram_hot_diagnostics.lookup_duration_ns, lookup);
RamHotDiagnostics::add(&self.ram_hot_diagnostics.value_clone_duration_ns, clone);
RamHotDiagnostics::add(&self.ram_hot_diagnostics.value_acquire_duration_ns, acquire);
}
fn record_ram_mutation_timing(&self, operation_count: u64, duration_ns: u64) {
if self.ram_keyspaces.is_some() {
RamHotDiagnostics::add(&self.ram_hot_diagnostics.mutation_count, operation_count);
RamHotDiagnostics::add(&self.ram_hot_diagnostics.mutation_duration_ns, duration_ns);
}
}
#[cfg(feature = "benchmark")]
fn commit_ram_rcu_batch(&self, batch: Vec<BatchOperation>) -> Result<()> {
let started = Instant::now();
let rcu = self
.ram_rcu_keyspaces
.as_ref()
.ok_or_else(|| Error::message("ThingDB RCU state is unavailable"))?;
for operation in &batch {
validate_memory_batch_operation(operation)?;
}
let operation_count = batch.len() as u64;
let current = rcu.load_full();
let mut next = current.as_ref().clone();
for operation in batch {
let keyspace = next
.entry(Arc::clone(&operation.keyspace))
.or_insert_with(|| Arc::new(BTreeMap::new()));
let keyspace = Arc::make_mut(keyspace);
match operation.value {
Some(value) => {
keyspace.insert(operation.key, Arc::new(value));
},
None => {
keyspace.remove(&operation.key);
},
}
}
rcu.store(Arc::new(next));
let elapsed = elapsed_nanos(started.elapsed());
self.record_ram_mutation_timing(operation_count, elapsed);
self.ram_logical_commit_count
.fetch_add(1, Ordering::Relaxed);
self.ram_total_group_size.fetch_add(1, Ordering::Relaxed);
self.ram_state_apply_duration_ns
.fetch_add(elapsed, Ordering::Relaxed);
Ok(())
}
pub fn in_memory() -> Result<Self> {
let commit_gate = Arc::new(Mutex::new(()));
let ram_diagnostics = Arc::new(Mutex::new(RamDiagnostics::default()));
let ram_hot_diagnostics = Arc::new(RamHotDiagnostics::default());
let ram_logical_commit_count = Arc::new(AtomicU64::new(0));
let ram_total_group_size = Arc::new(AtomicU64::new(0));
let ram_state_apply_duration_ns = Arc::new(AtomicU64::new(0));
let table_block_cache = Arc::new(TableBlockCache::default());
let inner = Arc::new(Mutex::new(Inner {
path: PathBuf::new(),
wal: None,
lock: None,
in_memory: true,
state: BTreeMap::new(),
sequence: 0,
table_sequence: 0,
table_files: Vec::new(),
table_layers: Vec::new(),
pending_table: BTreeMap::new(),
pending_table_bytes: 0,
max_journaling_size: 0,
max_memtable_bytes: 0,
max_table_layers: 0,
diagnostics: WalDiagnostics::default(),
table_block_cache,
recovery_required: false,
commit_gate: Arc::clone(&commit_gate),
wal_io_lock: Arc::new(Mutex::new(())),
state_generation: 0,
wal_sync_mode: WalSyncMode::Data,
flush_scheduled: Arc::new(AtomicBool::new(false)),
}));
let writer = WriterCoordinator::new(Arc::downgrade(&inner))?;
Ok(Self {
inner,
ram_keyspaces: Some(Arc::new(RwLock::new(HashMap::new()))),
#[cfg(feature = "benchmark")]
ram_rcu_keyspaces: None,
ram_diagnostics,
ram_hot_diagnostics,
ram_logical_commit_count,
ram_total_group_size,
ram_state_apply_duration_ns,
writer,
commit_gate,
})
}
#[cfg(feature = "benchmark")]
#[doc(hidden)]
pub fn in_memory_with_rcu() -> Result<Self> {
let mut database = Self::in_memory()?;
database.ram_rcu_keyspaces = Some(Arc::new(ArcSwap::from_pointee(HashMap::new())));
Ok(database)
}
pub fn builder(path: impl AsRef<Path>) -> DatabaseBuilder {
DatabaseBuilder {
path: path.as_ref().to_path_buf(),
max_journaling_size: 32 * 1024 * 1024,
max_memtable_bytes: 64 * 1024 * 1024,
max_table_layers: 8,
wal_sync_mode: WalSyncMode::Data,
}
}
pub fn open(path: impl AsRef<Path>) -> Result<Self> {
Self::builder(path).open()
}
pub fn keyspace(&self, name: &str, _options: KeyspaceCreateOptions) -> Result<Keyspace> {
if name.is_empty() || name.as_bytes().contains(&0) {
return Err(Error::message(
"keyspace names must be non-empty and contain no NUL",
));
}
Ok(Keyspace {
db: self.clone(),
name: Arc::from(name.to_owned()),
namespace: Arc::from(namespace(name)),
})
}
pub fn batch(&self) -> Batch {
self.batch_with_capacity(0)
}
pub fn batch_with_capacity(&self, capacity: usize) -> Batch {
Batch {
db: self.clone(),
memory_mode: self.ram_keyspaces.is_some(),
operations: Vec::with_capacity(capacity),
}
}
pub fn persist(&self, mode: PersistMode) -> Result<()> {
if self
.inner
.lock()
.map_err(|_| Error::message("database lock poisoned"))?
.in_memory
{
let _ = mode;
return Err(Error::message(
"ThingDB in-memory databases do not support persistence",
));
}
match mode {
PersistMode::SyncAll => self.flush_table(true),
}
}
pub fn compact(&self) -> Result<()> {
if self
.inner
.lock()
.map_err(|_| Error::message("database lock poisoned"))?
.in_memory
{
return Err(Error::message(
"ThingDB in-memory databases do not support compaction",
));
}
self.compact_tables(true)
}
pub fn snapshot(&self) -> Result<Snapshot> {
let started = Instant::now();
#[cfg(feature = "benchmark")]
if let Some(rcu) = &self.ram_rcu_keyspaces {
let generation = rcu.load_full();
let mut state = BTreeMap::new();
for (name, entries) in generation.iter() {
let namespace = namespace(name);
for (key, value) in entries.iter() {
let mut physical = namespace.clone();
physical.extend_from_slice(key);
state.insert(physical, value.as_ref().clone());
}
}
let elapsed = elapsed_nanos(started.elapsed());
self.update_ram_diagnostics(|diagnostics| {
diagnostics.snapshot_count = diagnostics.snapshot_count.saturating_add(1);
diagnostics.snapshot_duration_ns =
diagnostics.snapshot_duration_ns.saturating_add(elapsed);
});
return Ok(Snapshot {
state: Arc::new(state),
});
}
let mut inner = self
.inner
.lock()
.map_err(|_| Error::message("database lock poisoned"))?;
if inner.in_memory {
drop(inner);
let keyspaces = self
.ram_keyspaces
.as_ref()
.ok_or_else(|| Error::message("ThingDB RAM state is unavailable"))?
.read()
.map_err(|_| Error::message("ThingDB RAM state lock poisoned"))?;
let mut state = BTreeMap::new();
for (name, entries) in keyspaces.iter() {
let namespace = namespace(name);
for (key, value) in entries {
let mut physical = namespace.clone();
physical.extend_from_slice(key);
state.insert(physical, value.as_ref().clone());
}
}
drop(keyspaces);
let elapsed = elapsed_nanos(started.elapsed());
self.update_ram_diagnostics(|diagnostics| {
diagnostics.snapshot_count = diagnostics.snapshot_count.saturating_add(1);
diagnostics.snapshot_duration_ns =
diagnostics.snapshot_duration_ns.saturating_add(elapsed);
});
return Ok(Snapshot {
state: Arc::new(state),
});
}
Ok(Snapshot {
state: Arc::new(inner.materialize_state()?),
})
}
pub fn journal_disk_space(&self) -> Result<u64> {
let inner = self
.inner
.lock()
.map_err(|_| Error::message("database lock poisoned"))?;
if inner.in_memory {
Ok(0)
} else {
inner
.wal
.as_ref()
.ok_or_else(|| Error::message("ThingDB WAL is unavailable"))?
.metadata()
.map(|metadata| metadata.len())
.map_err(Error::from)
}
}
pub fn journal_count(&self) -> usize {
self.inner
.lock()
.map(|inner| usize::from(!inner.in_memory))
.unwrap_or_default()
}
pub fn wal_diagnostics(&self) -> Result<WalDiagnostics> {
let inner = self
.inner
.lock()
.map_err(|_| Error::message("database lock poisoned"))?;
let mut diagnostics = inner.diagnostics.clone();
let block_cache = inner.table_block_cache.diagnostics();
diagnostics.table_block_cache_capacity_bytes =
u64::try_from(block_cache.capacity_bytes).unwrap_or(u64::MAX);
diagnostics.table_block_cache_resident_bytes =
u64::try_from(block_cache.resident_bytes).unwrap_or(u64::MAX);
diagnostics.table_block_cache_entries =
u64::try_from(block_cache.entries).unwrap_or(u64::MAX);
diagnostics.table_block_cache_hits = block_cache.hits;
diagnostics.table_block_cache_misses = block_cache.misses;
diagnostics.table_block_cache_decoded_hits = block_cache.decoded_hits;
diagnostics.table_block_cache_decoded_misses = block_cache.decoded_misses;
diagnostics.table_block_cache_evictions = block_cache.evictions;
if inner.in_memory {
diagnostics.logical_commit_count =
self.ram_logical_commit_count.load(Ordering::Relaxed);
diagnostics.total_group_size = self.ram_total_group_size.load(Ordering::Relaxed);
diagnostics.max_group_size = u64::from(diagnostics.logical_commit_count > 0);
diagnostics.state_apply_duration_ns =
self.ram_state_apply_duration_ns.load(Ordering::Relaxed);
}
diagnostics.journal_bytes = if inner.in_memory {
0
} else {
inner
.wal
.as_ref()
.ok_or_else(|| Error::message("ThingDB WAL is unavailable"))?
.metadata()
.map_err(Error::from)?
.len()
};
Ok(diagnostics)
}
pub fn ram_diagnostics(&self) -> Result<RamDiagnostics> {
if self.ram_keyspaces.is_some() {
let mut diagnostics = self
.ram_diagnostics
.lock()
.map_err(|_| Error::message("RAM diagnostics lock poisoned"))?
.clone();
self.ram_hot_diagnostics.snapshot_into(&mut diagnostics);
Ok(diagnostics)
} else {
Ok(RamDiagnostics::default())
}
}
pub fn record_ram_deserialization(&self, duration_ns: u64) {
if self.ram_keyspaces.is_some() {
RamHotDiagnostics::add(
&self.ram_hot_diagnostics.deserialization_duration_ns,
duration_ns,
);
}
}
pub fn record_ram_search(&self, duration_ns: u64) {
self.update_ram_diagnostics(|diagnostics| {
diagnostics.search_count = diagnostics.search_count.saturating_add(1);
diagnostics.search_duration_ns =
diagnostics.search_duration_ns.saturating_add(duration_ns);
});
}
pub fn record_ram_serialization(&self, duration_ns: u64) {
if self.ram_keyspaces.is_some() {
self.ram_hot_diagnostics
.serialization_count
.fetch_add(1, Ordering::Relaxed);
RamHotDiagnostics::add(
&self.ram_hot_diagnostics.serialization_duration_ns,
duration_ns,
);
}
}
pub fn record_ram_search_index(&self, duration_ns: u64) {
self.update_ram_diagnostics(|diagnostics| {
diagnostics.search_index_count = diagnostics.search_index_count.saturating_add(1);
diagnostics.search_index_duration_ns = diagnostics
.search_index_duration_ns
.saturating_add(duration_ns);
});
}
fn flush_table(&self, sync: bool) -> Result<()> {
let _gate = self
.commit_gate
.lock()
.map_err(|_| Error::message("ThingDB commit gate poisoned"))?;
let mut inner = self
.inner
.lock()
.map_err(|_| Error::message("database lock poisoned"))?;
flush_table_locked(&mut inner, sync, current_fault_point())
}
fn commit_batch(&self, batch: Vec<BatchOperation>) -> Result<()> {
if batch.is_empty() {
return Ok(());
}
#[cfg(feature = "benchmark")]
if self.ram_rcu_keyspaces.is_some() {
return self.commit_ram_rcu_batch(batch);
}
if self.ram_keyspaces.is_some() {
let started = Instant::now();
let ram_keyspaces = self
.ram_keyspaces
.as_ref()
.ok_or_else(|| Error::message("ThingDB RAM state is unavailable"))?;
let mut keyspaces = ram_keyspaces
.write()
.map_err(|_| Error::message("ThingDB RAM state lock poisoned"))?;
for operation in &batch {
validate_memory_batch_operation(operation)?;
}
let operation_count = batch.len() as u64;
for operation in batch {
apply_memory_batch_operation(&mut keyspaces, operation);
}
let elapsed = elapsed_nanos(started.elapsed());
drop(keyspaces);
self.record_ram_mutation_timing(operation_count, elapsed);
self.ram_logical_commit_count
.fetch_add(1, Ordering::Relaxed);
self.ram_total_group_size.fetch_add(1, Ordering::Relaxed);
self.ram_state_apply_duration_ns
.fetch_add(elapsed, Ordering::Relaxed);
return Ok(());
}
let operations = batch
.into_iter()
.map(|operation| match operation.value {
Some(value) => Operation::Put {
key: operation.key,
value,
},
None => Operation::Delete { key: operation.key },
})
.collect();
self.commit_operations(operations)
}
fn commit_operations(&self, operations: Vec<Operation>) -> Result<()> {
if operations.is_empty() {
return Ok(());
}
if self.ram_keyspaces.is_some() {
let started = Instant::now();
let ram_keyspaces = self
.ram_keyspaces
.as_ref()
.ok_or_else(|| Error::message("ThingDB RAM state is unavailable"))?;
let mut keyspaces = ram_keyspaces
.write()
.map_err(|_| Error::message("ThingDB RAM state lock poisoned"))?;
for operation in &operations {
validate_memory_operation(operation)?;
}
let operation_count = operations.len() as u64;
for operation in operations {
apply_memory_operation(&mut keyspaces, operation)?;
}
let elapsed = elapsed_nanos(started.elapsed());
drop(keyspaces);
self.record_ram_mutation_timing(operation_count, elapsed);
self.ram_logical_commit_count
.fetch_add(1, Ordering::Relaxed);
self.ram_total_group_size.fetch_add(1, Ordering::Relaxed);
self.ram_state_apply_duration_ns
.fetch_add(elapsed_nanos(started.elapsed()), Ordering::Relaxed);
return Ok(());
}
let (response, result) = mpsc::channel();
let encoded_bytes = encoded_frame_capacity(&operations);
let request = CommitRequest {
encoded_bytes,
operations,
submitted_at: Instant::now(),
fault_point: current_fault_point(),
response,
};
let sender = self
.writer
.sender
.lock()
.map_err(|_| Error::message("ThingDB writer state poisoned"))?
.clone()
.ok_or_else(|| Error::message("ThingDB writer is unavailable"))?;
sender
.send(request)
.map_err(|_| Error::message("ThingDB writer is unavailable"))?;
result
.recv()
.map_err(|_| Error::message("ThingDB writer stopped unexpectedly"))?
}
}
fn flush_table_locked(
inner: &mut Inner,
sync: bool,
fault_point: Option<&'static str>,
) -> Result<()> {
let started = Instant::now();
if inner.recovery_required {
return Err(Error::message(
"ThingDB requires reopen and recovery before writing",
));
}
if inner.pending_table.is_empty() {
let _wal_lock = inner
.wal_io_lock
.lock()
.map_err(|_| Error::message("ThingDB WAL lock poisoned"))?;
let wal = inner
.wal
.as_mut()
.ok_or_else(|| Error::message("ThingDB WAL is unavailable"))?;
sync_wal(wal, inner.wal_sync_mode)?;
return Ok(());
}
let updates = std::mem::take(&mut inner.pending_table);
let update_bytes = inner.pending_table_bytes;
let result = (|| {
let _wal_lock = inner
.wal_io_lock
.lock()
.map_err(|_| Error::message("ThingDB WAL lock poisoned"))?;
let next_sequence = inner.sequence;
let table_name = format!(
"table-{next_sequence:020}-{:04}.tdb",
inner.table_files.len()
);
let table_path = inner.path.join(&table_name);
let temp_path = inner.path.join(format!(".{table_name}.tmp"));
maybe_fail("before-table-write", fault_point)?;
write_table(&temp_path, next_sequence, &updates, sync)?;
inner.diagnostics.table_bytes_written = inner
.diagnostics
.table_bytes_written
.saturating_add(fs::metadata(&temp_path)?.len());
maybe_fail("after-table-sync-before-rename", fault_point)?;
maybe_fail("before-table-rename", fault_point)?;
fs::rename(&temp_path, &table_path)?;
maybe_fail("after-table-rename-before-manifest", fault_point)?;
let mut table_files = inner.table_files.clone();
table_files.push(table_name.clone());
let manifest = Manifest {
format_version: FORMAT_VERSION,
table_file: Some(table_name),
table_files: table_files.clone(),
table_sequence: next_sequence,
};
maybe_fail("before-manifest-write", fault_point)?;
write_manifest(&inner.path, &manifest, sync)?;
maybe_fail("after-manifest-rename-before-wal-truncate", fault_point)?;
inner.table_files = table_files;
let (_, entries, is_v2, blocks) = read_table_metadata(&table_path)?;
inner.table_layers.push(TableLayer {
file: Arc::new(File::open(&table_path)?),
path: table_path,
entries: Arc::new(if blocks.is_empty() {
OnceLock::from(Arc::new(entries))
} else {
OnceLock::new()
}),
blocks: Arc::new(blocks),
block_cache: Arc::clone(&inner.table_block_cache),
is_v2,
});
inner.diagnostics.table_layer_count = inner.table_layers.len() as u64;
inner.table_sequence = next_sequence;
inner.state.clear();
inner.pending_table_bytes = 0;
{
let wal = inner
.wal
.as_mut()
.ok_or_else(|| Error::message("ThingDB WAL is unavailable"))?;
wal.set_len(0)?;
if sync {
sync_wal(wal, inner.wal_sync_mode)?;
}
inner.diagnostics.journal_bytes = 0;
}
inner.diagnostics.frame_count = 0;
inner.diagnostics.memtable_bytes = 0;
inner.diagnostics.memtable_over_budget = false;
inner.diagnostics.flush_count = inner.diagnostics.flush_count.saturating_add(1);
Ok(())
})();
if result.is_err() {
inner.pending_table = updates;
inner.pending_table_bytes = update_bytes;
}
inner.state_generation = inner.state_generation.saturating_add(1);
inner.diagnostics.flush_duration_ns = inner
.diagnostics
.flush_duration_ns
.saturating_add(elapsed_nanos(started.elapsed()));
result
}
impl Database {
fn compact_tables(&self, sync: bool) -> Result<()> {
let _gate = self
.commit_gate
.lock()
.map_err(|_| Error::message("ThingDB commit gate poisoned"))?;
let mut inner = self
.inner
.lock()
.map_err(|_| Error::message("database lock poisoned"))?;
compact_tables_locked(&mut inner, sync, current_fault_point())
}
}
#[allow(clippy::too_many_lines)]
fn compact_tables_locked(
inner: &mut Inner,
sync: bool,
fault_point: Option<&'static str>,
) -> Result<()> {
let started = Instant::now();
if inner.recovery_required {
return Err(Error::message(
"ThingDB requires reopen and recovery before writing",
));
}
{
let _wal_lock = inner
.wal_io_lock
.lock()
.map_err(|_| Error::message("ThingDB WAL lock poisoned"))?;
let wal = inner
.wal
.as_mut()
.ok_or_else(|| Error::message("ThingDB WAL is unavailable"))?;
sync_wal(wal, inner.wal_sync_mode)?;
}
let next_sequence = inner.sequence;
let table_name = format!("table-{next_sequence:020}-compact.tdb");
let table_path = inner.path.join(&table_name);
let temp_path = inner.path.join(format!(".{table_name}.tmp"));
let mut input_bytes: u64 = 0;
for layer in &inner.table_layers {
input_bytes = input_bytes.saturating_add(
layer
.loaded_entries()?
.iter()
.map(|entry| entry.length)
.sum::<u64>(),
);
}
let entries: BTreeMap<_, _> = inner
.materialize_state()?
.into_iter()
.map(|(key, value)| (key, Some(value)))
.collect();
maybe_fail("before-table-write", fault_point)?;
write_table(&temp_path, next_sequence, &entries, sync)?;
inner.diagnostics.table_bytes_written = inner
.diagnostics
.table_bytes_written
.saturating_add(fs::metadata(&temp_path)?.len());
maybe_fail("after-table-sync-before-rename", fault_point)?;
maybe_fail("before-table-rename", fault_point)?;
fs::rename(&temp_path, &table_path)?;
maybe_fail("after-table-rename-before-manifest", fault_point)?;
let manifest = Manifest {
format_version: FORMAT_VERSION,
table_file: Some(table_name.clone()),
table_files: vec![table_name.clone()],
table_sequence: next_sequence,
};
maybe_fail("before-manifest-write", fault_point)?;
write_manifest(&inner.path, &manifest, sync)?;
maybe_fail("after-manifest-rename-before-wal-truncate", fault_point)?;
for old_table in &inner.table_files {
if old_table != &table_name {
let _ = fs::remove_file(inner.path.join(old_table));
}
}
inner.table_files = vec![table_name];
let (_, entries, is_v2, blocks) = read_table_metadata(&table_path)?;
inner.table_layers = vec![TableLayer {
file: Arc::new(File::open(&table_path)?),
path: table_path.clone(),
entries: Arc::new(if blocks.is_empty() {
OnceLock::from(Arc::new(entries))
} else {
OnceLock::new()
}),
blocks: Arc::new(blocks),
block_cache: Arc::clone(&inner.table_block_cache),
is_v2,
}];
inner.diagnostics.table_layer_count = 1;
inner.table_sequence = next_sequence;
inner.state.clear();
inner.pending_table.clear();
inner.pending_table_bytes = 0;
inner.state_generation = inner.state_generation.saturating_add(1);
{
let wal = inner
.wal
.as_mut()
.ok_or_else(|| Error::message("ThingDB WAL is unavailable"))?;
wal.set_len(0)?;
if sync {
sync_wal(wal, inner.wal_sync_mode)?;
}
inner.diagnostics.journal_bytes = 0;
}
inner.diagnostics.frame_count = 0;
inner.diagnostics.memtable_bytes = 0;
inner.diagnostics.memtable_over_budget = false;
inner.diagnostics.compaction_count = inner.diagnostics.compaction_count.saturating_add(1);
inner.diagnostics.compaction_duration_ns = inner
.diagnostics
.compaction_duration_ns
.saturating_add(elapsed_nanos(started.elapsed()));
inner.diagnostics.compaction_input_bytes = input_bytes;
inner.diagnostics.compaction_output_bytes = fs::metadata(&table_path)?.len();
Ok(())
}
impl DatabaseBuilder {
#[cfg(feature = "benchmark")]
#[doc(hidden)]
pub fn benchmark_common_fsync(mut self) -> Self {
self.wal_sync_mode = WalSyncMode::All;
self
}
pub fn max_journaling_size(mut self, bytes: u64) -> Self {
self.max_journaling_size = bytes;
self
}
pub fn max_memtable_bytes(mut self, bytes: u64) -> Self {
self.max_memtable_bytes = bytes.max(1);
self
}
pub fn max_table_layers(mut self, layers: usize) -> Self {
self.max_table_layers = layers.max(1);
self
}
pub fn open(self) -> Result<Database> {
fs::create_dir_all(&self.path)?;
let lock_path = self.path.join(LOCK_FILE);
let lock = OpenOptions::new()
.write(true)
.create_new(true)
.open(&lock_path)
.map_err(|error| {
if error.kind() == ErrorKind::AlreadyExists {
Error::message(format!("database is locked: {}", self.path.display()))
} else {
error.into()
}
})?;
let result = Self::open_locked(self, lock);
if result.is_err() {
let _ = fs::remove_file(lock_path);
}
result
}
#[allow(clippy::too_many_lines)]
fn open_locked(self, lock: File) -> Result<Database> {
cleanup_temporary_files(&self.path)?;
let manifest_path = self.path.join(MANIFEST_FILE);
let manifest = if manifest_path.exists() {
let manifest: Manifest = serde_json::from_slice(&fs::read(&manifest_path)?)?;
if manifest.format_version != FORMAT_VERSION {
return Err(Error::message(format!(
"unsupported ThingDB format version {}",
manifest.format_version
)));
}
validate_manifest(&manifest)?;
Some(manifest)
} else {
None
};
let mut state = BTreeMap::new();
let mut table_sequence = 0;
let mut table_layers = Vec::new();
let table_block_cache = Arc::new(TableBlockCache::default());
let mut table_open_duration_ns: u64 = 0;
let table_files = manifest
.as_ref()
.map(|manifest| {
if manifest.table_files.is_empty() {
manifest.table_file.iter().cloned().collect::<Vec<_>>()
} else {
manifest.table_files.clone()
}
})
.unwrap_or_default();
if let Some(manifest) = &manifest {
let mut previous_sequence = 0;
for table_file in &table_files {
let table_path = self.path.join(table_file);
if !table_path.is_file() {
return Err(Error::message(format!(
"ThingDB manifest references missing table: {table_file}"
)));
}
let (sequence, entries, is_v2, blocks) = read_table_metadata(&table_path)?;
if sequence > manifest.table_sequence {
return Err(Error::message("table sequence exceeds manifest sequence"));
}
if sequence < previous_sequence {
return Err(Error::message(
"ThingDB table layers are not in sequence order",
));
}
previous_sequence = sequence;
let open_started = Instant::now();
let file = File::open(&table_path)?;
table_open_duration_ns =
table_open_duration_ns.saturating_add(elapsed_nanos(open_started.elapsed()));
table_layers.push(TableLayer {
file: Arc::new(file),
path: table_path,
entries: Arc::new(if blocks.is_empty() {
OnceLock::from(Arc::new(entries))
} else {
OnceLock::new()
}),
blocks: Arc::new(blocks),
block_cache: Arc::clone(&table_block_cache),
is_v2,
});
}
table_sequence = manifest.table_sequence;
}
let wal_path = self.path.join(WAL_FILE);
let mut wal = OpenOptions::new()
.create(true)
.read(true)
.append(true)
.open(&wal_path)?;
let recovery_started = Instant::now();
let (last_sequence, valid_offset, frame_count) =
replay_wal(&mut wal, table_sequence, &mut state)?;
let recovery_duration_ns = elapsed_nanos(recovery_started.elapsed());
let wal_len = wal.metadata()?.len();
if valid_offset < wal_len {
wal.set_len(valid_offset)?;
wal.seek(SeekFrom::End(0))?;
}
let journal_bytes = wal.metadata()?.len();
let sequence = last_sequence.max(table_sequence);
let table_layer_count = table_layers.len() as u64;
if manifest.is_none() {
write_manifest(
&self.path,
&Manifest {
format_version: FORMAT_VERSION,
table_file: None,
table_files: Vec::new(),
table_sequence: 0,
},
true,
)?;
}
let commit_gate = Arc::new(Mutex::new(()));
let ram_diagnostics = Arc::new(Mutex::new(RamDiagnostics::default()));
let ram_hot_diagnostics = Arc::new(RamHotDiagnostics::default());
let inner = Arc::new(Mutex::new(Inner {
path: self.path,
wal: Some(Arc::new(wal)),
lock: Some(lock),
in_memory: false,
state,
sequence,
table_sequence,
table_files,
table_layers,
pending_table: BTreeMap::new(),
pending_table_bytes: 0,
max_journaling_size: self.max_journaling_size,
max_memtable_bytes: self.max_memtable_bytes,
max_table_layers: self.max_table_layers,
diagnostics: WalDiagnostics {
journal_bytes,
frame_count,
recovery_bytes: valid_offset,
recovery_duration_ns,
table_layer_count,
table_open_duration_ns,
..WalDiagnostics::default()
},
table_block_cache,
recovery_required: false,
commit_gate: Arc::clone(&commit_gate),
wal_io_lock: Arc::new(Mutex::new(())),
state_generation: 0,
wal_sync_mode: self.wal_sync_mode,
flush_scheduled: Arc::new(AtomicBool::new(false)),
}));
let writer = WriterCoordinator::new(Arc::downgrade(&inner))?;
Ok(Database {
inner,
ram_keyspaces: None,
#[cfg(feature = "benchmark")]
ram_rcu_keyspaces: None,
ram_diagnostics,
ram_hot_diagnostics,
ram_logical_commit_count: Arc::new(AtomicU64::new(0)),
ram_total_group_size: Arc::new(AtomicU64::new(0)),
ram_state_apply_duration_ns: Arc::new(AtomicU64::new(0)),
writer,
commit_gate,
})
}
}
impl Drop for Inner {
fn drop(&mut self) {
if let Some(lock) = self.lock.as_ref() {
let _ = lock.sync_all();
let _ = fs::remove_file(self.path.join(LOCK_FILE));
}
}
}
impl Database {
fn count_durable_namespace(&self, namespace: &[u8], prefix: Option<&[u8]>) -> Result<usize> {
let lock_started = Instant::now();
let mut inner = self
.inner
.lock()
.map_err(|_| Error::message("database lock poisoned"))?;
if inner.in_memory {
return Err(Error::message(
"ThingDB RAM keyspace count should use its in-memory map",
));
}
let lock_wait_ns = elapsed_nanos(lock_started.elapsed());
let lock_held_started = Instant::now();
let mut capture_metrics = DurableScanPageCaptureMetrics::default();
let snapshot = capture_durable_table_page(
&inner,
namespace,
prefix,
None,
None,
lock_wait_ns,
elapsed_nanos(lock_held_started.elapsed()),
true,
&mut capture_metrics,
)
.ok_or_else(|| Error::message("ThingDB durable count requires a durable database"))?;
capture_metrics.record(&mut inner.diagnostics);
drop(inner);
let mut count = 0usize;
iter_durable_table_page(
self,
namespace,
prefix,
None,
None,
0,
usize::MAX,
snapshot,
Some(&mut count),
)
.into_result()?;
Ok(count)
}
#[allow(clippy::too_many_lines)]
fn get_many_durable_values(&self, keys: &[Vec<u8>]) -> Result<Vec<Option<Vec<u8>>>> {
let lock_started = Instant::now();
let (mut values, unresolved, table_layers) = {
let mut inner = self
.inner
.lock()
.map_err(|_| Error::message("database lock poisoned"))?;
if inner.in_memory {
return Err(Error::message(
"durable multi-get called for an in-memory database",
));
}
let lock_wait = elapsed_nanos(lock_started.elapsed());
let lookup_started = Instant::now();
let mut values = vec![None; keys.len()];
let mut unresolved = Vec::new();
for (index, key) in keys.iter().enumerate() {
inner.diagnostics.pending_table_lookup_count = inner
.diagnostics
.pending_table_lookup_count
.saturating_add(1);
if let Some(value) = inner.pending_table.get(key) {
values[index].clone_from(value);
continue;
}
inner.diagnostics.mutable_state_lookup_count = inner
.diagnostics
.mutable_state_lookup_count
.saturating_add(1);
if let Some(value) = inner.state.get(key) {
values[index] = Some(value.clone());
} else {
unresolved.push(index);
}
}
let table_layers = if unresolved.is_empty() {
Vec::new()
} else {
let unresolved_count = unresolved.len() as u64;
let layer_count = inner.table_layers.len() as u64;
inner.diagnostics.table_lookup_count = inner
.diagnostics
.table_lookup_count
.saturating_add(unresolved_count);
inner.diagnostics.immutable_layer_lookup_count = inner
.diagnostics
.immutable_layer_lookup_count
.saturating_add(unresolved_count.saturating_mul(layer_count));
inner.diagnostics.table_layers_consulted = inner
.diagnostics
.table_layers_consulted
.saturating_add(unresolved_count.saturating_mul(layer_count));
inner.table_layers.clone()
};
let lookup_duration = elapsed_nanos(lookup_started.elapsed());
inner.diagnostics.read_lock_wait_duration_ns = inner
.diagnostics
.read_lock_wait_duration_ns
.saturating_add(lock_wait);
inner.diagnostics.read_lock_held_duration_ns = inner
.diagnostics
.read_lock_held_duration_ns
.saturating_add(elapsed_nanos(lock_started.elapsed()));
inner.diagnostics.table_lookup_duration_ns = inner
.diagnostics
.table_lookup_duration_ns
.saturating_add(lookup_duration);
(values, unresolved, table_layers)
};
let mut bytes_read = 0_u64;
let mut reader_wait_ns = 0_u64;
let mut file_read_ns = 0_u64;
for index in unresolved {
let key = &keys[index];
for layer in table_layers.iter().rev() {
if let Some(block) = layer.candidate_block(key) {
let entries = layer.loaded_entries()?;
let range = layer.candidate_entry_range(key);
let Ok(relative_index) = entries[range.clone()]
.binary_search_by(|entry| entry.key.as_slice().cmp(key))
else {
continue;
};
let entry = &entries[range.start + relative_index];
let (found, bytes, duration) =
read_table_block_entry_value(layer, block, entry)?;
bytes_read = bytes_read.saturating_add(bytes);
file_read_ns = file_read_ns.saturating_add(duration);
if let Some(value) = found {
values[index] = value;
break;
}
continue;
}
let entries = layer.loaded_entries()?;
let range = layer.candidate_entry_range(key);
let Ok(relative_index) =
entries[range.clone()].binary_search_by(|entry| entry.key.as_slice().cmp(key))
else {
continue;
};
let entry = &entries[range.start + relative_index];
let (value, reader_wait, duration) =
read_table_value_handle(&layer.file, entry, layer.is_v2)?;
values[index] = value;
bytes_read = bytes_read.saturating_add(entry.length);
reader_wait_ns = reader_wait_ns.saturating_add(reader_wait);
file_read_ns = file_read_ns.saturating_add(duration);
break;
}
}
if bytes_read > 0 || reader_wait_ns > 0 || file_read_ns > 0 {
let mut inner = self
.inner
.lock()
.map_err(|_| Error::message("database lock poisoned"))?;
inner.diagnostics.table_bytes_read = inner
.diagnostics
.table_bytes_read
.saturating_add(bytes_read);
inner.diagnostics.table_read_duration_ns = inner
.diagnostics
.table_read_duration_ns
.saturating_add(file_read_ns);
inner.diagnostics.table_reader_wait_duration_ns = inner
.diagnostics
.table_reader_wait_duration_ns
.saturating_add(reader_wait_ns);
inner.diagnostics.file_read_duration_ns = inner
.diagnostics
.file_read_duration_ns
.saturating_add(file_read_ns);
}
Ok(values)
}
#[allow(clippy::too_many_lines)]
fn get_durable_value(&self, key: &[u8]) -> Result<Option<Vec<u8>>> {
let lock_started = Instant::now();
let (resolved, immediate, table_layers) = {
let mut inner = self
.inner
.lock()
.map_err(|_| Error::message("database lock poisoned"))?;
let lock_wait = elapsed_nanos(lock_started.elapsed());
let lookup_started = Instant::now();
let mut resolved = false;
let mut immediate = None;
let mut table_layers = Vec::new();
inner.diagnostics.pending_table_lookup_count = inner
.diagnostics
.pending_table_lookup_count
.saturating_add(1);
if let Some(value) = inner.pending_table.get(key) {
resolved = true;
immediate.clone_from(value);
} else {
inner.diagnostics.mutable_state_lookup_count = inner
.diagnostics
.mutable_state_lookup_count
.saturating_add(1);
if let Some(value) = inner.state.get(key) {
resolved = true;
immediate = Some(value.clone());
} else {
inner.diagnostics.table_lookup_count =
inner.diagnostics.table_lookup_count.saturating_add(1);
table_layers.clone_from(&inner.table_layers);
let layers_examined = table_layers.len();
inner.diagnostics.immutable_layer_lookup_count = inner
.diagnostics
.immutable_layer_lookup_count
.saturating_add(layers_examined as u64);
inner.diagnostics.table_layers_consulted = inner
.diagnostics
.table_layers_consulted
.saturating_add(layers_examined as u64);
}
}
let lookup_duration = elapsed_nanos(lookup_started.elapsed());
let held_duration = elapsed_nanos(lock_started.elapsed());
inner.diagnostics.read_lock_wait_duration_ns = inner
.diagnostics
.read_lock_wait_duration_ns
.saturating_add(lock_wait);
inner.diagnostics.read_lock_held_duration_ns = inner
.diagnostics
.read_lock_held_duration_ns
.saturating_add(held_duration);
inner.diagnostics.table_lookup_duration_ns = inner
.diagnostics
.table_lookup_duration_ns
.saturating_add(lookup_duration);
(resolved, immediate, table_layers)
};
if resolved {
return Ok(immediate);
}
for layer in table_layers.iter().rev() {
if let Some(block) = layer.candidate_block(key) {
let entries = layer.loaded_entries()?;
let candidate_range = layer.candidate_entry_range(key);
let Ok(relative_index) = entries[candidate_range.clone()]
.binary_search_by(|entry| entry.key.as_slice().cmp(key))
else {
continue;
};
let entry = &entries[candidate_range.start + relative_index];
let (found, bytes_read, read_duration) =
read_table_block_entry_value(layer, block, entry)?;
let mut inner = self
.inner
.lock()
.map_err(|_| Error::message("database lock poisoned"))?;
inner.diagnostics.table_bytes_read = inner
.diagnostics
.table_bytes_read
.saturating_add(bytes_read);
inner.diagnostics.table_read_duration_ns = inner
.diagnostics
.table_read_duration_ns
.saturating_add(read_duration);
inner.diagnostics.file_read_duration_ns = inner
.diagnostics
.file_read_duration_ns
.saturating_add(read_duration);
if let Some(value) = found {
return Ok(value);
}
continue;
}
let entries = layer.loaded_entries()?;
let candidate_range = layer.candidate_entry_range(key);
let Ok(relative_index) = entries[candidate_range.clone()]
.binary_search_by(|entry| entry.key.as_slice().cmp(key))
else {
continue;
};
let index = candidate_range.start + relative_index;
let entry = &entries[index];
let (result, reader_wait, file_read) =
read_table_value_handle(&layer.file, entry, layer.is_v2)?;
let mut inner = self
.inner
.lock()
.map_err(|_| Error::message("database lock poisoned"))?;
inner.diagnostics.table_reader_wait_duration_ns = inner
.diagnostics
.table_reader_wait_duration_ns
.saturating_add(reader_wait);
inner.diagnostics.file_read_duration_ns = inner
.diagnostics
.file_read_duration_ns
.saturating_add(file_read);
inner.diagnostics.table_bytes_read = inner
.diagnostics
.table_bytes_read
.saturating_add(entry.length);
inner.diagnostics.table_read_duration_ns = inner
.diagnostics
.table_read_duration_ns
.saturating_add(file_read);
return Ok(result);
}
Ok(None)
}
}
impl Keyspace {
pub fn with_value<T>(
&self,
key: impl AsRef<[u8]>,
callback: impl FnOnce(Option<&[u8]>) -> std::result::Result<T, String>,
) -> Result<T> {
let key = key.as_ref();
#[cfg(feature = "benchmark")]
if let Some(rcu) = &self.db.ram_rcu_keyspaces {
let started = Instant::now();
let generation = rcu.load_full();
let value = generation
.get(self.name.as_ref())
.and_then(|keyspace| keyspace.get(key))
.map(|value| value.as_slice());
let result = callback(value).map_err(Error::message);
self.db
.record_ram_lookup_timing(0, 0, elapsed_nanos(started.elapsed()), 0, 0);
return result;
}
if self.db.ram_keyspaces.is_some() {
let lookup_started = Instant::now();
let ram_keyspaces = self
.db
.ram_keyspaces
.as_ref()
.ok_or_else(|| Error::message("ThingDB RAM state is unavailable"))?;
let state_lock_started = Instant::now();
let keyspaces = ram_keyspaces
.read()
.map_err(|_| Error::message("ThingDB RAM state lock poisoned"))?;
let lock_wait = elapsed_nanos(state_lock_started.elapsed());
let value = keyspaces
.get(self.name.as_ref())
.and_then(|keyspace| keyspace.get(key))
.map(|value| value.as_slice());
let result = callback(value).map_err(Error::message);
let lookup_duration = elapsed_nanos(lookup_started.elapsed());
drop(keyspaces);
self.db.record_ram_lookup_timing(
lock_wait,
lookup_duration.saturating_sub(lock_wait),
lookup_duration,
0,
0,
);
return result;
}
let lock_started = Instant::now();
let inner = self
.db
.inner
.lock()
.map_err(|_| Error::message("database lock poisoned"))?;
let lock_wait = elapsed_nanos(lock_started.elapsed());
if inner.in_memory {
drop(inner);
let lookup_started = Instant::now();
let ram_keyspaces = self
.db
.ram_keyspaces
.as_ref()
.ok_or_else(|| Error::message("ThingDB RAM state is unavailable"))?;
let keyspaces = ram_keyspaces
.read()
.map_err(|_| Error::message("ThingDB RAM state lock poisoned"))?;
let value = keyspaces
.get(self.name.as_ref())
.and_then(|keyspace| keyspace.get(key))
.map(|value| value.as_slice());
let lookup_duration = elapsed_nanos(lookup_started.elapsed());
let result = callback(value).map_err(Error::message);
let held_duration = lookup_duration;
drop(keyspaces);
self.db
.record_ram_lookup_timing(lock_wait, held_duration, lookup_duration, 0, 0);
return result;
}
drop(inner);
let value = self.db.get_durable_value(key)?;
callback(value.as_deref()).map_err(Error::message)
}
pub fn get_shared(&self, key: impl AsRef<[u8]>) -> Result<Option<Arc<Vec<u8>>>> {
let key = key.as_ref();
#[cfg(feature = "benchmark")]
if let Some(rcu) = &self.db.ram_rcu_keyspaces {
let started = Instant::now();
let generation = rcu.load_full();
let value = generation
.get(self.name.as_ref())
.and_then(|keyspace| keyspace.get(key))
.cloned();
self.db
.record_ram_lookup_timing(0, elapsed_nanos(started.elapsed()), 0, 0, 0);
return Ok(value);
}
if self.db.ram_keyspaces.is_some() {
let lookup_started = Instant::now();
let ram_keyspaces = self
.db
.ram_keyspaces
.as_ref()
.ok_or_else(|| Error::message("ThingDB RAM state is unavailable"))?;
let state_lock_started = Instant::now();
let keyspaces = ram_keyspaces
.read()
.map_err(|_| Error::message("ThingDB RAM state lock poisoned"))?;
let lock_wait = elapsed_nanos(state_lock_started.elapsed());
let value_ref = keyspaces
.get(self.name.as_ref())
.and_then(|keyspace| keyspace.get(key));
let acquire_started = Instant::now();
let value = value_ref.cloned();
let acquire_duration = elapsed_nanos(acquire_started.elapsed());
let lookup_duration = elapsed_nanos(lookup_started.elapsed());
drop(keyspaces);
self.db.record_ram_lookup_timing(
lock_wait,
lookup_duration.saturating_sub(lock_wait),
lookup_duration,
0,
acquire_duration,
);
return Ok(value);
}
let lock_started = Instant::now();
let inner = self
.db
.inner
.lock()
.map_err(|_| Error::message("database lock poisoned"))?;
let lock_wait = elapsed_nanos(lock_started.elapsed());
if !inner.in_memory {
return Err(Error::message(
"ThingDB shared reads are available only in memory mode",
));
}
drop(inner);
let lookup_started = Instant::now();
let ram_keyspaces = self
.db
.ram_keyspaces
.as_ref()
.ok_or_else(|| Error::message("ThingDB RAM state is unavailable"))?;
let keyspaces = ram_keyspaces
.read()
.map_err(|_| Error::message("ThingDB RAM state lock poisoned"))?;
let value_ref = keyspaces
.get(self.name.as_ref())
.and_then(|keyspace| keyspace.get(key));
let lookup_duration = elapsed_nanos(lookup_started.elapsed());
let acquire_started = Instant::now();
let value = value_ref.cloned();
let acquire_duration = elapsed_nanos(acquire_started.elapsed());
let held_duration = lookup_duration.saturating_add(acquire_duration);
drop(keyspaces);
self.db.record_ram_lookup_timing(
lock_wait,
held_duration,
lookup_duration,
0,
acquire_duration,
);
Ok(value)
}
pub fn get_many_shared(&self, keys: &[Vec<u8>]) -> Result<Vec<Option<Arc<Vec<u8>>>>> {
if keys.is_empty() {
return Ok(Vec::new());
}
#[cfg(feature = "benchmark")]
if let Some(rcu) = &self.db.ram_rcu_keyspaces {
let started = Instant::now();
let generation = rcu.load_full();
let values = keys
.iter()
.map(|key| {
generation
.get(self.name.as_ref())
.and_then(|keyspace| keyspace.get(key))
.cloned()
})
.collect();
self.db.record_ram_lookup_batch_timing(
u64::try_from(keys.len()).unwrap_or(u64::MAX),
0,
0,
elapsed_nanos(started.elapsed()),
0,
0,
);
return Ok(values);
}
if let Some(ram_keyspaces) = self.db.ram_keyspaces.as_ref() {
let lookup_started = Instant::now();
let lock_started = Instant::now();
let keyspaces = ram_keyspaces
.read()
.map_err(|_| Error::message("ThingDB RAM state lock poisoned"))?;
let lock_wait = elapsed_nanos(lock_started.elapsed());
let acquire_started = Instant::now();
let values = keys
.iter()
.map(|key| {
keyspaces
.get(self.name.as_ref())
.and_then(|keyspace| keyspace.get(key))
.cloned()
})
.collect();
let acquire_duration = elapsed_nanos(acquire_started.elapsed());
let lookup_duration = elapsed_nanos(lookup_started.elapsed());
drop(keyspaces);
self.db.record_ram_lookup_batch_timing(
u64::try_from(keys.len()).unwrap_or(u64::MAX),
lock_wait,
lookup_duration.saturating_sub(lock_wait),
lookup_duration,
0,
acquire_duration,
);
return Ok(values);
}
let physical_keys: Vec<_> = keys
.iter()
.map(|key| physical_key_from_namespace(&self.namespace, key))
.collect();
self.db
.get_many_durable_values(&physical_keys)
.map(|values| {
values
.into_iter()
.map(|value| value.map(Arc::new))
.collect()
})
}
pub fn get(&self, key: impl AsRef<[u8]>) -> Result<Option<Vec<u8>>> {
let key = key.as_ref();
#[cfg(feature = "benchmark")]
if let Some(rcu) = &self.db.ram_rcu_keyspaces {
let started = Instant::now();
let generation = rcu.load_full();
let value = generation
.get(self.name.as_ref())
.and_then(|keyspace| keyspace.get(key))
.map(|value| value.as_ref().clone());
let elapsed = elapsed_nanos(started.elapsed());
self.db
.record_ram_lookup_timing(0, elapsed, elapsed, elapsed, 0);
return Ok(value);
}
if self.db.ram_keyspaces.is_some() {
let lookup_started = Instant::now();
let ram_keyspaces = self
.db
.ram_keyspaces
.as_ref()
.ok_or_else(|| Error::message("ThingDB RAM state is unavailable"))?;
let state_lock_started = Instant::now();
let keyspaces = ram_keyspaces
.read()
.map_err(|_| Error::message("ThingDB RAM state lock poisoned"))?;
let lock_wait = elapsed_nanos(state_lock_started.elapsed());
let value = keyspaces
.get(self.name.as_ref())
.and_then(|keyspace| keyspace.get(key));
let clone_started = Instant::now();
let value = value.map(|value| value.as_ref().clone());
let clone_duration = elapsed_nanos(clone_started.elapsed());
let lookup_duration = elapsed_nanos(lookup_started.elapsed());
drop(keyspaces);
self.db.record_ram_lookup_timing(
lock_wait,
lookup_duration.saturating_sub(lock_wait),
lookup_duration,
clone_duration,
0,
);
return Ok(value);
}
let lock_started = Instant::now();
let inner = self
.db
.inner
.lock()
.map_err(|_| Error::message("database lock poisoned"))?;
let lock_wait = elapsed_nanos(lock_started.elapsed());
if inner.in_memory {
drop(inner);
let lookup_started = Instant::now();
let ram_keyspaces = self
.db
.ram_keyspaces
.as_ref()
.ok_or_else(|| Error::message("ThingDB RAM state is unavailable"))?;
let keyspaces = ram_keyspaces
.read()
.map_err(|_| Error::message("ThingDB RAM state lock poisoned"))?;
let value = keyspaces
.get(self.name.as_ref())
.and_then(|keyspace| keyspace.get(key));
let lookup_duration = elapsed_nanos(lookup_started.elapsed());
let clone_started = Instant::now();
let value = value.map(|value| value.as_ref().clone());
let clone_duration = elapsed_nanos(clone_started.elapsed());
let held_duration = lookup_duration.saturating_add(clone_duration);
drop(keyspaces);
self.db.record_ram_lookup_timing(
lock_wait,
held_duration,
lookup_duration,
clone_duration,
0,
);
return Ok(value);
}
let key_started = Instant::now();
let physical = physical_key_from_namespace(&self.namespace, key);
let key_duration = elapsed_nanos(key_started.elapsed());
drop(inner);
let result = self.db.get_durable_value(&physical);
self.db.update_ram_diagnostics(|diagnostics| {
diagnostics.key_encode_duration_ns = diagnostics
.key_encode_duration_ns
.saturating_add(key_duration);
});
result
}
pub fn insert(&self, key: impl AsRef<[u8]>, value: impl AsRef<[u8]>) -> Result<()> {
self.db.batch().put(self, key, value).commit()
}
pub fn remove(&self, key: impl AsRef<[u8]>) -> Result<()> {
self.db.batch().delete(self, key).commit()
}
pub fn iter(&self) -> Iter {
self.iter_bounds(None, None, None)
}
pub fn prefix(&self, prefix: impl AsRef<[u8]>) -> Iter {
self.iter_bounds(Some(prefix.as_ref()), None, None)
}
pub fn prefix_page(&self, prefix: impl AsRef<[u8]>, offset: usize, limit: usize) -> Iter {
self.iter_bounds_paginated(Some(prefix.as_ref()), None, None, offset, Some(limit))
}
pub fn prefix_page_after(
&self,
prefix: impl AsRef<[u8]>,
after_key: Option<&[u8]>,
limit: usize,
) -> Iter {
let start = after_key.map(|key| (key.to_vec(), false));
self.iter_bounds_paginated(Some(prefix.as_ref()), start, None, 0, Some(limit))
}
pub fn count(&self) -> Result<usize> {
#[cfg(feature = "benchmark")]
if let Some(rcu) = &self.db.ram_rcu_keyspaces {
return Ok(rcu
.load()
.get(self.name.as_ref())
.map_or(0, |keyspace| keyspace.len()));
}
if let Some(ram_keyspaces) = &self.db.ram_keyspaces {
let keyspaces = ram_keyspaces
.read()
.map_err(|_| Error::message("ThingDB RAM state lock poisoned"))?;
return Ok(keyspaces.get(self.name.as_ref()).map_or(0, BTreeMap::len));
}
self.db.count_durable_namespace(&self.namespace, None)
}
pub fn count_prefix(&self, prefix: impl AsRef<[u8]>) -> Result<usize> {
let prefix = prefix.as_ref();
#[cfg(feature = "benchmark")]
if let Some(rcu) = &self.db.ram_rcu_keyspaces {
return Ok(rcu
.load()
.get(self.name.as_ref())
.map_or(0, |keyspace| count_memory_prefix(keyspace, prefix)));
}
if let Some(ram_keyspaces) = &self.db.ram_keyspaces {
let keyspaces = ram_keyspaces
.read()
.map_err(|_| Error::message("ThingDB RAM state lock poisoned"))?;
return Ok(keyspaces
.get(self.name.as_ref())
.map_or(0, |keyspace| count_memory_prefix(keyspace, prefix)));
}
self.db
.count_durable_namespace(&self.namespace, Some(prefix))
}
pub fn first_prefix(&self, prefix: impl AsRef<[u8]>) -> Result<Option<Entry>> {
self.first_prefix_after(prefix, None)
}
pub fn first_prefix_after(
&self,
prefix: impl AsRef<[u8]>,
after: Option<&[u8]>,
) -> Result<Option<Entry>> {
let prefix = prefix.as_ref().to_vec();
let start = after.map(|key| (key.to_vec(), false));
self.iter_bounds_limited(Some(&prefix), start, None, Some(1))
.into_result()
.map(|entries| entries.into_iter().next())
}
pub fn range<K, R>(&self, range: R) -> Iter
where
K: AsRef<[u8]>,
R: RangeBounds<K>,
{
let start = match range.start_bound() {
Bound::Included(value) => Some((value.as_ref().to_vec(), true)),
Bound::Excluded(value) => Some((value.as_ref().to_vec(), false)),
Bound::Unbounded => None,
};
let end = match range.end_bound() {
Bound::Included(value) => Some((value.as_ref().to_vec(), true)),
Bound::Excluded(value) => Some((value.as_ref().to_vec(), false)),
Bound::Unbounded => None,
};
self.range_bounds(
start
.as_ref()
.map(|(key, inclusive)| (key.as_slice(), *inclusive)),
end.as_ref()
.map(|(key, inclusive)| (key.as_slice(), *inclusive)),
)
}
pub fn range_bounds(&self, start: Option<(&[u8], bool)>, end: Option<(&[u8], bool)>) -> Iter {
self.iter_bounds(
None,
start.map(|(key, inclusive)| (key.to_vec(), inclusive)),
end.map(|(key, inclusive)| (key.to_vec(), inclusive)),
)
}
#[allow(clippy::too_many_lines)]
fn iter_bounds(
&self,
prefix: Option<&[u8]>,
start: Option<(Vec<u8>, bool)>,
end: Option<(Vec<u8>, bool)>,
) -> Iter {
self.iter_bounds_paginated(prefix, start, end, 0, None)
}
#[allow(clippy::too_many_lines)]
fn iter_bounds_limited(
&self,
prefix: Option<&[u8]>,
start: Option<(Vec<u8>, bool)>,
end: Option<(Vec<u8>, bool)>,
limit: Option<usize>,
) -> Iter {
self.iter_bounds_paginated(prefix, start, end, 0, limit)
}
#[allow(clippy::too_many_lines)]
fn iter_bounds_paginated(
&self,
prefix: Option<&[u8]>,
start: Option<(Vec<u8>, bool)>,
end: Option<(Vec<u8>, bool)>,
offset: usize,
limit: Option<usize>,
) -> Iter {
if limit == Some(0) {
return Iter {
entries: Vec::new().into_iter(),
error: None,
};
}
#[cfg(feature = "benchmark")]
if let Some(rcu) = &self.db.ram_rcu_keyspaces {
return iter_memory_rcu_bounds(
&self.db,
rcu.load_full(),
&self.name,
ScanBounds {
prefix,
start,
end,
offset,
limit,
},
);
}
if self.db.ram_keyspaces.is_some() {
let ram_keyspaces = self
.db
.ram_keyspaces
.as_ref()
.ok_or_else(|| Error::message("ThingDB RAM state is unavailable"));
return match ram_keyspaces {
Ok(ram_keyspaces) => iter_memory_bounds(
&self.db,
ram_keyspaces,
&self.name,
ScanBounds {
prefix,
start,
end,
offset,
limit,
},
),
Err(error) => Iter {
entries: Vec::new().into_iter(),
error: Some(error),
},
};
}
let scan_lock_started = Instant::now();
let Ok(mut inner) = self.db.inner.lock() else {
return Iter {
entries: Vec::new().into_iter(),
error: None,
};
};
let scan_lock_wait = elapsed_nanos(scan_lock_started.elapsed());
if inner.in_memory {
drop(inner);
let ram_keyspaces = self
.db
.ram_keyspaces
.as_ref()
.ok_or_else(|| Error::message("ThingDB RAM state is unavailable"));
return match ram_keyspaces {
Ok(ram_keyspaces) => iter_memory_bounds(
&self.db,
ram_keyspaces,
&self.name,
ScanBounds {
prefix,
start,
end,
offset,
limit,
},
),
Err(error) => Iter {
entries: Vec::new().into_iter(),
error: Some(error),
},
};
}
if inner.table_layers.is_empty()
&& limit.is_some_and(|limit| limit <= 4_096)
&& let Some(page) = iter_durable_memtable_page(
&mut inner,
&self.namespace,
prefix,
start.as_ref(),
end.as_ref(),
offset,
limit.unwrap_or_default(),
scan_lock_wait,
&scan_lock_started,
)
{
return page;
}
if offset == 0 && limit == Some(1) {
drop(inner);
return self.iter_durable_first(prefix, start, end);
}
if let Some(limit) = limit
&& limit <= 4_096
&& offset.saturating_add(limit) <= 16_384
{
let mut capture_metrics = DurableScanPageCaptureMetrics::default();
let snapshot = capture_durable_table_page(
&inner,
&self.namespace,
prefix,
start.as_ref(),
end.as_ref(),
scan_lock_wait,
elapsed_nanos(scan_lock_started.elapsed()).saturating_sub(scan_lock_wait),
false,
&mut capture_metrics,
);
capture_metrics.record(&mut inner.diagnostics);
if let Some(snapshot) = snapshot {
drop(inner);
return iter_durable_table_page(
&self.db,
&self.namespace,
prefix,
start,
end,
offset,
limit,
snapshot,
None,
);
}
}
let state = inner.state.clone();
let pending_table = inner.pending_table.clone();
let table_layers = inner.table_layers.clone();
let scan_lock_held =
elapsed_nanos(scan_lock_started.elapsed()).saturating_sub(scan_lock_wait);
drop(inner);
let namespace = self.namespace.clone();
let scan_started = Instant::now();
let cursor_started = Instant::now();
let lower = durable_scan_lower(&namespace, prefix, start.as_ref());
let upper = durable_scan_upper(&namespace, prefix, end.as_ref());
if upper
.as_deref()
.is_some_and(|upper| lower.as_slice() >= upper)
{
return Iter {
entries: Vec::new().into_iter(),
error: None,
};
}
let cursor_after = start
.as_ref()
.and_then(|(key, inclusive)| {
(!inclusive).then(|| physical_key_from_namespace(&namespace, key))
})
.filter(|key| key.as_slice() >= lower.as_slice());
let layer_entries = match table_layers
.iter()
.map(TableLayer::loaded_entries)
.collect::<Result<Vec<_>>>()
{
Ok(entries) => entries,
Err(error) => {
return Iter {
entries: Vec::new().into_iter(),
error: Some(error),
};
},
};
let mut entries = Vec::new();
let mut scan_error = None;
let mut scan_keys_examined = 0u64;
let mut scan_layers_consulted = 0u64;
let mut table_bytes_read = 0u64;
let mut table_read_duration_ns = 0u64;
let mut entries_skipped = 0usize;
let mut state_key = next_map_key(&state, &lower, upper.as_deref(), cursor_after.as_deref());
let mut pending_key = next_map_key(
&pending_table,
&lower,
upper.as_deref(),
cursor_after.as_deref(),
);
let mut layer_indices = layer_entries
.iter()
.map(|entries| {
let index = entries
.binary_search_by(|entry| entry.key.as_slice().cmp(lower.as_slice()))
.unwrap_or_else(|index| index);
if cursor_after.is_some()
&& entries.get(index).is_some_and(|entry| {
cursor_after
.as_deref()
.is_some_and(|after| entry.key == after)
})
{
index + 1
} else {
index
}
})
.collect::<Vec<_>>();
let cursor_duration = elapsed_nanos(cursor_started.elapsed());
let merge_started = Instant::now();
loop {
let mut next_key = state_key.clone();
if pending_key.as_deref().is_some_and(|candidate| {
next_key
.as_deref()
.is_none_or(|current| candidate < current)
}) {
next_key.clone_from(&pending_key);
}
for (entries, index) in layer_entries.iter().zip(&layer_indices) {
if let Some(candidate) = entries.get(*index).map(|entry| &entry.key)
&& next_key
.as_deref()
.is_none_or(|current| candidate.as_slice() < current)
{
next_key = Some(candidate.clone());
}
}
let Some(key) = next_key else {
break;
};
if upper.as_ref().is_some_and(|upper| key >= *upper) {
break;
}
if state_key.as_deref() == Some(key.as_slice()) {
state_key = next_map_key(&state, &lower, upper.as_deref(), Some(&key));
}
if pending_key.as_deref() == Some(key.as_slice()) {
pending_key = next_map_key(&pending_table, &lower, upper.as_deref(), Some(&key));
}
for (entries, index) in layer_entries.iter().zip(&mut layer_indices) {
if entries.get(*index).is_some_and(|entry| entry.key == key) {
*index += 1;
}
}
scan_keys_examined = scan_keys_examined.saturating_add(1);
let value = match get_scan_value_snapshot(&state, &pending_table, &table_layers, &key) {
Ok((value, layers, bytes, duration)) => {
scan_layers_consulted = scan_layers_consulted.saturating_add(layers);
table_bytes_read = table_bytes_read.saturating_add(bytes);
table_read_duration_ns = table_read_duration_ns.saturating_add(duration);
value
},
Err(error) => {
scan_error = Some(error);
break;
},
};
let Some(value) = value else {
continue;
};
let Some(user_key) = key.strip_prefix(namespace.as_ref()) else {
continue;
};
if let Some(prefix) = prefix
&& !user_key.starts_with(prefix)
{
continue;
}
if let Some((start, inclusive)) = &start {
let matches = if *inclusive {
user_key >= start.as_slice()
} else {
user_key > start.as_slice()
};
if !matches {
continue;
}
}
if let Some((end, inclusive)) = &end {
let matches = if *inclusive {
user_key <= end.as_slice()
} else {
user_key < end.as_slice()
};
if !matches {
continue;
}
}
if entries_skipped < offset {
entries_skipped += 1;
continue;
}
entries.push(Entry {
key: user_key.to_vec(),
value,
});
if limit.is_some_and(|limit| entries.len() >= limit) {
break;
}
}
let Ok(mut inner) = self.db.inner.lock() else {
return Iter {
entries: entries.into_iter(),
error: Some(Error::message("database lock poisoned")),
};
};
inner.diagnostics.scan_keys_examined = inner
.diagnostics
.scan_keys_examined
.saturating_add(scan_keys_examined);
inner.diagnostics.scan_layers_consulted = inner
.diagnostics
.scan_layers_consulted
.saturating_add(scan_layers_consulted);
inner.diagnostics.scan_lock_wait_duration_ns = inner
.diagnostics
.scan_lock_wait_duration_ns
.saturating_add(scan_lock_wait);
inner.diagnostics.scan_lock_held_duration_ns = inner
.diagnostics
.scan_lock_held_duration_ns
.saturating_add(scan_lock_held);
inner.diagnostics.scan_cursor_init_duration_ns = inner
.diagnostics
.scan_cursor_init_duration_ns
.saturating_add(cursor_duration);
inner.diagnostics.scan_merge_duration_ns = inner
.diagnostics
.scan_merge_duration_ns
.saturating_add(elapsed_nanos(merge_started.elapsed()));
inner.diagnostics.scan_returned_entries = inner
.diagnostics
.scan_returned_entries
.saturating_add(entries.len() as u64);
if scan_error.is_some() {
inner.diagnostics.scan_error_count =
inner.diagnostics.scan_error_count.saturating_add(1);
}
inner.diagnostics.table_bytes_read = inner
.diagnostics
.table_bytes_read
.saturating_add(table_bytes_read);
inner.diagnostics.table_read_duration_ns = inner
.diagnostics
.table_read_duration_ns
.saturating_add(table_read_duration_ns);
inner.diagnostics.scan_count = inner.diagnostics.scan_count.saturating_add(1);
inner.diagnostics.scan_duration_ns = inner
.diagnostics
.scan_duration_ns
.saturating_add(elapsed_nanos(scan_started.elapsed()));
Iter {
entries: entries.into_iter(),
error: scan_error,
}
}
#[allow(clippy::too_many_lines)]
fn iter_durable_first(
&self,
prefix: Option<&[u8]>,
start: Option<(Vec<u8>, bool)>,
end: Option<(Vec<u8>, bool)>,
) -> Iter {
let namespace = self.namespace.clone();
let mut after = start.as_ref().and_then(|(key, inclusive)| {
(!inclusive).then(|| physical_key_from_namespace(&namespace, key))
});
let mut retries = 0;
loop {
let lock_started = Instant::now();
let snapshot = match self.db.inner.lock() {
Ok(inner) if !inner.in_memory => {
let lock_wait = elapsed_nanos(lock_started.elapsed());
let lower = durable_scan_lower(&namespace, prefix, start.as_ref());
let upper = durable_scan_upper(&namespace, prefix, end.as_ref());
let cursor_after = after.as_deref().filter(|key| *key >= lower.as_slice());
let state_candidate =
next_map_key(&inner.state, &lower, upper.as_deref(), cursor_after)
.and_then(|key| {
inner.state.get(&key).map(|value| (key, value.clone()))
});
let pending_candidate =
next_map_key(&inner.pending_table, &lower, upper.as_deref(), cursor_after)
.and_then(|key| {
inner
.pending_table
.get(&key)
.map(|value| (key, value.clone()))
});
let layers = inner.table_layers.clone();
let generation = inner.state_generation;
let lock_held = elapsed_nanos(lock_started.elapsed());
(
lower,
upper,
state_candidate,
pending_candidate,
layers,
generation,
lock_wait,
lock_held,
)
},
Ok(_) => {
return Iter {
entries: Vec::new().into_iter(),
error: Some(Error::message("ThingDB durable scan used for RAM state")),
};
},
Err(_) => {
return Iter {
entries: Vec::new().into_iter(),
error: Some(Error::message("database lock poisoned")),
};
},
};
let (
lower,
upper,
state_candidate,
pending_candidate,
layers,
generation,
lock_wait,
lock_held,
) = snapshot;
let table_candidates = layers
.iter()
.map(|layer| {
let entries = layer.loaded_entries()?;
let seek = after
.as_deref()
.filter(|key| *key > lower.as_slice())
.unwrap_or(&lower);
let index = entries
.binary_search_by(|entry| entry.key.as_slice().cmp(seek))
.unwrap_or_else(|index| index);
let index = if after.as_deref().is_some_and(|after| {
entries
.get(index)
.is_some_and(|entry| entry.key.as_slice() == after)
}) {
index + 1
} else {
index
};
Ok(entries
.get(index)
.filter(|entry| {
upper
.as_deref()
.is_none_or(|bound| entry.key.as_slice() < bound)
})
.map(|entry| entry.key.clone()))
})
.collect::<Result<Vec<_>>>();
let table_candidates = match table_candidates {
Ok(candidates) => candidates,
Err(error) => {
return Iter {
entries: Vec::new().into_iter(),
error: Some(error),
};
},
};
let mut key = state_candidate.as_ref().map(|(key, _)| key.clone());
if pending_candidate.as_ref().is_some_and(|(candidate, _)| {
key.as_deref()
.is_none_or(|current| candidate.as_slice() < current)
}) {
key = pending_candidate.as_ref().map(|(key, _)| key.clone());
}
for candidate in table_candidates.iter().flatten() {
if key
.as_deref()
.is_none_or(|current| candidate.as_slice() < current)
{
key = Some(candidate.clone());
}
}
let Some(key) = key else {
return self.finish_durable_first_diagnostics(
lock_wait,
lock_held,
0,
0,
Vec::new(),
);
};
let value = if pending_candidate
.as_ref()
.is_some_and(|(candidate, _)| candidate == &key)
{
pending_candidate.and_then(|(_, value)| value)
} else if state_candidate
.as_ref()
.is_some_and(|(candidate, _)| candidate == &key)
{
state_candidate.map(|(_, value)| value)
} else {
match get_scan_value_snapshot(&BTreeMap::new(), &BTreeMap::new(), &layers, &key) {
Ok((value, _, _, _)) => value,
Err(error) => {
return Iter {
entries: Vec::new().into_iter(),
error: Some(error),
};
},
}
};
let generation_unchanged = self
.db
.inner
.lock()
.map(|inner| inner.state_generation == generation)
.unwrap_or(false);
if !generation_unchanged {
retries += 1;
if retries >= 8 {
return Iter {
entries: Vec::new().into_iter(),
error: Some(Error::message(
"ThingDB durable scan changed during point lookup",
)),
};
}
continue;
}
after = Some(key.clone());
let Some(value) = value else {
continue;
};
let Some(user_key) = key.strip_prefix(namespace.as_ref()) else {
return self.finish_durable_first_diagnostics(
lock_wait,
lock_held,
layers.len() as u64,
0,
Vec::new(),
);
};
return self.finish_durable_first_diagnostics(
lock_wait,
lock_held,
layers.len() as u64,
1,
vec![Entry {
key: user_key.to_vec(),
value,
}],
);
}
}
fn finish_durable_first_diagnostics(
&self,
lock_wait: u64,
lock_held: u64,
layers: u64,
returned: u64,
entries: Vec<Entry>,
) -> Iter {
if let Ok(mut inner) = self.db.inner.lock() {
inner.diagnostics.scan_count = inner.diagnostics.scan_count.saturating_add(1);
inner.diagnostics.scan_lock_wait_duration_ns = inner
.diagnostics
.scan_lock_wait_duration_ns
.saturating_add(lock_wait);
inner.diagnostics.scan_lock_held_duration_ns = inner
.diagnostics
.scan_lock_held_duration_ns
.saturating_add(lock_held);
inner.diagnostics.scan_layers_consulted = inner
.diagnostics
.scan_layers_consulted
.saturating_add(layers);
inner.diagnostics.scan_returned_entries = inner
.diagnostics
.scan_returned_entries
.saturating_add(returned);
}
Iter {
entries: entries.into_iter(),
error: None,
}
}
}
fn get_scan_value_snapshot(
state: &BTreeMap<Vec<u8>, Vec<u8>>,
pending_table: &BTreeMap<Vec<u8>, Option<Vec<u8>>>,
table_layers: &[TableLayer],
key: &[u8],
) -> Result<(Option<Vec<u8>>, u64, u64, u64)> {
if let Some(value) = pending_table.get(key) {
return Ok((value.clone(), 0, 0, 0));
}
if let Some(value) = state.get(key) {
return Ok((Some(value.clone()), 0, 0, 0));
}
let mut layers_consulted = 0;
for layer in table_layers.iter().rev() {
layers_consulted += 1;
if let Some(block) = layer.candidate_block(key) {
let entries = layer.loaded_entries()?;
let candidate_range = layer.candidate_entry_range(key);
let Ok(relative_index) = entries[candidate_range.clone()]
.binary_search_by(|entry| entry.key.as_slice().cmp(key))
else {
continue;
};
let entry = &entries[candidate_range.start + relative_index];
let (value, bytes_read, duration) = read_table_block_entry_value(layer, block, entry)?;
let value = value.ok_or_else(|| {
Error::message("ThingDB table index record was not found in its block")
})?;
return Ok((value, layers_consulted, bytes_read, duration));
}
let entries = layer.loaded_entries()?;
let candidate_range = layer.candidate_entry_range(key);
let Ok(relative_index) = entries[candidate_range.clone()]
.binary_search_by(|entry| entry.key.as_slice().cmp(key))
else {
continue;
};
let index = candidate_range.start + relative_index;
return read_table_value_handle(&layer.file, &entries[index], layer.is_v2).map(
|(value, _, duration)| (value, layers_consulted, entries[index].length, duration),
);
}
Ok((None, layers_consulted, 0, 0))
}
#[allow(clippy::too_many_arguments)]
#[allow(clippy::too_many_lines)]
fn iter_durable_memtable_page(
inner: &mut Inner,
namespace: &[u8],
prefix: Option<&[u8]>,
start: Option<&(Vec<u8>, bool)>,
end: Option<&(Vec<u8>, bool)>,
offset: usize,
limit: usize,
scan_lock_wait: u64,
scan_lock_started: &Instant,
) -> Option<Iter> {
let scan_started = Instant::now();
let cursor_started = Instant::now();
let lower = durable_scan_lower(namespace, prefix, start);
let upper = durable_scan_upper(namespace, prefix, end);
let cursor_after = start
.and_then(|(key, inclusive)| {
(!inclusive).then(|| physical_key_from_namespace(namespace, key))
})
.filter(|key| key.as_slice() >= lower.as_slice());
let cursor_duration = elapsed_nanos(cursor_started.elapsed());
let merge_started = Instant::now();
let mut entries = Vec::with_capacity(limit.min(1024));
let mut scan_keys_examined = 0u64;
if upper
.as_deref()
.is_none_or(|upper| lower.as_slice() < upper)
{
let range_start =
cursor_after.map_or_else(|| Bound::Included(lower.clone()), Bound::Excluded);
let range_end = upper
.as_ref()
.map_or(Bound::Unbounded, |key| Bound::Excluded(key.clone()));
let mut state = inner
.state
.range((range_start.clone(), range_end.clone()))
.peekable();
let mut pending = inner
.pending_table
.range((range_start, range_end))
.peekable();
let max_examined = offset
.saturating_add(limit)
.saturating_mul(4)
.saturating_add(64)
.clamp(256, 16_384);
let mut visible_entries_skipped = 0usize;
while entries.len() < limit {
let state_key = state.peek().map(|(key, _)| key.as_slice());
let pending_key = pending.peek().map(|(key, _)| key.as_slice());
let (key, from_pending, advance_state, advance_pending) = match (state_key, pending_key)
{
(None, None) => break,
(Some(_), None) => {
let (key, _) = state.peek().expect("state cursor was inspected");
((*key).clone(), false, true, false)
},
(None, Some(_)) => {
let (key, _) = pending.peek().expect("pending cursor was inspected");
((*key).clone(), true, false, true)
},
(Some(state_key), Some(pending_key)) => match state_key.cmp(pending_key) {
std::cmp::Ordering::Less => {
let (key, _) = state.peek().expect("state cursor was inspected");
((*key).clone(), false, true, false)
},
std::cmp::Ordering::Equal => {
let (key, _) = pending.peek().expect("pending cursor was inspected");
((*key).clone(), true, true, true)
},
std::cmp::Ordering::Greater => {
let (key, _) = pending.peek().expect("pending cursor was inspected");
((*key).clone(), true, false, true)
},
},
};
if advance_state {
state.next();
}
if advance_pending {
pending.next();
}
scan_keys_examined = scan_keys_examined.saturating_add(1);
if scan_keys_examined as usize > max_examined && entries.len() < limit {
return None;
}
let value = if from_pending {
inner.pending_table.get(&key).and_then(Option::as_ref)
} else {
inner.state.get(&key)
};
let Some(value) = value else {
continue;
};
let Some(user_key) = key.strip_prefix(namespace) else {
continue;
};
if prefix.is_some_and(|prefix| !user_key.starts_with(prefix)) {
continue;
}
if let Some((start, inclusive)) = start {
let matches = if *inclusive {
user_key >= start.as_slice()
} else {
user_key > start.as_slice()
};
if !matches {
continue;
}
}
if let Some((end, inclusive)) = end {
let matches = if *inclusive {
user_key <= end.as_slice()
} else {
user_key < end.as_slice()
};
if !matches {
continue;
}
}
if visible_entries_skipped < offset {
visible_entries_skipped += 1;
continue;
}
entries.push(Entry {
key: user_key.to_vec(),
value: value.clone(),
});
}
}
let scan_merge_duration = elapsed_nanos(merge_started.elapsed());
let scan_lock_held = elapsed_nanos(scan_lock_started.elapsed()).saturating_sub(scan_lock_wait);
let scan_duration = elapsed_nanos(scan_started.elapsed());
inner.diagnostics.scan_count = inner.diagnostics.scan_count.saturating_add(1);
inner.diagnostics.scan_keys_examined = inner
.diagnostics
.scan_keys_examined
.saturating_add(scan_keys_examined);
inner.diagnostics.scan_lock_wait_duration_ns = inner
.diagnostics
.scan_lock_wait_duration_ns
.saturating_add(scan_lock_wait);
inner.diagnostics.scan_lock_held_duration_ns = inner
.diagnostics
.scan_lock_held_duration_ns
.saturating_add(scan_lock_held);
inner.diagnostics.scan_cursor_init_duration_ns = inner
.diagnostics
.scan_cursor_init_duration_ns
.saturating_add(cursor_duration);
inner.diagnostics.scan_merge_duration_ns = inner
.diagnostics
.scan_merge_duration_ns
.saturating_add(scan_merge_duration);
inner.diagnostics.scan_returned_entries = inner
.diagnostics
.scan_returned_entries
.saturating_add(entries.len() as u64);
inner.diagnostics.scan_duration_ns = inner
.diagnostics
.scan_duration_ns
.saturating_add(scan_duration);
Some(Iter {
entries: entries.into_iter(),
error: None,
})
}
#[allow(clippy::too_many_arguments)]
fn capture_durable_table_page(
inner: &Inner,
namespace: &[u8],
prefix: Option<&[u8]>,
start: Option<&(Vec<u8>, bool)>,
end: Option<&(Vec<u8>, bool)>,
lock_wait_ns: u64,
lock_held_ns: u64,
count_only: bool,
metrics: &mut DurableScanPageCaptureMetrics,
) -> Option<DurableScanPageSnapshot> {
if inner.in_memory {
return None;
}
let cursor_init_started = Instant::now();
metrics.attempted = true;
let lower = durable_scan_lower(namespace, prefix, start);
let upper = durable_scan_upper(namespace, prefix, end);
if upper
.as_deref()
.is_some_and(|upper| lower.as_slice() >= upper)
{
metrics.duration_ns = elapsed_nanos(cursor_init_started.elapsed());
return Some(DurableScanPageSnapshot {
state: Vec::new(),
pending: Vec::new(),
state_after: None,
pending_after: None,
state_has_more: false,
pending_has_more: false,
layers: Vec::new(),
lower,
upper,
after: None,
generation: inner.state_generation,
lock_wait_ns,
lock_held_ns,
cursor_init_ns: elapsed_nanos(cursor_init_started.elapsed()),
});
}
let after = start
.and_then(|(key, inclusive)| {
(!inclusive).then(|| physical_key_from_namespace(namespace, key))
})
.filter(|key| key.as_slice() >= lower.as_slice());
let state_chunk = capture_durable_memtable_chunk(
&inner.state,
&lower,
upper.as_deref(),
after.as_deref(),
usize::MAX - 1,
|value| {
Some(if count_only {
Vec::new()
} else {
value.clone()
})
},
);
let pending_chunk = capture_durable_memtable_chunk(
&inner.pending_table,
&lower,
upper.as_deref(),
after.as_deref(),
usize::MAX,
|value| {
value.as_ref().map(|value| {
if count_only {
Vec::new()
} else {
value.clone()
}
})
},
);
metrics.candidates_copied =
state_chunk.records.len() as u64 + pending_chunk.records.len() as u64;
metrics.duration_ns = elapsed_nanos(cursor_init_started.elapsed());
Some(DurableScanPageSnapshot {
state: state_chunk.records,
pending: pending_chunk.records,
state_after: state_chunk.after,
pending_after: pending_chunk.after,
state_has_more: state_chunk.has_more,
pending_has_more: pending_chunk.has_more,
layers: inner.table_layers.clone(),
lower,
upper,
after,
generation: inner.state_generation,
lock_wait_ns,
lock_held_ns,
cursor_init_ns: elapsed_nanos(cursor_init_started.elapsed()),
})
}
#[allow(clippy::too_many_arguments)]
#[allow(clippy::too_many_lines)]
fn iter_durable_table_page(
database: &Database,
namespace: &[u8],
prefix: Option<&[u8]>,
start: Option<(Vec<u8>, bool)>,
end: Option<(Vec<u8>, bool)>,
offset: usize,
limit: usize,
mut snapshot: DurableScanPageSnapshot,
mut count_output: Option<&mut usize>,
) -> Iter {
for attempt in 0..4 {
let count_only = count_output.is_some();
if let Some(count) = count_output.as_deref_mut() {
*count = 0;
}
let scan_started = Instant::now();
let merge_started = Instant::now();
let mut table_cursors = Vec::with_capacity(snapshot.layers.len());
let mut scan_error = None;
let mut counted_entries = 0usize;
for (index, layer) in snapshot.layers.iter().enumerate() {
if layer.blocks.is_empty()
&& layer.entries.get().is_none_or(|entries| entries.is_empty())
{
continue;
}
match TableScanCursor::new(
layer,
index.saturating_add(1),
&snapshot.lower,
snapshot.upper.as_deref(),
snapshot.after.as_deref(),
!count_only,
) {
Ok(cursor) => table_cursors.push((index, cursor)),
Err(error) => {
scan_error = Some(error);
break;
},
}
}
let cursor_init_ns = elapsed_nanos(merge_started.elapsed());
let mut entries = Vec::with_capacity(limit.min(1024));
let mut scan_keys_examined = 0u64;
let mut entries_skipped = 0usize;
let mut state_index = 0usize;
let mut pending_index = 0usize;
let mut scan_lock_wait_ns = snapshot.lock_wait_ns;
let mut scan_lock_held_ns = snapshot.lock_held_ns;
if scan_error.is_none() {
while if count_only {
counted_entries < limit
} else {
entries.len() < limit
} {
let refill_state = state_index == snapshot.state.len() && snapshot.state_has_more;
let refill_pending =
pending_index == snapshot.pending.len() && snapshot.pending_has_more;
if refill_state || refill_pending {
let lock_started = Instant::now();
let Ok(mut inner) = database.inner.lock() else {
scan_error = Some(Error::message("database lock poisoned"));
break;
};
let refill_lock_wait_ns = elapsed_nanos(lock_started.elapsed());
scan_lock_wait_ns = scan_lock_wait_ns.saturating_add(refill_lock_wait_ns);
let lock_held_started = Instant::now();
if inner.state_generation != snapshot.generation {
scan_lock_held_ns = scan_lock_held_ns
.saturating_add(elapsed_nanos(lock_held_started.elapsed()));
break;
}
let capture_started = Instant::now();
let mut capture_metrics = DurableScanPageCaptureMetrics {
attempted: true,
..DurableScanPageCaptureMetrics::default()
};
if refill_state {
let chunk = capture_durable_memtable_chunk(
&inner.state,
&snapshot.lower,
snapshot.upper.as_deref(),
snapshot.state_after.as_deref(),
usize::MAX - 1,
|value| {
Some(if count_only {
Vec::new()
} else {
value.clone()
})
},
);
capture_metrics.candidates_copied = capture_metrics
.candidates_copied
.saturating_add(chunk.records.len() as u64);
snapshot.state = chunk.records;
snapshot.state_after = chunk.after;
snapshot.state_has_more = chunk.has_more;
state_index = 0;
}
if refill_pending {
let chunk = capture_durable_memtable_chunk(
&inner.pending_table,
&snapshot.lower,
snapshot.upper.as_deref(),
snapshot.pending_after.as_deref(),
usize::MAX,
|value| {
value.as_ref().map(|value| {
if count_only {
Vec::new()
} else {
value.clone()
}
})
},
);
capture_metrics.candidates_copied = capture_metrics
.candidates_copied
.saturating_add(chunk.records.len() as u64);
snapshot.pending = chunk.records;
snapshot.pending_after = chunk.after;
snapshot.pending_has_more = chunk.has_more;
pending_index = 0;
}
capture_metrics.duration_ns = elapsed_nanos(capture_started.elapsed());
capture_metrics.record(&mut inner.diagnostics);
scan_lock_held_ns = scan_lock_held_ns
.saturating_add(elapsed_nanos(lock_held_started.elapsed()));
drop(inner);
}
let mut next_key: Option<&[u8]> = snapshot
.state
.get(state_index)
.map(|record| record.key.as_slice());
if let Some(key) = snapshot
.pending
.get(pending_index)
.map(|record| record.key.as_slice())
&& next_key.is_none_or(|current| key < current)
{
next_key = Some(key);
}
for (_, cursor) in &table_cursors {
if let Some(key) = cursor.head().map(|record| record.key.as_slice())
&& next_key.is_none_or(|current| key < current)
{
next_key = Some(key);
}
}
let Some(key) = next_key.map(<[u8]>::to_vec) else {
break;
};
if snapshot
.upper
.as_deref()
.is_some_and(|upper| key.as_slice() >= upper)
{
break;
}
scan_keys_examined = scan_keys_examined.saturating_add(1);
let mut selected: Option<(usize, bool, Option<Vec<u8>>)> = None;
for record in [
snapshot.state.get(state_index),
snapshot.pending.get(pending_index),
]
.into_iter()
.flatten()
.filter(|record| record.key == key)
{
if selected
.as_ref()
.is_none_or(|(priority, _, _)| record.priority > *priority)
{
selected = Some((
record.priority,
record.value.is_some(),
(!count_only).then(|| record.value.clone()).flatten(),
));
}
}
for (_, cursor) in &table_cursors {
if let Some(record) = cursor.head().filter(|record| record.key == key)
&& selected
.as_ref()
.is_none_or(|(priority, _, _)| cursor.priority > *priority)
{
selected = Some((
cursor.priority,
record.value.is_some(),
(!count_only).then(|| record.value.clone()).flatten(),
));
}
}
if let Some((_, is_live, value)) = selected
&& is_live
&& let Some(user_key) = key.strip_prefix(namespace)
&& prefix.is_none_or(|prefix| user_key.starts_with(prefix))
&& start.as_ref().is_none_or(|(bound, inclusive)| {
if *inclusive {
user_key >= bound.as_slice()
} else {
user_key > bound.as_slice()
}
})
&& end.as_ref().is_none_or(|(bound, inclusive)| {
if *inclusive {
user_key <= bound.as_slice()
} else {
user_key < bound.as_slice()
}
})
{
if entries_skipped < offset {
entries_skipped += 1;
} else if count_only {
counted_entries = counted_entries.saturating_add(1);
} else {
entries.push(Entry {
key: user_key.to_vec(),
value: value.unwrap_or_default(),
});
if entries.len() >= limit {
break;
}
}
}
if snapshot
.state
.get(state_index)
.is_some_and(|record| record.key == key)
{
state_index += 1;
}
if snapshot
.pending
.get(pending_index)
.is_some_and(|record| record.key == key)
{
pending_index += 1;
}
for (layer_index, cursor) in &mut table_cursors {
if cursor.head().is_some_and(|record| record.key == key)
&& let Err(error) = cursor.advance(
&snapshot.layers[*layer_index],
&snapshot.lower,
snapshot.upper.as_deref(),
)
{
scan_error = Some(error);
break;
}
}
if scan_error.is_some() {
break;
}
}
}
let scan_merge_ns = elapsed_nanos(merge_started.elapsed());
let table_bytes_read = table_cursors
.iter()
.map(|(_, cursor)| cursor.bytes_read)
.sum::<u64>();
let table_read_duration_ns = table_cursors
.iter()
.map(|(_, cursor)| cursor.read_duration_ns)
.sum::<u64>();
let scan_layers = table_cursors.len() as u64;
let lock_started = Instant::now();
let Ok(mut inner) = database.inner.lock() else {
return Iter {
entries: entries.into_iter(),
error: Some(Error::message("database lock poisoned")),
};
};
let validation_lock_wait_ns = elapsed_nanos(lock_started.elapsed());
let validation_lock_held_started = Instant::now();
let final_attempt = attempt == 3;
let generation_matches = inner.state_generation == snapshot.generation;
inner.diagnostics.scan_count = inner.diagnostics.scan_count.saturating_add(1);
inner.diagnostics.scan_keys_examined = inner
.diagnostics
.scan_keys_examined
.saturating_add(scan_keys_examined);
inner.diagnostics.scan_layers_consulted = inner
.diagnostics
.scan_layers_consulted
.saturating_add(scan_layers);
inner.diagnostics.scan_lock_wait_duration_ns = inner
.diagnostics
.scan_lock_wait_duration_ns
.saturating_add(scan_lock_wait_ns)
.saturating_add(validation_lock_wait_ns);
inner.diagnostics.scan_lock_held_duration_ns = inner
.diagnostics
.scan_lock_held_duration_ns
.saturating_add(scan_lock_held_ns)
.saturating_add(elapsed_nanos(validation_lock_held_started.elapsed()));
inner.diagnostics.scan_cursor_init_duration_ns = inner
.diagnostics
.scan_cursor_init_duration_ns
.saturating_add(snapshot.cursor_init_ns)
.saturating_add(cursor_init_ns);
inner.diagnostics.scan_merge_duration_ns = inner
.diagnostics
.scan_merge_duration_ns
.saturating_add(scan_merge_ns);
inner.diagnostics.scan_returned_entries = inner
.diagnostics
.scan_returned_entries
.saturating_add(if count_only {
counted_entries as u64
} else {
entries.len() as u64
});
inner.diagnostics.table_bytes_read = inner
.diagnostics
.table_bytes_read
.saturating_add(table_bytes_read);
inner.diagnostics.table_read_duration_ns = inner
.diagnostics
.table_read_duration_ns
.saturating_add(table_read_duration_ns);
inner.diagnostics.scan_duration_ns = inner
.diagnostics
.scan_duration_ns
.saturating_add(elapsed_nanos(scan_started.elapsed()));
if scan_error.is_some() || (final_attempt && !generation_matches) {
inner.diagnostics.scan_error_count =
inner.diagnostics.scan_error_count.saturating_add(1);
}
if let Some(error) = scan_error {
return Iter {
entries: entries.into_iter(),
error: Some(error),
};
}
if generation_matches {
if let Some(count) = count_output.as_deref_mut() {
*count = counted_entries;
}
return Iter {
entries: entries.into_iter(),
error: None,
};
}
if final_attempt {
return Iter {
entries: Vec::new().into_iter(),
error: Some(Error::message(
"ThingDB durable scan changed repeatedly while reading table blocks",
)),
};
}
let lock_wait_ns = elapsed_nanos(lock_started.elapsed());
let recapture_started = Instant::now();
let mut capture_metrics = DurableScanPageCaptureMetrics::default();
let next_snapshot = capture_durable_table_page(
&inner,
namespace,
prefix,
start.as_ref(),
end.as_ref(),
lock_wait_ns,
0,
count_only,
&mut capture_metrics,
);
capture_metrics.record(&mut inner.diagnostics);
let Some(next_snapshot) = next_snapshot else {
inner.diagnostics.scan_error_count =
inner.diagnostics.scan_error_count.saturating_add(1);
return Iter {
entries: Vec::new().into_iter(),
error: Some(Error::message(
"ThingDB durable scan changed to a state requiring compatibility scan",
)),
};
};
let next_lock_held_ns = elapsed_nanos(validation_lock_held_started.elapsed());
drop(inner);
snapshot = DurableScanPageSnapshot {
lock_held_ns: next_lock_held_ns,
cursor_init_ns: next_snapshot
.cursor_init_ns
.saturating_add(elapsed_nanos(recapture_started.elapsed())),
..next_snapshot
};
}
unreachable!("bounded ThingDB table scan retry loop exits explicitly")
}
fn next_map_key<V>(
map: &BTreeMap<Vec<u8>, V>,
lower: &[u8],
upper: Option<&[u8]>,
after: Option<&[u8]>,
) -> Option<Vec<u8>> {
let start = after.map_or_else(
|| Bound::Included(lower.to_vec()),
|key| Bound::Excluded(key.to_vec()),
);
let end = upper.map_or(Bound::Unbounded, |key| Bound::Excluded(key.to_vec()));
map.range((start, end)).next().map(|(key, _)| key.clone())
}
fn durable_scan_lower(
namespace: &[u8],
prefix: Option<&[u8]>,
start: Option<&(Vec<u8>, bool)>,
) -> Vec<u8> {
let user_key = match (prefix, start) {
(Some(prefix), Some((start, _))) if start.as_slice() >= prefix => start.as_slice(),
(Some(prefix), _) => prefix,
(None, Some((start, _))) => start.as_slice(),
(None, None) => &[],
};
physical_key_from_namespace(namespace, user_key)
}
#[allow(clippy::tuple_array_conversions)]
fn durable_scan_upper(
namespace: &[u8],
prefix: Option<&[u8]>,
end: Option<&(Vec<u8>, bool)>,
) -> Option<Vec<u8>> {
let namespace_end = successor(namespace);
let prefix_end = prefix
.and_then(successor)
.map(|prefix| physical_key_from_namespace(namespace, &prefix));
let explicit_end = end.and_then(|(end, inclusive)| {
let physical = physical_key_from_namespace(namespace, end);
if *inclusive {
successor(&physical)
} else {
Some(physical)
}
});
match (namespace_end, prefix_end, explicit_end) {
(namespace_end, None, None) => namespace_end,
(namespace_end, prefix_end, explicit_end) => [namespace_end, prefix_end, explicit_end]
.into_iter()
.flatten()
.min(),
}
}
fn iter_memory_bounds(
db: &Database,
ram_keyspaces: &Arc<RwLock<HashMap<Arc<str>, BTreeMap<Vec<u8>, Arc<Vec<u8>>>>>>,
name: &str,
bounds: ScanBounds<'_>,
) -> Iter {
let ScanBounds {
prefix,
start,
end,
offset,
limit,
} = bounds;
let iteration_started = Instant::now();
let mut entries = Vec::new();
let mut entries_examined = 0u64;
let mut entries_returned = 0u64;
if let Ok(keyspaces) = ram_keyspaces.read()
&& let Some(keyspace) = keyspaces.get(name)
{
let lower = match (start.as_ref(), prefix) {
(Some((start, inclusive)), Some(prefix)) if start.as_slice() >= prefix => {
if *inclusive {
Bound::Included(start.as_slice())
} else {
Bound::Excluded(start.as_slice())
}
},
(_, Some(prefix)) => Bound::Included(prefix),
(Some((start, inclusive)), None) => {
if *inclusive {
Bound::Included(start.as_slice())
} else {
Bound::Excluded(start.as_slice())
}
},
(None, None) => Bound::Unbounded,
};
let prefix_upper = prefix.and_then(successor);
let upper = match (end.as_ref(), prefix_upper.as_deref()) {
(Some((end, inclusive)), Some(prefix_upper)) if end.as_slice() <= prefix_upper => {
if *inclusive {
Bound::Included(end.as_slice())
} else {
Bound::Excluded(end.as_slice())
}
},
(Some((end, inclusive)), None) => {
if *inclusive {
Bound::Included(end.as_slice())
} else {
Bound::Excluded(end.as_slice())
}
},
(_, Some(prefix_upper)) => Bound::Excluded(prefix_upper),
(None, None) => Bound::Unbounded,
};
let mut skipped = 0usize;
for (key, value) in keyspace.range::<[u8], _>((lower, upper)) {
entries_examined = entries_examined.saturating_add(1);
if let Some(prefix) = prefix
&& !key.starts_with(prefix)
{
break;
}
if skipped < offset {
skipped += 1;
continue;
}
entries.push(Entry {
key: key.clone(),
value: value.as_ref().clone(),
});
entries_returned = entries_returned.saturating_add(1);
if limit.is_some_and(|limit| entries.len() >= limit) {
break;
}
}
}
let elapsed = elapsed_nanos(iteration_started.elapsed());
db.update_ram_diagnostics(|diagnostics| {
diagnostics.iteration_count = diagnostics.iteration_count.saturating_add(1);
diagnostics.iteration_duration_ns =
diagnostics.iteration_duration_ns.saturating_add(elapsed);
diagnostics.iteration_entries_examined = diagnostics
.iteration_entries_examined
.saturating_add(entries_examined);
diagnostics.iteration_entries_returned = diagnostics
.iteration_entries_returned
.saturating_add(entries_returned);
});
Iter {
entries: entries.into_iter(),
error: None,
}
}
fn count_memory_prefix(keyspace: &BTreeMap<Vec<u8>, Arc<Vec<u8>>>, prefix: &[u8]) -> usize {
keyspace
.range::<[u8], _>((Bound::Included(prefix), Bound::Unbounded))
.take_while(|(key, _)| key.starts_with(prefix))
.count()
}
#[cfg(feature = "benchmark")]
fn iter_memory_rcu_bounds(
db: &Database,
generation: Arc<RamGeneration>,
name: &str,
bounds: ScanBounds<'_>,
) -> Iter {
let ScanBounds {
prefix,
start,
end,
offset,
limit,
} = bounds;
let started = Instant::now();
let mut entries = Vec::new();
let mut examined = 0u64;
if let Some(keyspace) = generation.get(name) {
let lower = match (start.as_ref(), prefix) {
(Some((key, inclusive)), Some(prefix)) if key.as_slice() >= prefix => {
if *inclusive {
Bound::Included(key.as_slice())
} else {
Bound::Excluded(key.as_slice())
}
},
(_, Some(prefix)) => Bound::Included(prefix),
(Some((key, inclusive)), None) => {
if *inclusive {
Bound::Included(key.as_slice())
} else {
Bound::Excluded(key.as_slice())
}
},
(None, None) => Bound::Unbounded,
};
let prefix_upper = prefix.and_then(successor);
let upper = match (end.as_ref(), prefix_upper.as_deref()) {
(Some((key, inclusive)), Some(prefix_upper)) if key.as_slice() <= prefix_upper => {
if *inclusive {
Bound::Included(key.as_slice())
} else {
Bound::Excluded(key.as_slice())
}
},
(Some((key, inclusive)), None) => {
if *inclusive {
Bound::Included(key.as_slice())
} else {
Bound::Excluded(key.as_slice())
}
},
(_, Some(prefix_upper)) => Bound::Excluded(prefix_upper),
(None, None) => Bound::Unbounded,
};
let mut skipped = 0usize;
for (key, value) in keyspace.range::<[u8], _>((lower, upper)) {
examined = examined.saturating_add(1);
if prefix.is_some_and(|prefix| !key.starts_with(prefix)) {
break;
}
if skipped < offset {
skipped += 1;
continue;
}
entries.push(Entry {
key: key.clone(),
value: value.as_ref().clone(),
});
if limit.is_some_and(|limit| entries.len() >= limit) {
break;
}
}
}
let elapsed = elapsed_nanos(started.elapsed());
db.update_ram_diagnostics(|diagnostics| {
diagnostics.iteration_count = diagnostics.iteration_count.saturating_add(1);
diagnostics.iteration_duration_ns =
diagnostics.iteration_duration_ns.saturating_add(elapsed);
diagnostics.iteration_entries_examined = diagnostics
.iteration_entries_examined
.saturating_add(examined);
diagnostics.iteration_entries_returned = diagnostics
.iteration_entries_returned
.saturating_add(entries.len() as u64);
});
Iter {
entries: entries.into_iter(),
error: None,
}
}
impl Batch {
pub fn put(
mut self,
keyspace: &Keyspace,
key: impl AsRef<[u8]>,
value: impl AsRef<[u8]>,
) -> Self {
self.operations.push(BatchOperation {
keyspace: Arc::clone(&keyspace.name),
key: self.batch_key(keyspace, key.as_ref()),
value: Some(value.as_ref().to_vec()),
});
self
}
pub fn put_owned(mut self, keyspace: &Keyspace, key: Vec<u8>, value: Vec<u8>) -> Self {
self.operations.push(BatchOperation {
keyspace: Arc::clone(&keyspace.name),
key: self.batch_key(keyspace, &key),
value: Some(value),
});
self
}
pub fn delete(mut self, keyspace: &Keyspace, key: impl AsRef<[u8]>) -> Self {
self.operations.push(BatchOperation {
keyspace: Arc::clone(&keyspace.name),
key: self.batch_key(keyspace, key.as_ref()),
value: None,
});
self
}
pub fn delete_owned(mut self, keyspace: &Keyspace, key: Vec<u8>) -> Self {
self.operations.push(BatchOperation {
keyspace: Arc::clone(&keyspace.name),
key: self.batch_key(keyspace, &key),
value: None,
});
self
}
pub fn commit(self) -> Result<()> {
self.db.commit_batch(self.operations)
}
fn batch_key(&self, keyspace: &Keyspace, key: &[u8]) -> Vec<u8> {
if self.memory_mode {
key.to_vec()
} else {
physical_key_from_namespace(&keyspace.namespace, key)
}
}
}
impl Iterator for Iter {
type Item = Entry;
fn next(&mut self) -> Option<Self::Item> {
self.entries.next()
}
}
impl Snapshot {
pub fn keyspace(&self, name: &str) -> SnapshotKeyspace {
SnapshotKeyspace {
state: Arc::clone(&self.state),
name: name.to_string(),
}
}
}
pub struct SnapshotKeyspace {
state: Arc<BTreeMap<Vec<u8>, Vec<u8>>>,
name: String,
}
impl SnapshotKeyspace {
pub fn get(&self, key: impl AsRef<[u8]>) -> Option<Vec<u8>> {
self.state
.get(&physical_key(&self.name, key.as_ref()))
.cloned()
}
}
fn namespace(name: &str) -> Vec<u8> {
let mut bytes = name.as_bytes().to_vec();
bytes.push(0);
bytes
}
fn physical_key(name: &str, key: &[u8]) -> Vec<u8> {
physical_key_from_namespace(&namespace(name), key)
}
fn physical_key_from_namespace(namespace: &[u8], key: &[u8]) -> Vec<u8> {
let mut physical = namespace.to_vec();
physical.extend_from_slice(key);
physical
}
fn successor(key: &[u8]) -> Option<Vec<u8>> {
let mut result = key.to_vec();
for index in (0..result.len()).rev() {
if result[index] != u8::MAX {
result[index] += 1;
result.truncate(index + 1);
return Some(result);
}
}
None
}
fn encoded_frame_capacity(operations: &[Operation]) -> usize {
WAL_MAGIC
.len()
.saturating_add(8)
.saturating_add(8)
.saturating_add(4)
.saturating_add(
operations
.iter()
.map(|operation| match operation {
Operation::Put { key, value } => 1usize
.saturating_add(8)
.saturating_add(key.len())
.saturating_add(8)
.saturating_add(value.len()),
Operation::Delete { key } => 1usize
.saturating_add(8)
.saturating_add(key.len())
.saturating_add(8),
})
.sum(),
)
.saturating_add(4)
}
#[cfg(test)]
fn encode_frame(sequence: u64, operations: &[Operation]) -> Result<Vec<u8>> {
let mut frame = Vec::with_capacity(encoded_frame_capacity(operations));
encode_frame_into(&mut frame, sequence, operations)?;
Ok(frame)
}
fn encode_frame_into(output: &mut Vec<u8>, sequence: u64, operations: &[Operation]) -> Result<()> {
output.extend_from_slice(WAL_MAGIC);
let length_offset = output.len();
write_u64(output, 0);
let body_start = output.len();
write_u64(output, sequence);
write_u32(
output,
operations
.len()
.try_into()
.map_err(|_| Error::message("too many operations in batch"))?,
);
for operation in operations {
match operation {
Operation::Put { key, value } => {
output.push(1);
write_bytes(output, key)?;
write_bytes(output, value)?;
},
Operation::Delete { key } => {
output.push(2);
write_bytes(output, key)?;
write_u64(output, 0);
},
}
}
let checksum_offset = output.len();
let frame_checksum = checksum(&output[body_start..checksum_offset]);
write_u32(output, frame_checksum);
let frame_len: u64 = output
.len()
.saturating_sub(body_start)
.try_into()
.ok()
.ok_or_else(|| Error::message("WAL frame is too large"))?;
output[length_offset..length_offset + 8].copy_from_slice(&frame_len.to_be_bytes());
Ok(())
}
fn replay_wal(
wal: &mut File,
table_sequence: u64,
state: &mut BTreeMap<Vec<u8>, Vec<u8>>,
) -> Result<(u64, u64, u64)> {
wal.seek(SeekFrom::Start(0))?;
let mut bytes = Vec::new();
wal.read_to_end(&mut bytes)?;
let mut cursor = 0usize;
let mut last_sequence = table_sequence;
let mut frame_count = 0;
while cursor < bytes.len() {
let frame_start = cursor;
if bytes.len() - cursor < WAL_MAGIC.len() + 8 {
return Ok((last_sequence, frame_start as u64, frame_count));
}
if &bytes[cursor..cursor + WAL_MAGIC.len()] != WAL_MAGIC {
return Err(Error::message("invalid ThingDB WAL magic"));
}
cursor += WAL_MAGIC.len();
let frame_len = read_u64(&bytes, &mut cursor)? as usize;
if frame_len < 12 {
return Err(Error::message("invalid ThingDB WAL frame length"));
}
if frame_len > bytes.len().saturating_sub(cursor) {
return Ok((last_sequence, frame_start as u64, frame_count));
}
let frame_end = cursor + frame_len;
let sequence = read_u64(&bytes, &mut cursor)?;
let count = read_u32(&bytes, &mut cursor)? as usize;
let mut operations = Vec::with_capacity(count);
for _ in 0..count {
let kind = read_byte(&bytes, &mut cursor)?;
let key = read_bytes(&bytes, &mut cursor)?;
let value = read_bytes(&bytes, &mut cursor)?;
operations.push(match kind {
1 => Operation::Put { key, value },
2 => Operation::Delete { key },
_ => return Err(Error::message("invalid ThingDB WAL operation")),
});
}
let checksum_offset = frame_end
.checked_sub(4)
.ok_or_else(|| Error::message("invalid ThingDB WAL frame"))?;
if cursor != checksum_offset {
return Err(Error::message("invalid ThingDB WAL payload length"));
}
let stored_checksum = u32::from_be_bytes(
bytes[checksum_offset..frame_end]
.try_into()
.map_err(|_| Error::message("invalid ThingDB WAL checksum"))?,
);
let actual_checksum = checksum(&bytes[frame_start + WAL_MAGIC.len() + 8..checksum_offset]);
if stored_checksum != actual_checksum {
return Err(Error::message("ThingDB WAL checksum mismatch"));
}
if sequence > last_sequence {
for operation in operations {
apply_operation(state, operation);
}
last_sequence = sequence;
}
frame_count += 1;
cursor = frame_end;
}
Ok((last_sequence, cursor as u64, frame_count))
}
fn elapsed_nanos(duration: std::time::Duration) -> u64 {
u64::try_from(duration.as_nanos()).unwrap_or(u64::MAX)
}
fn apply_operation(state: &mut BTreeMap<Vec<u8>, Vec<u8>>, operation: Operation) {
match operation {
Operation::Put { key, value } => {
state.insert(key, value);
},
Operation::Delete { key } => {
state.remove(&key);
},
}
}
fn apply_memory_operation(
keyspaces: &mut HashMap<Arc<str>, BTreeMap<Vec<u8>, Arc<Vec<u8>>>>,
operation: Operation,
) -> Result<()> {
let (key, value) = match operation {
Operation::Put { key, value } => (key, Some(value)),
Operation::Delete { key } => (key, None),
};
let separator = key
.iter()
.position(|byte| *byte == 0)
.ok_or_else(|| Error::message("invalid ThingDB in-memory key"))?;
let name = std::str::from_utf8(&key[..separator])
.map_err(|_| Error::message("invalid ThingDB in-memory keyspace"))?;
let user_key = &key[separator + 1..];
let entries = keyspaces.entry(Arc::from(name)).or_default();
match value {
Some(value) => {
entries.insert(user_key.to_vec(), Arc::new(value));
},
None => {
entries.remove(user_key);
},
}
Ok(())
}
fn validate_memory_batch_operation(operation: &BatchOperation) -> Result<()> {
if operation.keyspace.is_empty() || operation.keyspace.as_bytes().contains(&0) {
return Err(Error::message("invalid ThingDB in-memory keyspace"));
}
Ok(())
}
fn apply_memory_batch_operation(
keyspaces: &mut HashMap<Arc<str>, BTreeMap<Vec<u8>, Arc<Vec<u8>>>>,
operation: BatchOperation,
) {
let entries = keyspaces.entry(operation.keyspace.clone()).or_default();
match operation.value {
Some(value) => {
entries.insert(operation.key, Arc::new(value));
},
None => {
entries.remove(&operation.key);
},
}
}
fn validate_memory_operation(operation: &Operation) -> Result<()> {
let key = match operation {
Operation::Put { key, .. } | Operation::Delete { key } => key,
};
let separator = key
.iter()
.position(|byte| *byte == 0)
.ok_or_else(|| Error::message("invalid ThingDB in-memory key"))?;
std::str::from_utf8(&key[..separator])
.map_err(|_| Error::message("invalid ThingDB in-memory keyspace"))?;
Ok(())
}
fn apply_operation_with_pending(
state: &mut BTreeMap<Vec<u8>, Vec<u8>>,
pending: &mut BTreeMap<Vec<u8>, Option<Vec<u8>>>,
pending_bytes: &mut u64,
operation: Operation,
) {
match operation {
Operation::Put { key, value } => {
let key_bytes = key.len() as u64;
let value_bytes = value.len() as u64;
state.insert(key.clone(), value.clone());
if let Some(previous) = pending.insert(key, Some(value)) {
*pending_bytes = pending_bytes.saturating_sub(
key_bytes
.saturating_add(1)
.saturating_add(previous.as_ref().map_or(0, |value| value.len() as u64)),
);
}
*pending_bytes = pending_bytes
.saturating_add(key_bytes.saturating_add(1).saturating_add(value_bytes));
},
Operation::Delete { key } => {
let key_bytes = key.len() as u64;
state.remove(&key);
if let Some(previous) = pending.insert(key, None) {
*pending_bytes = pending_bytes.saturating_sub(
key_bytes
.saturating_add(1)
.saturating_add(previous.as_ref().map_or(0, |value| value.len() as u64)),
);
}
*pending_bytes = pending_bytes.saturating_add(key_bytes.saturating_add(1));
},
}
}
fn write_table(
path: &Path,
sequence: u64,
entries: &BTreeMap<Vec<u8>, Option<Vec<u8>>>,
sync: bool,
) -> Result<()> {
const TABLE_WRITE_BUFFER_BYTES: usize = 64 * 1024;
let mut file = File::create(path)?;
let mut buffer = Vec::with_capacity(TABLE_WRITE_BUFFER_BYTES);
let mut block_first_key = None;
let mut block_last_key = None;
let mut block_offset = (TABLE_MAGIC_V3.len() + 16) as u64;
let mut blocks = Vec::new();
let entry_count: u64 = entries
.len()
.try_into()
.map_err(|_| Error::message("too many entries in ThingDB table"))?;
file.write_all(TABLE_MAGIC_V3)?;
file.write_all(&sequence.to_be_bytes())?;
file.write_all(&entry_count.to_be_bytes())?;
for (key, value) in entries {
let mut record = Vec::new();
write_bytes(&mut record, key)?;
match value {
Some(value) => {
record.push(1);
write_bytes(&mut record, value)?;
},
None => record.push(2),
}
let record_checksum = checksum(&record);
write_u32(&mut record, record_checksum);
if buffer.len().saturating_add(record.len()) > TABLE_WRITE_BUFFER_BYTES
&& !buffer.is_empty()
{
file.write_all(&buffer)?;
blocks.push((
block_offset,
buffer.len() as u64,
block_first_key
.take()
.ok_or_else(|| Error::message("ThingDB table block has no first key"))?,
block_last_key
.take()
.ok_or_else(|| Error::message("ThingDB table block has no last key"))?,
checksum(&buffer),
));
block_offset = block_offset.saturating_add(buffer.len() as u64);
buffer.clear();
}
if block_first_key.is_none() {
block_first_key = Some(key.clone());
}
block_last_key = Some(key.clone());
buffer.extend_from_slice(&record);
}
if !buffer.is_empty() {
file.write_all(&buffer)?;
blocks.push((
block_offset,
buffer.len() as u64,
block_first_key
.take()
.ok_or_else(|| Error::message("ThingDB table block has no first key"))?,
block_last_key
.take()
.ok_or_else(|| Error::message("ThingDB table block has no last key"))?,
checksum(&buffer),
));
}
let footer_start = block_offset.saturating_add(buffer.len() as u64);
let mut footer = Vec::new();
footer.extend_from_slice(TABLE_FOOTER_MAGIC);
footer.extend_from_slice(&(blocks.len() as u64).to_be_bytes());
for (offset, length, first_key, last_key, block_checksum) in &blocks {
footer.extend_from_slice(&offset.to_be_bytes());
footer.extend_from_slice(&length.to_be_bytes());
write_bytes(&mut footer, first_key)?;
write_bytes(&mut footer, last_key)?;
write_u32(&mut footer, *block_checksum);
}
let footer_checksum = checksum(&footer);
write_u32(&mut footer, footer_checksum);
debug_assert_eq!(footer_start, file.metadata()?.len());
file.write_all(&footer)?;
if sync {
file.sync_all()?;
}
Ok(())
}
fn read_table_index(path: &Path) -> Result<(u64, Vec<TableIndexEntry>, bool, Vec<TableBlock>)> {
let bytes = fs::read(path)?;
if bytes.len() < TABLE_MAGIC.len() + 16
|| (&bytes[..TABLE_MAGIC.len()] != TABLE_MAGIC
&& &bytes[..TABLE_MAGIC_V2.len()] != TABLE_MAGIC_V2
&& &bytes[..TABLE_MAGIC_V3.len()] != TABLE_MAGIC_V3)
{
return Err(Error::message("invalid ThingDB table"));
}
let version = &bytes[..TABLE_MAGIC.len()];
let is_v2 = version != TABLE_MAGIC;
let is_v3 = version == TABLE_MAGIC_V3;
let mut cursor = TABLE_MAGIC.len();
let sequence = read_u64(&bytes, &mut cursor)?;
let count = read_u64(&bytes, &mut cursor)? as usize;
let mut entries = Vec::with_capacity(count);
for _ in 0..count {
if is_v3
&& bytes.get(cursor..cursor + TABLE_FOOTER_MAGIC.len())
== Some(TABLE_FOOTER_MAGIC.as_slice())
{
return Err(Error::message(
"ThingDB table footer appears before all records",
));
}
let record_start = cursor;
let key = read_bytes(&bytes, &mut cursor)?;
let value = if is_v2 {
match read_byte(&bytes, &mut cursor)? {
1 => Some(read_bytes(&bytes, &mut cursor)?),
2 => None,
_ => return Err(Error::message("invalid ThingDB table operation")),
}
} else {
Some(read_bytes(&bytes, &mut cursor)?)
};
let checksum_end = cursor;
let stored = read_u32(&bytes, &mut cursor)?;
let actual = checksum(&bytes[record_start..checksum_end]);
if stored != actual {
return Err(Error::message("ThingDB table checksum mismatch"));
}
entries.push(TableIndexEntry {
key,
offset: record_start as u64,
length: (cursor - record_start) as u64,
});
let _ = value;
}
if entries
.windows(2)
.any(|entries| entries[0].key >= entries[1].key)
{
return Err(Error::message(
"ThingDB table keys are not strictly ordered",
));
}
if is_v3 {
let footer_start = bytes
.get(cursor..cursor + TABLE_FOOTER_MAGIC.len())
.is_some_and(|magic| magic == TABLE_FOOTER_MAGIC.as_slice())
.then_some(cursor)
.ok_or_else(|| Error::message("ThingDB table is missing its validated footer"))?;
let blocks = validate_table_footer(&bytes, footer_start)?;
return Ok((sequence, entries, is_v2, blocks));
}
if cursor != bytes.len() {
return Err(Error::message("trailing bytes in ThingDB table"));
}
Ok((sequence, entries, is_v2, Vec::new()))
}
fn read_table_metadata(path: &Path) -> Result<(u64, Vec<TableIndexEntry>, bool, Vec<TableBlock>)> {
let bytes = fs::read(path)?;
if bytes.len() < TABLE_MAGIC.len() + 16
|| (&bytes[..TABLE_MAGIC.len()] != TABLE_MAGIC
&& &bytes[..TABLE_MAGIC_V2.len()] != TABLE_MAGIC_V2
&& &bytes[..TABLE_MAGIC_V3.len()] != TABLE_MAGIC_V3)
{
return Err(Error::message("invalid ThingDB table"));
}
let version = &bytes[..TABLE_MAGIC.len()];
let mut cursor = TABLE_MAGIC.len();
let sequence = read_u64(&bytes, &mut cursor)?;
if version != TABLE_MAGIC_V3 {
let (sequence, entries, is_v2, blocks) = read_table_index(path)?;
return Ok((sequence, entries, is_v2, blocks));
}
let (_, _, _, blocks) = read_table_index(path)?;
Ok((sequence, Vec::new(), true, blocks))
}
fn validate_table_footer(bytes: &[u8], footer_start: usize) -> Result<Vec<TableBlock>> {
let mut cursor = footer_start;
if bytes.get(cursor..cursor + TABLE_FOOTER_MAGIC.len()) != Some(TABLE_FOOTER_MAGIC.as_slice()) {
return Err(Error::message("invalid ThingDB table footer"));
}
cursor += TABLE_FOOTER_MAGIC.len();
let block_count = read_u64(bytes, &mut cursor)? as usize;
let mut previous_offset = None;
let mut previous_end = None;
let data_start = (TABLE_MAGIC_V3.len() + 16) as u64;
let mut blocks = Vec::with_capacity(block_count);
for _ in 0..block_count {
let offset = read_u64(bytes, &mut cursor)?;
let length = read_u64(bytes, &mut cursor)?;
let first_key = read_bytes(bytes, &mut cursor)?;
let last_key = read_bytes(bytes, &mut cursor)?;
let block_checksum = read_u32(bytes, &mut cursor)?;
let block_end = offset
.checked_add(length)
.ok_or_else(|| Error::message("ThingDB table block range overflow"))?;
let footer_start_u64 = footer_start as u64;
if offset < data_start
|| block_end > footer_start_u64
|| previous_offset.is_some_and(|previous| offset <= previous)
|| previous_end.is_some_and(|previous| offset != previous)
|| first_key > last_key
{
return Err(Error::message("invalid ThingDB table block metadata"));
}
let start: usize = offset
.try_into()
.map_err(|_| Error::message("ThingDB table block offset is too large"))?;
let end: usize = block_end
.try_into()
.map_err(|_| Error::message("ThingDB table block end is too large"))?;
if checksum(&bytes[start..end]) != block_checksum {
return Err(Error::message("ThingDB table block checksum mismatch"));
}
previous_offset = Some(offset);
previous_end = Some(block_end);
blocks.push(TableBlock {
offset,
length,
first_key,
last_key,
checksum: block_checksum,
});
}
if block_count > 0 && (previous_end != Some(footer_start as u64)) {
return Err(Error::message(
"ThingDB table blocks do not cover the data area",
));
}
let stored_checksum = read_u32(bytes, &mut cursor)?;
if stored_checksum != checksum(&bytes[footer_start..cursor - 4]) {
return Err(Error::message("ThingDB table footer checksum mismatch"));
}
if cursor != bytes.len() {
return Err(Error::message("trailing bytes after ThingDB table footer"));
}
Ok(blocks)
}
#[cfg(not(unix))]
fn read_table_value(
file: &mut File,
entry: &TableIndexEntry,
is_v2: bool,
) -> Result<Option<Vec<u8>>> {
file.seek(SeekFrom::Start(entry.offset))?;
let length: usize = entry
.length
.try_into()
.map_err(|_| Error::message("ThingDB table record is too large"))?;
let mut bytes = vec![0; length];
file.read_exact(&mut bytes)?;
let mut cursor = 0;
let key = read_bytes(&bytes, &mut cursor)?;
if key != entry.key {
return Err(Error::message("ThingDB table index key mismatch"));
}
let value = if !is_v2 {
Some(read_bytes(&bytes, &mut cursor)?)
} else if bytes.get(cursor) == Some(&1) {
cursor += 1;
Some(read_bytes(&bytes, &mut cursor)?)
} else if bytes.get(cursor) == Some(&2) {
cursor += 1;
None
} else {
return Err(Error::message("invalid ThingDB table operation"));
};
let checksum_offset = cursor;
let stored = read_u32(&bytes, &mut cursor)?;
if stored != checksum(&bytes[..checksum_offset]) {
return Err(Error::message("ThingDB table checksum mismatch"));
}
if cursor != bytes.len() {
return Err(Error::message("trailing bytes in ThingDB table record"));
}
Ok(value)
}
fn read_table_value_handle(
file: &Arc<File>,
entry: &TableIndexEntry,
is_v2: bool,
) -> Result<(Option<Vec<u8>>, u64, u64)> {
let reader_wait = 0;
let read_started = Instant::now();
#[cfg(unix)]
let value = {
let length: usize = entry
.length
.try_into()
.map_err(|_| Error::message("ThingDB table record is too large"))?;
let mut bytes = vec![0; length];
file.read_exact_at(&mut bytes, entry.offset)?;
decode_table_value(&bytes, entry, is_v2)
};
#[cfg(not(unix))]
let value = {
let mut reader = file.try_clone()?;
read_table_value(&mut reader, entry, is_v2)
};
let read_duration = elapsed_nanos(read_started.elapsed());
Ok((value?, reader_wait, read_duration))
}
fn read_cached_table_block(
layer: &TableLayer,
block: &TableBlock,
) -> Result<(Arc<Vec<u8>>, u64, u64)> {
let cache_key = TableBlockCacheKey {
path: layer.path.clone(),
offset: block.offset,
};
if let Some(bytes) = layer.block_cache.get(&cache_key) {
return Ok((bytes, 0, 0));
}
let started = Instant::now();
let length: usize = block
.length
.try_into()
.map_err(|_| Error::message("ThingDB table block is too large"))?;
let mut bytes = vec![0; length];
#[cfg(unix)]
layer.file.read_exact_at(&mut bytes, block.offset)?;
#[cfg(not(unix))]
{
let mut reader = layer.file.try_clone()?;
reader.seek(SeekFrom::Start(block.offset))?;
reader.read_exact(&mut bytes)?;
}
if checksum(&bytes) != block.checksum {
return Err(Error::message("ThingDB table block checksum mismatch"));
}
let read_duration = elapsed_nanos(started.elapsed());
let bytes = Arc::new(bytes);
layer.block_cache.insert(cache_key, Arc::clone(&bytes));
Ok((bytes, block.length, read_duration))
}
fn read_table_block_records(
layer: &TableLayer,
block: &TableBlock,
include_values: bool,
) -> Result<(Arc<Vec<TableScanRecord>>, u64, u64)> {
let cache_key = TableBlockCacheKey {
path: layer.path.clone(),
offset: block.offset,
};
if let Some(records) = layer.block_cache.get_records(&cache_key) {
return Ok((records, 0, 0));
}
let (bytes, bytes_read, read_duration) = read_cached_table_block(layer, block)?;
let mut records = Vec::new();
let mut cursor = 0;
while cursor < bytes.len() {
let record_start = cursor;
let key = read_bytes(&bytes, &mut cursor)?;
let value = match read_byte(&bytes, &mut cursor)? {
1 if include_values => Some(read_bytes(&bytes, &mut cursor)?),
1 => {
skip_bytes(&bytes, &mut cursor)?;
Some(Vec::new())
},
2 => None,
_ => return Err(Error::message("invalid ThingDB table operation")),
};
let checksum_end = cursor;
let stored = read_u32(&bytes, &mut cursor)?;
if stored != checksum(&bytes[record_start..checksum_end]) {
return Err(Error::message("ThingDB table checksum mismatch"));
}
if records
.last()
.is_some_and(|record: &TableScanRecord| record.key >= key)
{
return Err(Error::message(
"ThingDB table block keys are not strictly ordered",
));
}
records.push(TableScanRecord {
key,
value,
priority: 0,
});
}
if records.first().map(|record| &record.key) != Some(&block.first_key)
|| records.last().map(|record| &record.key) != Some(&block.last_key)
{
return Err(Error::message(
"ThingDB table block key range does not match its index",
));
}
let records = Arc::new(records);
if include_values {
layer
.block_cache
.insert_records(&cache_key, Arc::clone(&records));
}
Ok((records, bytes_read, read_duration))
}
fn read_table_block_entry_value(
layer: &TableLayer,
block: &TableBlock,
entry: &TableIndexEntry,
) -> Result<(Option<Option<Vec<u8>>>, u64, u64)> {
let (bytes, bytes_read, read_duration) = read_cached_table_block(layer, block)?;
let offset: usize = entry
.offset
.checked_sub(block.offset)
.ok_or_else(|| Error::message("ThingDB table index precedes its block"))?
.try_into()
.map_err(|_| Error::message("ThingDB table index offset is too large"))?;
let length: usize = entry
.length
.try_into()
.map_err(|_| Error::message("ThingDB table record is too large"))?;
let end = offset
.checked_add(length)
.ok_or_else(|| Error::message("ThingDB table record range overflow"))?;
let record = bytes
.get(offset..end)
.ok_or_else(|| Error::message("ThingDB table index record is outside its block"))?;
let mut cursor = 0;
let key = read_bytes(record, &mut cursor)?;
if key != entry.key {
return Err(Error::message("ThingDB table index key mismatch"));
}
let value = match read_byte(record, &mut cursor)? {
1 => Some(read_bytes(record, &mut cursor)?),
2 => None,
_ => return Err(Error::message("invalid ThingDB table operation")),
};
let checksum_end = cursor;
let stored = read_u32(record, &mut cursor)?;
if stored != checksum(&record[..checksum_end]) {
return Err(Error::message("ThingDB table checksum mismatch"));
}
if cursor != record.len() {
return Err(Error::message("trailing bytes in ThingDB table record"));
}
Ok((Some(value), bytes_read, read_duration))
}
#[cfg(unix)]
fn decode_table_value(
bytes: &[u8],
entry: &TableIndexEntry,
is_v2: bool,
) -> Result<Option<Vec<u8>>> {
let mut cursor = 0;
let key = read_bytes(bytes, &mut cursor)?;
if key != entry.key {
return Err(Error::message("ThingDB table index key mismatch"));
}
let value = if !is_v2 {
Some(read_bytes(bytes, &mut cursor)?)
} else if bytes.get(cursor) == Some(&1) {
cursor += 1;
Some(read_bytes(bytes, &mut cursor)?)
} else if bytes.get(cursor) == Some(&2) {
cursor += 1;
None
} else {
return Err(Error::message("invalid ThingDB table operation"));
};
let checksum_offset = cursor;
let stored = read_u32(bytes, &mut cursor)?;
if stored != checksum(&bytes[..checksum_offset]) {
return Err(Error::message("ThingDB table checksum mismatch"));
}
if cursor != bytes.len() {
return Err(Error::message("trailing bytes in ThingDB table record"));
}
Ok(value)
}
fn write_manifest(path: &Path, manifest: &Manifest, sync: bool) -> Result<()> {
let bytes = serde_json::to_vec_pretty(manifest)?;
let temp = path.join(MANIFEST_TEMP_FILE);
let final_path = path.join(MANIFEST_FILE);
let mut file = File::create(&temp)?;
file.write_all(&bytes)?;
if sync {
file.sync_all()?;
}
maybe_fail("after-manifest-sync-before-rename", current_fault_point())?;
fs::rename(temp, final_path)?;
if sync {
sync_directory(path)?;
}
Ok(())
}
#[cfg(unix)]
fn sync_directory(path: &Path) -> Result<()> {
OpenOptions::new().read(true).open(path)?.sync_all()?;
Ok(())
}
#[cfg(not(unix))]
fn sync_directory(_path: &Path) -> Result<()> {
Ok(())
}
fn checksum(bytes: &[u8]) -> u32 {
let mut hasher = Hasher::new();
hasher.update(bytes);
hasher.finalize()
}
fn write_u32(output: &mut Vec<u8>, value: u32) {
output.extend_from_slice(&value.to_be_bytes());
}
fn write_u64(output: &mut Vec<u8>, value: u64) {
output.extend_from_slice(&value.to_be_bytes());
}
fn write_bytes(output: &mut Vec<u8>, bytes: &[u8]) -> Result<()> {
let length: u64 = bytes
.len()
.try_into()
.map_err(|_| Error::message("ThingDB value is too large"))?;
write_u64(output, length);
output.extend_from_slice(bytes);
Ok(())
}
fn read_byte(bytes: &[u8], cursor: &mut usize) -> Result<u8> {
if *cursor >= bytes.len() {
return Err(Error::message("truncated ThingDB record"));
}
let value = bytes[*cursor];
*cursor += 1;
Ok(value)
}
fn read_u32(bytes: &[u8], cursor: &mut usize) -> Result<u32> {
let end = cursor
.checked_add(4)
.ok_or_else(|| Error::message("ThingDB length overflow"))?;
let value = bytes
.get(*cursor..end)
.ok_or_else(|| Error::message("truncated ThingDB record"))?;
*cursor = end;
Ok(u32::from_be_bytes(
value
.try_into()
.map_err(|_| Error::message("invalid ThingDB integer"))?,
))
}
fn read_u64(bytes: &[u8], cursor: &mut usize) -> Result<u64> {
let end = cursor
.checked_add(8)
.ok_or_else(|| Error::message("ThingDB length overflow"))?;
let value = bytes
.get(*cursor..end)
.ok_or_else(|| Error::message("truncated ThingDB record"))?;
*cursor = end;
Ok(u64::from_be_bytes(
value
.try_into()
.map_err(|_| Error::message("invalid ThingDB integer"))?,
))
}
fn read_bytes(bytes: &[u8], cursor: &mut usize) -> Result<Vec<u8>> {
let length = read_u64(bytes, cursor)?;
let length: usize = length
.try_into()
.map_err(|_| Error::message("ThingDB value length does not fit platform"))?;
let end = cursor
.checked_add(length)
.ok_or_else(|| Error::message("ThingDB value length overflow"))?;
let value = bytes
.get(*cursor..end)
.ok_or_else(|| Error::message("truncated ThingDB value"))?
.to_vec();
*cursor = end;
Ok(value)
}
fn skip_bytes(bytes: &[u8], cursor: &mut usize) -> Result<()> {
let length = read_u64(bytes, cursor)?;
let length: usize = length
.try_into()
.map_err(|_| Error::message("ThingDB value length does not fit platform"))?;
let end = cursor
.checked_add(length)
.ok_or_else(|| Error::message("ThingDB value length overflow"))?;
if end > bytes.len() {
return Err(Error::message("truncated ThingDB value"));
}
*cursor = end;
Ok(())
}
#[cfg(test)]
mod tests {
use super::*;
use std::fs::OpenOptions;
#[test]
fn in_memory_database_is_ordered_atomic_and_non_durable() {
let directory = tempfile::tempdir().unwrap();
let db = Database::in_memory().unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
let events = db
.keyspace("events", KeyspaceCreateOptions::default)
.unwrap();
db.batch()
.put(&objects, b"b", b"two")
.put(&events, b"1", b"event")
.put(&objects, b"a", b"one")
.commit()
.unwrap();
let snapshot = db.snapshot().unwrap();
objects.insert(b"a", b"updated").unwrap();
assert_eq!(
snapshot.keyspace("objects").get(b"a"),
Some(b"one".to_vec())
);
assert_eq!(objects.get(b"a").unwrap(), Some(b"updated".to_vec()));
assert_eq!(
objects
.prefix(b"")
.map(|entry| entry.key)
.collect::<Vec<_>>(),
vec![b"a".to_vec(), b"b".to_vec()]
);
assert_eq!(
objects
.range_bounds(Some((b"a", true)), Some((b"a", true)))
.count(),
1
);
assert_eq!(events.get(b"1").unwrap(), Some(b"event".to_vec()));
let diagnostics = db.wal_diagnostics().unwrap();
assert_eq!(diagnostics.journal_bytes, 0);
assert_eq!(diagnostics.frame_count, 0);
assert_eq!(diagnostics.physical_sync_count, 0);
assert_eq!(diagnostics.recovery_bytes, 0);
assert_eq!(diagnostics.flush_count, 0);
assert_eq!(db.journal_disk_space().unwrap(), 0);
assert_eq!(db.journal_count(), 0);
assert!(db.persist(PersistMode::SyncAll).is_err());
assert!(db.compact().is_err());
assert!(directory.path().read_dir().unwrap().next().is_none());
}
#[test]
fn in_memory_instances_are_isolated_and_batches_share_one_state_boundary() {
let first = Database::in_memory().unwrap();
let second = Database::in_memory().unwrap();
let first_objects = first
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
let second_objects = second
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
first_objects.insert(b"only-first", b"value").unwrap();
first
.batch()
.put(&first_objects, b"a", b"one")
.put(&first_objects, b"b", b"two")
.commit()
.unwrap();
assert!(second_objects.get(b"only-first").unwrap().is_none());
assert_eq!(first_objects.iter().count(), 3);
let diagnostics = first.wal_diagnostics().unwrap();
assert_eq!(diagnostics.logical_commit_count, 2);
assert_eq!(diagnostics.total_group_size, 2);
assert_eq!(diagnostics.physical_sync_count, 0);
}
#[test]
fn in_memory_commits_bypass_durable_coordination() {
let db = Database::in_memory().unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
for index in 0..128u16 {
objects
.insert(index.to_be_bytes(), index.to_be_bytes())
.unwrap();
}
let diagnostics = db.wal_diagnostics().unwrap();
assert_eq!(diagnostics.physical_sync_count, 0);
assert_eq!(diagnostics.queue_wait_duration_ns, 0);
assert_eq!(diagnostics.journal_bytes, 0);
assert_eq!(diagnostics.frame_count, 0);
assert_eq!(objects.iter().count(), 128);
}
#[test]
fn in_memory_keyspaces_use_isolated_fast_lookup_state() {
let db = Database::in_memory().unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
let events = db
.keyspace("events", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"same-key", b"object").unwrap();
events.insert(b"same-key", b"event").unwrap();
assert_eq!(objects.get(b"same-key").unwrap(), Some(b"object".to_vec()));
assert_eq!(events.get(b"same-key").unwrap(), Some(b"event".to_vec()));
let diagnostics = db.ram_diagnostics().unwrap();
assert_eq!(diagnostics.lookup_count, 2);
assert!(diagnostics.lock_held_duration_ns > 0);
assert_eq!(db.journal_disk_space().unwrap(), 0);
assert_eq!(db.journal_count(), 0);
}
#[test]
fn in_memory_with_value_reads_through_borrowed_value_boundary() {
let db = Database::in_memory().unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"key", b"value").unwrap();
let value = objects
.with_value(b"key", |value| {
Ok(value.map(|value| String::from_utf8_lossy(value).into_owned()))
})
.unwrap();
assert_eq!(value.as_deref(), Some("value"));
}
#[test]
fn in_memory_bounded_iterations_use_ordered_bounds() {
let db = Database::in_memory().unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
for key in [b"a-1".as_slice(), b"a-2", b"b-1", b"c-1"] {
objects.insert(key, key).unwrap();
}
let entries = objects
.range_bounds(Some((b"a-2", true)), Some((b"c-1", false)))
.into_result()
.unwrap();
assert_eq!(
entries
.iter()
.map(|entry| entry.key.as_slice())
.collect::<Vec<_>>(),
vec![b"a-2".as_slice(), b"b-1"]
);
let prefix = objects.prefix(b"b-").into_result().unwrap();
assert_eq!(prefix.len(), 1);
let diagnostics = db.ram_diagnostics().unwrap();
assert_eq!(diagnostics.iteration_count, 2);
assert_eq!(diagnostics.iteration_entries_examined, 3);
assert_eq!(diagnostics.iteration_entries_returned, 3);
}
#[test]
fn in_memory_prefix_page_only_materializes_the_requested_page() {
let db = Database::in_memory().unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
for index in 0..1_000_u32 {
let key = format!("collection/{index:04}");
objects.insert(key.as_bytes(), b"payload").unwrap();
}
let before = db.ram_diagnostics().unwrap().iteration_entries_examined;
let page: Vec<_> = objects
.prefix_page(b"collection/", 50, 25)
.map(|entry| entry.key)
.collect();
let examined = db
.ram_diagnostics()
.unwrap()
.iteration_entries_examined
.saturating_sub(before);
assert_eq!(page.len(), 25);
assert_eq!(page.first(), Some(&b"collection/0050".to_vec()));
assert_eq!(page.last(), Some(&b"collection/0074".to_vec()));
assert_eq!(examined, 75);
assert!(objects.prefix_page(b"collection/", 0, 0).next().is_none());
}
#[test]
fn in_memory_prefix_page_after_uses_an_exclusive_cursor() {
let db = Database::in_memory().unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
for index in 0..1_000_u32 {
let key = format!("collection/{index:04}");
objects.insert(key.as_bytes(), b"payload").unwrap();
}
let before = db.ram_diagnostics().unwrap().iteration_entries_examined;
let page: Vec<_> = objects
.prefix_page_after(b"collection/", Some(b"collection/0050"), 25)
.map(|entry| entry.key)
.collect();
let examined = db
.ram_diagnostics()
.unwrap()
.iteration_entries_examined
.saturating_sub(before);
assert_eq!(page.len(), 25);
assert_eq!(page.first(), Some(&b"collection/0051".to_vec()));
assert_eq!(page.last(), Some(&b"collection/0075".to_vec()));
assert_eq!(examined, 25);
assert!(
objects
.prefix_page_after(b"collection/", Some(b"collection/0050"), 0)
.next()
.is_none()
);
}
#[test]
fn in_memory_counts_do_not_materialize_values() {
let db = Database::in_memory().unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
for index in 0..1_000_u32 {
let key = format!("collection/{index:04}");
objects.insert(key.as_bytes(), b"large-ish-value").unwrap();
}
let before = db.ram_diagnostics().unwrap().iteration_count;
assert_eq!(objects.count().unwrap(), 1_000);
assert_eq!(objects.count_prefix(b"collection/00").unwrap(), 100);
assert_eq!(objects.count_prefix(b"missing/").unwrap(), 0);
assert_eq!(db.ram_diagnostics().unwrap().iteration_count, before);
}
#[test]
fn in_memory_first_prefix_after_honors_result_limit() {
let db = Database::in_memory().unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
for index in 0..1024u16 {
let key = format!("queue\0{index:04}");
objects.insert(key.as_bytes(), b"job").unwrap();
}
let entry = objects
.first_prefix_after(b"queue\0", None)
.unwrap()
.expect("prefix should contain an entry");
let expected = "queue\0".to_string() + "0000";
assert_eq!(entry.key, expected.as_bytes());
let diagnostics = db.ram_diagnostics().unwrap();
assert_eq!(diagnostics.iteration_entries_returned, 1);
assert_eq!(diagnostics.iteration_entries_examined, 1);
}
#[test]
fn in_memory_shared_reads_survive_mutation_after_lookup() {
let db = Database::in_memory().unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"key", b"before").unwrap();
let shared = objects.get_shared(b"key").unwrap().unwrap();
objects.insert(b"key", b"after").unwrap();
assert_eq!(shared.as_slice(), b"before");
assert_eq!(objects.get(b"key").unwrap(), Some(b"after".to_vec()));
assert!(db.ram_diagnostics().unwrap().lookup_count >= 1);
}
#[test]
fn in_memory_batched_shared_reads_preserve_order_duplicates_and_snapshot_values() {
let db = Database::in_memory().unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
db.batch()
.put(&objects, b"a", b"one")
.put(&objects, b"b", b"two")
.commit()
.unwrap();
let keys = vec![
b"b".to_vec(),
b"missing".to_vec(),
b"a".to_vec(),
b"b".to_vec(),
];
let values = objects.get_many_shared(&keys).unwrap();
objects.insert(b"b", b"updated").unwrap();
assert_eq!(values.len(), keys.len());
assert_eq!(
values[0].as_deref().map(Vec::as_slice),
Some(b"two".as_slice())
);
assert!(values[1].is_none());
assert_eq!(
values[2].as_deref().map(Vec::as_slice),
Some(b"one".as_slice())
);
assert_eq!(
values[3].as_deref().map(Vec::as_slice),
Some(b"two".as_slice())
);
assert_eq!(objects.get(b"b").unwrap(), Some(b"updated".to_vec()));
}
#[test]
fn in_memory_snapshots_remain_atomic_during_concurrent_batches() {
let db = Database::in_memory().unwrap();
let left = db.keyspace("left", KeyspaceCreateOptions::default).unwrap();
let right = db
.keyspace("right", KeyspaceCreateOptions::default)
.unwrap();
let writer_db = db.clone();
let writer_left = left;
let writer_right = right;
let writer = std::thread::spawn(move || {
for index in 0..256u16 {
let key = index.to_be_bytes();
writer_db
.batch()
.put(&writer_left, key, b"left")
.put(&writer_right, key, b"right")
.commit()
.unwrap();
}
});
for _ in 0..64 {
let snapshot = db.snapshot().unwrap();
for index in 0..256u16 {
let key = index.to_be_bytes();
let left_value = snapshot.keyspace("left").get(key);
let right_value = snapshot.keyspace("right").get(key);
assert_eq!(left_value.is_some(), right_value.is_some());
}
}
writer.join().unwrap();
}
#[test]
fn in_memory_diagnostics_are_zero_for_durable_databases() {
let directory = tempfile::tempdir().unwrap();
let db = Database::builder(directory.path()).open().unwrap();
assert_eq!(db.ram_diagnostics().unwrap(), RamDiagnostics::default());
}
#[test]
fn persists_and_reopens() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let keyspace = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
keyspace.insert(b"b", b"two").unwrap();
keyspace.insert(b"a", b"one").unwrap();
db.persist(PersistMode::SyncAll).unwrap();
drop(keyspace);
drop(db);
let db = Database::open(directory.path()).unwrap();
let keyspace = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
assert_eq!(keyspace.get(b"a").unwrap(), Some(b"one".to_vec()));
let entries: Vec<_> = keyspace.iter().collect();
assert_eq!(entries[0].key, b"a");
assert_eq!(entries[1].key, b"b");
}
#[test]
fn durable_table_reads_record_reader_and_file_timings() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"key", b"value").unwrap();
db.persist(PersistMode::SyncAll).unwrap();
assert_eq!(objects.get(b"key").unwrap(), Some(b"value".to_vec()));
let diagnostics = db.wal_diagnostics().unwrap();
assert!(diagnostics.table_lookup_count > 0);
assert_eq!(diagnostics.table_reader_wait_duration_ns, 0);
assert!(diagnostics.file_read_duration_ns > 0);
assert!(diagnostics.read_lock_held_duration_ns > 0);
}
#[test]
fn incremental_tables_preserve_updates_and_tombstones() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"a", b"one").unwrap();
db.persist(PersistMode::SyncAll).unwrap();
objects.insert(b"b", b"two").unwrap();
db.persist(PersistMode::SyncAll).unwrap();
objects.remove(b"a").unwrap();
db.persist(PersistMode::SyncAll).unwrap();
drop(objects);
drop(db);
let manifest: Manifest =
serde_json::from_slice(&std::fs::read(directory.path().join(MANIFEST_FILE)).unwrap())
.unwrap();
assert_eq!(manifest.table_files.len(), 3);
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
assert_eq!(objects.get(b"a").unwrap(), None);
assert_eq!(objects.get(b"b").unwrap(), Some(b"two".to_vec()));
db.compact().unwrap();
drop(objects);
drop(db);
let manifest: Manifest =
serde_json::from_slice(&std::fs::read(directory.path().join(MANIFEST_FILE)).unwrap())
.unwrap();
assert_eq!(manifest.table_files.len(), 1);
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
assert_eq!(objects.get(b"a").unwrap(), None);
assert_eq!(objects.get(b"b").unwrap(), Some(b"two".to_vec()));
}
#[test]
fn layered_reads_and_scans_use_newest_values_and_report_table_work() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"a", b"old").unwrap();
objects.insert(b"b", b"two").unwrap();
db.persist(PersistMode::SyncAll).unwrap();
objects.insert(b"a", b"new").unwrap();
objects.remove(b"b").unwrap();
db.persist(PersistMode::SyncAll).unwrap();
assert_eq!(objects.get(b"a").unwrap(), Some(b"new".to_vec()));
assert_eq!(objects.get(b"b").unwrap(), None);
let entries: Vec<_> = objects
.range_bounds(Some((b"a", true)), Some((b"z", true)))
.collect();
assert_eq!(
entries,
vec![Entry {
key: b"a".to_vec(),
value: b"new".to_vec()
}]
);
let diagnostics = db.wal_diagnostics().unwrap();
assert_eq!(diagnostics.table_layer_count, 2);
assert!(diagnostics.table_lookup_count >= 2);
assert!(diagnostics.table_layers_consulted >= 2);
assert!(diagnostics.table_bytes_read > 0);
assert!(diagnostics.table_read_duration_ns > 0);
assert_eq!(diagnostics.scan_count, 1);
assert_eq!(diagnostics.scan_keys_examined, 2);
assert!(diagnostics.scan_layers_consulted >= 2);
assert!(diagnostics.scan_duration_ns > 0);
}
#[test]
fn durable_batched_reads_preserve_layers_tombstones_order_and_duplicates() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
db.batch()
.put(&objects, b"a", b"old")
.put(&objects, b"deleted", b"before")
.commit()
.unwrap();
db.persist(PersistMode::SyncAll).unwrap();
db.batch()
.put(&objects, b"a", b"new")
.delete(&objects, b"deleted")
.commit()
.unwrap();
db.persist(PersistMode::SyncAll).unwrap();
objects.insert(b"mutable", b"current").unwrap();
let values = objects
.get_many_shared(&[
b"a".to_vec(),
b"deleted".to_vec(),
b"mutable".to_vec(),
b"missing".to_vec(),
b"a".to_vec(),
])
.unwrap();
let values: Vec<_> = values
.into_iter()
.map(|value| value.map(|value| value.as_ref().clone()))
.collect();
assert_eq!(
values,
vec![
Some(b"new".to_vec()),
None,
Some(b"current".to_vec()),
None,
Some(b"new".to_vec()),
]
);
}
#[test]
fn legacy_table_formats_use_bounded_paginated_scans() {
for legacy_magic in [TABLE_MAGIC, TABLE_MAGIC_V2] {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
for index in 0..32_u8 {
let key = format!("legacy/{index:02}");
let value = format!("value-{index:02}");
objects.insert(key.as_bytes(), value.as_bytes()).unwrap();
}
db.compact().unwrap();
drop(objects);
drop(db);
let manifest: Manifest = serde_json::from_slice(
&std::fs::read(directory.path().join(MANIFEST_FILE)).unwrap(),
)
.unwrap();
let table_path = directory.path().join(manifest.table_file.unwrap());
let (sequence, entries, _, _) = read_table_index(&table_path).unwrap();
let file = Arc::new(File::open(&table_path).unwrap());
let mut legacy = Vec::new();
legacy.extend_from_slice(legacy_magic);
write_u64(&mut legacy, sequence);
write_u64(&mut legacy, entries.len() as u64);
for entry in &entries {
let value = read_table_value_handle(&file, entry, true)
.unwrap()
.0
.unwrap();
let record_start = legacy.len();
write_bytes(&mut legacy, &entry.key).unwrap();
if legacy_magic == TABLE_MAGIC_V2 {
legacy.push(1);
}
write_bytes(&mut legacy, &value).unwrap();
let record_checksum = checksum(&legacy[record_start..]);
write_u32(&mut legacy, record_checksum);
}
std::fs::write(&table_path, legacy).unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
let first_page = objects
.prefix_page(b"legacy/", 0, 10)
.into_result()
.unwrap();
let second_page = objects
.prefix_page(b"legacy/", 10, 10)
.into_result()
.unwrap();
assert_eq!(first_page.len(), 10);
assert_eq!(second_page.len(), 10);
assert_eq!(first_page[0].key, b"legacy/00");
assert_eq!(second_page[0].key, b"legacy/10");
assert_eq!(second_page[9].value, b"value-19");
let diagnostics = db.wal_diagnostics().unwrap();
assert_eq!(diagnostics.scan_count, 2);
assert!(diagnostics.table_bytes_read > 0);
}
}
#[test]
fn bounded_scans_merge_overlapping_layers_without_materializing_outside_range() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"aa-1", b"old").unwrap();
objects.insert(b"ab-1", b"keep").unwrap();
objects.insert(b"ba-1", b"outside").unwrap();
db.persist(PersistMode::SyncAll).unwrap();
objects.insert(b"aa-1", b"new").unwrap();
objects.insert(b"ac-1", b"added").unwrap();
db.persist(PersistMode::SyncAll).unwrap();
objects.remove(b"ab-1").unwrap();
objects.insert(b"ad-1", b"latest").unwrap();
db.persist(PersistMode::SyncAll).unwrap();
let range: Vec<_> = objects
.range_bounds(Some((b"aa-1", true)), Some((b"ad-1", false)))
.map(|entry| (entry.key, entry.value))
.collect();
assert_eq!(
range,
vec![
(b"aa-1".to_vec(), b"new".to_vec()),
(b"ac-1".to_vec(), b"added".to_vec()),
]
);
let prefix: Vec<_> = objects.prefix(b"a").map(|entry| entry.key).collect();
assert_eq!(
prefix,
vec![b"aa-1".to_vec(), b"ac-1".to_vec(), b"ad-1".to_vec()]
);
let diagnostics = db.wal_diagnostics().unwrap();
assert_eq!(diagnostics.scan_count, 2);
assert!(diagnostics.scan_keys_examined >= 4);
assert!(diagnostics.scan_layers_consulted >= 3);
drop(objects);
drop(db);
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
let reopened_range: Vec<_> = objects
.range_bounds(Some((b"aa-1", true)), Some((b"ad-1", false)))
.map(|entry| (entry.key, entry.value))
.collect();
assert_eq!(reopened_range, range);
let reopened_prefix: Vec<_> = objects.prefix(b"a").map(|entry| entry.key).collect();
assert_eq!(
reopened_prefix,
vec![b"aa-1".to_vec(), b"ac-1".to_vec(), b"ad-1".to_vec()]
);
}
#[test]
fn durable_prefix_pages_seek_to_prefix_and_skip_pending_tombstones() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
let mut batch = db.batch_with_capacity(1_100);
for index in 0..1_000_u32 {
let key = format!("a/{index:04}");
batch = batch.put(&objects, key.as_bytes(), b"outside");
}
for index in 0..100_u32 {
let key = format!("target/{index:04}");
batch = batch.put(&objects, key.as_bytes(), b"inside");
}
batch.commit().unwrap();
db.batch()
.delete(&objects, b"target/0000")
.delete(&objects, b"target/0001")
.commit()
.unwrap();
assert_eq!(
objects
.first_prefix_after(b"target/", Some(b"a/0999"))
.unwrap()
.map(|entry| entry.key),
Some(b"target/0002".to_vec())
);
let before = db.wal_diagnostics().unwrap().scan_keys_examined;
let page: Vec<_> = objects
.prefix_page_after(b"target/", Some(b"a/0999"), 10)
.map(|entry| entry.key)
.collect();
let examined = db
.wal_diagnostics()
.unwrap()
.scan_keys_examined
.saturating_sub(before);
assert_eq!(page.len(), 10);
assert_eq!(page.first(), Some(&b"target/0002".to_vec()));
assert_eq!(page.last(), Some(&b"target/0011".to_vec()));
assert_eq!(
examined, 12,
"prefix seek should examine only matching keys"
);
let before = db.wal_diagnostics().unwrap().scan_keys_examined;
let page: Vec<_> = objects
.prefix_page_after(b"target/", Some(b"target/0050"), 10)
.map(|entry| entry.key)
.collect();
let examined = db
.wal_diagnostics()
.unwrap()
.scan_keys_examined
.saturating_sub(before);
assert_eq!(page.first(), Some(&b"target/0051".to_vec()));
assert_eq!(page.last(), Some(&b"target/0060".to_vec()));
assert_eq!(examined, 10, "exclusive cursor should seek past its key");
}
#[test]
fn durable_table_pages_seek_blocks_and_keep_the_full_index_lazy() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
let payload = vec![b'x'; 128];
let mut batch = db.batch_with_capacity(3_000);
for index in 0..3_000_u32 {
let key = format!("target/{index:06}");
batch = batch.put(&objects, key.as_bytes(), &payload);
}
batch.commit().unwrap();
db.compact().unwrap();
drop(objects);
drop(db);
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
let layer = db.inner.lock().unwrap().table_layers[0].clone();
assert!(layer.blocks.len() > 2);
assert!(layer.entries.get().is_none());
let file_bytes = std::fs::metadata(&layer.path).unwrap().len();
let page: Vec<_> = objects
.prefix_page_after(b"target/", Some(b"target/002500"), 10)
.into_result()
.unwrap()
.into_iter()
.map(|entry| entry.key)
.collect();
assert_eq!(page.first(), Some(&b"target/002501".to_vec()));
assert_eq!(page.last(), Some(&b"target/002510".to_vec()));
assert!(
db.wal_diagnostics().unwrap().table_bytes_read < file_bytes,
"a bounded page should read fewer bytes than the full table"
);
assert!(
layer.entries.get().is_none(),
"bounded scans should not populate the full table index"
);
}
#[test]
fn durable_counts_merge_layers_and_tombstones_without_loading_full_indexes() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
let mut initial = db.batch_with_capacity(600);
for index in 0..600_u32 {
initial = initial.put(
&objects,
format!("collection/00/{index:04}").as_bytes(),
b"payload that should not be copied for count",
);
}
initial.commit().unwrap();
db.persist(PersistMode::SyncAll).unwrap();
let mut changes = db.batch_with_capacity(305);
for index in 0..300_u32 {
changes = changes.delete(&objects, format!("collection/00/{index:04}").as_bytes());
}
changes = changes
.put(&objects, b"collection/00/0599", b"updated")
.put(&objects, b"collection/01/0000", b"new")
.put(&objects, b"collection/01/0001", b"new")
.put(&objects, b"collection/01/0002", b"new")
.put(&objects, b"collection/01/0003", b"new")
.put(&objects, b"collection/01/0004", b"new");
changes.commit().unwrap();
db.persist(PersistMode::SyncAll).unwrap();
objects.insert(b"collection/01/0005", b"new").unwrap();
objects.insert(b"collection/01/0006", b"new").unwrap();
objects.insert(b"other/0000", b"new").unwrap();
assert_eq!(objects.count().unwrap(), 308);
assert_eq!(objects.count_prefix(b"collection/00").unwrap(), 300);
assert_eq!(objects.count_prefix(b"collection/01").unwrap(), 7);
assert_eq!(objects.count_prefix(b"missing/").unwrap(), 0);
assert!(
db.inner
.lock()
.unwrap()
.table_layers
.iter()
.all(|layer| layer.entries.get().is_none())
);
drop(objects);
drop(db);
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
assert_eq!(objects.count().unwrap(), 308);
assert_eq!(objects.count_prefix(b"collection/00").unwrap(), 300);
assert_eq!(objects.count_prefix(b"collection/01").unwrap(), 7);
}
#[test]
fn bounded_table_pages_refill_memtable_chunks_after_tombstones() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
let mut batch = db.batch_with_capacity(600);
for index in 0..600_u32 {
batch = batch.put(&objects, format!("target/{index:04}").as_bytes(), b"value");
}
batch.commit().unwrap();
db.persist(PersistMode::SyncAll).unwrap();
let mut batch = db.batch_with_capacity(300);
for index in 0..300_u32 {
batch = batch.delete(&objects, format!("target/{index:04}").as_bytes());
}
batch.commit().unwrap();
let page: Vec<_> = objects
.prefix_page(b"target/", 0, 10)
.into_result()
.unwrap();
assert_eq!(
page.iter()
.map(|entry| (entry.key.clone(), entry.value.clone()))
.collect::<Vec<_>>(),
(300..310_u32)
.map(|index| { (format!("target/{index:04}").into_bytes(), b"value".to_vec(),) })
.collect::<Vec<_>>()
);
let diagnostics = db.wal_diagnostics().unwrap();
assert_eq!(diagnostics.scan_page_capture_count, 2);
assert_eq!(diagnostics.scan_page_capture_fallback_count, 0);
assert_eq!(diagnostics.scan_page_capture_candidates_copied, 300);
assert_eq!(diagnostics.scan_page_capture_fallback_candidates_copied, 0);
assert!(diagnostics.scan_page_capture_duration_ns > 0);
}
#[test]
fn durable_table_pages_merge_updates_tombstones_and_pending_values() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
db.batch()
.put(&objects, b"range/01", b"old")
.put(&objects, b"range/02", b"deleted")
.put(&objects, b"range/03", b"old-three")
.commit()
.unwrap();
db.persist(PersistMode::SyncAll).unwrap();
db.batch()
.put(&objects, b"range/01", b"new")
.delete(&objects, b"range/02")
.put(&objects, b"range/04", b"four")
.commit()
.unwrap();
db.persist(PersistMode::SyncAll).unwrap();
db.batch()
.put(&objects, b"range/03", b"pending-three")
.put(&objects, b"range/05", b"five")
.commit()
.unwrap();
let page: Vec<_> = objects
.prefix_page(b"range/", 0, 10)
.into_result()
.unwrap()
.into_iter()
.map(|entry| (entry.key, entry.value))
.collect();
assert_eq!(
page,
vec![
(b"range/01".to_vec(), b"new".to_vec()),
(b"range/03".to_vec(), b"pending-three".to_vec()),
(b"range/04".to_vec(), b"four".to_vec()),
(b"range/05".to_vec(), b"five".to_vec()),
]
);
let bounded_page: Vec<_> = objects
.iter_bounds_paginated(
None,
Some((b"range/01".to_vec(), false)),
Some((b"range/05".to_vec(), false)),
0,
Some(10),
)
.into_result()
.unwrap()
.into_iter()
.map(|entry| entry.key)
.collect();
assert_eq!(bounded_page, vec![b"range/03", b"range/04"]);
let empty_page = objects
.iter_bounds_paginated(
None,
Some((b"range/04".to_vec(), true)),
Some((b"range/04".to_vec(), false)),
0,
Some(10),
)
.into_result()
.unwrap();
assert_eq!(empty_page, []);
}
#[test]
fn durable_table_page_propagates_block_corruption() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"target/one", b"value").unwrap();
db.compact().unwrap();
let layer = db.inner.lock().unwrap().table_layers[0].clone();
let mut table = OpenOptions::new().write(true).open(&layer.path).unwrap();
table
.seek(SeekFrom::Start(layer.blocks[0].offset + 1))
.unwrap();
table.write_all(b"z").unwrap();
table.sync_all().unwrap();
let error = objects
.prefix_page(b"target/", 0, 10)
.into_result()
.unwrap_err();
assert!(error.to_string().contains("table block checksum mismatch"));
}
#[test]
fn durable_table_block_cache_reuses_verified_immutable_blocks() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
let mut batch = db.batch_with_capacity(512);
for index in 0..512_u32 {
let key = format!("cache/{index:04}");
batch = batch.put(&objects, key.as_bytes(), b"cache-value");
}
batch.commit().unwrap();
db.compact().unwrap();
assert_eq!(
objects.get(b"cache/0000").unwrap(),
Some(b"cache-value".to_vec())
);
let first_read = db.wal_diagnostics().unwrap().table_bytes_read;
assert!(first_read > 0);
assert_eq!(
objects.get(b"cache/0000").unwrap(),
Some(b"cache-value".to_vec())
);
let second_read = db.wal_diagnostics().unwrap().table_bytes_read;
assert_eq!(second_read, first_read);
let first_page = objects
.prefix_page_after(b"cache/", None, 16)
.into_result()
.unwrap();
assert_eq!(first_page.len(), 16);
let next_page = objects
.prefix_page_after(b"cache/", Some(&first_page[15].key), 16)
.into_result()
.unwrap();
assert_eq!(next_page.len(), 16);
assert_eq!(next_page[0].key, b"cache/0016");
let inner = db.inner.lock().unwrap();
let cache = inner.table_block_cache.state.lock().unwrap();
assert!(cache.hits >= 1);
assert!(cache.decoded_hits >= 1);
assert!(cache.resident_bytes <= cache.capacity_bytes);
drop(cache);
drop(inner);
let diagnostics = db.wal_diagnostics().unwrap();
assert!(diagnostics.table_block_cache_capacity_bytes > 0);
assert!(diagnostics.table_block_cache_entries > 0);
assert!(diagnostics.table_block_cache_hits >= 1);
assert!(diagnostics.table_block_cache_decoded_hits >= 1);
assert!(
diagnostics.table_block_cache_resident_bytes
<= diagnostics.table_block_cache_capacity_bytes
);
}
#[test]
fn durable_first_prefix_lookup_reuses_verified_immutable_blocks() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"prefix/a", b"one").unwrap();
objects.insert(b"prefix/b", b"two").unwrap();
db.compact().unwrap();
let layer = db.inner.lock().unwrap().table_layers[0].clone();
assert!(layer.entries.get().is_none());
assert_eq!(
objects
.first_prefix_after(b"prefix/", None)
.unwrap()
.unwrap()
.key,
b"prefix/a"
);
assert_eq!(
objects
.first_prefix_after(b"prefix/", Some(b"prefix/a"))
.unwrap()
.unwrap()
.key,
b"prefix/b"
);
assert!(layer.entries.get().is_some());
let inner = db.inner.lock().unwrap();
let cache = inner.table_block_cache.state.lock().unwrap();
assert!(cache.resident_bytes <= cache.capacity_bytes);
}
#[test]
fn table_block_cache_evicts_the_least_recently_used_entry_within_its_bound() {
let cache = TableBlockCache::with_capacity(6);
let key = |offset| TableBlockCacheKey {
path: PathBuf::from("table.tdb"),
offset,
};
let first = key(0);
let second = key(1);
let third = key(2);
cache.insert(first.clone(), Arc::new(vec![1; 3]));
cache.insert(second.clone(), Arc::new(vec![2; 3]));
assert!(cache.get(&first).is_some());
cache.insert(third.clone(), Arc::new(vec![3; 3]));
assert!(cache.get(&first).is_some());
assert!(cache.get(&second).is_none());
assert!(cache.get(&third).is_some());
let state = cache.state.lock().unwrap();
assert_eq!(state.resident_bytes, 6);
assert!(state.resident_bytes <= state.capacity_bytes);
assert_eq!(state.evictions, 1);
}
#[test]
fn automatic_layer_threshold_compacts_after_bounded_flush() {
let directory = tempfile::tempdir().unwrap();
let db = Database::builder(directory.path())
.max_memtable_bytes(1)
.max_table_layers(2)
.open()
.unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"a", b"one").unwrap();
objects.insert(b"b", b"two").unwrap();
assert_eq!(objects.get(b"a").unwrap(), Some(b"one".to_vec()));
assert_eq!(objects.get(b"b").unwrap(), Some(b"two".to_vec()));
assert_eq!(objects.iter().count(), 2);
let manifest: Manifest =
serde_json::from_slice(&std::fs::read(directory.path().join(MANIFEST_FILE)).unwrap())
.unwrap();
assert_eq!(manifest.table_files.len(), 1);
}
#[test]
fn interrupted_flush_recovers_from_previous_manifest_and_wal() {
for point in [
"before-table-write",
"after-table-sync-before-rename",
"before-table-rename",
"after-table-rename-before-manifest",
"before-manifest-write",
"after-manifest-sync-before-rename",
"after-manifest-rename-before-wal-truncate",
] {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"a", b"one").unwrap();
db.persist(PersistMode::SyncAll).unwrap();
objects.insert(b"b", b"two").unwrap();
set_fault_point(Some(point));
let result = db.persist(PersistMode::SyncAll);
set_fault_point(None);
assert!(result.is_err(), "fault point {point} did not fail");
drop(objects);
drop(db);
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
assert_eq!(objects.get(b"a").unwrap(), Some(b"one".to_vec()), "{point}");
assert_eq!(objects.get(b"b").unwrap(), Some(b"two".to_vec()), "{point}");
assert!(
!directory.path().join(MANIFEST_TEMP_FILE).exists(),
"temporary manifest remained after {point}"
);
}
}
#[test]
fn interrupted_compaction_recovers_from_old_or_new_manifest() {
for point in [
"before-table-write",
"after-table-sync-before-rename",
"before-table-rename",
"after-table-rename-before-manifest",
"before-manifest-write",
"after-manifest-sync-before-rename",
"after-manifest-rename-before-wal-truncate",
] {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"a", b"one").unwrap();
db.persist(PersistMode::SyncAll).unwrap();
objects.insert(b"b", b"two").unwrap();
set_fault_point(Some(point));
let result = db.compact();
set_fault_point(None);
assert!(result.is_err(), "fault point {point} did not fail");
drop(objects);
drop(db);
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
assert_eq!(objects.get(b"a").unwrap(), Some(b"one".to_vec()), "{point}");
assert_eq!(objects.get(b"b").unwrap(), Some(b"two".to_vec()), "{point}");
assert!(
!directory.path().join(MANIFEST_TEMP_FILE).exists(),
"temporary manifest remained after {point}"
);
}
}
#[test]
fn invalid_manifest_table_names_are_rejected() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
drop(db);
let manifest_path = directory.path().join(MANIFEST_FILE);
let mut manifest: serde_json::Value =
serde_json::from_slice(&std::fs::read(&manifest_path).unwrap()).unwrap();
manifest["table_file"] = serde_json::Value::String("../outside.tdb".to_string());
manifest["table_files"] = serde_json::json!(["../outside.tdb"]);
std::fs::write(&manifest_path, serde_json::to_vec(&manifest).unwrap()).unwrap();
let Err(error) = Database::open(directory.path()) else {
panic!("manifest with path traversal unexpectedly opened")
};
assert!(error.to_string().contains("invalid ThingDB table filename"));
}
#[test]
fn invalid_manifest_state_is_rejected_before_recovery() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
drop(db);
let manifest_path = directory.path().join(MANIFEST_FILE);
let mut manifest: serde_json::Value =
serde_json::from_slice(&std::fs::read(&manifest_path).unwrap()).unwrap();
manifest["table_sequence"] = serde_json::json!(1);
std::fs::write(&manifest_path, serde_json::to_vec(&manifest).unwrap()).unwrap();
let Err(error) = Database::open(directory.path()) else {
panic!("manifest without a table unexpectedly opened")
};
assert!(error.to_string().contains("table sequence without a table"));
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"a", b"one").unwrap();
db.compact().unwrap();
drop(objects);
drop(db);
let manifest_path = directory.path().join(MANIFEST_FILE);
let mut manifest: serde_json::Value =
serde_json::from_slice(&std::fs::read(&manifest_path).unwrap()).unwrap();
manifest["table_files"] = serde_json::json!(["table-99999999999999999999-missing.tdb"]);
manifest["table_file"] = serde_json::Value::Null;
std::fs::write(&manifest_path, serde_json::to_vec(&manifest).unwrap()).unwrap();
let Err(error) = Database::open(directory.path()) else {
panic!("manifest with a missing table unexpectedly opened")
};
assert!(
error
.to_string()
.contains("manifest references missing table")
);
}
#[test]
fn unsupported_manifest_version_is_rejected_before_recovery() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
drop(db);
let manifest_path = directory.path().join(MANIFEST_FILE);
let mut manifest: serde_json::Value =
serde_json::from_slice(&std::fs::read(&manifest_path).unwrap()).unwrap();
manifest["format_version"] = serde_json::json!(FORMAT_VERSION + 1);
std::fs::write(&manifest_path, serde_json::to_vec(&manifest).unwrap()).unwrap();
let Err(error) = Database::open(directory.path()) else {
panic!("unsupported manifest version unexpectedly opened")
};
assert!(
error
.to_string()
.contains("unsupported ThingDB format version")
);
}
#[test]
fn manifest_rejects_table_sequence_older_than_referenced_table() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"a", b"one").unwrap();
db.compact().unwrap();
drop(objects);
drop(db);
let manifest_path = directory.path().join(MANIFEST_FILE);
let mut manifest: serde_json::Value =
serde_json::from_slice(&std::fs::read(&manifest_path).unwrap()).unwrap();
manifest["table_sequence"] = serde_json::json!(0);
std::fs::write(&manifest_path, serde_json::to_vec(&manifest).unwrap()).unwrap();
let Err(error) = Database::open(directory.path()) else {
panic!("manifest with an older table sequence unexpectedly opened")
};
assert!(
error
.to_string()
.contains("table sequence exceeds manifest sequence")
);
}
#[test]
fn table_key_order_corruption_is_reported() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"a", b"one").unwrap();
objects.insert(b"b", b"two").unwrap();
db.compact().unwrap();
drop(objects);
drop(db);
let manifest: Manifest =
serde_json::from_slice(&std::fs::read(directory.path().join(MANIFEST_FILE)).unwrap())
.unwrap();
let table_path = directory.path().join(manifest.table_file.unwrap());
let mut bytes = std::fs::read(&table_path).unwrap();
let first_record_start = TABLE_MAGIC.len() + 16;
let key_length = usize::try_from(u64::from_be_bytes(
bytes[first_record_start..first_record_start + 8]
.try_into()
.unwrap(),
))
.unwrap();
let first_key_offset = first_record_start + 8;
bytes[first_key_offset] = b'z';
let value_length_offset = first_key_offset + key_length + 1;
let value_length = usize::try_from(u64::from_be_bytes(
bytes[value_length_offset..value_length_offset + 8]
.try_into()
.unwrap(),
))
.unwrap();
let first_record_end = value_length_offset + 8 + value_length;
let record_checksum = checksum(&bytes[first_record_start..first_record_end]);
bytes[first_record_end..first_record_end + 4]
.copy_from_slice(&record_checksum.to_be_bytes());
std::fs::write(&table_path, bytes).unwrap();
let Err(error) = Database::open(directory.path()) else {
panic!("table with unsorted keys unexpectedly opened")
};
assert!(
error
.to_string()
.contains("table keys are not strictly ordered")
);
}
#[test]
fn batch_is_atomic_after_reopen() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
db.batch()
.put(&objects, b"a", b"one")
.put(&objects, b"b", b"two")
.commit()
.unwrap();
drop(objects);
drop(db);
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
assert_eq!(objects.get(b"a").unwrap(), Some(b"one".to_vec()));
assert_eq!(objects.get(b"b").unwrap(), Some(b"two".to_vec()));
}
#[test]
fn cross_keyspace_batch_is_atomic_after_reopen() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
let events = db
.keyspace("events", KeyspaceCreateOptions::default)
.unwrap();
db.batch()
.put(&objects, b"a", b"one")
.put(&events, b"1", b"created")
.commit()
.unwrap();
drop(events);
drop(objects);
drop(db);
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
let events = db
.keyspace("events", KeyspaceCreateOptions::default)
.unwrap();
assert_eq!(objects.get(b"a").unwrap(), Some(b"one".to_vec()));
assert_eq!(events.get(b"1").unwrap(), Some(b"created".to_vec()));
}
#[test]
fn grouped_writes_replay_completely_after_reopen() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
let writers = 16;
let barrier = Arc::new(std::sync::Barrier::new(writers));
let handles: Vec<_> = (0..writers)
.map(|index| {
let objects = objects.clone();
let barrier = Arc::clone(&barrier);
std::thread::spawn(move || {
barrier.wait();
objects
.insert(format!("key-{index}").as_bytes(), b"value")
.unwrap();
})
})
.collect();
for handle in handles {
handle.join().unwrap();
}
drop(objects);
drop(db);
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
for index in 0..writers {
assert_eq!(
objects.get(format!("key-{index}").as_bytes()).unwrap(),
Some(b"value".to_vec())
);
}
}
#[test]
fn injected_wal_failures_preserve_batch_atomicity() {
for point in [
"before-wal-append",
"after-wal-write-before-sync",
"after-wal-sync-before-state-apply",
] {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
set_fault_point(Some(point));
let result = db
.batch()
.put(&objects, b"a", b"one")
.put(&objects, b"b", b"two")
.commit();
set_fault_point(None);
assert!(result.is_err(), "fault point {point} did not fail");
if point == "after-wal-sync-before-state-apply" {
let rejected = db.batch().put(&objects, b"rejected", b"write").commit();
assert!(rejected.is_err());
drop(objects);
drop(db);
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
assert_eq!(objects.get(b"a").unwrap(), Some(b"one".to_vec()));
assert_eq!(objects.get(b"b").unwrap(), Some(b"two".to_vec()));
continue;
}
db.batch()
.put(&objects, b"a", b"one")
.put(&objects, b"b", b"two")
.commit()
.unwrap();
drop(objects);
drop(db);
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
let first = objects.get(b"a").unwrap();
let second = objects.get(b"b").unwrap();
assert_eq!(first, Some(b"one".to_vec()), "fault point {point}");
assert_eq!(second, Some(b"two".to_vec()), "fault point {point}");
}
}
#[test]
fn truncating_wal_at_every_boundary_recovers_only_complete_frames() {
let source = tempfile::tempdir().unwrap();
let db = Database::open(source.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"a", b"one").unwrap();
let first_frame_len = std::fs::metadata(source.path().join(WAL_FILE))
.unwrap()
.len();
objects.insert(b"b", b"two").unwrap();
drop(objects);
drop(db);
let complete = std::fs::read(source.path().join(WAL_FILE)).unwrap();
let second_frame_len = complete.len() as u64 - first_frame_len;
for cut in 0..=complete.len() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
drop(db);
std::fs::write(directory.path().join(WAL_FILE), &complete[..cut]).unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
let expected = if cut < first_frame_len as usize {
0
} else if cut < (first_frame_len + second_frame_len) as usize {
1
} else {
2
};
let actual = usize::from(objects.get(b"a").unwrap().is_some())
+ usize::from(objects.get(b"b").unwrap().is_some());
assert_eq!(actual, expected, "unexpected recovery at WAL byte {cut}");
}
}
#[test]
fn malformed_wal_length_and_operation_are_reported() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
drop(db);
let mut malformed = Vec::from(WAL_MAGIC.as_slice());
malformed.extend_from_slice(&1_u64.to_be_bytes());
std::fs::write(directory.path().join(WAL_FILE), malformed).unwrap();
let Err(error) = Database::open(directory.path()) else {
panic!("malformed WAL length unexpectedly opened")
};
assert!(error.to_string().contains("frame length"));
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
drop(db);
let mut invalid = encode_frame(
1,
&[Operation::Put {
key: b"objects\0a".to_vec(),
value: b"one".to_vec(),
}],
)
.unwrap();
invalid[28] = 9;
std::fs::write(directory.path().join(WAL_FILE), invalid).unwrap();
let Err(error) = Database::open(directory.path()) else {
panic!("invalid WAL operation unexpectedly opened")
};
assert!(error.to_string().contains("invalid ThingDB WAL operation"));
}
#[test]
fn diagnostics_report_wal_timings_and_recovery() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"a", b"one").unwrap();
let diagnostics = db.wal_diagnostics().unwrap();
assert_eq!(diagnostics.frame_count, 1);
assert_eq!(diagnostics.logical_commit_count, 1);
assert_eq!(diagnostics.physical_sync_count, 1);
assert_eq!(diagnostics.max_group_size, 1);
assert!(diagnostics.journal_bytes > 0);
assert!(diagnostics.wal_bytes_appended > 0);
assert!(diagnostics.buffer_reserved_bytes >= diagnostics.wal_bytes_appended);
assert!(diagnostics.sync_duration_ns > 0);
drop(objects);
drop(db);
let db = Database::open(directory.path()).unwrap();
let diagnostics = db.wal_diagnostics().unwrap();
assert!(diagnostics.recovery_bytes > 0);
assert!(diagnostics.recovery_duration_ns > 0);
}
#[test]
fn bounded_memtable_flushes_before_acknowledgement() {
let directory = tempfile::tempdir().unwrap();
let db = Database::builder(directory.path())
.max_memtable_bytes(1)
.open()
.unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"a", b"one").unwrap();
let diagnostics = db.wal_diagnostics().unwrap();
assert_eq!(diagnostics.memtable_bytes, 0);
assert!(!diagnostics.memtable_over_budget);
assert_eq!(diagnostics.flush_count, 1);
assert_eq!(diagnostics.automatic_flush_count, 1);
assert_eq!(diagnostics.journal_bytes, 0);
drop(objects);
drop(db);
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
assert_eq!(objects.get(b"a").unwrap(), Some(b"one".to_vec()));
}
#[test]
fn durable_memtable_flushes_in_background_after_acknowledgement() {
let directory = tempfile::tempdir().unwrap();
let db = Database::builder(directory.path())
.max_memtable_bytes(1024)
.open()
.unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"a", vec![b'x'; 2048]).unwrap();
assert_eq!(objects.get(b"a").unwrap(), Some(vec![b'x'; 2048]));
let deadline = Instant::now() + Duration::from_secs(2);
loop {
let diagnostics = db.wal_diagnostics().unwrap();
if diagnostics.flush_count >= 1 {
assert_eq!(diagnostics.memtable_bytes, 0);
assert_eq!(diagnostics.journal_bytes, 0);
assert!(!diagnostics.recovery_required);
break;
}
assert!(Instant::now() < deadline, "background flush did not finish");
std::thread::sleep(Duration::from_millis(1));
}
drop(objects);
drop(db);
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
assert_eq!(objects.get(b"a").unwrap(), Some(vec![b'x'; 2048]));
}
#[test]
fn wal_budget_schedules_background_checkpoint() {
let directory = tempfile::tempdir().unwrap();
let db = Database::builder(directory.path())
.max_journaling_size(1)
.max_memtable_bytes(1024 * 1024)
.open()
.unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"a", b"one").unwrap();
let deadline = Instant::now() + Duration::from_secs(2);
loop {
let diagnostics = db.wal_diagnostics().unwrap();
if diagnostics.flush_count >= 1 {
assert_eq!(diagnostics.journal_bytes, 0);
assert_eq!(diagnostics.memtable_bytes, 0);
assert!(!diagnostics.recovery_required);
break;
}
assert!(
Instant::now() < deadline,
"WAL-budget checkpoint did not finish"
);
std::thread::sleep(Duration::from_millis(1));
}
assert_eq!(objects.get(b"a").unwrap(), Some(b"one".to_vec()));
}
#[test]
fn failed_bounded_memtable_flush_requires_reopen() {
let directory = tempfile::tempdir().unwrap();
let db = Database::builder(directory.path())
.max_memtable_bytes(1)
.open()
.unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
set_fault_point(Some("before-table-write"));
let result = objects.insert(b"a", b"one");
set_fault_point(None);
assert!(result.is_err());
assert!(db.wal_diagnostics().unwrap().recovery_required);
assert!(objects.insert(b"b", b"two").is_err());
drop(objects);
drop(db);
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
assert_eq!(objects.get(b"a").unwrap(), Some(b"one".to_vec()));
}
#[test]
fn concurrent_writes_share_physical_syncs() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
let writers = 32;
let barrier = Arc::new(std::sync::Barrier::new(writers));
let handles: Vec<_> = (0..writers)
.map(|index| {
let objects = objects.clone();
let barrier = Arc::clone(&barrier);
std::thread::spawn(move || {
barrier.wait();
objects
.insert(format!("key-{index}").as_bytes(), b"value")
.unwrap();
})
})
.collect();
for handle in handles {
handle.join().unwrap();
}
let diagnostics = db.wal_diagnostics().unwrap();
assert_eq!(diagnostics.logical_commit_count, writers as u64);
assert_eq!(diagnostics.frame_count, writers as u64);
assert!(diagnostics.physical_sync_count < diagnostics.logical_commit_count);
assert!(diagnostics.max_group_size > 1);
for index in 0..writers {
assert_eq!(
objects.get(format!("key-{index}").as_bytes()).unwrap(),
Some(b"value".to_vec())
);
}
}
#[test]
fn incomplete_wal_frame_is_truncated() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"a", b"one").unwrap();
drop(objects);
drop(db);
let wal_path = directory.path().join(WAL_FILE);
let length = std::fs::metadata(&wal_path).unwrap().len();
let file = OpenOptions::new().write(true).open(wal_path).unwrap();
file.set_len(length.saturating_sub(2)).unwrap();
drop(file);
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
assert!(objects.get(b"a").unwrap().is_none());
}
#[test]
fn wal_checksum_corruption_is_reported() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"a", b"one").unwrap();
drop(objects);
drop(db);
let wal_path = directory.path().join(WAL_FILE);
let mut bytes = std::fs::read(&wal_path).unwrap();
*bytes.last_mut().unwrap() ^= 0xff;
std::fs::write(&wal_path, bytes).unwrap();
let Err(error) = Database::open(directory.path()) else {
panic!("corrupted WAL unexpectedly opened")
};
assert!(error.to_string().contains("WAL checksum mismatch"));
}
#[test]
fn table_checksum_corruption_is_reported() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"a", b"one").unwrap();
db.compact().unwrap();
drop(objects);
drop(db);
let manifest: Manifest =
serde_json::from_slice(&std::fs::read(directory.path().join(MANIFEST_FILE)).unwrap())
.unwrap();
let table_path = directory.path().join(manifest.table_file.unwrap());
let mut bytes = std::fs::read(&table_path).unwrap();
let first_record_start = TABLE_MAGIC.len() + 16;
let key_length = usize::try_from(u64::from_be_bytes(
bytes[first_record_start..first_record_start + 8]
.try_into()
.unwrap(),
))
.unwrap();
let value_length_offset = first_record_start + 8 + key_length + 1;
let value_length = usize::try_from(u64::from_be_bytes(
bytes[value_length_offset..value_length_offset + 8]
.try_into()
.unwrap(),
))
.unwrap();
let first_record_end = value_length_offset + 8 + value_length + 4;
bytes[first_record_end - 1] ^= 0xff;
std::fs::write(table_path, bytes).unwrap();
let Err(error) = Database::open(directory.path()) else {
panic!("corrupted table unexpectedly opened")
};
assert!(error.to_string().contains("table checksum mismatch"));
}
#[test]
fn table_v3_footer_corruption_is_reported() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"a", b"one").unwrap();
db.compact().unwrap();
drop(objects);
drop(db);
let manifest: Manifest =
serde_json::from_slice(&std::fs::read(directory.path().join(MANIFEST_FILE)).unwrap())
.unwrap();
let table_path = directory.path().join(manifest.table_file.unwrap());
let mut bytes = std::fs::read(&table_path).unwrap();
assert_eq!(&bytes[..TABLE_MAGIC_V3.len()], TABLE_MAGIC_V3);
*bytes.last_mut().unwrap() ^= 0xff;
std::fs::write(table_path, bytes).unwrap();
let Err(error) = Database::open(directory.path()) else {
panic!("corrupted table footer unexpectedly opened")
};
assert!(error.to_string().contains("table footer checksum mismatch"));
}
#[test]
fn table_v3_reopens_and_scans_multiple_sorted_blocks() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
for index in 0..2_000u32 {
let key = format!("key-{index:04}");
let value = format!("value-{index:04}-with-padding");
objects.insert(key.as_bytes(), value.as_bytes()).unwrap();
}
db.compact().unwrap();
drop(objects);
drop(db);
let manifest: Manifest =
serde_json::from_slice(&std::fs::read(directory.path().join(MANIFEST_FILE)).unwrap())
.unwrap();
let table_path = directory.path().join(manifest.table_file.unwrap());
let bytes = std::fs::read(&table_path).unwrap();
let footer_start = bytes
.windows(TABLE_FOOTER_MAGIC.len())
.position(|window| window == TABLE_FOOTER_MAGIC)
.unwrap();
let mut cursor = footer_start + TABLE_FOOTER_MAGIC.len();
let block_count = read_u64(&bytes, &mut cursor).unwrap();
assert!(block_count > 1);
let reopened = Database::open(directory.path()).unwrap();
let objects = reopened
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
let start: &[u8] = b"key-0100";
let end: &[u8] = b"key-0109";
let entries = objects
.range::<&[u8], _>(start..=end)
.into_result()
.unwrap();
assert_eq!(entries.len(), 10);
assert_eq!(entries[0].value, b"value-0100-with-padding");
}
#[test]
fn scan_checksum_corruption_is_not_treated_as_an_empty_result() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"a", b"one").unwrap();
objects.insert(b"b", b"two").unwrap();
db.compact().unwrap();
let manifest: Manifest =
serde_json::from_slice(&std::fs::read(directory.path().join(MANIFEST_FILE)).unwrap())
.unwrap();
let table_path = directory.path().join(manifest.table_file.unwrap());
let mut bytes = std::fs::read(&table_path).unwrap();
let first_record_start = TABLE_MAGIC.len() + 16;
let key_length = usize::try_from(u64::from_be_bytes(
bytes[first_record_start..first_record_start + 8]
.try_into()
.unwrap(),
))
.unwrap();
let value_length_offset = first_record_start + 8 + key_length + 1;
let value_length = usize::try_from(u64::from_be_bytes(
bytes[value_length_offset..value_length_offset + 8]
.try_into()
.unwrap(),
))
.unwrap();
let first_record_end = value_length_offset + 8 + value_length + 4;
bytes[first_record_end - 1] ^= 0xff;
std::fs::write(&table_path, bytes).unwrap();
let error = objects.iter().into_result().unwrap_err();
assert!(error.to_string().contains("table checksum mismatch"));
let error = objects.prefix(b"a").into_result().unwrap_err();
assert!(error.to_string().contains("table checksum mismatch"));
let error = objects
.range_bounds(Some((b"a", true)), Some((b"b", true)))
.into_result()
.unwrap_err();
assert!(error.to_string().contains("table checksum mismatch"));
let error = objects.first_prefix_after(b"a", None).unwrap_err();
assert!(error.to_string().contains("table checksum mismatch"));
let error = objects.count().unwrap_err();
assert!(error.to_string().contains("checksum mismatch"));
let error = objects.count_prefix(b"a").unwrap_err();
assert!(error.to_string().contains("checksum mismatch"));
}
#[test]
fn repeated_open_close_preserves_durable_state() {
let directory = tempfile::tempdir().unwrap();
for value in 0..8 {
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects
.insert(b"counter", value.to_string().as_bytes())
.unwrap();
if value % 2 == 1 {
db.compact().unwrap();
}
drop(objects);
drop(db);
}
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
assert_eq!(objects.get(b"counter").unwrap(), Some(b"7".to_vec()));
}
#[test]
fn prefix_and_range_are_ordered() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
for key in [b"aa".as_slice(), b"ab", b"ba"] {
objects.insert(key, b"value").unwrap();
}
let prefix: Vec<_> = objects.prefix(b"a").map(|entry| entry.key).collect();
assert_eq!(prefix, vec![b"aa".to_vec(), b"ab".to_vec()]);
let start: &[u8] = b"aa";
let end: &[u8] = b"ab";
let range: Vec<_> = objects
.range::<&[u8], _>(start..=end)
.map(|entry| entry.key)
.collect();
assert_eq!(range, vec![b"aa".to_vec(), b"ab".to_vec()]);
let page: Vec<_> = objects
.prefix_page(b"a", 1, 1)
.map(|entry| entry.key)
.collect();
assert_eq!(page, vec![b"ab".to_vec()]);
}
#[test]
fn first_prefix_after_excludes_the_cursor_key() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
for key in [b"aa".as_slice(), b"ab", b"ac"] {
objects.insert(key, b"value").unwrap();
}
db.compact().unwrap();
assert_eq!(
objects
.first_prefix_after(b"a", Some(b"aa"))
.unwrap()
.map(|entry| entry.key),
Some(b"ab".to_vec())
);
assert_eq!(
objects
.first_prefix_after(b"a", Some(b"ab"))
.unwrap()
.map(|entry| entry.key),
Some(b"ac".to_vec())
);
}
#[test]
fn durable_first_prefix_uses_bounded_memtable_path_without_table_layers() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let ready = db
.keyspace("ready", KeyspaceCreateOptions::default)
.unwrap();
ready.insert(b"queue\0a", b"a").unwrap();
ready.insert(b"queue\0b", b"b").unwrap();
let first = ready.first_prefix_after(b"queue\0", None).unwrap().unwrap();
assert_eq!(first.key, b"queue\0a");
let diagnostics = db.wal_diagnostics().unwrap();
assert_eq!(diagnostics.scan_keys_examined, 1);
assert_eq!(diagnostics.scan_returned_entries, 1);
assert_eq!(diagnostics.table_layer_count, 0);
}
#[test]
fn snapshot_is_consistent() {
let directory = tempfile::tempdir().unwrap();
let db = Database::open(directory.path()).unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
objects.insert(b"a", b"one").unwrap();
let snapshot = db.snapshot().unwrap();
objects.insert(b"a", b"two").unwrap();
assert_eq!(
snapshot.keyspace("objects").get(b"a"),
Some(b"one".to_vec())
);
}
#[cfg(feature = "benchmark")]
#[test]
fn rcu_memory_mode_preserves_atomic_batches_and_snapshots() {
let db = Database::in_memory_with_rcu().unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
let events = db
.keyspace("events", KeyspaceCreateOptions::default)
.unwrap();
db.batch()
.put(&objects, b"a", b"one")
.put(&events, b"e1", b"event")
.commit()
.unwrap();
let snapshot = db.snapshot().unwrap();
db.batch()
.put(&objects, b"a", b"two")
.delete(&events, b"e1")
.commit()
.unwrap();
assert_eq!(objects.get(b"a").unwrap(), Some(b"two".to_vec()));
assert_eq!(events.get(b"e1").unwrap(), None);
assert_eq!(
snapshot.keyspace("objects").get(b"a"),
Some(b"one".to_vec())
);
assert_eq!(
snapshot.keyspace("events").get(b"e1"),
Some(b"event".to_vec())
);
}
#[cfg(feature = "benchmark")]
#[test]
fn rcu_memory_mode_keeps_ordered_scans_and_shared_reads() {
let db = Database::in_memory_with_rcu().unwrap();
let objects = db
.keyspace("objects", KeyspaceCreateOptions::default)
.unwrap();
for key in [b"aa".as_slice(), b"ab", b"ba"] {
objects.insert(key, b"value").unwrap();
}
assert_eq!(
objects
.prefix(b"a")
.into_result()
.unwrap()
.into_iter()
.map(|entry| entry.key)
.collect::<Vec<_>>(),
vec![b"aa".to_vec(), b"ab".to_vec()]
);
assert_eq!(
objects.get_shared(b"aa").unwrap().as_deref(),
Some(&b"value".to_vec())
);
}
}