Skip to main content

stateknot_runtime/
fair_scheduler.rs

1// Copyright 2026 StateKnot contributors
2// SPDX-License-Identifier: Apache-2.0
3
4//! Replica-safe deterministic weighted fairness above tenant-isolated workers.
5
6use std::{sync::Arc, time::Duration};
7
8use serde::Serialize;
9use stateknot_core::{
10    BoxFuture, CancellationSignal, Digest, SchedulerReservationId, SchedulerShardId, TenantId,
11};
12use stateknot_store_postgres::{
13    PostgresStore, SchedulerFairnessPolicyRegistration, SchedulerFairnessReservation, StoreError,
14};
15use thiserror::Error;
16
17use crate::{
18    DurableGraphDriverOptions, DurableGraphLifecycleOptions, DurableTenantScheduler,
19    DurableTenantSchedulerBuildError, DurableTenantSchedulerOptions, ExecutableGraphRegistry,
20    GraphLifecycleEvidenceProvider, TenantSchedulerError, TenantSchedulerTick,
21};
22
23const ALGORITHM: &str = "smooth_weighted_round_robin_v1";
24const MAX_RESERVATION_RETRY_DELAY: Duration = Duration::from_secs(1);
25
26/// One tenant's positive service weight inside a fairness shard.
27#[derive(Clone, Debug, Eq, PartialEq)]
28pub struct TenantFairnessWeight {
29    tenant_id: TenantId,
30    weight: u16,
31}
32
33impl TenantFairnessWeight {
34    /// Largest individual weight. The aggregate cycle has a separate bound.
35    pub const MAX_WEIGHT: u16 = 1024;
36
37    /// Constructs one positive bounded tenant weight.
38    ///
39    /// # Errors
40    ///
41    /// Rejects zero and values above [`Self::MAX_WEIGHT`].
42    pub fn new(tenant_id: TenantId, weight: u16) -> Result<Self, TenantFairnessWeightError> {
43        if weight == 0 || weight > Self::MAX_WEIGHT {
44            return Err(TenantFairnessWeightError::InvalidWeight);
45        }
46        Ok(Self { tenant_id, weight })
47    }
48
49    /// Returns the exact tenant queue boundary.
50    #[must_use]
51    pub const fn tenant_id(&self) -> &TenantId {
52        &self.tenant_id
53    }
54
55    /// Returns this tenant's positive cycle weight.
56    #[must_use]
57    pub const fn weight(&self) -> u16 {
58        self.weight
59    }
60}
61
62/// Invalid individual tenant fairness weight.
63#[derive(Clone, Copy, Debug, Eq, Error, PartialEq)]
64#[non_exhaustive]
65pub enum TenantFairnessWeightError {
66    /// Weight was zero or exceeded the hard per-tenant bound.
67    #[error("tenant fairness weight is invalid")]
68    InvalidWeight,
69}
70
71/// Exact reservation-count starvation bound for one continuously eligible tenant.
72#[derive(Clone, Copy, Debug, Eq, PartialEq)]
73pub struct TenantStarvationBound {
74    maximum_reservations_until_selection: u16,
75}
76
77impl TenantStarvationBound {
78    /// Returns the maximum global slot reservations between selections.
79    ///
80    /// This is a scheduling-order bound, not a wall-clock latency promise. A
81    /// deployment must still keep worker capacity available and bound each
82    /// tenant scan/claim operation to translate it into elapsed time.
83    #[must_use]
84    pub const fn maximum_reservations_until_selection(self) -> u16 {
85        self.maximum_reservations_until_selection
86    }
87}
88
89/// Immutable deterministic weighted schedule shared by every shard replica.
90///
91/// Construction sorts tenants by exact identifier, executes one complete
92/// smooth weighted-round-robin cycle, verifies exact weight counts, and derives
93/// each tenant's largest circular slot gap from the resulting cycle. The
94/// canonical policy bytes include the algorithm version and ordered weights;
95/// `PostgreSQL` permanently binds those bytes to the shard identity.
96#[derive(Clone, Debug)]
97pub struct WeightedFairnessPolicy {
98    shard_id: SchedulerShardId,
99    tenants: Box<[TenantFairnessWeight]>,
100    cycle: Box<[usize]>,
101    starvation_bounds: Box<[TenantStarvationBound]>,
102    canonical_bytes: Box<[u8]>,
103    registration: SchedulerFairnessPolicyRegistration,
104}
105
106impl WeightedFairnessPolicy {
107    /// Maximum tenant queues in one shard.
108    pub const MAX_TENANTS: usize = 1024;
109    /// Maximum weighted slots in one deterministic cycle.
110    pub const MAX_CYCLE_LENGTH: u16 = SchedulerFairnessPolicyRegistration::MAX_CYCLE_LENGTH;
111
112    /// Compiles an immutable replica-independent weighted schedule.
113    ///
114    /// # Errors
115    ///
116    /// Rejects empty/oversized tenant sets, duplicate tenant IDs, aggregate
117    /// weight overflow, canonical encoding failure, or invalid store binding.
118    pub fn new<I>(
119        shard_id: SchedulerShardId,
120        tenants: I,
121    ) -> Result<Self, WeightedFairnessPolicyError>
122    where
123        I: IntoIterator<Item = TenantFairnessWeight>,
124    {
125        let mut tenants = tenants.into_iter().collect::<Vec<_>>();
126        if tenants.is_empty() {
127            return Err(WeightedFairnessPolicyError::Empty);
128        }
129        if tenants.len() > Self::MAX_TENANTS {
130            return Err(WeightedFairnessPolicyError::TooManyTenants);
131        }
132        tenants.sort_by(|left, right| left.tenant_id.cmp(&right.tenant_id));
133        if tenants
134            .windows(2)
135            .any(|pair| pair[0].tenant_id == pair[1].tenant_id)
136        {
137            return Err(WeightedFairnessPolicyError::DuplicateTenant);
138        }
139
140        let cycle_length = tenants.iter().try_fold(0_u16, |total, tenant| {
141            total
142                .checked_add(tenant.weight)
143                .filter(|value| *value <= Self::MAX_CYCLE_LENGTH)
144                .ok_or(WeightedFairnessPolicyError::CycleTooLarge)
145        })?;
146        let cycle = compile_smooth_cycle(&tenants, cycle_length);
147        verify_cycle_counts(&tenants, &cycle)?;
148        let starvation_bounds = derive_starvation_bounds(tenants.len(), &cycle)?;
149        let wire = FairnessPolicyWire {
150            algorithm: ALGORITHM,
151            tenants: tenants
152                .iter()
153                .map(|tenant| FairnessTenantWire {
154                    tenant_id: tenant.tenant_id.as_str(),
155                    weight: tenant.weight,
156                })
157                .collect(),
158        };
159        let canonical_bytes = serde_json_canonicalizer::to_vec(&wire)
160            .map_err(|_| WeightedFairnessPolicyError::CanonicalEncoding)?;
161        let registration = SchedulerFairnessPolicyRegistration::new(
162            shard_id.clone(),
163            canonical_bytes.clone(),
164            cycle_length,
165        )
166        .map_err(|_| WeightedFairnessPolicyError::StoreBinding)?;
167        Ok(Self {
168            shard_id,
169            tenants: tenants.into_boxed_slice(),
170            cycle: cycle.into_boxed_slice(),
171            starvation_bounds: starvation_bounds.into_boxed_slice(),
172            canonical_bytes: canonical_bytes.into_boxed_slice(),
173            registration,
174        })
175    }
176
177    /// Returns the immutable distributed shard identity.
178    #[must_use]
179    pub const fn shard_id(&self) -> &SchedulerShardId {
180        &self.shard_id
181    }
182
183    /// Returns the domain-separated durable policy checksum.
184    #[must_use]
185    pub const fn digest(&self) -> Digest {
186        self.registration.policy_digest()
187    }
188
189    /// Returns the exact number of weighted slots per complete cycle.
190    #[must_use]
191    pub fn cycle_length(&self) -> u16 {
192        u16::try_from(self.cycle.len()).expect("policy construction bounds cycle length")
193    }
194
195    /// Returns the canonical exact tenant/weight snapshot.
196    #[must_use]
197    pub const fn tenants(&self) -> &[TenantFairnessWeight] {
198        &self.tenants
199    }
200
201    /// Returns the canonical policy bytes registered durably.
202    #[must_use]
203    pub const fn canonical_bytes(&self) -> &[u8] {
204        &self.canonical_bytes
205    }
206
207    /// Returns the exact continuously-eligible selection bound for a tenant.
208    #[must_use]
209    pub fn starvation_bound(&self, tenant_id: &TenantId) -> Option<TenantStarvationBound> {
210        self.tenants
211            .binary_search_by(|entry| entry.tenant_id.cmp(tenant_id))
212            .ok()
213            .map(|index| self.starvation_bounds[index])
214    }
215
216    /// Resolves one reserved cycle slot to its tenant queue.
217    #[must_use]
218    pub fn tenant_for_slot(&self, slot: u16) -> Option<&TenantId> {
219        self.cycle
220            .get(usize::from(slot))
221            .map(|index| &self.tenants[*index].tenant_id)
222    }
223
224    fn registration(&self) -> SchedulerFairnessPolicyRegistration {
225        self.registration.clone()
226    }
227}
228
229#[derive(Serialize)]
230struct FairnessPolicyWire<'a> {
231    algorithm: &'static str,
232    tenants: Vec<FairnessTenantWire<'a>>,
233}
234
235#[derive(Serialize)]
236struct FairnessTenantWire<'a> {
237    tenant_id: &'a str,
238    weight: u16,
239}
240
241/// Invalid immutable weighted fairness policy.
242#[derive(Clone, Copy, Debug, Eq, Error, PartialEq)]
243#[non_exhaustive]
244pub enum WeightedFairnessPolicyError {
245    /// No tenant queues were configured.
246    #[error("weighted fairness policy must contain at least one tenant")]
247    Empty,
248    /// The hard tenant count was exceeded.
249    #[error("weighted fairness policy contains too many tenants")]
250    TooManyTenants,
251    /// The same tenant boundary appeared more than once.
252    #[error("weighted fairness policy contains a duplicate tenant")]
253    DuplicateTenant,
254    /// Aggregate weights exceeded the bounded cycle.
255    #[error("weighted fairness policy cycle is too large")]
256    CycleTooLarge,
257    /// The compiled cycle did not preserve exact configured shares.
258    #[error("weighted fairness cycle failed internal count verification")]
259    InvalidCompiledCycle,
260    /// The deterministic policy could not be encoded canonically.
261    #[error("weighted fairness policy canonical encoding failed")]
262    CanonicalEncoding,
263    /// The compiled policy could not satisfy the durability-provider contract.
264    #[error("weighted fairness policy store binding failed")]
265    StoreBinding,
266}
267
268fn compile_smooth_cycle(tenants: &[TenantFairnessWeight], cycle_length: u16) -> Vec<usize> {
269    let total = i64::from(cycle_length);
270    let mut current = vec![0_i64; tenants.len()];
271    let mut cycle = Vec::with_capacity(usize::from(cycle_length));
272    for _ in 0..cycle_length {
273        for (score, tenant) in current.iter_mut().zip(tenants) {
274            *score += i64::from(tenant.weight);
275        }
276        let selected = current
277            .iter()
278            .enumerate()
279            .max_by(|(left_index, left), (right_index, right)| {
280                left.cmp(right).then_with(|| right_index.cmp(left_index))
281            })
282            .map(|(index, _)| index)
283            .expect("nonempty policy has one smooth weighted candidate");
284        current[selected] -= total;
285        cycle.push(selected);
286    }
287    cycle
288}
289
290fn verify_cycle_counts(
291    tenants: &[TenantFairnessWeight],
292    cycle: &[usize],
293) -> Result<(), WeightedFairnessPolicyError> {
294    let mut counts = vec![0_u16; tenants.len()];
295    for index in cycle {
296        let Some(count) = counts.get_mut(*index) else {
297            return Err(WeightedFairnessPolicyError::InvalidCompiledCycle);
298        };
299        *count = count
300            .checked_add(1)
301            .ok_or(WeightedFairnessPolicyError::InvalidCompiledCycle)?;
302    }
303    if counts
304        .iter()
305        .zip(tenants)
306        .any(|(actual, tenant)| *actual != tenant.weight)
307    {
308        return Err(WeightedFairnessPolicyError::InvalidCompiledCycle);
309    }
310    Ok(())
311}
312
313fn derive_starvation_bounds(
314    tenant_count: usize,
315    cycle: &[usize],
316) -> Result<Vec<TenantStarvationBound>, WeightedFairnessPolicyError> {
317    let cycle_length = cycle.len();
318    let mut positions = vec![Vec::new(); tenant_count];
319    for (position, index) in cycle.iter().copied().enumerate() {
320        positions
321            .get_mut(index)
322            .ok_or(WeightedFairnessPolicyError::InvalidCompiledCycle)?
323            .push(position);
324    }
325    positions
326        .into_iter()
327        .map(|tenant_positions| {
328            if tenant_positions.is_empty() {
329                return Err(WeightedFairnessPolicyError::InvalidCompiledCycle);
330            }
331            let maximum = tenant_positions
332                .iter()
333                .copied()
334                .zip(
335                    tenant_positions
336                        .iter()
337                        .copied()
338                        .skip(1)
339                        .chain(tenant_positions.first().map(|first| first + cycle_length)),
340                )
341                .map(|(current, next)| next - current)
342                .max()
343                .ok_or(WeightedFairnessPolicyError::InvalidCompiledCycle)?;
344            Ok(TenantStarvationBound {
345                maximum_reservations_until_selection: u16::try_from(maximum)
346                    .map_err(|_| WeightedFairnessPolicyError::InvalidCompiledCycle)?,
347            })
348        })
349        .collect()
350}
351
352/// Retry policy for one durable global slot reservation.
353#[derive(Clone, Copy, Debug, Eq, PartialEq)]
354pub struct DurableFairSchedulerOptions {
355    maximum_reservation_attempts: u8,
356    reservation_retry_initial_delay: Duration,
357}
358
359impl DurableFairSchedulerOptions {
360    /// Absolute number of identical reservation attempts.
361    pub const HARD_MAXIMUM_RESERVATION_ATTEMPTS: u8 = 10;
362
363    /// Constructs a bounded lost-acknowledgement retry policy.
364    ///
365    /// # Errors
366    ///
367    /// Rejects zero/excessive attempts or a zero/greater-than-one-second delay.
368    pub fn new(
369        maximum_reservation_attempts: u8,
370        reservation_retry_initial_delay: Duration,
371    ) -> Result<Self, DurableFairSchedulerOptionsError> {
372        if maximum_reservation_attempts == 0
373            || maximum_reservation_attempts > Self::HARD_MAXIMUM_RESERVATION_ATTEMPTS
374        {
375            return Err(DurableFairSchedulerOptionsError::InvalidReservationAttempts);
376        }
377        if reservation_retry_initial_delay.is_zero()
378            || reservation_retry_initial_delay > MAX_RESERVATION_RETRY_DELAY
379        {
380            return Err(DurableFairSchedulerOptionsError::InvalidReservationRetryDelay);
381        }
382        Ok(Self {
383            maximum_reservation_attempts,
384            reservation_retry_initial_delay,
385        })
386    }
387
388    /// Returns the maximum identical transaction attempts.
389    #[must_use]
390    pub const fn maximum_reservation_attempts(self) -> u8 {
391        self.maximum_reservation_attempts
392    }
393
394    /// Returns the first exponential retry delay.
395    #[must_use]
396    pub const fn reservation_retry_initial_delay(self) -> Duration {
397        self.reservation_retry_initial_delay
398    }
399}
400
401impl Default for DurableFairSchedulerOptions {
402    fn default() -> Self {
403        Self {
404            maximum_reservation_attempts: 3,
405            reservation_retry_initial_delay: Duration::from_millis(25),
406        }
407    }
408}
409
410/// Invalid distributed fairness retry policy.
411#[derive(Clone, Copy, Debug, Eq, Error, PartialEq)]
412#[non_exhaustive]
413pub enum DurableFairSchedulerOptionsError {
414    /// Reservation attempts were zero or above the hard ceiling.
415    #[error("fair scheduler reservation attempt count is invalid")]
416    InvalidReservationAttempts,
417    /// Initial retry delay was zero or above one second.
418    #[error("fair scheduler reservation retry delay is invalid")]
419    InvalidReservationRetryDelay,
420}
421
422/// Complete result of one globally fair scheduler tick.
423#[derive(Debug)]
424pub struct FairSchedulerTick {
425    reservation: SchedulerFairnessReservation,
426    tenant_id: TenantId,
427    starvation_bound: TenantStarvationBound,
428    reservation_retries: u8,
429    tenant_tick: TenantSchedulerTick,
430}
431
432impl FairSchedulerTick {
433    /// Returns the globally ordered durable slot reservation.
434    #[must_use]
435    pub const fn reservation(&self) -> &SchedulerFairnessReservation {
436        &self.reservation
437    }
438
439    /// Returns the selected tenant queue.
440    #[must_use]
441    pub const fn tenant_id(&self) -> &TenantId {
442        &self.tenant_id
443    }
444
445    /// Returns the configured continuously-eligible scheduling bound.
446    #[must_use]
447    pub const fn starvation_bound(&self) -> TenantStarvationBound {
448        self.starvation_bound
449    }
450
451    /// Returns transient database retries that reused the reservation ID.
452    #[must_use]
453    pub const fn reservation_retries(&self) -> u8 {
454        self.reservation_retries
455    }
456
457    /// Returns the selected tenant worker's bounded outcome.
458    #[must_use]
459    pub const fn tenant_tick(&self) -> &TenantSchedulerTick {
460        &self.tenant_tick
461    }
462
463    /// Consumes this value into durable selection and tenant execution parts.
464    #[must_use]
465    pub fn into_parts(
466        self,
467    ) -> (
468        SchedulerFairnessReservation,
469        TenantId,
470        TenantStarvationBound,
471        u8,
472        TenantSchedulerTick,
473    ) {
474        (
475            self.reservation,
476            self.tenant_id,
477            self.starvation_bound,
478            self.reservation_retries,
479            self.tenant_tick,
480        )
481    }
482}
483
484/// Distributed weighted-fair scheduler layered over tenant-isolated workers.
485///
486/// Every replica reserves from the same `PostgreSQL` cursor before inspecting a
487/// tenant queue. Therefore aggregate selection order, exact per-cycle shares,
488/// and reservation-count starvation bounds survive process restarts and
489/// horizontal scaling. Tenant queue scans and claims remain strictly scoped to
490/// the selected tenant.
491#[derive(Clone)]
492pub struct DurableFairScheduler {
493    store: PostgresStore,
494    tenant_scheduler: DurableTenantScheduler,
495    policy: Arc<WeightedFairnessPolicy>,
496    options: DurableFairSchedulerOptions,
497}
498
499impl DurableFairScheduler {
500    /// Returns shared node-future completion accounting for this scheduler and clones.
501    pub fn execution_activity(&self) -> crate::GraphExecutionActivity {
502        self.tenant_scheduler.execution_activity()
503    }
504
505    /// Verifies the persisted immutable policy without reserving a slot.
506    pub async fn check_readiness(&self) -> Result<(), FairSchedulerError> {
507        let stored = self
508            .store
509            .load_scheduler_fairness_policy(self.policy.shard_id())
510            .await
511            .map_err(|source| FairSchedulerError::Store { source })?;
512        if stored.registration() == &self.policy.registration() {
513            Ok(())
514        } else {
515            Err(FairSchedulerError::PolicyProjectionMismatch)
516        }
517    }
518
519    /// Builds the tenant worker and registers the immutable global policy.
520    ///
521    /// # Errors
522    ///
523    /// Returns a local tenant-scheduler binding failure, immutable policy
524    /// conflict, corruption, or database error. No run work is claimed before
525    /// this constructor completes.
526    #[allow(clippy::too_many_arguments)]
527    pub async fn register(
528        store: PostgresStore,
529        registry: ExecutableGraphRegistry,
530        evidence: Arc<dyn GraphLifecycleEvidenceProvider>,
531        driver_options: DurableGraphDriverOptions,
532        lifecycle_options: DurableGraphLifecycleOptions,
533        tenant_options: DurableTenantSchedulerOptions,
534        policy: WeightedFairnessPolicy,
535        options: DurableFairSchedulerOptions,
536    ) -> Result<Self, DurableFairSchedulerBuildError> {
537        let tenant_scheduler = DurableTenantScheduler::new(
538            store.clone(),
539            registry,
540            evidence,
541            driver_options,
542            lifecycle_options,
543            tenant_options,
544        )?;
545        let registration = policy.registration();
546        let outcome = store
547            .register_scheduler_fairness_policy(registration.clone())
548            .await?;
549        if outcome.policy().registration() != &registration {
550            return Err(DurableFairSchedulerBuildError::PolicyProjectionMismatch);
551        }
552        Ok(Self {
553            store,
554            tenant_scheduler,
555            policy: Arc::new(policy),
556            options,
557        })
558    }
559
560    /// Returns the immutable weighted policy snapshot.
561    #[must_use]
562    pub fn policy(&self) -> &WeightedFairnessPolicy {
563        &self.policy
564    }
565
566    /// Returns the bounded durable reservation retry policy.
567    #[must_use]
568    pub const fn options(&self) -> DurableFairSchedulerOptions {
569        self.options
570    }
571
572    /// Reserves one global slot, selects its tenant, and executes one tenant tick.
573    ///
574    /// A stable reservation ID is allocated once and retained across transient
575    /// database errors. Cancellation observed before a durable reservation
576    /// returns an error-free cancelled tenant tick only after selection; callers
577    /// that need to stop before any new selection should cease calling `tick`.
578    pub fn tick(
579        &self,
580        shutdown: CancellationSignal,
581    ) -> BoxFuture<'_, Result<FairSchedulerTick, FairSchedulerError>> {
582        Box::pin(self.tick_inner(shutdown))
583    }
584
585    async fn tick_inner(
586        &self,
587        shutdown: CancellationSignal,
588    ) -> Result<FairSchedulerTick, FairSchedulerError> {
589        let reservation_id = SchedulerReservationId::generate();
590        let mut attempt = 1_u8;
591        let (reservation, reservation_retries) = loop {
592            match self
593                .store
594                .reserve_scheduler_fairness_slot(
595                    self.policy.shard_id(),
596                    self.policy.digest(),
597                    reservation_id,
598                )
599                .await
600            {
601                Ok(reservation) => break (reservation, attempt - 1),
602                Err(error)
603                    if attempt < self.options.maximum_reservation_attempts()
604                        && error.is_retryable() =>
605                {
606                    let delay = exponential_backoff(
607                        self.options.reservation_retry_initial_delay(),
608                        attempt,
609                    );
610                    tokio::time::sleep(delay).await;
611                    attempt = attempt.saturating_add(1);
612                }
613                Err(source) => return Err(FairSchedulerError::Store { source }),
614            }
615        };
616        let tenant_id = self
617            .policy
618            .tenant_for_slot(reservation.slot())
619            .cloned()
620            .ok_or(FairSchedulerError::PolicyProjectionMismatch)?;
621        let starvation_bound = self
622            .policy
623            .starvation_bound(&tenant_id)
624            .ok_or(FairSchedulerError::PolicyProjectionMismatch)?;
625        let tenant_tick = self
626            .tenant_scheduler
627            .tick(tenant_id.clone(), shutdown)
628            .await
629            .map_err(|source| FairSchedulerError::Tenant { source })?;
630        Ok(FairSchedulerTick {
631            reservation,
632            tenant_id,
633            starvation_bound,
634            reservation_retries,
635            tenant_tick,
636        })
637    }
638}
639
640/// Startup failure for a distributed fair scheduler.
641#[derive(Debug, Error)]
642#[non_exhaustive]
643pub enum DurableFairSchedulerBuildError {
644    /// Tenant worker/agent loop construction failed.
645    #[error("fair scheduler tenant worker binding failed: {source}")]
646    Tenant {
647        /// Exact local binding failure.
648        #[from]
649        source: DurableTenantSchedulerBuildError,
650    },
651    /// Durable policy registration failed.
652    #[error("fair scheduler policy registration failed: {source}")]
653    Store {
654        /// Payload-redacted provider failure.
655        #[from]
656        source: StoreError,
657    },
658    /// Stored policy projection differed from the local immutable snapshot.
659    #[error("fair scheduler durable policy projection does not match local policy")]
660    PolicyProjectionMismatch,
661}
662
663/// Failure after a fair scheduler is fully registered.
664#[derive(Debug, Error)]
665#[non_exhaustive]
666pub enum FairSchedulerError {
667    /// Durable slot reservation failed.
668    #[error("fair scheduler slot reservation failed: {source}")]
669    Store {
670        /// Payload-redacted provider failure.
671        #[source]
672        source: StoreError,
673    },
674    /// The tenant-scoped scheduler failed before a closed tick outcome.
675    #[error("selected tenant scheduler failed: {source}")]
676    Tenant {
677        /// Exact tenant scheduler failure.
678        #[source]
679        source: TenantSchedulerError,
680    },
681    /// Durable slot coordinates escaped the registered immutable policy.
682    #[error("fair scheduler durable slot does not match the registered policy")]
683    PolicyProjectionMismatch,
684}
685
686fn exponential_backoff(initial: Duration, attempt: u8) -> Duration {
687    let multiplier = 1_u32
688        .checked_shl(u32::from(attempt.saturating_sub(1)))
689        .unwrap_or(u32::MAX);
690    initial
691        .checked_mul(multiplier)
692        .unwrap_or(MAX_RESERVATION_RETRY_DELAY)
693        .min(MAX_RESERVATION_RETRY_DELAY)
694}
695
696#[cfg(test)]
697mod tests {
698    use std::collections::BTreeMap;
699
700    use proptest::prelude::*;
701
702    use super::*;
703
704    fn tenant(value: &str) -> TenantId {
705        TenantId::try_from(value).unwrap()
706    }
707
708    fn shard(value: &str) -> SchedulerShardId {
709        SchedulerShardId::try_from(value).unwrap()
710    }
711
712    fn weight(value: &str, weight: u16) -> TenantFairnessWeight {
713        TenantFairnessWeight::new(tenant(value), weight).unwrap()
714    }
715
716    #[test]
717    fn policy_is_order_independent_and_preserves_exact_weight_counts() {
718        let left = WeightedFairnessPolicy::new(
719            shard("prod:v1"),
720            [
721                weight("tenant-c", 1),
722                weight("tenant-a", 5),
723                weight("tenant-b", 2),
724            ],
725        )
726        .unwrap();
727        let right = WeightedFairnessPolicy::new(
728            shard("prod:v1"),
729            [
730                weight("tenant-b", 2),
731                weight("tenant-c", 1),
732                weight("tenant-a", 5),
733            ],
734        )
735        .unwrap();
736        assert_eq!(left.digest(), right.digest());
737        assert_eq!(left.canonical_bytes(), right.canonical_bytes());
738        assert_eq!(left.cycle, right.cycle);
739
740        let counts = left
741            .cycle
742            .iter()
743            .fold(BTreeMap::new(), |mut counts, index| {
744                *counts
745                    .entry(left.tenants[*index].tenant_id.as_str())
746                    .or_insert(0_u16) += 1;
747                counts
748            });
749        assert_eq!(counts["tenant-a"], 5);
750        assert_eq!(counts["tenant-b"], 2);
751        assert_eq!(counts["tenant-c"], 1);
752    }
753
754    #[test]
755    fn every_reported_starvation_bound_matches_the_circular_schedule() {
756        let policy = WeightedFairnessPolicy::new(
757            shard("bounds:v1"),
758            [
759                weight("a", 20),
760                weight("b", 8),
761                weight("c", 8),
762                weight("d", 8),
763            ],
764        )
765        .unwrap();
766        for tenant in policy.tenants() {
767            let bound = policy.starvation_bound(tenant.tenant_id()).unwrap();
768            let mut last = None;
769            let mut observed = 0_usize;
770            for offset in 0..(policy.cycle.len() * 2) {
771                let slot = offset % policy.cycle.len();
772                if policy.tenant_for_slot(u16::try_from(slot).unwrap()) == Some(tenant.tenant_id())
773                {
774                    if let Some(previous) = last {
775                        observed = observed.max(offset - previous);
776                    }
777                    last = Some(offset);
778                }
779            }
780            assert_eq!(
781                usize::from(bound.maximum_reservations_until_selection()),
782                observed
783            );
784        }
785    }
786
787    #[test]
788    fn reference_noisy_tenant_receives_exactly_twenty_percent_per_cycle() {
789        let mut tenants = vec![weight("noisy", 20)];
790        for index in 0..10 {
791            tenants.push(weight(&format!("small-{index:02}"), 8));
792        }
793        let policy = WeightedFairnessPolicy::new(shard("reference-load:v1"), tenants).unwrap();
794        assert_eq!(policy.cycle_length(), 100);
795        let noisy_index = policy
796            .tenants
797            .iter()
798            .position(|entry| entry.tenant_id.as_str() == "noisy")
799            .unwrap();
800        assert_eq!(
801            policy
802                .cycle
803                .iter()
804                .filter(|index| **index == noisy_index)
805                .count(),
806            20
807        );
808        assert!(
809            policy
810                .starvation_bound(&tenant("small-00"))
811                .unwrap()
812                .maximum_reservations_until_selection()
813                <= 13
814        );
815    }
816
817    #[test]
818    fn invalid_policy_shapes_fail_closed() {
819        assert!(matches!(
820            WeightedFairnessPolicy::new(shard("empty"), []),
821            Err(WeightedFairnessPolicyError::Empty)
822        ));
823        assert!(matches!(
824            WeightedFairnessPolicy::new(shard("duplicate"), [weight("a", 1), weight("a", 2)]),
825            Err(WeightedFairnessPolicyError::DuplicateTenant)
826        ));
827        assert_eq!(
828            TenantFairnessWeight::new(tenant("a"), 0),
829            Err(TenantFairnessWeightError::InvalidWeight)
830        );
831    }
832
833    #[test]
834    fn fair_scheduler_options_enforce_bounded_lost_ack_retries() {
835        assert_eq!(
836            DurableFairSchedulerOptions::new(0, Duration::from_millis(1)),
837            Err(DurableFairSchedulerOptionsError::InvalidReservationAttempts)
838        );
839        assert_eq!(
840            DurableFairSchedulerOptions::new(1, Duration::ZERO),
841            Err(DurableFairSchedulerOptionsError::InvalidReservationRetryDelay)
842        );
843        assert!(DurableFairSchedulerOptions::default().maximum_reservation_attempts() > 0);
844    }
845
846    proptest! {
847        #[test]
848        fn compiled_policy_preserves_arbitrary_bounded_weights_and_circular_bounds(
849            weights in prop::collection::vec(1_u16..=32, 1..=24),
850        ) {
851            let entries = weights
852                .iter()
853                .copied()
854                .enumerate()
855                .map(|(index, weight)| {
856                    TenantFairnessWeight::new(
857                        tenant(&format!("property-{index:03}")),
858                        weight,
859                    )
860                    .unwrap()
861                })
862                .collect::<Vec<_>>();
863            let mut reversed = entries.clone();
864            reversed.reverse();
865            let policy = WeightedFairnessPolicy::new(shard("property:v1"), entries).unwrap();
866            let reversed_policy =
867                WeightedFairnessPolicy::new(shard("property:v1"), reversed).unwrap();
868            prop_assert_eq!(policy.digest(), reversed_policy.digest());
869            prop_assert_eq!(policy.cycle.as_ref(), reversed_policy.cycle.as_ref());
870
871            for (index, entry) in policy.tenants.iter().enumerate() {
872                let actual = policy.cycle.iter().filter(|slot| **slot == index).count();
873                prop_assert_eq!(actual, usize::from(entry.weight()));
874                let positions = policy
875                    .cycle
876                    .iter()
877                    .enumerate()
878                    .filter_map(|(slot, selected)| (*selected == index).then_some(slot))
879                    .collect::<Vec<_>>();
880                let maximum_gap = positions
881                    .iter()
882                    .copied()
883                    .zip(
884                        positions
885                            .iter()
886                            .copied()
887                            .skip(1)
888                            .chain(positions.first().map(|first| first + policy.cycle.len())),
889                    )
890                    .map(|(current, next)| next - current)
891                    .max()
892                    .unwrap();
893                prop_assert_eq!(
894                    usize::from(
895                        policy
896                            .starvation_bound(entry.tenant_id())
897                            .unwrap()
898                            .maximum_reservations_until_selection()
899                    ),
900                    maximum_gap,
901                );
902            }
903        }
904    }
905}