mod codec;
mod epoch;
mod error;
mod replay;
use liminal::durability::settle::{append_settled, flush_settled};
use std::sync::Arc;
use liminal::durability::DurableStore;
use liminal_protocol::{
lifecycle::{
ConnectionIncarnationAllocationDecision, ConnectionIncarnationAllocator,
ConnectionIncarnationAllocatorRestore, ConnectionOrdinalExhaustion,
DurableIncarnationReferences, ServerIncarnationStartupDecision,
allocate_connection_incarnation, prepare_server_incarnation_startup,
},
outcome::ConnectionIncarnationExhausted,
wire::ConnectionIncarnation,
};
pub(in crate::server) use super::dispatch::ConnectionFateClass;
use codec::{IncarnationEvent, decode_event, encode_event};
use epoch::{EPOCH_STARTUP_SEQUENCE, EpochSource};
use replay::{
AllocationGeneration, ReplayAccumulator, ReplayedIncarnationState, UnmatchedConnectionFates,
retain_active_allocations,
};
pub(in crate::server) use epoch::AnchorSwap;
pub(in crate::server) use error::{
DurableWriteReach, IncarnationOperationError, IncarnationStreamError,
};
pub(in crate::server) use replay::ConnectionFateIntent;
#[cfg(test)]
pub(in crate::server) use codec::{
encode_allocate_event_fixture, encode_complete_connection_fate_event_fixture,
encode_frozen_v1_startup_event_fixture, encode_open_connection_fate_event_fixture,
encode_startup_event_fixture,
};
const REPLAY_PAGE_SIZE: usize = 256;
#[derive(Debug)]
pub(in crate::server) enum IncarnationStartup {
Started(StartedIncarnationStream),
RecoveryRequired(ConnectionFateRecovery),
Exhausted(ConnectionIncarnationExhausted),
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(in crate::server) enum IncarnationAllocation {
Allocated {
connection_incarnation: ConnectionIncarnation,
skipped_collisions: usize,
},
Exhausted(ConnectionIncarnationExhausted),
}
#[derive(Debug)]
pub(in crate::server) struct IncarnationStream {
store: Arc<dyn DurableStore>,
maximum_references: usize,
#[cfg(test)]
replay_seed: Option<ConnectionIncarnationAllocatorRestore>,
}
impl IncarnationStream {
#[must_use]
pub(in crate::server) const fn new(
store: Arc<dyn DurableStore>,
maximum_references: usize,
) -> Self {
Self {
store,
maximum_references,
#[cfg(test)]
replay_seed: None,
}
}
#[must_use]
#[cfg(test)]
pub(in crate::server) const fn stream_key() -> &'static str {
epoch::GENESIS_STREAM_KEY
}
#[must_use]
#[cfg(test)]
pub(in crate::server) fn epoch_stream_key(server_incarnation: u64) -> String {
epoch::epoch_stream_key(server_incarnation)
}
#[must_use]
#[cfg(test)]
pub(in crate::server) const fn epoch_anchor_key() -> &'static str {
epoch::EPOCH_ANCHOR_KEY
}
#[cfg(test)]
pub(in crate::server) async fn stream_key_of_record(
store: &Arc<dyn DurableStore>,
) -> Result<String, IncarnationStreamError> {
Ok(EpochSource::from_anchor(epoch::read_anchor(store).await?).stream_key())
}
#[cfg(test)]
pub(in crate::server) fn seeded_for_test(
store: Arc<dyn DurableStore>,
maximum_references: usize,
replay_seed: ConnectionIncarnationAllocatorRestore,
) -> Result<Self, IncarnationStreamError> {
let _validated = ConnectionIncarnationAllocator::try_restore(replay_seed)?;
Ok(Self {
store,
maximum_references,
replay_seed: Some(replay_seed),
})
}
pub(in crate::server) async fn startup(
self,
) -> Result<IncarnationStartup, IncarnationStreamError> {
let (source, replayed) = self.replay_of_record().await?;
if !replayed.unmatched.by_sequence.is_empty() {
return Ok(IncarnationStartup::RecoveryRequired(
ConnectionFateRecovery {
store: self.store,
stream_key: source.stream_key(),
source,
maximum_references: self.maximum_references,
allocator: replayed.allocator,
next_sequence: replayed.next_sequence,
unmatched: replayed.unmatched,
},
));
}
rotate_into_successor_epoch(
&self.store,
self.maximum_references,
source,
replayed.allocator,
)
.await
}
async fn replay_of_record(
&self,
) -> Result<(EpochSource, ReplayedIncarnationState), IncarnationStreamError> {
let mut anchor = epoch::read_anchor(&self.store).await?;
loop {
anchor = epoch::roll_anchor_forward(&self.store, anchor).await?;
let source = EpochSource::from_anchor(anchor);
let replayed = self.replay(source).await?;
let replayed_server_incarnation = replayed.allocator.as_restore().server_incarnation;
if let EpochSource::Epoch(named) = source {
if replayed_server_incarnation == named.get() {
return Ok((source, replayed));
}
return Err(IncarnationStreamError::EpochHeaderMismatch {
epoch_server_incarnation: named.get(),
replayed_server_incarnation,
});
}
let Some(successor) = replayed_server_incarnation.checked_add(1) else {
return Ok((source, replayed));
};
if !epoch::epoch_exists(&self.store, successor).await? {
return Ok((source, replayed));
}
epoch::advance_anchor(&self.store, anchor, successor).await?;
anchor = successor;
}
}
async fn replay(
&self,
source: EpochSource,
) -> Result<ReplayedIncarnationState, IncarnationStreamError> {
let started = std::time::Instant::now();
let stream_key = source.stream_key();
tracing::info!(
step = "incarnation-stream recovery",
stream_key = %stream_key,
"incarnation-stream replay started"
);
#[cfg(test)]
let replay_seed = self.replay_seed;
#[cfg(not(test))]
let replay_seed = None;
let (allocator, has_started) = Self::initial_replay_state(replay_seed, source)?;
let mut next_sequence = 0_u64;
let generation = has_started.then(|| {
AllocationGeneration::new(next_sequence, allocator.as_restore().server_incarnation)
});
let mut replay = ReplayAccumulator {
allocator,
generation,
unmatched: UnmatchedConnectionFates::default(),
has_started,
};
loop {
let entries = self
.store
.read_from(&stream_key, next_sequence, REPLAY_PAGE_SIZE)
.await?;
if entries.is_empty() {
break;
}
for entry in entries {
if entry.sequence != next_sequence {
return Err(IncarnationStreamError::EventSequence {
expected: next_sequence,
actual: entry.sequence,
});
}
let event = decode_event(&entry.payload)?;
replay = replay.apply(event, entry.sequence)?;
next_sequence = next_sequence
.checked_add(1)
.ok_or(IncarnationStreamError::StreamSequenceExhausted)?;
}
}
tracing::info!(
step = "incarnation-stream recovery",
rows = next_sequence,
unmatched_opens = replay.unmatched.by_sequence.len(),
elapsed_ms = u64::try_from(started.elapsed().as_millis()).unwrap_or(u64::MAX),
"incarnation-stream replay finished"
);
Ok(ReplayedIncarnationState {
allocator: replay.allocator,
next_sequence,
generation: replay.generation,
unmatched: replay.unmatched,
has_started: replay.has_started,
})
}
pub(in crate::server) async fn resume_after_ambiguous_write(
self,
expected_server_incarnation: u64,
) -> Result<StartedIncarnationStream, IncarnationStreamError> {
let anchor = epoch::read_anchor(&self.store).await?;
if anchor > expected_server_incarnation {
return Err(IncarnationStreamError::ResumeServerIncarnationMoved {
expected: expected_server_incarnation,
actual: anchor,
});
}
if let Some(successor) = expected_server_incarnation.checked_add(1)
&& epoch::epoch_exists(&self.store, successor).await?
{
return Err(IncarnationStreamError::ResumeServerIncarnationMoved {
expected: expected_server_incarnation,
actual: successor,
});
}
let source = EpochSource::from_anchor(expected_server_incarnation);
let replayed = self.replay(source).await?;
if !replayed.has_started {
return Err(IncarnationStreamError::MissingStartup);
}
let header = replayed.allocator.as_restore();
if header.server_incarnation != expected_server_incarnation {
return Err(IncarnationStreamError::ResumeServerIncarnationMoved {
expected: expected_server_incarnation,
actual: header.server_incarnation,
});
}
let generation = replayed
.generation
.ok_or(IncarnationStreamError::MissingStartup)?;
Ok(StartedIncarnationStream {
store: self.store,
stream_key: source.stream_key(),
maximum_references: self.maximum_references,
header,
next_sequence: replayed.next_sequence,
generation,
unmatched: replayed.unmatched,
anchor_swap: None,
})
}
fn initial_replay_state(
replay_seed: Option<ConnectionIncarnationAllocatorRestore>,
source: EpochSource,
) -> Result<(ConnectionIncarnationAllocator, bool), IncarnationStreamError> {
if let Some(seed) = replay_seed {
return Ok((ConnectionIncarnationAllocator::try_restore(seed)?, true));
}
Ok((
ConnectionIncarnationAllocator::try_restore(source.resume_seed())?,
false,
))
}
#[cfg(test)]
pub(in crate::server) async fn resume_started_for_test(
self,
) -> Result<StartedIncarnationStream, IncarnationStreamError> {
let (source, replayed) = self.replay_of_record().await?;
if !replayed.has_started {
return Err(IncarnationStreamError::MissingStartup);
}
if !replayed.unmatched.by_sequence.is_empty() {
return Err(IncarnationStreamError::UnmatchedConnectionFates {
count: replayed.unmatched.by_sequence.len(),
});
}
let header = replayed.allocator.as_restore();
Ok(StartedIncarnationStream {
store: self.store,
stream_key: source.stream_key(),
maximum_references: self.maximum_references,
header,
next_sequence: replayed.next_sequence,
generation: replayed
.generation
.unwrap_or_else(|| AllocationGeneration::new(0, header.server_incarnation)),
unmatched: UnmatchedConnectionFates::default(),
anchor_swap: None,
})
}
#[cfg(test)]
pub(in crate::server) async fn unmatched_intents_for_test(
&self,
) -> Result<Vec<ConnectionFateIntent>, IncarnationStreamError> {
let (_, replayed) = self.replay_of_record().await?;
Ok(replayed.unmatched.by_sequence.into_values().collect())
}
}
async fn rotate_into_successor_epoch(
store: &Arc<dyn DurableStore>,
maximum_references: usize,
source: EpochSource,
allocator: ConnectionIncarnationAllocator,
) -> Result<IncarnationStartup, IncarnationStreamError> {
match prepare_server_incarnation_startup(allocator) {
ServerIncarnationStartupDecision::Fsync(intent) => {
let server_incarnation = intent.server_incarnation();
let stream_key = epoch::epoch_stream_key(server_incarnation);
let payload = encode_event(&IncarnationEvent::Startup)?;
let appending = std::time::Instant::now();
let next_sequence =
append_and_flush(store, &stream_key, EPOCH_STARTUP_SEQUENCE, payload).await?;
tracing::info!(
server_incarnation,
append_ms = u64::try_from(appending.elapsed().as_millis()).unwrap_or(u64::MAX),
"incarnation-stream epoch rotated"
);
let header = intent.complete_after_fsync().as_restore();
Ok(IncarnationStartup::Started(StartedIncarnationStream {
store: Arc::clone(store),
stream_key,
maximum_references,
header,
next_sequence,
generation: AllocationGeneration::new(
EPOCH_STARTUP_SEQUENCE,
header.server_incarnation,
),
unmatched: UnmatchedConnectionFates::default(),
anchor_swap: Some(AnchorSwap::new(
Arc::clone(store),
source.anchor_value(),
server_incarnation,
)),
}))
}
ServerIncarnationStartupDecision::Exhausted(exhausted) => {
Ok(IncarnationStartup::Exhausted(exhausted.outcome()))
}
}
}
#[derive(Debug)]
pub struct ConnectionFateRecovery {
store: Arc<dyn DurableStore>,
stream_key: String,
source: EpochSource,
maximum_references: usize,
allocator: ConnectionIncarnationAllocator,
next_sequence: u64,
unmatched: UnmatchedConnectionFates,
}
impl ConnectionFateRecovery {
#[must_use]
pub fn intents(&self) -> Vec<ConnectionFateIntent> {
self.unmatched.by_sequence.values().cloned().collect()
}
pub async fn complete(&mut self, open_sequence: u64) -> Result<(), IncarnationStreamError> {
if !self.unmatched.by_sequence.contains_key(&open_sequence) {
return Err(IncarnationStreamError::RecoveryCompleteForAbsentOpen { open_sequence });
}
let payload = encode_event(&IncarnationEvent::CompleteConnectionFate {
open_event_sequence: open_sequence,
})?;
let complete_sequence = self.next_sequence;
self.next_sequence =
append_and_flush(&self.store, &self.stream_key, complete_sequence, payload).await?;
self.unmatched.complete(complete_sequence, open_sequence)?;
Ok(())
}
pub async fn finish_startup(self) -> Result<IncarnationStartup, IncarnationStreamError> {
if !self.unmatched.by_sequence.is_empty() {
return Err(IncarnationStreamError::RecoveryIncomplete {
count: self.unmatched.by_sequence.len(),
});
}
rotate_into_successor_epoch(
&self.store,
self.maximum_references,
self.source,
self.allocator,
)
.await
}
}
#[derive(Debug)]
pub(in crate::server) struct StartedIncarnationStream {
store: Arc<dyn DurableStore>,
stream_key: String,
maximum_references: usize,
header: ConnectionIncarnationAllocatorRestore,
next_sequence: u64,
generation: AllocationGeneration,
unmatched: UnmatchedConnectionFates,
anchor_swap: Option<AnchorSwap>,
}
impl StartedIncarnationStream {
#[must_use]
pub(in crate::server) const fn server_incarnation(&self) -> u64 {
self.header.server_incarnation
}
#[must_use]
pub(in crate::server) fn store(&self) -> Arc<dyn DurableStore> {
Arc::clone(&self.store)
}
#[must_use]
pub(in crate::server) const fn maximum_references(&self) -> usize {
self.maximum_references
}
#[must_use]
#[cfg(test)]
pub(super) const fn header(&self) -> ConnectionIncarnationAllocatorRestore {
self.header
}
pub(in crate::server) async fn allocate(
&mut self,
referenced_incarnations: &[ConnectionIncarnation],
) -> Result<IncarnationAllocation, IncarnationOperationError> {
self.generation
.establish_bound(self.next_sequence, self.maximum_references)?;
let references = DurableIncarnationReferences::try_new(
referenced_incarnations,
self.maximum_references,
)?;
let event = IncarnationEvent::Allocate {
declared_reference_bound: self.maximum_references,
referenced_incarnations: referenced_incarnations.to_vec(),
};
let payload = encode_event(&event)?;
let allocator = ConnectionIncarnationAllocator::try_restore(self.header)?;
match allocate_connection_incarnation(allocator, references) {
ConnectionIncarnationAllocationDecision::Allocated(allocation) => {
let connection_incarnation = allocation.connection_incarnation();
let skipped_collisions = allocation.skipped_collisions();
let next_sequence =
append_and_flush(&self.store, &self.stream_key, self.next_sequence, payload)
.await?;
let resulting = allocation.into_resulting();
self.header = resulting.as_restore();
retain_active_allocations(
&mut self.generation,
referenced_incarnations,
Some((connection_incarnation, self.next_sequence)),
);
self.next_sequence = next_sequence;
Ok(IncarnationAllocation::Allocated {
connection_incarnation,
skipped_collisions,
})
}
ConnectionIncarnationAllocationDecision::Exhausted(exhaustion) => {
let outcome = exhaustion.outcome();
let must_append =
matches!(&exhaustion, ConnectionOrdinalExhaustion::MarkExhausted(_));
let next_sequence = if must_append {
append_and_flush(&self.store, &self.stream_key, self.next_sequence, payload)
.await?
} else {
self.next_sequence
};
let resulting = exhaustion.into_resulting();
self.header = resulting.as_restore();
if must_append {
retain_active_allocations(&mut self.generation, referenced_incarnations, None);
}
self.next_sequence = next_sequence;
Ok(IncarnationAllocation::Exhausted(outcome))
}
}
}
pub(in crate::server) async fn open_connection_fate(
&mut self,
connection_incarnation: ConnectionIncarnation,
class: ConnectionFateClass,
declared_conversation_bound: usize,
conversations: &[u64],
) -> Result<ConnectionFateIntent, IncarnationOperationError> {
let event = IncarnationEvent::OpenConnectionFate {
connection_incarnation,
class,
declared_conversation_bound,
conversations: conversations.to_vec(),
};
let payload = encode_event(&event)?;
let open_sequence = self.next_sequence;
let mut staged_unmatched = self.unmatched.clone();
let intent = staged_unmatched.open(
open_sequence,
&self.generation,
connection_incarnation,
class,
declared_conversation_bound,
conversations.to_vec(),
)?;
self.next_sequence =
append_and_flush(&self.store, &self.stream_key, open_sequence, payload).await?;
self.unmatched = staged_unmatched;
Ok(intent)
}
pub(in crate::server) async fn complete_connection_fate(
&mut self,
open_sequence: u64,
) -> Result<(), IncarnationOperationError> {
let payload = encode_event(&IncarnationEvent::CompleteConnectionFate {
open_event_sequence: open_sequence,
})?;
let complete_sequence = self.next_sequence;
let mut staged_unmatched = self.unmatched.clone();
staged_unmatched.complete(complete_sequence, open_sequence)?;
self.next_sequence =
append_and_flush(&self.store, &self.stream_key, complete_sequence, payload).await?;
self.unmatched = staged_unmatched;
Ok(())
}
}
async fn append_and_flush(
store: &Arc<dyn DurableStore>,
stream_key: &str,
expected_sequence: u64,
payload: Vec<u8>,
) -> Result<u64, IncarnationOperationError> {
let next_sequence = expected_sequence.checked_add(1).ok_or_else(|| {
IncarnationOperationError::not_attempted(IncarnationStreamError::StreamSequenceExhausted)
})?;
let assigned = append_settled(store.as_ref(), stream_key, payload, expected_sequence)
.await
.map_err(|error| IncarnationOperationError::ambiguous(error.into()))?;
if assigned != expected_sequence {
return Err(IncarnationOperationError::ambiguous(
IncarnationStreamError::AssignedSequence {
expected: expected_sequence,
actual: assigned,
},
));
}
flush_settled(store.as_ref())
.await
.map_err(|error| IncarnationOperationError::ambiguous(error.into()))?;
Ok(next_sequence)
}