gw-06 step 01 — Power-of-two-choices load balancing + outlier ejection

Goal

Implement P2C load balancing with EWMA latency scoring and passive outlier ejection, then show it routes around a slow endpoint where round-robin does not.

Code — src/go/balancer.go

package lb

import (
	"math/rand"
	"sync"
	"sync/atomic"
	"time"
)

type Endpoint struct {
	Addr     string
	inflight atomic.Int64
	ewmaNs   atomic.Int64 // EWMA of latency in ns
	ejectedUntil atomic.Int64 // unix-nano; 0 = healthy
	fails    atomic.Int64
}

// score: lower is better. Combine in-flight and latency EWMA.
func (e *Endpoint) score() float64 {
	return float64(e.inflight.Load()+1) * float64(e.ewmaNs.Load()+1)
}

func (e *Endpoint) ejected(now int64) bool { return e.ejectedUntil.Load() > now }

type P2C struct {
	mu   sync.RWMutex
	eps  []*Endpoint
	rnd  *rand.Rand
}

func NewP2C(addrs []string) *P2C {
	b := &P2C{rnd: rand.New(rand.NewSource(time.Now().UnixNano()))}
	for _, a := range addrs {
		b.eps = append(b.eps, &Endpoint{Addr: a})
	}
	return b
}

// Pick returns an endpoint via power-of-two-choices among healthy ones.
func (b *P2C) Pick() *Endpoint {
	b.mu.RLock()
	defer b.mu.RUnlock()
	now := time.Now().UnixNano()
	healthy := make([]*Endpoint, 0, len(b.eps))
	for _, e := range b.eps {
		if !e.ejected(now) {
			healthy = append(healthy, e)
		}
	}
	if len(healthy) == 0 {
		healthy = b.eps // panic mode: everyone ejected -> use all (don't black-hole)
	}
	if len(healthy) == 1 {
		return healthy[0]
	}
	i := b.rnd.Intn(len(healthy))
	j := b.rnd.Intn(len(healthy) - 1)
	if j >= i {
		j++ // distinct second choice
	}
	a, c := healthy[i], healthy[j]
	if a.score() <= c.score() {
		return a
	}
	return c
}

// Observe records the result of a call for EWMA + ejection.
func (b *P2C) Observe(e *Endpoint, latency time.Duration, ok bool) {
	// EWMA: new = alpha*sample + (1-alpha)*old
	const alpha = 0.2
	old := e.ewmaNs.Load()
	sample := latency.Nanoseconds()
	e.ewmaNs.Store(int64(alpha*float64(sample) + (1-alpha)*float64(old)))

	if ok {
		e.fails.Store(0)
		return
	}
	// Consecutive-failure ejection with growing cool-down.
	n := e.fails.Add(1)
	if n >= 5 {
		cool := time.Duration(n) * 2 * time.Second
		e.ejectedUntil.Store(time.Now().Add(cool).UnixNano())
	}
}

The experiment — P2C vs round-robin under a slow endpoint

setup: 5 endpoints; endpoint #3 injected with 10x latency (a "gray
failure" — up but slow).

round-robin: 1/5 of requests hit #3 and eat its 10x latency; the p99 is
dominated by #3. Throughput drops because in-flight piles up on #3.

P2C + EWMA: as #3's EWMA latency climbs, it almost always loses the
"two choices" comparison, so it gets a shrinking share. The p99 stays
near the healthy endpoints'. If #3 starts erroring, outlier ejection
removes it entirely.

Tasks

1. Implement P2C, Observe, EWMA, and ejection.
2. Stand up 5 mock endpoints; inject 10× latency on one. Drive load and compare the request distribution and p99 for round-robin vs P2C.
3. Flip the slow endpoint to erroring; confirm outlier ejection removes it within ~5 failures and probes it back after the cool-down.
4. Add the panic threshold: when >50% would be ejected, stop ejecting (a fleet-wide brown-out must not black-hole all traffic).

Acceptance

• P2C sends a shrinking share to the slow endpoint; p99 stays near the healthy set's. Round-robin's p99 is dragged by the slow one.
• Outlier ejection removes a failing endpoint and restores it after cool-down; the panic threshold prevents ejecting everyone.

Discussion prompts

• Why is EWMA (not the last latency) the right signal? What does a too- high vs too-low alpha do?
• Why does P2C beat round-robin so much for almost no extra cost? (The "power of two choices" exponential max-load result.)
• With per-event-loop state (gw-04), each loop sees only its own in-flight counts. Is per-loop P2C good enough, or do you need shared counters? Argue it.