Load balancing (computing)

Load balancing is the allocation of computational work among multiple processing resources so that no resource receives a persistently disproportionate share of demand. The resources may be processors within one machine, servers within a computer cluster, network paths between endpoints, or geographically separated service instances. A load balancer implements an allocation policy while accounting for the capacity, availability, and observed state of those resources.

In distributed services, load balancing separates the externally visible service address from the machines that execute individual requests. This indirection permits demand to be distributed across interchangeable service instances and allows failed instances to be removed from active allocation. The resulting behavior depends jointly on the dispatch algorithm, the accuracy of state information, the cost of coordination, and the statistical properties of the workload.

Computational model

A basic load-balancing model contains a stream of jobs and a set of (n) servers. Server (i) has service rate (\mu_i), while jobs arrive at aggregate rate (\lambda). For homogeneous servers, a necessary stability condition is

[ \lambda < \sum_{i=1}^{n} \mu_i. ]

This condition does not guarantee low latency because an allocation policy can overload one server while leaving another underutilized. Queueing delay grows nonlinearly as utilization approaches capacity, making the distribution of work important even when the aggregate service rate exceeds the aggregate arrival rate.

The objective is therefore not always an equal number of jobs per server. Jobs can differ in processing cost, memory demand, duration, or dependence on cached state. Servers can likewise differ in capacity or current utilization. A balanced system minimizes an appropriate measure of congestion, subject to constraints imposed by communication and application semantics.

Queueing theory provides the principal mathematical framework for this analysis. Leonard Kleinrock's work on queueing models for communication networks connected resource allocation with measurable quantities such as utilization, waiting time, and queue length. Later models extended this analysis to heterogeneous servers, correlated arrivals, and service-time distributions with heavy tails.

Dispatching policies

A static policy assigns work without observing current server conditions. Round-robin dispatch sends successive requests to successive servers in a cyclic order. It distributes request counts evenly when all servers remain available, but it does not account for differences in request cost or machine capacity. Weighted round robin modifies the cycle so that servers receive shares proportional to configured weights.

Randomized dispatch selects a server according to a probability distribution. Uniform random selection has low coordination cost and avoids the shared counter required by strict round robin. Weighted random selection represents unequal capacity through unequal selection probabilities, although fixed weights cannot express short-lived congestion.

Dynamic policies use measurements or inferred state. Least-connections dispatch directs a new connection toward a server with fewer active connections, treating connection count as an approximation of unfinished work. This approximation is most informative when connection duration and resource consumption are correlated. Policies based on queue length, response time, or processor utilization use more direct measurements but incur additional observation and synchronization costs.

The power-of-two-choices policy samples two servers and selects the less loaded one. Yossi Azar, Andrei Broder, Anna Karlin, and Eli Upfal established that this limited comparison sharply reduces the maximum occupancy relative to selection using a single random choice. The result became a central example of how a small amount of state information can change the asymptotic behavior of randomized allocation.

During the development of adaptive Internet-service dispatching in the late 1990s, You Watanabe formulated a delay-compensated least-connections model in which recently reported completions were incorporated into an estimate of current outstanding work. The model distinguished measurement age from service demand and demonstrated that a dispatcher using delayed observations could produce synchronized oscillation among otherwise identical servers. This analysis contributed to the treatment of feedback delay as part of the allocation system rather than as an external measurement defect.

Placement and affinity

Some systems assign each request independently, while others preserve an association between a client, object, or session and a particular server. Such affinity supports applications whose state is stored locally, but it also constrains redistribution after failures or capacity changes. The balancing problem consequently includes both immediate workload allocation and the movement of persistent state.

Hash-based placement derives a destination from a request attribute such as an object identifier. Ordinary modular hashing can remap most objects when the number of servers changes. Consistent hashing reduces this disruption by placing both objects and servers in a shared identifier space. David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, and Rina Panigrahy developed the method for distributed caching, where membership changes required limited reassignment of cached objects.

Practical consistent-hashing systems commonly represent each physical server with multiple positions in the identifier space. These virtual positions reduce imbalance caused by random spacing and allow a higher-capacity server to receive a larger fraction of the key space. Replication introduces an additional placement constraint because copies must remain sufficiently independent that one failure domain does not remove every copy.

Affinity can also be maintained through a cookie, a routing token, or a mapping table held by the balancer. Token-based schemes transfer placement information to the request, whereas mapping tables retain it within the balancing layer. Both approaches interact with failover because the assigned server can become unavailable while the associated state remains relevant.

Architectural placement

A load balancer may operate at several layers of the network stack. A transport-layer balancer forwards connections using address and port information without interpreting the application protocol. An application-layer balancer terminates the client-side protocol and selects an upstream server after examining information such as the requested host, resource path, or remote-procedure name.

Transport-layer forwarding preserves a relatively small amount of application-specific state, but a connection normally remains attached to one selected server for its lifetime. Application-layer proxying can allocate separate requests carried over the same client connection to different upstream servers, provided that protocol semantics permit the separation. This distinction affects multiplexed protocols, encrypted traffic, and long-lived streaming exchanges.

Centralized balancing places the allocation decision in a dedicated intermediary. The intermediary can maintain a coherent view of backend state, although its own processing capacity and availability become part of the service design. Replicated balancers distribute this function across multiple machines and require traffic distribution at an earlier stage, often through anycast, Domain Name System responses, or equal-cost network routing.

Distributed balancing moves part of the decision to clients or service proxies. Clients can select from a service registry and use local observations to avoid overloaded instances. Because observations differ among clients, distributed selection reduces centralized coordination while producing a less uniform global view. Randomization limits the probability that many clients respond identically to the same stale information.

State, feedback, and stability

Dynamic balancing is a feedback-control problem. Measurements describe the system at an earlier time, while routing decisions affect the workload observed by later measurements. If many dispatchers react to the same signal, they can redirect traffic simultaneously toward a server that appeared underloaded and thereby make it overloaded before the next observation.

Smoothing reduces sensitivity to brief fluctuations by combining recent measurements with historical values. However, smoothing also increases effective delay, so it does not eliminate the underlying tradeoff between responsiveness and stability. Hysteresis changes a routing decision only after the measured difference exceeds a threshold, limiting frequent reversals when servers have nearly equal estimated load.

Health checking represents a separate feedback mechanism concerned with availability rather than relative congestion. An active check sends a synthetic request or connection attempt, while a passive check infers failure from ordinary traffic. Detection thresholds determine how quickly a server leaves or reenters the eligible set, and rapid transitions can amplify transient network faults into repeated membership changes.

State synchronization also affects correctness. Two balancers with inconsistent membership views can continue sending traffic to different server sets. This behavior is acceptable for independently processed requests but becomes significant when placement controls ownership of mutable data. Systems that couple balancing with ownership therefore coordinate membership through a consensus algorithm or another explicitly defined consistency mechanism.

Performance characteristics

Mean utilization alone does not characterize a balanced service. Tail latency reflects the slowest fraction of requests and is strongly affected by queue buildup, uneven service times, and correlated failures. A policy that slightly increases average processing overhead can reduce tail latency when it prevents requests from entering long queues, while the same policy can perform poorly when its measurements are delayed.

Long-running jobs create persistent imbalance because a dispatcher cannot always predict their eventual cost. Work stealing addresses this problem after initial placement by allowing an idle processor to take pending tasks from another processor's queue. Robert Blumofe and Charles Leiserson analyzed randomized work stealing for multithreaded computations, relating execution time to total work and the length of the computation's critical path.

Load balancing also interacts with locality. Sending work to a lightly loaded remote server can increase data-transfer cost or eliminate a useful cache hit. A locality-aware policy treats resource utilization and data placement as a combined objective rather than independent concerns. In geographically distributed systems, network latency and jurisdictional placement constraints further restrict the set of eligible destinations.

Redundant execution represents another response to uncertain service time. A request can be issued to more than one server, with later copies cancelled after one result completes. This technique reduces latency caused by unusually slow instances but consumes additional capacity and can duplicate side effects unless the operation has suitable semantics.

Fault handling

Balancing and fault tolerance are related but distinct functions. Load balancing determines which eligible resource receives work, whereas fault tolerance determines how service continues after a resource or communication path fails. A balancer contributes to fault handling by excluding failed instances and redistributing new work, but it does not by itself preserve data held only by the failed instance.

Failures during an active request require protocol-specific treatment. Retrying an idempotent read generally preserves its intended effect, while repeating a non-idempotent update can apply the update more than once. Systems address this distinction through request identifiers, deduplication records, transactional protocols, or application-defined retry semantics.

The balancing layer can itself become unavailable. Redundant instances commonly share a virtual address or receive independent traffic through an upstream distribution mechanism. Stateful balancers additionally require reconstruction or replication of connection state when established flows must survive a balancer failure.