Rust · reconcile to fixed point
Shepherd is a dependency free, Kubernetes style reconciliation control loop in pure Rust. Declare nodes and apps and it schedules pods by resource fit, bin packs to keep the cluster tight, keeps replica counts satisfied, and reschedules pods when a node fails, never overcommitting a node. Deploy an app below, scale it, and kill a node to watch the reconciler restore the desired state, tick by tick.
Shepherd never overcommits a node. It filters feasible nodes, bin packs onto the tightest fit, and loops until observed state equals desired state.
Each card is a node. Bars show CPU and memory utilization; pods are colored by owning app. Failed nodes are dimmed and free their capacity.
Runs fully client-side, nothing leaves the page. The same reconcile-to-fixed-point loop, bin-packing scheduler, and constraint checks as the Rust library.
The provable core is that the reconciler converges and never overcommits a node. Eight randomized property tests in tests/gate.rs enforce it, each rechecking its property from scratch with independent verifiers, and a second file gates rolling updates. The reconciler is a few hundred lines of ordinary Rust with no I/O, no threads, and no randomness beyond one seeded PRNG.
# eight property tests: convergence, capacity invariant, failure recovery # and determinism, constraints, adversarial edges, node rejoins, # the capacity boundary, and idempotence, plus a rollout gate cargo test # crank the randomized sweep as high as you like SHEPHERD_FUZZ_OPS=5000 cargo test --release --test gate
The sum of pod requests bound to any node never exceeds that node's capacity, checked after every single scheduling decision. Killing a node reschedules its pods to restore the desired count on the remaining feasible nodes, and the same seed produces identical placement. No binding ever violates a taint, node selector, affinity or anti-affinity rule. A template roll never dips below replicas - maxUnavailable or exceeds replicas + maxSurge, and a PodDisruptionBudget caps how many pods may be disrupted at once.
Real orchestrators are large distributed systems. Shepherd keeps the same reconcile loop and pulls everything else away, so the core idea is something you can read in an afternoon.
The production reconcile loop. Powerful and battle tested, but enormous, and it needs a live cluster and etcd. The control loop hides behind network calls and stored state, so the converging core is hard to see, test, or fuzz.
A smaller single-binary orchestrator, yet still a real distributed system with servers, clients, and cluster state to stand up before you can watch a single placement decision.
The reconcile-to-fixed-point pattern extracted into a few hundred lines of dependency-free Rust with no I/O, no threads, and no randomness beyond one seeded PRNG. Time is a tick counter you inject and failures are scripted events, so the whole system is a deterministic function you can read, unit test, and fuzz in a fraction of a second.
The primitives that matter
Each is a real piece of the loop, and each is checked from scratch by the randomized property tests.
Create or delete pods and schedule until observed state equals desired, then stop. One more pass at the fixed point changes nothing, so it never oscillates.
Among the feasible nodes the scheduler picks the one with the least room left after placing, keeping the cluster tight, with a deterministic tie-break by node id.
Every controller declares a desired replica count. The reconciler drives the running count to it, creating pods when short and removing them when over.
No binding ever violates a taint, a node selector, or an affinity or anti-affinity rule. Anti-affinity spreads at most one matching replica per node.
When a node fails its pods are marked lost and its capacity is freed. The reconciler reschedules replacements onto the remaining feasible nodes, identically for a given seed.
A PodDisruptionBudget caps how many pods a voluntary eviction may disrupt at once, and a template roll stays within maxUnavailable and maxSurge on the way to the new version.
Run demo for a scripted tour, or converge --seed --nodes --apps to generate a random workload and reconcile it to a fixed point, printing per-node utilization and per-app desired versus observed.
Build a Cluster, add Nodes and a Controller, then call reconcile_to_fixed_point with ScorePolicy::BinPack or LeastLoaded and assert fully_satisfied and verify_capacity.
simulator::Simulator owns the injected clock, the seeded PRNG, and a script of Events. Each step advances one tick, delivers heartbeats, fires due events, detects failed nodes, and reconciles.
tests/gate.rs runs eight randomized property tests and tests/rollout.rs gates rolling updates. Turn up the sweep with SHEPHERD_FUZZ_OPS.
# a scripted tour: nodes join, an app is bin packed, it scales, # a node is killed and its pods reschedule, then the node recovers cargo run --release -- demo # generate a random workload from a seed and reconcile to a fixed point cargo run --release -- converge --seed 7 --nodes 6 --apps 4 cargo test