Governor: A Resource Governor for Workloads That Fan Out

An agent spawns sub-agents. A crawler follows every link it finds. A job retries at three layers, and each layer thinks it is the only one retrying. In all three, one request quietly becomes hundreds, and the thing that pays for it is a shared database or an API with a rate limit.

A rate limiter does not fix this. It answers "how many per second for this key". The question here is different: may this piece of work proceed, given everything above it? Above it is the task that spawned it, the tenant that owns the task, and the pools every tenant shares.

Governor is my answer to that question. It is a small Go daemon, governord, plus an SDK. It does not run any work. It only decides how much work a tree of tasks may create, and it keeps deciding correctly when workers crash, when it crashes itself, and when one tenant queues ten thousand jobs in front of another.

This post is the whole design in one place: what it does, how each part works, why I chose each trade-off, how I know it is correct, and where it stops.

The same workload without and with Governor. The numbers at the end are from the benchmark below.

The short version#

Governor answers three questions, and it answers them the same way for a task, its subtasks and the tenant that owns them:

The facts worth knowing before the details:

• One daemon is the authority. The whole tree lives in its memory, behind one lock.
• Every change is an event, committed to Postgres or SQLite before the caller gets a reply.
• A restart rebuilds the tree from the newest snapshot and the events after it. Nothing a caller was told is lost.
• Lease ids are fencing tokens, so a downstream system can refuse a worker whose lease has expired.
• Tenants share queued capacity by weight, whatever the length of their queues.
• It is not replicated. I explain below exactly what would break if it were replicated the easy way.

Three numbers, measured on an Apple M1:

The model: a tree#

Everything is a node in one tree: the root, a tenant, a task, a subtask.

Two rules about this tree shape the rest of the design.

A limit is a cap, not a reservation. Creating a child sets nothing aside from its parent. A child with a cap of 100 under a parent with 150 left does not reduce what its siblings may use. Each consume is checked against every ancestor at the moment it happens.

This has a cost and I want to state it: a cap is not a guarantee. A child with a cap of 100 can be refused at 10 because a sibling spent the parent's budget. What it buys is that unused budget is never stranded in a child that finished early, and that there are no balances to move between nodes.

Quota is never refunded. A request that was sent stays sent. Leases come back; budgets do not.

Charging a whole chain in one step#

A consume must fit under the task's cap, its parent's, its tenant's and the root's. It must be applied to all of them or to none.

The engine does this the plain way. It has one mutex. Under it, check walks from the node to the root and returns a denial if any cap would be exceeded. Only if every node passes does charge walk the chain again and add to each one.

// check reports the denial if amount more of r would not fit on n's whole chain.
func (n *node) check(r Resource, amount int64) error {
	for a := n; a != nil; a = a.parent {
		if limit, ok := a.quota[r]; ok && amount > limit-a.used[r] {
			return a.denied(r, amount, limit)
		}
	}
	return nil
}

No other operation can run between the two walks, so there is no partial state and nothing to roll back. One event records the whole charge. A denial names the cap that was hit and its largest consumer, so the caller learns who spent the budget and not only that it is gone.

Why one lock, and not a lock per node#

This is the first thing a reviewer questions, so here is the argument.

Every operation needs its whole chain, and every chain ends at the root. With a lock per node I would take them leaf to root in a fixed order, and the root's lock would still be taken by every operation in the process. The contention point does not go away. What I would lose is the simple argument above.

I measured before deciding. A consume takes about 390 ns under contention on eight cores, so the lock allows roughly 2.5 million operations per second. The network call around it costs about 100 µs and the commit about a millisecond. The lock is two to three orders of magnitude away from being the bottleneck.

The real ceiling is the commit: 6,600 consumes per second with Postgres against 66,000 in memory. If I needed more, I would do these in order:

1. Let a client reserve a block of budget in one call and spend it locally, returning the rest. That trades precision for far fewer round trips.
2. Shard by tenant. Tenants only share the root, so each tenant's subtree could live in its own engine, with the root's pools divided between them.

I would not start with finer locking, because the measurement says it is not the problem.

Lowering a cap below what is used#

Nothing is taken back. For a quota, usage stays above the cap and every further consume through that node is denied. For a concurrency limit, no lease is revoked; grants through that node stop until enough leases are returned. So the invariant is stated as "no consume takes a node over a cap", not "usage never exceeds the cap".

The parts#

The engine does no I/O at all. It takes a clock and a sink for events as inputs. That one decision is what makes the testing later possible: the whole engine can be driven by a random sequence of operations with a fake clock, deterministically.

For a worker, using it looks like this:

client, err := governor.Dial(ctx)
if err != nil {
	return err
}
defer client.Close()
 
// The context is cancelled when the task ends, for any reason.
ctx, task, err := client.NewTask(ctx, governor.Spec{
	Name:     "crawl-site",
	Quotas:   map[string]int64{"http": 500, "retry": 20},
	Deadline: time.Now().Add(10 * time.Minute),
})
if err != nil {
	return err
}
defer task.Close()
 
// One "http" unit and one "http" lease per request.
httpClient := &http.Client{Transport: governor.Transport(nil)}
 
// Fan-out: each function is a subtask that waits for an "agents" lease.
g, ctx := governor.NewGroup(ctx, governor.ClassAgents)
for _, page := range pages {
	g.Go(governor.Spec{Name: page.URL}, func(ctx context.Context) error { return crawl(ctx, page) })
}
err = g.Wait()

The context.Context carries the task, so library code deep in the call stack needs no handle to be governed.

Leases that survive a dead worker#

A lease is one slot of a concurrency limit. The hard part of a lease is not granting it. It is getting it back when its holder dies without saying so.

Every lease belongs to a session, and a session has a TTL. The SDK heartbeats three times per TTL. When a worker dies, the heartbeats stop, the session lapses, and every lease it held ends. The freed slots go to whoever is waiting.

Two details matter here:

• Expiry is checked lazily as well as on a timer. A background reaper ends expired sessions every interval, but any call that touches an expired session or lease also ends it on the spot. Correctness does not depend on the reaper's timing; only promptness does.
• An ended lease leaves a tombstone for one minute, recording how it ended. A second release of a released lease is a no-op. A release of a lease that expired returns that fact as an error, so the worker learns its work ran without cover.

In the benchmark, a worker dies holding all four slots on a one second session. Another tenant gets the pool after 1,009 ms, and all four late releases by the dead worker are refused.

Why a TTL is not enough#

A TTL tells the server when to give the capacity to someone else. It cannot stop the old holder.

A worker can be paused for longer than its TTL: a long garbage collection, a suspended VM, a closed laptop lid. It wakes up still believing it holds the lease. It cannot detect this with its own timer, because its timer was not running either.

So the check has to sit where the work lands. Lease ids come from one counter that only grows and is never reissued, which makes a larger id a later grant. The downstream has two options, in order of strength:

1. Remember the largest lease id it has seen and refuse anything smaller. This needs no call to Governor and closes the gap completely.
2. Call Validate(lease) before irreversible work. This is weaker, because the lease can expire between the check and the work.

If the downstream does neither, Governor still rejects every later call from the stale worker, and the SDK cancels the worker's contexts at a local deadline. But one operation by a paused worker can slip through. Governor cannot stop a paused process from trying, and the spec says so.

The SDK's local deadline#

The client gives up its session at 80% of the TTL after the last heartbeat that succeeded, and it measures from the moment that heartbeat was sent, not when the reply arrived.

Measuring from the send time is the safe side. The server renewed the session at some point after that, so the client's deadline is always earlier than the server's. The 20% margin covers clock drift and work that is slow to notice its context was cancelled. Go's timers use the monotonic clock, so a wall-clock jump does not move the deadline.

Sharing a pool between tenants#

When a pool is full, acquires wait. Who gets the next free slot is where the noisy neighbour problem lives. First come, first served hands everything to whoever queued first and most.

Governor keeps one queue per tenant for each class of lease and serves the tenants in a ring by weighted deficit round robin. When a tenant's turn comes it gets up to weight grants, then the cursor moves on.

What this guarantees, while tenants have waiters that fit:

• Grants are shared in proportion to weights, whatever the queue lengths. A tenant with 10,000 waiters and one with 2, at equal weight, alternate.
• A tenant waits at most one round: the sum of the other tenants' weights, in grants.
• The queue is work conserving. No acquire is left waiting when it would fit.

What it does not guarantee, and I would rather say it first than be asked:

1. Fairness inside a tenant. Priority there is strict. A steady stream of high-priority tasks starves the same tenant's low-priority tasks.
2. Fairness of time held. The queue counts grants, not how long a lease is kept. A tenant that holds each lease ten times longer occupies ten times more of the pool.
3. Credit for the past. A tenant that is skipped because none of its waiters fitted loses the rest of its round and is not repaid.

Why "work conserving" is not automatic#

Limits sit on every level of the tree. The waiter at the head of a tenant's queue may be blocked only by its own task's cap, while the waiter behind it, in another task, would fit. A strict head-of-line queue would stall behind the first one.

So the dispatcher takes the tenant's first waiter that fits, and skips a tenant whose own cap is full:

func (q *classQueue) pick(class Class) (int, *waiter) {
	for i := range q.ring {
		idx := (q.cursor + i) % len(q.ring)
		tq := q.ring[idx]
		w := tq.firstFit(class)
		if w == nil {
			continue
		}
		// Tenants passed over on the way forfeit the rest of their round.
		for j := range i {
			q.ring[(q.cursor+j)%len(q.ring)].deficit = 0
		}
		return idx, w
	}
	return 0, nil
}

Why deficit round robin#

Weighted fair queueing with virtual time gives tighter bounds, but it needs a cost per request and a priority queue. Here every grant costs exactly one slot. Deficit round robin gives the same proportional share with constant work per grant and state that is one integer per tenant.

To fix the second gap above I would charge the deficit by time held instead of by grant. That needs the hold time, which is only known at release.

A waiter that gives up at the moment it is granted#

The wait happens outside the lock, so there is a race: the caller's context can end at the same instant a grant arrives. The waiter has a buffered channel that receives exactly one result. If the context ends, the waiter takes the lock again and looks. If nothing was sent, it removes itself from the queue. If a grant raced in first, it releases that lease straight away and runs the dispatcher, so the slot goes to the next waiter. No lease is leaked either way.

Limits that follow the downstream#

A fixed concurrency limit is a guess about someone else's capacity. When the downstream loses capacity mid-run, the guess is wrong and every extra request makes things worse.

Each released lease reports its latency and whether the downstream signalled overload. Every interval a controller looks at the reports:

• If the p95 latency is over the target, or the share of overloaded calls is too high, the limit is multiplied by 0.7.
• Otherwise it goes up by one.
• With too few samples it does not move.

This is additive increase, multiplicative decrease, the same shape as TCP congestion control, and for the same reason: back off fast, probe slowly. Lowering the limit revokes nothing; grants stop until enough leases come back.

In the benchmark, the downstream's capacity falls from 20 to 5. The fixed limit sheds 4,781 requests afterwards and serves 204. The adaptive one sheds 294 and serves 602. It still sheds some because it keeps probing upward, and a limit that never probes never recovers.

A retry budget instead of retry counts#

Retries multiply across layers. Three nested loops of three attempts make 27 requests for one call, and each layer is behaving reasonably by its own rules.

In Governor, retry is an ordinary quota. Every retry at any layer consumes one unit from its node, and so from the whole chain. The first attempt is free. When the budget is gone the last error is returned at once. The total is bounded by the budget, not by the product of the attempt counts.

Measured with the downstream fully down: 27 requests per call without, 2 with.

Durability: nothing a caller was told is lost#

The tree lives in memory. The database is an append-only record of events, each with a sequence number. Four rules make a crash safe.

1. Write before reply#

The order matters and is easy to get subtly wrong:

1. Under the engine's lock: check, apply in memory, emit the event with the next sequence number. The store only appends it to a pending list. It never touches the database while the lock is held.
2. Outside the lock: the handler waits until the store has committed everything up to that sequence number.
3. Only then reply.

So memory can be ahead of the record, but no caller is ever ahead of the record.

"But another caller can see state that is not committed yet." It can, and it is still safe, because the record is always a prefix of what happened. Events get their sequence numbers under one lock and are written in that order. Take a release (event 10) followed by a grant of the freed slot (event 11). The second caller's reply waits for event 11, and event 11 cannot be on record without event 10. Any answer that depended on an earlier change is only delivered once that earlier change is durable too.

The one visible effect is conservative: a consume can be denied because of a charge that is then lost in a crash. That is a refusal the caller retries, never an over-spend.

2. Group commit#

A commit per request would be slow. One writer goroutine takes everything pending and commits it as one transaction. While that transaction is in flight, new events pile up and become the next batch. The batch size grows by itself with load. One caller pays about 1.2 ms per call; sixteen callers together get 6,600 calls per second instead of about 830.

3. A failed commit stops the process#

After a failed commit the engine holds changes that are not on record, and a restart would lose them. Serving from that state would mean handing out answers that can be un-happened. So the store signals failure, the daemon stops the gRPC server at once, and a supervisor restarts it from the record.

I chose crash over rollback because rollback would mean undoing in-memory state that later operations have already built on. Restart is the one recovery path, and it is the one that is tested most.

4. Restart is replay#

Snapshots keep the restart short. When enough events have accumulated, the engine captures its whole state under the lock, and the store saves it and deletes the events it covers in one transaction. There is never a snapshot with a hole after it.

Two more decisions in this path:

Heartbeats are not recorded. They are the most frequent call, and writing each one would dominate the load. The price is that a restart cannot know which sessions were alive. Ending them all would punish every healthy worker for the server's restart, so each gets one fresh TTL to reconnect. A dead worker's leases are held for at most one extra TTL. That is a bounded delay in reclaiming capacity, not a safety problem: no capacity is given out twice.

Session tokens are stored as SHA-256 hashes. Reading the database does not give anyone a usable token, and it is also how a connected worker keeps its session across the restart.

The reply was lost. Was I charged?#

A caller whose request succeeded but whose reply was lost will retry. To avoid charging twice, the caller sends a request id and retries with the same id. There are two layers:

• In the engine, durable. The id is stored inside the event it caused. Each session remembers what its last 1,024 ids did, and that memory is rebuilt on replay. A retry, even after a restart, returns the original result and applies nothing.
• In the server, in memory. This handles a retry that arrives while the first attempt is still running: the retry waits for it and gets the same answer.

An id reused with different arguments is an error, not a silent wrong answer.

Can a lease id be issued twice after a crash?#

Only an id that no caller ever saw. After a restart the counter is restored as the largest id on record. An id handed out in memory whose event was not committed can be handed out again. But write before reply means the first holder was never told about it, so from outside the id was issued once. This is exactly the property that naive replication breaks, further down.

The API, isolation and encryption#

Everything talks to governord over one gRPC service of about sixteen calls: sessions, nodes, Consume, Acquire, Release, Validate, and edits to caps. gRPC fits for three reasons: a worker calls before almost every piece of work so the call must be cheap, the contract is checked by the compiler on both sides, and a waiting Acquire needs a long-lived call with clean cancellation.

Authentication. A tenant's API key opens a session and returns a random token; later calls carry the token.

Isolation. A session is confined to a scope, which for an API key is the tenant's node. Every operation resolves its target through one function that checks the node lies inside the session's subtree. Node ids are small integers and easy to guess, so nothing relies on them being secret. A worker for tenant A that names tenant B's node gets PermissionDenied.

Who may change a cap. A session may change any node in its scope except the scope node itself. A tenant can re-divide its own budget among its tasks but cannot raise the cap the operator gave it.

Errors are standard status codes, which the SDK turns back into Go errors:

Encryption. governord serves TLS 1.3 when its configuration names a certificate. Because every call carries a key or a token, it refuses to start on an address that is not loopback without TLS, unless the operator sets allow_plaintext: true. The server proves itself with the certificate and a client with its key, so there are no client certificates.

Failing closed. If a client cannot reach governord, new work is denied, and work holding a lease stops at the session's local deadline. Failing open would make the governor optional exactly when the system is under most stress. The cost is that governord is a single point of failure for admission.

Seeing what it is doing#

governord serves Prometheus metrics: calls by method and status code, events by kind, queue depth per pool, how full each pool is, what each tenant has spent, commit duration and batch size.

One rule shaped the metrics: labels are tenants, classes and resources only, never a task. The number of series grows with the configuration and not with the work, so a million tasks do not become a million series. The tree is read once per scrape, and only the root and the tenants are read.

Five minutes of two tenants against an adaptive db pool. The sawtooth is the limit probing upward and being cut.

How I know it is correct#

The spec states nine invariants. They are what "correct" means here.

The test that checks them is randomized: 40 seeds, 1,500 random operations each. Create, consume, acquire, release, cancel, close, open and expire sessions, advance the clock, change caps and defaults, and make calls outside the scope on purpose.

The invariants are checked after every step. Six are recomputed from scratch from the engine's state. Three (I1, I4, I5) are checked by an auditor on each event as it is emitted, because they are statements about transitions and not about states.

Then each history is replayed through the restart path three ways:

1. from events only,
2. from a mid-run snapshot plus the later events,
3. from a final snapshot.

Each result is compared field by field with the live engine. This is what "replay is the same code path as a snapshot" means in practice.

The clock is injected, so time-dependent behaviour is deterministic and a failing seed reproduces exactly.

Would the test catch a bug? I broke the code on purpose and checked that it failed. Removing the "cannot edit your own scope" check, ignoring the "no cap" value, and dropping the replay of a defaults change were each caught. A test that has never failed has not shown it can.

What is not tested, so nobody assumes it is:

• No fault injection on the network between client and server.
• No linearizability checker. The engine is linearizable for one process, because every operation takes effect at one point while holding the lock, but the evidence is invariants, not a checker.
• No long soak test, and no slow or flapping database beyond a commit that fails outright.

What it measures#

govbench runs the same workload with and without Governor against a simulated downstream, then breaks things on purpose.

And the failures:

How to read these:

• The downstream is simulated. The numbers show how Governor behaves, not how a production system performs.
• Timings vary between runs, counts do not. Durable throughput ranged from 3,600 to 7,200 per second across three runs on a machine that was also running Docker. I report the middle one.
• A call in flight when governord stops can be on record without having been acknowledged. It is never the other way round.

Why not something simpler#

Why not Redis or a rate limiter library? A rate limiter answers "how many per second, for this key". Governor checks a charge against every ancestor at once, spends budgets instead of refilling them, reclaims leases when their holder dies, and shares the wait fairly. Pieces of this can be built on Redis with Lua scripts, but the atomic check across a chain and the recovery story are the hard parts, and they would still be mine to write.

Why keep state in memory and not query the database on each call? Every operation reads a chain of nodes and may reorder a queue. In memory that is a few hundred nanoseconds under one lock. In SQL it is a multi-row transaction with a lock on the hot root row for every call. Keeping the state in memory and using the database as an append-only record gives one writer, sequential writes and group commit. The cost is that the state must fit in memory and that a restart needs replay, which snapshots bound.

Why both Postgres and SQLite? The store only needs an ordered log, a snapshot row and a table of token hashes. SQLite makes Governor usable on one machine with no other process; Postgres is for when governord serves several machines.

What breaks if it is replicated the easy way#

There is one governord on purpose. Every guarantee above is a statement about one ordered history: this consume came before that one, this lease was granted after that one ended. One process with one lock gives that order for free.

Each obvious way of adding a second one breaks a guarantee:

The second row is the one worth walking through:

Why not put the events in Kafka, or let Postgres replication do it? Both give a durable, replicated log. Neither makes the decision. Governor does not only record "charged 5". It decides "is there room? then charge". The check and the append must be one step by one authority. With Kafka, two daemons can both read "1 left" and both append a charge. With Postgres synchronous replication the record survives, but something still has to ensure that only one governord is deciding and to fence off the old one. That election and fencing is the problem consensus solves.

A correct version needs a consensus log such as Raft: one leader, and an event counts only once a majority has stored it. Governor is already shaped for it:

The hard parts are the interesting ones. Expiry must become an entry in the log decided by the leader, not something each replica computes from its own clock. Waiting acquires live in the leader's memory and must be failed cleanly on a leader change. A leader that has been replaced but does not know it yet must not answer Validate. And the claim becomes linearizability, which needs a checker run against histories with injected partitions and crashes. None of this is built.

Where it stops#

Known limits, as they stand:

• One governord is the authority. Everything fails closed, so its outage is an outage of admission for everything behind it. The restart is fast and loses nothing that was acknowledged, but it is a single point of failure.
• API keys sit in the configuration file in the clear, and a new TLS certificate needs a restart.
• Metrics and logs, but no traces.
• Quota counts permission, not delivery. A unit is charged when the consume is granted, before the request is sent. A budget may be under-used but never exceeded.
• Request ids sent directly with an API key, as the agent hook does, are not kept across a restart.

What I would do differently if I started again:

• Put the clock into the log from the start. Expiry decided by local time is fine for one node and is the first thing replication has to undo.
• Charge the fair queue by time held, not by grant.
• Add metrics before the terminal screen. Queue depth and commit latency are what an operator needs first.

One real client: agent CLIs#

To put a real fan-out workload behind it, I wrote governor hook, a PreToolUse hook for Claude Code and Codex. It caps how many tool calls a run makes, how many subagents it uses, and for how long it may keep going. When a budget is spent the tool is refused and the model is told why:

Governor blocked this tool: the tool_calls budget of "claude:4f2a" is spent (500 of 500 used).
Do not retry; stop and tell the user the budget is exhausted.

The hook keeps no state between calls: it finds or creates the run's node by name on every call. governor ui is a terminal screen over the same tree that shows what every run has used and edits its caps while it runs.

Both are clients of the same three primitives. Governor is meant to stay a resource governor for fan-out workloads; the agent hook is one use of it, not its direction.

The questions this design has to answer#

If you only read one section, these are the ones that carry the weight, with the short answer and where it is argued above.

1. Why is a TTL not enough for a lease? A paused worker cannot notice its own pause. The check must sit at the downstream, using an id that only grows. (Leases)
2. State is applied in memory before it is committed. Why is that safe? The record is always a prefix, and no reply is sent before its event is durable. (Write before reply)
3. Why one global lock? Every chain ends at the root, so per-node locks keep the same contention point. The lock costs 390 ns against a millisecond for the commit. (One lock)
4. What does the fair queue not guarantee? Fairness inside a tenant, fairness of time held, and credit for the past. (Fair queue)
5. Why not two instances, or a standby? Walk the four steps in figure 10: the same slot and the same id are given out twice. (Replication)
6. How do you know the invariants hold? Nine invariants checked after every step of 40 random histories, each replayed three ways, and the test was shown to fail on deliberate bugs. (Testing)
7. What is the weakest part? One governord. (Limits)

The code, the spec the tests check, and the raw benchmark output are at github.com/Avik-creator/governor.