Skip to main content

hyprstream_core/services/
router.rs

1//! Leaf-tier cell-router for federated inference scheduling (#322).
2//!
3//! Capacity-weighted HRW (Highest Random Weight / Rendezvous Hashing) for
4//! session placement within a single cell (a PDS / trust domain). This is the
5//! **leaf tier** of the federated scheduling design — a bounded set of tens to
6//! low-thousands of nodes. The global tier (cell directory over ~10k–100k
7//! cells) is a separate epic.
8//!
9//! # Two keys, two jobs
10//!
11//! - **OID** (git commit SHA) = content selector → yields the replica set
12//!   (nodes serving that checkpoint). The router body operates on a *resolved*
13//!   replica set; how the OID is resolved (`at://`→DID→OID per the
14//!   federated-model-addressing spike, or the local `Resolver`) is the entry's
15//!   job, not the router's.
16//! - **session_id** = placement key → capacity-weighted HRW over the replica
17//!   set → owner node.
18//!
19//! HRW gives both placement properties simultaneously:
20//! - **Affinity:** the same `session_id` always hashes to the same node while
21//!   the replica set is stable → KV-cache reuse.
22//! - **Spread:** distinct `session_id`s distribute uniformly across the set.
23//!
24//! # Failure detection
25//!
26//! Two reactive layers, no proactive membership protocol (SWIM is unnecessary
27//! at this tier — see the federated-scheduling-dht-pq-spike §4):
28//! - **Dial-fail (sync):** a failed dial marks the node down and reassigns to
29//!   the next HRW choice on the next call.
30//! - **Token-stream stall watchdog:** absence of tokens past a deadline marks
31//!   the node stalled and reassigns.
32//!
33//! # v1 constraints
34//!
35//! - **No new capnp surface.** Reuse `healthCheck@13` / `isReady@3` from
36//!   `service_events.capnp` for health integration.
37//! - **No gossip.** Load counters are router-side local state only (v1); gossip
38//!   is a future option for proactive capacity rebalancing (spike §4).
39//! - **CPU-testable.** Router logic is plain data structures — no tensors, no
40//!   GPU. tch-rs is `!Send`; this module touches none of it.
41//!
42//! # Determinism
43//!
44//! HRW requires a hash that is **stable across processes** (so two routers in
45//! the same cell pick the same owner for the same session). `DefaultHasher::new()`
46//! is documented to use constant keys, so its output is deterministic across
47//! runs and processes. We do *not* use `RandomState` (which is randomly seeded
48//! per process and would break cross-router agreement).
49
50use 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/// Opaque identifier for an inference replica used only for placement.
58///
59/// This is not an iroh `EndpointId`, application signing key, or authorization
60/// subject. Network reach and authenticated authority must be resolved and
61/// verified independently before a future remote placement can be dialed.
62#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
63pub struct ReplicaId([u8; 32]);
64
65impl ReplicaId {
66    /// Construct placement metadata from its stable byte representation.
67    ///
68    /// This explicit conversion does not verify or grant any transport or
69    /// authority role; it only prevents accidental type interchange.
70    pub const fn from_bytes(bytes: [u8; 32]) -> Self {
71        Self(bytes)
72    }
73
74    /// Borrow the stable bytes used by the placement hash.
75    pub const fn as_bytes(&self) -> &[u8; 32] {
76        &self.0
77    }
78}
79
80/// Identifier for a chat / inference session (used as the HRW placement key).
81pub type SessionId = String;
82
83/// Default lease for a session→owner affinity binding. Renewed on every
84/// heartbeat; expiry forces a fresh HRW on the next request.
85pub const DEFAULT_LEASE_DURATION: Duration = Duration::from_secs(30);
86
87/// Default deadline before a token-starved stream is declared stalled.
88pub const DEFAULT_STALL_DEADLINE: Duration = Duration::from_secs(45);
89
90/// Default negative-cache TTL on a dial-fail (avoid hammering a down node).
91pub const DEFAULT_DOWN_TTL: Duration = Duration::from_secs(5);
92
93/// Information about a candidate inference server in the cell.
94///
95/// The replica set for a resolved OID is `Vec<InferenceServerInfo>`. The router
96/// applies HRW over this set keyed by `session_id`.
97#[derive(Debug, Clone)]
98pub struct InferenceServerInfo {
99    /// Opaque replica placement identifier; carries no transport or authority role.
100    pub replica_id: ReplicaId,
101    /// How to dial this node (Iroh for cross-host, Inproc for co-located).
102    pub transport: TransportConfig,
103    /// Free GPU memory in bytes (capacity weight for HRW).
104    pub gpu_memory_free: u64,
105    /// Active sessions currently routed to this node (router-side counter).
106    pub active_sessions: u64,
107    /// Last heartbeat / state change observed by the router.
108    pub last_heartbeat: Instant,
109}
110
111impl InferenceServerInfo {
112    /// Capacity weight used by HRW. Free GPU memory is the primary signal
113    /// (more free → more likely to win HRW for a new session). We add 1 so a
114    /// zero-free node is still a selectable fallback rather than weight-0.
115    fn weight(&self) -> u64 {
116        self.gpu_memory_free.saturating_add(1)
117    }
118}
119
120/// Where to place a session within the replica set.
121#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
122pub enum PlacementPolicy {
123    /// Stick a session to its existing owner for KV-cache reuse. Falls back to
124    /// HRW when there is no live binding. This is the default — most inference
125    /// workloads benefit from KV-cache reuse.
126    #[default]
127    Affinity,
128    /// Always pick the least-loaded candidate (stateless fanout). Bypasses the
129    /// affinity map entirely; useful for one-shot / stateless requests.
130    Spread,
131}
132
133/// Session→owner affinity map with heartbeat-lease renewal.
134///
135/// A binding is only valid while its lease is fresh. A heartbeat (any request
136/// touching the session) renews the lease; once the lease expires the next
137/// request re-runs HRW and rebinds. This keeps affinity as a *perf hint, not a
138/// correctness invariant* — a stale binding can't corrupt state because git
139/// ref-CAS remains the only hard-consistency point (spike §5.4).
140#[derive(Debug, Clone)]
141pub struct SessionAffinity {
142    map: HashMap<SessionId, AffinityBinding>,
143    /// Bumped on every structural change (insert/remove/expiry sweep) so
144    /// observers can cheaply detect "something changed".
145    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    /// Create an empty affinity map with the given lease duration.
163    pub fn new(lease_duration: Duration) -> Self {
164        Self {
165            map: HashMap::new(),
166            generation: 0,
167            lease_duration,
168        }
169    }
170
171    /// Look up a live (non-expired) binding for a session, renewing its lease
172    /// on hit. Returns `None` if there is no binding or it has expired.
173    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            // Expired — drop and re-HRW. Don't touch `generation` here; the
178            // subsequent `set` from the rebind will bump it.
179            self.map.remove(session_id);
180            return None;
181        }
182        // Renew on hit.
183        binding.leased_until = now + self.lease_duration;
184        Some(binding.owner)
185    }
186
187    /// Read-only peek (no lease renewal). Used by tests and observers.
188    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    /// Bind (or rebind) a session to an owner with a fresh lease.
197    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    /// Drop a binding (e.g. on session-complete or explicit release).
215    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    /// Drop all bindings whose lease has elapsed. Returns the number dropped.
222    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    /// Number of live bindings (does not sweep first).
234    pub fn len(&self) -> usize {
235        self.map.len()
236    }
237
238    /// Whether the map is empty.
239    pub fn is_empty(&self) -> bool {
240        self.map.is_empty()
241    }
242
243    /// Monotonic generation counter — bumps on any structural change.
244    pub fn generation(&self) -> u64 {
245        self.generation
246    }
247
248    /// Lease duration currently in effect.
249    pub fn lease_duration(&self) -> Duration {
250        self.lease_duration
251    }
252}
253
254/// Highest Random Weight (Rendezvous Hashing) selection.
255///
256/// For each candidate, compute `h(session_id ‖ replica_id)` weighted by capacity.
257/// The candidate with the highest weighted score wins. Deterministic for a
258/// given `(session_id, replica set)` pair: every router in the cell agrees on
259/// the owner without any coordination.
260///
261/// Returns the **index** into `candidates` of the winner, or `None` if the
262/// slice is empty.
263///
264/// # Capacity weighting
265///
266/// To bias placement toward higher-capacity (more free GPU memory) nodes without
267/// breaking HRW's consistency, we derive the per-node score from
268/// `weight_for_rank = -weight / ln(uniform_rand)` — the classic
269/// "weighted rendezvous" transform (Heintz et al.) which reduces to plain HRW
270/// when all weights are equal. We approximate it here with a cheaper but still
271/// consistency-preserving transform `score = hash * weight` so a heavier node
272/// wins ties more often. (Both transforms are deterministic in `(session,
273/// node)`, which is the only property HRW needs.)
274pub 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
290/// Select the `skip`-th HRW choice (0 = primary, 1 = first fallback, ...).
291///
292/// Used after a dial-fail / stall to pick the *next* candidate without
293/// disturbing the primary ranking. Returns `None` once `skip >= candidates.len()`.
294pub 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    // Build (score, idx) and sort descending; the `skip`-th entry is the answer.
303    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
312/// Select the least-loaded candidate (lowest `active_sessions`, ties broken by
313/// most free GPU memory). Returns `None` for an empty set.
314pub 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
331/// Weighted HRW score for a (session, node) pair. Deterministic across
332/// processes (see module docs on `DefaultHasher::new`).
333fn 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    // Multiply by the capacity weight. u64 wrapping mul preserves total order
339    // for non-pathological weights (we expect weights well below u64::MAX).
340    raw.wrapping_mul(cand.weight())
341}
342
343/// Outcome of a placement decision.
344#[derive(Debug, Clone, PartialEq, Eq)]
345pub struct Placement {
346    /// Index into the candidate slice that was chosen.
347    pub candidate_idx: usize,
348    /// The owning node id.
349    pub replica_id: ReplicaId,
350    /// Whether a new affinity binding was recorded (vs a cache hit).
351    pub rebound: bool,
352}
353
354/// Reason a node was excluded from placement (for the failure log / tests).
355#[derive(Debug, Clone, Copy, PartialEq, Eq)]
356pub enum ExcludeReason {
357    /// Explicitly marked down after a dial-fail (negative-cached for `down_ttl`).
358    Down,
359    /// Declared stalled by the token-stream watchdog.
360    Stalled,
361}
362
363/// Per-node failure state maintained by the router.
364#[derive(Debug, Clone, Copy)]
365struct NodeHealth {
366    /// When the negative-cache entry expires (`Instant`) and the node becomes
367    /// eligible again. `None` = healthy.
368    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/// Router-side load + health state for a cell's replica set.
378///
379/// Holds the replica set, the affinity map, and per-node health / down-cache.
380/// All updates are router-local in v1 (no gossip).
381#[derive(Debug, Clone)]
382pub struct CellRouter {
383    policy: PlacementPolicy,
384    affinity: SessionAffinity,
385    health: HashMap<ReplicaId, NodeHealth>,
386    /// Nodes currently declared stalled by the token-stream watchdog.
387    /// `Instant` = when the stall was declared (used for log/TTL).
388    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    /// Create a router with the given placement policy and default timers.
401    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    /// Override the dial-fail negative-cache TTL.
413    pub fn with_down_ttl(mut self, ttl: Duration) -> Self {
414        self.down_ttl = ttl;
415        self
416    }
417
418    /// Override the token-stream stall deadline.
419    pub fn with_stall_deadline(mut self, deadline: Duration) -> Self {
420        self.stall_deadline = deadline;
421        self
422    }
423
424    /// Override the affinity lease duration.
425    pub fn with_lease_duration(mut self, d: Duration) -> Self {
426        self.affinity = SessionAffinity::new(d);
427        self
428    }
429
430    /// Current placement policy.
431    pub fn policy(&self) -> PlacementPolicy {
432        self.policy
433    }
434
435    /// Borrow the affinity map (for tests / status).
436    pub fn affinity(&self) -> &SessionAffinity {
437        &self.affinity
438    }
439
440    /// Borrow the affinity map mutably (e.g. to renew/sweep from outside).
441    pub fn affinity_mut(&mut self) -> &mut SessionAffinity {
442        &mut self.affinity
443    }
444
445    /// Filter the candidate set to currently-healthy (non-down, non-stalled)
446    /// nodes, preserving order. Returns the original indices paired with the
447    /// info so callers can map back.
448    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    /// Place a session on a candidate from the replica set.
468    ///
469    /// - `Affinity`: reuses the live binding if present; otherwise HRW-selects
470    ///   over healthy candidates and records a new binding.
471    /// - `Spread`: always least-loaded-selects over healthy candidates (no
472    ///   affinity consulted).
473    ///
474    /// Down / stalled nodes are excluded. Returns `None` only if **no** healthy
475    /// candidate remains (the replica set is empty or entirely failed).
476    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        // Fast path: affinity hit on a node that is still in the healthy set.
487        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                // Owner is down/stalled/gone — fall through to HRW rebind.
497            }
498        }
499        // Cold path: select by policy over the healthy subset. The select
500        // functions return an index into the contiguous healthy view; we map
501        // back to the original candidate index via `healthy[local_idx].0`.
502        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    /// Mark a node down after a synchronous dial-fail. The node is
518    /// negative-cached for [`down_ttl`](Self::with_down_ttl) and excluded from
519    /// subsequent placements. The next `place()` for an affected session will
520    /// rebind to the next HRW choice.
521    ///
522    /// Returns `true` if this was a new down-mark (the node was previously
523    /// healthy), `false` if it was already down.
524    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    /// Mark a node stalled (token-stream watchdog fired). Stalled nodes are
541    /// excluded from placement until explicitly cleared
542    /// ([`clear_stall`](Self::clear_stall)). A stall does *not* start the
543    /// down-clock — it is a stronger signal (the node answered but is not
544    /// producing tokens).
545    pub fn report_stall(&mut self, replica_id: ReplicaId, now: Instant) {
546        self.stalled.insert(replica_id, now);
547    }
548
549    /// Clear a stall / down mark once the node recovers (e.g. a subsequent
550    /// `healthCheck` succeeds, or tokens resume).
551    pub fn clear_node(&mut self, replica_id: ReplicaId) {
552        self.health.remove(&replica_id);
553        self.stalled.remove(&replica_id);
554    }
555
556    /// Token-stream stall deadline currently in effect.
557    pub fn stall_deadline(&self) -> Duration {
558        self.stall_deadline
559    }
560
561    /// Record that a session has completed (release its affinity binding).
562    pub fn release_session(&mut self, session_id: &str) {
563        self.affinity.remove(session_id);
564    }
565
566    /// Record a heartbeat (renew the lease) for a session. Returns `true` if a
567    /// binding existed and was renewed.
568    pub fn heartbeat(&mut self, session_id: &str) -> bool {
569        self.affinity.get(session_id).is_some()
570    }
571
572    /// Whether a node is currently excluded (down or stalled).
573    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)] // panicking on `None` is the right behavior in unit tests
590mod 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    // ---- HRW determinism ----
612
613    #[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        // With equal-weight nodes, ~50 distinct sessions should land on all 3
636        // nodes (no single node should get > ~70% — that would indicate a
637        // broken hash).
638        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        // All nodes got at least one, and no node got everything.
645        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        // One node with 10x the free memory should win a disproportionate share
658        // (not necessarily exactly 10x — `score = hash * weight` is an
659        // approximation — but strictly more than its equal-weight siblings).
660        const GB: u64 = 1024 * 1024 * 1024;
661        let heavy_set = vec![
662            node(0x10, GB, 0),      // 1 GB
663            node(0x20, 10 * GB, 0), // 10 GB
664            node(0x30, GB, 0),      // 1 GB
665        ];
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        // skip past the end → None
690        assert_eq!(hrw_select_skip("sess-X", &set, 3), None);
691    }
692
693    #[test]
694    fn hrw_consistent_under_set_shrink_grow() {
695        // Removing a node must not move the sessions that *weren't* on it — the
696        // HRW consistency property. (Sessions on the removed node rebind.)
697        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        // Remove each non-owner and confirm sess-Z's selection is stable.
701        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    // ---- Spread policy ----
720
721    #[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), // fewest
726            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), // tied, more memory
737            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    // ---- SessionAffinity ----
744
745    #[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        // get() renews the lease.
753        assert_eq!(aff.get("s1"), Some(owner));
754        // Let the lease lapse (no renewal for >50ms).
755        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        // get() on an expired binding returns None and drops it.
762        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        // Same owner rebind → no bump.
773        aff.set("s1".to_owned(), ReplicaId::from_bytes([1; 32]));
774        assert_eq!(aff.generation(), g1);
775        // Different owner → bump.
776        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    // ---- CellRouter: Affinity policy ----
801
802    #[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    // ---- CellRouter: Spread policy ----
832
833    #[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), // least loaded
839            node(0x30, 8 * 1024 * 1024 * 1024, 9),
840        ];
841        let now = Instant::now();
842        // Even after a prior placement, Spread must ignore affinity and pick
843        // the least-loaded node.
844        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    // ---- Failure detection: dial-fail → reassign ----
853
854    #[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        // Mark the owner down.
861        let was_new = router.report_dial_fail(p1.replica_id, now);
862        assert!(was_new, "first down-mark must be a transition");
863        // Next placement must rebind to a different node.
864        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        // Idempotent re-report.
874        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        // After the TTL, the node is eligible again.
889        let t1 = t0 + Duration::from_millis(40);
890        // We must clear the session's (now-rebound) binding first, otherwise
891        // affinity would just keep returning the rebound owner.
892        router.release_session("sess-A");
893        let p2 = router.place("sess-A", &set, t1).unwrap();
894        // The recovered node is now eligible; if it wins HRW again, great.
895        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    // ---- Failure detection: token-stream stall ----
917
918    #[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        // Recovery.
935        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    // ---- Heartbeat / release ----
946
947    #[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}