hedge

package module
v1.0.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 25, 2026 License: MIT Imports: 10 Imported by: 0

README

hedge

CI CodeQL Coverage Mutation Documentation Go Reference Release Go License

hedge reduces eligible tail latency by starting a finite number of duplicate attempts after explicit delays. Unlike retry, an earlier attempt is still running when a hedge starts. The package makes replay safety, amplification, deadlines, shared budgets, cancellation, result ownership, and endpoint-safe observability explicit.

The design follows Failsafe-Go hedge semantics and the delayed-duplicate technique described in The Tail at Scale. Go contexts make cancellation cooperative: canceling a context asks work to stop; it does not wait for it to stop.

Quick start

budget, err := hedge.NewOutstandingBudget(20)
if err != nil {
	return err
}
policy, err := hedge.NewPolicy(hedge.Config[*http.Response]{
	MaxHedges:          1,
	ReplaySafe:         true, // a reviewed downstream duplicate-suppression contract
	Delay:              40 * time.Millisecond,
	TotalTimeout:       300 * time.Millisecond,
	AttemptTimeout:     200 * time.Millisecond,
	CleanupTimeout:     50 * time.Millisecond,
	Clock:              hedge.RealClock{},
	Budget:             budget,
	Classifier: hedge.ClassifyFunc[*http.Response](func(_ context.Context, r hedge.AttemptResult[*http.Response]) (hedge.Classification, error) {
		if r.Err == nil && r.Value.StatusCode < 500 {
			return hedge.ClassificationSuccess, nil
		}
		return hedge.ClassificationFailure, nil
	}),
	Disposer: hedge.DisposeFunc[*http.Response](func(_ context.Context, response *http.Response) error {
		if response == nil || response.Body == nil {
			return nil
		}
		return response.Body.Close()
	}),
	Resource:           "catalogue-read",
	FactoryFailureMode: hedge.FactoryFailureStop,
})
if err != nil {
	return err
}

response, report, err := hedge.Do(ctx, policy,
	hedge.AttemptFactoryFunc[*http.Response](func(info hedge.AttemptInfo) (hedge.Attempt[*http.Response], string, error) {
		req, err := newIndependentlyOwnedRequest(info) // including a fresh Body
		if err != nil {
			return nil, "", err
		}
		return func(attemptCtx context.Context) (*http.Response, error) {
			return client.Do(req.WithContext(attemptCtx))
		}, safeEndpointID(info), nil
	}))
if err != nil {
	// A non-nil response is the deterministic selected failed result and is now
	// caller-owned. All other returned results are disposed by the policy.
}
// During shutdown, wait with a bounded context for cooperative losers.
_ = report.Wait(shutdownCtx)

http.Request.Clone only shallow-copies Body; use GetBody or an application-owned replay factory to create a fresh body for every attempt.

Safety boundary

ReplaySafe: true is a declaration, not an inferred property. Do not hedge payments, non-idempotent writes, queue acknowledgements, transactions, or non-replayable streams unless every downstream hop provides and honors a reviewed idempotency key and duplicate suppression. An idempotency key by itself does not prove this.

The package never clones requests, discovers endpoints, load balances, retries sequentially, chooses fallbacks, or combines retry and hedge presets. See replay safety, composition, and Kubernetes sizing.

API and ownership

  • Ordinal 0 is the original; 1..MaxHedges are delayed hedges.
  • Exactly one published success wins. Published equal-clock successes use the lower ordinal; publication itself is linearized by the execution.
  • Winner cancellation is immediate but cooperative. Report.Wait exposes attempts that ignore cancellation.
  • The returned value is caller-owned. On all-failure, it is the lowest-ordinal failed result. Every other returned value is passed exactly once to the configured disposer.
  • ExecutionError.Error and observations exclude raw downstream messages.
  • OutstandingBudget bounds concurrent additional attempts across every execution sharing it. Use a distinct shared instance per resource when independent bounds are required.

See the API reference, operations guide, FAQ, and changelog.

Ecosystem

Use the Golib documentation portal to choose companion packages, supported stacks, recipes, and operations guidance.

Documentation

Overview

Package hedge executes explicitly replay-safe operations with bounded, delayed concurrent attempts. It does not infer idempotency or clone request state; an AttemptFactory must create independently owned mutable state for every attempt.

Index

Examples

Constants

View Source 
const MaxBudgetCapacity uint = 1_000_000

MaxBudgetCapacity prevents a nominally finite budget from acting as an operationally unbounded admission policy.

View Source 
const MaxHedges uint = 64

MaxHedges bounds policy allocation, retained failure metadata, and fan-out.

View Source 
const MaxResourceLength = 128

MaxResourceLength bounds endpoint-safe resource identity used by budgets and observations.

Variables

View Source 
var ErrInvalidBudget = errors.New("hedge: invalid budget")

ErrInvalidBudget identifies a zero or otherwise unusable shared-work bound.

View Source 
var ErrInvalidPolicy = errors.New("hedge: invalid policy")

ErrInvalidPolicy identifies implicit, contradictory, or unbounded policy configuration.

Functions

This section is empty.

Types

type Attempt 

type Attempt[T any] func(context.Context) (T, error)

Attempt performs one independently owned execution. Cancellation is cooperative; implementations must return promptly when ctx is canceled.

type AttemptFactory 

type AttemptFactory[T any] interface {
	NewAttempt(context.Context, AttemptInfo) (Attempt[T], string, error)
}

AttemptFactory creates independently owned mutable state for every attempt. Construction must honor the context, return promptly, and avoid starting the external operation. Endpoint must be a bounded, credential-free identity suitable for labels.

type AttemptFactoryFunc 

type AttemptFactoryFunc[T any] func(AttemptInfo) (Attempt[T], string, error)

AttemptFactoryFunc adapts a non-blocking factory function. Use a concrete AttemptFactory when construction itself needs the logical context.

func (AttemptFactoryFunc[T]) NewAttempt 

func (function AttemptFactoryFunc[T]) NewAttempt(_ context.Context, info AttemptInfo) (Attempt[T], string, error)

NewAttempt invokes the adapted function.

type AttemptInfo 

type AttemptInfo struct {
	Ordinal uint
	Hedge   bool
	Delay   time.Duration
}

AttemptInfo identifies an original or additional execution. Ordinal zero is always the original; positive ordinals are hedges.

type AttemptResult 

type AttemptResult[T any] struct {
	Value      T
	Err        error
	ContextErr error
	Ordinal    uint
	Hedge      bool
}

AttemptResult is passed to a Classifier. Value and Err are never included in observations or error strings.

type Budget 

type Budget interface {
	Capacity() uint
	TryAcquire(resource string) (Permit, bool)
}

Budget bounds shared additional work. Implementations may account globally, per resource, or over a documented recent-work window. Capacity must be immutable, finite, and consistent with non-blocking, panic-free TryAcquire.

type CanceledError 

type CanceledError struct {
	// contains filtered or unexported fields
}

CanceledError distinguishes caller cancellation from downstream failure.

func (*CanceledError) Error 

func (err *CanceledError) Error() string

func (*CanceledError) Unwrap 

func (err *CanceledError) Unwrap() error

type Classification 

type Classification uint8

Classification is the explicit policy decision for one completed attempt. 

const (
	// ClassificationSuccess selects the attempt as the winner.
	ClassificationSuccess Classification = iota + 1
	// ClassificationFailure retains the failure and permits active or scheduled
	// attempts to continue.
	ClassificationFailure
	// ClassificationCanceled records a non-downstream cancellation and permits
	// other attempts to continue.
	ClassificationCanceled
	// ClassificationTerminal stops the logical operation without a winner.
	ClassificationTerminal
)

type Classifier 

type Classifier[T any] interface {
	Classify(context.Context, AttemptResult[T]) (Classification, error)
}

Classifier decides whether one result wins, fails, was canceled, or terminally stops the logical operation. It must be safe for concurrent use.

type ClassifyFunc 

type ClassifyFunc[T any] func(context.Context, AttemptResult[T]) (Classification, error)

ClassifyFunc adapts a function to Classifier.

func (ClassifyFunc[T]) Classify 

func (function ClassifyFunc[T]) Classify(ctx context.Context, result AttemptResult[T]) (Classification, error)

Classify invokes the adapted function.

type CleanupError 

type CleanupError struct{ Failures uint }

CleanupError reports how many result disposals failed.

func (*CleanupError) Error 

func (err *CleanupError) Error() string

type Clock 

type Clock interface {
	Now() time.Time
	NewTimer(time.Duration) Timer
	WithTimeout(context.Context, time.Duration) (context.Context, context.CancelFunc)
}

Clock supplies monotonic policy time, timers, and deadline contexts so scheduling can be tested deterministically. Implementations must be safe for concurrent use and must not panic.

type Config 

type Config[T any] struct {
	MaxHedges          uint
	ReplaySafe         bool
	Delay              time.Duration
	Schedule           []time.Duration
	DynamicDelay       DelayFunc
	TotalTimeout       time.Duration
	AttemptTimeout     time.Duration
	CleanupTimeout     time.Duration
	Clock              Clock
	Budget             Budget
	Classifier         Classifier[T]
	Disposer           Disposer[T]
	Observer           Observer
	Resource           string
	FactoryFailureMode FactoryFailureMode
	// UseResilienceBudget consumes the shared work-amplification scope attached
	// to the execution context instead of the compatibility Budget.
	UseResilienceBudget bool
}

Config defines every safety decision and dependency for a Policy. Exactly one of Delay, Schedule, or DynamicDelay must be configured.

type DeadlineError 

type DeadlineError struct{}

DeadlineError distinguishes the total policy deadline from downstream failure.

func (*DeadlineError) Error 

func (*DeadlineError) Error() string

func (*DeadlineError) Unwrap 

func (*DeadlineError) Unwrap() error

type DelayFunc 

type DelayFunc func(DelayInput) (time.Duration, error)

DelayFunc returns the delay after the preceding attempt launch.

type DelayInput 

type DelayInput struct {
	Hedge    uint
	Previous time.Duration
}

DelayInput gives a dynamic delay policy bounded metadata. Dynamic functions must not retain hidden unbounded latency history.

type DisposeFunc 

type DisposeFunc[T any] func(context.Context, T) error

DisposeFunc adapts a function to Disposer.

func (DisposeFunc[T]) Dispose 

func (function DisposeFunc[T]) Dispose(ctx context.Context, value T) error

Dispose invokes the adapted function.

type Disposer 

type Disposer[T any] interface {
	Dispose(context.Context, T) error
}

Disposer releases resources owned by every non-winning result. It must be concurrency-safe and honor its cleanup context.

type ExecutionError 

type ExecutionError struct {
	// contains filtered or unexported fields
}

ExecutionError reports deterministic all-attempt failure. Its message never contains downstream errors; Unwrap exposes only the documented selected cause, which is the lowest ordinal failure.

func (*ExecutionError) Error 

func (err *ExecutionError) Error() string

func (*ExecutionError) Unwrap 

func (err *ExecutionError) Unwrap() error

type FactoryFailureMode 

type FactoryFailureMode uint8

FactoryFailureMode defines what happens when a hedge attempt cannot be constructed. Original-attempt factory failure always stops execution. 

const (
	// FactoryFailureStop stops the logical operation and cancels active attempts.
	FactoryFailureStop FactoryFailureMode = iota + 1
	// FactoryFailureContinue records the failed hedge and permits later work.
	FactoryFailureContinue
)

type Failure 

type Failure struct {
	Ordinal        uint
	Hedge          bool
	Delay          time.Duration
	Duration       time.Duration
	Endpoint       string
	Classification Classification
}

Failure retains bounded attempt metadata without retaining or joining raw error messages.

type Observation 

type Observation struct {
	Outcome  Outcome
	Ordinal  uint
	Delay    time.Duration
	Duration time.Duration
	Resource string
	Endpoint string
	// Classification is set for OutcomeAttemptCompleted and zero otherwise.
	Classification Classification
	Winner         bool
	Loser          bool
}

Observation contains bounded metadata and deliberately excludes results, request data, URLs, and raw errors.

type Observer 

type Observer interface {
	TryObserve(Observation) bool
}

Observer receives bounded lifecycle metadata through a non-blocking method. TryObserve must return immediately and must not call back into an execution.

type Outcome 

type Outcome uint8

Outcome identifies one bounded lifecycle event. It is safe to use as a metric label after mapping unknown values to a bounded fallback. 

const (
	// OutcomeNoHedgeNeeded records an original winner before any hedge started.
	OutcomeNoHedgeNeeded Outcome = iota + 1
	// OutcomeHedgeStarted records one admitted additional attempt.
	OutcomeHedgeStarted
	// OutcomeBudgetDenied records rejected additional work.
	OutcomeBudgetDenied
	// OutcomeWinnerSelected records a winner after additional work started.
	OutcomeWinnerSelected
	// OutcomeAllAttemptsFailed records deterministic failed-result selection.
	OutcomeAllAttemptsFailed
	// OutcomeCallerCanceled records caller cancellation.
	OutcomeCallerCanceled
	// OutcomeTotalDeadline records total timeout expiry.
	OutcomeTotalDeadline
	// OutcomeAttemptCompleted records one result published to the coordinator.
	OutcomeAttemptCompleted
	// OutcomeCleanupFailed records one disposer failure.
	OutcomeCleanupFailed
)

func (Outcome) String 

func (outcome Outcome) String() string

String returns a bounded label; unknown values collapse to "unknown".

type OutstandingBudget 

type OutstandingBudget struct {
	// contains filtered or unexported fields
}

OutstandingBudget bounds concurrent additional attempts across every policy and execution sharing the instance. Use one instance per resource when resources require independent limits; doing so avoids an unbounded hidden resource-key registry.

func NewOutstandingBudget 

func NewOutstandingBudget(limit uint) (*OutstandingBudget, error)

NewOutstandingBudget constructs a finite shared concurrency budget.

func (*OutstandingBudget) Capacity 

func (budget *OutstandingBudget) Capacity() uint

Capacity returns the immutable maximum number of outstanding hedges.

func (*OutstandingBudget) Outstanding 

func (budget *OutstandingBudget) Outstanding() uint64

Outstanding returns the number of currently admitted additional attempts.

func (*OutstandingBudget) TryAcquire 

func (budget *OutstandingBudget) TryAcquire(_ string) (Permit, bool)

TryAcquire reserves one additional attempt without blocking. A policy holds the permit until the completed result is consumed or reclaimed. Resource is accepted for the Budget contract but this implementation deliberately has a single bounded scope.

type Permit 

type Permit interface{ Release() }

Permit accounts for one additional attempt. Release must be idempotent, concurrency-safe, non-blocking, and must not panic.

type Policy 

type Policy[T any] struct {
	// contains filtered or unexported fields
}

Policy is immutable and safe for concurrent execution. Its Budget, Classifier, Disposer, Clock, and Observer dependencies must also be safe for concurrent use.

func NewPolicy 

func NewPolicy[T any](config Config[T]) (*Policy[T], error)

NewPolicy validates finite amplification, time, replay, ownership, and dependency contracts and copies mutable configuration.

type RealClock 

type RealClock struct{}

RealClock uses the standard library's monotonic clock and timers.

func (RealClock) NewTimer 

func (RealClock) NewTimer(delay time.Duration) Timer

NewTimer starts a standard-library timer.

func (RealClock) Now 

func (RealClock) Now() time.Time

Now returns the current time.

func (RealClock) WithTimeout 

func (RealClock) WithTimeout(parent context.Context, timeout time.Duration) (context.Context, context.CancelFunc)

WithTimeout derives a standard-library timeout context.

type Reason 

type Reason uint8

Reason identifies the terminal logical outcome. 

const (
	// ReasonNoHedgeNeeded means the original won before additional work started.
	ReasonNoHedgeNeeded Reason = iota + 1
	// ReasonWinnerSelected means one of multiple started attempts won.
	ReasonWinnerSelected
	// ReasonAllAttemptsFailed means every admitted attempt completed unsuccessfully.
	ReasonAllAttemptsFailed
	// ReasonCallerCanceled means the caller canceled the logical operation.
	ReasonCallerCanceled
	// ReasonTotalDeadline means the configured total timeout elapsed.
	ReasonTotalDeadline
	// ReasonTerminalFailure means classification stopped the logical operation.
	ReasonTerminalFailure
	// ReasonFactoryFailure means attempt construction stopped the operation.
	ReasonFactoryFailure
	// ReasonDelayFailure means dynamic delay selection failed validation.
	ReasonDelayFailure
	// ReasonBudgetFailure means shared budget setup or admission failed locally.
	ReasonBudgetFailure
)

type Report 

type Report struct {
	Reason          Reason
	AttemptsStarted uint
	HedgesStarted   uint
	BudgetDenied    uint
	WinnerOrdinal   uint
	SelectedOrdinal uint
	Failures        []Failure
	// contains filtered or unexported fields
}

Report describes one logical execution. Wait lets callers and graceful shutdown code wait for cooperative loser cleanup without delaying winner delivery.

func Do 

func Do[T any](ctx context.Context, policy *Policy[T], factory AttemptFactory[T]) (T, Report, error)

Do executes one original attempt and at most MaxHedges delayed concurrent attempts. The factory is required to create independently owned mutable state; Do never clones or interprets application requests.

Example 
package main

import (
	"context"
	"fmt"
	"time"

	"github.com/faustbrian/go-hedge"
)

func main() {
	budget, _ := hedge.NewOutstandingBudget(1)
	policy, _ := hedge.NewPolicy(hedge.Config[string]{
		MaxHedges:      1,
		ReplaySafe:     true,
		Delay:          time.Hour,
		TotalTimeout:   time.Second,
		CleanupTimeout: time.Second,
		Clock:          hedge.RealClock{},
		Budget:         budget,
		Classifier: hedge.ClassifyFunc[string](func(_ context.Context, result hedge.AttemptResult[string]) (hedge.Classification, error) {
			if result.Err == nil {
				return hedge.ClassificationSuccess, nil
			}
			return hedge.ClassificationFailure, nil
		}),
		Disposer:           hedge.DisposeFunc[string](func(context.Context, string) error { return nil }),
		Resource:           "profile-read",
		FactoryFailureMode: hedge.FactoryFailureStop,
	})
	value, report, err := hedge.Do(context.Background(), policy,
		hedge.AttemptFactoryFunc[string](func(hedge.AttemptInfo) (hedge.Attempt[string], string, error) {
			return func(context.Context) (string, error) { return "profile", nil }, "pod-a", nil
		}))
	fmt.Println(value, report.Reason == hedge.ReasonNoHedgeNeeded, err)
}

Output:
profile true <nil>

func (Report) Wait 

func (report Report) Wait(ctx context.Context) error

Wait waits for all started attempt functions to return and for every non-winning returned value to be disposed. It reports cleanup failures by count without exposing raw disposer messages.

type Timer 

type Timer interface {
	C() <-chan time.Time
	Stop() bool
}

Timer is owned by one execution. Stop releases its resources; callers must not close C.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.