1use crate::config::{MAX_GATEWAY_AFFINITY_KEY_BYTES, MAX_GATEWAY_WORKER_INFLIGHT};
14use crate::connection::WorkerConnectionKey;
15use crate::registry::CapabilityRegistry;
16use crate::tenant::TenantState;
17use appcore_types::CapabilityName;
18use std::cmp::Ordering;
19use std::collections::HashSet;
20use std::sync::atomic::{AtomicU64, Ordering as AtomicOrdering};
21use std::sync::Arc;
22use std::time::Duration;
23
24#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
29pub enum SelectionPolicy {
30 #[default]
32 FirstAvailable,
33}
34
35#[non_exhaustive]
37#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
38pub enum WorkerSelectionPolicy {
39 #[default]
41 FirstAvailable,
42 RoundRobin,
44 LeastInflight,
46 HealthWeighted,
48 Affinity,
50}
51
52#[derive(Debug, Clone, Copy)]
54pub struct WorkerSelectionInput<'a> {
55 now_ms: u64,
56 heartbeat_timeout: Duration,
57 max_inflight: u64,
58 affinity_key: Option<&'a str>,
59}
60
61impl<'a> WorkerSelectionInput<'a> {
62 pub fn new(now_ms: u64, heartbeat_timeout: Duration) -> Self {
64 Self {
65 now_ms,
66 heartbeat_timeout,
67 max_inflight: MAX_GATEWAY_WORKER_INFLIGHT,
68 affinity_key: None,
69 }
70 }
71
72 pub fn with_max_inflight(mut self, max_inflight: u64) -> Self {
74 self.max_inflight = max_inflight;
75 self
76 }
77
78 pub fn with_affinity(mut self, affinity_key: &'a str) -> Self {
80 self.affinity_key = Some(affinity_key);
81 self
82 }
83}
84
85#[derive(Debug, Clone, Copy, PartialEq, Eq, thiserror::Error)]
87pub enum WorkerSelectionError {
88 #[error("capability has no registered worker")]
90 CapabilityUnavailable,
91 #[error("capability has no healthy worker")]
93 NoHealthyWorker,
94 #[error("all healthy workers are at capacity")]
96 AtCapacity,
97 #[error("affinity policy requires a valid bounded key")]
99 InvalidAffinity,
100 #[error("worker selection limits are invalid")]
102 InvalidLimits,
103}
104
105#[derive(Debug, Clone)]
107pub struct CapabilityResolver {
108 policy: WorkerSelectionPolicy,
109 cursor: Arc<AtomicU64>,
110}
111
112impl Default for CapabilityResolver {
113 fn default() -> Self {
114 Self {
115 policy: WorkerSelectionPolicy::FirstAvailable,
116 cursor: Arc::new(AtomicU64::new(0)),
117 }
118 }
119}
120
121impl CapabilityResolver {
122 pub fn new() -> Self {
124 Self::default()
125 }
126
127 pub fn with_policy(policy: WorkerSelectionPolicy) -> Self {
129 Self {
130 policy,
131 cursor: Arc::new(AtomicU64::new(0)),
132 }
133 }
134
135 pub fn policy(&self) -> WorkerSelectionPolicy {
137 self.policy
138 }
139
140 pub fn resolve(
145 &self,
146 capability: &CapabilityName,
147 registry: &CapabilityRegistry,
148 ) -> Option<WorkerConnectionKey> {
149 let registered = registry.resolve(capability)?;
150 match self.policy {
151 WorkerSelectionPolicy::FirstAvailable
152 | WorkerSelectionPolicy::LeastInflight
153 | WorkerSelectionPolicy::HealthWeighted => registered
154 .iter()
155 .min_by(|left, right| compare_worker_keys(left, right))
156 .cloned(),
157 WorkerSelectionPolicy::RoundRobin => {
158 let mut candidates = registered.iter().collect::<Vec<_>>();
159 candidates.sort_by(|left, right| compare_worker_keys(left, right));
160 if candidates.is_empty() {
161 return None;
162 }
163 Some((*select_cursor(&self.cursor, &candidates)).clone())
164 }
165 WorkerSelectionPolicy::Affinity => None,
166 }
167 }
168
169 pub fn select(
171 &self,
172 capability: &CapabilityName,
173 tenant: &TenantState,
174 input: WorkerSelectionInput<'_>,
175 ) -> Result<WorkerConnectionKey, WorkerSelectionError> {
176 validate_input(self.policy, input)?;
177 let registered = tenant
178 .registry
179 .resolve(capability)
180 .ok_or(WorkerSelectionError::CapabilityUnavailable)?;
181 let candidates = healthy_candidates(registered, tenant, input);
182 let selected = match self.policy {
183 WorkerSelectionPolicy::FirstAvailable => {
184 select_best(candidates, input.max_inflight, |candidate, current| {
185 compare_worker_keys(candidate.key, current.key).is_lt()
186 })?
187 }
188 WorkerSelectionPolicy::LeastInflight => {
189 select_best(candidates, input.max_inflight, |candidate, current| {
190 compare_candidate_load(candidate, current).is_lt()
191 })?
192 }
193 WorkerSelectionPolicy::Affinity => {
194 select_best(candidates, input.max_inflight, |candidate, current| {
195 compare_candidate_affinity(candidate, current, capability, tenant, input)
196 .is_gt()
197 })?
198 }
199 WorkerSelectionPolicy::RoundRobin => self.choose_buffered(
200 candidates,
201 input.max_inflight,
202 BufferedSelectionPolicy::RoundRobin,
203 )?,
204 WorkerSelectionPolicy::HealthWeighted => self.choose_buffered(
205 candidates,
206 input.max_inflight,
207 BufferedSelectionPolicy::HealthWeighted,
208 )?,
209 };
210 Ok(selected.key.clone())
211 }
212
213 fn choose_buffered<'a>(
214 &self,
215 candidates: impl Iterator<Item = Candidate<'a>>,
216 max_inflight: u64,
217 policy: BufferedSelectionPolicy,
218 ) -> Result<Candidate<'a>, WorkerSelectionError> {
219 let mut saw_healthy = false;
220 let mut eligible = Vec::with_capacity(candidates.size_hint().1.unwrap_or(0));
221 for candidate in candidates {
222 saw_healthy = true;
223 if candidate.is_eligible(max_inflight) {
224 eligible.push(candidate);
225 }
226 }
227 if eligible.is_empty() {
228 return Err(empty_selection_error(saw_healthy));
229 }
230 eligible.sort_by(|left, right| compare_worker_keys(left.key, right.key));
231 Ok(match policy {
232 BufferedSelectionPolicy::RoundRobin => *select_cursor(&self.cursor, &eligible),
233 BufferedSelectionPolicy::HealthWeighted => {
234 *select_health_weighted(&self.cursor, &eligible)
235 }
236 })
237 }
238}
239
240fn healthy_candidates<'a>(
241 registered: &'a HashSet<WorkerConnectionKey>,
242 tenant: &'a TenantState,
243 input: WorkerSelectionInput<'_>,
244) -> impl Iterator<Item = Candidate<'a>> + 'a {
245 let now_ms = input.now_ms;
246 let heartbeat_timeout = input.heartbeat_timeout;
247 registered.iter().filter_map(move |key| {
248 if key.tenant_id != tenant.tenant_id {
249 return None;
250 }
251 let worker = tenant.get_worker(&key.installation_id, &key.core_id)?;
252 worker
253 .is_open_and_healthy(now_ms, heartbeat_timeout)
254 .then(|| Candidate::from_worker(worker, now_ms, heartbeat_timeout))
255 })
256}
257
258fn select_best<'a>(
259 candidates: impl Iterator<Item = Candidate<'a>>,
260 max_inflight: u64,
261 is_better: impl Fn(&Candidate<'a>, &Candidate<'a>) -> bool,
262) -> Result<Candidate<'a>, WorkerSelectionError> {
263 let mut saw_healthy = false;
264 let mut selected = None;
265 for candidate in candidates {
266 saw_healthy = true;
267 if !candidate.is_eligible(max_inflight) {
268 continue;
269 }
270 if selected
271 .as_ref()
272 .is_none_or(|current| is_better(&candidate, current))
273 {
274 selected = Some(candidate);
275 }
276 }
277 selected.ok_or_else(|| empty_selection_error(saw_healthy))
278}
279
280fn compare_candidate_load(left: &Candidate<'_>, right: &Candidate<'_>) -> Ordering {
281 left.inflight
282 .cmp(&right.inflight)
283 .then_with(|| left.queue_depth.cmp(&right.queue_depth))
284 .then_with(|| compare_worker_keys(left.key, right.key))
285}
286
287fn compare_candidate_affinity(
288 left: &Candidate<'_>,
289 right: &Candidate<'_>,
290 capability: &CapabilityName,
291 tenant: &TenantState,
292 input: WorkerSelectionInput<'_>,
293) -> Ordering {
294 affinity_score(
295 tenant.tenant_id.as_str(),
296 capability.as_str(),
297 input.affinity_key.unwrap_or_default(),
298 left.key,
299 )
300 .cmp(&affinity_score(
301 tenant.tenant_id.as_str(),
302 capability.as_str(),
303 input.affinity_key.unwrap_or_default(),
304 right.key,
305 ))
306 .then_with(|| compare_worker_keys(right.key, left.key))
307}
308
309fn empty_selection_error(saw_healthy: bool) -> WorkerSelectionError {
310 if saw_healthy {
311 WorkerSelectionError::AtCapacity
312 } else {
313 WorkerSelectionError::NoHealthyWorker
314 }
315}
316
317#[derive(Clone, Copy)]
318enum BufferedSelectionPolicy {
319 RoundRobin,
320 HealthWeighted,
321}
322
323#[derive(Debug, Clone, Copy)]
324struct Candidate<'a> {
325 key: &'a WorkerConnectionKey,
326 inflight: u64,
327 queue_depth: usize,
328 queue_remaining: usize,
329 health_weight: u64,
330}
331
332impl<'a> Candidate<'a> {
333 fn from_worker(
334 worker: &'a crate::WorkerConnection,
335 now_ms: u64,
336 heartbeat_timeout: Duration,
337 ) -> Self {
338 let timeout_ms = duration_ms(heartbeat_timeout);
339 let age_ms = now_ms.saturating_sub(worker.last_heartbeat());
340 let remaining_ms = timeout_ms.saturating_sub(age_ms);
341 let health_weight = 1_u64.saturating_add(
342 remaining_ms
343 .saturating_mul(15)
344 .checked_div(timeout_ms)
345 .unwrap_or(0),
346 );
347 Self {
348 key: &worker.key,
349 inflight: worker.inflight(),
350 queue_depth: worker.outbound_queue_depth(),
351 queue_remaining: worker.outbound_queue_remaining(),
352 health_weight,
353 }
354 }
355
356 fn is_eligible(self, max_inflight: u64) -> bool {
357 self.inflight < max_inflight && self.queue_remaining > 0
358 }
359}
360
361fn validate_input(
362 policy: WorkerSelectionPolicy,
363 input: WorkerSelectionInput<'_>,
364) -> Result<(), WorkerSelectionError> {
365 if input.heartbeat_timeout.is_zero()
366 || input.max_inflight == 0
367 || input.max_inflight > MAX_GATEWAY_WORKER_INFLIGHT
368 {
369 return Err(WorkerSelectionError::InvalidLimits);
370 }
371 if policy == WorkerSelectionPolicy::Affinity {
372 let affinity = input
373 .affinity_key
374 .filter(|value| !value.is_empty())
375 .filter(|value| value.len() <= MAX_GATEWAY_AFFINITY_KEY_BYTES)
376 .filter(|value| !value.chars().any(char::is_control));
377 if affinity.is_none() {
378 return Err(WorkerSelectionError::InvalidAffinity);
379 }
380 }
381 Ok(())
382}
383
384fn select_cursor<'a, T>(cursor: &AtomicU64, candidates: &'a [T]) -> &'a T {
385 let ticket = cursor.fetch_add(1, AtomicOrdering::Relaxed);
386 let index = usize::try_from(ticket).unwrap_or(usize::MAX) % candidates.len();
387 &candidates[index]
388}
389
390fn select_health_weighted<'a, 'worker>(
391 cursor: &AtomicU64,
392 candidates: &'a [Candidate<'worker>],
393) -> &'a Candidate<'worker> {
394 let total = candidates.iter().fold(0_u64, |sum, candidate| {
395 sum.saturating_add(candidate.health_weight)
396 });
397 let mut slot = cursor.fetch_add(1, AtomicOrdering::Relaxed) % total.max(1);
398 for candidate in candidates {
399 if slot < candidate.health_weight {
400 return candidate;
401 }
402 slot = slot.saturating_sub(candidate.health_weight);
403 }
404 &candidates[0]
405}
406
407fn affinity_score(
408 tenant: &str,
409 capability: &str,
410 affinity: &str,
411 worker: &WorkerConnectionKey,
412) -> u64 {
413 let mut hash = 0xcbf2_9ce4_8422_2325_u64;
414 for value in [
415 tenant,
416 capability,
417 affinity,
418 worker.tenant_id.as_str(),
419 worker.installation_id.as_str(),
420 worker.core_id.as_str(),
421 ] {
422 for byte in (value.len() as u64)
423 .to_le_bytes()
424 .iter()
425 .chain(value.as_bytes())
426 {
427 hash ^= u64::from(*byte);
428 hash = hash.wrapping_mul(0x0000_0100_0000_01b3);
429 }
430 }
431 hash
432}
433
434fn compare_worker_keys(left: &WorkerConnectionKey, right: &WorkerConnectionKey) -> Ordering {
435 left.tenant_id
436 .as_str()
437 .cmp(right.tenant_id.as_str())
438 .then_with(|| {
439 left.installation_id
440 .as_str()
441 .cmp(right.installation_id.as_str())
442 })
443 .then_with(|| left.core_id.as_str().cmp(right.core_id.as_str()))
444}
445
446fn duration_ms(duration: Duration) -> u64 {
447 u64::try_from(duration.as_millis()).unwrap_or(u64::MAX)
448}
449
450#[cfg(test)]
451#[path = "resolver_tests.rs"]
452mod tests;