use std::cmp::{Ordering, Reverse};
use std::collections::BinaryHeap;
use std::hash::Hash;
use std::ops::ControlFlow;
use std::sync::Arc;
use super::block::EntryIter;
use super::core::SegCore;
use super::generation::{GenLoc, Generation};
use super::hash::{SCAN_WINDOWS, cmp_hk, key_hash, window_range};
use super::page_index::IndexGroup;
use super::segment::Segment;
use crate::disk_loc::DiskLoc;
use crate::error::{DbError, DbResult};
use crate::key::Key;
enum Payload {
Tombstone,
Journal(DiskLoc),
Bytes(Vec<u8>),
}
struct Item<K> {
h: u64,
key: K,
payload: Payload,
}
struct SegmentStream {
segment: Arc<Segment>,
lo: u64,
hi: u64,
want_values: bool,
block: usize,
payload: Option<Arc<[u8]>>,
offset: usize,
group: Option<Arc<IndexGroup>>,
}
impl SegmentStream {
fn new(segment: Arc<Segment>, lo: u64, hi: u64, want_values: bool) -> DbResult<Self> {
let mut group = None;
let block = segment.locate_hash_in(lo, &mut group, None)?.unwrap_or(0);
Ok(Self {
segment,
lo,
hi,
want_values,
block,
payload: None,
offset: 0,
group,
})
}
fn next<K: Key>(&mut self) -> DbResult<Option<Item<K>>> {
loop {
let payload = match &self.payload {
Some(payload) => payload.clone(),
None => {
if self.block >= self.segment.block_count()?
|| self.segment.first_h_in(self.block, &mut self.group, None)? > self.hi
{
return Ok(None);
}
let payload =
self.segment
.block_payload_in(self.block, &mut self.group, None)?;
self.payload = Some(payload.clone());
self.offset = 0;
payload
}
};
if self.offset >= payload.len() {
self.payload = None;
self.block += 1;
continue;
}
let entry = EntryIter::new(&payload[self.offset..], self.segment.key_len())
.next()
.expect("the payload has bytes left")
.map_err(|fault| {
fault.into_db(
self.segment.id(),
Some(self.block as u32),
self.segment.sdat_path(),
)
})?;
self.offset += entry.raw.len();
let h = key_hash(entry.key, self.segment.seed());
if h < self.lo {
continue;
}
if h > self.hi {
return Ok(None);
}
entry.verify_crc().map_err(|fault| {
fault.into_db(
self.segment.id(),
Some(self.block as u32),
self.segment.sdat_path(),
)
})?;
let payload = if entry.is_tombstone() {
Payload::Tombstone
} else if self.want_values {
Payload::Bytes(entry.value.to_vec())
} else {
Payload::Bytes(Vec::new())
};
return Ok(Some(Item {
h,
key: K::from_bytes(entry.key),
payload,
}));
}
}
}
enum Stream<K: Key + Hash + Eq + Send + Sync> {
Generation {
generation: Arc<Generation<K>>,
entries: std::vec::IntoIter<(u64, K, GenLoc)>,
},
Segment(SegmentStream),
}
impl<K: Key + Hash + Eq + Send + Sync> Stream<K> {
fn next(&mut self) -> DbResult<Option<Item<K>>> {
match self {
Self::Generation { entries, .. } => Ok(entries.next().map(|(h, key, loc)| Item {
h,
key,
payload: if loc.tombstone {
Payload::Tombstone
} else {
Payload::Journal(loc.loc)
},
})),
Self::Segment(stream) => stream.next(),
}
}
}
struct Ranked<K> {
h: u64,
key: K,
rank: usize,
}
impl<K: Key> Ord for Ranked<K> {
fn cmp(&self, other: &Self) -> Ordering {
cmp_hk(self.h, self.key.as_bytes(), other.h, other.key.as_bytes())
.then(self.rank.cmp(&other.rank))
}
}
impl<K: Key> PartialOrd for Ranked<K> {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl<K: Key> PartialEq for Ranked<K> {
fn eq(&self, other: &Self) -> bool {
self.cmp(other) == Ordering::Equal
}
}
impl<K: Key> Eq for Ranked<K> {}
type Visit<'a, K> = dyn FnMut(DbResult<(K, Vec<u8>)>) -> ControlFlow<()> + 'a;
impl<K: Key + Hash + Eq + Send + Sync + 'static> SegCore<K> {
fn scan_window(
&self,
window: usize,
want_values: bool,
visit: &mut Visit<'_, K>,
) -> ControlFlow<()> {
let (lo, hi) = window_range(window);
let view = self.view();
let mut streams: Vec<Stream<K>> =
Vec::with_capacity(1 + view.frozen.len() + view.sealed.len());
for generation in std::iter::once(&view.active).chain(view.frozen.iter()) {
streams.push(Stream::Generation {
generation: generation.clone(),
entries: generation.snapshot_range(lo, hi, self.seed).into_iter(),
});
}
for segment in &view.sealed {
let stream = match SegmentStream::new(segment.clone(), lo, hi, want_values) {
Ok(stream) => stream,
Err(e) => {
let _ = visit(Err(e));
return ControlFlow::Break(());
}
};
streams.push(Stream::Segment(stream));
}
let mut heads: Vec<Option<Item<K>>> = Vec::with_capacity(streams.len());
let mut heap: BinaryHeap<Reverse<Ranked<K>>> = BinaryHeap::with_capacity(streams.len());
let advance = |rank: usize,
streams: &mut Vec<Stream<K>>,
heads: &mut Vec<Option<Item<K>>>,
heap: &mut BinaryHeap<Reverse<Ranked<K>>>|
-> DbResult<()> {
let item = streams[rank].next()?;
if let Some(item) = &item {
heap.push(Reverse(Ranked {
h: item.h,
key: item.key,
rank,
}));
}
heads[rank] = item;
Ok(())
};
for rank in 0..streams.len() {
heads.push(None);
if let Err(e) = advance(rank, &mut streams, &mut heads, &mut heap) {
let _ = visit(Err(e));
return ControlFlow::Break(());
}
}
while let Some(Reverse(top)) = heap.pop() {
let winner = heads[top.rank]
.take()
.expect("the heap and the heads agree");
if let Err(e) = advance(top.rank, &mut streams, &mut heads, &mut heap) {
let _ = visit(Err(e));
return ControlFlow::Break(());
}
while let Some(Reverse(next)) = heap.peek() {
if next.h != top.h || next.key.as_bytes() != top.key.as_bytes() {
break;
}
let rank = next.rank;
heap.pop();
heads[rank] = None;
if let Err(e) = advance(rank, &mut streams, &mut heads, &mut heap) {
let _ = visit(Err(e));
return ControlFlow::Break(());
}
}
let value = match winner.payload {
Payload::Tombstone => continue,
Payload::Bytes(bytes) => Ok(bytes),
Payload::Journal(_) if !want_values => Ok(Vec::new()),
Payload::Journal(loc) => match &streams[top.rank] {
Stream::Generation { generation, .. } => generation.read_value(winner.h, &loc),
Stream::Segment(_) => Err(DbError::Internal(
"a journal location came from a segment stream",
)),
},
};
match value {
Ok(bytes) => visit(Ok((winner.key, bytes)))?,
Err(e) => {
let _ = visit(Err(e));
return ControlFlow::Break(());
}
}
}
ControlFlow::Continue(())
}
fn scan_all(&self, want_values: bool, visit: &mut Visit<'_, K>) {
if self.order == super::sidecar::OrderKind::ByKey {
for row in self.ordered_iter(super::query::SegRange::all(), want_values, false) {
if visit(row).is_break() {
return;
}
}
return;
}
for window in 0..SCAN_WINDOWS {
if self.scan_window(window, want_values, visit).is_break() {
return;
}
}
}
pub(crate) fn scan(&self, visit: &mut Visit<'_, K>) {
self.scan_all(true, visit);
}
pub(crate) fn scan_keys(&self, visit: &mut dyn FnMut(DbResult<K>) -> ControlFlow<()>) {
self.scan_all(false, &mut |row| visit(row.map(|(key, _)| key)));
}
pub(crate) fn count_exact(&self) -> DbResult<u64> {
let mut count = 0u64;
let mut failure = None;
self.scan_keys(&mut |key| match key {
Ok(_) => {
count += 1;
ControlFlow::Continue(())
}
Err(e) => {
failure = Some(e);
ControlFlow::Break(())
}
});
failure.map_or(Ok(count), Err)
}
}
#[cfg(test)]
mod tests {
use crate::error::DbError;
use crate::key::Key;
use crate::seg::config::SegConfig;
use crate::seg::core::SegCore;
use crate::seg::hash::key_hash;
use crate::seg::seal::sdat_name;
use crate::seg::testkit::{TestKey, build_collection, key_of, open_core, value_of};
use std::collections::BTreeMap;
use std::ops::ControlFlow;
fn roomy() -> SegConfig {
SegConfig {
seal_max_keys: 1_000_000,
max_frozen_generations: 64,
..SegConfig::test()
}
}
fn collect(core: &SegCore<TestKey>) -> Vec<(TestKey, Vec<u8>)> {
let mut rows = Vec::new();
core.scan(&mut |row| {
rows.push(row.unwrap());
ControlFlow::Continue(())
});
rows
}
fn expected() -> BTreeMap<TestKey, Vec<u8>> {
let mut out = BTreeMap::new();
for i in (0..100u64).filter(|i| i % 10 != 9) {
out.insert(key_of(i), value_of(i));
}
for i in 110..200u64 {
out.insert(key_of(i), format!("frozen-{i}").into_bytes());
}
for i in 210..300u64 {
out.insert(key_of(i), format!("active-{i}").into_bytes());
}
out
}
#[test]
fn a_hash_window_scan_over_cold_segments_returns_every_row() {
let dir = tempfile::tempdir().unwrap();
build_collection(dir.path());
let hot = open_core(dir.path(), roomy());
let expected = collect(&hot);
drop(hot);
let cold = open_core(
dir.path(),
SegConfig {
resident_metadata_bytes: Some(0),
block_cache_bytes: 0,
..roomy()
},
);
assert!(cold.view().sealed.iter().all(|s| s.hot.is_none()));
assert_eq!(collect(&cold), expected);
let segment = cold.view().sealed[0].clone();
let before = segment.shared_io_requests();
let mut stream = super::SegmentStream::new(segment.clone(), 0, u64::MAX, true).unwrap();
while stream.next::<TestKey>().unwrap().is_some() {}
assert_eq!(
segment.shared_io_requests() - before,
segment.block_count().unwrap().div_ceil(128) as u64
);
}
#[test]
fn every_visible_key_comes_once_in_its_newest_version() {
let dir = tempfile::tempdir().unwrap();
build_collection(dir.path());
let core = open_core(dir.path(), roomy());
let rows = collect(&core);
let seen: BTreeMap<TestKey, Vec<u8>> = rows.iter().cloned().collect();
assert_eq!(rows.len(), seen.len(), "a key came twice");
assert_eq!(seen, expected());
}
#[test]
fn rows_come_in_hash_order() {
let dir = tempfile::tempdir().unwrap();
build_collection(dir.path());
let core = open_core(dir.path(), roomy());
let order: Vec<(u64, TestKey)> = collect(&core)
.iter()
.map(|(key, _)| (key_hash(key.as_bytes(), core.seed), *key))
.collect();
assert!(order.windows(2).all(|w| w[0] < w[1]));
}
#[test]
fn the_exact_count_is_the_number_of_visible_keys() {
let dir = tempfile::tempdir().unwrap();
build_collection(dir.path());
let core = open_core(dir.path(), roomy());
assert_eq!(core.count_exact().unwrap(), expected().len() as u64);
assert!(
core.len() as u64 > core.count_exact().unwrap(),
"len is an upper bound"
);
let mut keys = 0;
core.scan_keys(&mut |key| {
key.unwrap();
keys += 1;
ControlFlow::Continue(())
});
assert_eq!(keys, expected().len());
}
#[test]
fn an_empty_collection_yields_nothing() {
let dir = tempfile::tempdir().unwrap();
let core = open_core(dir.path(), roomy());
assert!(collect(&core).is_empty());
assert_eq!(core.count_exact().unwrap(), 0);
}
#[test]
fn a_collection_of_tombstones_yields_nothing() {
let dir = tempfile::tempdir().unwrap();
let core = open_core(dir.path(), roomy());
for i in 0..50 {
core.put(&key_of(i), b"v").unwrap();
}
core.seal().unwrap();
core.seal_oldest().unwrap();
for i in 0..50 {
core.delete(&key_of(i)).unwrap();
}
assert!(collect(&core).is_empty());
assert_eq!(core.len(), 50, "the shadowed versions are still counted");
}
#[test]
fn the_visitor_can_stop_the_scan() {
let dir = tempfile::tempdir().unwrap();
build_collection(dir.path());
let core = open_core(dir.path(), roomy());
let mut seen = 0;
core.scan(&mut |row| {
row.unwrap();
seen += 1;
if seen == 5 {
ControlFlow::Break(())
} else {
ControlFlow::Continue(())
}
});
assert_eq!(seen, 5);
}
#[test]
fn a_seal_in_the_middle_of_a_scan_changes_no_answer() {
let dir = tempfile::tempdir().unwrap();
let core = open_core(dir.path(), roomy());
for i in 0..2_000u64 {
core.put(&key_of(i), &value_of(i)).unwrap();
}
let mut rows = Vec::new();
core.scan(&mut |row| {
rows.push(row.unwrap());
if rows.len() == 100 {
core.seal().unwrap();
core.seal_oldest().unwrap();
}
ControlFlow::Continue(())
});
assert_eq!(core.view().sealed.len(), 1);
let seen: BTreeMap<TestKey, Vec<u8>> = rows.iter().cloned().collect();
assert_eq!(rows.len(), 2_000);
assert_eq!(seen.len(), 2_000, "a key came twice or not at all");
for i in 0..2_000u64 {
assert_eq!(seen.get(&key_of(i)), Some(&value_of(i)), "key {i}");
}
}
#[test]
fn a_scan_does_not_keep_a_retired_generation() {
let dir = tempfile::tempdir().unwrap();
let core = open_core(dir.path(), roomy());
for i in 0..2_000u64 {
core.put(&key_of(i), &value_of(i)).unwrap();
}
let generation = dir.path().join("gen/0000000000000001");
assert!(generation.exists(), "the scan starts over this generation");
let mut rows = 0;
let mut gone_during_scan = false;
core.scan(&mut |row| {
row.unwrap();
rows += 1;
if rows == 100 {
core.seal().unwrap();
core.seal_oldest().unwrap();
}
if rows > 1_000 && !generation.exists() {
gone_during_scan = true;
}
ControlFlow::Continue(())
});
assert!(gone_during_scan, "the scan held the generation to its end");
}
#[test]
fn a_damaged_block_ends_the_scan_with_an_error() {
let dir = tempfile::tempdir().unwrap();
build_collection(dir.path());
let core = open_core(dir.path(), roomy());
std::fs::OpenOptions::new()
.write(true)
.open(dir.path().join("seg").join(sdat_name(1, 1)))
.unwrap()
.set_len(64)
.unwrap();
let mut errors = 0;
let mut after_error = 0;
core.scan(&mut |row| {
match row {
Err(DbError::SegmentCorrupt { .. }) => errors += 1,
Err(other) => panic!("{other:?}"),
Ok(_) if errors > 0 => after_error += 1,
Ok(_) => {}
}
ControlFlow::Continue(())
});
assert_eq!(errors, 1);
assert_eq!(after_error, 0);
assert!(core.count_exact().is_err());
}
#[test]
fn an_entry_that_fails_its_own_crc_ends_the_scan_with_an_error() {
let dir = tempfile::tempdir().unwrap();
build_collection(dir.path());
let path = dir.path().join("seg").join(sdat_name(1, 1));
let (offset, len) = {
let core = open_core(dir.path(), roomy());
let segment = core.view().sealed[0].clone();
segment.hot().index.hash_index().range(0)
};
let mut bytes = std::fs::read(&path).unwrap();
let block = &mut bytes[offset as usize..(offset + len as u64) as usize];
block[crate::seg::block::BLOCK_HEADER_LEN] ^= 1;
let mut hasher = crc32fast::Hasher::new();
hasher.update(&block[..12]);
hasher.update(&block[crate::seg::block::BLOCK_HEADER_LEN..]);
block[12..16].copy_from_slice(&hasher.finalize().to_le_bytes());
std::fs::write(&path, bytes).unwrap();
let core = open_core(dir.path(), roomy());
let mut errors = 0;
core.scan(&mut |row| {
match row {
Err(DbError::SegmentCorrupt { block, .. }) => {
assert_eq!(block, Some(0));
errors += 1;
}
Err(other) => panic!("{other:?}"),
Ok(_) => {}
}
ControlFlow::Continue(())
});
assert_eq!(errors, 1);
assert!(core.count_exact().is_err());
}
#[test]
fn key_scan_and_count_do_not_read_generation_values() {
let dir = tempfile::tempdir().unwrap();
build_collection(dir.path());
let core = open_core(dir.path(), roomy());
let _damaged = crate::seg::testkit::UnreadableJournals::new(dir.path());
let mut keys = std::collections::BTreeSet::new();
core.scan_keys(&mut |key| {
assert!(keys.insert(key.unwrap()));
ControlFlow::Continue(())
});
assert_eq!(keys, expected().into_keys().collect());
assert_eq!(core.count_exact().unwrap(), keys.len() as u64);
let mut errors = 0;
core.scan(&mut |row| {
if row.is_err() {
errors += 1;
}
ControlFlow::Continue(())
});
assert_eq!(errors, 1);
}
#[test]
fn a_later_block_error_ends_stream_advancement() {
let dir = tempfile::tempdir().unwrap();
let core = open_core(
dir.path(),
SegConfig {
block_size: 256,
..roomy()
},
);
let keys: Vec<_> = (0..100_000)
.map(key_of)
.filter(|key| crate::seg::hash::window_of(key_hash(key, core.seed)) == 0)
.take(30)
.collect();
assert_eq!(keys.len(), 30);
for key in &keys {
core.put(key, &[7; 80]).unwrap();
}
core.seal().unwrap();
core.seal_oldest().unwrap();
let segment = core.view().sealed[0].clone();
assert!(segment.hot().index.hash_index().len() > 2);
let (offset, _) = segment.hot().index.hash_index().range(2);
std::fs::OpenOptions::new()
.write(true)
.open(segment.sdat_path())
.unwrap()
.set_len(offset)
.unwrap();
let (mut good, mut errors, mut after_error) = (0, 0, 0);
core.scan(&mut |row| {
match row {
Ok(_) if errors > 0 => after_error += 1,
Ok(_) => good += 1,
Err(DbError::SegmentCorrupt { block: Some(2), .. }) => errors += 1,
Err(other) => panic!("{other:?}"),
}
ControlFlow::Continue(())
});
assert!(good > 0);
assert_eq!((errors, after_error), (1, 0));
}
#[test]
fn equal_hash_heap_orders_distinct_keys_before_layer_rank() {
use super::Ranked;
use std::cmp::Reverse;
use std::collections::BinaryHeap;
let mut heap = BinaryHeap::new();
for (key, rank) in [(key_of(2), 0), (key_of(1), 2), (key_of(1), 0)] {
heap.push(Reverse(Ranked { h: 7, key, rank }));
}
let order: Vec<_> = std::iter::from_fn(|| heap.pop())
.map(|Reverse(row)| (row.key, row.rank))
.collect();
assert_eq!(order, [(key_of(1), 0), (key_of(1), 2), (key_of(2), 0)]);
assert!(
Ranked {
h: 7,
key: key_of(1),
rank: 0
} != Ranked {
h: 7,
key: key_of(2),
rank: 0
}
);
}
}