System requirements

Functional:

• Distribute incoming network traffic across a set of servers based of configurable algorithms.
• Supported algorithms: round-robin, least connection, IP hashing.
• Support session persistence
• Support SSL termination
• Monitor failed servers and direct traffic away from them.

Non-Functional:

• High availability (99.99%)
• Supports up to 1M concurrent connections
• Network bandwidth: support up to 5Mb / request+response
• Configuration changes can be eventually consistent
• Very low latency (<5ms)
• Automatic scaling out and in

Capacity estimation

• Assume each server can handle up to 100k concurrent connections, we need at least 10 servers. We start with 50% utilization, so that is 20 servers.
• Assume on average each connection lasts 10 seconds. Network bandwidth: 1M / 10 * 5Mb = 500Mb / sec = 4GB/sec = 32Gbps. Assuming standard instance having 10Gbps, spreading 32Gbps over 20 instances is well within the capacity.
• This system isn't memory heavy, so we omit the estimation on memory requirement.
• Certain parts of the system like SSL termination needs processing power, so we should monitor the CPU load.
• Log storage: 4Gb/sec * 86400 sec/day = 350T/day or 100Pb/year. In reality average length of logs is probably 5k, which results in 200Tb/year.

API design

The API for network traffic forwarding is omitted.

API for management:

// Create load balancer

POST /loadBalancers -> LoadBalancer

{

id, // output

name,

algorithm,

config, // algorithm parameters

}

// Other CRUD methods for load balancer is omitted.

POST /loadBalancers//registration -> Registration

{

id, // output

serverIp,

weight, // for weighted round-robin

}

// Other CRUD methods for registrations are omitted.

// status

GET /loadBalancers//status -> Status

{

id,

status, // online | offline | etc.

uptime,

lastHeartbeat,

...

}

// log

Get /loadBalancer//logs&startTime={}&endTime={}&pageSize={}&pageToken={} -> Log

{

id,

log, // Array of logs

}

Database design

A database is used to store configuration information:

LoadBalancer table:

• id (PK)
• name
• algorithm
• config

Registration table:

• id (PK)
• loadBalancerId (FK into LoadBalancer table)
• serverIP[]

A relational database can be used here. Say we support up to 10k of load balancers, and each load balancer supports up to 1k of server IPs, the storage need: 10k * 1k * 1k (data) = 10Gb which is very small for a database.

Logs

• Stored locally on load balancer servers and shipped to blob storage every 5 minutes
• timestamp
• client ip
• url
• headers
• status code
• request message
• response message

High-level design

Request Handler:

• Responsible for receiving the request, perform SSL termination, and forward the request to load balancing engine
• Logs the request and response

Load balancing engine

• Responsible for applying the load balancing algorithm
• Forwards request to the application server

Request handler and load balancing engine is located on the same server.

Config DB

• Source of truth for the configuration of the load balancer

Management API

• Used by load balancer admins to configure load balancer

Health Monitor

• Monitor the health of the system
• Bring up / take down load balance instances when necessary
• Implements the /status endpoint
• Trigger alerts when anomalies are detected

Logging Service

• Responsible for shipping logs on load balancer servers to blob storage
• Implements the read log endpoint

Session Manager

• Establish sessions and store mapping of session id / cookie / client ip -> backend server
• Ensure stickness of the session until the session expires
• Leverages redis as a fast in-memory store of the session id -> app server mapping

Request flows

Client request flow:

1. Client initiates a request, which is received by request handler
2. Request handler performs SSL termination, decodes headers and request body, and logs this information to local disk. Then it passes request information to load balancing engine.
3. Load balancing engine applies the load balancer rules. In order to know all servers, it loads the list of app server ips from the config DB, and then cache it in memory. The algorithm will determine the server that should receive the request.
4. Load balancing engine forwards the request to the app server, waits for the response, and forwards the response back to request handler.
5. If session is enabled, the target app server for the first request is stored in redis. On subsquent requests for the same session, the session manager looks up redis for the target server.
6. If request fails due to non-application specific error code, it may retry the request on the next app server.
7. The request handler logs the response (if configured), then returns the response to the client.

Management flow:

• Create load balancer
  1. The load balancer configuration is stored in database
  2. A reconciliation loop is kicked off, where it instantiates N server VMs to host the load balancer. Each server VM is going to host the request handler, load balancing engine, and session manager.
  3. Each LB server instance participate in load balancing via DNS-based distribution, or Anycast
  • Other operations in CRUD omitted
• Create a registration
  • First the config DB is updated
  • Then management API invalidates the cached app server ips in redis.

Health checks

• Periodically the health monitor service pings app servers. If an app server is unhealthy, it updates the status of the app server (Redis)

Detailed component design

Load balancing algorithm

• Round robin: in redis we can place a counter, where each time a new request comes in, it in incremented by 1 and the mod of that number by the number of healthy backend indicates the server to forward to.
• Least connection: we can keep a count of connections for each app server in redis, and store them as sorted set. Then each time we grab the server with the least number of connections.
• IP hashing: we hash client IP to a value and apply mod over the number of healthy servers

Trade offs/Tech choices

Single instance, active-passive, or multi-instance software load balancer

• Single instance is not reliable enough. Plus, we need 20 load balancer instances to support the scale.

Failure scenarios/bottlenecks

Handle peak traffic

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?