So, the core idea is to select R random nodes from the list of N total nodes behind the load balancer. Then query the "load" on these R nodes and pick the one with the least "load". Depending on the use-case, "load" could be modeled as the number of connections to a node. A couple of additional constraints to consider:
- "load" in a busy environment is continuously changing. To provide some sanity during selection, pessimistic locking could be employed by the load balancer during the selection and allocation phases
- selection could result in ties with same load. In order to break ties and avoid over-allocation to the first node, a second round of randomization should be performed to pick 1 of the T nodes with same load
Note that this algorithm can work well for an HTTP/L7 or an L4 load balancer. It is important to understand the use-case and associated tradeoffs before selecting an algorithm.
From the paper: https://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf Suppose that n balls are thrown into n bins, with each ball choosing a bin independently and uniformly at random. Then the maximum load, or the largest number of balls in any bin, is approximately log n / log (log n) with high probability. Now suppose instead that the balls 2 bins chosen independently and uniformly at random, the maximum load is log (log n) / log d + \theta(1) with high probability. The important implication of this result is that even a small amount of choice can lead to drastically diㄦent results in load balancing. Indeed, having just two random choices (i.e., d = 2) yields a large reduction in the maximum load over having one choice, while each additional choice beyond two decreases the maximum load by just a constant factor.
Basic idea is to round-robin between available nodes (next-in-loop) without giving weight to their respective loads or weights (could imply available capacity). This generally assumes homogeneity with regard to server capacities.
Weighted round-robin shares the simplicity of round-robin algorithm but gives due consideration to the fact that a fleet of nodes is not always homogeneous and operators could assign relative weights to nodes to let them service a higher percentage of requests. A second consideration here would be load-shedding wherein a set of nodes need to be taken offline for maintenance - having their weights gradually reduced over time can help with draining their activity before taking them completely out of rotation.
| Feature | Options |
|---|---|
| Strategy | Random, RR, WRR, Sticky |
| Protocol | TCP, HTTP, HTTPS, UDP |
| Persistence | Cookies, Source IP |
| Health checking | Active, Passive |
| High Availability | Health check state, Source IP persistence state, L4 flow state |
| SSL handling | SSL Offloading, SSL End-to-end, Client certificates |
| Backend Pools | Dynamic, Static |
| SNAT support | Transparent (no SNAT), Automapping (via LB IP), IP Lists |
| L7 support | Regex rules for URL blacklists, rewrites, sticky sessions |
Add mvn dependency:
<dependency>
<groupId>com.github.lb</groupId>
<artifactId>load-balancer</artifactId>
<version>1.0-SNAPSHOT</version>
</dependency>