Skip to content

armgit / orca

Public Imported from GitHub
0

Orca is the place for working with a fleet of agents (e.g. Grok Bot, Claude Code). Run any coding agent with your own subscription. Available on desktop, mobile and remote runtime.

9.0 KB
Raw Blame
import type { RelayRegion } from '@orca-cloud/relay-contract'
import { CELL_INTAKE_BURST, CELL_RESERVE_TTL_MS, type ReserveOutcome } from './cell-reserve-contract.js'

// Directors estimate/pick from their own maps; cells decide bookings. Simulation drives this same pure logic.

export const RESERVE_MAX_TRIES = 3
// A cell not polled this recently is not a candidate (unverifiable, never gone).
export const RESERVE_CELL_FRESH_MS = 3_000
// Each director estimates 1/5 of intake; fewer under-use budget, more only cause refusals.
export const RESERVE_DIRECTOR_SHARE = 5
export const RESERVE_PACE_MIN_SECONDS = 1
export const RESERVE_PACE_MAX_SECONDS = 10

export type PlacementCell = {
  cellId: string
  region: RelayRegion
  // The cell reports admitMode=reserve as applied.
  reserve: boolean
  general: boolean
  draining: boolean
  // When this director last sent a poll that the cell answered; null if never.
  polledAt: number | null
  seats: number
  bookings: number
  // Cell-reported placement ceiling; undefined from a cell that predates step 5.
  ceiling?: number
  intakePerSec: number
  intakeTokens: number
}

export type ReserveAttempt = ReserveOutcome | { outcome: 'unreachable' } | { outcome: string }

export type PlacementResult =
  | { kind: 'placed'; cellId: string; epoch: number; calls: number }
  // No reserve cell said yes: the caller runs today's database path.
  | { kind: 'database'; calls: number }
  // Reserve cells have seats but no intake budget: 503 with this Retry-After.
  | { kind: 'pace'; retryAfterSeconds: number; calls: number }

type Estimate = { tokens: number; refilledAt: number; ownBookings: number[] }

export class ReservePlacer {
  private readonly estimates = new Map<string, Estimate>()

  constructor(
    private readonly now: () => number = Date.now,
    private readonly random: () => number = Math.random,
    private readonly share = RESERVE_DIRECTOR_SHARE
  ) {}

  isCandidate(cell: PlacementCell, region: RelayRegion, now = this.now()): boolean {
    return (
      cell.reserve &&
      cell.region === region &&
      cell.general &&
      !cell.draining &&
      cell.ceiling !== undefined &&
      cell.polledAt !== null &&
      now - cell.polledAt <= RESERVE_CELL_FRESH_MS
    )
  }

  load(cell: PlacementCell): number {
    return cell.seats + cell.bookings + this.ownBookingsSince(cell)
  }

  free(cell: PlacementCell): number {
    return cell.ceiling === undefined ? 0 : Math.max(0, cell.ceiling - this.load(cell))
  }

  hasSeat(cell: PlacementCell): boolean {
    return cell.ceiling !== undefined && this.load(cell) < cell.ceiling
  }

  hasBudget(cell: PlacementCell, now = this.now()): boolean {
    return this.refill(cell, now).tokens >= 1
  }

  // Power of two choices over cells with an estimated seat and budget.
  pick(cells: readonly PlacementCell[], region: RelayRegion, tried: ReadonlySet<string>) {
    const now = this.now()
    const candidates = cells.filter(
      (cell) =>
        !tried.has(cell.cellId) &&
        this.isCandidate(cell, region, now) &&
        this.hasSeat(cell) &&
        this.hasBudget(cell, now)
    )
    if (candidates.length === 0) return null
    const first = candidates[Math.floor(this.random() * candidates.length)]!
    if (candidates.length === 1) return first
    let second = candidates[Math.floor(this.random() * (candidates.length - 1))]!
    if (second === first) second = candidates[candidates.length - 1]!
    const ratio = (cell: PlacementCell) => this.load(cell) / cell.ceiling!
    return ratio(second) < ratio(first) ? second : first
  }

  async place(input: {
    cells: readonly PlacementCell[]
    region: RelayRegion
    // Above every epoch this director knows for the host.
    epoch: number
    reserve: (cellId: string, epoch: number) => Promise<ReserveAttempt>
    // The database lane found the region full: a throttled reserve cell paces instead.
    regionFull?: boolean
  }): Promise<PlacementResult> {
    const tried = new Set<string>()
    // Refused for a reason other than intake: no seat to wait for this time.
    const refused = new Set<string>()
    let epoch = input.epoch
    let calls = 0
    while (calls < RESERVE_MAX_TRIES) {
      const cell = this.pick(input.cells, input.region, tried)
      if (!cell) break
      tried.add(cell.cellId)
      const countedAt = this.countBooking(cell)
      calls += 1
      const answer = await input.reserve(cell.cellId, epoch)
      if (answer.outcome === 'ok') return { kind: 'placed', cellId: cell.cellId, epoch, calls }
      this.uncountBooking(cell, countedAt)
      if (answer.outcome === 'intake') this.drain(cell)
      else refused.add(cell.cellId)
      if (answer.outcome === 'seated-newer' && 'epoch' in answer && typeof answer.epoch === 'number') {
        epoch = Math.max(epoch, answer.epoch + 1)
      }
    }
    return this.fallback(input.cells, input.region, calls, { regionFull: input.regionFull, refused })
  }

  // Try regional DB cells before pacing budget-only reserve shortages; otherwise database placement may spill.
  fallback(
    cells: readonly PlacementCell[],
    region: RelayRegion,
    calls: number,
    options: { regionFull?: boolean; refused?: ReadonlySet<string> } = {}
  ): PlacementResult {
    const now = this.now()
    const databaseCells =
      !options.regionFull &&
      cells.some((cell) => !cell.reserve && cell.region === region && cell.general && !cell.draining)
    if (databaseCells) return { kind: 'database', calls }
    let refillMs: number | null = null
    for (const cell of cells) {
      if (options.refused?.has(cell.cellId)) continue
      if (!this.isCandidate(cell, region, now) || !this.hasSeat(cell)) continue
      const estimate = this.refill(cell, now)
      const rate = this.ratePerSec(cell)
      if (rate <= 0) continue
      const waitMs = (Math.max(0, 1 - estimate.tokens) / rate) * 1_000
      refillMs = refillMs === null ? waitMs : Math.min(refillMs, waitMs)
    }
    if (refillMs === null) return { kind: 'database', calls }
    const seconds = Math.ceil(refillMs / 1_000)
    return {
      kind: 'pace',
      retryAfterSeconds: Math.min(RESERVE_PACE_MAX_SECONDS, Math.max(RESERVE_PACE_MIN_SECONDS, seconds)),
      calls
    }
  }

  // Without every regional DB cell’s ceiling, return zero share to avoid accidentally placing only on reserve cells.
  reservePoolShare(cells: readonly PlacementCell[], region: RelayRegion): number {
    const now = this.now()
    let reserveFree = 0
    let databaseFree = 0
    for (const cell of cells) {
      if (cell.region !== region || !cell.general || cell.draining) continue
      if (cell.reserve) {
        if (this.isCandidate(cell, region, now)) {
          reserveFree += this.free(cell)
        }
        continue
      }
      if (cell.ceiling === undefined) return 0
      databaseFree += Math.max(0, cell.ceiling - cell.seats)
    }
    const total = reserveFree + databaseFree
    return total === 0 ? 0 : reserveFree / total
  }

  private ratePerSec(cell: PlacementCell): number {
    return cell.intakePerSec / this.share
  }

  private burst(): number {
    return Math.max(1, CELL_INTAKE_BURST / this.share)
  }

  private refill(cell: PlacementCell, now: number): Estimate {
    let estimate = this.estimates.get(cell.cellId)
    if (!estimate) {
      // A restarted director starts empty and refills, so it cannot burst on top of the others.
      estimate = { tokens: 0, refilledAt: now, ownBookings: [] }
      this.estimates.set(cell.cellId, estimate)
    }
    const elapsed = Math.max(0, now - estimate.refilledAt) / 1_000
    estimate.tokens = Math.min(this.burst(), estimate.tokens + elapsed * this.ratePerSec(cell))
    estimate.refilledAt = now
    return estimate
  }

  private ownBookingsSince(cell: PlacementCell): number {
    const estimate = this.estimates.get(cell.cellId)
    if (!estimate) return 0
    const now = this.now()
    const since = cell.polledAt ?? -Infinity
    return estimate.ownBookings.filter((at) => at >= since && at > now - CELL_RESERVE_TTL_MS)
      .length
  }

  // Remember exact added entry so refusal cannot undo another concurrent call’s booking.
  private countBooking(cell: PlacementCell): number {
    const estimate = this.refill(cell, this.now())
    estimate.tokens = Math.max(0, estimate.tokens - 1)
    const at = this.now()
    estimate.ownBookings.push(at)
    if (estimate.ownBookings.length > 1_000) estimate.ownBookings.shift()
    return at
  }

  // A refusal other than `intake` spent no token on the cell.
  private uncountBooking(cell: PlacementCell, at: number): void {
    const estimate = this.refill(cell, this.now())
    // A poll may already have dropped it; then there is nothing of this call's to remove.
    const index = estimate.ownBookings.lastIndexOf(at)
    if (index >= 0) estimate.ownBookings.splice(index, 1)
    estimate.tokens = Math.min(this.burst(), estimate.tokens + 1)
  }

  private drain(cell: PlacementCell): void {
    this.refill(cell, this.now()).tokens = 0
  }
}

export function mintEpoch(knownEpochs: Iterable<number>): number {
  let highest = 0
  for (const epoch of knownEpochs) highest = Math.max(highest, epoch)
  return highest + 1
}