Decisions Made

Storage -> SQLite

SQLite provides a lot of value for this use case. The single-writer model with conditional UPDATE statements lets me atomically check capacity and reserve resources in one operation, preventing race conditions during concurrent placement. Additionally, with the right table structure, the bulk of the placement strategy can be done in a SQL query, which prevents me from having to implement multi-dimensional sorting and filtering in code.

Placement Strategy

This is where I had a lot of fun.

I chose best fit as my placement strategy. Since machines are placed on-demand as customers create and destroy them, I want to keep the largest contiguous block of resources available to satisfy future requests. The tradeoff of load not being evenly spread out is worth being able to fulfill more requests over time.

This is especially useful in heterogeneous fleets where we have hosts of different sizes. In my mind, if we had a fresh fleet with:

Host 1 | 4 CPU | 4GB RAM
Host 2 | 4 CPU | 4GB RAM
Host 3 | 8 CPU | 8GB RAM

If we were to somehow place a machine needing 1 CPU and 1GB RAM on Host 3, when it fits on Host 1 or 2, we now can't fulfill a request for 4 CPU and 8GB RAM.

This strategy is still useful in homogeneous fleets as well, since the available resources will change over time as customers use the platform. The strategy of maintaining the largest box free as much as possible allows us to make the best use of available resources.

Breaking ties

For the reasons listed above, I also went with the tightest fit when it came to breaking ties between hosts where the usage ratio would be the same if we simply added up the requested resources.

On an empty fleet of:

Host 1 | 4 CPU | 4GB RAM | 100GB Disk
Host 2 | 8 CPU | 8GB RAM | 100GB Disk

A machine requiring 1 CPU, 1GB RAM, and 40GB disk, should always be placed on Host 1.

To rank hosts, I score each one by the average utilization ratio across all dimensions after placement:

(cpu_ratio + mem_ratio + disk_ratio) / 3

The host with the highest average score is the tightest fit.

For the example above, placing 1 CPU / 1 GB / 40 GB on empty hosts:

• Host 1: (1/4 + 1024/4096 + 40/100) / 3 = 0.30
• Host 2: (1/8 + 1024/8192 + 40/100) / 3 = 0.22

Host 1 wins — the machine consumes a larger fraction of its total resources. An earlier version of this code used MAX across dimensions instead of the average, which broke down when two hosts shared the same bottleneck (e.g., identical disk sizes). The sum/average captures the overall fit rather than just the single worst dimension.

Respecting capacity

This is one of the main reasons I went with SQLite. The conditional UPDATE in TryReserveAndAssign checks capacity constraints in the WHERE clause — if two placements race for the last slot, only one succeeds. The loser falls through to the next candidate host.

This is also the reason why I rank the hosts and loop through them instead of just picking one and rejecting the machine if it fails.

Overcommit early

I went back and forth on this a little bit. The current implementation will prefer to overcommit if it's the tightest fit. I tried out preferring real physical resource availability before overcommitting, but then realized it goes against my original intent of leaving the largest possible block of resources open for as long as we can.

So in the scenario where we have:

Host 1 | 4 CPU | 4GB RAM
Host 2 | 4 CPU | 4GB RAM

And

Machine 1 | 1 CPU | 0.5GB RAM
Machine 2 | 1 CPU | 0.5GB RAM
Machine 3 | 1 CPU | 0.5GB RAM
Machine 4 | 1 CPU | 0.5GB RAM
Machine 5 | 1 CPU | 0.5GB RAM
Machine 6 | 1 CPU | 0.5GB RAM
Machine 7 | 6 CPU | 4GB RAM

With a 1.5 allowed cpu overcommit, the placement strategy will fill up one host with all the small machines, so that the larger one can be placed on the second host.

Units Used

Didn't over complicate it.

• CPU: Cores
• Memory: MiB
• Disk: GiB

Machine Lifecycle

scheduling → scheduled → creating → starting → running ⇄ stopped
     ↓                                            |           |
  rejected                                        +-----------+--→ terminated

Placement is a first-class FSM state, not a helper function called from the side. A machine enters scheduling, the placer finds a host and atomically reserves capacity, and the machine moves to scheduled. If no host has room, it transitions to rejected.

Stopped machines hold their resources and host assignment — only terminate releases capacity. This means a stopped machine can be restarted without rerunning placement.

Crash recovery

Each lifecycle operation (create, start, stop, terminate) is its own FSM pipeline. If the process crashes mid-pipeline, the FSM resumes from the last persisted state on the next startup. Handlers are idempotent — they re-read state from the database and guard on the current state before advancing, so retries after a crash are safe.

Smaller Decisions

• The ranking query is a string literal instead of a sqlc generated method. I ran into issues with how sqlc was handling the dynamic parameters.

Running the solution

Requires Go 1.23+ and make. GCC is needed to compile the FSMv2 library.

If you have devenv set up, I've already included all the dependencies.

Copy the example configs to get started:

cp config.example.json config.json
cp fleet.example.json fleet.json

Or

make config

config.json

You can configure over-commit ratios for each resource here.

fleet.json

The fleet we're testing on.

Testing batches

You can copy batch.example.json to a file like batch.json and use it with make batch FILE=batch.json.

Quick start

make init                                          # Initialize fleet from config
make place CPU=2 MEM=1024 DISK=10                  # Place a single machine
make list                                          # Show hosts and machines
make stop ID=<machine-id>                          # Stop a running machine
make start ID=<machine-id>                         # Restart a stopped machine
make terminate ID=<machine-id>                     # Terminate and free resources
make batch FILE=batch.json                         # Place multiple machines concurrently
make recover                                       # Resume any crashed FSM pipelines
make test                                          # Run integration tests
make clean                                         # Wipe all state

Simulating crashes

To test crash recovery, create a file called crash at the repo root before placing a machine:

touch crash
make place CPU=1 MEM=512 DISK=10    # process will exit mid-pipeline
make recover                         # resumes from last persisted state
make list                            # machine should be running

The create pipeline checks for the crash file at each step. If the file exists, each step has a 50/50 chance of crashing — except the last step, which always crashes if it hasn't happened yet. The file is removed on crash, so recovery runs cleanly. This lets you verify that idempotent handlers and FSM resume work correctly regardless of where the crash occurs.

Without make

mkdir -p storage
go run ./cmd/wing init -fleet fleet.json -config config.json
go run ./cmd/wing place -cpu 2 -mem 1024 -disk 10
go run ./cmd/wing list
go test ./internal/orchestrator/ -v