use std::io::{Read, Seek, SeekFrom, Write};
use std::path::{Path, PathBuf};
use std::time::{SystemTime, UNIX_EPOCH};
use xorf::Filter;
use crate::error::EdgestoreError;
use crate::manifest::Manifest;
use crate::memtable::MemTable;
use crate::types::{
cohort_bucket_for, death_time_for, MemEntry, Operation, SegmentId, SegmentMeta,
};
pub mod in_memory;
pub(crate) const SEGMENT_BLOCK_MAGIC: u32 = 0x45445347; pub(crate) const SEGMENT_FILE_MAGIC: u32 = 0x45445347;
pub(crate) const SEGMENT_FORMAT_VERSION: u8 = 1;
pub(crate) const SEGMENT_HEADER_LEN: usize = 8;
const BLOCK_TARGET_BYTES: usize = 3900;
pub(crate) const SEGMENT_BLOCK_SIZE: usize = 4096;
pub(crate) const MAX_BLOCK_DECOMPRESSED: usize = SEGMENT_BLOCK_SIZE * 512;
pub const SPARSE_INDEX_STRIDE: usize = 64;
pub(crate) fn serialize_entry(key: &[u8], entry: &MemEntry) -> Vec<u8> {
let val = entry.value.as_deref().unwrap_or(&[]);
let mut buf = Vec::with_capacity(4 + key.len() + 4 + val.len() + 21);
buf.extend_from_slice(&(key.len() as u32).to_le_bytes());
buf.extend_from_slice(key);
buf.extend_from_slice(&(val.len() as u32).to_le_bytes());
buf.extend_from_slice(val);
buf.extend_from_slice(&entry.lsn.to_le_bytes());
buf.extend_from_slice(&entry.timestamp.to_le_bytes());
buf.extend_from_slice(&entry.ttl.to_le_bytes());
buf.push(match entry.op {
Operation::Put => 1,
Operation::Delete => 2,
});
buf
}
pub(crate) fn deserialize_entry(
buf: &[u8],
pos: &mut usize,
) -> Result<(Vec<u8>, MemEntry), EdgestoreError> {
macro_rules! read_bytes {
($n:expr, $field:literal) => {{
if buf.len() < *pos + $n {
return Err(EdgestoreError::SegmentCorrupt(format!(
"buffer too short: field {}",
$field
)));
}
let slice = &buf[*pos..*pos + $n];
*pos += $n;
slice
}};
}
let key_len = u32::from_le_bytes(read_bytes!(4, "key_len").try_into().unwrap()) as usize;
let key = read_bytes!(key_len, "key").to_vec();
let val_len = u32::from_le_bytes(read_bytes!(4, "val_len").try_into().unwrap()) as usize;
let val_bytes = read_bytes!(val_len, "val").to_vec();
let lsn = u64::from_le_bytes(read_bytes!(8, "lsn").try_into().unwrap());
let timestamp = i64::from_le_bytes(read_bytes!(8, "timestamp").try_into().unwrap());
let ttl = u32::from_le_bytes(read_bytes!(4, "ttl").try_into().unwrap());
let op_byte = read_bytes!(1, "op")[0];
let op = match op_byte {
1 => Operation::Put,
2 => Operation::Delete,
b => {
return Err(EdgestoreError::SegmentCorrupt(format!(
"unknown op byte: {}",
b
)))
}
};
let value = if op == Operation::Delete {
None
} else {
Some(val_bytes)
};
Ok((
key.clone(),
MemEntry {
key,
value,
op,
lsn,
timestamp,
ttl,
},
))
}
fn hash_key_to_u64(key: &[u8]) -> u64 {
let h = blake3::hash(key);
u64::from_le_bytes(h.as_bytes()[0..8].try_into().unwrap())
}
pub(crate) fn build_xor_filter(keys: &[Vec<u8>]) -> Result<xorf::Xor8, EdgestoreError> {
let mut hashes: Vec<u64> = keys.iter().map(|k| hash_key_to_u64(k)).collect();
hashes.sort_unstable();
hashes.dedup();
Ok(xorf::Xor8::from(hashes.as_slice()))
}
pub(crate) fn write_xf_file(filter: &xorf::Xor8, path: &Path) -> Result<(), EdgestoreError> {
let mut f = std::fs::File::create(path)?;
f.write_all(&filter.seed.to_le_bytes())?;
f.write_all(&(filter.block_length as u64).to_le_bytes())?;
f.write_all(&(filter.fingerprints.len() as u64).to_le_bytes())?;
f.write_all(&filter.fingerprints)?;
f.sync_all()?;
Ok(())
}
pub(crate) fn read_xf_file(path: &Path) -> Result<xorf::Xor8, EdgestoreError> {
let mut f = std::fs::File::open(path)?;
let mut buf8 = [0u8; 8];
f.read_exact(&mut buf8)
.map_err(|_| EdgestoreError::SegmentCorrupt("xf: truncated seed".to_string()))?;
let seed = u64::from_le_bytes(buf8);
f.read_exact(&mut buf8)
.map_err(|_| EdgestoreError::SegmentCorrupt("xf: truncated block_length".to_string()))?;
let block_length = u64::from_le_bytes(buf8) as usize;
f.read_exact(&mut buf8).map_err(|_| {
EdgestoreError::SegmentCorrupt("xf: truncated fingerprints_len".to_string())
})?;
let fp_len = u64::from_le_bytes(buf8) as usize;
if fp_len > 1_000_000 {
return Err(EdgestoreError::SegmentCorrupt(
"xf: fingerprints_len too large".to_string(),
));
}
let mut fingerprints = vec![0u8; fp_len];
f.read_exact(&mut fingerprints)
.map_err(|_| EdgestoreError::SegmentCorrupt("xf: truncated fingerprints".to_string()))?;
Ok(xorf::Xor8 {
seed,
block_length,
fingerprints: fingerprints.into_boxed_slice(),
})
}
pub(crate) fn filter_contains(filter: &xorf::Xor8, key: &[u8]) -> bool {
filter.contains(&hash_key_to_u64(key))
}
pub(crate) fn write_idx_file(index: &[(Vec<u8>, u64)], path: &Path) -> Result<(), EdgestoreError> {
let mut f = std::fs::File::create(path)?;
f.write_all(&(index.len() as u64).to_le_bytes())?;
for (key, offset) in index {
f.write_all(&(key.len() as u32).to_le_bytes())?;
f.write_all(key)?;
f.write_all(&offset.to_le_bytes())?;
}
f.sync_all()?;
Ok(())
}
pub fn read_idx_file(path: &Path) -> Result<Vec<(Vec<u8>, u64)>, EdgestoreError> {
let mut f = std::fs::File::open(path)?;
let mut buf8 = [0u8; 8];
f.read_exact(&mut buf8)
.map_err(|_| EdgestoreError::SegmentCorrupt("idx: truncated count".to_string()))?;
let count = u64::from_le_bytes(buf8) as usize;
if count > 10_000_000 {
return Err(EdgestoreError::SegmentCorrupt(
"idx: count too large".to_string(),
));
}
let mut entries = Vec::with_capacity(count);
for _ in 0..count {
let mut buf4 = [0u8; 4];
f.read_exact(&mut buf4)
.map_err(|_| EdgestoreError::SegmentCorrupt("idx: truncated key_len".to_string()))?;
let key_len = u32::from_le_bytes(buf4) as usize;
let mut key = vec![0u8; key_len];
f.read_exact(&mut key)
.map_err(|_| EdgestoreError::SegmentCorrupt("idx: truncated key".to_string()))?;
f.read_exact(&mut buf8)
.map_err(|_| EdgestoreError::SegmentCorrupt("idx: truncated offset".to_string()))?;
let offset = u64::from_le_bytes(buf8);
entries.push((key, offset));
}
Ok(entries)
}
pub struct SegmentWriter {
base_path: PathBuf,
segment_id: SegmentId,
cohort_window_secs: u64,
}
impl SegmentWriter {
pub fn new(base_path: PathBuf, segment_id: SegmentId, cohort_window_secs: u64) -> Self {
SegmentWriter {
base_path,
segment_id,
cohort_window_secs,
}
}
fn dat_path(&self) -> PathBuf {
self.base_path
.join(format!("segment-{:08}.dat", self.segment_id))
}
fn idx_path(&self) -> PathBuf {
self.base_path
.join(format!("segment-{:08}.idx", self.segment_id))
}
fn xf_path(&self) -> PathBuf {
self.base_path
.join(format!("segment-{:08}.xf", self.segment_id))
}
fn meta_path(&self) -> PathBuf {
self.base_path
.join(format!("segment-{:08}.meta", self.segment_id))
}
#[allow(clippy::type_complexity)]
fn write_dat_and_index(
&self,
entries: &[(Vec<u8>, MemEntry)],
) -> Result<(u64, u64, Vec<(Vec<u8>, u64)>), EdgestoreError> {
let mut dat = std::fs::File::create(self.dat_path())?;
dat.write_all(&SEGMENT_FILE_MAGIC.to_le_bytes())?;
dat.write_all(&[SEGMENT_FORMAT_VERSION, 0, 0, 0])?;
let mut current_block: Vec<u8> = Vec::new();
let mut sparse_index: Vec<(Vec<u8>, u64)> = Vec::new();
let mut block_start_offset: u64 = SEGMENT_HEADER_LEN as u64;
let mut file_offset: u64 = SEGMENT_HEADER_LEN as u64;
let mut compressed_total: u64 = 0;
let mut uncompressed_total: u64 = 0;
for (idx, (key, entry)) in entries.iter().enumerate() {
let serialized = serialize_entry(key, entry);
uncompressed_total += serialized.len() as u64;
if idx.is_multiple_of(SPARSE_INDEX_STRIDE) {
sparse_index.push((key.clone(), block_start_offset));
}
current_block.extend_from_slice(&serialized);
if current_block.len() >= BLOCK_TARGET_BYTES {
let written = flush_block_to_file(&mut dat, ¤t_block)?;
compressed_total += written as u64;
file_offset += written as u64;
block_start_offset = file_offset;
current_block.clear();
}
}
if !current_block.is_empty() {
let written = flush_block_to_file(&mut dat, ¤t_block)?;
compressed_total += written as u64;
}
dat.sync_all()?;
write_idx_file(&sparse_index, &self.idx_path())?;
Ok((compressed_total, uncompressed_total, sparse_index))
}
pub fn flush(
&mut self,
entries: &[(Vec<u8>, MemEntry)],
) -> Result<SegmentMeta, EdgestoreError> {
if entries.is_empty() {
return Err(EdgestoreError::SegmentCorrupt("empty entries".to_string()));
}
let (compressed_bytes, uncompressed_bytes, _) = self.write_dat_and_index(entries)?;
let keys: Vec<Vec<u8>> = entries.iter().map(|(k, _)| k.clone()).collect();
let filter = build_xor_filter(&keys)?;
write_xf_file(&filter, &self.xf_path())?;
let dat_bytes = std::fs::read(self.dat_path())?;
let segment_hash = blake3::hash(&dat_bytes).as_bytes().to_vec();
let first = &entries[0].1;
let cohort_bucket = cohort_bucket_for(first.timestamp, first.ttl, self.cohort_window_secs);
let death_time = entries
.iter()
.map(|(_, e)| death_time_for(e.timestamp, e.ttl, self.cohort_window_secs))
.max()
.unwrap_or(0);
let mut key_hashes: Vec<[u8; 32]> =
keys.iter().map(|k| *blake3::hash(k).as_bytes()).collect();
key_hashes.sort_unstable();
let mut hasher = blake3::Hasher::new();
for h in &key_hashes {
hasher.update(h);
}
let merkle_root = hasher.finalize().as_bytes().to_vec();
let min_key = entries.first().map(|(k, _)| k.clone()).unwrap();
let max_key = entries.last().map(|(k, _)| k.clone()).unwrap();
let min_lsn = entries.iter().map(|(_, e)| e.lsn).min().unwrap_or(0);
let max_lsn = entries.iter().map(|(_, e)| e.lsn).max().unwrap_or(0);
let created_at = SystemTime::now()
.duration_since(UNIX_EPOCH)
.unwrap_or_default()
.as_nanos() as i64;
let meta = SegmentMeta {
segment_id: self.segment_id,
segment_hash,
min_key,
max_key,
min_lsn,
max_lsn,
record_count: entries.len() as u64,
compressed_bytes,
uncompressed_bytes,
compression: "zstd:1".to_string(),
cohort_bucket,
death_time,
merkle_root,
created_at,
text_index_stripped: false,
vector_index_stripped: false,
};
let meta_file = std::fs::File::create(self.meta_path())?;
serde_json::to_writer_pretty(meta_file, &meta)
.map_err(|e| EdgestoreError::SegmentCorrupt(format!("meta serialize: {}", e)))?;
Ok(meta)
}
}
fn flush_block_to_file(dat: &mut std::fs::File, block: &[u8]) -> Result<usize, EdgestoreError> {
let compressed = zstd::encode_all(block, 1)
.map_err(|e| EdgestoreError::SegmentCorrupt(format!("zstd encode: {}", e)))?;
let compressed_len = compressed.len() as u32;
let payload_size = 8 + compressed.len();
let aligned_size = if payload_size.is_multiple_of(SEGMENT_BLOCK_SIZE) {
payload_size
} else {
(payload_size / SEGMENT_BLOCK_SIZE + 1) * SEGMENT_BLOCK_SIZE
};
let padding = aligned_size - payload_size;
dat.write_all(&SEGMENT_BLOCK_MAGIC.to_le_bytes())?;
dat.write_all(&compressed_len.to_le_bytes())?;
dat.write_all(&compressed)?;
if padding > 0 {
dat.write_all(&vec![0u8; padding])?;
}
Ok(aligned_size)
}
pub struct FlushWork {
pub entries: Vec<(Vec<u8>, MemEntry)>,
pub segment_id: SegmentId,
pub base_path: PathBuf,
pub cohort_window_secs: u64,
pub flushed_max_lsn: u64,
}
impl FlushWork {
pub fn execute(self) -> Result<SegmentMeta, EdgestoreError> {
debug_assert!(!self.entries.is_empty(), "FlushWork::execute: entries must not be empty");
let mut writer = SegmentWriter::new(self.base_path, self.segment_id, self.cohort_window_secs);
let meta = writer.flush(&self.entries)?;
debug_assert_eq!(meta.segment_id, self.segment_id, "segment ID must match reserved ID");
Ok(meta)
}
}
#[derive(Clone)]
pub struct SegmentReader {
base_path: PathBuf,
segment_id: SegmentId,
pub meta: SegmentMeta,
filter: xorf::Xor8,
index: Vec<(Vec<u8>, u64)>,
}
impl SegmentReader {
fn dat_path(&self) -> PathBuf {
self.base_path
.join(format!("segment-{:08}.dat", self.segment_id))
}
pub fn open(
base_path: PathBuf,
segment_id: SegmentId,
) -> Result<SegmentReader, EdgestoreError> {
let meta_path = base_path.join(format!("segment-{:08}.meta", segment_id));
let xf_path = base_path.join(format!("segment-{:08}.xf", segment_id));
let idx_path = base_path.join(format!("segment-{:08}.idx", segment_id));
let meta_file = std::fs::File::open(&meta_path)?;
let meta: SegmentMeta = serde_json::from_reader(meta_file)
.map_err(|e| EdgestoreError::SegmentCorrupt(format!("meta parse: {}", e)))?;
let filter = read_xf_file(&xf_path)?;
let index = read_idx_file(&idx_path)?;
Ok(SegmentReader {
base_path,
segment_id,
meta,
filter,
index,
})
}
#[allow(clippy::type_complexity)]
fn read_block_at(
&self,
dat: &mut std::fs::File,
offset: u64,
) -> Result<(Vec<(Vec<u8>, MemEntry)>, usize), EdgestoreError> {
read_block_at_offset(dat, offset)
}
pub fn get(&self, key: &[u8]) -> Result<Option<MemEntry>, EdgestoreError> {
if !filter_contains(&self.filter, key) {
return Ok(None);
}
let start_offset = find_block_offset(&self.index, key);
let mut dat = std::fs::File::open(self.dat_path())?;
let dat_len = dat.metadata()?.len();
let mut current_offset = start_offset;
loop {
if current_offset >= dat_len {
break;
}
let (entries, aligned_size) = self.read_block_at(&mut dat, current_offset)?;
if entries.is_empty() || aligned_size == 0 {
break;
}
for (k, entry) in &entries {
if k == key {
return Ok(Some(entry.clone()));
}
if k.as_slice() > key {
return Ok(None);
}
}
current_offset += aligned_size as u64;
}
Ok(None)
}
pub fn range_scan(
&self,
start: &[u8],
end: &[u8],
) -> Result<Vec<(Vec<u8>, MemEntry)>, EdgestoreError> {
if end < self.meta.min_key.as_slice() || start > self.meta.max_key.as_slice() {
return Ok(vec![]);
}
let start_offset = find_block_offset(&self.index, start);
let mut dat = std::fs::File::open(self.dat_path())?;
let dat_len = dat.metadata()?.len();
let mut current_offset = start_offset;
let mut results = Vec::new();
loop {
if current_offset >= dat_len {
break;
}
let (entries, aligned_size) = self.read_block_at(&mut dat, current_offset)?;
if entries.is_empty() || aligned_size == 0 {
break;
}
let mut past_end = false;
for (k, entry) in entries {
if k.as_slice() >= end {
past_end = true;
break;
}
if k.as_slice() >= start {
results.push((k, entry));
}
}
if past_end {
break;
}
current_offset += aligned_size as u64;
}
Ok(results)
}
}
fn find_block_offset(index: &[(Vec<u8>, u64)], query_key: &[u8]) -> u64 {
if index.is_empty() {
return 8;
} let pos = index.partition_point(|(k, _)| k.as_slice() <= query_key);
if pos == 0 {
index[0].1
} else {
index[pos - 1].1
}
}
#[allow(clippy::type_complexity)]
pub(crate) fn read_block_at_offset(
dat: &mut std::fs::File,
offset: u64,
) -> Result<(Vec<(Vec<u8>, MemEntry)>, usize), EdgestoreError> {
dat.seek(SeekFrom::Start(offset))?;
let mut buf4 = [0u8; 4];
match dat.read_exact(&mut buf4) {
Ok(_) => {}
Err(e) if e.kind() == std::io::ErrorKind::UnexpectedEof => return Ok((vec![], 0)),
Err(e) => return Err(EdgestoreError::Io(e)),
}
let magic = u32::from_le_bytes(buf4);
if magic != SEGMENT_BLOCK_MAGIC {
return Ok((vec![], 0));
}
dat.read_exact(&mut buf4)?;
let compressed_len = u32::from_le_bytes(buf4) as usize;
let mut compressed = vec![0u8; compressed_len];
dat.read_exact(&mut compressed)?;
let payload_size = 8 + compressed_len;
let aligned_size = if payload_size.is_multiple_of(SEGMENT_BLOCK_SIZE) {
payload_size
} else {
(payload_size / SEGMENT_BLOCK_SIZE + 1) * SEGMENT_BLOCK_SIZE
};
let decompressed = zstd::decode_all(compressed.as_slice())
.map_err(|e| EdgestoreError::SegmentCorrupt(format!("zstd decode: {}", e)))?;
if decompressed.len() > MAX_BLOCK_DECOMPRESSED {
return Err(EdgestoreError::SegmentCorrupt(
"decompressed block too large".to_string(),
));
}
let mut entries = Vec::new();
let mut pos = 0;
while pos < decompressed.len() {
match deserialize_entry(&decompressed, &mut pos) {
Ok(entry) => entries.push(entry),
Err(_) => break,
}
}
Ok((entries, aligned_size))
}
pub(crate) fn parse_dat_entries(
data: &[u8],
) -> Result<Vec<(Vec<u8>, MemEntry)>, EdgestoreError> {
let mut entries = Vec::new();
let mut offset = SEGMENT_HEADER_LEN;
while offset < data.len() {
if offset + 8 > data.len() {
break;
}
let magic = u32::from_le_bytes(data[offset..offset + 4].try_into().unwrap());
if magic != SEGMENT_BLOCK_MAGIC {
break;
}
let compressed_len =
u32::from_le_bytes(data[offset + 4..offset + 8].try_into().unwrap()) as usize;
let payload_size = 8 + compressed_len;
let aligned_size = if payload_size.is_multiple_of(SEGMENT_BLOCK_SIZE) {
payload_size
} else {
(payload_size / SEGMENT_BLOCK_SIZE + 1) * SEGMENT_BLOCK_SIZE
};
if offset + 8 + compressed_len > data.len() {
break;
}
let compressed = &data[offset + 8..offset + 8 + compressed_len];
let decompressed = zstd::decode_all(compressed).map_err(|e| {
EdgestoreError::SegmentCorrupt(format!("parse_dat_entries zstd decode: {e}"))
})?;
if decompressed.len() > MAX_BLOCK_DECOMPRESSED {
return Err(EdgestoreError::SegmentCorrupt(
"decompressed block too large".to_string(),
));
}
let mut pos = 0;
while pos < decompressed.len() {
match deserialize_entry(&decompressed, &mut pos) {
Ok(entry) => entries.push(entry),
Err(_) => break,
}
}
offset += aligned_size;
}
Ok(entries)
}
pub(crate) struct SegmentCursor {
dat: std::fs::File,
dat_len: u64,
current_offset: u64,
start: Vec<u8>,
end: Vec<u8>,
buffer: std::collections::VecDeque<(Vec<u8>, MemEntry)>,
done: bool,
}
impl SegmentCursor {
pub(crate) fn open(
reader: &SegmentReader,
start: &[u8],
end: &[u8],
) -> Result<Option<Self>, EdgestoreError> {
if end <= reader.meta.min_key.as_slice() || start > reader.meta.max_key.as_slice() {
return Ok(None);
}
let start_offset = find_block_offset(&reader.index, start);
let dat = std::fs::File::open(reader.dat_path())?;
let dat_len = dat.metadata()?.len();
Ok(Some(SegmentCursor {
dat,
dat_len,
current_offset: start_offset,
start: start.to_vec(),
end: end.to_vec(),
buffer: std::collections::VecDeque::new(),
done: false,
}))
}
fn fill(&mut self) -> Result<(), EdgestoreError> {
while self.buffer.is_empty() && !self.done {
if self.current_offset >= self.dat_len {
self.done = true;
break;
}
let (entries, aligned_size) =
read_block_at_offset(&mut self.dat, self.current_offset)?;
if entries.is_empty() || aligned_size == 0 {
self.done = true;
break;
}
self.current_offset += aligned_size as u64;
for (k, entry) in entries {
if k.as_slice() >= self.end.as_slice() {
self.done = true;
break;
}
if k.as_slice() >= self.start.as_slice() {
self.buffer.push_back((k, entry));
}
}
}
Ok(())
}
pub(crate) fn pop(&mut self) -> Result<Option<(Vec<u8>, MemEntry)>, EdgestoreError> {
self.fill()?;
Ok(self.buffer.pop_front())
}
}
pub(crate) struct SegmentStore {
base_path: PathBuf,
manifest: Manifest,
readers: Vec<SegmentReader>,
next_segment_id: SegmentId,
cohort_window_secs: u64,
}
impl SegmentStore {
pub(crate) fn open(
base_path: PathBuf,
cohort_window_secs: u64,
) -> Result<SegmentStore, EdgestoreError> {
let manifest_path = base_path.join("manifest.mf");
let manifest = Manifest::open(&manifest_path)?;
let mut readers = Vec::new();
let mut next_id: SegmentId = 0;
for meta in manifest.list_segments() {
let reader = SegmentReader::open(base_path.clone(), meta.segment_id)?;
if meta.segment_id >= next_id {
next_id = meta.segment_id + 1;
}
readers.push(reader);
}
Ok(SegmentStore {
base_path,
manifest,
readers,
next_segment_id: next_id,
cohort_window_secs,
})
}
pub(crate) fn prepare_flush(&mut self, memtable: &dyn MemTable) -> Option<FlushWork> {
let entries = memtable.iter();
debug_assert!(!entries.is_empty() || memtable.is_empty(), "iter vs is_empty mismatch");
if entries.is_empty() {
return None;
}
let flushed_max_lsn = entries.iter().map(|(_, e)| e.lsn).max().unwrap_or(0);
let segment_id = self.next_segment_id;
self.next_segment_id += 1;
debug_assert!(segment_id < self.next_segment_id, "segment_id must advance");
Some(FlushWork {
entries,
segment_id,
base_path: self.base_path.clone(),
cohort_window_secs: self.cohort_window_secs,
flushed_max_lsn,
})
}
pub(crate) fn finalize_segment(&mut self, meta: SegmentMeta) -> Result<(), EdgestoreError> {
debug_assert!(meta.segment_id < self.next_segment_id, "meta must use a reserved ID");
self.manifest.add_segment(meta.clone())?;
let reader = SegmentReader::open(self.base_path.clone(), meta.segment_id)?;
self.readers.push(reader);
debug_assert!(!self.readers.is_empty(), "reader list must not be empty after finalize");
Ok(())
}
pub(crate) fn next_segment_id(&self) -> SegmentId {
self.next_segment_id
}
pub(crate) fn segment_ids(&self) -> Vec<crate::types::SegmentId> {
self.readers.iter().map(|r| r.segment_id).collect()
}
pub(crate) fn clone_readers_for(&self, ids: &[SegmentId]) -> Vec<SegmentReader> {
let id_set: std::collections::HashSet<SegmentId> = ids.iter().copied().collect();
self.readers
.iter()
.filter(|r| id_set.contains(&r.segment_id))
.cloned()
.collect()
}
pub(crate) fn list_segment_metas(&self) -> &[SegmentMeta] {
self.manifest.list_segments()
}
pub(crate) fn alloc_segment_id(&mut self) -> SegmentId {
let id = self.next_segment_id;
self.next_segment_id += 1;
id
}
pub(crate) fn add_imported_segment(
&mut self,
meta: SegmentMeta,
reader: SegmentReader,
) -> Result<(), EdgestoreError> {
self.manifest.add_segment(meta)?;
self.readers.push(reader);
Ok(())
}
pub(crate) fn base_path(&self) -> &std::path::Path {
&self.base_path
}
pub(crate) fn reader_for(&self, segment_id: SegmentId) -> Option<&SegmentReader> {
self.readers.iter().find(|r| r.segment_id == segment_id)
}
pub(crate) fn replace_segment(
&mut self,
old_id: SegmentId,
new_meta: SegmentMeta,
new_reader: SegmentReader,
) -> Result<(), EdgestoreError> {
self.manifest.remove_segments(&[old_id])?;
self.readers.retain(|r| r.segment_id != old_id);
self.manifest.add_segment(new_meta)?;
self.readers.push(new_reader);
for ext in &["dat", "idx", "xf", "meta"] {
let path = self
.base_path
.join(format!("segment-{:08}.{}", old_id, ext));
if path.exists() {
std::fs::remove_file(&path).map_err(EdgestoreError::Io)?;
}
}
Ok(())
}
pub(crate) fn remove_segment(&mut self, id: SegmentId) -> Result<(), EdgestoreError> {
self.manifest.remove_segments(&[id])?;
self.readers.retain(|r| r.segment_id != id);
for ext in &["dat", "idx", "xf", "meta"] {
let path = self.base_path.join(format!("segment-{:08}.{}", id, ext));
if path.exists() {
std::fs::remove_file(&path).map_err(EdgestoreError::Io)?;
}
}
Ok(())
}
pub(crate) fn get(&self, key: &[u8]) -> Result<Option<MemEntry>, EdgestoreError> {
for reader in self.readers.iter().rev() {
if let Some(entry) = reader.get(key)? {
return Ok(Some(entry));
}
}
Ok(None)
}
pub(crate) fn range_scan_budgeted(
&self,
start: &[u8],
end: &[u8],
max_items: Option<usize>,
) -> Result<(Vec<(Vec<u8>, MemEntry)>, bool), EdgestoreError> {
let mut cursors: Vec<SegmentCursor> = Vec::with_capacity(self.readers.len());
for reader in &self.readers {
if let Some(cursor) = SegmentCursor::open(reader, start, end)? {
cursors.push(cursor);
}
}
if cursors.is_empty() {
return Ok((vec![], false));
}
use std::collections::BinaryHeap;
use std::cmp::Ordering;
struct HeapItem {
key: Vec<u8>,
entry: MemEntry,
cursor_idx: usize,
}
impl PartialEq for HeapItem {
fn eq(&self, other: &Self) -> bool {
self.key == other.key
}
}
impl Eq for HeapItem {}
impl Ord for HeapItem {
fn cmp(&self, other: &Self) -> Ordering {
let key_cmp = other.key.cmp(&self.key);
if key_cmp != Ordering::Equal {
return key_cmp;
}
other.entry.lsn.cmp(&self.entry.lsn)
}
}
impl PartialOrd for HeapItem {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
let mut heap = BinaryHeap::new();
for (i, cursor) in cursors.iter_mut().enumerate() {
if let Some((k, e)) = cursor.pop()? {
heap.push(HeapItem { key: k, entry: e, cursor_idx: i });
}
}
let mut results: Vec<(Vec<u8>, MemEntry)> = Vec::new();
let mut last_key: Option<Vec<u8>> = None;
let mut last_entry: Option<MemEntry> = None;
while let Some(item) = heap.pop() {
if let Some((k, e)) = cursors[item.cursor_idx].pop()? {
heap.push(HeapItem { key: k, entry: e, cursor_idx: item.cursor_idx });
}
match &last_key {
Some(lk) if lk == &item.key => {
if let Some(ref le) = last_entry {
if item.entry.lsn > le.lsn {
last_entry = Some(item.entry);
}
}
}
_ => {
if let Some(e) = last_entry.take() {
if e.op != Operation::Delete {
if let Some(lk) = last_key.take() {
results.push((lk, e));
if max_items.is_some_and(|m| results.len() >= m) {
return Ok((results, true));
}
}
}
}
last_key = Some(item.key);
last_entry = Some(item.entry);
}
}
}
if let Some(e) = last_entry {
if e.op != Operation::Delete {
if let Some(lk) = last_key {
results.push((lk, e));
}
}
}
Ok((results, false))
}
pub(crate) fn range_scan_rev_budgeted(
&self,
start: &[u8],
end: &[u8],
max_items: usize,
) -> Result<Vec<(Vec<u8>, MemEntry)>, EdgestoreError> {
let mut per_reader: Vec<Vec<(Vec<u8>, MemEntry)>> = Vec::new();
for reader in &self.readers {
if end <= reader.meta.min_key.as_slice() || start > reader.meta.max_key.as_slice() {
continue;
}
let seg = reader.range_scan(start, end)?;
if !seg.is_empty() {
per_reader.push(seg);
}
}
if per_reader.is_empty() {
return Ok(vec![]);
}
use std::collections::BinaryHeap;
use std::cmp::Ordering;
struct HeapItem {
key: Vec<u8>,
entry: MemEntry,
reader_idx: usize,
elem_idx: usize,
}
impl PartialEq for HeapItem {
fn eq(&self, other: &Self) -> bool {
self.key == other.key
}
}
impl Eq for HeapItem {}
impl Ord for HeapItem {
fn cmp(&self, other: &Self) -> Ordering {
let key_cmp = self.key.cmp(&other.key);
if key_cmp != Ordering::Equal {
return key_cmp;
}
self.entry.lsn.cmp(&other.entry.lsn)
}
}
impl PartialOrd for HeapItem {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
let mut heap = BinaryHeap::new();
for (ri, seg) in per_reader.iter().enumerate() {
if !seg.is_empty() {
let ei = seg.len() - 1;
heap.push(HeapItem {
key: seg[ei].0.clone(),
entry: seg[ei].1.clone(),
reader_idx: ri,
elem_idx: ei,
});
}
}
let mut results: Vec<(Vec<u8>, MemEntry)> = Vec::new();
let mut last_key: Option<Vec<u8>> = None;
let mut last_entry: Option<MemEntry> = None;
while let Some(item) = heap.pop() {
if item.elem_idx > 0 {
let prev = item.elem_idx - 1;
let seg = &per_reader[item.reader_idx];
heap.push(HeapItem {
key: seg[prev].0.clone(),
entry: seg[prev].1.clone(),
reader_idx: item.reader_idx,
elem_idx: prev,
});
}
match &last_key {
Some(lk) if lk == &item.key => {
if let Some(ref le) = last_entry {
if item.entry.lsn > le.lsn {
last_entry = Some(item.entry);
}
}
}
_ => {
if let Some(e) = last_entry.take() {
if e.op != Operation::Delete {
if let Some(lk) = last_key.take() {
results.push((lk, e));
if results.len() >= max_items {
return Ok(results);
}
}
}
}
last_key = Some(item.key);
last_entry = Some(item.entry);
}
}
}
if let Some(e) = last_entry {
if e.op != Operation::Delete {
if let Some(lk) = last_key {
results.push((lk, e));
}
}
}
Ok(results)
}
}
#[cfg(test)]
#[path = "segment_tests.rs"]
mod tests;