1use 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#[derive(Clone, Debug, Eq, PartialEq)]
28pub struct TenantFairnessWeight {
29 tenant_id: TenantId,
30 weight: u16,
31}
32
33impl TenantFairnessWeight {
34 pub const MAX_WEIGHT: u16 = 1024;
36
37 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 #[must_use]
51 pub const fn tenant_id(&self) -> &TenantId {
52 &self.tenant_id
53 }
54
55 #[must_use]
57 pub const fn weight(&self) -> u16 {
58 self.weight
59 }
60}
61
62#[derive(Clone, Copy, Debug, Eq, Error, PartialEq)]
64#[non_exhaustive]
65pub enum TenantFairnessWeightError {
66 #[error("tenant fairness weight is invalid")]
68 InvalidWeight,
69}
70
71#[derive(Clone, Copy, Debug, Eq, PartialEq)]
73pub struct TenantStarvationBound {
74 maximum_reservations_until_selection: u16,
75}
76
77impl TenantStarvationBound {
78 #[must_use]
84 pub const fn maximum_reservations_until_selection(self) -> u16 {
85 self.maximum_reservations_until_selection
86 }
87}
88
89#[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 pub const MAX_TENANTS: usize = 1024;
109 pub const MAX_CYCLE_LENGTH: u16 = SchedulerFairnessPolicyRegistration::MAX_CYCLE_LENGTH;
111
112 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 #[must_use]
179 pub const fn shard_id(&self) -> &SchedulerShardId {
180 &self.shard_id
181 }
182
183 #[must_use]
185 pub const fn digest(&self) -> Digest {
186 self.registration.policy_digest()
187 }
188
189 #[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 #[must_use]
197 pub const fn tenants(&self) -> &[TenantFairnessWeight] {
198 &self.tenants
199 }
200
201 #[must_use]
203 pub const fn canonical_bytes(&self) -> &[u8] {
204 &self.canonical_bytes
205 }
206
207 #[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 #[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#[derive(Clone, Copy, Debug, Eq, Error, PartialEq)]
243#[non_exhaustive]
244pub enum WeightedFairnessPolicyError {
245 #[error("weighted fairness policy must contain at least one tenant")]
247 Empty,
248 #[error("weighted fairness policy contains too many tenants")]
250 TooManyTenants,
251 #[error("weighted fairness policy contains a duplicate tenant")]
253 DuplicateTenant,
254 #[error("weighted fairness policy cycle is too large")]
256 CycleTooLarge,
257 #[error("weighted fairness cycle failed internal count verification")]
259 InvalidCompiledCycle,
260 #[error("weighted fairness policy canonical encoding failed")]
262 CanonicalEncoding,
263 #[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#[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 pub const HARD_MAXIMUM_RESERVATION_ATTEMPTS: u8 = 10;
362
363 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 #[must_use]
390 pub const fn maximum_reservation_attempts(self) -> u8 {
391 self.maximum_reservation_attempts
392 }
393
394 #[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#[derive(Clone, Copy, Debug, Eq, Error, PartialEq)]
412#[non_exhaustive]
413pub enum DurableFairSchedulerOptionsError {
414 #[error("fair scheduler reservation attempt count is invalid")]
416 InvalidReservationAttempts,
417 #[error("fair scheduler reservation retry delay is invalid")]
419 InvalidReservationRetryDelay,
420}
421
422#[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 #[must_use]
435 pub const fn reservation(&self) -> &SchedulerFairnessReservation {
436 &self.reservation
437 }
438
439 #[must_use]
441 pub const fn tenant_id(&self) -> &TenantId {
442 &self.tenant_id
443 }
444
445 #[must_use]
447 pub const fn starvation_bound(&self) -> TenantStarvationBound {
448 self.starvation_bound
449 }
450
451 #[must_use]
453 pub const fn reservation_retries(&self) -> u8 {
454 self.reservation_retries
455 }
456
457 #[must_use]
459 pub const fn tenant_tick(&self) -> &TenantSchedulerTick {
460 &self.tenant_tick
461 }
462
463 #[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#[derive(Clone)]
492pub struct DurableFairScheduler {
493 store: PostgresStore,
494 tenant_scheduler: DurableTenantScheduler,
495 policy: Arc<WeightedFairnessPolicy>,
496 options: DurableFairSchedulerOptions,
497}
498
499impl DurableFairScheduler {
500 pub fn execution_activity(&self) -> crate::GraphExecutionActivity {
502 self.tenant_scheduler.execution_activity()
503 }
504
505 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 #[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() != ®istration {
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 #[must_use]
562 pub fn policy(&self) -> &WeightedFairnessPolicy {
563 &self.policy
564 }
565
566 #[must_use]
568 pub const fn options(&self) -> DurableFairSchedulerOptions {
569 self.options
570 }
571
572 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#[derive(Debug, Error)]
642#[non_exhaustive]
643pub enum DurableFairSchedulerBuildError {
644 #[error("fair scheduler tenant worker binding failed: {source}")]
646 Tenant {
647 #[from]
649 source: DurableTenantSchedulerBuildError,
650 },
651 #[error("fair scheduler policy registration failed: {source}")]
653 Store {
654 #[from]
656 source: StoreError,
657 },
658 #[error("fair scheduler durable policy projection does not match local policy")]
660 PolicyProjectionMismatch,
661}
662
663#[derive(Debug, Error)]
665#[non_exhaustive]
666pub enum FairSchedulerError {
667 #[error("fair scheduler slot reservation failed: {source}")]
669 Store {
670 #[source]
672 source: StoreError,
673 },
674 #[error("selected tenant scheduler failed: {source}")]
676 Tenant {
677 #[source]
679 source: TenantSchedulerError,
680 },
681 #[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}