gw-04 step 03 — Subsetting with a Van der Corput ring

Goal

Stop every gateway from connecting to every origin. Each gateway picks a balanced subset of origins using a low-discrepancy (Van der Corput) distribution ring, so total connections = gateways × subset while load stays even and barely moves when membership changes. This is the core of the Netflix churn win.

Code — the Van der Corput sequence

package subset

// vanDerCorput returns the i-th value of the binary Van der Corput
// low-discrepancy sequence in [0,1): write i in binary, reverse the
// bits, read back as a fraction. Successive points always land in the
// largest remaining gap — no clumping.
func vanDerCorput(i uint32) float64 {
	var rev uint32
	bits := 32
	x := i
	for b := 0; b < bits; b++ {
		rev = (rev << 1) | (x & 1)
		x >>= 1
	}
	return float64(rev) / float64(1<<32) // rev / 2^32  in [0,1)
}

Code — map members to the ring and pick a subset

package subset

import "sort"

type Ring struct {
	points []ringPoint // origins placed on [0,1), sorted
}
type ringPoint struct {
	pos    float64
	origin string
}

// BuildRing places each origin deterministically on the ring using the
// Van der Corput sequence indexed by a stable per-origin index.
func BuildRing(origins []string) *Ring {
	pts := make([]ringPoint, len(origins))
	for i, o := range origins {
		pts[i] = ringPoint{pos: vanDerCorput(uint32(i)), origin: o}
	}
	sort.Slice(pts, func(a, b int) bool { return pts[a].pos < pts[b].pos })
	return &Ring{points: pts}
}

// Subset returns `size` origins for the gateway placed at gwPos: walk
// clockwise from gwPos and take the next `size` distinct origins. Two
// gateways at nearby positions overlap a lot; gateways spread evenly
// (because gwPos also comes from the Van der Corput sequence) cover the
// origins evenly.
func (r *Ring) Subset(gwPos float64, size int) []string {
	if size >= len(r.points) {
		out := make([]string, len(r.points))
		for i, p := range r.points {
			out[i] = p.origin
		}
		return out
	}
	// find first point >= gwPos
	start := sort.Search(len(r.points), func(i int) bool {
		return r.points[i].pos >= gwPos
	})
	out := make([]string, 0, size)
	for i := 0; i < size; i++ {
		out = append(out, r.points[(start+i)%len(r.points)].origin)
	}
	return out
}

// GatewayPosition places gateway g on the same ring via Van der Corput,
// so the whole fleet is evenly distributed without coordination.
func GatewayPosition(gatewayIndex int) float64 {
	return vanDerCorput(uint32(gatewayIndex))
}

Prove balance and stability

// coverage[origin] = number of gateways whose subset includes it.
// Even coverage => even load on origins.
func coverage(origins []string, gateways, subsetSize int) map[string]int {
	ring := BuildRing(origins)
	cov := map[string]int{}
	for g := 0; g < gateways; g++ {
		for _, o := range ring.Subset(GatewayPosition(g), subsetSize) {
			cov[o]++
		}
	}
	return cov
}

Experiments:

1. Connection math. origins=1000, gateways=500, subset=20. Total connections = 500 × 20 = 10,000 vs 500 × 1000 = 500,000 everyone-to-everyone. Print both.
2. Balance. Compute coverage and report min/max/stddev. Compare Van der Corput placement vs naive rand.Float64() placement — the random version has higher variance (hot/cold origins).
3. Stability under churn. Remove one origin, rebuild the ring, and count how many (gateway → origin) assignments changed. Compare to hash-mod subsetting (origins[(hash(gw)+i) % len]), which reshuffles almost everything when len changes. The ring moves only a small, balanced fraction.

Tasks

1. Implement vanDerCorput, BuildRing, Subset, and the coverage analysis.
2. Print the connection-count reduction for a realistic fleet size.
3. Show, with numbers: (a) lower coverage variance than random; (b) far fewer assignment changes than hash-mod when one member leaves.
4. Combine with step 02: each per-loop pool only dials origins in this gateway's subset. Re-measure total idle connections — the K× rise from step 02 is now bounded by the subset size.

Acceptance

• Correct Van der Corput values (0, .5, .25, .75, .125, ...).
• A printed N×M → N×subset reduction (e.g. 500k → 10k).
• Quantified balance (low coverage variance) and stability (few reassignments on membership change) versus random and hash-mod.

Discussion prompts

• Why does bit-reversal produce an evenly-spread sequence, intuitively? (Each new point bisects the largest existing gap.)
• How big must the subset be so that losing f origins still leaves enough capacity? (A quorum-style argument — connect it to db-17's majority reasoning.)
• Membership comes from the control plane (gw-08 EDS / gw-09 EndpointSlices). Rapid pod churn would rebuild the ring constantly. How do you debounce re-subsetting so the fix doesn't cause churn?
• Where does this interact with load balancing (gw-06)? (You still P2C within the subset and eject outliers within it.)