Day 45 — Load Balancing Algorithms

Learning Objectives

• Implement round-robin, weighted round-robin, least-connections, and power-of-two
• Measure load distribution under unequal request costs
• Know which algorithm to recommend for different traffic patterns

Key Concepts

Algorithm         | State     | Best for
─────────────────────────────────────────────────────
Round-robin       | none      | Homogeneous backends, equal request cost
Weighted RR       | weights   | Backends with different capacity
Least-connections | per-conn  | Variable request duration (API + slow DB queries)
Random            | none      | Simple, scales well, similar to RR
Power-of-two      | sampled   | Best for cache backends (reduces stale connections)

Real usage:
  AWS NLB:         Flow hash (5-tuple) — same client always hits same backend
  nginx upstream:  Round-robin by default, least_conn available
  Cloudflare:      Least-connections with health checking
  HAProxy:         Least-connections by default

Exercise: Four Algorithms, One Interface

package main

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

type Backend struct {
    Addr        string
    Weight      int
    ActiveConns atomic.Int64
}

type Balancer interface {
    Pick(backends []*Backend) *Backend
}

// RoundRobin — stateless modulo
type RoundRobin struct{ counter atomic.Uint64 }

func (rb *RoundRobin) Pick(backends []*Backend) *Backend {
    if len(backends) == 0 { return nil }
    idx := rb.counter.Add(1) - 1
    return backends[idx%uint64(len(backends))]
}

// WeightedRoundRobin — higher weight = more requests
type WeightedRoundRobin struct {
    mu      sync.Mutex
    current int
    gcd     int
    maxW    int
    cw      int // current weight
}

func gcd(a, b int) int {
    for b != 0 { a, b = b, a%b }
    return a
}

func (wrr *WeightedRoundRobin) Pick(backends []*Backend) *Backend {
    wrr.mu.Lock()
    defer wrr.mu.Unlock()
    n := len(backends)
    if n == 0 { return nil }

    // Compute GCD and max weight
    g := backends[0].Weight
    maxW := backends[0].Weight
    for _, b := range backends[1:] {
        g = gcd(g, b.Weight)
        if b.Weight > maxW { maxW = b.Weight }
    }

    for {
        wrr.current = (wrr.current + 1) % n
        if wrr.current == 0 {
            wrr.cw -= g
            if wrr.cw <= 0 {
                wrr.cw = maxW
            }
        }
        if backends[wrr.current].Weight >= wrr.cw {
            return backends[wrr.current]
        }
    }
}

// LeastConnections — pick the backend with fewest active connections
type LeastConnections struct{}

func (lc *LeastConnections) Pick(backends []*Backend) *Backend {
    if len(backends) == 0 { return nil }
    best := backends[0]
    for _, b := range backends[1:] {
        if b.ActiveConns.Load() < best.ActiveConns.Load() {
            best = b
        }
    }
    return best
}

// PowerOfTwo — sample 2 random backends, pick the less-loaded
type PowerOfTwo struct{}

func (p *PowerOfTwo) Pick(backends []*Backend) *Backend {
    if len(backends) == 0 { return nil }
    if len(backends) == 1 { return backends[0] }
    i := rand.Intn(len(backends))
    j := rand.Intn(len(backends) - 1)
    if j >= i { j++ }
    a, b := backends[i], backends[j]
    if a.ActiveConns.Load() <= b.ActiveConns.Load() {
        return a
    }
    return b
}

func main() {
    backends := []*Backend{
        {Addr: "10.0.0.1:8080", Weight: 1},
        {Addr: "10.0.0.2:8080", Weight: 2},
        {Addr: "10.0.0.3:8080", Weight: 1},
    }

    // Simulate load with variable connection counts
    backends[1].ActiveConns.Store(50)
    backends[2].ActiveConns.Store(10)

    algorithms := map[string]Balancer{
        "round-robin":        &RoundRobin{},
        "weighted-rr":        &WeightedRoundRobin{},
        "least-connections":  &LeastConnections{},
        "power-of-two":       &PowerOfTwo{},
    }

    for name, algo := range algorithms {
        counts := make(map[string]int)
        for i := 0; i < 1000; i++ {
            b := algo.Pick(backends)
            counts[b.Addr]++
        }
        fmt.Printf("\n%s (1000 reqs):\n", name)
        for addr, count := range counts {
            fmt.Printf("  %s: %d (%.1f%%)\n", addr, count, float64(count)/10)
        }
    }
}

Real-World Context

AWS NLB costs $0.006/LCU-hour. Understanding these algorithms helps you answer: "Why does the NLB keep sending traffic to the slow backend?" (Round-robin ignores backend latency — use Least-connections for APIs with variable response time.)