Supported load balancers

This is a simple policy in which each available upstream host is selected in round robin order. If weights are assigned to endpoints in a locality, then a weighted round robin schedule is used, where higher weighted endpoints will appear more often in the rotation to achieve the effective weighting.

The least request load balancer uses different algorithms depending on whether hosts have the same or different weights.

The ring/modulo hash load balancer implements consistent hashing to upstream hosts. Each host is mapped onto a circle (the “ring”) by hashing its address; each request is then routed to a host by hashing some property of the request, and finding the nearest corresponding host clockwise around the ring. This technique is also commonly known as hashing, and like all hash-based load balancers, it is only effective when protocol routing is used that specifies a value to hash on.

Each host is hashed and placed on the ring some number of times proportional to its weight. For example, if host A has a weight of 1 and host B has a weight of 2, then there might be three entries on the ring: one for host A and two for host B. This doesn’t actually provide the desired 2:1 partitioning of the circle, however, since the computed hashes could be coincidentally very close to one another; so it is necessary to multiply the number of hashes per host—for example inserting 100 entries on the ring for host A and 200 entries for host B—to better approximate the desired distribution. Best practice is to explicitly set minimum_ring_size and , and monitor the min_hashes_per_host and max_hashes_per_host gauges to ensure good distribution. With the ring partitioned appropriately, the addition or removal of one host from a set of N hosts will affect only 1/N requests.

When priority based load balancing is in use, the priority level is also chosen by hash, so the endpoint selected will still be consistent when the set of backends is stable.

The table construction algorithm places each host in the table some number of times proportional to its weight, until the table is completely filled. For example, if host A has a weight of 1 and host B has a weight of 2, then host A will have 21,846 entries and host B will have 43,691 entries (totaling 65,537 entries). The algorithm attempts to place each host in the table at least once, regardless of the configured host and locality weights, so in some extreme cases the actual proportions may differ from the configured weights. For example, if the total number of hosts is larger than the fixed table size, then some hosts will get 1 entry each and the rest will get 0, regardless of weight. Best practice is to monitor the to ensure no hosts are underrepresented or missing.

In general, when compared to the ring hash (“ketama”) algorithm, Maglev has substantially faster table lookup build times as well as host selection times (approximately 10x and 5x respectively when using a large ring size of 256K entries). The downside of Maglev is that it is not as stable as ring hash. More keys will move position when hosts are removed (simulations show approximately double the keys will move). With that said, for many applications including Redis, Maglev is very likely a superior drop in replacement for ring hash. The advanced reader can use this benchmark to compare ring hash versus Maglev with different parameters.

The random load balancer selects a random available host. The random load balancer generally performs better than round robin if no health checking policy is configured. Random selection avoids bias towards the host in the set that comes after a failed host.