In part 1 I built the smallest possible load balancer: one backend, and Go’s httputil.ReverseProxy doing almost all the work. This time I wanted it to actually balance something, so phase 2 of steer is round robin across several backends.
Round robin is the simplest load balancing algorithm there is: request 1 goes to backend A, request 2 to B, request 3 to C, request 4 back to A, and so on. I figured this would take about ten minutes. The routing part did! But it led me into a concurrency bug that I think is really interesting, so most of this post is about that.
the obvious version Link to heading
You need a list of backends and a counter. Every request picks backends[counter % len(backends)] and then bumps the counter:
backend := backends[counter % len(backends)]
counter++
This looks fine, and if you test it by running curl in a loop, it works fine. But there’s a problem.
every request is its own goroutine Link to heading
In part 1 I learned that http.ListenAndServe starts a new goroutine for each connection. So if 100 requests arrive at once, my handler runs 100 times at the same time, and all 100 of them are touching counter.
I wanted to see what that actually does, so I wrote a tiny program where 1000 goroutines each run counter++ exactly once. Here’s what it printed over 5 runs:
plain counter: 966
plain counter: 964
plain counter: 974
plain counter: 975
plain counter: 990
1000 increments, and it never got to 1000! It came up short by 10 to 36 every time, and by a different amount each run.
why counter++ loses increments Link to heading
The thing I hadn’t really internalised is that counter++ looks like one operation, but the CPU does it in three steps:
- read
counterfrom memory - add 1
- write it back
If two goroutines interleave, this happens:
goroutine A: read counter → 41
goroutine B: read counter → 41
goroutine A: add 1, write → 42
goroutine B: add 1, write → 42 (A's increment is gone)
Both did their job, and one increment vanished. That’s a data race: two goroutines accessing the same memory at the same time, where at least one of them is writing.
In a load balancer, the symptom is pretty mild: two requests get the same counter value, so they both go to the same backend. You’d probably never notice. But in Go, a data race is officially undefined behaviour. I think that means you don’t get to reason about what happens, even if it seems harmless.
the race detector is amazing Link to heading
Go has a built-in race detector. You just add -race:
$ go run -race .
==================
WARNING: DATA RACE
Read at 0x00c000012140 by goroutine 12:
main.main.func1()
main.go:17 +0x70
Previous write at 0x00c000012140 by goroutine 7:
main.main.func1()
main.go:17 +0x80
It tells you exactly which line had the race, and which two goroutines were involved. Line 17 is the counter++. I’d heard of the race detector but never actually seen it catch something. It’s really satisfying!
the fix: atomic.Uint64 Link to heading
The fix is to use an atomic counter from sync/atomic:
var counter atomic.Uint64
n := counter.Add(1) - 1
backend := backends[n % uint64(len(backends))]
Add(1) does the read, the add and the write as one indivisible CPU instruction. No other goroutine can sneak in between the steps, so every caller gets a unique number. In my test program, the atomic counter got to exactly 1000 every single time.
(The - 1 is just so the first request goes to the first backend: Add returns the new value, so the first call returns 1.)
There’s another standard way to fix races, which is a mutex: you lock, do whatever you want, and unlock. I think of it like this: a mutex protects a whole block of code, and an atomic protects one number. For a single counter, atomic is simpler and faster.
but wait, isn’t reading the backend list also a race? Link to heading
This confused me for a bit. Every request also reads backends at the same time, with no lock. Why isn’t that a race?
It turns out concurrent reads are totally fine. A race needs at least one writer, and nothing ever writes to the backend list after startup. So it’s safe as long as that stays true.
It’s not going to stay true for long, though. In phase 3, health checks will be marking backends as up or down while requests are reading them. So I’m going to have this problem again, just in a more interesting shape.
the code Link to heading
I moved the routing logic out of main into its own package, internal/pool, mostly so I could test it. Here’s the whole round-robin part:
type Pool struct {
backends []*Backend
next atomic.Uint64
}
func (p *Pool) Next() *Backend {
n := p.next.Add(1) - 1
return p.backends[n%uint64(len(p.backends))]
}
And the handler in main.go from part 1 just changed from “always use this one proxy” to “ask the pool”:
handler := http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
b := p.Next()
b.Proxy.ServeHTTP(w, r)
})
That p.Next() call is the whole routing decision. I expect every smarter algorithm I add later (skipping dead backends, least connections) to just be a better version of Next().
A few small things I ran into:
- Each backend gets its own
ReverseProxy. Each proxy keeps its own pool of keep-alive TCP connections to its backend, so creating one per request would throw that away. (p *Pool)has to be a pointer receiver. With(p Pool), every call would get a copy of the pool, increment the copy’s counter, and throw it away. So every request would go to backend 0.url.Parseaccepts almost anything. If you writelocalhost:8081without thehttp://, it happily parseslocalhostas the scheme. The load balancer would start up fine and then fail every request. So I check that the scheme and host aren’t empty and refuse to start otherwise.- An empty backend list would crash it.
n % 0panics in Go, sopool.Newrejects an empty list up front. - What about overflow? After 18 quintillion requests the counter wraps back to 0, and the modulo keeps working. At a million requests per second, that takes about 580,000 years.
testing it Link to heading
The test I care most about starts 100 goroutines that each call Next() 300 times, so 30,000 picks across 3 backends. Then it checks each backend got exactly 10,000:
$ go test -race -v ./...
=== RUN TestNextIsEvenUnderConcurrency
--- PASS: TestNextIsEvenUnderConcurrency (0.02s)
The test passing with -race is the important part: it checks both that the distribution is perfectly even and that there’s no race. If I swap the atomic back to a plain counter++, it fails.
it works! and then I killed a backend Link to heading
With three backends running:
$ for i in 1 2 3 4 5 6; do curl -s localhost:8080/req$i; done
hello from backend-8081 (path=/req1)
hello from backend-8082 (path=/req2)
hello from backend-8083 (path=/req3)
hello from backend-8081 (path=/req4)
hello from backend-8082 (path=/req5)
hello from backend-8083 (path=/req6)
That’s perfect rotation. Then I killed the backend on port 8082 and ran it again:
HTTP 200 hello from backend-8081 (path=/req1)
HTTP 502
HTTP 200 hello from backend-8083 (path=/req3)
HTTP 200 hello from backend-8081 (path=/req4)
HTTP 502
HTTP 200 hello from backend-8083 (path=/req6)
Every third request fails. Round robin has no idea 8082 is dead, so it keeps faithfully sending it exactly its fair share of traffic.
In some ways this is worse than part 1. With one backend, a dead backend at least looked like an outage. With three, two thirds of requests succeed, so it looks like a flaky service with a 33% error rate. I think that’s a much more confusing thing to debug.
next: health checks Link to heading
So phase 3 is making steer notice. I think it needs two pieces:
- active health checks: a background goroutine that polls each backend’s
/healthzevery few seconds and takes it out of rotation if it stops answering - passive detection: if a real request fails, mark that backend as down immediately and retry the request somewhere else, so the user never sees the 502
And since health checks will be writing to the backends while requests are reading them, the backend list is about to stop being read-only. So, more races!
The code is at github.com/balakrishnan-vasudevan/steer.