Documentation
¶
Overview ¶
Package turnstile bounds how many callers may hold a resource at once AND decides which waiter is admitted next: the lowest priority band, and within a band the job that started earliest.
A job declares itself once, and every call it goes on to make takes its turns from the context:
ctx = set.ContextWithPriority(ctx, shard, priority) // once, when the JOB begins ... pass := turnstile.WaitTurn(ctx) // at each call that holds the resource defer pass.Return()
Nothing is wrapped, so each call site chooses where its own pass begins and ends. That is deliberate: only the call site knows when the resource is really released. A query hands back a cursor that keeps holding a connection until it is closed, so a wrapper returning that cursor could not know when to hand the pass back, while the call site simply holds it until it has finished reading.
A PASS MUST STRICTLY ENCLOSE THE RESOURCE IT ORDERS ACCESS TO - for the whole time it is held, which for a query means until its rows are closed and for a transaction means until it commits. Never take a pass while already holding the resource: with a pass for every unit of the resource, callers holding units without passes and callers holding passes without units deadlock each other, and neither side can break the cycle. Where a unit is held across several operations, one pass wraps them all rather than one per operation.
THE CLAIM IS THE JOB'S, NOT THE CALL'S. Claim.Since is when the job began and Claim.Seq identifies it, so both stay fixed for every turn it takes - which is what makes the ordering first-in-first-out over JOBS rather than over calls: a caller coming back for its next turn keeps its original age and is served ahead of work that started later, so a job in progress finishes before a new one begins. The claim is trusted entirely, so it must not come from anywhere a caller could pick its own place in line - which is why a context's claim can only be set through this package.
Ordering is by priority band first, so a band is served to exhaustion before the next one is looked at. A band therefore cannot be given to any caller that can arrive faster than it is served, or the bands below it never run at all.
Close is the stop signal: it releases every waiter and the turnstile admits nobody forever after. Concurrency is live (Resize), because the resource it is sized against moves at runtime.
One Turnstile governs one resource, and a Set holds one per shard. A single turnstile spanning several resources would let a caller queued for a busy one hold up a caller bound for an idle one.
Index ¶
- type Claim
- type Gate
- type Pass
- type Set
- func (s *Set) Close()
- func (s *Set) Closed() bool
- func (s *Set) ContextWithPriority(ctx context.Context, shard int, priority int) context.Context
- func (s *Set) Gate(priority int) *Gate
- func (s *Set) Resize(shard int, concurrency int)
- func (s *Set) Snapshot() (available, waiting map[int]int)
- func (s *Set) Turnstile(shard int) *Turnstile
- type Turnstile
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Claim ¶
Claim is what a caller is asking with, and the whole of what orders it against the other waiters: the band it sits in, when its WORK began, and a tiebreak for the two of those being equal.
Since is the age of the JOB, not of the call. Seq identifies the job when two of them share a Since, which a clock coarser than the arrival rate makes common; it must therefore be constant for every turn one job takes, or two tied jobs interleave instead of one finishing first.
type Gate ¶
type Gate struct {
// contains filtered or unexported fields
}
Gate takes a job's FIRST turn, at a fixed band, before the job has been picked up.
It exists for a caller that hands work to a pool of goroutines and decides how big that pool should be by watching whether they are blocked - the pattern internal/workers implements. Such a caller must take its turn BEFORE it takes the work, for two reasons that have nothing to do with bounding the database:
- A goroutine blocked here is holding no work, so it reads as available, so the pool does not grow to add capacity that could only queue behind the same turnstile. Blocking IS the signal; nothing has to ask this package how full it is.
- Work not yet taken is still visible to every other goroutine. Taking it first and blocking afterwards strands it inside one that cannot proceed with it.
The turn it takes is the job's first, not a separate reservation: the context it returns carries the claim, stamped at the moment the job was picked up, so every later turn the job takes is ordered by that same moment. The caller releases it when the work stops holding the resource - typically right after the first database call - and takes further turns on the returned context from there on.
func (*Gate) Acquire ¶
Acquire stamps a claim for a job about to be picked up on a shard and blocks until its turn comes, returning the context every later turn of that job must be taken on.
ok is false only when the set has CLOSED, which is the caller's stop signal. It is checked on both sides of the wait: before, so a drained set admits nobody, and after, because a close is what releases a blocked caller and it must be told to stop rather than left to carry on into a shutting-down system. This is the one place a closed turnstile means "stop" instead of "proceed unordered" - which is why it asks the set rather than reading the pass.
type Pass ¶
type Pass struct {
// contains filtered or unexported fields
}
Pass is one issued turn. Return it when the work that holds the resource is done.
func WaitTurn ¶
WaitTurn takes a turn for the claim on ctx, blocking until it is the best one waiting. Wrap it around the work that holds the resource:
pass := turnstile.WaitTurn(ctx) defer pass.Return() ... the call that holds a connection, INCLUDING reading the rows it returns ...
The pass must enclose the resource for the whole time it is held, which for a query means until its rows are closed and for a transaction means until it commits - a query hands back a connection-holding cursor, so returning the pass when the call returns leaves the connection held by a caller that no longer has a turn. That is the one arrangement this cannot survive: with a pass for every unit of the resource, callers holding units without passes and callers holding passes without units deadlock each other.
It never refuses to let a caller proceed. A context that was never prioritized, a shard with no turnstile, an expired ctx and a closed turnstile all yield a zero Pass, which is safe to Return and simply means this caller went unordered - so a call site can be converted before or after the paths that stamp its context, and a drain never strands work whose outcome exists nowhere else.
func (Pass) Return ¶
func (p Pass) Return()
Return hands the pass back, admitting the best waiting caller. Calling it twice is a no-op: a second release would issue a pass that was never taken, inflating the ceiling past the resource it is sized against - which does not fail loudly, it quietly moves the waiting somewhere that has no ordering. Returning a pass that was never issued (the !ok case, or the zero value) is also a no-op.
Not calling it at all is the failure this cannot absorb: admission decays with every leak until it stops. Where the acquire and the return sit in different functions, call it unconditionally on the way out - the no-op cases are what make that safe.
type Set ¶
type Set struct {
// contains filtered or unexported fields
}
Set holds one Turnstile per shard. It is a lookup table and nothing more: the turnstiles are wholly independent, each with its own lock and queue, so one shard's contention is invisible to another and a release on one can never wake a waiter on another.
func NewSet ¶
func NewSet() *Set
NewSet returns an empty Set. A shard admits nothing through this package until Resize gives it a turnstile; see ContextWithPriority for what happens to a context bound for a shard that has none.
func (*Set) Close ¶
func (s *Set) Close()
Close closes every turnstile in the set, releasing all their waiters. Idempotent.
func (*Set) Closed ¶
Closed reports whether the set has been closed. WaitTurn deliberately cannot answer this - it lets every caller through so that work already under way still finishes - so a caller whose job is to STOP on a drain, rather than to proceed unordered, asks here.
func (*Set) ContextWithPriority ¶
ContextWithPriority binds a context to one shard's turnstile at the given band, so that WaitTurn can be called anywhere downstream without the turnstile being threaded through every signature.
It stamps the job's age and identity ONCE. Calling it again on an already-stamped context - which is what a cross-shard operation does, re-pointing the same job at each shard in turn - keeps the original age and job number and changes only the shard and the band. Re-stamping instead would make a job look newly arrived at every hop, which is precisely the ordering this exists to provide: a job that has been running for a while would keep losing to work that just started.
A shard with no turnstile yields a context that WaitTurn passes straight through. That is the fail-open direction and it is the right one here, because this orders access to a resource that already bounds itself - so the cost of an unsized shard is that its callers go unordered, not that they are blocked. A gate that IS the bound would have to fail the other way.
func (*Set) Gate ¶
Gate returns a gate over this set at the given band. The band is the caller's policy, which is why it is bound here rather than assumed.
func (*Set) Resize ¶
Resize sets a shard's ceiling, creating its turnstile on first use. Size it against the resource being ordered - AT MOST as many passes as there are units of it, or the surplus callers simply queue inside the resource again, where there is no ordering, while this reports itself healthy.
Every path that changes that resource's size must call this, for the same reason the ceiling exists.
type Turnstile ¶
type Turnstile struct {
// contains filtered or unexported fields
}
Turnstile admits up to a configured number of concurrent holders, choosing among waiters by priority and then by age. Safe for concurrent use by any number of goroutines. The zero value is not usable; call New.
func New ¶
New returns a Turnstile issuing at most concurrency passes at a time. A concurrency of zero admits nobody until Resize gives it one.
func (*Turnstile) Close ¶
func (t *Turnstile) Close()
Close permanently releases every waiter; WaitTurn reports !ok forever after. Idempotent. It is the only stop signal, so a caller parked here is unreachable until it is called - closing whatever else the callers park on is not enough to drain them.
func (*Turnstile) Resize ¶
Resize changes the ceiling, live. The available count moves by its DELTA, never to the new value, so passes held right now stay held - assigning the ceiling outright would issue those a second time. Shrinking below what is held drives the count negative, which simply admits nobody until enough holders return, and needs no special case. A grow hands the new passes straight to the waiters at the head.
func (*Turnstile) Snapshot ¶
Snapshot reports the passes currently free and the callers currently queued, for metrics. available is signed only because a live Resize can shrink the ceiling below what is held.
Both numbers are instantaneous, so a turnstile that was saturated for a whole window without ever being sampled empty reads the same as an idle one. The durable measure is how long callers actually waited, which Pass.Waited reports per acquisition.
func (*Turnstile) WaitTurn ¶
WaitTurn blocks until this claim is the best one waiting on a free pass, the ctx is done, or the turnstile closes.
ok is false when no pass was issued, which is either the ctx expiring or a close; the caller's own ctx.Err() tells the two apart. The returned Pass is safe to Return either way.
The returned Pass is not reusable and not safe to share: it names one issued pass, and returning it twice is a no-op rather than a second release.
Source Files