1use std::collections::hash_map::DefaultHasher;
51use std::collections::HashMap;
52use std::hash::{Hash, Hasher};
53use std::time::{Duration, Instant};
54
55use hyprstream_rpc::transport::TransportConfig;
56
57#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
63pub struct ReplicaId([u8; 32]);
64
65impl ReplicaId {
66 pub const fn from_bytes(bytes: [u8; 32]) -> Self {
71 Self(bytes)
72 }
73
74 pub const fn as_bytes(&self) -> &[u8; 32] {
76 &self.0
77 }
78}
79
80pub type SessionId = String;
82
83pub const DEFAULT_LEASE_DURATION: Duration = Duration::from_secs(30);
86
87pub const DEFAULT_STALL_DEADLINE: Duration = Duration::from_secs(45);
89
90pub const DEFAULT_DOWN_TTL: Duration = Duration::from_secs(5);
92
93#[derive(Debug, Clone)]
98pub struct InferenceServerInfo {
99 pub replica_id: ReplicaId,
101 pub transport: TransportConfig,
103 pub gpu_memory_free: u64,
105 pub active_sessions: u64,
107 pub last_heartbeat: Instant,
109}
110
111impl InferenceServerInfo {
112 fn weight(&self) -> u64 {
116 self.gpu_memory_free.saturating_add(1)
117 }
118}
119
120#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
122pub enum PlacementPolicy {
123 #[default]
127 Affinity,
128 Spread,
131}
132
133#[derive(Debug, Clone)]
141pub struct SessionAffinity {
142 map: HashMap<SessionId, AffinityBinding>,
143 generation: u64,
146 lease_duration: Duration,
147}
148
149#[derive(Debug, Clone, Copy)]
150struct AffinityBinding {
151 owner: ReplicaId,
152 leased_until: Instant,
153}
154
155impl Default for SessionAffinity {
156 fn default() -> Self {
157 Self::new(DEFAULT_LEASE_DURATION)
158 }
159}
160
161impl SessionAffinity {
162 pub fn new(lease_duration: Duration) -> Self {
164 Self {
165 map: HashMap::new(),
166 generation: 0,
167 lease_duration,
168 }
169 }
170
171 pub fn get(&mut self, session_id: &str) -> Option<ReplicaId> {
174 let now = Instant::now();
175 let binding = self.map.get_mut(session_id)?;
176 if binding.leased_until <= now {
177 self.map.remove(session_id);
180 return None;
181 }
182 binding.leased_until = now + self.lease_duration;
184 Some(binding.owner)
185 }
186
187 pub fn peek(&self, session_id: &str) -> Option<ReplicaId> {
189 let now = Instant::now();
190 self.map
191 .get(session_id)
192 .filter(|b| b.leased_until > now)
193 .map(|b| b.owner)
194 }
195
196 pub fn set(&mut self, session_id: SessionId, owner: ReplicaId) {
198 let leased_until = Instant::now() + self.lease_duration;
199 match self.map.insert(
200 session_id,
201 AffinityBinding {
202 owner,
203 leased_until,
204 },
205 ) {
206 None => self.generation = self.generation.wrapping_add(1),
207 Some(old) if old.owner != owner => {
208 self.generation = self.generation.wrapping_add(1);
209 }
210 _ => {}
211 }
212 }
213
214 pub fn remove(&mut self, session_id: &str) {
216 if self.map.remove(session_id).is_some() {
217 self.generation = self.generation.wrapping_add(1);
218 }
219 }
220
221 pub fn sweep_expired(&mut self) -> usize {
223 let now = Instant::now();
224 let before = self.map.len();
225 self.map.retain(|_, b| b.leased_until > now);
226 let dropped = before - self.map.len();
227 if dropped > 0 {
228 self.generation = self.generation.wrapping_add(1);
229 }
230 dropped
231 }
232
233 pub fn len(&self) -> usize {
235 self.map.len()
236 }
237
238 pub fn is_empty(&self) -> bool {
240 self.map.is_empty()
241 }
242
243 pub fn generation(&self) -> u64 {
245 self.generation
246 }
247
248 pub fn lease_duration(&self) -> Duration {
250 self.lease_duration
251 }
252}
253
254pub fn hrw_select(session_id: &str, candidates: &[InferenceServerInfo]) -> Option<usize> {
275 if candidates.is_empty() {
276 return None;
277 }
278 let mut best_idx = 0usize;
279 let mut best_score = score(session_id, &candidates[0]);
280 for (idx, cand) in candidates.iter().enumerate().skip(1) {
281 let s = score(session_id, cand);
282 if s > best_score {
283 best_score = s;
284 best_idx = idx;
285 }
286 }
287 Some(best_idx)
288}
289
290pub fn hrw_select_skip(
295 session_id: &str,
296 candidates: &[InferenceServerInfo],
297 skip: usize,
298) -> Option<usize> {
299 if candidates.is_empty() || skip >= candidates.len() {
300 return None;
301 }
302 let mut ranked: Vec<(u64, usize)> = candidates
304 .iter()
305 .enumerate()
306 .map(|(i, c)| (score(session_id, c), i))
307 .collect();
308 ranked.sort_unstable_by(|a, b| b.0.cmp(&a.0).then(a.1.cmp(&b.1)));
309 ranked.get(skip).map(|(_, idx)| *idx)
310}
311
312pub fn least_loaded_select(candidates: &[InferenceServerInfo]) -> Option<usize> {
315 if candidates.is_empty() {
316 return None;
317 }
318 let mut best_idx = 0usize;
319 for (idx, cand) in candidates.iter().enumerate().skip(1) {
320 let cur = &candidates[best_idx];
321 let better = cand.active_sessions < cur.active_sessions
322 || (cand.active_sessions == cur.active_sessions
323 && cand.gpu_memory_free > cur.gpu_memory_free);
324 if better {
325 best_idx = idx;
326 }
327 }
328 Some(best_idx)
329}
330
331fn score(session_id: &str, cand: &InferenceServerInfo) -> u64 {
334 let mut h = DefaultHasher::new();
335 session_id.hash(&mut h);
336 cand.replica_id.hash(&mut h);
337 let raw = h.finish();
338 raw.wrapping_mul(cand.weight())
341}
342
343#[derive(Debug, Clone, PartialEq, Eq)]
345pub struct Placement {
346 pub candidate_idx: usize,
348 pub replica_id: ReplicaId,
350 pub rebound: bool,
352}
353
354#[derive(Debug, Clone, Copy, PartialEq, Eq)]
356pub enum ExcludeReason {
357 Down,
359 Stalled,
361}
362
363#[derive(Debug, Clone, Copy)]
365struct NodeHealth {
366 down_until: Option<Instant>,
369}
370
371impl NodeHealth {
372 fn is_excluded(&self, now: Instant) -> bool {
373 self.down_until.is_some_and(|t| t > now)
374 }
375}
376
377#[derive(Debug, Clone)]
382pub struct CellRouter {
383 policy: PlacementPolicy,
384 affinity: SessionAffinity,
385 health: HashMap<ReplicaId, NodeHealth>,
386 stalled: HashMap<ReplicaId, Instant>,
389 down_ttl: Duration,
390 stall_deadline: Duration,
391}
392
393impl Default for CellRouter {
394 fn default() -> Self {
395 Self::new(PlacementPolicy::default())
396 }
397}
398
399impl CellRouter {
400 pub fn new(policy: PlacementPolicy) -> Self {
402 Self {
403 policy,
404 affinity: SessionAffinity::default(),
405 health: HashMap::new(),
406 stalled: HashMap::new(),
407 down_ttl: DEFAULT_DOWN_TTL,
408 stall_deadline: DEFAULT_STALL_DEADLINE,
409 }
410 }
411
412 pub fn with_down_ttl(mut self, ttl: Duration) -> Self {
414 self.down_ttl = ttl;
415 self
416 }
417
418 pub fn with_stall_deadline(mut self, deadline: Duration) -> Self {
420 self.stall_deadline = deadline;
421 self
422 }
423
424 pub fn with_lease_duration(mut self, d: Duration) -> Self {
426 self.affinity = SessionAffinity::new(d);
427 self
428 }
429
430 pub fn policy(&self) -> PlacementPolicy {
432 self.policy
433 }
434
435 pub fn affinity(&self) -> &SessionAffinity {
437 &self.affinity
438 }
439
440 pub fn affinity_mut(&mut self) -> &mut SessionAffinity {
442 &mut self.affinity
443 }
444
445 fn healthy<'a>(
449 &self,
450 candidates: &'a [InferenceServerInfo],
451 now: Instant,
452 ) -> Vec<(usize, &'a InferenceServerInfo)> {
453 candidates
454 .iter()
455 .enumerate()
456 .filter(|(_, c)| {
457 let down = self
458 .health
459 .get(&c.replica_id)
460 .is_some_and(|h| h.is_excluded(now));
461 let stalled = self.stalled.contains_key(&c.replica_id);
462 !down && !stalled
463 })
464 .collect()
465 }
466
467 pub fn place(
477 &mut self,
478 session_id: &str,
479 candidates: &[InferenceServerInfo],
480 now: Instant,
481 ) -> Option<Placement> {
482 let healthy = self.healthy(candidates, now);
483 if healthy.is_empty() {
484 return None;
485 }
486 if matches!(self.policy, PlacementPolicy::Affinity) {
488 if let Some(owner) = self.affinity.get(session_id) {
489 if let Some(&(idx, _)) = healthy.iter().find(|(_, c)| c.replica_id == owner) {
490 return Some(Placement {
491 candidate_idx: idx,
492 replica_id: owner,
493 rebound: false,
494 });
495 }
496 }
498 }
499 let healthy_view: Vec<InferenceServerInfo> =
503 healthy.iter().map(|(_, c)| (*c).clone()).collect();
504 let local_idx = match self.policy {
505 PlacementPolicy::Affinity => hrw_select(session_id, &healthy_view),
506 PlacementPolicy::Spread => least_loaded_select(&healthy_view),
507 }?;
508 let (idx, chosen) = healthy[local_idx];
509 self.affinity.set(session_id.to_owned(), chosen.replica_id);
510 Some(Placement {
511 candidate_idx: idx,
512 replica_id: chosen.replica_id,
513 rebound: true,
514 })
515 }
516
517 pub fn report_dial_fail(&mut self, replica_id: ReplicaId, now: Instant) -> bool {
525 let down_until = now + self.down_ttl;
526 match self.health.get(&replica_id) {
527 Some(h) if h.is_excluded(now) => false,
528 _ => {
529 self.health.insert(
530 replica_id,
531 NodeHealth {
532 down_until: Some(down_until),
533 },
534 );
535 true
536 }
537 }
538 }
539
540 pub fn report_stall(&mut self, replica_id: ReplicaId, now: Instant) {
546 self.stalled.insert(replica_id, now);
547 }
548
549 pub fn clear_node(&mut self, replica_id: ReplicaId) {
552 self.health.remove(&replica_id);
553 self.stalled.remove(&replica_id);
554 }
555
556 pub fn stall_deadline(&self) -> Duration {
558 self.stall_deadline
559 }
560
561 pub fn release_session(&mut self, session_id: &str) {
563 self.affinity.remove(session_id);
564 }
565
566 pub fn heartbeat(&mut self, session_id: &str) -> bool {
569 self.affinity.get(session_id).is_some()
570 }
571
572 pub fn is_excluded(&self, replica_id: ReplicaId, now: Instant) -> Option<ExcludeReason> {
574 if self.stalled.contains_key(&replica_id) {
575 return Some(ExcludeReason::Stalled);
576 }
577 if self
578 .health
579 .get(&replica_id)
580 .is_some_and(|h| h.is_excluded(now))
581 {
582 return Some(ExcludeReason::Down);
583 }
584 None
585 }
586}
587
588#[cfg(test)]
589#[allow(clippy::unwrap_used)] mod tests {
591 use super::*;
592
593 fn node(id: u8, mem_free: u64, active: u64) -> InferenceServerInfo {
594 InferenceServerInfo {
595 replica_id: ReplicaId::from_bytes([id; 32]),
596 transport: TransportConfig::inproc("test"),
597 gpu_memory_free: mem_free,
598 active_sessions: active,
599 last_heartbeat: Instant::now(),
600 }
601 }
602
603 fn replica_set() -> Vec<InferenceServerInfo> {
604 vec![
605 node(0x10, 16 * 1024 * 1024 * 1024, 0),
606 node(0x20, 16 * 1024 * 1024 * 1024, 0),
607 node(0x30, 16 * 1024 * 1024 * 1024, 0),
608 ]
609 }
610
611 #[test]
614 fn hrw_same_session_same_node() {
615 let set = replica_set();
616 let a = hrw_select("sess-A", &set).unwrap();
617 let b = hrw_select("sess-A", &set).unwrap();
618 assert_eq!(a, b, "same session must always select the same node");
619 }
620
621 #[test]
622 fn hrw_uses_index_into_input_slice() {
623 let set = replica_set();
624 let idx = hrw_select("sess-A", &set).unwrap();
625 assert!(idx < set.len());
626 }
627
628 #[test]
629 fn hrw_empty_returns_none() {
630 assert_eq!(hrw_select("sess", &[]), None);
631 }
632
633 #[test]
634 fn hrw_spreads_distinct_sessions() {
635 let set = replica_set();
639 let mut counts = [0usize; 3];
640 for i in 0..150u32 {
641 let idx = hrw_select(&format!("sess-{i}"), &set).unwrap();
642 counts[idx] += 1;
643 }
644 assert!(
646 counts.iter().all(|&c| c > 0),
647 "every node must get some sessions: {counts:?}"
648 );
649 assert!(
650 counts.iter().all(|&c| c < 150),
651 "no node should get all sessions: {counts:?}"
652 );
653 }
654
655 #[test]
656 fn hrw_capacity_weight_biases_heavier_node() {
657 const GB: u64 = 1024 * 1024 * 1024;
661 let heavy_set = vec![
662 node(0x10, GB, 0), node(0x20, 10 * GB, 0), node(0x30, GB, 0), ];
666 let mut counts = [0usize; 3];
667 for i in 0..600u32 {
668 let idx = hrw_select(&format!("sess-{i}"), &heavy_set).unwrap();
669 counts[idx] += 1;
670 }
671 assert!(
672 counts[1] > counts[0] && counts[1] > counts[2],
673 "heavier node should win the most: {counts:?}"
674 );
675 }
676
677 #[test]
678 fn hrw_select_skip_picks_distinct_nodes() {
679 let set = replica_set();
680 let primary = hrw_select("sess-X", &set).unwrap();
681 let first_fallback = hrw_select_skip("sess-X", &set, 1).unwrap();
682 let second_fallback = hrw_select_skip("sess-X", &set, 2).unwrap();
683 assert_ne!(
684 primary, first_fallback,
685 "primary and first fallback must differ"
686 );
687 assert_ne!(primary, second_fallback);
688 assert_ne!(first_fallback, second_fallback);
689 assert_eq!(hrw_select_skip("sess-X", &set, 3), None);
691 }
692
693 #[test]
694 fn hrw_consistent_under_set_shrink_grow() {
695 let set = replica_set();
698 let owner_full = hrw_select("sess-Z", &set).unwrap();
699 let owner_replica_id = set[owner_full].replica_id;
700 for drop_idx in 0..set.len() {
702 if drop_idx == owner_full {
703 continue;
704 }
705 let subset: Vec<_> = set
706 .iter()
707 .enumerate()
708 .filter(|(i, _)| *i != drop_idx)
709 .map(|(_, c)| c.clone())
710 .collect();
711 let owner_sub = hrw_select("sess-Z", &subset).unwrap();
712 assert_eq!(
713 subset[owner_sub].replica_id, owner_replica_id,
714 "sess-Z must stay on its owner when a different node is dropped"
715 );
716 }
717 }
718
719 #[test]
722 fn least_loaded_picks_fewest_active_sessions() {
723 let set = vec![
724 node(0x10, 8 * 1024 * 1024 * 1024, 5),
725 node(0x20, 8 * 1024 * 1024 * 1024, 1), node(0x30, 8 * 1024 * 1024 * 1024, 9),
727 ];
728 let idx = least_loaded_select(&set).unwrap();
729 assert_eq!(idx, 1, "least-loaded must pick the fewest active sessions");
730 }
731
732 #[test]
733 fn least_loaded_breaks_ties_by_memory() {
734 let set = vec![
735 node(0x10, 4 * 1024 * 1024 * 1024, 2),
736 node(0x20, 16 * 1024 * 1024 * 1024, 2), node(0x30, 2 * 1024 * 1024 * 1024, 2),
738 ];
739 let idx = least_loaded_select(&set).unwrap();
740 assert_eq!(idx, 1, "tie should break toward most free memory");
741 }
742
743 #[test]
746 fn affinity_get_set_expire() {
747 let mut aff = SessionAffinity::new(Duration::from_millis(50));
748 let owner = ReplicaId::from_bytes([0xAB; 32]);
749 assert_eq!(aff.peek("s1"), None, "empty map → no binding");
750 aff.set("s1".to_owned(), owner);
751 assert_eq!(aff.peek("s1"), Some(owner));
752 assert_eq!(aff.get("s1"), Some(owner));
754 std::thread::sleep(Duration::from_millis(80));
756 assert_eq!(
757 aff.peek("s1"),
758 None,
759 "expired binding must not be visible to peek"
760 );
761 assert_eq!(aff.get("s1"), None);
763 }
764
765 #[test]
766 fn affinity_generation_bumps_on_change() {
767 let mut aff = SessionAffinity::new(Duration::from_secs(10));
768 let g0 = aff.generation();
769 aff.set("s1".to_owned(), ReplicaId::from_bytes([1; 32]));
770 assert!(aff.generation() > g0);
771 let g1 = aff.generation();
772 aff.set("s1".to_owned(), ReplicaId::from_bytes([1; 32]));
774 assert_eq!(aff.generation(), g1);
775 aff.set("s1".to_owned(), ReplicaId::from_bytes([2; 32]));
777 assert!(aff.generation() > g1);
778 }
779
780 #[test]
781 fn affinity_remove_drops_binding() {
782 let mut aff = SessionAffinity::new(Duration::from_secs(10));
783 aff.set("s1".to_owned(), ReplicaId::from_bytes([1; 32]));
784 assert_eq!(aff.len(), 1);
785 aff.remove("s1");
786 assert!(aff.is_empty());
787 }
788
789 #[test]
790 fn affinity_sweep_expired() {
791 let mut aff = SessionAffinity::new(Duration::from_millis(20));
792 aff.set("a".to_owned(), ReplicaId::from_bytes([1; 32]));
793 aff.set("b".to_owned(), ReplicaId::from_bytes([2; 32]));
794 std::thread::sleep(Duration::from_millis(40));
795 let dropped = aff.sweep_expired();
796 assert_eq!(dropped, 2);
797 assert!(aff.is_empty());
798 }
799
800 #[test]
803 fn router_affinity_reuses_binding() {
804 let mut router = CellRouter::default();
805 let set = replica_set();
806 let now = Instant::now();
807 let p1 = router.place("sess-A", &set, now).unwrap();
808 assert!(p1.rebound, "first placement must be a rebind");
809 let p2 = router.place("sess-A", &set, now).unwrap();
810 assert!(!p2.rebound, "second placement must hit the affinity cache");
811 assert_eq!(p1.replica_id, p2.replica_id);
812 assert_eq!(p1.candidate_idx, p2.candidate_idx);
813 }
814
815 #[test]
816 fn router_affinity_distinct_sessions_spread() {
817 let mut router = CellRouter::default();
818 let set = replica_set();
819 let now = Instant::now();
820 let mut owners = std::collections::HashSet::new();
821 for i in 0..60 {
822 let p = router.place(&format!("sess-{i}"), &set, now).unwrap();
823 owners.insert(p.replica_id);
824 }
825 assert!(
826 owners.len() > 1,
827 "distinct sessions should spread: got {owners:?}"
828 );
829 }
830
831 #[test]
834 fn router_sprow_bypasses_affinity_and_picks_least_loaded() {
835 let mut router = CellRouter::new(PlacementPolicy::Spread);
836 let set = vec![
837 node(0x10, 8 * 1024 * 1024 * 1024, 5),
838 node(0x20, 8 * 1024 * 1024 * 1024, 1), node(0x30, 8 * 1024 * 1024 * 1024, 9),
840 ];
841 let now = Instant::now();
842 let _ = router.place("sess-A", &set, now).unwrap();
845 let p = router.place("sess-B", &set, now).unwrap();
846 assert_eq!(
847 p.replica_id, set[1].replica_id,
848 "Spread must pick least-loaded"
849 );
850 }
851
852 #[test]
855 fn router_dial_fail_excludes_and_reassigns() {
856 let mut router = CellRouter::default();
857 let set = replica_set();
858 let now = Instant::now();
859 let p1 = router.place("sess-A", &set, now).unwrap();
860 let was_new = router.report_dial_fail(p1.replica_id, now);
862 assert!(was_new, "first down-mark must be a transition");
863 let p2 = router.place("sess-A", &set, now).unwrap();
865 assert_ne!(
866 p2.replica_id, p1.replica_id,
867 "down node must not be reselected"
868 );
869 assert!(
870 p2.rebound,
871 "reassignment after down must record a new binding"
872 );
873 let was_new2 = router.report_dial_fail(p1.replica_id, now);
875 assert!(
876 !was_new2,
877 "re-reporting an already-down node is not a transition"
878 );
879 }
880
881 #[test]
882 fn router_down_node_recovers_after_ttl() {
883 let mut router = CellRouter::default().with_down_ttl(Duration::from_millis(30));
884 let set = replica_set();
885 let t0 = Instant::now();
886 let p1 = router.place("sess-A", &set, t0).unwrap();
887 router.report_dial_fail(p1.replica_id, t0);
888 let t1 = t0 + Duration::from_millis(40);
890 router.release_session("sess-A");
893 let p2 = router.place("sess-A", &set, t1).unwrap();
894 assert!(
896 router.is_excluded(p1.replica_id, t1).is_none(),
897 "node should be healthy after TTL"
898 );
899 let _ = p2;
900 }
901
902 #[test]
903 fn router_all_down_returns_none() {
904 let mut router = CellRouter::default();
905 let set = replica_set();
906 let now = Instant::now();
907 for n in &set {
908 router.report_dial_fail(n.replica_id, now);
909 }
910 assert!(
911 router.place("sess-A", &set, now).is_none(),
912 "all-down → no placement"
913 );
914 }
915
916 #[test]
919 fn router_stall_excludes_and_reassigns() {
920 let mut router = CellRouter::default();
921 let set = replica_set();
922 let now = Instant::now();
923 let p1 = router.place("sess-A", &set, now).unwrap();
924 router.report_stall(p1.replica_id, now);
925 assert_eq!(
926 router.is_excluded(p1.replica_id, now),
927 Some(ExcludeReason::Stalled)
928 );
929 let p2 = router.place("sess-A", &set, now).unwrap();
930 assert_ne!(
931 p2.replica_id, p1.replica_id,
932 "stalled node must not be reselected"
933 );
934 router.clear_node(p1.replica_id);
936 assert!(router.is_excluded(p1.replica_id, now).is_none());
937 }
938
939 #[test]
940 fn router_stall_deadline_exposed() {
941 let r = CellRouter::default().with_stall_deadline(Duration::from_secs(7));
942 assert_eq!(r.stall_deadline(), Duration::from_secs(7));
943 }
944
945 #[test]
948 fn router_heartbeat_renews_and_release_drops() {
949 let mut router = CellRouter::default();
950 let set = replica_set();
951 let now = Instant::now();
952 router.place("sess-A", &set, now).unwrap();
953 assert!(
954 router.heartbeat("sess-A"),
955 "heartbeat on a live session renews the lease"
956 );
957 router.release_session("sess-A");
958 assert!(
959 !router.heartbeat("sess-A"),
960 "heartbeat after release has nothing to renew"
961 );
962 }
963}