Algorithm Overview

The load balancer implements five distinct distribution algorithms, each with specific use cases:

1. Round Robin:

• Distributes requests sequentially across backends
• Uses atomic counter for thread-safe indexing
• Best for: Homogeneous backends with similar capacity
• Guarantees: Even distribution over time

2. Least Connections:

• Routes to backend with fewest active connections
• Dynamically adapts to backend load
• Best for: Variable request processing times
• Handles: Long-lived connections effectively

3. Weighted Round Robin:

• Distributes based on backend capacity weights
• Higher weight = more requests
• Best for: Heterogeneous backends with different capacities
• Allows: 2:1 or 3:1 traffic ratios

4. IP Hash:

• Consistent hashing based on client IP
• Same client always routes to same backend
• Best for: Stateful applications requiring sticky sessions
• Uses: FNV-1a hash for uniform distribution

5. Random:

• Randomly selects healthy backend
• Simple and effective under high load
• Best for: High-volume, low-latency scenarios
• Performs: Surprisingly well in practice

Time Complexity Analysis

Space Complexity

• O(n) where n = number of backends
• Each backend: ~200 bytes
• Total overhead: ~1-2 KB for typical 5-10 backend setup

Implementation

  1package loadbalancer
  2
  3import (
  4    "context"
  5    "errors"
  6    "hash/fnv"
  7    "io"
  8    "math/rand"
  9    "net/http"
 10    "net/http/httputil"
 11    "net/url"
 12    "sync"
 13    "sync/atomic"
 14    "time"
 15)
 16
 17var (
 18    ErrNoHealthyBackends = errors.New("no healthy backends available")
 19)
 20
 21type Algorithm string
 22
 23const (
 24    RoundRobin Algorithm = "round-robin"
 25    LeastConn  Algorithm = "least-conn"
 26    WeightedRR Algorithm = "weighted-rr"
 27    IPHash     Algorithm = "ip-hash"
 28    Random     Algorithm = "random"
 29)
 30
 31type Backend struct {
 32    URL         string
 33    Weight      int
 34    Healthy     bool
 35    ActiveConns int32
 36    TotalReqs   uint64
 37    proxy       *httputil.ReverseProxy
 38    mu          sync.RWMutex
 39}
 40
 41type LoadBalancer struct {
 42    backends  []*Backend
 43    algorithm Algorithm
 44    rrIndex   uint32
 45    mu        sync.RWMutex
 46}
 47
 48func New(algorithm Algorithm) *LoadBalancer {
 49    return &LoadBalancer{
 50        backends:  make([]*Backend, 0),
 51        algorithm: algorithm,
 52    }
 53}
 54
 55func AddBackend(urlStr string, weight int) error {
 56    parsedURL, err := url.Parse(urlStr)
 57    if err != nil {
 58        return err
 59    }
 60
 61    backend := &Backend{
 62        URL:     urlStr,
 63        Weight:  weight,
 64        Healthy: true,
 65        proxy:   httputil.NewSingleHostReverseProxy(parsedURL),
 66    }
 67
 68    lb.mu.Lock()
 69    lb.backends = append(lb.backends, backend)
 70    lb.mu.Unlock()
 71
 72    return nil
 73}
 74
 75func RemoveBackend(url string) {
 76    lb.mu.Lock()
 77    defer lb.mu.Unlock()
 78
 79    for i, backend := range lb.backends {
 80        if backend.URL == url {
 81            lb.backends = append(lb.backends[:i], lb.backends[i+1:]...)
 82            return
 83        }
 84    }
 85}
 86
 87func SelectBackend(clientIP string) {
 88    lb.mu.RLock()
 89    defer lb.mu.RUnlock()
 90
 91    healthy := lb.getHealthyBackends()
 92    if len(healthy) == 0 {
 93        return nil, ErrNoHealthyBackends
 94    }
 95
 96    switch lb.algorithm {
 97    case RoundRobin:
 98        return lb.roundRobin(healthy), nil
 99    case LeastConn:
100        return lb.leastConnections(healthy), nil
101    case WeightedRR:
102        return lb.weightedRoundRobin(healthy), nil
103    case IPHash:
104        return lb.ipHash(healthy, clientIP), nil
105    case Random:
106        return healthy[rand.Intn(len(healthy))], nil
107    default:
108        return lb.roundRobin(healthy), nil
109    }
110}
111
112func getHealthyBackends() []*Backend {
113    healthy := make([]*Backend, 0)
114    for _, backend := range lb.backends {
115        backend.mu.RLock()
116        if backend.Healthy {
117            healthy = append(healthy, backend)
118        }
119        backend.mu.RUnlock()
120    }
121    return healthy
122}
123
124func roundRobin(backends []*Backend) *Backend {
125    idx := atomic.AddUint32(&lb.rrIndex, 1) % uint32(len(backends))
126    return backends[idx]
127}
128
129func leastConnections(backends []*Backend) *Backend {
130    var selected *Backend
131    minConns := int32(^uint32(0) >> 1) // Max int32
132
133    for _, backend := range backends {
134        conns := atomic.LoadInt32(&backend.ActiveConns)
135        if conns < minConns {
136            minConns = conns
137            selected = backend
138        }
139    }
140
141    return selected
142}
143
144func weightedRoundRobin(backends []*Backend) *Backend {
145    totalWeight := 0
146    for _, b := range backends {
147        totalWeight += b.Weight
148    }
149
150    if totalWeight == 0 {
151        return lb.roundRobin(backends)
152    }
153
154    idx := int(atomic.AddUint32(&lb.rrIndex, 1)) % totalWeight
155    cumulative := 0
156
157    for _, backend := range backends {
158        cumulative += backend.Weight
159        if idx < cumulative {
160            return backend
161        }
162    }
163
164    return backends[0]
165}
166
167func ipHash(backends []*Backend, clientIP string) *Backend {
168    h := fnv.New32a()
169    h.Write([]byte(clientIP))
170    idx := h.Sum32() % uint32(len(backends))
171    return backends[idx]
172}
173
174func ServeHTTP(w http.ResponseWriter, r *http.Request) {
175    clientIP := r.RemoteAddr
176    backend, err := lb.SelectBackend(clientIP)
177    if err != nil {
178        http.Error(w, err.Error(), http.StatusServiceUnavailable)
179        return
180    }
181
182    // Track connection
183    atomic.AddInt32(&backend.ActiveConns, 1)
184    atomic.AddUint64(&backend.TotalReqs, 1)
185    defer atomic.AddInt32(&backend.ActiveConns, -1)
186
187    // Proxy request
188    backend.proxy.ServeHTTP(w, r)
189}
190
191func StartHealthChecks(ctx context.Context, interval time.Duration) {
192    ticker := time.NewTicker(interval)
193    go func() {
194        for {
195            select {
196            case <-ctx.Done():
197                ticker.Stop()
198                return
199            case <-ticker.C:
200                lb.performHealthChecks(ctx)
201            }
202        }
203    }()
204}
205
206func performHealthChecks(ctx context.Context) {
207    lb.mu.RLock()
208    backends := make([]*Backend, len(lb.backends))
209    copy(backends, lb.backends)
210    lb.mu.RUnlock()
211
212    for _, backend := range backends {
213        go lb.checkBackend(ctx, backend)
214    }
215}
216
217func checkBackend(ctx context.Context, backend *Backend) {
218    healthURL := backend.URL + "/health"
219    req, err := http.NewRequestWithContext(ctx, "GET", healthURL, nil)
220    if err != nil {
221        lb.markUnhealthy(backend)
222        return
223    }
224
225    client := &http.Client{Timeout: 3 * time.Second}
226    resp, err := client.Do(req)
227    if err != nil {
228        lb.markUnhealthy(backend)
229        return
230    }
231    defer resp.Body.Close()
232    io.Copy(io.Discard, resp.Body)
233
234    if resp.StatusCode == http.StatusOK {
235        lb.markHealthy(backend)
236    } else {
237        lb.markUnhealthy(backend)
238    }
239}
240
241func markHealthy(backend *Backend) {
242    backend.mu.Lock()
243    wasUnhealthy := !backend.Healthy
244    backend.Healthy = true
245    backend.mu.Unlock()
246
247    if wasUnhealthy {
248        // Log recovery
249    }
250}
251
252func markUnhealthy(backend *Backend) {
253    backend.mu.Lock()
254    wasHealthy := backend.Healthy
255    backend.Healthy = false
256    backend.mu.Unlock()
257
258    if wasHealthy {
259        // Log failure
260    }
261}
262
263func Stats() map[string]interface{} {
264    lb.mu.RLock()
265    defer lb.mu.RUnlock()
266
267    stats := make(map[string]interface{})
268    backendStats := make([]map[string]interface{}, len(lb.backends))
269
270    for i, backend := range lb.backends {
271        backend.mu.RLock()
272        backendStats[i] = map[string]interface{}{
273            "url":          backend.URL,
274            "healthy":      backend.Healthy,
275            "active_conns": atomic.LoadInt32(&backend.ActiveConns),
276            "total_reqs":   atomic.LoadUint64(&backend.TotalReqs),
277            "weight":       backend.Weight,
278        }
279        backend.mu.RUnlock()
280    }
281
282    stats["backends"] = backendStats
283    stats["algorithm"] = lb.algorithm
284    return stats
285}

Usage Example

 1package main
 2
 3import (
 4    "context"
 5    "fmt"
 6    "log"
 7    "net/http"
 8    "time"
 9)
10
11func main() {
12    // Create load balancer with least connections algorithm
13    lb := loadbalancer.New(loadbalancer.LeastConn)
14
15    // Add backends
16    lb.AddBackend("http://localhost:8081", 1)
17    lb.AddBackend("http://localhost:8082", 2) // Higher weight
18    lb.AddBackend("http://localhost:8083", 1)
19
20    // Start health checks
21    ctx := context.Background()
22    lb.StartHealthChecks(ctx, 10*time.Second)
23
24    // Serve HTTP
25    http.Handle("/", lb)
26
27    // Stats endpoint
28    http.HandleFunc("/stats", func(w http.ResponseWriter, r *http.Request) {
29        stats := lb.Stats()
30        fmt.Fprintf(w, "%+v\n", stats)
31    })
32
33    log.Println("Load balancer started on :8080")
34    log.Fatal(http.ListenAndServe(":8080", nil))
35}

Benchmarking Code

  1package loadbalancer_test
  2
  3import (
  4    "context"
  5    "net/http"
  6    "net/http/httptest"
  7    "sync"
  8    "sync/atomic"
  9    "testing"
 10    "time"
 11)
 12
 13// Benchmark round robin algorithm
 14func BenchmarkRoundRobin(b *testing.B) {
 15    lb := setupTestLoadBalancer(loadbalancer.RoundRobin, 10)
 16    ctx := context.Background()
 17
 18    b.ResetTimer()
 19    b.RunParallel(func(pb *testing.PB) {
 20        for pb.Next() {
 21            lb.SelectBackend(ctx, "127.0.0.1")
 22        }
 23    })
 24}
 25
 26// Benchmark least connections algorithm
 27func BenchmarkLeastConnections(b *testing.B) {
 28    lb := setupTestLoadBalancer(loadbalancer.LeastConn, 10)
 29    ctx := context.Background()
 30
 31    b.ResetTimer()
 32    b.RunParallel(func(pb *testing.PB) {
 33        for pb.Next() {
 34            backend, _ := lb.SelectBackend(ctx, "127.0.0.1")
 35            if backend != nil {
 36                atomic.AddInt32(&backend.ActiveConns, 1)
 37                atomic.AddInt32(&backend.ActiveConns, -1)
 38            }
 39        }
 40    })
 41}
 42
 43// Benchmark IP hash algorithm
 44func BenchmarkIPHash(b *testing.B) {
 45    lb := setupTestLoadBalancer(loadbalancer.IPHash, 10)
 46    ctx := context.Background()
 47    ips := []string{"192.168.1.1", "192.168.1.2", "192.168.1.3"}
 48
 49    b.ResetTimer()
 50    b.RunParallel(func(pb *testing.PB) {
 51        i := 0
 52        for pb.Next() {
 53            lb.SelectBackend(ctx, ips[i%len(ips)])
 54            i++
 55        }
 56    })
 57}
 58
 59// Benchmark full request flow
 60func BenchmarkServeHTTP(b *testing.B) {
 61    // Setup backend servers
 62    backend1 := httptest.NewServer(http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
 63        w.WriteHeader(http.StatusOK)
 64    }))
 65    defer backend1.Close()
 66
 67    backend2 := httptest.NewServer(http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
 68        w.WriteHeader(http.StatusOK)
 69    }))
 70    defer backend2.Close()
 71
 72    lb := loadbalancer.New(loadbalancer.RoundRobin)
 73    lb.AddBackend(backend1.URL, 1)
 74    lb.AddBackend(backend2.URL, 1)
 75
 76    b.ResetTimer()
 77    b.RunParallel(func(pb *testing.PB) {
 78        for pb.Next() {
 79            req := httptest.NewRequest("GET", "/", nil)
 80            w := httptest.NewRecorder()
 81            lb.ServeHTTP(w, req)
 82        }
 83    })
 84}
 85
 86// Benchmark health checks
 87func BenchmarkHealthChecks(b *testing.B) {
 88    lb := setupTestLoadBalancer(loadbalancer.RoundRobin, 10)
 89    ctx := context.Background()
 90
 91    b.ResetTimer()
 92    for i := 0; i < b.N; i++ {
 93        lb.performHealthChecks(ctx)
 94    }
 95}
 96
 97// Benchmark concurrent requests with high load
 98func BenchmarkHighConcurrency(b *testing.B) {
 99    backend := httptest.NewServer(http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
100        time.Sleep(10 * time.Millisecond) // Simulate work
101        w.WriteHeader(http.StatusOK)
102    }))
103    defer backend.Close()
104
105    lb := loadbalancer.New(loadbalancer.LeastConn)
106    for i := 0; i < 5; i++ {
107        lb.AddBackend(backend.URL, 1)
108    }
109
110    var successCount int64
111
112    b.ResetTimer()
113    b.RunParallel(func(pb *testing.PB) {
114        for pb.Next() {
115            req := httptest.NewRequest("GET", "/", nil)
116            w := httptest.NewRecorder()
117            lb.ServeHTTP(w, req)
118            if w.Code == http.StatusOK {
119                atomic.AddInt64(&successCount, 1)
120            }
121        }
122    })
123}
124
125func setupTestLoadBalancer(algo loadbalancer.Algorithm, numBackends int) *loadbalancer.LoadBalancer {
126    lb := loadbalancer.New(algo)
127    for i := 0; i < numBackends; i++ {
128        lb.AddBackend("http://localhost:800"+string(rune(i)), 1)
129    }
130    return lb
131}
132
133// Example benchmark results:
134// BenchmarkRoundRobin-8          50000000     25.3 ns/op     0 B/op     0 allocs/op
135// BenchmarkLeastConnections-8    10000000    125.0 ns/op     0 B/op     0 allocs/op
136// BenchmarkIPHash-8              20000000     68.4 ns/op     0 B/op     0 allocs/op
137// BenchmarkServeHTTP-8            1000000   1250.0 ns/op   512 B/op    10 allocs/op
138// BenchmarkHealthChecks-8          100000  12500.0 ns/op  2048 B/op    50 allocs/op

Production Considerations

1. Advanced Health Checking:

 1type HealthChecker struct {
 2    endpoint       string
 3    interval       time.Duration
 4    timeout        time.Duration
 5    failThreshold  int
 6    passThreshold  int
 7    consecutiveFails map[string]int
 8    mu             sync.Mutex
 9}
10
11func Check(ctx context.Context, backend *Backend) bool {
12    client := &http.Client{Timeout: h.timeout}
13    req, _ := http.NewRequestWithContext(ctx, "GET", backend.URL+h.endpoint, nil)
14
15    resp, err := client.Do(req)
16    if err != nil || resp.StatusCode != http.StatusOK {
17        h.mu.Lock()
18        h.consecutiveFails[backend.URL]++
19        fails := h.consecutiveFails[backend.URL]
20        h.mu.Unlock()
21
22        if fails >= h.failThreshold {
23            return false
24        }
25    } else {
26        h.mu.Lock()
27        h.consecutiveFails[backend.URL] = 0
28        h.mu.Unlock()
29    }
30
31    return true
32}

2. Connection Draining for Graceful Shutdown:

 1type GracefulLoadBalancer struct {
 2    *LoadBalancer
 3    draining atomic.Bool
 4    activeReqs atomic.Int64
 5}
 6
 7func Shutdown(ctx context.Context) error {
 8    g.draining.Store(true)
 9
10    // Wait for active requests to complete
11    ticker := time.NewTicker(100 * time.Millisecond)
12    defer ticker.Stop()
13
14    for {
15        select {
16        case <-ctx.Done():
17            return ctx.Err()
18        case <-ticker.C:
19            if g.activeReqs.Load() == 0 {
20                return nil
21            }
22        }
23    }
24}
25
26func ServeHTTP(w http.ResponseWriter, r *http.Request) {
27    if g.draining.Load() {
28        http.Error(w, "Service shutting down", http.StatusServiceUnavailable)
29        return
30    }
31
32    g.activeReqs.Add(1)
33    defer g.activeReqs.Add(-1)
34
35    g.LoadBalancer.ServeHTTP(w, r)
36}

3. Circuit Breaker Integration:

 1type BackendWithCircuitBreaker struct {
 2    *Backend
 3    breaker *CircuitBreaker
 4}
 5
 6func ServeHTTP(w http.ResponseWriter, r *http.Request) error {
 7    return b.breaker.Call(r.Context(), func() error {
 8        b.proxy.ServeHTTP(w, r)
 9        return nil
10    })
11}

4. Consistent Hashing for Better Distribution:

 1type ConsistentHash struct {
 2    circle map[uint32]string
 3    nodes  []uint32
 4    mu     sync.RWMutex
 5}
 6
 7func Add(node string, replicas int) {
 8    c.mu.Lock()
 9    defer c.mu.Unlock()
10
11    for i := 0; i < replicas; i++ {
12        hash := c.hashKey(fmt.Sprintf("%s:%d", node, i))
13        c.circle[hash] = node
14        c.nodes = append(c.nodes, hash)
15    }
16    sort.Slice(c.nodes, func(i, j int) bool {
17        return c.nodes[i] < c.nodes[j]
18    })
19}
20
21func Get(key string) string {
22    c.mu.RLock()
23    defer c.mu.RUnlock()
24
25    hash := c.hashKey(key)
26    idx := sort.Search(len(c.nodes), func(i int) bool {
27        return c.nodes[i] >= hash
28    })
29
30    if idx == len(c.nodes) {
31        idx = 0
32    }
33
34    return c.circle[c.nodes[idx]]
35}

5. Monitoring Metrics:

 1type LoadBalancerMetrics struct {
 2    RequestsTotal      prometheus.Counter
 3    RequestDuration    prometheus.Histogram
 4    BackendErrors      *prometheus.CounterVec
 5    ActiveConnections  *prometheus.GaugeVec
 6    BackendHealth      *prometheus.GaugeVec
 7}
 8
 9func RecordRequest(backend string, duration time.Duration, err error) {
10    m.RequestsTotal.Inc()
11    m.RequestDuration.Observe(duration.Seconds())
12
13    if err != nil {
14        m.BackendErrors.WithLabelValues(backend).Inc()
15    }
16}

Performance Characteristics:

Scaling Considerations:

• Use connection pooling for backend connections
• Implement request coalescing for duplicate requests
• Add rate limiting per backend
• Monitor backend latency percentiles
• Implement automatic backend discovery