Implement Power-of-Two-Choices Load Balancing - Load Balancers

                      TASK
                    

Implementation

Power-of-two-choices is a randomized load balancing algorithm that approximates least-connections with constant-time selection. Instead of checking all N backends, it randomly samples 2 and picks the better one.

The algorithm:

function selectBackend(backends: Backend[]): string {
  // Pick 2 random backends (with replacement)
  const backend1 = backends[randomInt(0, backends.length - 1)];
  const backend2 = backends[randomInt(0, backends.length - 1)];

  // Choose the one with fewer connections
  if (backend1.activeConnections <= backend2.activeConnections) {
    return backend1.name;
  } else {
    return backend2.name;
  }
}

Why it works:

Checking 2 random backends gives you a lot of information
Probability of picking the 2 worst backends is very low
With 10 backends, checking 2 gives you the top 20% in expectation
As N grows, the gap between checking 2 and checking all shrinks

Comparison:

Algorithm           | Selection Time | Quality
--------------------|----------------|----------------
Round-robin         | O(1)          | Poor (no load awareness)
Least-connections   | O(N)          | Optimal
Power-of-two-choices| O(1)          | Near-optimal (~95% of optimal)

With 100 backends:
  Least-connections: 100 queries
  Power-of-two: 2 queries
  Speedup: 50x
  Quality loss: <5%

Example power-of-two routing:

// Backends state:
{
  "backends": [
    {"name": "api-1", "connections": 10},
    {"name": "api-2", "connections": 5},
    {"name": "api-3", "connections": 8},
    {"name": "api-4", "connections": 12},
    {"name": "api-5", "connections": 3}
  ]
}

// Request 1: randomly pick api-3 (8) and api-5 (3)
// Select api-5 (fewer connections)
Request:  {"type": "http_request", "msg_id": 1, "algorithm": "power-of-two-choices"}
Response: {"type": "http_response", "in_reply_to": 1, "backend": "api-5", "sampled": ["api-3", "api-5"], "selected": "api-5", "reason": "3 < 8 connections"}

Sample Test Cases

Power-of-two selects better of 2 randomTimeout: 5000ms

Input

{"src":"client","dest":"lb","body":{"type":"init","msg_id":1,"backends":[{"name":"api-1","connections":10},{"name":"api-2","connections":5},{"name":"api-3","connections":8}],"algorithm":"power-of-two-choices"}}
{"src":"client","dest":"lb","body":{"type":"http_request","msg_id":2,"algorithm":"power-of-two-choices"}}

Expected Output

{"src": "lb", "dest": "client", "body": {"type": "init_ok", "in_reply_to": 1}}

Comparison with least-connectionsTimeout: 10000ms

Input

{
  "src": "client",
  "dest": "lb",
  "body": {
    "type": "benchmark",
    "msg_id": 1,
    "algorithms": [
      "least-connections",
      "power-of-two-choices"
    ],
    "backends": [
      {
        "name": "api-1",
        "connections": 10
      },
      {
        "name": "api-2",
        "connections": 5
      },
      {
        "name": "api-3",
        "connections": 8
      }
    ],
    "requests": 1000
  }
}

Expected Output

{"src": "lb", "dest": "client", "body": {"type": "benchmark_ok", "in_reply_to": 1, "results": {"least-connections": {"avg_connections": 7.67}, "power-of-two-choices": {"avg_connections": 8.1}}}}

Hints

Hint 1▾

Pick 2 random backends (with replacement)

Hint 2▾

Query their active connection counts

Hint 3▾

Send request to the backend with fewer connections

Hint 4▾

Nearly as good as least-connections but O(1) instead of O(N)

Hint 5▾

Prove this with a simulation or benchmark

Resources

The Power of Two Random Choices

Original paper on the power-of-two-choices technique

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

power-of-two-choicesrandomized load balancingleast-connections approximationconstant-time selectionscalability

main.py

python