use super::{
block::EntryIter,
cache::SegBlockCache,
core::SegCore,
generation::{GenLoc, Generation},
hash::key_hash,
page_index::IndexGroup,
query::{SegRange, bound_key},
segment::Segment,
};
use crate::{
error::{DbError, DbResult},
key::Key,
map_index::Dir,
};
use std::{
cmp::{Ordering, Reverse},
collections::{BinaryHeap, HashMap, VecDeque},
hash::Hash,
sync::Arc,
};
const ROW_LIMIT: usize = 256;
const BYTE_LIMIT: usize = 1 << 20;
const CONSUMED_LIMIT: usize = 4096;
struct CarriedBlock {
group: Option<Arc<IndexGroup>>,
block: usize,
payload: Arc<[u8]>,
offsets: Arc<[usize]>,
}
enum Payload {
Tombstone,
Journal(GenLoc),
Block { offset: usize },
}
struct Item<K> {
key: K,
payload: Payload,
}
struct GenerationStream<K: Key + Hash + Eq + Send + Sync> {
generation: Arc<Generation<K>>,
shard: usize,
query: SegRange<K>,
cursor: Option<K>,
entries: std::vec::IntoIter<(K, GenLoc)>,
batch: usize,
done: bool,
}
impl<K: Key + Hash + Eq + Send + Sync> GenerationStream<K> {
fn next(&mut self) -> Option<Item<K>> {
if self.entries.len() == 0 && !self.done {
let query = self.query.clone().after(self.cursor.as_ref());
let batch = if query.empty {
Vec::new()
} else {
self.generation.ordered_batch(
self.shard,
query.start.as_ref(),
query.end.as_ref(),
query.dir,
self.batch,
)
};
self.done = batch.len() < self.batch;
self.entries = batch.into_iter();
}
self.entries.next().map(|(key, loc)| {
self.cursor = Some(key);
Item {
key,
payload: if loc.tombstone {
Payload::Tombstone
} else {
Payload::Journal(loc)
},
}
})
}
}
struct SegmentStream<K: Key> {
segment: Arc<Segment>,
query: SegRange<K>,
block: usize,
payload: Option<Arc<[u8]>>,
parsed: Option<Arc<[usize]>>,
offsets: VecDeque<usize>,
carried: Option<CarriedBlock>,
group: Option<Arc<IndexGroup>>,
done: bool,
}
impl<K: Key> SegmentStream<K> {
fn new(
segment: Arc<Segment>,
query: SegRange<K>,
carried: Option<CarriedBlock>,
cache: Option<&SegBlockCache>,
) -> DbResult<Self> {
let bound = match query.dir {
Dir::Asc => &query.start,
Dir::Desc => &query.end,
};
let mut group = carried.as_ref().and_then(|c| c.group.clone());
let block = if let Some(carried) = &carried {
carried.block
} else {
match bound_key(bound) {
Some(k) => segment.locate_key_in(k.as_bytes(), &mut group, cache)?,
None if query.dir == Dir::Asc => 0,
None => segment.block_count()? - 1,
}
};
Ok(Self {
segment,
query,
block,
payload: None,
parsed: None,
offsets: VecDeque::new(),
carried,
group,
done: false,
})
}
fn into_carried(self) -> Option<CarriedBlock> {
Some(CarriedBlock {
group: self.group,
block: self.block,
payload: self.payload?,
offsets: self.parsed?,
})
}
fn next(&mut self, core: &SegCore<K>, use_cache: bool) -> DbResult<Option<Item<K>>>
where
K: Hash + Eq + Send + Sync,
{
loop {
if self.done {
return Ok(None);
}
if self.payload.is_none() {
let block = self.block;
let (payload, parsed) = match self.carried.take_if(|c| c.block == block) {
Some(c) => {
self.group = c.group;
(c.payload, c.offsets)
}
None => {
let payload = self.segment.block_payload_in(
self.block,
&mut self.group,
use_cache.then_some(&core.cache),
)?;
let mut offsets = Vec::new();
let mut offset = 0;
for entry in EntryIter::new(&payload, self.segment.key_len()) {
let entry = entry.map_err(|e| {
e.into_db(
self.segment.id(),
Some(self.block as u32),
self.segment.sdat_path(),
)
})?;
offsets.push(offset);
offset += entry.raw.len();
}
(payload, Arc::from(offsets))
}
};
self.offsets = parsed.iter().copied().collect();
self.payload = Some(payload);
self.parsed = Some(parsed);
}
let offset = match self.query.dir {
Dir::Asc => self.offsets.pop_front(),
Dir::Desc => self.offsets.pop_back(),
};
let Some(offset) = offset else {
self.payload = None;
self.parsed = None;
match self.query.dir {
Dir::Asc if self.block + 1 < self.segment.block_count()? => self.block += 1,
Dir::Desc if self.block > 0 => self.block -= 1,
_ => self.done = true,
}
continue;
};
let payload = self.payload.as_ref().expect("loaded block");
let entry = EntryIter::new(&payload[offset..], self.segment.key_len())
.next()
.expect("known entry offset")
.map_err(|e| {
e.into_db(
self.segment.id(),
Some(self.block as u32),
self.segment.sdat_path(),
)
})?;
if !self.query.contains(entry.key) {
let past = match self.query.dir {
Dir::Asc => {
bound_key(&self.query.end).is_some_and(|k| entry.key >= k.as_bytes())
}
Dir::Desc => {
bound_key(&self.query.start).is_some_and(|k| entry.key <= k.as_bytes())
}
};
if past {
self.done = true;
return Ok(None);
}
continue;
}
entry.verify_crc().map_err(|e| {
e.into_db(
self.segment.id(),
Some(self.block as u32),
self.segment.sdat_path(),
)
})?;
return Ok(Some(Item {
key: K::from_bytes(entry.key),
payload: if entry.is_tombstone() {
Payload::Tombstone
} else {
Payload::Block { offset }
},
}));
}
}
fn value(&self, offset: usize) -> DbResult<Vec<u8>> {
let payload = self
.payload
.as_ref()
.ok_or(DbError::Internal("ordered block head lost its payload"))?;
let entry = EntryIter::new(&payload[offset..], self.segment.key_len())
.next()
.expect("known entry offset")
.map_err(|e| {
e.into_db(
self.segment.id(),
Some(self.block as u32),
self.segment.sdat_path(),
)
})?;
Ok(entry.value.to_vec())
}
}
enum Stream<K: Key + Hash + Eq + Send + Sync> {
Generation(GenerationStream<K>),
Segment(SegmentStream<K>),
}
impl<K: Key + Hash + Eq + Send + Sync> Stream<K> {
fn next(&mut self, core: &SegCore<K>, use_cache: bool) -> DbResult<Option<Item<K>>> {
match self {
Self::Generation(s) => Ok(s.next()),
Self::Segment(s) => s.next(core, use_cache),
}
}
fn value(
&self,
key: &K,
payload: Payload,
seed: u64,
want_values: bool,
) -> DbResult<Option<Vec<u8>>> {
if matches!(payload, Payload::Tombstone) {
return Ok(None);
}
if !want_values {
return Ok(Some(Vec::new()));
}
match (self, payload) {
(Self::Generation(s), Payload::Journal(loc)) => s
.generation
.read_value(key_hash(key.as_bytes(), seed), &loc.loc)
.map(Some),
(Self::Segment(s), Payload::Block { offset }) => s.value(offset).map(Some),
_ => Err(DbError::Internal(
"ordered payload disagrees with its stream",
)),
}
}
}
struct Ranked<K> {
key: K,
rank: usize,
dir: Dir,
}
impl<K: Key> Ord for Ranked<K> {
fn cmp(&self, other: &Self) -> Ordering {
let order = self.key.as_bytes().cmp(other.key.as_bytes());
(if self.dir == Dir::Asc {
order
} else {
order.reverse()
})
.then(self.rank.cmp(&other.rank))
}
}
impl<K: Key> PartialOrd for Ranked<K> {
fn partial_cmp(&self, o: &Self) -> Option<Ordering> {
Some(self.cmp(o))
}
}
impl<K: Key> PartialEq for Ranked<K> {
fn eq(&self, o: &Self) -> bool {
self.cmp(o) == Ordering::Equal
}
}
impl<K: Key> Eq for Ranked<K> {}
pub(crate) struct RawOrderedIter<'a, K: Key + Hash + Eq + Send + Sync> {
core: &'a SegCore<K>,
query: SegRange<K>,
cursor: Option<K>,
rows: VecDeque<(K, Vec<u8>)>,
error: Option<DbError>,
done: bool,
want_values: bool,
use_cache: bool,
row_limit: usize,
carried: HashMap<(u64, u32), CarriedBlock>,
}
impl<K: Key + Hash + Eq + Send + Sync + 'static> SegCore<K> {
pub(crate) fn ordered_iter(
&self,
query: SegRange<K>,
want_values: bool,
use_cache: bool,
) -> RawOrderedIter<'_, K> {
RawOrderedIter {
core: self,
query,
cursor: None,
rows: VecDeque::new(),
error: None,
done: false,
want_values,
use_cache,
row_limit: ROW_LIMIT,
carried: HashMap::new(),
}
}
}
impl<K: Key + Hash + Eq + Send + Sync + 'static> RawOrderedIter<'_, K> {
pub(crate) fn limit_rows(&mut self, rows: usize) {
self.row_limit = rows.clamp(1, ROW_LIMIT);
}
#[cfg(test)]
pub(crate) fn buffered_stats(&self) -> (usize, usize) {
(
self.rows.len(),
self.rows.iter().map(|(_, v)| v.len()).sum(),
)
}
fn refill(&mut self) -> DbResult<()> {
let query = self.query.clone().after(self.cursor.as_ref());
if query.empty {
self.done = true;
return Ok(());
}
metrics::counter!("armdb.seg.ordered_refills", "collection" => self.core.meta.name)
.increment(1);
let view = self.core.view();
let mut streams = Vec::new();
for (i, generation) in std::iter::once(&view.active)
.chain(view.frozen.iter())
.enumerate()
{
if i > 0
&& query
.since_ms
.is_some_and(|ms| generation.frozen_at_ms() < ms)
{
continue;
}
for shard in 0..generation.shard_count() {
streams.push(Stream::Generation(GenerationStream {
generation: generation.clone(),
shard,
query: query.clone(),
cursor: None,
entries: Vec::new().into_iter(),
batch: self.row_limit,
done: false,
}));
}
}
for segment in &view.sealed {
if segment
.key_range()
.is_some_and(|r| !query.overlaps(&r.min, &r.max))
{
continue;
}
if query
.since_ms
.is_some_and(|ms| segment.record().frozen_at_ms < ms)
{
continue;
}
let id = (segment.id(), segment.record().version);
let filter_len = segment
.prefix_filter_lens()
.iter()
.map(|n| usize::from(*n))
.filter(|n| *n <= query.pruning_prefix.len())
.max();
if !self.carried.contains_key(&id)
&& let Some(n) = filter_len
&& !segment.prefix_may_contain(
&query.pruning_prefix[..n],
self.use_cache.then_some(&self.core.cache),
)?
{
continue;
}
metrics::counter!("armdb.seg.ordered_reseeks", "collection" => self.core.meta.name)
.increment(1);
let carried = self.carried.remove(&id);
streams.push(Stream::Segment(SegmentStream::new(
segment.clone(),
query.clone(),
carried,
self.use_cache.then_some(&self.core.cache),
)?));
}
let result = self.merge(&query, &mut streams);
self.carried.clear();
for stream in streams {
if let Stream::Segment(s) = stream {
let id = (s.segment.id(), s.segment.record().version);
if let Some(c) = s.into_carried() {
self.carried.insert(id, c);
}
}
}
result
}
fn merge(&mut self, query: &SegRange<K>, streams: &mut [Stream<K>]) -> DbResult<()> {
let mut heads = Vec::with_capacity(streams.len());
let mut heap = BinaryHeap::new();
for (rank, stream) in streams.iter_mut().enumerate() {
let item = stream.next(self.core, self.use_cache)?;
if let Some(item) = &item {
heap.push(Reverse(Ranked {
key: item.key,
rank,
dir: query.dir,
}));
}
heads.push(item);
}
let mut bytes: usize = 0;
for _ in 0..CONSUMED_LIMIT {
let Some(Reverse(top)) = heap.pop() else {
self.done = true;
return Ok(());
};
let item = heads[top.rank].take().expect("heap head");
let value = streams[top.rank].value(
&item.key,
item.payload,
self.core.seed,
self.want_values,
)?;
if let Some(value) = value {
if !self.rows.is_empty() && bytes.saturating_add(value.len()) > BYTE_LIMIT {
return Ok(());
}
bytes += value.len();
self.rows.push_back((item.key, value));
}
self.cursor = Some(item.key);
let mut ranks = vec![top.rank];
while heap
.peek()
.is_some_and(|Reverse(next)| next.key.as_bytes() == item.key.as_bytes())
{
let Reverse(next) = heap.pop().expect("peeked head");
heads[next.rank] = None;
ranks.push(next.rank);
}
if self.rows.len() == self.row_limit || bytes >= BYTE_LIMIT {
return Ok(());
}
for rank in ranks {
let next = streams[rank].next(self.core, self.use_cache)?;
if let Some(item) = &next {
heap.push(Reverse(Ranked {
key: item.key,
rank,
dir: query.dir,
}));
}
heads[rank] = next;
}
}
Ok(())
}
}
impl<K: Key + Hash + Eq + Send + Sync + 'static> Iterator for RawOrderedIter<'_, K> {
type Item = DbResult<(K, Vec<u8>)>;
fn next(&mut self) -> Option<Self::Item> {
loop {
if let Some(row) = self.rows.pop_front() {
return Some(Ok(row));
}
if let Some(error) = self.error.take() {
return Some(Err(error));
}
if self.done {
return None;
}
if let Err(error) = self.refill() {
self.done = true;
self.error = Some(error);
}
}
}
}