use std::fmt;
use std::io;
use std::ops::Range;
use std::sync::Arc;
use std::sync::Mutex;
use std::sync::MutexGuard;
use std::sync::TryLockError;
use std::sync::atomic::AtomicU8;
use std::sync::atomic::AtomicU64;
use std::sync::atomic::Ordering;
use crate::checksum::crc32c;
use crate::hashing::route_hash;
use crate::io::background::BackgroundIoAttempt;
use crate::io::engine::IoBuffer;
use crate::io::engine::IoEngine;
use crate::io::engine::ReadSlot;
use crate::io::file::DIRECT_IO_ALIGNMENT;
use crate::managed_memory::BufferLease;
use crate::region::appender::WriteCompletion;
use crate::region::appender::submit_write;
use crate::region::index::ReclaimIndexAction;
use crate::region::index::RegionIndex;
use crate::region::index::heat_memory_bytes;
#[cfg(test)]
use crate::region::index::packed::IndexEntry;
use crate::region::index::packed::PackedLocation;
use crate::region::index::storage::IndexPartitionRange;
use crate::region::index::storage::IndexPhysicalStats;
use crate::region::index::storage::IndexStorageError;
use crate::region::index::storage::PartitionedIndexStorage;
use crate::region::index::storage::WARM_IMAGE_WRITE_BATCH_BYTES;
use crate::region::index::storage::canonical_index_partition_ranges;
use crate::region::index::storage::page_format::INDEX_IMAGE_PAGE_SIZE;
use crate::region::manager::RegionManager;
use crate::region::manager::RegionMutationError;
use crate::region::manager::RegionReclaimReceipt;
use crate::region::manager::RegionWriteSpan;
use crate::region::reader::PendingRead;
use crate::region::reader::ReadCandidate;
use crate::region::reader::ReadCompletion;
use crate::region::reader::ReadDesc;
#[cfg(test)]
use crate::region::reader::describe_read;
use crate::region::reader::submit_read;
use crate::region::record::RECORD_ALIGNMENT;
use crate::region::record::RECORD_HEADER_SIZE;
use crate::region::record::RecordHeader;
use crate::region::record::codec::RecordEncodeError;
use crate::region::record::codec::RecordPayload;
use crate::region::record::codec::encode_reinsert_into_hashed;
use crate::region::record::codec::encode_value_into_hashed;
#[cfg(test)]
use crate::region::record::codec::hash_key;
use crate::region::recovery::DataGeometry;
use crate::region::recovery::metadata::PartitionMetadataRecord;
use crate::region::recovery::metadata::RegionMetadata;
use crate::region::recovery::metadata::RegionMetadataError;
use crate::region::recovery::metadata::region_metadata_encoded_len;
use crate::region::recovery::recovery_image_index_len;
use crate::region::staging::AppendStaging;
use crate::region::staging::StageAppend;
use crate::region::staging::StagedRecord;
use crate::region::staging::StagedWrite;
use crate::region::staging::StagingEncodeError;
use crate::region::staging::StagingError;
use crate::snapshot::CacheIndexSnapshot;
use crate::snapshot::RegionSnapshot;
pub mod index;
pub mod manager;
pub mod persistence;
pub mod record;
pub mod recovery;
pub mod staging;
pub mod appender;
pub mod reader;
const REGION_HEALTHY: u8 = 0;
const REGION_MISS_ONLY: u8 = 1;
#[derive(Clone)]
pub struct RegionHealthLatch {
state: Arc<AtomicU8>,
}
impl RegionHealthLatch {
fn healthy() -> Self {
Self {
state: Arc::new(AtomicU8::new(REGION_HEALTHY)),
}
}
pub fn is_healthy(&self) -> bool {
self.state.load(Ordering::Acquire) == REGION_HEALTHY
}
pub fn enter_miss_only(&self) {
if self.transition_to_miss_only() {
log::warn!(
target: "cache2::health",
event = "cache_miss_only",
reason = "internal_failure";
"cache entered miss-only mode"
);
}
}
fn enter_miss_only_with_error(&self, reason: &'static str, error: &impl fmt::Display) {
if self.transition_to_miss_only() {
log::warn!(
target: "cache2::health",
event = "cache_miss_only",
reason,
error:% = error;
"cache entered miss-only mode"
);
}
}
fn transition_to_miss_only(&self) -> bool {
self.state
.compare_exchange(
REGION_HEALTHY,
REGION_MISS_ONLY,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_ok()
}
fn require_healthy(&self) -> io::Result<()> {
self.is_healthy().then_some(()).ok_or_else(|| {
io::Error::new(
io::ErrorKind::InvalidData,
"Region store is miss-only and cannot publish CLEAN",
)
})
}
}
struct RegionManagerLock {
state: Mutex<RegionManager>,
health: RegionHealthLatch,
}
impl RegionManagerLock {
fn new(manager: RegionManager, health: RegionHealthLatch) -> Self {
Self {
state: Mutex::new(manager),
health,
}
}
fn lock(&self) -> io::Result<MutexGuard<'_, RegionManager>> {
self.health.require_healthy()?;
match self.state.lock() {
Ok(guard) if self.health.is_healthy() => Ok(guard),
Ok(_) => Err(io::Error::new(
io::ErrorKind::InvalidData,
"Region store became miss-only while acquiring Region authority",
)),
Err(_) => {
self.health.enter_miss_only();
Err(io::Error::new(
io::ErrorKind::InvalidData,
"Region manager is poisoned",
))
}
}
}
fn try_lock(&self) -> io::Result<Option<MutexGuard<'_, RegionManager>>> {
self.health.require_healthy()?;
match self.state.try_lock() {
Ok(guard) if self.health.is_healthy() => Ok(Some(guard)),
Ok(_) => Err(io::Error::new(
io::ErrorKind::InvalidData,
"Region store became miss-only while acquiring Region authority",
)),
Err(TryLockError::WouldBlock) => Ok(None),
Err(TryLockError::Poisoned(_)) => {
self.health.enter_miss_only();
Err(io::Error::new(
io::ErrorKind::InvalidData,
"Region manager is poisoned",
))
}
}
}
}
pub struct FrozenRegionStore {
regions: Arc<RegionStore>,
metadata: RegionMetadata,
}
pub struct RegionStore {
index: RegionIndex,
geometry: DataGeometry,
manager: RegionManagerLock,
append_gates: Box<[Mutex<()>]>,
region_generations: Box<[AtomicU64]>,
health: RegionHealthLatch,
}
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub struct RegionReclaimStats {
pub records_scanned: u64,
pub records_removed: u64,
pub bytes_read: u64,
pub reinsert_records: u64,
pub reinsert_bytes: u64,
pub reinsert_skipped: u64,
pub reinsert_budget_skipped: u64,
}
pub struct RegionReinsertRecord<'a> {
pub hash: u64,
pub previous_location: PackedLocation,
pub logical_seqno: u64,
pub record_bytes: u32,
payload: RecordPayload<'a>,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum RegionStageValue {
Staged {
seqno: u64,
previous_bytes: usize,
current_bytes: usize,
},
Contended,
NeedsFlush,
NeedsRotation,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum RegionRotation {
Idle,
Pending,
Rotated,
}
pub struct RegionValue {
buffer: BufferLease,
buffer_len: usize,
value_range: Range<usize>,
seqno: u64,
}
unsafe impl Sync for RegionValue {}
impl RegionValue {
pub fn value(&self) -> &[u8] {
&self
.buffer
.prepared(self.buffer_len)
.expect("validated read retains its prepared buffer")[self.value_range.clone()]
}
pub const fn seqno(&self) -> u64 {
self.seqno
}
}
impl RegionStore {
#[cfg(test)]
pub fn lock_manager_for_test(&self) -> MutexGuard<'_, RegionManager> {
self.manager.lock().unwrap()
}
#[cfg(test)]
pub fn lock_append_for_test(&self, shard_id: usize) -> MutexGuard<'_, ()> {
self.append_gates[shard_id].lock().unwrap()
}
pub fn from_recovery(
index: PartitionedIndexStorage,
metadata: RegionMetadata,
) -> io::Result<Self> {
let physical_stats = index.partition_stats().map_err(index_storage_io_error)?;
let slot_count = u64::try_from(index.slot_count()).map_err(|_| {
io::Error::new(io::ErrorKind::InvalidData, "index capacity is too large")
})?;
if metadata.root.index_slots != slot_count
|| metadata.root.partition_count as usize != index.partition_count()
|| !metadata_partition_stats_match(&metadata, &physical_stats)
{
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"index and Region metadata do not describe one authority",
));
}
let data_file_len =
DataGeometry::expected_file_len(metadata.root.region_size, metadata.root.region_count)
.ok_or_else(|| {
io::Error::new(io::ErrorKind::InvalidData, "data geometry overflow")
})?;
let geometry = DataGeometry {
data_file_len,
region_size: metadata.root.region_size,
region_count: metadata.root.region_count,
};
let manager = RegionManager::from_metadata(metadata).map_err(region_metadata_io_error)?;
let mut append_gates = Vec::new();
append_gates
.try_reserve_exact(manager.active_regions().len())
.map_err(|_| {
io::Error::new(
io::ErrorKind::OutOfMemory,
"cannot allocate append shard gates",
)
})?;
append_gates.resize_with(manager.active_regions().len(), || Mutex::new(()));
let mut region_generations = Vec::new();
region_generations
.try_reserve_exact(manager.regions().len())
.map_err(|_| {
io::Error::new(
io::ErrorKind::OutOfMemory,
"cannot allocate Region generations",
)
})?;
for region in manager.regions() {
region_generations.push(AtomicU64::new(region.created_seqno));
}
let health = RegionHealthLatch::healthy();
let index = RegionIndex::from_storage(index).map_err(index_storage_io_error)?;
Ok(Self {
index,
geometry,
manager: RegionManagerLock::new(manager, health.clone()),
append_gates: append_gates.into_boxed_slice(),
region_generations: region_generations.into_boxed_slice(),
health,
})
}
pub fn freeze(self: Arc<Self>) -> io::Result<FrozenRegionStore> {
self.health.require_healthy()?;
let regions = self;
if regions.append_gates.iter().any(Mutex::is_poisoned) {
regions.health.enter_miss_only();
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"append shard gate is poisoned",
));
}
let partitions = index_partition_metadata(regions.index.storage(), ®ions.health)?;
let metadata = regions
.manager
.lock()?
.freeze_metadata(partitions)
.map_err(region_metadata_io_error)?;
regions.health.require_healthy()?;
Ok(FrozenRegionStore { regions, metadata })
}
pub const fn shard_count(&self) -> usize {
self.append_gates.len()
}
pub const fn index_slot_count(&self) -> usize {
self.index.storage().slot_count()
}
pub const fn region_count(&self) -> usize {
self.region_generations.len()
}
pub fn configure_reclaim_workers(&self, workers: usize) -> io::Result<()> {
self.manager
.lock()?
.configure_reclaim_workers(workers)
.map_err(region_metadata_io_error)
}
pub fn append_shard(&self, hash: u64) -> usize {
route_hash(hash, self.append_gates.len())
}
pub fn region_snapshot(&self) -> io::Result<RegionSnapshot> {
self.manager
.lock()?
.region_snapshot()
.map_err(region_metadata_io_error)
}
pub fn index_snapshot(&self) -> io::Result<CacheIndexSnapshot> {
self.index.snapshot().map_err(index_storage_io_error)
}
pub fn set_index_activity_counters_enabled(&self, enabled: bool) {
self.index.set_activity_counters_enabled(enabled);
}
pub fn begin_reclaim(&self) -> io::Result<Option<RegionReclaimReceipt>> {
self.manager
.lock()?
.begin_reclaim()
.map_err(|error| region_mutation_context("reclaim begin", error))
}
pub fn reclaim_needed(&self) -> io::Result<bool> {
Ok(self.manager.lock()?.reclaim_needed())
}
pub fn reclaim_can_reinsert(&self) -> io::Result<bool> {
Ok(self.manager.lock()?.reclaim_can_reinsert())
}
pub fn reclaim_absolute(&self, receipt: RegionReclaimReceipt) -> io::Result<u64> {
self.geometry
.region_offset(receipt.region_id)
.ok_or_else(|| io::Error::new(io::ErrorKind::InvalidData, "reclaim offset overflow"))
}
pub fn scan_reclaim(
&self,
receipt: RegionReclaimReceipt,
bytes: &[u8],
mut accepting_reinserts: bool,
mut try_reinsert: impl FnMut(RegionReinsertRecord<'_>) -> io::Result<bool>,
) -> io::Result<RegionReclaimStats> {
if bytes.len() as u64 != receipt.used_offset {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"reclaim read does not match the sealed Region prefix",
));
}
let mut offset = 0_usize;
let mut stats = RegionReclaimStats {
bytes_read: receipt.used_offset,
..RegionReclaimStats::default()
};
let alignment = u64::from(RECORD_ALIGNMENT);
let raw_budget = (receipt.used_offset / 8).saturating_sub(DIRECT_IO_ALIGNMENT as u64);
let mut reinsert_budget = raw_budget - raw_budget % alignment;
while offset < bytes.len() {
let header_end = offset.checked_add(RECORD_HEADER_SIZE).ok_or_else(|| {
io::Error::new(io::ErrorKind::InvalidData, "reclaim header offset overflow")
})?;
let header = bytes
.get(offset..header_end)
.and_then(RecordHeader::decode)
.ok_or_else(|| {
io::Error::new(
io::ErrorKind::InvalidData,
"reclaim found an invalid record header",
)
})?;
let record_len = usize::try_from(header.record_len).map_err(|_| {
io::Error::new(
io::ErrorKind::InvalidData,
"reclaim record length is too large",
)
})?;
let record_end = offset
.checked_add(record_len)
.filter(|end| *end <= bytes.len())
.ok_or_else(|| {
io::Error::new(
io::ErrorKind::InvalidData,
"reclaim record crosses the sealed prefix",
)
})?;
let payload_end = header_end
.checked_add(usize::from(header.key_len))
.and_then(|end| end.checked_add(header.value_len as usize))
.filter(|end| *end <= record_end)
.ok_or_else(|| {
io::Error::new(
io::ErrorKind::InvalidData,
"reclaim record payload is out of bounds",
)
})?;
if header.region_generation != receipt.created_seqno {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"reclaim record belongs to another Region generation",
));
}
let location = PackedLocation::new(
receipt.region_id,
u32::try_from(offset).map_err(|_| {
io::Error::new(
io::ErrorKind::InvalidData,
"reclaim record offset is too large",
)
})?,
header.record_len,
)
.map_err(|error| io::Error::new(io::ErrorKind::InvalidData, error))?;
let action = self
.index
.prepare_reclaim(header.key_hash, location)
.map_err(index_storage_io_error)?;
match action {
ReclaimIndexAction::Missing => {}
ReclaimIndexAction::Removed => {
stats.records_removed = stats.records_removed.saturating_add(1);
}
ReclaimIndexAction::Reinsert => {
let key_end = header_end + usize::from(header.key_len);
let key = &bytes[header_end..key_end];
let value = &bytes[key_end..payload_end];
let rewrite_bytes = RecordHeader::aligned_len(key.len(), value.len())
.ok_or_else(|| {
io::Error::new(
io::ErrorKind::InvalidData,
"reclaim replacement record is too large",
)
})?;
let within_budget = u64::from(rewrite_bytes) <= reinsert_budget;
let mut reinserted = false;
if (accepting_reinserts || !within_budget)
&& let Some(payload) =
RecordPayload::validate(key, value, header.payload_crc)
{
if within_budget {
reinserted = try_reinsert(RegionReinsertRecord {
hash: header.key_hash,
previous_location: location,
logical_seqno: header.seqno,
record_bytes: rewrite_bytes,
payload,
})?;
accepting_reinserts = reinserted;
} else {
stats.reinsert_budget_skipped =
stats.reinsert_budget_skipped.saturating_add(1);
}
}
if reinserted {
reinsert_budget = reinsert_budget.saturating_sub(u64::from(rewrite_bytes));
stats.reinsert_records = stats.reinsert_records.saturating_add(1);
stats.reinsert_bytes = stats
.reinsert_bytes
.saturating_add(u64::from(rewrite_bytes));
} else {
if self
.index
.remove_if_match(header.key_hash, location)
.map_err(index_storage_io_error)?
{
stats.records_removed = stats.records_removed.saturating_add(1);
}
stats.reinsert_skipped = stats.reinsert_skipped.saturating_add(1);
}
}
}
stats.records_scanned = stats.records_scanned.saturating_add(1);
offset = record_end;
}
if stats.records_scanned != receipt.physical_record_count {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"reclaim record count does not match Region metadata",
));
}
Ok(stats)
}
pub fn complete_reclaim(&self, receipt: RegionReclaimReceipt) -> io::Result<()> {
let generation = self
.region_generations
.get(receipt.region_id as usize)
.ok_or_else(|| {
io::Error::new(
io::ErrorKind::InvalidData,
"reclaim Region id is out of bounds",
)
})?;
generation.store(0, Ordering::Release);
self.manager
.lock()?
.finish_reclaim(receipt)
.map_err(|error| region_mutation_context("reclaim completion", error))?;
Ok(())
}
pub fn enter_miss_only(&self) {
self.health.enter_miss_only();
}
pub fn enter_miss_only_with_error(&self, reason: &'static str, error: &impl fmt::Display) {
self.health.enter_miss_only_with_error(reason, error);
}
pub fn is_healthy(&self) -> bool {
self.health.is_healthy()
}
fn lock_shard_mutation(&self, shard_id: usize) -> io::Result<MutexGuard<'_, ()>> {
let gate = self.append_gate(shard_id)?;
self.lock_shard_gate(gate)
}
fn append_gate(&self, shard_id: usize) -> io::Result<&Mutex<()>> {
self.append_gates.get(shard_id).ok_or_else(|| {
io::Error::new(io::ErrorKind::InvalidInput, "data shard is out of bounds")
})
}
fn lock_shard_gate<'a>(&self, gate: &'a Mutex<()>) -> io::Result<MutexGuard<'a, ()>> {
self.health.require_healthy()?;
gate.lock().map_err(|_| {
self.health.enter_miss_only();
io::Error::new(io::ErrorKind::InvalidData, "append shard gate is poisoned")
})
}
#[cfg(test)]
fn lookup_snapshot(&self, hash: u64) -> Option<IndexEntry> {
if !self.health.is_healthy() {
return None;
}
match self.index.lookup_raw(hash) {
Ok(result) if self.health.is_healthy() => result,
Ok(_) => None,
Err(error) => {
enter_miss_only_for_index_error(&self.health, &error);
None
}
}
}
pub fn begin_point_read(&self, hash: u64) -> Option<ReadCandidate> {
if !self.health.is_healthy() {
return None;
}
let entry = match self.index.lookup_raw(hash) {
Ok(Some(entry)) => entry,
Ok(None) => return None,
Err(IndexStorageError::PageBusy { .. } | IndexStorageError::PartitionBusy { .. }) => {
return None;
}
Err(error) => {
enter_miss_only_for_index_error(&self.health, &error);
return None;
}
};
let generation = self
.region_generations
.get(entry.location.region_id() as usize)?;
let region_generation = generation.load(Ordering::Acquire);
if region_generation == 0 {
return None;
}
Some(ReadCandidate {
entry,
region_generation,
})
}
#[cfg(test)]
fn read_value(
&self,
engine: &IoEngine,
buffer: BufferLease,
hash_seed: u64,
key: &[u8],
) -> io::Result<Option<RegionValue>> {
let hash = hash_key(hash_seed, key);
let Some(candidate) = self.begin_point_read(hash) else {
return Ok(None);
};
let desc = describe_read(self.geometry, hash, candidate, true)?;
let slot = engine.try_reserve_read()?;
self.read_value_from_desc(engine, slot, buffer, desc, key)
}
#[cfg(test)]
fn read_value_from_desc(
&self,
engine: &IoEngine,
slot: ReadSlot,
buffer: BufferLease,
desc: ReadDesc,
key: &[u8],
) -> io::Result<Option<RegionValue>> {
let pending = self.submit_value_read(engine, slot, buffer, desc)?;
let completion = pending.wait(engine);
self.finish_value_read(completion, key)
}
pub fn submit_value_read(
&self,
engine: &IoEngine,
slot: ReadSlot,
buffer: BufferLease,
desc: ReadDesc,
) -> io::Result<PendingRead> {
match submit_read(engine, slot, desc, buffer) {
Ok(pending) => Ok(pending),
Err(error) => {
if !is_read_pressure(error.kind()) {
self.health
.enter_miss_only_with_error("record_read_submit_failed", &error);
}
Err(error)
}
}
}
pub fn finish_value_read(
&self,
completion: ReadCompletion,
key: &[u8],
) -> io::Result<Option<RegionValue>> {
let hash = completion.desc.hash;
let buffer = match completion.result {
Ok(buffer) => buffer,
Err(error) => {
if !is_read_pressure(error.kind()) {
self.health
.enter_miss_only_with_error("record_read_completion_failed", &error);
}
return Err(error);
}
};
let Some(record) = buffer
.prepared(completion.desc.read_len)
.and_then(|bytes| bytes.get(completion.desc.record_range.clone()))
else {
let error = io::Error::new(
io::ErrorKind::InvalidData,
"record completion lost its bounded candidate range",
);
self.health
.enter_miss_only_with_error("record_read_completion_invalid", &error);
return Err(error);
};
let Some(header) = record
.get(..RECORD_HEADER_SIZE)
.and_then(RecordHeader::decode)
else {
return Ok(None);
};
if header.region_generation != completion.desc.region_generation || header.key_hash != hash
{
return Ok(None);
}
let indexed_location = completion.desc.entry.location;
let Ok(exact_location) = PackedLocation::new(
indexed_location.region_id(),
indexed_location.offset(),
header.record_len,
) else {
return Ok(None);
};
if !indexed_location.index_equivalent(exact_location) {
return Ok(None);
}
let Some(record) = usize::try_from(header.record_len)
.ok()
.and_then(|record_len| record.get(..record_len))
else {
return Ok(None);
};
let key_len = usize::from(header.key_len);
let value_len = header.value_len as usize;
let Some(payload_end) = RECORD_HEADER_SIZE
.checked_add(key_len)
.and_then(|end| end.checked_add(value_len))
.filter(|end| *end <= record.len())
else {
return Ok(None);
};
let encoded_key = &record[RECORD_HEADER_SIZE..RECORD_HEADER_SIZE + key_len];
if encoded_key != key {
return Ok(None);
}
if crc32c(&[&record[RECORD_HEADER_SIZE..payload_end]]) != header.payload_crc {
return Ok(None);
}
let value_start = completion.desc.record_range.start + RECORD_HEADER_SIZE + key_len;
let Some(value_end) = value_start.checked_add(value_len) else {
return Ok(None);
};
Ok(Some(RegionValue {
buffer,
buffer_len: completion.desc.read_len,
value_range: value_start..value_end,
seqno: header.seqno,
}))
}
pub fn try_stage_value(
&self,
staging: &AppendStaging,
shard_id: usize,
hash: u64,
record_bytes: u32,
key: &[u8],
value: &[u8],
) -> io::Result<RegionStageValue> {
self.validate_stage(staging, record_bytes)?;
let payload = RecordPayload::new(key, value);
self.try_stage_record(staging, shard_id, hash, record_bytes, &payload, None)
}
pub fn try_stage_reinsert(
&self,
staging: &AppendStaging,
shard_id: usize,
record: RegionReinsertRecord<'_>,
) -> io::Result<RegionStageValue> {
self.validate_stage(staging, record.record_bytes)?;
self.try_stage_record(
staging,
shard_id,
record.hash,
record.record_bytes,
&record.payload,
Some((record.logical_seqno, record.previous_location)),
)
}
fn validate_stage(&self, staging: &AppendStaging, record_bytes: u32) -> io::Result<()> {
self.health.require_healthy()?;
if record_bytes as usize > staging.chunk_bytes() {
return Err(io::Error::new(
io::ErrorKind::InvalidInput,
"value exceeds one Region staging buffer",
));
}
Ok(())
}
fn try_stage_record(
&self,
staging: &AppendStaging,
shard_id: usize,
hash: u64,
record_bytes: u32,
payload: &RecordPayload<'_>,
reinsert: Option<(u64, PackedLocation)>,
) -> io::Result<RegionStageValue> {
let _shard_mutation = match self.append_gate(shard_id)?.try_lock() {
Ok(guard) => guard,
Err(TryLockError::WouldBlock) => return Ok(RegionStageValue::Contended),
Err(TryLockError::Poisoned(_)) => {
self.health.enter_miss_only();
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"append shard gate is poisoned",
));
}
};
let needs_seal = match staging.preflight_append(shard_id, record_bytes) {
Ok(StageAppend::Appended { .. }) => false,
Ok(StageAppend::NeedsSeal) => true,
Err(StagingError::WouldBlock) => {
return Ok(RegionStageValue::Contended);
}
Err(error) => {
self.health.enter_miss_only();
staging.close();
return Err(staging_io_error(error));
}
};
let receipt = {
let Some(mut manager) = self.manager.try_lock()? else {
return Ok(RegionStageValue::Contended);
};
if needs_seal {
let needs_rotation = manager
.request_rotation_for_append(shard_id, record_bytes)
.map_err(|error| {
self.health.enter_miss_only();
region_mutation_io_error(error)
})?;
return Ok(if needs_rotation {
RegionStageValue::NeedsRotation
} else {
RegionStageValue::NeedsFlush
});
}
let receipt = match manager.reserve_append(shard_id, record_bytes) {
Ok(receipt) => receipt,
Err(RegionMutationError::WouldBlock) => {
return Ok(RegionStageValue::NeedsFlush);
}
Err(RegionMutationError::FlushBeforeRotation) => {
return Ok(RegionStageValue::NeedsRotation);
}
Err(RegionMutationError::RegionFull) => {
return Ok(RegionStageValue::NeedsRotation);
}
Err(error) => {
self.health.enter_miss_only();
return Err(region_mutation_io_error(error));
}
};
if let Err(error) = manager.stage_reservation(receipt) {
self.health.enter_miss_only();
staging.close();
return Err(region_mutation_io_error(error));
}
receipt
};
let staged = staging.encode_reserved(receipt, |destination| {
let entry = match reinsert {
Some((logical_seqno, _)) => encode_reinsert_into_hashed(
destination,
receipt,
hash,
record_bytes,
payload,
logical_seqno,
)?,
None => {
encode_value_into_hashed(destination, receipt, hash, record_bytes, payload)?
}
};
Ok::<StagedRecord, RecordEncodeError>(match reinsert {
Some((_, previous_location)) => {
StagedRecord::reinsert(hash, entry, receipt.seqno, previous_location)
}
None => StagedRecord::new(hash, entry, receipt.seqno),
})
});
match staged {
Ok(StageAppend::Appended {
previous_bytes,
current_bytes,
}) => Ok(RegionStageValue::Staged {
seqno: receipt.seqno,
previous_bytes,
current_bytes,
}),
Ok(StageAppend::NeedsSeal) => self.fail_preflighted_stage(
staging,
"staging capacity changed after successful preflight",
),
Err(StagingEncodeError::Encode(error)) => {
self.health.enter_miss_only();
staging.close();
Err(record_encode_io_error(error))
}
Err(StagingEncodeError::Staging(StagingError::WouldBlock)) => {
self.fail_preflighted_stage(staging, "staging became busy after preflight")
}
Err(StagingEncodeError::Staging(error)) => {
self.health.enter_miss_only();
staging.close();
Err(staging_io_error(error))
}
}
}
pub fn try_delete_value(&self, hash: u64) -> io::Result<Option<u64>> {
let seqno = {
let Some(mut manager) = self.manager.try_lock()? else {
return Ok(None);
};
match manager.allocate_seqno() {
Ok(seqno) => seqno,
Err(error) => {
self.health.enter_miss_only();
return Err(region_mutation_io_error(error));
}
}
};
match self.index.try_delete(hash) {
Ok(_) => Ok(Some(seqno)),
Err(IndexStorageError::PageBusy { .. } | IndexStorageError::PartitionBusy { .. }) => {
Ok(None)
}
Err(error) => {
enter_miss_only_for_index_error(&self.health, &error);
Err(index_storage_io_error(error))
}
}
}
fn fail_preflighted_stage(
&self,
staging: &AppendStaging,
message: &'static str,
) -> io::Result<RegionStageValue> {
self.health.enter_miss_only();
staging.close();
Err(io::Error::new(io::ErrorKind::InvalidData, message))
}
pub fn flush_staging_shard(
&self,
staging: &AppendStaging,
engine: &IoEngine,
shard_id: usize,
mut attempt: BackgroundIoAttempt<'_>,
) -> io::Result<Option<RegionWriteSpan>> {
let shard_mutation = self.lock_shard_mutation(shard_id)?;
let (padding, span) = {
let mut manager = self.manager.lock()?;
let padding = match manager.reserve_write_padding(shard_id) {
Ok(padding) => padding,
Err(RegionMutationError::WouldBlock) => return Ok(None),
Err(error) => {
self.health.enter_miss_only();
return Err(region_mutation_io_error(error));
}
};
let span = if padding.is_none() {
Some(manager.seal_write_span(shard_id).map_err(|error| {
self.health.enter_miss_only();
region_mutation_io_error(error)
})?)
} else {
None
};
(padding, span)
};
let span = match span {
Some(span) => span,
None => {
let padding = padding.expect("padding receipt exists when span is unsealed");
if let Err(error) = staging.apply_write_padding(padding) {
self.health.enter_miss_only();
staging.close();
return Err(staging_io_error(error));
}
let mut manager = self.manager.lock()?;
match manager.seal_write_span_with_padding(padding) {
Ok(span) => span,
Err(error) => {
drop(manager);
self.health.enter_miss_only();
staging.close();
return Err(region_mutation_io_error(error));
}
}
}
};
let job = match staging.take_sealed(span) {
Ok(Some(job)) => job,
Ok(None) => {
self.health.enter_miss_only();
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"manager sealed a span with no staging bytes",
));
}
Err(error) => {
self.health.enter_miss_only();
return Err(staging_io_error(error));
}
};
drop(shard_mutation);
let StagedWrite {
span,
buffer,
records,
} = job;
let pending = match submit_write(engine, self.geometry, span, buffer, &mut attempt) {
Ok(pending) => pending,
Err(error) => {
let original = error.error;
self.fail_staged_span(staging, span, Some(error.buffer), records);
return Err(original);
}
};
let completion = pending.wait(engine, &mut attempt);
let WriteCompletion {
span,
result,
buffer,
} = completion;
if let Err(error) = result {
self.fail_staged_span(staging, span, buffer, records);
return Err(error);
}
let Some(buffer) = buffer else {
self.fail_staged_span(staging, span, None, records);
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"span completion lost its owned buffer",
));
};
{
let mut manager = match self.manager.lock() {
Ok(manager) => manager,
Err(error) => {
self.fail_staged_span(staging, span, Some(buffer), records);
return Err(error);
}
};
if let Err(error) = manager.complete_write_span(span) {
self.health.enter_miss_only();
drop(manager);
self.fail_staged_span(staging, span, Some(buffer), records);
return Err(region_mutation_io_error(error));
}
}
if let Err(error) = self.publish_completed_records(records.as_slice()) {
self.fail_staged_span(staging, span, Some(buffer), records);
return Err(error);
}
if let Err(error) = staging.finish_success(span, buffer, records) {
self.health.enter_miss_only();
return Err(staging_io_error(error));
}
attempt.finish();
Ok(Some(span))
}
pub fn rotate_shard(&self, shard_id: usize) -> io::Result<RegionRotation> {
let _shard_mutation = self.lock_shard_mutation(shard_id)?;
let mut manager = self.manager.lock()?;
if !manager
.rotation_requested(shard_id)
.map_err(|error| region_mutation_context("rotation selection", error))?
{
return Ok(RegionRotation::Idle);
}
let receipt = match manager.rotate_shard(shard_id) {
Ok(receipt) => receipt,
Err(RegionMutationError::WouldBlock) => return Ok(RegionRotation::Pending),
Err(error) => {
self.health.enter_miss_only();
return Err(region_mutation_context("rotation", error));
}
};
let Some(generation) = self
.region_generations
.get(receipt.activated_region_id as usize)
else {
self.health.enter_miss_only();
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"rotation activated an untracked Region",
));
};
generation.store(receipt.activated_created_seqno, Ordering::Release);
Ok(RegionRotation::Rotated)
}
fn publish_completed_records(&self, records: &[StagedRecord]) -> io::Result<()> {
for record in records.iter().copied() {
let entry = record.entry();
let published = match record.previous_location() {
Some(previous) => self
.index
.replace_if_match(record.hash(), previous, entry)
.map(|_| ()),
None => self.index.upsert(record.hash(), entry),
};
if let Err(error) = published {
enter_miss_only_for_index_error(&self.health, &error);
return Err(index_storage_io_error(error));
}
}
Ok(())
}
fn fail_staged_span(
&self,
staging: &AppendStaging,
span: RegionWriteSpan,
buffer: Option<IoBuffer>,
records: Vec<StagedRecord>,
) {
self.health.enter_miss_only();
let _ = staging.finish_failure(span, buffer, records);
}
}
pub fn is_read_pressure(kind: io::ErrorKind) -> bool {
matches!(
kind,
io::ErrorKind::OutOfMemory
| io::ErrorKind::WouldBlock
| io::ErrorKind::TimedOut
| io::ErrorKind::Interrupted
| io::ErrorKind::BrokenPipe
)
}
pub fn runtime_fixed_memory_bytes(index_slots: usize, region_count: u32) -> io::Result<usize> {
let slots = u64::try_from(index_slots)
.map_err(|_| io::Error::new(io::ErrorKind::InvalidInput, "index capacity is too large"))?;
let index_bytes = recovery_image_index_len(slots)
.and_then(|bytes| usize::try_from(bytes).ok())
.ok_or_else(|| {
io::Error::new(
io::ErrorKind::InvalidInput,
"index memory does not fit the platform",
)
})?;
let index_page_state_bytes = (index_bytes / INDEX_IMAGE_PAGE_SIZE)
.checked_mul(size_of::<AtomicU8>())
.ok_or_else(|| {
io::Error::new(
io::ErrorKind::InvalidInput,
"index page-state memory does not fit the platform",
)
})?;
let region_count_usize = usize::try_from(region_count)
.map_err(|_| io::Error::new(io::ErrorKind::InvalidInput, "Region count is too large"))?;
let region_bytes = region_count_usize
.checked_mul(256)
.ok_or_else(|| io::Error::new(io::ErrorKind::InvalidInput, "memory size overflow"))?;
let partition_count = u32::try_from(
canonical_index_partition_ranges(index_slots)
.map_err(index_storage_io_error)?
.len(),
)
.map_err(|_| io::Error::new(io::ErrorKind::InvalidInput, "too many index partitions"))?;
let metadata_bytes = region_metadata_encoded_len(region_count, partition_count)
.and_then(|bytes| usize::try_from(bytes).ok())
.ok_or_else(|| io::Error::new(io::ErrorKind::InvalidInput, "metadata size overflow"))?;
let recovery_scratch = metadata_bytes
.checked_mul(2)
.and_then(|bytes| bytes.checked_add(WARM_IMAGE_WRITE_BATCH_BYTES))
.ok_or_else(|| io::Error::new(io::ErrorKind::InvalidInput, "recovery memory overflow"))?;
let heat_bytes = heat_memory_bytes(index_slots).ok_or_else(|| {
io::Error::new(
io::ErrorKind::InvalidInput,
"index heat memory does not fit the platform",
)
})?;
index_bytes
.checked_add(index_page_state_bytes)
.and_then(|bytes| bytes.checked_add(heat_bytes))
.and_then(|bytes| bytes.checked_add(region_bytes))
.and_then(|bytes| bytes.checked_add(recovery_scratch))
.ok_or_else(|| io::Error::new(io::ErrorKind::InvalidInput, "memory size overflow"))
}
fn region_metadata_io_error(error: RegionMetadataError) -> io::Error {
match error {
RegionMetadataError::Allocation => io::Error::new(io::ErrorKind::OutOfMemory, error),
error => io::Error::new(io::ErrorKind::InvalidData, error),
}
}
fn region_mutation_io_error(error: RegionMutationError) -> io::Error {
io::Error::new(
io::ErrorKind::InvalidData,
format!("Region state mutation failed: {error:?}"),
)
}
fn region_mutation_context(context: &'static str, error: RegionMutationError) -> io::Error {
io::Error::new(
io::ErrorKind::InvalidData,
format!("Region {context} failed: {error:?}"),
)
}
fn record_encode_io_error(error: RecordEncodeError) -> io::Error {
io::Error::new(io::ErrorKind::InvalidInput, error)
}
fn staging_io_error(error: StagingError) -> io::Error {
let kind = match error {
StagingError::Closed => io::ErrorKind::BrokenPipe,
StagingError::WouldBlock => io::ErrorKind::WouldBlock,
StagingError::InvalidShard => io::ErrorKind::InvalidInput,
_ => io::ErrorKind::InvalidData,
};
io::Error::new(kind, error)
}
fn index_storage_io_error(error: IndexStorageError) -> io::Error {
match error {
IndexStorageError::Io(error) => error,
error => io::Error::new(io::ErrorKind::InvalidData, error),
}
}
fn guarded_index_result<T>(
health: &RegionHealthLatch,
result: Result<T, IndexStorageError>,
) -> io::Result<T> {
result.map_err(|error| {
enter_miss_only_for_index_error(health, &error);
index_storage_io_error(error)
})
}
fn enter_miss_only_for_index_error(health: &RegionHealthLatch, error: &IndexStorageError) {
let reason = match error {
IndexStorageError::CorruptPage { .. } | IndexStorageError::CorruptSlot { .. } => {
"index_recovery_validation_failed"
}
IndexStorageError::PartitionPoisoned { .. } => "index_partition_poisoned",
IndexStorageError::Io(_) => "index_storage_io_failed",
_ => "index_storage_invalid",
};
health.enter_miss_only_with_error(reason, error);
}
fn empty_partition_metadata(
ranges: &[IndexPartitionRange],
) -> io::Result<Box<[PartitionMetadataRecord]>> {
let mut stats = Vec::new();
stats.try_reserve_exact(ranges.len()).map_err(|_| {
io::Error::new(
io::ErrorKind::OutOfMemory,
"cannot allocate index partition statistics",
)
})?;
stats.resize(ranges.len(), IndexPhysicalStats::default());
partition_metadata_from_stats(ranges, &stats)
}
fn index_partition_metadata(
index: &PartitionedIndexStorage,
health: &RegionHealthLatch,
) -> io::Result<Box<[PartitionMetadataRecord]>> {
let stats = guarded_index_result(health, index.partition_stats())?;
partition_metadata_from_stats(index.partition_ranges(), &stats)
}
fn partition_metadata_from_stats(
ranges: &[IndexPartitionRange],
stats: &[IndexPhysicalStats],
) -> io::Result<Box<[PartitionMetadataRecord]>> {
if ranges.len() != stats.len() {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"index partition ranges and statistics disagree",
));
}
let mut partitions = Vec::new();
partitions.try_reserve_exact(ranges.len()).map_err(|_| {
io::Error::new(
io::ErrorKind::OutOfMemory,
"cannot allocate index partition directory",
)
})?;
for (range, stats) in ranges.iter().zip(stats) {
partitions.push(PartitionMetadataRecord {
partition_id: u32::try_from(range.partition_id).map_err(|_| {
io::Error::new(io::ErrorKind::InvalidInput, "partition id is too large")
})?,
first_index_page: u64::try_from(range.first_page).map_err(|_| {
io::Error::new(
io::ErrorKind::InvalidInput,
"partition page offset is too large",
)
})?,
index_page_count: u64::try_from(range.page_count).map_err(|_| {
io::Error::new(
io::ErrorKind::InvalidInput,
"partition page count is too large",
)
})?,
first_slot: u64::try_from(range.first_slot).map_err(|_| {
io::Error::new(
io::ErrorKind::InvalidInput,
"partition slot offset is too large",
)
})?,
slot_count: u64::try_from(range.slot_count).map_err(|_| {
io::Error::new(
io::ErrorKind::InvalidInput,
"partition slot count is too large",
)
})?,
physical_value_slots: stats.value,
physical_deleted_slots: 0,
});
}
Ok(partitions.into_boxed_slice())
}
fn metadata_partition_stats(metadata: &RegionMetadata) -> io::Result<Box<[IndexPhysicalStats]>> {
let mut stats = Vec::new();
stats
.try_reserve_exact(metadata.partitions.len())
.map_err(|_| {
io::Error::new(
io::ErrorKind::OutOfMemory,
"cannot allocate index partition statistics",
)
})?;
for partition in &metadata.partitions {
if partition.physical_deleted_slots != 0 {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"partition metadata contains unsupported deleted slots",
));
}
stats.push(IndexPhysicalStats {
value: partition.physical_value_slots,
});
}
Ok(stats.into_boxed_slice())
}
fn metadata_partition_stats_match(metadata: &RegionMetadata, stats: &[IndexPhysicalStats]) -> bool {
metadata.partitions.len() == stats.len()
&& metadata
.partitions
.iter()
.zip(stats)
.all(|(metadata, actual)| {
metadata.physical_value_slots == actual.value
&& metadata.physical_deleted_slots == 0
})
}
#[cfg(test)]
mod tests {
use super::*;
use crate::region::index::storage::page_format::INDEX_IMAGE_SLOTS_PER_PAGE;
#[test]
fn index_page_validation_state_is_fixed_memory_accounted() {
let one_page = runtime_fixed_memory_bytes(INDEX_IMAGE_SLOTS_PER_PAGE, 2).unwrap();
let two_pages = runtime_fixed_memory_bytes(INDEX_IMAGE_SLOTS_PER_PAGE + 1, 2).unwrap();
assert_eq!(
two_pages - one_page,
INDEX_IMAGE_PAGE_SIZE + size_of::<AtomicU8>()
);
}
}